import Pathfinder , { reconstructPath , reconstructPathReversed } from './Pathfinder' ; import { DijkstraNode } from './Node' ; import { Point } from '../core/Components' ; import { HashTable , stringify } from '../structures/Hash' ; import Heap from '../structures/Heap' ; interface ControlStructures { frontier : Heap < DijkstraNode > ; closedSet : HashTable < DijkstraNode > ; } class BiDijkstraPathfinder extends Pathfinder { getAlgorithmName ( ) { return 'Bidirectional Dijkstra' ; } param initial param goal findPath ( initial , goal ) { this . clearRecentSearch ( ) ; const grid = this . navigator . getGrid ( ) ; const startVisited = new HashTable < DijkstraNode > ( ) ; const endVisited = new HashTable < DijkstraNode > ( ) ; const startFrontier = new Heap < DijkstraNode > ( ( a , b ) => a . g < b . g ) ; const endFrontier = new Heap < DijkstraNode > ( ( a , b ) => a . g < b . g ) ; const initialRoot = new DijkstraNode ( grid . get ( initial ) , 0 ) ; startFrontier . push ( initialRoot ) ; startVisited . add ( stringify ( initial ) , initialRoot ) ; const goalRoot = new DijkstraNode ( grid . get ( goal ) , 0 ) ; endFrontier . push ( goalRoot ) ; endVisited . add ( stringify ( goal ) , goalRoot ) ; while ( ! startFrontier . isEmpty ( ) && ! endFrontier . isEmpty ( ) ) { const startCurrentNode = startFrontier . pop ( ) ; const startCurrentPoint = startCurrentNode . tile . point ; const startCurrentPointKey = stringify ( startCurrentPoint ) ; this . addRecent ( startCurrentNode ) ; if ( endVisited . has ( startCurrentPointKey ) ) { if ( startCurrentNode . parent != null ) { return reconstructPath ( startCurrentNode . parent ) . concat ( reconstructPathReversed ( endVisited . get ( startCurrentPointKey ) ! ) ) . concat ( grid . get ( goal ) ) ; } else { return [ grid . get ( goal ) ] ; } } this . doDijkstraExpansion ( { frontier : startFrontier , closedSet : startVisited } , startCurrentNode ) ; const endCurrentNode = endFrontier . pop ( ) ; const endCurrentPoint = endCurrentNode . tile . point ; const endCurrentPointKey = stringify ( endCurrentPoint ) ; this . addRecent ( endCurrentNode ) ; if ( startVisited . has ( endCurrentPointKey ) ) { if ( endCurrentNode . parent != null ) { return reconstructPath ( startVisited . get ( endCurrentPointKey ) ! ) . concat ( reconstructPathReversed ( endCurrentNode . parent ) ) . concat ( grid . get ( goal ) ) ; } else { return [ grid . get ( goal ) ] ; } } this . doDijkstraExpansion ( { frontier : endFrontier , closedSet : endVisited } , endCurrentNode ) ; } return [ ] ; } private doDijkstraExpansion ( structures , currentNode ) { const currentPoint = currentNode . tile . point ; for ( const neighbor of this . navigator . neighbors ( currentPoint ) ) { const neighborPoint = neighbor . point ; const neighborKey = stringify ( neighborPoint ) ; const g = currentNode . g + this . stepCost ( currentPoint , neighborPoint ) ; if ( ! structures . closedSet . has ( neighborKey ) ) { const neighborNode = new DijkstraNode ( neighbor , g ) ; currentNode . addChild ( neighborNode ) ; structures . frontier . push ( neighborNode ) ; structures . closedSet . add ( neighborKey , neighborNode ) ; } } } param currentPoint param neighborPoint stepCost ( currentPoint , neighborPoint ) { return this . navigator . cost ( currentPoint , neighborPoint ) ; } } export default BiDijkstraPathfinder ;