java - 使用非递归回溯算法生成迷宫的问题

Question

我正在开发一款随机生成可探索区域的 Android 游戏。现在我只是想生成迷宫(使用一些 ASCII 艺术输出以便我可以看到它)，我已经用了大约 4-5 天了，但我只是被难住了。

我正在尝试使用“深度优先搜索”算法，我能找到的所有示例都使用递归回溯。由于这是针对 Android 的，而手机相对较弱，递归很快会导致调用堆栈溢出，这就是为什么我尝试使用堆栈编写自己的算法进行回溯。

我想出了这个解决方案，使用 MazeGenerator 类和 MazeCell 类。

迷宫生成器:

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

迷宫单元:

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 这样的结果

注意段是如何被分解的。

除了这里提到的内容，我还尝试了 很多，但没有任何真正的改进——大多数最终看起来就像第二张图片。有帮助吗？

Answer 1

我建议创建一个名为 Direction oppositeOf(Direction d) 的函数(具有明显的逻辑)。此函数允许您在 setNeighbor 中完全删除 switch 语句(如果已添加)。在这里，我重写了 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 boolean 值 总是 等于 true(不管它是否设置为 false，它总是然后设置为 true)，我愿意我打赌你不希望它这样做。

这可能不是您最大的问题，可能还有其他逻辑错误。