import Pathfinder , { reconstructPath } from './Pathfinder' ; import { Node } from './Node' ; import { Point } from '../core/Components' ; import { HashSet , stringify } from '../structures/Hash' ; import Stack from '../structures/Stack' ; class DFSPathfinder extends Pathfinder { getAlgorithmName ( ) { return 'Depth First Search' ; } param initial param goal findPath ( initial , goal ) { this . clearRecentSearch ( ) ; const grid = this . navigator . getGrid ( ) ; const root = new Node ( grid . get ( initial ) ) ; const frontier = new Stack < Node > ( ) ; const visited = new HashSet ( ) ; frontier . push ( root ) ; while ( ! frontier . isEmpty ( ) ) { const currentNode = frontier . pop ( ) ! ; const currentPoint = currentNode . tile . point ; visited . add ( stringify ( currentPoint ) ) ; this . addRecent ( currentNode ) ; if ( this . navigator . equals ( currentPoint , goal ) ) { return reconstructPath ( currentNode ) ; } for ( const neighbor of this . navigator . neighbors ( currentPoint ) . reverse ( ) ) { const neighborKey = stringify ( neighbor . point ) ; if ( ! visited . has ( neighborKey ) ) { const neighborNode = new Node ( neighbor ) ; currentNode . addChild ( neighborNode ) ; frontier . push ( neighborNode ) ; } } } return [ ] ; } } export default DFSPathfinder ;