用Prim算法实现随机生成的迷宫
用Prim算法实现随机生成的迷宫
提问于 2015-04-20 05:13:00
我试图用Prim的算法实现一个随机生成的迷宫。
我要我的迷宫看起来像这样：
然而，我从我的程序中产生的迷宫看起来如下：
目前，我正致力于正确地执行粗体突出显示的步骤：
- 从一个满是墙的网格开始。
- 选择一个细胞，标记为迷宫的一部分。将单元格的墙壁添加到墙列表中。
- 当列表中有墙壁时：
- **1.从名单中随机挑选一堵墙。如果对面的细胞还没有在迷宫中：
-
- 让墙壁成为一条通道，把对面的细胞标记为迷宫的一部分。**
-
- **1.从名单中随机挑选一堵墙。如果对面的细胞还没有在迷宫中：
-
1. Add the neighboring walls of the cell to the wall list.
-
1. Remove the wall from the list.
来自这篇文章是关于迷宫生成的。
如何确定单元格是否为墙列表的有效候选人？我想改变我的算法，使它产生一个正确的迷宫。任何能帮助我解决问题的想法都将不胜感激。
回答 8
Stack Overflow用户
回答已采纳
发布于 2015-04-20 21:41:41
维基百科文章中的描述确实值得改进。
文章的第一个令人困惑的部分是，随机Prim算法的描述没有详细说明算法所使用的假设数据结构。因此，像“相反的细胞”这样的短语变得很混乱。
基本上，“迷宫生成器程序员”可以选择两种主要方法：
- 细胞有墙壁或通道给他们的4个邻居。有关墙壁/通道的信息被储存和操纵。
- 细胞可以被阻塞(墙壁)或通道，而不需要存储任何额外的连接信息。
根据读者在阅读算法描述时所想到的模型(1)或(2)，他们要么理解，要么不理解。
就我个人而言，我更喜欢用细胞作为墙壁或通道，而不是摆弄专门的通道/墙壁信息。
然后，“边界”斑块与通道之间的距离为2(而不是1)。从边界斑块列表中选择随机边界块，并将其连接到相邻通道(距离2处)，并使边界斑块与相邻通道之间的单元成为通道。
在这里，我的F#实现是如何实现的：
let rng = new System.Random()
type Cell = | Blocked | Passage
type Maze =
{
Grid : Cell[,]
Width : int
Height : int
}
let initMaze dx dy =
let six,siy = (1,1)
let eix,eiy = (dx-2,dy-2)
{
Grid = Array2D.init dx dy
(fun _ _ -> Blocked
)
Width = dx
Height = dy
}
let generate (maze : Maze) : Maze =
let isLegal (x,y) =
x>0 && x < maze.Width-1 && y>0 && y<maze.Height-1
let frontier (x,y) =
[x-2,y;x+2,y; x,y-2; x, y+2]
|> List.filter (fun (x,y) -> isLegal (x,y) && maze.Grid.[x,y] = Blocked)
let neighbor (x,y) =
[x-2,y;x+2,y; x,y-2; x, y+2]
|> List.filter (fun (x,y) -> isLegal (x,y) && maze.Grid.[x,y] = Passage)
let randomCell () = rng.Next(maze.Width),rng.Next(maze.Height)
let removeAt index (lst : (int * int) list) : (int * int) list =
let x,y = lst.[index]
lst |> List.filter (fun (a,b) -> not (a = x && b = y) )
let between p1 p2 =
let x =
match (fst p2 - fst p1) with
| 0 -> fst p1
| 2 -> 1 + fst p1
| -2 -> -1 + fst p1
| _ -> failwith "Invalid arguments for between()"
let y =
match (snd p2 - snd p1) with
| 0 -> snd p1
| 2 -> 1 + snd p1
| -2 -> -1 + snd p1
| _ -> failwith "Invalid arguments for between()"
(x,y)
let connectRandomNeighbor (x,y) =
let neighbors = neighbor (x,y)
let pickedIndex = rng.Next(neighbors.Length)
let xn,yn = neighbors.[pickedIndex]
let xb,yb = between (x,y) (xn,yn)
maze.Grid.[xb,yb] <- Passage
()
let rec extend front =
match front with
| [] -> ()
| _ ->
let pickedIndex = rng.Next(front.Length)
let xf,yf = front.[pickedIndex]
maze.Grid.[xf,yf] <- Passage
connectRandomNeighbor (xf,yf)
extend ((front |> removeAt pickedIndex) @ frontier (xf,yf))
let x,y = randomCell()
maze.Grid.[x,y] <- Passage
extend (frontier (x,y))
maze
let show maze =
printfn "%A" maze
maze.Grid |> Array2D.iteri
(fun y x cell ->
if x = 0 && y > 0 then
printfn "|"
let c =
match cell with
| Blocked -> "X"
| Passage -> " "
printf "%s" c
)
maze
let render maze =
let cellWidth = 10;
let cellHeight = 10;
let pw = maze.Width * cellWidth
let ph = maze.Height * cellHeight
let passageBrush = System.Drawing.Brushes.White
let wallBrush = System.Drawing.Brushes.Black
let bmp = new System.Drawing.Bitmap(pw,ph)
let g = System.Drawing.Graphics.FromImage(bmp);
maze.Grid
|> Array2D.iteri
(fun y x cell ->
let brush =
match cell with
| Passage -> passageBrush
| Blocked -> wallBrush
g.FillRectangle(brush,x*cellWidth,y*cellHeight,cellWidth,cellHeight)
)
g.Flush()
bmp.Save("""E:\temp\maze.bmp""")
initMaze 50 50 |> generate |> show |> render由此产生的迷宫可能看起来是这样的：
这里试图用维基百科的“算法”风格来描述我的解决方案：
- 网格由一个二维的单元格数组组成。
- 单元格有两种状态:阻塞或通过。
- 从一个网格开始，网格中充满处于阻塞状态的单元格。
- 选择一个随机单元格，将其设置为状态通道并计算其边界单元。一个细胞的前沿细胞是一个距离为2的细胞在状态被阻塞和在网格内。
- 当前沿单元格列表不为空时：
- 从边界单元列表中选择一个随机边界单元。
- 让邻居(FrontierCell)=状态通道中距离2的所有单元格。选择一个随机邻居，并通过将边界单元设置为状态通道，将边界单元与邻居连接起来。计算所选边界单元格的边界单元格，并将它们添加到边界列表中。从前沿单元格列表中删除选定的边界单元格。
Stack Overflow用户
发布于 2015-04-22 22:45:38
Prim算法的一个简单Java实现：
import java.util.LinkedList;
import java.util.Random;
public class Maze {
public static final char PASSAGE_CHAR = ' ';
public static final char WALL_CHAR = '▓';
public static final boolean WALL = false;
public static final boolean PASSAGE = !WALL;
private final boolean map[][];
private final int width;
private final int height;
public Maze( final int width, final int height ){
this.width = width;
this.height = height;
this.map = new boolean[width][height];
final LinkedList<int[]> frontiers = new LinkedList<>();
final Random random = new Random();
int x = random.nextInt(width);
int y = random.nextInt(height);
frontiers.add(new int[]{x,y,x,y});
while ( !frontiers.isEmpty() ){
final int[] f = frontiers.remove( random.nextInt( frontiers.size() ) );
x = f[2];
y = f[3];
if ( map[x][y] == WALL )
{
map[f[0]][f[1]] = map[x][y] = PASSAGE;
if ( x >= 2 && map[x-2][y] == WALL )
frontiers.add( new int[]{x-1,y,x-2,y} );
if ( y >= 2 && map[x][y-2] == WALL )
frontiers.add( new int[]{x,y-1,x,y-2} );
if ( x < width-2 && map[x+2][y] == WALL )
frontiers.add( new int[]{x+1,y,x+2,y} );
if ( y < height-2 && map[x][y+2] == WALL )
frontiers.add( new int[]{x,y+1,x,y+2} );
}
}
}
@Override
public String toString(){
final StringBuffer b = new StringBuffer();
for ( int x = 0; x < width + 2; x++ )
b.append( WALL_CHAR );
b.append( '\n' );
for ( int y = 0; y < height; y++ ){
b.append( WALL_CHAR );
for ( int x = 0; x < width; x++ )
b.append( map[x][y] == WALL ? WALL_CHAR : PASSAGE_CHAR );
b.append( WALL_CHAR );
b.append( '\n' );
}
for ( int x = 0; x < width + 2; x++ )
b.append( WALL_CHAR );
b.append( '\n' );
return b.toString();
}
}new Maze(20,20).toString()的一个示例输出是：
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓ ▓ ▓ ▓ ▓▓
▓ ▓▓▓ ▓▓▓▓▓▓▓▓▓ ▓▓▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓▓
▓ ▓▓▓▓▓ ▓ ▓ ▓▓▓ ▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓▓▓▓▓▓▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓▓
▓ ▓▓▓ ▓ ▓▓▓ ▓ ▓ ▓▓▓▓▓▓
▓ ▓ ▓ ▓ ▓ ▓ ▓▓
▓ ▓▓▓▓▓ ▓▓▓ ▓ ▓ ▓▓▓ ▓▓
▓ ▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓▓▓ ▓▓▓▓▓▓▓▓▓▓
▓ ▓ ▓ ▓ ▓ ▓▓
▓ ▓▓▓▓▓▓▓ ▓ ▓▓▓▓▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓ ▓▓
▓▓▓ ▓▓▓ ▓▓▓ ▓ ▓▓▓▓▓ ▓▓
▓ ▓ ▓▓
▓▓▓ ▓ ▓▓▓ ▓▓▓ ▓▓▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓ ▓▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓Stack Overflow用户
发布于 2020-06-25 13:53:57
下面是基于接受答案的注释Java实现
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;
/**
* Generate a maze using Prime's algorithm
* Based on: https://stackoverflow.com/a/29758926/3992939
*
* @author c0der
* 25 Jun 2020
*
*/
public class PrimeMazeGenerator implements Runnable {
private static final int[][] DIRECTIONS = { //distance of 2 to each side
{ 0 ,-2}, // north
{ 0 , 2}, // south
{ 2 , 0}, // east
{-2 , 0}, // west
};
private long delay = 0;
private final CellModel[][] cells;
private final Random random;
public PrimeMazeGenerator(CellModel[][] cells) {
this.cells = cells;
random = new Random();
}
@Override
public void run() {
primMazeGeneration();
}
public void execute() {
new Thread(this).start();
}
void primMazeGeneration() {
//Start with a grid full of cellModelViews in state wall (not a path).
for(int i = 0; i < cells.length; i++){
for(int j = 0; j < cells[0].length ; j++){
cells[i][j].setWall(true);
}
}
//Pick a random cell
int x = random.nextInt(cells.length);
int y = random.nextInt(cells[0].length);
cells[x][y].setWall(false); //set cell to path
//Compute cell frontier and add it to a frontier collection
Set<CellModel> frontierCells = new HashSet<>(frontierCellsOf(cells[x][y]));
while (!frontierCells.isEmpty()){
//Pick a random cell from the frontier collection
CellModel frontierCell = frontierCells.stream().skip(random.nextInt(frontierCells.size())).findFirst().orElse(null);
//Get its neighbors: cells in distance 2 in state path (no wall)
List<CellModel> frontierNeighbors = passageCellsOf(frontierCell);
if(!frontierNeighbors.isEmpty()) {
//Pick a random neighbor
CellModel neighbor = frontierNeighbors.get(random.nextInt(frontierNeighbors.size()));
//Connect the frontier cell with the neighbor
connect(frontierCell, neighbor);
}
//Compute the frontier cells of the chosen frontier cell and add them to the frontier collection
frontierCells.addAll(frontierCellsOf(frontierCell));
//Remove frontier cell from the frontier collection
frontierCells.remove( frontierCell);
try {
Thread.sleep(delay);
} catch (InterruptedException ex) { ex.printStackTrace();}
}
}
//Frontier cells: wall cells in a distance of 2
private List<CellModel> frontierCellsOf(CellModel cell) {
return cellsAround(cell, true);
}
//Frontier cells: passage (no wall) cells in a distance of 2
private List<CellModel> passageCellsOf(CellModel cell) {
return cellsAround(cell, false);
}
private List<CellModel> cellsAround(CellModel cell, boolean isWall) {
List<CellModel> frontier = new ArrayList<>();
for(int[] direction : DIRECTIONS){
int newRow = cell.getRow() + direction[0];
int newCol = cell.getColumn() + direction[1];
if(isValidPosition(newRow, newCol) && cells[newRow][newCol].isWall() == isWall){
frontier.add(cells[newRow][newCol]);
}
}
return frontier;
}
//connects cells which are distance 2 apart
private void connect( CellModel frontierCellModelView, CellModel neighbour) {
int inBetweenRow = (neighbour.getRow() + frontierCellModelView.getRow())/2;
int inBetweenCol = (neighbour.getColumn() + frontierCellModelView.getColumn())/2;
frontierCellModelView.setWall(false);
cells[inBetweenRow][inBetweenCol].setWall(false);
neighbour.setWall(false);
}
private boolean isValidPosition(int row, int col) {
return row >= 0 && row < cells.length
&& col >= 0 && col < cells[0].length;
}
public PrimeMazeGenerator setDelay(long delay) {
this.delay = delay;
return this;
}
}CellModel.java
/**
* Maze cell representation
*
* @author c0der
* 25 Jun 2020
*
*/
public class CellModel{
private final int row, column;
private boolean isWall;
//support to fire property change events
private PropertyChangeSupport pcs;
public CellModel(int row, int column) {
this(row, column, false);
}
public CellModel(int row, int column, boolean isWall) {
this.row = row;
this.column = column;
this.isWall = isWall;
}
@Override
public boolean equals(Object obj) {
if(!(obj instanceof CellModel)) return false;
CellModel other = (CellModel)obj;
return row == other.getRow() && column == other.getColumn();
}
public void setPropertChangeSupport(PropertyChangeSupport pcs) {
this.pcs = pcs;
}
private void firePropertyChange(String name, Object oldValue, Object newValue) {
if(pcs != null) {
pcs.firePropertyChange(name, oldValue, newValue);
}
}
/**
* Get {@link #isWall}
*/
public boolean isWall() {
return isWall;
}
/**
* Set {@link #isWall}
*/
public void setWall(boolean isWall) {
Object old = this.isWall;
this.isWall = isWall;
firePropertyChange("Wall", old, isWall);
}
/**
* Get {@link #row}
*/
public int getRow() {
return row;
}
/**
* Get {@link #column}
*/
public int getColumn() {
return column;
}
@Override
public String toString() {
return "["+ (isWall ? "Wall " : "Path " ) + row + "-" + column + "]";
}
/* (non-Javadoc)
* @see java.lang.Object#hashCode()
*/
@Override
public int hashCode() {
return 17*row + 31*column;
}
}CellModel[][] cells可以从MazeModel获得
/**
* Maze representation
*
* @author c0der
* 25 Jun 2020
*
*/
public class MazeModel {
/**
* Collection to represent an entire maze
*/
private final CellModel[][] cellModels;
public MazeModel(int rows, int columns) {
cellModels = new CellModel[rows][columns];
for(int row=0; row <cellModels.length; row++) {
for(int col=0; col<cellModels[row].length; col++) {
CellModel cellModel = new CellModel(row, col);
cellModels[row][col] = cellModel;
}
}
}
/**
* Get {@link #cellModels}
*/
public CellModel[][] getCellModels() {
return cellModels;
}
}包括Swing和JavaFx gui在内的完整可运行代码可在这存储库上使用。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/29739751
复制相关文章
相似问题
腾讯云开发者
