import { CellPathCandidate } from "./cell-path-candidate" ; import { CellPathData } from "./cell-path-data" ; export class PathFinder { private mapPoints ; private grid ; private useOldMovementSystem ; private firstCellZone ; private OCCUPIED_CELL_WEIGHT ; private ELEVATION_TOLERANCE ; private WIDTH ; private HEIGHT ; private CELL_NUMBER ; constructor ( ) { this . mapPoints = { } ; this . grid = [ ] ; this . useOldMovementSystem = false ; this . firstCellZone ; this . OCCUPIED_CELL_WEIGHT = 10 ; this . ELEVATION_TOLERANCE = 11.825 ; this . WIDTH = 33 + 2 ; this . HEIGHT = 34 + 2 ; this . CELL_NUMBER = 560 ; this . _generateMapPoints ( ) ; this . _generateGrid ( ) ; } resetPath ( ) { this . mapPoints = { } ; this . grid = [ ] ; this . useOldMovementSystem = false ; this . _generateMapPoints ( ) ; this . _generateGrid ( ) ; } fillPathGrid ( map ) { this . firstCellZone = map . cells [ 0 ] . z || 0 ; this . useOldMovementSystem = true ; for ( let i = 0 ; i < this . WIDTH ; i += 1 ) { const row = this . grid [ i ] ; for ( let j = 0 ; j < this . HEIGHT ; j += 1 ) { const cellId = this . getCellId ( i - 1 , j - 1 ) ; const cellPath = row [ j ] ; const cell = map . cells [ cellId ] ; this . updateCellPath ( cell , cellPath ) ; } } } param { * } source param { * } target param { * } occupiedCells param { * } allowDiagonals param { * } stopNextToTarget getPath ( source , target , occupiedCells , allowDiagonals , stopNextToTarget ) { let c , candidate ; allowDiagonals = allowDiagonals === undefined ? true : ! ! allowDiagonals ; const srcPos = this . getMapPoint ( source ) ; const dstPos = this . getMapPoint ( target ) ; const si = srcPos . x + 1 ; const sj = srcPos . y + 1 ; const srcCell = this . grid [ si ] [ sj ] ; if ( srcCell . zone === - 1 ) { let bestFit = null ; let bestDist = Infinity ; let bestFloorDiff = Infinity ; for ( let i = - 1 ; i <= 1 ; i += 1 ) { for ( let j = - 1 ; j <= 1 ; j += 1 ) { if ( i === 0 && j === 0 ) { continue ; } const cell = this . grid [ si + i ] [ sj + j ] ; if ( cell . zone === - 1 ) { continue ; } const floorDiff = Math . abs ( cell . f - srcCell . f ) ; const dist = Math . abs ( i ) + Math . abs ( j ) ; if ( bestFit === null || floorDiff < bestFloorDiff || ( floorDiff <= bestFloorDiff && dist < bestDist ) ) { bestFit = cell ; bestDist = dist ; bestFloorDiff = floorDiff ; } } } if ( bestFit !== null ) { return [ source , this . getCellId ( bestFit . i - 1 , bestFit . j - 1 ) ] ; } console . error ( new Error ( "[pathFinder.getPath] Player is stuck in " + si + "/" + sj ) ) ; return [ source ] ; } const di = dstPos . x + 1 ; const dj = dstPos . y + 1 ; let cellPos , cellId ; for ( cellId in occupiedCells ) { cellPos = this . getMapPoint ( cellId ) ; this . grid [ cellPos . x + 1 ] [ cellPos . y + 1 ] . weight += this . OCCUPIED_CELL_WEIGHT ; } let candidates = [ ] ; const selections = [ ] ; const distSrcDst = Math . sqrt ( ( si - di ) * ( si - di ) + ( sj - dj ) * ( sj - dj ) ) ; let selection = new CellPathCandidate ( si , sj , 0 , distSrcDst , null ) ; let reachingPath = null ; let closestPath = selection ; while ( selection . i !== di || selection . j !== dj ) { this . addCandidates ( selection , di , dj , candidates , allowDiagonals ) ; const n = candidates . length ; if ( n === 0 ) { selection = closestPath ; break ; } let minPotentialWeight = Infinity ; let selectionIndex = 0 ; for ( c = 0 ; c < n ; c += 1 ) { candidate = candidates [ c ] ; if ( candidate . w + candidate . d < minPotentialWeight ) { selection = candidate ; minPotentialWeight = candidate . w + candidate . d ; selectionIndex = c ; } } selections . push ( selection ) ; candidates . splice ( selectionIndex , 1 ) ; if ( selection . d === 0 || ( stopNextToTarget && selection . d < 1.5 ) ) { if ( reachingPath === null || selection . w < reachingPath . w ) { reachingPath = selection ; closestPath = selection ; const trimmedCandidates = [ ] ; for ( c = 0 ; c < candidates . length ; c += 1 ) { candidate = candidates [ c ] ; if ( candidate . w + candidate . d < reachingPath . w ) { trimmedCandidates . push ( candidate ) ; } else { this . grid [ candidate . i ] [ candidate . j ] . candidateRef = null ; } } candidates = trimmedCandidates ; } } else { if ( selection . d < closestPath . d ) { closestPath = selection ; } } } for ( c = 0 ; c < candidates . length ; c += 1 ) { candidate = candidates [ c ] ; this . grid [ candidate . i ] [ candidate . j ] . candidateRef = null ; } for ( let s = 0 ; s < selections . length ; s += 1 ) { selection = selections [ s ] ; this . grid [ selection . i ] [ selection . j ] . candidateRef = null ; } for ( cellId in occupiedCells ) { cellPos = this . getMapPoint ( cellId ) ; this . grid [ cellPos . x + 1 ] [ cellPos . y + 1 ] . weight -= this . OCCUPIED_CELL_WEIGHT ; } const shortestPath = [ ] ; while ( closestPath !== null ) { shortestPath . unshift ( this . getCellId ( closestPath . i - 1 , closestPath . j - 1 ) ) ; closestPath = closestPath . path ; } return shortestPath ; } updateCellPath ( cell , cellPath ) { if ( ( cell !== undefined ) && ( cell . l & 1 ) ) { cellPath . floor = cell . f || 0 ; cellPath . zone = cell . z || 0 ; cellPath . speed = 1 + ( cell . s || 0 ) / 10 ; if ( cellPath . zone !== this . firstCellZone ) { this . useOldMovementSystem = false ; } } else { cellPath . floor = - 1 ; cellPath . zone = - 1 ; } } addCandidate ( c , w , di , dj , candidates , path ) { const i = c . i ; const j = c . j ; const distanceToDestination = Math . sqrt ( ( di - i ) * ( di - i ) + ( dj - j ) * ( dj - j ) ) ; w = w / c . speed + c . weight ; if ( c . candidateRef === null ) { const candidateRef = new CellPathCandidate ( i , j , path . w + w , distanceToDestination , path ) ; candidates . push ( candidateRef ) ; c . candidateRef = candidateRef ; } else { const currentWeight = c . candidateRef . w ; const newWeight = path . w + w ; if ( newWeight < currentWeight ) { c . candidateRef . w = newWeight ; c . candidateRef . path = path ; } } } addCandidates ( path , di , dj , candidates , allowDiagonals ) { const i = path . i ; const j = path . j ; const c = this . grid [ i ] [ j ] ; const c01 = this . grid [ i - 1 ] [ j ] ; const c10 = this . grid [ i ] [ j - 1 ] ; const c12 = this . grid [ i ] [ j + 1 ] ; const c21 = this . grid [ i + 1 ] [ j ] ; const weightStraight = 1 ; if ( this . areCommunicating ( c , c01 ) ) { this . addCandidate ( c01 , weightStraight , di , dj , candidates , path ) ; } if ( this . areCommunicating ( c , c21 ) ) { this . addCandidate ( c21 , weightStraight , di , dj , candidates , path ) ; } if ( this . areCommunicating ( c , c10 ) ) { this . addCandidate ( c10 , weightStraight , di , dj , candidates , path ) ; } if ( this . areCommunicating ( c , c12 ) ) { this . addCandidate ( c12 , weightStraight , di , dj , candidates , path ) ; } const c00 = this . grid [ i - 1 ] [ j - 1 ] ; const c02 = this . grid [ i - 1 ] [ j + 1 ] ; const c20 = this . grid [ i + 1 ] [ j - 1 ] ; const c22 = this . grid [ i + 1 ] [ j + 1 ] ; const weightDiagonal = Math . sqrt ( 2 ) ; if ( allowDiagonals ) { if ( this . canMoveDiagonallyTo ( c , c00 , c01 , c10 ) ) { this . addCandidate ( c00 , weightDiagonal , di , dj , candidates , path ) ; } if ( this . canMoveDiagonallyTo ( c , c20 , c21 , c10 ) ) { this . addCandidate ( c20 , weightDiagonal , di , dj , candidates , path ) ; } if ( this . canMoveDiagonallyTo ( c , c02 , c01 , c12 ) ) { this . addCandidate ( c02 , weightDiagonal , di , dj , candidates , path ) ; } if ( this . canMoveDiagonallyTo ( c , c22 , c21 , c12 ) ) { this . addCandidate ( c22 , weightDiagonal , di , dj , candidates , path ) ; } } } getCellId ( x , y ) { return this . mapPoints [ x + "_" + y ] ; } _generateMapPoints ( ) { this . mapPoints = { } ; for ( let cellId = 0 ; cellId < this . CELL_NUMBER ; cellId ++ ) { const { x , y } = this . getMapPoint ( cellId ) ; this . mapPoints [ x + "_" + y ] = cellId ; } } _generateGrid ( ) { this . grid = [ ] ; for ( let i = 0 ; i < this . WIDTH ; i += 1 ) { const row = [ ] ; for ( let j = 0 ; j < this . HEIGHT ; j += 1 ) { row [ j ] = new CellPathData ( i , j ) ; } this . grid [ i ] = row ; } } getMapPoint ( cellId ) { const row = cellId % 14 - ~ ~ ( cellId / 28 ) ; const x = row + 19 ; const y = row + ~ ~ ( cellId / 14 ) ; return { x , y } ; } areCommunicating ( c1 , c2 , oldMovementSystem = false ) { const sameFloor = c1 . floor === c2 . floor ; const sameZone = c1 . zone === c2 . zone ; const ELEVATION_TOLERANCE = 11.825 ; if ( sameFloor ) return true ; if ( ! sameZone ) return false ; return oldMovementSystem || c1 . zone !== 0 || ( Math . abs ( c1 . floor - c2 . floor ) <= ELEVATION_TOLERANCE ) ; } canMoveDiagonallyTo ( c1 , c2 , c3 , c4 ) { return this . areCommunicating ( c1 , c2 , this . useOldMovementSystem ) && ( this . areCommunicating ( c1 , c3 , this . useOldMovementSystem ) || this . areCommunicating ( c1 , c4 , this . useOldMovementSystem ) ) ; } }