Untitled

const getAllDistanceInfo = (position: ILocation, map: number[][]) => {
  const h = MAP_ROWS,
    w = MAP_COLUMNS
  const dx = [0, -1, 0, 1],
    dy = [-1, 0, 1, 0]
  const visited: ICell[] = []
  const q: ICell[] = []

  q.push({ x: position.x, y: position.y, d: 0 })
  while (q && q.length > 0) {
    const c = q.shift()
    if (c) {
      visited.push(c)
      for (let i = 0; i < 4; i++) {
        const nx = c.x + dx[i],
          ny = c.y + dy[i]
        const nc = { x: nx, y: ny, d: c.d + 1 }
        if (!getBlockAt(q, nc) && !getBlockAt(visited, nc) && nx >= 0 && nx < w && ny >= 0 && ny < h && map[ny][nx] == 0) {
          q.push(nc)
        }
      }
    }
  }

  return visited
}

const getShortestPath = (source: ILocation, target: ILocation | null, map: number[][]) => {
  const path: ICell[] = []
  if (target === null) return path
  const h = MAP_ROWS,
    w = MAP_COLUMNS
  const dx = [0, -1, 0, 1],
    dy = [-1, 0, 1, 0]
  map = map.map((m) => m.slice()) // avoid reference
  map[target.y][target.x] = 0
  const distanceInfo = getAllDistanceInfo(source, map)
  const targetBlock = getBlockAt(distanceInfo, { x: target.x, y: target.y, d: 0 })
  if (targetBlock != null) {
    let currentBlock = targetBlock
    path.push(currentBlock)
    while (currentBlock.d > 0) {
      for (let i = 0; i < 4; i++) {
        const nx = currentBlock.x + dx[i],
          ny = currentBlock.y + dy[i]
        if (nx >= 0 && nx < w && ny >= 0 && ny < h) {
          const adjacentBlock = getBlockAt(distanceInfo, { x: nx, y: ny, d: 0 })
          if (adjacentBlock != null && adjacentBlock.d == currentBlock.d - 1) {
            currentBlock = adjacentBlock
            path.push(currentBlock)
            break
          }
        }
      }
    }
  }

  if (path.length > 0) path.shift()
  return path
}

const getBlockAt = (ar: ICell[], c: ICell) => {
  const result = ar.filter((_) => _.x == c.x && _.y == c.y)
  if (result.length > 0) return result[0]
  return null
}