我正在尝试使用Prim算法实现一个随机生成的迷宫。
我希望我的迷宫看起来像这样:
然而，我从程序生成的迷宫看起来像这样:
我目前卡在了正确实现粗体步骤上：
- 开始时，将网格填满墙壁。
- 选择一个单元格，将其标记为迷宫的一部分。将该单元格的墙壁添加到墙壁列表中。
- 当列表中有墙壁时:
- **1. 从列表中随机选择一堵墙。如果对面的单元格还没有在迷宫中：
- 将墙壁改为通道，并将对面的单元格标记为迷宫的一部分。
- 将该单元格的相邻墙壁添加到墙壁列表中。
- 从列表中删除该墙壁。
来自 此迷宫生成算法文章。
如何确定一个单元格是否是墙列表的有效候选项？我想改变算法以便生成正确的迷宫。任何能帮助我解决问题的想法都将不胜感激。
维基百科文章中的描述确实需要改进。
文章的第一个令人困惑的部分是，随机 Prim 算法的描述没有详细说明算法所使用的假设数据结构。因此，“相反的单元格”等短语变得令人困惑。
基本上，“迷宫生成程序员”可以选择两种主要方法：
根据读者在阅读算法描述时心中的模型(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个阻塞单元格以内且在网格内的单元格。
- 当前沿单元格列表不为空时：
- 从前沿单元格列表中随机选择一个前沿单元格。
- 让neighbors(frontierCell) = 距离2个通道单元格的所有单元格。 随机选择一个邻居，并通过将中间的单元格设置为通道状态将前沿单元格与邻居相连。 计算所选前沿单元格的前沿单元格并将它们添加到前沿列表中。 从前沿单元格列表中删除所选前沿单元格。
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() 的示例输出如下：
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓ ▓ ▓ ▓ ▓▓
▓ ▓▓▓ ▓▓▓▓▓▓▓▓▓ ▓▓▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓▓
▓ ▓▓▓▓▓ ▓ ▓ ▓▓▓ ▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓▓▓▓▓▓▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓▓
▓ ▓▓▓ ▓ ▓▓▓ ▓ ▓ ▓▓▓▓▓▓
▓ ▓ ▓ ▓ ▓ ▓ ▓▓
▓ ▓▓▓▓▓ ▓▓▓ ▓ ▓ ▓▓▓ ▓▓
▓ ▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓▓▓ ▓▓▓▓▓▓▓▓▓▓
▓ ▓ ▓ ▓ ▓ ▓▓
▓ ▓▓▓▓▓▓▓ ▓ ▓▓▓▓▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓ ▓▓
▓▓▓ ▓▓▓ ▓▓▓ ▓ ▓▓▓▓▓ ▓▓
▓ ▓ ▓▓
▓▓▓ ▓ ▓▓▓ ▓▓▓ ▓▓▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓ ▓▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
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://dev59.com/QF0a5IYBdhLWcg3w-87a#29758926
*
* @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。你可以在这里找到。
(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) 是相应墙壁对面的方块。在过程的最开始，尝试使用唯一随机权重加权墙壁。该权重列表将永远不会改变。当您从可用墙壁列表中选择下一个墙壁时，请选择具有最小权重的墙壁。
┌│───────┐
│└─┐┌┐│ │
││┌┴┤│├─┐│
│├┴─┘│└┐││
│└─┐──┐│││
│┌┬┴─┌┘│││
││├┐│└┬┘││
│└┤│└┬┴─┤│
│─┴┴─┘──┤│
└───────│┘
╔═══╡ ╞═══════════════════════════════╗
║░░░│ │░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░║
║░░╔╡ ╞════════════════════════════╗░░║
║░░║│ └───────┐┌──────┐┌──┐ ║░░║
║░░║│ ││ ││ │ ║░░║
║░░║└───────┐ ││ ┌┐ ││ │ ║░░║
║░░║┌──┐┌───┘ └┘ ││ ││ └───────┐║░░║
║░░║│ ││ ││ ││ │║░░║
║░░║│ ││ ┌────┐ ││ ││ ┌────┐ │║░░║
║░░║│ └┘ └────┘ ││ ││ └───┐│ │║░░║
║░░║│ ││ ││ ││ │║░░║
║░░║│ ┌───────────┘└──┘└───┐ ││ │║░░║
║░░║│ └───────┐┌──────────┐│ ││ │║░░║
║░░║│ ││ ││ ││ │║░░║
║░░║└───────┐ │└───────┐ │└──┘│ │║░░║
║░░║┌───────┘ └───┐┌───┘ │┌──┐│ │║░░║
║░░║│ ││ ││ ││ │║░░║
║░░║│ ┌┐ ┌───────┘│ ┌───┘│ ││ │║░░║
║░░║│ ││ └───┐┌──┐│ └────┘ ││ │║░░║
║░░║│ ││ ││ ││ ││ │║░░║
║░░║│ ││ ┌┐ ││ │└───┐ ┌───┘│ │║░░║
║░░║│ └┘ ││ ││ └────┘ └────┘ │║░░║
║░░║│ ││ ││ │║░░║
║░░║└───┐ ││ │└───┐ ┌────────┐ │║░░║
║░░║┌───┘ └┘ └────┘ │┌───────┘ │║░░║
║░░║│ ││ │║░░║
║░░║└──────────────────┘└───────┐ │║░░║
║░░╚════════════════════════════╡ ╞╝░░║
║░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░│ │░░░║
╚═══════════════════════════════╡ ╞═══╝
看看您可以用这种方法做什么。（不同的字体选择使它看起来比这里更好，所有行都无缝连接-当然必须是等宽字体）。
我认为你的代码没有按预期工作，因为你忘记在前沿单元格列表中删除两个相同的前沿单元格。请注意，两个通道单元格可以共享同一个前沿单元格。