import Pathfinder , { reconstructPath } 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' ; class AStarPathfinder extends Pathfinder { private readonly heuristicFunc : HeuristicFunc = ( a , b ) => euclidean ( a , b ) ; private readonly p : number ; constructor ( navigator , func ? ) { super ( navigator ) ; const grid = this . getNavigator ( ) . getGrid ( ) ; this . p = 1 / ( grid . getWidth ( ) * grid . getHeight ( ) ) ; if ( func !== undefined ) { this . heuristicFunc = func ; } } getAlgorithmName ( ) { return 'A*' ; } param initial param goal findPath ( initial , goal ) { this . clearRecentSearch ( ) ; const grid = this . navigator . getGrid ( ) ; const openFrontier = new Heap < AStarNode > ( ( a , b ) => a . f ( ) < b . f ( ) ) ; const closedSet = new HashSet ( ) ; const openSet = new HashTable < number > ( ) ; const root = new AStarNode ( grid . get ( initial ) , 0 , 0 ) ; openFrontier . push ( root ) ; openSet . add ( stringify ( initial ) , root . g ) ; while ( ! openFrontier . isEmpty ( ) ) { const currentNode = openFrontier . pop ( ) ; const currentPoint = currentNode . tile . point ; const currentKey = stringify ( currentPoint ) ; openSet . remove ( currentKey ) ; if ( closedSet . has ( currentKey ) ) { continue ; } closedSet . add ( currentKey ) ; this . addRecent ( currentNode ) ; if ( this . navigator . equals ( currentPoint , goal ) ) { return reconstructPath ( currentNode ) ; } for ( const neighbor of this . navigator . neighbors ( currentPoint ) ) { const neighborPoint = neighbor . point ; const neighborKey = stringify ( neighborPoint ) ; if ( closedSet . has ( neighborKey ) ) { continue ; } const g = currentNode . g + this . stepCost ( currentPoint , neighborPoint ) ; const f = g + this . heuristic ( neighborPoint , goal ) ; if ( ! openSet . has ( neighborKey ) || g < openSet . get ( neighborKey ) ! ) { const neighborNode = new AStarNode ( neighbor , g , f ) ; currentNode . addChild ( neighborNode ) ; openFrontier . push ( neighborNode ) ; openSet . add ( neighborKey , neighborNode . g ) ; } } } return [ ] ; } param a param b heuristic ( a , b ) { return this . heuristicFunc ( a , b ) * ( 1 + this . p ) ; } param currentPoint param neighborPoint stepCost ( currentPoint , neighborPoint ) { return this . navigator . cost ( currentPoint , neighborPoint ) ; } } export default AStarPathfinder ;