2012-02-10 161 views
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

通知段如何各个击破结果。

我已经玩过很多不仅仅是这里提到的东西,但没有任何显示任何真正的改进 - 大多数最终只是看起来像第二张照片。任何帮助?

+0

即使您使用自己的堆栈,回溯也是按照定义递归的。 – osa 2013-10-15 19:45:19

回答

1

我建议创建一个名为Direction oppositeOf(Direction d)(具有明显的逻辑)的函数。如果添加该功能,您可以完全删除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布尔总是等同于真(不管它的设置假的,它总是被设置为真),我敢打赌,你不希望它这样做。

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

+0

setNeighbor布尔值在函数调用后总是等于true,这很好,因为每当从MazeGenerator调用它时,currentCell和nextCell都需要设置为彼此的邻居,因此在调用nextCell之前将其设置为false在currentCell中,nextCell不会再次为currentCell再次调用它,但是在下一次迭代之后它将被重置为真(因为它是一个静态变量)。这是一种混乱的处理方式,但它只是那种方式。虽然我确实喜欢Direction.oppositeOf的想法。谢谢。 – 2012-02-10 17:48:11

+1

我的观点是,写入'setNeighbor'布尔的方式决不会对你在这里的代码做任何事情。如果if语句可能为false,它从未检查过。 – 2012-02-10 20:58:24

1

我认为你发现的递归算法很好。你只需要通过使用栈或队列而不是递归调用(你模拟你的调用栈)来将它们转换为迭代的。你可以找到breadth first迭代here的一个很好的例子。希望这会有所帮助,并且可以将其应用于您的问题。