Search code examples
javascriptbreadth-first-searchmaze

BFS algorithm for maze not looping - Javascript


I am trying to use a BFS algorithm to solve a maze, which I have represented in an array where all the elements start as 999 except the centre (goal) which is 0. I am trying to have the code start from 0 and branch out four ways (north/south/east/west) and if the number is greater than the parent, add 1 to the parent number. The initial loop should have a 0 in the middle and the four adjacent cell should update to 1 from 999. This should loop over until the algorithm reaches position 0,0. Unfortunately, I don't seem to be able to get the loop running - I can get the first four elements updated to 1 and then it just stops. I think it is to do with how my queue is / isn't being picked up as the next loop's (y,x) input but I can't seem to get this to change. This is an assignment so not looking for a solution but any assistance in helping me see what I am missing for the loop would be greatly appreciated. I have shown the array code (mazeD) and the BFS/flood code below

// maze array showing numerical distance
let mazeD = [];
for (let y = 0; y < 10; y++) {
  let row = [];
  for (let x = 0; x < 10; x++) {
    row[x] = 999;
  }
  mazeD[y] = row;
}

mazeD[5][5] = 0;

// BFS function
function flood(x, y, d) {
  let queue = []
  queue.push([y, x]);
  while (queue.length > 0) {
    queue.shift();
    let fillArr = [
      [+y - 1, +x],
      [+y, +x - 1],
      [+y, +x + 1],
      [+y + 1, +x],
    ];
    if ((x < 10) && (y < 10)) {
      d++;
      for (let [yy, xx] of fillArr) {
      if (mazeD[yy][xx] > d) {
        queue.push([yy, xx]);
        mazeD[yy][xx] = d;
        console.log("queue =" +queue)
      }
    } 
  }
 }
}
flood(5, 5, 0);
console.log(mazeD);

Solution

  • Just do like this:

    let mazeD = [];
    for (let y = 0; y < 10; y++) {
      let row = [];
      for (let x = 0; x < 10; x++) {
        row[x] = 999;
      }
      mazeD[y] = row;
    }
    
    mazeD[5][5] = 0;
    
    // BFS function
    function flood(x, y, d) {
      let queue = [];
      let i = 0;
      queue.push([y, x]);
    
      while (i < queue.length) {
        
        [x,y] = queue[i,i];
        let fillArr = [
          [+y - 1, +x],
          [+y, +x - 1],
          [+y, +x + 1],
          [+y + 1, +x],
        ];
        if ((x < 10) && (y < 10) && x >=0 && y>=0) 
        {
          for (let [yy, xx] of fillArr) 
          {
            
          if(yy >=0 && yy < 10 && xx>=0 && xx<10)
          {
              if (mazeD[yy][xx] == 999) 
              {
                queue.push([yy, xx]);
                mazeD[yy][xx] = mazeD[y][x]+1;
                console.log(xx,yy,mazeD[y][x]+1);
              }
              if(xx == 0 && yy == 0){
                return;
              }
          }
          
        } 
      
       }
       i++;
      }
    }
    flood(5, 5, 0);
    console.log(mazeD);