Python prim algorithm generates maze

Before , We used... In another article Prim The algorithm generates a perfect maze , Using the method of traversing the grid , This time, , We will teach you how to generate by traversing the wall , Link to previous article ：Python Prim Algorithm Create mazes _Leleprogrammer The blog of -CSDN Blog _prim Algorithms generate mazes Prim Algorithm generates perfect maze matrix https://blog.csdn.net/leleprogrammer/article/details/124205148?spm=1001.2014.3001.5501

We need a random library random, And used to calculate the algorithm usage time time modular

Import these modules

import random as rd
import time

Let's define a function

def createMaze(a,b): # a:width b:height

Add a variable to store the start time of the algorithm

startTime=time.time()

Definition maze

maze={}

maze Used to store maze maps , The format is as follows ：

{(n,"u"):0}

n It means the first one n Block ,u d l r They represent the upper, lower, left and right walls ,0 No walls ,1 It means there are walls , The initial is all for 1, The generated code is as follows ：

 for n in range(a*b):
for face in ["u","d","l","r"]:
maze[(n,face)]=1

Create two variables

 history=[]
walls=[]

First, select a block randomly and add it to the traversed block

block=rd.choice(list(maze.keys()))[0]
history.append(block)

Add the corresponding walls of the four faces of the block to the list of candidate walls

 for face in ["u","d","l","r"]:
walls.append((block,face))

As long as the candidate wall is not empty, it will cycle all the time

while len(walls)!=0:

Select a wall , Get the two blocks separated by the wall , If you have reached the boundary , Then for None. Be careful , In the last elif In , obtain len(maze) Divide by 4, Because each of us has 4 Walls in different directions , This is also a point that is easy to overlook .

 wall=rd.choice(walls)
twoBlocks=[wall[0]]
faces=[wall[1]]
if wall[1]=="u":
if wall[0]-a<0:
twoBlocks.append(None)
else:
twoBlocks.append(wall[0]-a)
faces.append("d")
elif wall[1]=="r":
if (wall[0]+1)%a!=0:
twoBlocks.append(wall[0]+1)
faces.append("l")
else:
twoBlocks.append(None)
elif wall[1]=="l":
if wall[0]%a!=0:
twoBlocks.append(wall[0]-1)
faces.append("r")
else:
twoBlocks.append(None)
elif wall[1]=="d":
if wall[0]+a>len(maze)/4-1:
twoBlocks.append(None)
else:
twoBlocks.append(wall[0]+a)
faces.append("u")

Define two more lists

 ins=[]
infaces=[]

Get the two boxes that have been added to history Of

 for i,oneBlock in enumerate(twoBlocks):
if oneBlock in history:
ins.append(oneBlock)
infaces.append(faces[i])

Because only one has been traversed , So we need to delete the wall between the two blocks , Actually, there are two sides , One side is the first block , The other is in the opposite direction of the second block , It just overlaps , We need to set the corresponding values of these two walls to 0, First of all get mirrorFace, In the opposite direction , If None In the list of these two squares , So one of the blocks is on the edge , So there is no need to delete this wall , Keep this wall , Delete this wall directly from the candidate wall and start a new cycle , Use continue; If he's not a piece on the side , in other words twoBlocks There's no None, Just remove the wall of the first block （ Change it to 0）, Then get another block and put it in other variable , Then change the wall of the second block to 0, Then add this second block to history in , Then add the four walls of the second block to the candidate wall , Be careful , The value of the wall to be added here must be 1, That is, the walls that have not been checked and traversed , If the candidate wall already has this wall , There is no need to add , use for Circulation and if The statement is tie-in , You can simply write this code , It's not difficult to write when the logic is clear ！ The code is as follows ：

 if len(ins)==1:
mirrorFace=None
if infaces[0]=="u":
mirrorFace="d"
elif infaces[0]=="d":
mirrorFace="u"
elif infaces[0]=="r":
mirrorFace="l"
elif infaces[0]=="l":
mirrorFace="r"
if not (None in twoBlocks):
maze[(ins[0],infaces[0])]=0
other=None
if ins[0]==twoBlocks[0]:
other=twoBlocks[1]
else:
other=twoBlocks[0]
maze[(other,mirrorFace)]=0
walls.remove(wall)
history.append(other)
for face in ["u","l","r","d"]:
if maze.get((other,face))==1 and not ((other,face) in walls):
walls.append((other,face))
else:
walls.remove(wall)
continue
elif len(ins)==2:
walls.remove(wall)

Write here , Our algorithm is almost over , Final addition endTime Get the algorithm end time

endTime=time.time()

And output it to the console

print(f" Generation maze usage time ：{endTime-startTime} second ")

Return to maze

return maze

This algorithm is very fast ,99x99 The maze took only three seconds , Generally, more than 30 times more than 30 only generate 30 millisecond , It's very efficient ！

Next up ：

Next article , We're going to use Pygame Draw the whole process of the maze generation , Don't forget to pay attention to me , See more teaching ！