Embedding a randomly created maze using Prim Algorithm

Question

I am trying to implement a randomly generated maze using the Prim algorithm.

I want my maze to look like this:

however, the mazes that I generate from my program look like this:

I am now obsessed with the correct execution of the steps in bold:

• Start with a grid full of walls.
• Select a cell, mark it as part of the maze. Add cell walls to the wall list.
• While there are walls in the list:
  • ** 1. Select a random wall from the list. If the cell on the opposite side is not yet in the maze:
    • • Make the wall a passage and mark the cell on the opposite side as part of the maze. **
    • 2. Add adjacent cell walls to the wall list.
• 2. Remove the wall from the list.

from in this article about labyrinth generation.

How to determine if a cell is a valid candidate for a list on the wall? I would like to change my algorithm so that it creates the correct maze. Any ideas that will help me solve my problem will be appreciated.

Answer 1

The description on the Wikipedia article really deserves improvement.

The first confusing part of the article is that the description of the randomized Prim algorithm does not clarify the intended data structure used by the algorithm. Thus, phrases such as “opposite cell” get confused.

Basically, there are two main approaches: "labyrinth programmers-generators" can choose:

• Cells have walls or walkways to their 4 neighbors. Wall / walkway information is stored and processed.
• Cells can be blocked (walls) or walkways without saving additional connection information.

Depending on which model (1) or (2) the reader has in mind when reading the description of the algorithm, they either understand or do not understand.

Personally, I prefer to use the cells as walls or walkways, rather than messing around with highlighted pass / wall information.

Then the "border" sections have a distance of 2 (and not 1) from the passage. A random border patch from the list of border patches is selected and connected to a random neighboring passage (at a distance of 2), also making a cell between the border patch and the neighboring passage.

Here is my F # implementation, what it looks like:

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 yx 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 yx 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 

The resulting maze may look like this:

Here's an attempt to describe my solution in the "algorithm" style of Wikipedia:

• The grid consists of a 2-dimensional array of cells.
• A cell has 2 states: blocked or passing.
• Start with a grid full of cells in the Locked state.
• Select a random cell, set it to Pass and Calculate Your Border Cells. A border cell of a cell is a cell with a distance of 2 in the "Blocked" state and inside the grid.
• While the list of border cells is not empty:
  • Select a random border cell from the list of border cells.
  • Let adjacent (frontierCell) = all cells at a distance of 2 in the Passage state. Select a random neighbor and connect the border cell to the neighbor by setting the gateway to Passage. Calculate the border cells of the selected border cell and add them to the list of borders. Remove the selected border cell from the list of border cells.

Answer 2

Simple implementation of Java Prim algorithm:

 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(); } } 

Sample output new Maze(20,20).toString() :

 ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓ ▓ ▓ ▓ ▓ ▓▓ ▓ ▓▓▓ ▓▓▓▓▓▓▓▓▓ ▓▓▓ ▓▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓▓ ▓ ▓▓▓▓▓ ▓ ▓ ▓▓▓ ▓ ▓ ▓▓ ▓ ▓ ▓ ▓ ▓ ▓▓ ▓ ▓ ▓ ▓ ▓ ▓▓▓▓▓▓▓ ▓ ▓▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓▓ ▓ ▓▓▓ ▓ ▓▓▓ ▓ ▓ ▓▓▓▓▓▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓▓ ▓ ▓▓▓▓▓ ▓▓▓ ▓ ▓ ▓▓▓ ▓▓ ▓ ▓ ▓ ▓▓ ▓ ▓ ▓ ▓ ▓▓▓ ▓▓▓▓▓▓▓▓▓▓ ▓ ▓ ▓ ▓ ▓ ▓▓ ▓ ▓▓▓▓▓▓▓ ▓ ▓▓▓▓▓ ▓ ▓▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓▓ ▓▓▓ ▓▓▓ ▓▓▓ ▓ ▓▓▓▓▓ ▓▓ ▓ ▓ ▓▓ ▓▓▓ ▓ ▓▓▓ ▓▓▓ ▓▓▓ ▓ ▓▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓▓ ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓ ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓ 

Answer 3

Try to consider walls with a unique random weight at the very beginning of the procedure. This list of weights will never change. When you select the next wall from the list of available walls, select the wall with the minimum weight.

Answer 4

Your decision does not look right. In particular, it is a labyrinth, and (if you cannot walk diagonally) there is a unique path from each (open) location to each other (open) space. The only problem with it seems to be in style.

If you look at the “right” labyrinth that you placed, without an outer border, and take the dead-end cell to be (0,0) , you can observe that the passages and walls, in a sense, alternate. Each cell where both coordinates are even must be a passage, and each cell where both coordinates are odd must be a wall. Thus, the only cells in which you have a choice are those where one coordinate is even and the other is strange.

