Article | doug \
Source: Python Technology “ID: pythonall”
I believe we have played the maze game, for the simple maze, we can see the path at a glance, but for the complex maze, may have to carefully look for a long time, or even spend a few days, and then may have to respectively from the entrance and exit to find the path, or even may not find the path. \
Although the maze problem is complicated for us humans, it is very simple for computers. Why do you say that? Because there are rules to follow that seem complicated.
What we can do is take a long rope and go straight from the entrance, take the leftmost fork if there is a fork, until we come to a dead end or find a way out. If it’s A dead end, go back to the last fork, which we call fork A,
Then enter the second fork on the left and repeat the steps of the first fork until you find a way out or back out of a dead end. When you have gone through all the branches of the road and have not found A way out, walk back along the rope to the intersection B before fork A and repeat the process.
I don’t know if you noticed, but it’s just a recursive process, and that’s what computers are good at.
The maze algorithm above is known as depth-first traversal, as opposed to breadth-first traversal. With the theoretical basis, we will try to use procedures to achieve a maze of small procedures.
Let’s take a look at the final effect video.
Generate a maze
There are many kinds of algorithms to generate mazes. The most common ones are recursive backtracking, recursive segmentation and random Prim algorithm. Today is the last one we will use.
The main steps of the algorithm are as follows:
1, the maze rows and columns must be odd2, the intersection of odd rows and odd columns is a road, and the remaining points are walls. The maze is surrounded by walls3, select a cell as a path (in this case select [1.1], and then add its adjacent wall to the list wall4When a list wall contains a wall:4.1Select a wall at random from the list if only one of the two cells separated by the wall has been accessed4.11.Then remove the wall from the list and knock it through4.12., marks the cell as visited4.13.Add the adjacent wall of the unaccessed cell to list wall4.2If both sides of the wall have already been accessed, remove the wall from the listCopy the codeWe define a Maze class with a two-dimensional array representing the Maze map, with 1 for the wall and 0 for the path, initialize the upper left corner for the entrance and the lower right corner for the exit, and define the direction vector.
class Maze:
def __init__(self, width, height):
self.width = width
self.height = height
self.map = [[0 if x % 2= =1 and y % 2= =1 else 1 for x in range(width)] for y in range(height)]
self.map[1] [0] = 0The self # entry.map[height - 2][width - 1] = 0Self. Visited = [] # right up left down self.1.0.- 1.0]
self.dy = [0.- 1.0.1]
Copy the codeNext comes the main function that generates the maze.
def generate(self):
start = [1.1]
self.visited.append(start)
wall_list = self.get_neighbor_wall(start)
while wall_list:
wall_position = random.choice(wall_list)
neighbor_road = self.get_neighbor_road(wall_position)
wall_list.remove(wall_position)
self.deal_with_not_visited(neighbor_road[0], wall_position, wall_list)
self.deal_with_not_visited(neighbor_road[1], wall_position, wall_list)
Copy the codeThere are two main functions in this function: get_neighbor_road(point) and deal_with_not_visited(). The former retrieves the neighboring node of the passed coordinate point, and returns a two-dimensional array. The latter deal_with_not_visited() function handles the logic of step 4.1.
The Prim random algorithm randomly selects all the cells in the list, and the probability of newly added cells being selected is the same as that of old ones. Therefore, it has more branches, and the maze is more complex and difficult, and of course looks more natural. Take a look at the maze we created.
[1.1.1.1.1.1.1.1.1.1.1]
[0.0.0.0.0.0.0.0.0.0.1]
[1.1.1.1.1.0.1.1.1.1.1]
[1.0.0.0.0.0.0.0.0.0.1]
[1.1.1.0.1.0.1.0.1.0.1]
[1.0.0.0.1.0.1.0.1.0.1]
[1.0.1.0.1.0.1.1.1.1.1]
[1.0.1.0.1.0.0.0.0.0.1]
[1.0.1.0.1.1.1.0.1.0.1]
[1.0.1.0.1.0.0.0.1.0.0]
[1.1.1.1.1.1.1.1.1.1.1]
Copy the codeOut of the maze
Got the map of the maze, then according to our first ideas to go through the maze. The main function logic is as follows:
def dfs(self, x, y, path, visited=[]):
# outOfIndex
if self.is_out_of_index(x, y):
return False
# visited or is wall
if [x, y] in visited or self.get_value([x, y]) == 1:
return False
visited.append([x, y])
path.append([x, y])
# end...
if x == self.width - 2 and y == self.height - 2:
return True
# recursive
for i in range(4) :if 0 < x + self.dx[i] < self.width - 1 and 0 < y + self.dy[i] < self.height - 1 and \
self.get_value([x + self.dx[i], y + self.dy[i]]) == 0:
if self.dfs(x + self.dx[i], y + self.dy[i], path, visited):
return True
elif not self.is_out_of_index(x, y) and path[- 1] != [x, y]:
path.append([x, y])
Copy the codeObviously, this is a typical recursive program. Returns when the node coordinates are out of bounds, the node is visited, or the node is a wall, because the node must not be part of the path we are looking for, or we add the node to the collection of visited nodes and paths.
Then, if the node is an exit, the program is finished and the path has been found. Otherwise, it iterates through the four direction vectors, passing the node’s neighbor path to the function DFS and continues until a way out is found or all nodes of the program are iterated.
Let’s take a look at the path result obtained by our DFS:
[[0.1], [1.1], [2.1], [3.1], [4.1], [5.1], [6.1], [7.1], [8.1], [9.1], [9.1], [8.1], [7.1], [6.1], [5.1], [5.2], [5.3], [6.3], [7.3], [8.3], [9.3], [9.4], [9.5], [9.5], [9.4], [9.3], [8.3], [7.3], [7.4], [7.5], [7.5], [7.4], [7.3], [6.3], [5.3], [4.3], [3.3], [2.3], [1.3], [1.3], [2.3], [3.3], [3.4], [3.5], [2.5], [1.5], [1.6], [1.7], [1.8], [1.9], [1.9], [1.8], [1.7], [1.6], [1.5], [2.5], [3.5], [3.6], [3.7], [3.8], [3.9], [3.9], [3.8], [3.7], [3.6], [3.5], [3.4], [3.3], [4.3], [5.3], [5.4], [5.5], [5.6], [5.7], [6.7], [7.7], [8.7], [9.7], [9.8], [9.9], [10.9]]
Copy the codevisualization
With the maze map and path, all that remains is to render the points. The visualization library we’re using today is Pyxel, which is a Python library for writing pixel-level games,
Of course, you need to install the library before using it.
Win users can run the PIP install -u pyxel command to install the software.
Mac users use the following command to install:
brew install python3 gcc sdl2 sdl2_image gifsicle
pip3 install -U pyxel
Copy the codeSo let’s do a quick Demo.
import pyxel
class App:
def __init__(self):
pyxel.init(160.120)
self.x = 0
pyxel.run(self.update, self.draw)
def update(self):
self.x = (self.x + 1) % pyxel.width
def draw(self):
pyxel.cls(0)
pyxel.rect(self.x, 0.8.8.9)
App()
Copy the codeThe execution logic of class App is to constantly call the update function and draw function, so you can update the coordinate of the object in the update function, and then draw the image to the screen in the draw function.
So we draw the maze first, then render the DFS traversal animation.
width, height = 37.21
my_maze = Maze(width, height)
my_maze.generate()
class App:
def __init__(self):
pyxel.init(width * pixel, height * pixel)
pyxel.run(self.update, self.draw)
def update(self):
if pyxel.btn(pyxel.KEY_Q):
pyxel.quit()
if pyxel.btn(pyxel.KEY_S):
self.death = False
def draw(self):
# draw maze
for x in range(height):
for y in range(width):
color = road_color if my_maze.map[x][y] is 0 else wall_color
pyxel.rect(y * pixel, x * pixel, pixel, pixel, color)
pyxel.rect(0, pixel, pixel, pixel, start_point_color)
pyxel.rect((width - 1) * pixel, (height - 2) * pixel, pixel, pixel, end_point_color)
App()
Copy the codeIt looks ok, I used 37 pixels for the width and 21 pixels for the height, so the resulting maze is not very complicated, it would be if there were a lot of pixels.
Next we need to modify the update and draw functions to render paths. To make things easier, we add a few new properties to the init function.
self.index = 0Self.route = [] # Record the path to render self.step =1# Step size, the smaller the value, the faster the speed,1: one square at a time;10Every time:1/10Self.color = start_point_color self.bfs_route = my_maze.Copy the codeWhere index and step are used to control the rendering speed. In draw function, index increments by 1 each time, and then complements step to obtain the current real subscript real_index. In short, every step that index increases, Real_index is incremented and the render path takes a step forward.
def draw(self):
# draw maze
for x in range(height):
for y in range(width):
color = road_color if my_maze.map[x][y] is 0 else wall_color
pyxel.rect(y * pixel, x * pixel, pixel, pixel, color)
pyxel.rect(0, pixel, pixel, pixel, start_point_color)
pyxel.rect((width - 1) * pixel, (height - 2) * pixel, pixel, pixel, end_point_color)
if self.index > 0:
# draw route
offset = pixel / 2
for i in range(len(self.route) - 1):
curr = self.route[i]
next = self.route[i + 1]
self.color = backtrack_color if curr in self.route[:i] and next in self.route[:i] else route_color
pyxel.line(curr[0] + offset, (curr[1] + offset), next[0] + offset, next[1] + offset, self.color)
pyxel.circ(self.route[- 1] [0] + 2, self.route[- 1] [1] + 2.1, head_color)
Copy the codedef update(self):
if pyxel.btn(pyxel.KEY_Q):
pyxel.quit()
if pyxel.btn(pyxel.KEY_S):
self.death = False
if not self.death:
self.check_death()
self.update_route()
def check_death(self):
if self.dfs_model and len(self.route) == len(self.dfs_route) - 1:
self.death = True
elif not self.dfs_model and len(self.route) == len(self.bfs_route) - 1:
self.death = True
def update_route(self):
index = int(self.index / self.step)
self.index += 1
if index == len(self.route): # move
if self.dfs_model:
self.route.append([pixel * self.dfs_route[index][0], pixel * self.dfs_route[index][1]])
else:
self.route.append([pixel * self.bfs_route[index][0], pixel * self.bfs_route[index][1]])
App()
Copy the codeSo far, we complete from the maze generation, to find the path, and then to the path visualization has been all realized. Directly call the main function App() and press the S keyboard to start the game, you can see the effect of the beginning of the text.
conclusion
Today we use the depth-first algorithm to achieve the traversal of the maze, for the novice, recursion this idea may be difficult to understand, but it is in line with the computer thinking, with the deepening of experience will be more and more profound understanding.
Secondly, we use PyxEL library to achieve path visualization, the difficulty lies in the calculation and update of coordinates, details are more and cumbersome, of course, readers can also use other libraries or directly with the web page to achieve it.
Go get the source code in the background and try your hand.
PS: Reply “Python” within the public number to enter the Python novice learning exchange group, together with the 100-day plan! \
Old rules, brothers still remember, the lower right corner of the “watching” click, if you feel the content of the article is good, remember to share moments to let more people know!
[Code access ****]
Identify the qr code at the end of the text, reply: 200615
