Core code sharing of generating random maze algorithm implemented by python (including complete game code)
- 2020-04-02 13:50:30
- OfStack
Complete code download: (link: http://xiazai.jb51.net/201407/tools/python-migong.rar)
Recently, I studied the maze generation algorithm and then made a simple online maze game. The game address and the corresponding open source project address can be found through the link above. The server-side code is not included in the open source project because it is too simple. The following is a brief introduction to the random maze generation algorithm. Once you understand it, you'll see how simple the algorithm is.
1. Divide the maze map into multiple rooms, each with four walls.
2. Have the "person" start at any point A on the map and start wandering around the maze. Proceed in either of the 1/2/3/4 directions in room A. As you walk from room A to room B, pull down the wall between room A/B.
3. If the room opposite direction x has already passed, choose another direction. If the rooms in all directions have already been crossed, step back to the previous room to see if there is an alternative path.
4. When there is really no way out, you have walked through all the rooms and the maze is ready.
Here is the python implementation of the algorithm (the core part)
def gen_map(self, max_x=10, max_y=10):
""" Generate a maze """
self.max_x, self.max_y = max_x, max_y # Set the map size
self.mmap = [[None for j in range(self.max_y)] for i in range(self.max_x)] # Generate the original map
self.solution = [] # Maze solution
block_stack = [Block(self, 0, 0)] # from 0,0 Start generating the maze (and use this as the starting point) and place the starting point on the stack
while block_stack:
block = block_stack.pop() # Take out the current room
next_block = block.get_next_block() # Get the next room to go to
if next_block: # If the next post is successfully obtained, place the room you passed back on the stack
block_stack.append(block)
block_stack.append(next_block)
if next_block.x == self.max_x - 1 and next_block.y == self.max_y - 1: # When we get to the end, the path in the stack is the solution
for o in block_stack:
self.solution.append((o.x, o.y))
def get_next_block_pos(self, direction):
""" Gets the room number for the specified direction """
x = self.x
y = self.y
if direction == 0: # Top
y -= 1
elif direction == 1: # Right
x += 1
if direction == 2: # Bottom
y += 1
if direction == 3: # Left
x -= 1
return x, y
def get_next_block(self):
""" Get the next room to go to """
directions = list(range(4))
random.shuffle(directions) # Pick a random direction to go
for direction in directions:
x, y = self.get_next_block_pos(direction)
if x >= self.mmap.max_x or x < 0 or y >= self.mmap.max_y or y < 0: # The room number is in range
continue
if self.mmap.mmap[x][y]: # If you've already walked
continue
self.walls[direction] = False
return Block(self.mmap, x, y, direction)
return None # No available room was found
Note: since the number of branches of maze paths generated by this method is not too large, the coffeescript version adds random processing to the maze generation process, and the corresponding algorithm is slightly more complex.