Let the cell (x,y) be in the middle of the field, where both coordinates are even. This cell should be a passage. Cells (x-1,y) , (x+1,y) , (x,y-1) and (x,y+1) are the potential walls surrounding it, and cells (x-2,y) , (x+2,y) , (x,y-2) and (x,y+2) squares on the extremes of those walls, respectively.

With this information, you can simply implement the algorithm with the additional requirement that in step 2 you should select a cell in which both coordinates are even.

Answer 5

The simple answer to your question is that when adding an edge you need to check if the edge takes the removal of a wall that is the last neighbor of any of the adjacent parts of the wall.

This will prevent any walls from connecting to the corner only.

Answer 6

By myself, I came up with something completely different before I investigated the problem in general. See if you think this is a useful approach.

Once upon a time, when I saw the graphics of the IBM PC characters (glyphs that are part of the code page), I was thinking of creating mazes in this way. My approach consists of two stages:

• Creating a maze in an array of integers using bit-coded values ​​1-15 to indicate the directions open in each cell of the maze.
• Rendering its visible form. So the walls are not examined until I show the maze.

Each cell starts at 0 (not selected), and then any of 4 bits can be turned on (1 = right, 2 = down, 4 = left, 8 = up). Naively, you can just pick a random number from 1 to 15 in each cell, with the exception of five things:

• Start by drawing a “wall” of corridors and corners around the entire array and leave the passage at two points. This is the easiest way to deal with boundary conditions.
• Weighted choice, so dead ends are rare, and straight or corner corridors are common, full intersections are infrequent.
• Compare each cell with those already installed around it: if the neighboring cell has the corresponding On bit (1 bit in the cell on the left, etc.), force this bit in this cell, and if it is Off, disable it in this cell.
• Find a way to make sure the beginning and end of the connection (more research is needed).
• Manage the filling of all cells and not create voids (more research is needed).

This displays a raw array in terms of graphic characters:

  ┌│───────┐ │└─┐┌┐│ │ ││┌┴┤│├─┐│ │├┴─┘│└┐││ │└─┐──┐│││ │┌┬┴─┌┘│││ ││├┐│└┬┘││ │└┤│└┬┴─┤│ │─┴┴─┘──┤│ └───────│┘ 

When rendering the result, I show each cell using a 3x4 character grid. Here is an example:

 ╔═══╡ ╞═══════════════════════════════╗ ║░░░│ │░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░║ ║░░╔╡ ╞════════════════════════════╗░░║ ║░░║│ └───────┐┌──────┐┌──┐ ║░░║ ║░░║│ ││ ││ │ ║░░║ ║░░║└───────┐ ││ ┌┐ ││ │ ║░░║ ║░░║┌──┐┌───┘ └┘ ││ ││ └───────┐║░░║ ║░░║│ ││ ││ ││ │║░░║ ║░░║│ ││ ┌────┐ ││ ││ ┌────┐ │║░░║ ║░░║│ └┘ └────┘ ││ ││ └───┐│ │║░░║ ║░░║│ ││ ││ ││ │║░░║ ║░░║│ ┌───────────┘└──┘└───┐ ││ │║░░║ ║░░║│ └───────┐┌──────────┐│ ││ │║░░║ ║░░║│ ││ ││ ││ │║░░║ ║░░║└───────┐ │└───────┐ │└──┘│ │║░░║ ║░░║┌───────┘ └───┐┌───┘ │┌──┐│ │║░░║ ║░░║│ ││ ││ ││ │║░░║ ║░░║│ ┌┐ ┌───────┘│ ┌───┘│ ││ │║░░║ ║░░║│ ││ └───┐┌──┐│ └────┘ ││ │║░░║ ║░░║│ ││ ││ ││ ││ │║░░║ ║░░║│ ││ ┌┐ ││ │└───┐ ┌───┘│ │║░░║ ║░░║│ └┘ ││ ││ └────┘ └────┘ │║░░║ ║░░║│ ││ ││ │║░░║ ║░░║└───┐ ││ │└───┐ ┌────────┐ │║░░║ ║░░║┌───┘ └┘ └────┘ │┌───────┘ │║░░║ ║░░║│ ││ │║░░║ ║░░║└──────────────────┘└───────┐ │║░░║ ║░░╚════════════════════════════╡ ╞╝░░║ ║░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░│ │░░░║ ╚═══════════════════════════════╡ ╞═══╝ 

See what you can do with this method. (A different choice of font makes it better than here, all lines are connected easily - of course, they must be monospaced).