2
Я работаю над игрой для Android, где исследуемые области будут генерироваться случайным образом. Прямо сейчас я просто пытаюсь получить лабиринт (с некоторым выпуском ASCII, поэтому я вижу его), и я был на нем около 4-5 дней, но я просто в тупике.Проблемы с генерацией лабиринта с использованием нерекурсивного алгоритма обратного отслеживания
Я пытаюсь использовать алгоритм поиска по глубине, и все примеры, которые я мог найти, используют рекурсивный обратный поиск. Поскольку это для Android, а телефоны относительно wimpy, рекурсия быстро приводит к переполнению стека вызовов, поэтому я пытаюсь написать собственный алгоритм, используя стек для обратного отслеживания.
Я придумал это решение, используя класс 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
Обратите внимание, как сегменты все распались.
Я играл с ним лот больше, чем то, что упоминается здесь, но ничего, что показывает какое-либо реальное улучшение - большинство из них просто выглядит как вторая фотография. Любая помощь?
Backtracking является рекурсивным по определению, даже если вы используете свой собственный стек. – osa