Pathfinding - useful for exercises like "floating islands" or finding path in a maze.

pathfinding.js

// Code source https://btholt.github.io/four-semesters-of-cs-part-two/pathfinding

const NO_ONE = 0;
const BY_A = 1;
const BY_B = 2;

const processSearchIteration = ()=>{
  const aNeighbors = aQueue.reduce((acc, neighbor)=>{
    return acc.concat(getNeighbors(visited, neighbor.x, neighbor.y))
  }, [])

  aQueue = []

  for(let i=0; i< aNeighbors.length; i++) {
    const neighbor = aNeighbors[i]
    if(neighbor.openedBy === BY_B){
      // we found the connection
      return neighbor.length + iteration
    } else if (neighbor.openedBy === NO_ONE){
      neighbor.length = iteration
      neighbor.openedBy = BY_A
      aQueue.push(neighbor)
    }
  }
}
// write in a function thats a X by X array of arrays of numbers
// as well two x/y combinations and have it return the shortest
// length (you don't need to track the actual path) from point A
// to point B.
//
// the numbers in the maze array represent as follows:
// 0 – open space
// 1 - closed space, cannot pass through. a wall
// 2 - one of the two origination points
//
// you will almost certainly need to transform the maze into your own
// data structure to keep track of all the meta data
const findShortestPathLength = (maze, [xA, yA], [xB, yB]) => {
    const queue = [];
    const visited = maze.map((row, y)=>{
      return row.map((point, x)=>{
        return {
          closed: point === 1,
          length: 0,
          openedBy: NO_ONE,
          x,
          y
        }
      })
    })

    visited[yA][xA].openedBy = BY_A;
    visited[yB][xB].openedBy = BY_B;

    let aQueue = [visited[yA][xA]]
    let bQueue = [visited[yB][xB]]

    let iteration = 0;

    while(aQueue.length && bQueue.length){
      iteration++

      // A 
      const aNeighbors = aQueue.reduce((acc, neighbor)=>{
        return acc.concat(getNeighbors(visited, neighbor.x, neighbor.y))
      }, [])

      aQueue = []

      for(let i=0; i< aNeighbors.length; i++) {
        const neighbor = aNeighbors[i]
        if(neighbor.openedBy === BY_B){
          // we found the connection
          return neighbor.length + iteration
        } else if (neighbor.openedBy === NO_ONE){
          neighbor.length = iteration
          neighbor.openedBy = BY_A
          aQueue.push(neighbor)
        }
      }

      // B
      const bNeighbors = bQueue.reduce((acc, neighbor)=>{
        return acc.concat(getNeighbors(visited, neighbor.x, neighbor.y))
      }, [])

      bQueue = []

      for(let i=0; i< bNeighbors.length; i++) {
        const neighbor = bNeighbors[i]
        if(neighbor.openedBy === BY_A){
          // we found the connection
          return neighbor.length + iteration
        } else if (neighbor.openedBy === NO_ONE){
          neighbor.length = iteration
          neighbor.openedBy = BY_B
          bQueue.push(neighbor)
        }
      }
    }

    return -1
  
};


const getNeighbors = (visited, x, y) =>{
  const neighbors = [];

  if(y - 1 >= 0 && !visited[y-1][x].closed) {
    // left
    neighbors.push(visited[y-1][x])
  }

  if(y + 1 < visited[0].length && !visited[y+1][x].closed) {
    // right
    neighbors.push(visited[y+1][x])
  }

  if(x + 1 < visited[0].length && !visited[y][x+1].closed) {
    // down
    neighbors.push(visited[y][x+1])
  }


  if(x - 1 >= 0 && !visited[y][x-1].closed) {
    // up
    neighbors.push(visited[y][x-1])
  }

  return neighbors
}

// tests

  const fourByFour = [
    [2, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 2]
  ]

  let result = findShortestPathLength(fourByFour, [0, 0], [3, 3])
  console.log("fourByFour path length result", result)
  console.log(result == 6)

  const sixBySix = [
    [0, 0, 0, 0, 0, 0],
    [0, 2, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 1, 1, 1, 1, 1],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 2, 0, 0, 0]
  ];

  result = findShortestPathLength(sixBySix, [1, 1], [2, 5])
  console.log("fourByFour path length result", result)
  console.log(result == 7)