How to find if a path of certain length exists between two points in a 2d array

Question

I'm trying to find if a path of length X or less exists between two points in a 2d array in Javascript. Each element in the array stores which elements it "connects" to (left, right, top, bottom, any combination of the 4 options, or none).

Each element in the array stores an object, and what they connect to is inside that object. I don't have really any experience programming these sort of algorithms, so any help is appreciated. (sorry if this is a duplicate, I wasn't able to find a solution to my exact problem).

// an example of what my array looks like ("id" is just there as example data, it doesn't exist in the actual array):
let arr = [[{ id: 1, con: ["bottom", "right"] }, { id: 3, con: ["left"] }, { id: 8, con: ["right"] }],
            [{ id: 4, con: ["top", "bottom"] }, { id: 9, con: [] }, { id: 5, con: [] }],
            [{ id: 6, con: ["top", "right"] }, { id: 7, con: ["left", "right"] }, { id: 2, con: ["left"] }],
];

function validPath(arr, pathLength, startPos, endPos) {
// algorithm
};

// from id:1 to id:7    [y-index, x-index]
validPath(arr, 2, [0, 0], [2, 1]); // false
validPath(arr, 3, [0, 0], [2, 1]); // true
validPath(arr, 5, [0, 0], [2, 1]); // true

I tried Googling for similar problems, but I just found BFS and DFS algorithms (maybe these can work, but each element in my array is only a blocked or blank cell from a specific direction, so I wasn't sure how to implement them)

Answer 1

The idea will be to start at the starting position and explore all possible paths of length X or less by moving to neighbor cells that are not blocked. You can use a queue to keep track of the cells to visit, and a set to keep track of the ones you already visited.

Here How I would implement it :

let arr = [[{ id: 1, con: ["bottom", "right"] }, { id: 3, con: ["left"] }, { id: 8, con: ["right"] }],
            [{ id: 4, con: ["top", "bottom"] }, { id: 9, con: [] }, { id: 5, con: [] }],
            [{ id: 6, con: ["top", "right"] }, { id: 7, con: ["left", "right"] }, { id: 2, con: ["left"] }],
];

function validPath(arr, pathLength, startPos, endPos) {
  const numRows = arr.length;
  const numCols = arr[0].length;
  const queue = [[...startPos, 0]]; // [y, x, steps]
  const visited = new Set([startPos.toString()]);

  while (queue.length > 0) {
    const [y, x, steps] = queue.shift();
    console.log(`Checking cell [${y}, ${x}] with ${steps} steps`);
    if (y === endPos[0] && x === endPos[1]) {
      console.log(`Found valid path in ${steps} steps`);
      return steps <= pathLength;
    }
    if (steps >= pathLength) {
      console.log(`Reached path length limit of ${pathLength} steps`);
      continue;
    }
    const connections = arr[y][x].con;
    console.log(`Connections: ${connections}`);
    for (const [dy, dx, direction] of [[-1, 0, 'top'], [1, 0, 'bottom'], [0, -1, 'left'], [0, 1, 'right']]) {
      const ny = y + dy;
      const nx = x + dx;
      if (ny >= 0 && ny < numRows && nx >= 0 && nx < numCols && connections.includes(direction) && !visited.has([ny, nx].toString())) {
        queue.push([ny, nx, steps + 1]);
        visited.add([ny, nx].toString());
      }
    }
  }

  console.log(`No valid path found`);
  return false;
}
validPath(arr, 2, [0, 0], [2, 1]); // false
validPath(arr, 3, [0, 0], [2, 1]); // true
validPath(arr, 5, [0, 0], [2, 1]); // true