使用 Prim 算法实现随机生成的迷宫
Implementing a randomly generated maze using Prim's Algorithm
我正在尝试使用 Prim 算法实现随机生成的迷宫。
我希望我的迷宫看起来像这样：
然而，我从我的程序中生成的迷宫看起来像这样：
我目前无法正确执行以粗体突出显示的步骤：
- Start with a grid full of walls.
- Pick a cell, mark it as part of the maze. Add the walls of the cell to the wall list.
- While there are walls in the list:
- **1. Pick a random wall from the list. If the cell on the opposite side isn't in the maze yet:
- Make the wall a passage and mark the cell on the opposite side as part of the maze.**
- Add the neighboring walls of the cell to the wall list.
- Remove the wall from the list.
来自
this article on maze generation.
如何确定一个单元格是否是墙列表的有效候选者？我想更改我的算法以生成正确的迷宫。任何能帮助我解决问题的想法都将不胜感激。
尝试在程序开始时用独特的随机权重对墙壁进行加权。该权重列表永远不会改变。当您从可用墙列表中选择下一堵墙时，请选择重量最小的墙。
您的解决方案看起来并没有错。特别是，它是一个迷宫，并且（如果您不能沿对角线行走）从每个（开放）位置到彼此（开放）位置都有唯一的路径。唯一的问题似乎是样式。
如果你考虑你发布的 "correct" 迷宫，没有外边框，并将左上角的单元格设为 (0,0)，你可以观察到通道和墙壁在某种意义上是交替的。两个坐标均为偶数的每个单元格都必须是一条通道，而两个坐标均为奇数的每个单元格必须是一堵墙。因此，您唯一可以选择的单元格是一个坐标为偶数而另一个坐标为奇数的单元格。
让字段中间的一个单元格 (x,y) 给出，其中两个坐标都是偶数。这个细胞必须是一个通道。单元格 (x-1,y)、(x+1,y)、(x,y-1) 和 (x,y+1) 是它周围的势墙，单元格 (x-2,y)、(x+2,y)、(x,y-2) 和 (x,y+2) 分别是那些墙对面的正方形。
有了这些信息，您就可以实现您的算法，附加要求是在第 2 步中，您必须选择两个坐标都为偶数的单元格。
维基百科文章中的描述确实值得改进。
文章的第一个令人困惑的部分是，随机 Prim 算法的描述没有详细说明该算法使用的假定数据结构。因此，像 "opposite cell" 这样的短语变得令人困惑。
基本上有 2 种主要方法 "maze generator programmers" 可以选择：
- 牢房有墙壁或通往其 4 个邻居的通道。关于 walls/passages 的信息被存储和操纵。
- 单元格可以被阻塞（墙壁）或通道，而不存储任何额外的连接信息。
根据 reader 在阅读算法描述时想到的模型 (1) 或 (2)，他们要么理解要么不理解。
我个人更喜欢将单元格用作墙壁或通道，而不是摆弄专用的 passage/wall 信息。
然后，"frontier" 补丁与段落的距离为 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
一个由此产生的迷宫看起来像这样：
这里尝试用维基百科 "algorithm" 风格描述我的解决方案：
- A Grid consists of a 2 dimensional array of cells.
- A Cell has 2 states: Blocked or Passage.
- Start with a Grid full of Cells in state Blocked.
- Pick a random Cell, set it to state Passage and Compute its frontier cells.
A frontier cell of a Cell is a cell with distance 2 in state Blocked and within the grid.
- While the list of frontier cells is not empty:
- Pick a random frontier cell from the list of frontier cells.
- Let neighbors(frontierCell) = All cells in distance 2 in state Passage.
Pick a random neighbor and connect the frontier cell with the neighbor by setting the cell in-between to state Passage.
Compute the frontier cells of the chosen frontier cell and add them to the frontier list.
Remove the chosen frontier cell from the list of frontier cells.
您的问题的简单答案是，在添加边缘时，您需要检查该边缘是否意味着移除作为其任何相邻墙块的最后邻居的墙。
这将防止任何墙壁仅通过拐角连接。
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() 的示例输出是：
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓ ▓ ▓ ▓ ▓▓
▓ ▓▓▓ ▓▓▓▓▓▓▓▓▓ ▓▓▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓▓
▓ ▓▓▓▓▓ ▓ ▓ ▓▓▓ ▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓▓▓▓▓▓▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓▓
▓ ▓▓▓ ▓ ▓▓▓ ▓ ▓ ▓▓▓▓▓▓
▓ ▓ ▓ ▓ ▓ ▓ ▓▓
▓ ▓▓▓▓▓ ▓▓▓ ▓ ▓ ▓▓▓ ▓▓
▓ ▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓▓▓ ▓▓▓▓▓▓▓▓▓▓
▓ ▓ ▓ ▓ ▓ ▓▓
▓ ▓▓▓▓▓▓▓ ▓ ▓▓▓▓▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓ ▓▓
▓▓▓ ▓▓▓ ▓▓▓ ▓ ▓▓▓▓▓ ▓▓
▓ ▓ ▓▓
▓▓▓ ▓ ▓▓▓ ▓▓▓ ▓▓▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓ ▓▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
在我完全研究这个问题之前，我自己想出了一些完全不同的东西。看看您是否认为这是一种有用的方法。
很久以前，当我看到 IBM PC Character Graphics（代码页中的字形）时，我想到了以这种方式创建迷宫。我的方法分为两个阶段：
- 在整数数组中生成迷宫，使用位编码值 1-15 指示在迷宫的每个单元格处打开的方向
- 将其呈现为可见形式。所以在我展示迷宫之前，墙壁不是考虑因素。
每个单元格都从 0（未选中）开始，然后可以打开 4 个位中的任何一个（1 = 向右，2 = 向下，4 = 向左，8 = 向上）。天真地，您可以在每个单元格中从 1-15 中选择一个随机数，除了五件事：
- 首先在整个阵列周围绘制 "wall" 走廊和拐角，并在两个点留下一个通道。这是处理边界条件的最简单方法。
- 权衡选择，使死胡同很少见，直的或拐角的走廊很常见，完整的交叉路口很少见。
- 将每个单元格与其周围已设置的单元格相匹配：如果相邻单元格的相应位开启（左侧单元格中的 1 位，依此类推）强制该单元格中的该位开启，如果它已关闭，请在此单元格中强制关闭它。
- 找到一种方法来确保开始和结束挂钩（这里需要进一步研究）。
- 设法填充所有单元格而不产生空隙（需要更多研究）。
下面是"raw"数组的字符图形显示：
┌│───────┐
│└─┐┌┐│ │
││┌┴┤│├─┐│
│├┴─┘│└┐││
│└─┐──┐│││
│┌┬┴─┌┘│││
││├┐│└┬┘││
│└┤│└┬┴─┤│
│─┴┴─┘──┤│
└───────│┘
渲染结果时，我使用 3x4 字符图形网格显示每个单元格。这是一个例子：
╔═══╡ ╞═══════════════════════════════╗
║░░░│ │░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░║
║░░╔╡ ╞════════════════════════════╗░░║
║░░║│ └───────┐┌──────┐┌──┐ ║░░║
║░░║│ ││ ││ │ ║░░║
║░░║└───────┐ ││ ┌┐ ││ │ ║░░║
║░░║┌──┐┌───┘ └┘ ││ ││ └───────┐║░░║
║░░║│ ││ ││ ││ │║░░║
║░░║│ ││ ┌────┐ ││ ││ ┌────┐ │║░░║
║░░║│ └┘ └────┘ ││ ││ └───┐│ │║░░║
║░░║│ ││ ││ ││ │║░░║
║░░║│ ┌───────────┘└──┘└───┐ ││ │║░░║
║░░║│ └───────┐┌──────────┐│ ││ │║░░║
║░░║│ ││ ││ ││ │║░░║
║░░║└───────┐ │└───────┐ │└──┘│ │║░░║
║░░║┌───────┘ └───┐┌───┘ │┌──┐│ │║░░║
║░░║│ ││ ││ ││ │║░░║
║░░║│ ┌┐ ┌───────┘│ ┌───┘│ ││ │║░░║
║░░║│ ││ └───┐┌──┐│ └────┘ ││ │║░░║
║░░║│ ││ ││ ││ ││ │║░░║
║░░║│ ││ ┌┐ ││ │└───┐ ┌───┘│ │║░░║
║░░║│ └┘ ││ ││ └────┘ └────┘ │║░░║
║░░║│ ││ ││ │║░░║
║░░║└───┐ ││ │└───┐ ┌────────┐ │║░░║
║░░║┌───┘ └┘ └────┘ │┌───────┘ │║░░║
║░░║│ ││ │║░░║
║░░║└──────────────────┘└───────┐ │║░░║
║░░╚════════════════════════════╡ ╞╝░░║
║░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░│ │░░░║
╚═══════════════════════════════╡ ╞═══╝
看看你能用这个方法做什么。 （不同的字体选择使它看起来比这里更好，线条都无缝连接 - 当然必须是等宽的）。
以下是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:
*
* @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 的完整可运行代码在 this 存储库中可用。
我正在尝试使用 Prim 算法实现随机生成的迷宫。
我希望我的迷宫看起来像这样：
然而，我从我的程序中生成的迷宫看起来像这样：
我目前无法正确执行以粗体突出显示的步骤：
- Start with a grid full of walls.
- Pick a cell, mark it as part of the maze. Add the walls of the cell to the wall list.
- While there are walls in the list:
- **1. Pick a random wall from the list. If the cell on the opposite side isn't in the maze yet:
- Make the wall a passage and mark the cell on the opposite side as part of the maze.**
- Add the neighboring walls of the cell to the wall list.
- Remove the wall from the list.
来自 this article on maze generation.
如何确定一个单元格是否是墙列表的有效候选者？我想更改我的算法以生成正确的迷宫。任何能帮助我解决问题的想法都将不胜感激。
尝试在程序开始时用独特的随机权重对墙壁进行加权。该权重列表永远不会改变。当您从可用墙列表中选择下一堵墙时，请选择重量最小的墙。
您的解决方案看起来并没有错。特别是，它是一个迷宫，并且（如果您不能沿对角线行走）从每个（开放）位置到彼此（开放）位置都有唯一的路径。唯一的问题似乎是样式。
如果你考虑你发布的 "correct" 迷宫，没有外边框，并将左上角的单元格设为 (0,0)，你可以观察到通道和墙壁在某种意义上是交替的。两个坐标均为偶数的每个单元格都必须是一条通道，而两个坐标均为奇数的每个单元格必须是一堵墙。因此，您唯一可以选择的单元格是一个坐标为偶数而另一个坐标为奇数的单元格。
让字段中间的一个单元格 (x,y) 给出，其中两个坐标都是偶数。这个细胞必须是一个通道。单元格 (x-1,y)、(x+1,y)、(x,y-1) 和 (x,y+1) 是它周围的势墙，单元格 (x-2,y)、(x+2,y)、(x,y-2) 和 (x,y+2) 分别是那些墙对面的正方形。
有了这些信息，您就可以实现您的算法，附加要求是在第 2 步中，您必须选择两个坐标都为偶数的单元格。
维基百科文章中的描述确实值得改进。
文章的第一个令人困惑的部分是，随机 Prim 算法的描述没有详细说明该算法使用的假定数据结构。因此，像 "opposite cell" 这样的短语变得令人困惑。
基本上有 2 种主要方法 "maze generator programmers" 可以选择：
- 牢房有墙壁或通往其 4 个邻居的通道。关于 walls/passages 的信息被存储和操纵。
- 单元格可以被阻塞（墙壁）或通道，而不存储任何额外的连接信息。
根据 reader 在阅读算法描述时想到的模型 (1) 或 (2)，他们要么理解要么不理解。
我个人更喜欢将单元格用作墙壁或通道，而不是摆弄专用的 passage/wall 信息。
然后，"frontier" 补丁与段落的距离为 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
一个由此产生的迷宫看起来像这样：
这里尝试用维基百科 "algorithm" 风格描述我的解决方案：
- A Grid consists of a 2 dimensional array of cells.
- A Cell has 2 states: Blocked or Passage.
- Start with a Grid full of Cells in state Blocked.
- Pick a random Cell, set it to state Passage and Compute its frontier cells. A frontier cell of a Cell is a cell with distance 2 in state Blocked and within the grid.
- While the list of frontier cells is not empty:
- Pick a random frontier cell from the list of frontier cells.
- Let neighbors(frontierCell) = All cells in distance 2 in state Passage. Pick a random neighbor and connect the frontier cell with the neighbor by setting the cell in-between to state Passage. Compute the frontier cells of the chosen frontier cell and add them to the frontier list. Remove the chosen frontier cell from the list of frontier cells.
您的问题的简单答案是，在添加边缘时，您需要检查该边缘是否意味着移除作为其任何相邻墙块的最后邻居的墙。
这将防止任何墙壁仅通过拐角连接。
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() 的示例输出是：
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓ ▓ ▓ ▓ ▓▓
▓ ▓▓▓ ▓▓▓▓▓▓▓▓▓ ▓▓▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓▓
▓ ▓▓▓▓▓ ▓ ▓ ▓▓▓ ▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓▓▓▓▓▓▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓▓
▓ ▓▓▓ ▓ ▓▓▓ ▓ ▓ ▓▓▓▓▓▓
▓ ▓ ▓ ▓ ▓ ▓ ▓▓
▓ ▓▓▓▓▓ ▓▓▓ ▓ ▓ ▓▓▓ ▓▓
▓ ▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓▓▓ ▓▓▓▓▓▓▓▓▓▓
▓ ▓ ▓ ▓ ▓ ▓▓
▓ ▓▓▓▓▓▓▓ ▓ ▓▓▓▓▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓ ▓▓
▓▓▓ ▓▓▓ ▓▓▓ ▓ ▓▓▓▓▓ ▓▓
▓ ▓ ▓▓
▓▓▓ ▓ ▓▓▓ ▓▓▓ ▓▓▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓ ▓▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
在我完全研究这个问题之前，我自己想出了一些完全不同的东西。看看您是否认为这是一种有用的方法。
很久以前，当我看到 IBM PC Character Graphics（代码页中的字形）时，我想到了以这种方式创建迷宫。我的方法分为两个阶段：
- 在整数数组中生成迷宫，使用位编码值 1-15 指示在迷宫的每个单元格处打开的方向
- 将其呈现为可见形式。所以在我展示迷宫之前，墙壁不是考虑因素。
每个单元格都从 0（未选中）开始，然后可以打开 4 个位中的任何一个（1 = 向右，2 = 向下，4 = 向左，8 = 向上）。天真地，您可以在每个单元格中从 1-15 中选择一个随机数，除了五件事：
- 首先在整个阵列周围绘制 "wall" 走廊和拐角，并在两个点留下一个通道。这是处理边界条件的最简单方法。
- 权衡选择，使死胡同很少见，直的或拐角的走廊很常见，完整的交叉路口很少见。
- 将每个单元格与其周围已设置的单元格相匹配：如果相邻单元格的相应位开启（左侧单元格中的 1 位，依此类推）强制该单元格中的该位开启，如果它已关闭，请在此单元格中强制关闭它。
- 找到一种方法来确保开始和结束挂钩（这里需要进一步研究）。
- 设法填充所有单元格而不产生空隙（需要更多研究）。
下面是"raw"数组的字符图形显示：
┌│───────┐
│└─┐┌┐│ │
││┌┴┤│├─┐│
│├┴─┘│└┐││
│└─┐──┐│││
│┌┬┴─┌┘│││
││├┐│└┬┘││
│└┤│└┬┴─┤│
│─┴┴─┘──┤│
└───────│┘
渲染结果时，我使用 3x4 字符图形网格显示每个单元格。这是一个例子：
╔═══╡ ╞═══════════════════════════════╗
║░░░│ │░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░║
║░░╔╡ ╞════════════════════════════╗░░║
║░░║│ └───────┐┌──────┐┌──┐ ║░░║
║░░║│ ││ ││ │ ║░░║
║░░║└───────┐ ││ ┌┐ ││ │ ║░░║
║░░║┌──┐┌───┘ └┘ ││ ││ └───────┐║░░║
║░░║│ ││ ││ ││ │║░░║
║░░║│ ││ ┌────┐ ││ ││ ┌────┐ │║░░║
║░░║│ └┘ └────┘ ││ ││ └───┐│ │║░░║
║░░║│ ││ ││ ││ │║░░║
║░░║│ ┌───────────┘└──┘└───┐ ││ │║░░║
║░░║│ └───────┐┌──────────┐│ ││ │║░░║
║░░║│ ││ ││ ││ │║░░║
║░░║└───────┐ │└───────┐ │└──┘│ │║░░║
║░░║┌───────┘ └───┐┌───┘ │┌──┐│ │║░░║
║░░║│ ││ ││ ││ │║░░║
║░░║│ ┌┐ ┌───────┘│ ┌───┘│ ││ │║░░║
║░░║│ ││ └───┐┌──┐│ └────┘ ││ │║░░║
║░░║│ ││ ││ ││ ││ │║░░║
║░░║│ ││ ┌┐ ││ │└───┐ ┌───┘│ │║░░║
║░░║│ └┘ ││ ││ └────┘ └────┘ │║░░║
║░░║│ ││ ││ │║░░║
║░░║└───┐ ││ │└───┐ ┌────────┐ │║░░║
║░░║┌───┘ └┘ └────┘ │┌───────┘ │║░░║
║░░║│ ││ │║░░║
║░░║└──────────────────┘└───────┐ │║░░║
║░░╚════════════════════════════╡ ╞╝░░║
║░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░│ │░░░║
╚═══════════════════════════════╡ ╞═══╝
看看你能用这个方法做什么。 （不同的字体选择使它看起来比这里更好，线条都无缝连接 - 当然必须是等宽的）。
以下是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:
*
* @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 的完整可运行代码在 this 存储库中可用。