2
私は、探索可能な領域がランダムに生成される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
お知らせのような結果が得られます。
私はここで言及されるだけのものよりたくさんよりそれを周りにプレイしましたが、任意の本当の改善を示しているものは何も - ほとんどはちょうど二絵のように見える終わるん。どんな助け？
バックトラックは、独自のスタックを使用している場合でも、定義によって再帰的です。 – osa