使用非递归回溯算法生成迷宫的问题
我正在开发一款适用于Android的游戏，其中可探索区域将随机生成。现在，我只是试图让迷宫生成（有一些ASCII艺术输出，所以我可以看到它），我已经在这里约4-5天，但我只是难住。使用非递归回溯算法生成迷宫的问题
我正在尝试使用“深度优先搜索”算法，并且我可以找到的所有示例都使用递归回溯。由于这是Android和电话相对懦弱，递归很快导致调用堆栈溢出，这就是为什么我试图写一个自己的算法使用堆栈回溯。
我想出了这个解决方案，使用MazeGenerator类和MazeCell类。
MazeGenerator：
package com.zarokima.mistwalkers.explore;
import java.util.Random;
import java.util.Stack;
import org.anddev.andengine.util.path.Direction;
import android.graphics.Point;
public class MazeGenerator
{
private int x, y; // the dimensions of the maze
private MazeCell[][] maze;
private Random rand = new Random();
private Stack<MazeCell> stack;
public MazeGenerator(int x, int y)
{
this.x = x;
this.y = y;
generateMaze();
}
public void setSeed(long seed)
{
rand.setSeed(seed);
}
public void setSize(int x, int y)
{
this.x = x;
this.y = y;
}
public String outputMazeText()
{
String output = new String();
for (int i = 0; i < y; i++)
{
// draw the north edge
for (int k = 0; k < x; k++)
{
output += maze[k][i].hasNeighbor(Direction.UP) ? "+ " : "+---";
}
output += "+\n";
// draw the west edge
for (int k = 0; k < x; k++)
{
output += maze[k][i].hasNeighbor(Direction.LEFT) ? " " : "| ";
}
output += "|\n";
}
// draw the bottom line
for (int k = 0; k < x; k++)
{
output += "+---";
}
output += "+\n";
return output;
}
public void generateMaze()
{
maze = new MazeCell[x][y];
for (int i = 0; i < x; i++)
{
for (int k = 0; k < y; k++)
{
maze[i][k] = new MazeCell(i, k);
}
}
MazeCell.setBounds(x, y);
stack = new Stack<MazeCell>();
stack.push(maze[0][0]);
maze[0][0].setInMaze(true);
while (!stack.isEmpty())
{
MazeCell currentCell = stack.peek();
Direction[] possibleDirections = currentCell.getUncheckedDirections();
if (possibleDirections.length == 0)
{
stack.pop();
continue;
}
int dint = rand.nextInt(possibleDirections.length);
Direction direction = possibleDirections[dint];
MazeCell nextCell = null;
Point position = currentCell.getPosition();
switch (direction)
{
case UP:
nextCell = maze[position.x][position.y - 1];
break;
case DOWN:
nextCell = maze[position.x][position.y + 1];
break;
case LEFT:
nextCell = maze[position.x - 1][position.y];
break;
case RIGHT:
nextCell = maze[position.x + 1][position.y];
break;
}
currentCell.setNeighbor(nextCell, direction);
stack.push(nextCell);
}
}
}
MazeCell：
package com.zarokima.mistwalkers.explore;
import java.util.ArrayList;
import org.anddev.andengine.util.path.Direction;
import android.graphics.Point;
public class MazeCell
{
private MazeCell[] neighbors;
private boolean[] checked;
private boolean inMaze = false;
private Point position;
private static boolean setNeighbor = true; //whether the next call of SetNeighbor() should also call for the new neighbor
private static int xMax = 10, yMax = 10; //exclusive boundary for position
private int mapIndex; //will be used when maze generation is working properly
public MazeCell(int x, int y)
{
position = new Point(x,y);
neighbors = new MazeCell[4];
checked = new boolean[4];
for(int i = 0; i < neighbors.length; i++)
{
neighbors[i] = null;
}
}
public Point getPosition()
{
return position;
}
public void setInMaze(boolean b)
{
inMaze = b;
}
public static void setBounds(int x, int y)
{
xMax = x;
yMax = y;
}
public void setNeighbor(MazeCell c, Direction d)
{
checked[d.ordinal()] = true;
switch(d)
{
case UP:
if(!c.hasNeighbor(Direction.DOWN) && !c.isInMaze());
{
if(setNeighbor)
{
setNeighbor = false;
c.setNeighbor(this, Direction.DOWN);
}
neighbors[d.ordinal()] = c;
}
break;
case DOWN:
if(!c.hasNeighbor(Direction.UP) && !c.isInMaze())
{
if(setNeighbor)
{
setNeighbor = false;
c.setNeighbor(this, Direction.UP);
}
neighbors[d.ordinal()] = c;
}
break;
case LEFT:
if(!c.hasNeighbor(Direction.RIGHT) && !c.isInMaze())
{
if(setNeighbor)
{
setNeighbor = false;
c.setNeighbor(this, Direction.RIGHT);
}
neighbors[d.ordinal()] = c;
}
break;
case RIGHT:
if(!c.hasNeighbor(Direction.LEFT) && !c.isInMaze())
{
if(setNeighbor)
{
setNeighbor = false;
c.setNeighbor(this, Direction.LEFT);
}
neighbors[d.ordinal()] = c;
}
break;
}
setNeighbor = true;
inMaze = true;
}
public void setDirectionChecked(Direction d, boolean b)
{
checked[d.ordinal()] = b;
}
public boolean hasNeighbor(Direction d)
{
return (neighbors[d.ordinal()] != null);
}
public MazeCell getNeighbor(Direction d)
{
return neighbors[d.ordinal()];
}
public boolean isInMaze()
{
return inMaze;
}
public Direction[] getUncheckedDirections()
{
ArrayList<Direction> al = new ArrayList<Direction>();
for(Direction d : Direction.values())
{
//boundary cases
switch(d)
{
case UP:
if(position.y == 0)
continue;
break;
case DOWN:
if(position.y == yMax-1)
continue;
break;
case LEFT:
if(position.x == 0)
continue;
break;
case RIGHT:
if(position.x == xMax-1)
continue;
break;
}
if(checked[d.ordinal()] == false)
al.add(d);
}
Direction[] d = new Direction[al.size()];
for(int i = 0; i < d.length; i++)
d[i] = al.get(i);
return d;
}
}
这产生的结果看起来像this
注意如何每一个细胞都始终连接到它的上下邻居。我一直无法弄清楚这里有什么问题。
尽管MazeCell的setNeighbor函数中的检查看起来应该足够了，但我还是多加了一些，看看会发生什么。下面是第二generateMaze（）方法：
public void generateMaze()
{
maze = new MazeCell[x][y];
for (int i = 0; i < x; i++)
{
for (int k = 0; k < y; k++)
{
maze[i][k] = new MazeCell(i, k);
}
}
MazeCell.setBounds(x, y);
stack = new Stack<MazeCell>();
stack.push(maze[0][0]);
maze[0][0].setInMaze(true);
while (!stack.isEmpty())
{
MazeCell currentCell = stack.peek();
Direction[] possibleDirections = currentCell.getUncheckedDirections();
if (possibleDirections.length == 0)
{
stack.pop();
continue;
}
int dint = rand.nextInt(possibleDirections.length);
Direction direction = possibleDirections[dint];
currentCell.setDirectionChecked(direction, true);
MazeCell nextCell = null;
Point position = currentCell.getPosition();
switch (direction)
{
case UP:
nextCell = maze[position.x][position.y - 1];
break;
case DOWN:
nextCell = maze[position.x][position.y + 1];
break;
case LEFT:
nextCell = maze[position.x - 1][position.y];
break;
case RIGHT:
nextCell = maze[position.x + 1][position.y];
break;
}
if (!nextCell.isInMaze())
{
currentCell.setNeighbor(nextCell, direction);
stack.push(nextCell);
}
}
并可以产生像this
通知段如何各个击破结果。
我已经玩过很多不仅仅是这里提到的东西，但没有任何显示任何真正的改进 - 大多数最终只是看起来像第二张照片。任何帮助？
我建议创建一个名为Direction oppositeOf(Direction d)（具有明显的逻辑）的函数。如果添加该功能，您可以完全删除setNeighbor中的开关语句。 在这里，我已经重写setNeighbor有与上述完全相同的逻辑，只要使用此功能：
public void setNeighbor(MazeCell c, Direction d)
{
checked[d.ordinal()] = true;
if (!c.isInMaze() && !c.hasNeighbor(oppositeOf(d)))
{
if (setNeighbor)
{
setNeighbor = false;
c.setNeighbor(this, oppositeOf(d));
}
neighbors[d.ordinal()] = c;
{
setNeighbor = true;
inMaze = true;
}
...这实际上暴露了setNeighbor布尔总是等同于真（不管它的设置假的，它总是被设置为真），我敢打赌，你不希望它这样做。
这可能不是您最大的问题，可能还有其他逻辑错误。
setNeighbor布尔值在函数调用后总是等于true，这很好，因为每当从MazeGenerator调用它时，currentCell和nextCell都需要设置为彼此的邻居，因此在调用nextCell之前将其设置为false在currentCell中，nextCell不会再次为currentCell再次调用它，但是在下一次迭代之后它将被重置为真（因为它是一个静态变量）。这是一种混乱的处理方式，但它只是那种方式。虽然我确实喜欢Direction.oppositeOf的想法。谢谢。 – 2012-02-10 17:48:11
我的观点是，写入'setNeighbor'布尔的方式决不会对你在这里的代码做任何事情。如果if语句可能为false，它从未检查过。 – 2012-02-10 20:58:24
我认为你发现的递归算法很好。你只需要通过使用栈或队列而不是递归调用（你模拟你的调用栈）来将它们转换为迭代的。你可以找到breadth first迭代here的一个很好的例子。希望这会有所帮助，并且可以将其应用于您的问题。
即使您使用自己的堆栈，回溯也是按照定义递归的。 – osa 2013-10-15 19:45:19