This is the third day of my participation in the First Challenge 2022

This article is adapted from my wechat public number. The work I described is an interesting small project when I first learned programming. Although it has no gold content, it can be regarded as a brave attempt and interesting exploration of me as a beginner.

background

I opened my cell phone and found someone Shouting in QQ space.

From his triumphant look, he had obviously been at home for a long time and had forgotten how high it was.

pretreatment

Designing an automatic maze-finding algorithm is not difficult, but the first tricky part of the task at hand is how to turn the maze into what the computer knows it to be, a matrix of maze images.

The size of the image is 397×390. First cut off the white edges around, then binarize every pixel in the picture, and assign values according to color. Black is represented by 0, white by 1, and a 0/1 matrix is established. Considering that the boundaries of the maze are all closed, we forced all the elements on the four edges to be zeros in order to prevent some seemingly zeros from being ones due to image quality problems, which would cause some predictable effects in the process of the maze, such as the list crossing boundaries. At this point, the pre-processing of the maze is almost complete. If we hide the ones and print out all the zeros, after scaling, we get something like this:

Pathfinding algorithm

Once we have this maze matrix, we need to find a path from the top left to the bottom right.

In my memory, I once had a chance with the method of maze running. It was in an algorithm elective course. The teacher spoke affectionately about depth first search and breadth first search on the stage. So far, when I mention these two concepts, the only thing I can remember is their Abbreviations: one begins with D and the other begins with B.

But that’s okay. In those days, Chen Daozai could win 37 million yuan with 20 yuan. I solved this small maze with for loop, no problem.

Generally, the inside of a maze is not enclosed, and I can always fill it up by pouring water from any place. So if we take a little mouse and put it at the beginning, it will always find the end if it can automatically avoid obstacles, avoid the path it has taken, and retreat from a dead end.

Therefore, we define a point (x,y) at the initial position (1,1), which is the first point in the upper left corner of the boundary.

Define two lists, one for each point in its final path (that is, the path that leads to the end). The other is a footprint, which is used to store all the places it walks, including the wrong way it goes. The two lists are of the form [(1,1),(1,2),(2,2),……,(m,n)].

Then define the four actions: a step down (y=y+1), a step to the right (x=x+1), a step to the left (x=x-1) and a step up (y=y-1). Let’s make this point try four actions at a time, and let it go if it can. To determine whether you can’t go, see if the next coordinate is a wall or footprint. Place the new point in the path and footprint to become the new footprint.

Determine the priority of four actions, that is, down, right, left, up, can be down, can not be down right, can not be right is left, can not be left up. So it doesn’t wander around in an empty space for no reason, but it explores in a certain direction.

Next, give the algorithm the ability to roll back automatically. Let’s imagine a simple scenario:

This diagram is not accurate and does not satisfy the priority set for this article, but it is sufficient to illustrate the meaning

Faced with such a dead end, if the trail blocked the way out when entering, then this point could not come out again. Once we see that this point is cornered, that it can’t go anywhere, then we have to turn it back. Real lost its not far, back to a intersection is also very simple, nothing more than delete this section of the route. The method is to pop up the last element in the path list one by one. Since we have a footprint, it can’t walk all the places it has gone through twice. Therefore, as long as the wrong path is not completely gone, it can’t walk in any of the four directions because it has walked all around. So it will go all the way back to where we want it to be, which is the intersection where it went astray.

test

Now, let’s start the loop. As long as its coordinates are not equal to the coordinates of the end point, we keep letting it explore. At the end of the run, we have a circuitous curve, as shown (partial).

The program succeeded in getting a path to the destination, but the path was too verbose. In the picture above, for example, all the places that are not 1 width are caused by the point going around and around. Therefore, the path needs to be optimized.

To optimize the

Let’s consider the following simple case:

In this case, obviously 4-9 is a meaningless circle, and the correct path would be from 3 to 10.

Our optimization method is: if the NTH step is at (x,y), from the NTH +2 step (the next step of the next step), all the way to the last step, as long as one of these steps is within a distance of the next step (x,y), delete all the path points from the NTH +1 step to this step. In the example above, we start with step 1. When we checked the third step, we started from the fifth step to the tenth step, and found that 10 fell to the place that can be reached by the third step. At this time, we deleted all the 4-9 in the middle and directly connected 10 to the end of 3.

But, given that there might be a better case later, if you go from 12 to 20 and you find that 20 is right on top of 3, then we should actually just put 20 after 3 and get rid of 12, because there’s a flaw in the way we did it. So, to avoid that, we loop backwards, and for step 3, we loop backwards from step 20, all the way to step 5, to see if there’s anything that 3 can get to directly. So we can optimize this route to the maximum.

Draw the path

In the end, we got the correct and concise path, as well as the wrong path and the extra path.

According to the corresponding relationship between the matrix and the picture, we change the color of the corresponding pixels in the picture, and leave the other points unchanged.

Draw path:

Before optimization:

Total footprint:

conclusion

So far, we’ve pretty much solved the problem. The whole thing takes about three or five minutes to run on my computer like this, because it’s just a violent method for the for loop. That afternoon, I got the correct operation result 20 minutes before the evening class, and I was generally satisfied. However, the price is to read the one-hour audio PPT that the teacher gave us for preview three times faster in 20 minutes…

Project code: Yuezih-Playground/Maze (github.com) (It was a long time ago, the code is very bad, please forgive me)