2

我正在开发一款适用于 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;
}
}

这会产生如下所示的结果

请注意每个单元如何始终连接到其上下邻居。我无法弄清楚这里出了什么问题。

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

它会产生这样的结果

注意段是如何被分解的。

除了这里提到的之外，我已经玩过它很多，但没有任何东西显示出任何真正的改进——大多数最终看起来就像第二张照片。有什么帮助吗？

4

2 回答 2

1

I recommend creating a function called Direction oppositeOf(Direction d) (with obvious logic). This function allows you to remove the switch statement entirely in setNeighbor if added. Here I've rewritten setNeighbor to have the exact same logic as above, just using this function:

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

...which actually exposes that setNeighbor boolean always equates to true (regardless of if it's set false, it's always then set true), which I'm willing to bet you don't want it to do.

This might not be your biggest problem, there might be other logic errors.

于 2012-02-10T05:16:31.110 回答
1

我认为您找到的递归算法很好。您只需使用堆栈或队列而不是递归调用（模拟调用堆栈）将它们转换为迭代的。您可以在此处找到广度首次迭代的一个很好的示例。希望这会有所帮助，您可以根据自己的问题进行调整。

于 2012-02-10T06:24:32.977 回答