Проблемы с генерацией лабиринта с использованием нерекурсивного алгоритма возврата - PullRequest
Новая
       8

Проблемы с генерацией лабиринта с использованием нерекурсивного алгоритма возврата

2 голосов
/ 10 февраля 2012

Я работаю над игрой для 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

Обратите внимание, как каждая ячейка всегда соединяется со своими соседями вверх и вниз.Я не смог выяснить, что здесь не так.

Хотя проверки в функции setNeighbor в MazeCell кажутся достаточными, я добавил еще несколько, чтобы посмотреть, что произойдет.Вот второй метод 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

Обратите внимание, как все сегменты разбиты.

Я поиграл с этим на лот больше, чем просто то, что упомянуто здесь, но ничего, что не показывает какого-либо реального улучшения - большинство в конечном итоге выглядит просто как вторая картинка.Любая помощь?

Ответы [ 2 ]

1 голос
/ 10 февраля 2012

Я думаю, что рекурсивные алгоритмы, которые вы нашли, просто хороши. Вам просто нужно преобразовать их в итеративный, используя стек или очередь вместо рекурсивного вызова (вы моделируете свой стек вызовов). Вы можете найти хороший пример для ширина вначале итерация здесь . Надеюсь, что это поможет, и вы можете адаптировать это к вашей проблеме.

1 голос
/ 10 февраля 2012

Я рекомендую создать функцию с именем Direction oppositeOf(Direction d) (с очевидной логикой).Эта функция позволяет полностью удалить оператор switch в 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 логическое всегда равнона true (независимо от того, установлено ли оно на false, всегда устанавливается на true), что я готов поспорить, что вы этого не хотите.

Это может быть не самой большой проблемой, возможно,другие логические ошибки.

...