preface
These two days on the Internet to see a picture of the posture, the picture shows the snake game, it is estimated that most people have played. But if it’s just snake, there’s nothing uplifting about it. The problem is that the snake in this picture is really greedy for XD, as it eats all the food in the rectangle and then fills it up beautifully, which is really pleasing to watch. As a CSer, the first thing that comes to mind is that this thing is written by a program (because ordinary people can’t do it). Decisiveness is to let the program do it.) The second thought is, how should the program be implemented, what algorithm should it use? Start thinking about it, start doing it. Because Talk is cheap, show me the code. (Learned from Uncle Mouse)
Before we begin, let’s take another look at the snake that raises the posture :(right click to save and view the motion picture below if it doesn’t work well)
Language selection
Life is short, use python! So, I didn’t think twice about it and went straight to Python.
The first version
Let your program run first
First of all, the first thing we need to do is not analyze the problem yet. At least write a working Snake game first, and then worry about the AI. This should be easy, c++ is only about a hundred lines of code (if I remember correctly). Python is much simpler, with 5 or 60 lines of code removed from comments and blank lines. And, crucially, this stuff is pretty much overwritten on the Internet, so you don’t have to reinvent the wheel, just get a copy and adapt it to your will.
Simple version
I don’t think it’s a good idea to just write the perfect version. Because versions of Perfect tend to take a lot of things into account, it’s often buggy to write this right up front. So, my goal at the beginning was just to get the program to control the snake movement, to get it to eat food, and that was it. Now let’s state the initial question:
In a rectangle, each time there is a food, the snake has to find a path (not necessarily optimal) without bumping into itself, and then run along that path to enjoy its meal
Putting aside the fact that snakes are getting longer, the problem is basically, given a starting point (the snake’s head) and an ending point (the food), avoiding obstacles (the snake’s body), finding a viable path from the beginning to the end point. We can use the following methods:
- BFS
- DFS
- A*
As long as there is a choice, choose the simplest solution first, our goal now is to make the program run first, optimization later. So, let’s start with BFS. We initially put the snake head position in the queue, then as long as the queue is not empty, we put the head position out of the queue, then put its four points in the four fields into the queue, and iterate until we reach the food position. During this process, note the following: 1. The accessed points are no longer accessed. 2. Save the parent of each point (that is, where each position went to it, so that we can find the feasible path). 3. The location of the snake body and the four walls are inaccessible.
Once you’ve found food through BFS, you just have to move the snake along a viable path. Once this simple version is written, Snake can run happily for a while. Look at the picture :(the feeling of not smooth is from the screen recording software @_ @)
To keep it simple, I used the Curses module to draw directly on the terminal. As you can see from the motion picture above, simply using BFS every time, eventually one day, the greedy snake will get into trouble because of this reckless short-sighted behavior. And, even then, it will BFS only one strategy, leading it to think that because it can’t see what it wants to do (food), it will end up at a point in its life where it can’t move forward. (I’m so philosophical XD)
BFS+Wander
After running the simple version of the previous section, we realized that we can’t teach the snake just one strategy. He’s such a stupid snake. If you don’t teach him a bit, he’ll be dead in a minute. So, I wrote a Wander function, so as the name suggests, when the snake is in trouble, don’t let it BFS, but let it Wander around, think about life and so on. This is like trying to work when you are confused. Not being productive may prevent you from getting out of trouble. Instead, take a break from what you’re doing, stop, and go for a trip. When you come back, you may suddenly see the land level and the house looks like it.
Wander functions can be written either way, but there are always pros and cons. I wrote two versions, one of which was to take random steps in random directions, as far as possible. In other words, the direction of each movement of the snake is random, and so is the total number of steps it takes. After Wander, go to BFS to see if you can get some food. If you can, everyone will be happy. If not, you haven’t had enough time to think about your life. Wander again. The process repeats itself. However, just like “random process”, you “Wander randomly and hang randomly”. A snake who can Wander does take many more steps. But one day, it will put itself on a random road to death. You can Wander off into a dead end. There’s no rollback mechanism. So, for the second version of Wander functions, I let the snake bite. After BFS has no solution, the snake is told a step number (randomly generated step) and let it move step in an S-shape in a blank area. This time it’s not random, it’s organized and disciplined. Look at the picture first and then say what’s wrong with it:
That’s right, he finally died. The S-shape movement could not prevent the death of the snake. The snake can survive a little longer with s-shaped movement, but because of its strategy:
No ESC key pressed: If there is a path between the snake and the food else: Wander for a period of time
The problem is that the snake finds a path between itself and the food and runs off to eat it without saying a word. It doesn’t take into account that if you eat the food, the situation (snake body layout) will kill you. (such as entering a small enclosed space surrounded by your own snake)
So, in order for the snake to live longer, it has to be more far-sighted.
Far-sighted version
We now have a lower-end version and a slightly deeper understanding of the problem. Now it is time for some more rigorous and rigorous analysis. First, let’s list some questions: (Just write down what comes to mind, like brainstorming)
- There’s a path between the snake and the food. It’s not advisable to just eat it. So what to do?
- If the layout is safe for the snake to eat, does it just eat? (Is that optimal?)
- How do you define if a layout is secure?
- What if there is no path between the snake and the food?
- Is the shortest path optimal? (Apparently not.)
- So, if the layout is safe, is the shortest path optimal?
- Other than the shortest path, what else can we do? S form? The longest?
- What to do about growing snakes?
- Food is random. Is it possible to have an unsolvable layout?
- Can Brute Force get an optimal sequence? (Let the snake eat as much food as possible.)
There are a lot of questions when you think about it. Now let’s think process-oriented, with the above question in mind, and clarify our thinking. At first, the snake is very short (initial length 1), it sees a food, and uses BFS to get the shortest path length to the food at each position in the rectangle. Without the snake, that’s the distance to Manhattan. Then, I will judge whether it is safe to go to the snake. So I need a virtual snake, and it’s responsible for finding the way every time. Only let real snakes run if it’s safe. Of course, the virtual snake will not be drawn, it will only be used to simulate pathfinding. So, how do you define a layout as safe? If you look closely at the snake’s path in the moving picture at the beginning of this article, you will see that even though the snake is very long at the end, it still makes its way out without any problems. And follow the tail of the snake! Well, it’s not that hard to explain. Snakes consume their bodies as they move, and new space is constantly opening up behind their tails. It doesn’t matter when the snake is short, but when the snake is long, you find that the only way to survive is to basically run after it. While running after the snake’s tail, think about whether it’s safe to eat the food. (The figure below is a layout obtained after a BFS, 0 represents food, number represents the distance to the food, + represents the head of the snake, * represents the body of the snake, – represents the tail of the snake, # represents the space, and # represents the wall.)
0, 1, 2, 3, 4
1, 2, 3, times 5
2, 3, 4, minus 6
3 plus * * 7
4, 5, 6, 7, 8
After the above analysis, we can define whether the layout is safe as whether the snake can move with its tail, that is, whether there is a path between its head and tail after the snake finishes eating food. If there is a path, I think it is safe.
OK, go ahead. The real snake sent out the virtual snake to explore the way and found that the layout after eating the food was safe. So the real snake went straight for the food. Wait, is that a good strategy? Not necessarily. Because every time the snake moves, its layout changes. A change in layout means there might be a better solution. For example, because of the consumption of the snake’s tail, the food that would have taken a detour to eat suddenly appears in front of the snake. So, after the real snake has taken a step, it’s better to redo the BFS. Then make the same safety judgment as above, and then go.
Now let’s think about, what if there’s no path between the snake and the food? In fact, it has been mentioned above, follow the tail of the snake. As long as there is no path between the snake and the food, the snake follows its tail. Also, since the layout changes with each step, redo the BFS at each step to get the latest layout.
Okay, here we go again. What if there’s no path between the snake and the food and there’s no path between the snake and the tail? I don’t know what to do about it. Just take a viable path. Again, take one step at a time, update the layout, and then determine if there’s a safe path between the snake and the food. If not, is there a path between the snake’s head and tail? Not yet. Pick another one that works.
Several of the questions listed above involve snake walking strategies, and generally speaking, we would let the snake take the shortest path every time. This is for the snake to eat food, but not for the snake chasing its own tail. We want the head of the snake to chase the tail as slowly as possible. In this way, more space can be vacated between the head and tail of the snake, and more space can be developed. Therefore, there are two main walking strategies of snakes:
1. Take the shortest route if the target is food. 2. Take the longest route if the target is snake tail
What about case number three? With food and snake tail have no path to exist, this time just pick a feasible step to go, the shortest and longest relationship is not much. As for the artificial s-shape of the snake, I don’t think it’s a good strategy, as it was analyzed in the original version. (Unless, of course, you want to use the most watertight version, which is to leave the food out of the way and let the snake walk along, leaving a passage by the wall. This way, the snake can always perfectly eat all its food and fill up the space, but it’s boring. Doesn’t mean anything)
Here’s another question: Since food is random, is it possible to have no solution? The answer is: yes. I ran the program and then printed each layout to log and found something like this:
* * * * *
* * minus 0 *
* * # + *
* * * * *
* * * * *
The + sign is the head of the snake, the – sign is the tail of the snake, the * sign is the body of the snake, the 0 sign is the food, the # sign represents the space, and the # sign outside represents the wall. In this layout, the food is already in front of the snake head, but can it eat it? Can’t! Because when it finishes eating, it increases the length by 1, and the snake head fills in the 0’s and the layout becomes:
* * * * *
* * – + *
* * # * *
* * * * *
* * * * *
At this point, since the length of the snake increases by 1, the tail of the snake does not move, and the head of the snake is wrapped around itself and dies. However, we still have a blank grid # left unfilled. Following the strategy we taught the snake, faced with this situation, the snake head will just keep running after the snake’s tail. Whenever it has a path with the food, it will let the virtual snake run through and discover that the new layout is not safe, so it will not eat the food, but will continue to run after the snake’s tail. And it just kept running and running. Loop endlessly until you press ESC.
Since the food is random, it is possible to have this unsolvable layout. Of course, you can also get a happy ending, with snake filling the entire rectangle.
The last question above is whether the violence method can get the optimal sequence. From the above analysis, it can be obtained, but it is not guaranteed.
Finally, take a look at how the forward-looking snake runs:
The rectangle is 1020 in size, minus the border, which is 818. Linux under the record screen and then converted to GIF format pictures, optimization of the first 40 M, really can not be compared with Windows. When optimizing with the following command, there is a feeling that the system is optimizing with life:
After AE, use the following image sequences to create a dynamic image:
Last but not least
If you are interested in the source code, please poke the following link:
https://github.com/Hawstein/snake-ai
In addition, the snake program uses the Curses module, which is installed by default on unix-like systems. If you use Windows, you will need to install this module. Need curses please poke me http://www.lfd.uci.edu/~gohlke/pythonlibs/#curses
The above code can still be improved (currently with less than 300 lines of comments, maybe even less), or you can use PyGame or PyGlet libraries to make the interface more beautiful. Enjoy!
The original address: http://www.hawstein.com/posts/snake-ai.html, reprint please indicate the original address
Welcome to study and develop with me happily. The terminal RESEARCH and development Department is a technology-oriented learning and communication technology number, talking about technology, products, but also our life. Be the most thoughtful, tasteful Internet developer in the eastern hemisphere
