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