我一直在尝试用JavaScript实现递归回溯迷宫生成算法。这是在阅读了关于这个主题的一系列很棒的文章之后完成的,链接在这里。
虽然递归版本的算法很容易理解,但迭代版本让我感到困惑。
我以为我理解了这个概念,但我的实现明显产生了错误的结果。我一直在试图找出可能导致错误的错误,但我开始相信我的问题是由逻辑上的失败引起的,但当然我没有看到是哪里出错了。
我对迭代算法的理解如下:
1. 创建一个包含单元格状态表示的堆栈。 2. 每个表示都包含该特定单元格的坐标和访问相邻单元格的方向列表。 3. 当堆栈不为空时,通过堆栈顶部的方向进行迭代,测试相邻单元格。 4. 如果找到有效单元格,请将其置于堆栈顶部并继续处理该单元格。
这是我的递归实现(注意:按键向前):http://jsbin.com/urilan/14 这是我的迭代实现(再次,按键向前):http://jsbin.com/eyosij/2 感谢您的帮助。
编辑:如果我的问题不清楚,我很抱歉。我将尝试进一步解释我的问题。
运行迭代解决方案时会出现各种意外的行为。首先,算法在回溯之前没有耗尽所有可用选项。相反,当只剩一个有效单元格时,它似乎是随机选择单元格。总体而言,移动似乎并不随机。
我希望这能为您解答问题。如果还有不足之处,请告诉我。
再次感谢。
虽然递归版本的算法很容易理解,但迭代版本让我感到困惑。
我以为我理解了这个概念,但我的实现明显产生了错误的结果。我一直在试图找出可能导致错误的错误,但我开始相信我的问题是由逻辑上的失败引起的,但当然我没有看到是哪里出错了。
我对迭代算法的理解如下:
1. 创建一个包含单元格状态表示的堆栈。 2. 每个表示都包含该特定单元格的坐标和访问相邻单元格的方向列表。 3. 当堆栈不为空时,通过堆栈顶部的方向进行迭代,测试相邻单元格。 4. 如果找到有效单元格,请将其置于堆栈顶部并继续处理该单元格。
这是我的递归实现(注意:按键向前):http://jsbin.com/urilan/14 这是我的迭代实现(再次,按键向前):http://jsbin.com/eyosij/2 感谢您的帮助。
编辑:如果我的问题不清楚,我很抱歉。我将尝试进一步解释我的问题。
运行迭代解决方案时会出现各种意外的行为。首先,算法在回溯之前没有耗尽所有可用选项。相反,当只剩一个有效单元格时,它似乎是随机选择单元格。总体而言,移动似乎并不随机。
var dirs = [ 'N', 'W', 'E', 'S' ];
var XD = { 'N': 0, 'S':0, 'E':1, 'W':-1 };
var YD = { 'N':-1, 'S':1, 'E':0, 'W': 0 };
function genMaze(){
var dirtemp = dirs.slice().slice(); //copies 'dirs' so its not overwritten or altered
var path = []; // stores path traveled.
var stack = [[0,0, shuffle(dirtemp)]]; //Stack of instances. Each subarray in 'stacks' represents a cell
//and its current state. That is, its coordinates, and which adjacent cells have been
//checked. Each time it checks an adjacent cell a direction value is popped from
//from the list
while ( stack.length > 0 ) {
var current = stack[stack.length-1]; // With each iteration focus is to be placed on the newest cell.
var x = current[0], y = current[1], d = current[2];
var sLen = stack.length; // For testing whether there is a newer cell in the stack than the current.
path.push([x,y]); // Store current coordinates in the path
while ( d.length > 0 ) {
if( stack.length != sLen ){ break;}// If there is a newer cell in stack, break and then continue with that cell
else {
var cd = d.pop();
var nx = x + XD[ cd ];
var ny = y + YD[ cd ];
if ( nx >= 0 && ny >= 0 && nx < w && ny < h && !cells[nx][ny] ){
dtemp = dirs.slice().slice();
cells[nx][ny] = 1;
stack.push( [ nx, ny, shuffle(dtemp) ] ); //add new cell to the stack with new list of directions.
// from here the code should break from the loop and start again with this latest addition being considered.
}
}
}
if (current[2].length === 0){stack.pop(); } //if all available directions have been tested, remove from stack
}
return path;
}
我希望这能为您解答问题。如果还有不足之处,请告诉我。
再次感谢。