import Pathfinder , { reconstructPath } from './Pathfinder' ; import { euclidean , HeuristicFunc } from './Heuristics' ; import { BestFirstNode } from './Node' ; import { Point } from '../core/Components' ; import Navigator from '../core/Navigator' ; import { HashSet , stringify } from '../structures/Hash' ; import Heap from '../structures/Heap' ; class BestFirstPathfinder extends Pathfinder { private readonly heuristicFunc : HeuristicFunc = ( a , b ) => euclidean ( a , b ) ; constructor ( navigator , func ? ) { super ( navigator ) ; if ( func !== undefined ) { this . heuristicFunc = func ; } } getAlgorithmName ( ) { return 'Best-First Search' ; } param initial param goal findPath ( initial , goal ) { this . clearRecentSearch ( ) ; const grid = this . navigator . getGrid ( ) ; const frontier = new Heap < BestFirstNode > ( ( a , b ) => a . h < b . h ) ; const closedSet = new HashSet ( ) ; const root = new BestFirstNode ( grid . get ( initial ) , 0 ) ; frontier . push ( root ) ; closedSet . add ( stringify ( initial ) ) ; while ( ! frontier . isEmpty ( ) ) { const currentNode = frontier . pop ( ) ; const currentPoint = currentNode . tile . point ; 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 ) ; const h = this . heuristic ( neighborPoint , goal ) ; if ( ! closedSet . has ( neighborKey ) ) { const neighborNode = new BestFirstNode ( neighbor , h ) ; currentNode . addChild ( neighborNode ) ; frontier . push ( neighborNode ) ; closedSet . add ( neighborKey ) ; } } } return [ ] ; } param a param b heuristic ( a , b ) { return this . heuristicFunc ( a , b ) ; } } export default BestFirstPathfinder ;