import { Tile } from "../models" ; import { List } from "../helpers/list.class" ; import { GameService } from "../service/game.service" ; import { GridHelper } from "../helpers/grid.helper" ; export module PathFinder { export function searchPath ( game , start , end ) { let debugStartTime = performance . now ( ) ; /** Path validation */ if ( GridHelper . compareIndex ( start , end ) ) { console . log ( "the start tile = the end." ) ; return [ ] ; } if ( ! start . walkable ) { console . log ( 'The start tile in not walkable, choose different tile than' , start . index ) ; return [ ] ; } if ( ! end . walkable ) { console . log ( 'The end tile in not walkable, choose different tile than' , end . index ) ; return [ ] ; } /** Start A* Algorithm */ let openList = new List < Tile > ( ) ; let closedList = new List < Tile > ( ) ; /** Add the starting tile to the openList */ openList . push ( start ) ; let currentTile ; /** While openList is not empty */ while ( openList . length ) { currentTile = getTileWithLowestTotal ( openList ) ; if ( GridHelper . compareIndex ( currentTile , end ) ) { let debugEndTime = performance . now ( ) ; console . log ( `Path found in ${ ( debugEndTime - debugStartTime ) . toFixed ( 3 ) }ms` ) ; return shortestPath ( game , start , end , openList , closedList ) ; } else { openList . remove ( currentTile ) ; closedList . push ( currentTile ) ; let adjacentTiles = getAdjacentTiles ( game , currentTile ) ; for ( let adjacentTile of adjacentTiles ) { if ( ! openList . contains ( adjacentTile ) ) { if ( ! closedList . contains ( adjacentTile ) ) { openList . push ( adjacentTile ) ; adjacentTile . search . cost = currentTile . search . cost + 1 ; adjacentTile . search . heuristic = manhattanDistance ( adjacentTile , end ) ; adjacentTile . search . total = adjacentTile . search . cost + adjacentTile . search . heuristic ; } } } } } } const getTileWithLowestTotal = ( openList ) : Tile => { let tileWithLowestTotal = new Tile ( ) ; let lowestTotal = 999999999 ; /** Search open tiles and get the tile with the lowest total cost */ for ( let openTile of openList ) { if ( openTile . search . total <= lowestTotal ) { lowestTotal = openTile . search . total ; tileWithLowestTotal = openTile ; } } return tileWithLowestTotal ; } ; const getAdjacentTiles = ( game , current ) : Tile [ ] => { let adjacentTiles = [ ] ; let adjacentTile ; if ( current . index . x - 1 >= 0 ) { adjacentTile = game . grid [ current . index . x - 1 ] [ current . index . y ] ; if ( adjacentTile && adjacentTile . walkable ) { adjacentTiles . push ( adjacentTile ) ; } } if ( current . index . x + 1 < game . width ) { adjacentTile = game . grid [ current . index . x + 1 ] [ current . index . y ] ; if ( adjacentTile && adjacentTile . walkable ) { adjacentTiles . push ( adjacentTile ) ; } } if ( current . index . y + 1 < game . height ) { adjacentTile = game . grid [ current . index . x ] [ current . index . y + 1 ] ; if ( adjacentTile && adjacentTile . walkable ) { adjacentTiles . push ( adjacentTile ) ; } } if ( current . index . y - 1 >= 0 ) { adjacentTile = game . grid [ current . index . x ] [ current . index . y - 1 ] ; if ( adjacentTile && adjacentTile . walkable ) { adjacentTiles . push ( adjacentTile ) ; } } return adjacentTiles ; } ; /** Calculate the manhattan distance */ const manhattanDistance = ( adjacentTile , endTile ) : number => { return Math . abs ( ( endTile . index . x - adjacentTile . index . x ) + ( endTile . index . y - adjacentTile . index . y ) ) ; } ; const shortestPath = ( game , startTile , endTile , openList , closedList ) => { let startFound = false ; let currentTile = endTile ; let pathTiles = [ ] ; pathTiles . push ( endTile ) ; while ( ! startFound ) { let adjacentTiles = getAdjacentTiles ( game , currentTile ) ; for ( let adjacentTile of adjacentTiles ) { if ( GridHelper . compareIndex ( adjacentTile , startTile ) ) return pathTiles ; if ( closedList . contains ( adjacentTile ) || openList . contains ( adjacentTile ) ) { if ( adjacentTile . search . cost <= currentTile . search . cost && adjacentTile . search . cost > 0 ) { currentTile = adjacentTile ; pathTiles . push ( adjacentTile ) ; break ; } } } } } ; }