迷宫不循环的 BFS 算法 - Javascript
BFS algorithm for maze not looping - Javascript
我正在尝试使用 BFS 算法来解决迷宫问题,我已将其表示在一个数组中,其中所有元素都以 999 开头,但中心(目标)为 0。我正在尝试让代码开始从 0 分支出四种方式 (north/south/east/west),如果数字大于父级,则将父级数字加 1。初始循环应该在中间有一个 0,四个相邻单元格应该从 999 更新为 1。这应该循环直到算法到达位置 0,0。不幸的是,我似乎无法获得循环 运行 - 我可以将前四个元素更新为 1,然后它就停止了。我认为这与我的队列如何/没有被拾取为下一个循环的 (y,x) 输入有关,但我似乎无法改变这一点。
这是一项任务,因此不是在寻找解决方案,而是在帮助我了解我在循环中缺少什么方面的任何帮助将不胜感激。我已经显示了数组代码 (mazeD) 和下面的 BFS/flood 代码
// 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);
我认为您可能在这一行中遇到了问题:
queue.shift()
您似乎从来没有读取存储在队列中的值,因此循环中的坐标永远不会更新,这意味着您总是在检查相同的位置。您可能想将 queue.shift()
的值分配给一个变量并使用这些坐标继续搜索。
就这样:
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);
我正在尝试使用 BFS 算法来解决迷宫问题,我已将其表示在一个数组中,其中所有元素都以 999 开头,但中心(目标)为 0。我正在尝试让代码开始从 0 分支出四种方式 (north/south/east/west),如果数字大于父级,则将父级数字加 1。初始循环应该在中间有一个 0,四个相邻单元格应该从 999 更新为 1。这应该循环直到算法到达位置 0,0。不幸的是,我似乎无法获得循环 运行 - 我可以将前四个元素更新为 1,然后它就停止了。我认为这与我的队列如何/没有被拾取为下一个循环的 (y,x) 输入有关,但我似乎无法改变这一点。 这是一项任务,因此不是在寻找解决方案,而是在帮助我了解我在循环中缺少什么方面的任何帮助将不胜感激。我已经显示了数组代码 (mazeD) 和下面的 BFS/flood 代码
// 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);
我认为您可能在这一行中遇到了问题:
queue.shift()
您似乎从来没有读取存储在队列中的值,因此循环中的坐标永远不会更新,这意味着您总是在检查相同的位置。您可能想将 queue.shift()
的值分配给一个变量并使用这些坐标继续搜索。
就这样:
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);