import Pathfinder , { reconstructPath , reconstructPathReversed } from './Pathfinder' ; import { euclidean , HeuristicFunc } from './Heuristics' ; import { AStarNode } from './Node' ; import { Point } from '../core/Components' ; import Navigator from '../core/Navigator' ; import { HashSet , HashTable , stringify } from '../structures/Hash' ; import Heap from '../structures/Heap' ; interface ControlStructures { openSet : HashTable < AStarNode > ; closedSet : HashSet ; openFrontier : Heap < AStarNode > ; } class BiAStarPathfinder extends Pathfinder { private readonly heuristic : HeuristicFunc = ( a , b ) => euclidean ( a , b ) ; constructor ( navigator , func ? ) { super ( navigator ) ; if ( func !== undefined ) { this . heuristic = func ; } } getAlgorithmName ( ) { return 'Bidirectional A*' ; } param initial param goal findPath ( initial , goal ) { this . clearRecentSearch ( ) ; const grid = this . navigator . getGrid ( ) ; const closedSet = new HashSet ( ) ; const startOpenFrontier = new Heap < AStarNode > ( ( a , b ) => a . f ( ) < b . f ( ) ) ; const startOpenSet = new HashTable < AStarNode > ( ) ; const endOpenFrontier = new Heap < AStarNode > ( ( a , b ) => a . f ( ) < b . f ( ) ) ; const endOpenSet = new HashTable < AStarNode > ( ) ; const initialRoot = new AStarNode ( grid . get ( initial ) , 0 , 0 ) ; startOpenFrontier . push ( initialRoot ) ; startOpenSet . add ( stringify ( initial ) , initialRoot ) ; const goalRoot = new AStarNode ( grid . get ( goal ) , 0 , 0 ) ; endOpenFrontier . push ( goalRoot ) ; endOpenSet . add ( stringify ( goal ) , goalRoot ) ; while ( ! startOpenFrontier . isEmpty ( ) && ! endOpenFrontier . isEmpty ( ) ) { const startCurrentNode = startOpenFrontier . pop ( ) ; const startCurrentPoint = startCurrentNode . tile . point ; const startCurrentPointKey = stringify ( startCurrentPoint ) ; startOpenSet . remove ( startCurrentPointKey ) ; if ( closedSet . has ( startCurrentPointKey ) ) { continue ; } closedSet . add ( startCurrentPointKey ) ; this . addRecent ( startCurrentNode ) ; if ( endOpenSet . has ( startCurrentPointKey ) ) { if ( startCurrentNode . parent != null ) { return reconstructPath ( startCurrentNode . parent ! ) . concat ( reconstructPathReversed ( endOpenSet . get ( startCurrentPointKey ) ! ) ) . concat ( grid . get ( goal ) ) ; } else { return [ grid . get ( goal ) ] ; } } this . doAStarExpansion ( { openFrontier : startOpenFrontier , openSet : startOpenSet , closedSet : closedSet } , startCurrentNode , goal ) ; const endCurrentNode = endOpenFrontier . pop ( ) ; const endCurrentPoint = endCurrentNode . tile . point ; const endCurrentPointKey = stringify ( endCurrentPoint ) ; endOpenSet . remove ( endCurrentPointKey ) ; if ( closedSet . has ( endCurrentPointKey ) ) { continue ; } closedSet . add ( endCurrentPointKey ) ; this . addRecent ( endCurrentNode ) ; if ( startOpenSet . has ( endCurrentPointKey ) ) { if ( endCurrentNode . parent != null ) { return reconstructPath ( startOpenSet . get ( endCurrentPointKey ) ! ) . concat ( reconstructPathReversed ( endCurrentNode . parent ! ) ) . concat ( grid . get ( goal ) ) ; } else { return [ grid . get ( goal ) ] ; } } this . doAStarExpansion ( { openFrontier : endOpenFrontier , openSet : endOpenSet , closedSet : closedSet } , endCurrentNode , initial ) ; } return [ ] ; } param structures param currentNode param endPoint private private doAStarExpansion ( structures , currentNode , endPoint ) { const currentPoint = currentNode . tile . point ; for ( const neighbor of this . navigator . neighbors ( currentPoint ) ) { const neighborPoint = neighbor . point ; const neighborKey = stringify ( neighborPoint ) ; if ( structures . closedSet . has ( neighborKey ) ) { continue ; } const g = currentNode . g + this . stepCost ( currentPoint , neighborPoint ) ; const f = g + this . heuristic ( neighborPoint , endPoint ) ; if ( ! structures . openSet . has ( neighborKey ) || g < structures . openSet . get ( neighborKey ) ! . g ) { const neighborNode = new AStarNode ( neighbor , g , f ) ; currentNode . addChild ( neighborNode ) ; structures . openFrontier . push ( neighborNode ) ; structures . openSet . add ( neighborKey , neighborNode ) ; } } } param currentPoint param neighborPoint stepCost ( currentPoint , neighborPoint ) { return this . navigator . cost ( currentPoint , neighborPoint ) ; } } export default BiAStarPathfinder ;