CODEWITHSUNDEEP
javascriptbreadth-first-searchmaze
sophg
sophg

Reputation: 39

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);

Upvotes: 1

Views: 208

Answers (2)

Noa
Noa

Reputation: 1216

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);

Upvotes: 0

daniloxxv
daniloxxv

Reputation: 865

I think you might have an issue in this line:

queue.shift()

It seems you're never reading the values that were stored in the queue, so the coordinates in your loop are never updated, which means you're always checking the same positions. You probably want to assign the value of queue.shift() to a variable and use those coordinates to continue the search.

Upvotes: 0

Related Questions