One of the earliest, classic, video games is the game of Snake.
It dates back to the 1970's. In the standard variant of the game, the player controls a long snake-like create which is confined in a box.
The snake never stops moving, and the player controls the head of the snake using the four cardinal directions: Up, Down, Left and Right.
Each segement of the body of the snake follows the one infront. If the head touches either the walls, or any other part of the snake's body the game is over.
A single, randomly placed, piece of food is also on the screen. The snake starts off short, and the aim is to drive the snake over the food item.
After the snake eats the food, he grows in length and a new piece of food is randomly placed on the board.
The game starts off relatively easy and forgiving, but as the game progresses, it gets harder to get to the food and not eat part of your own tail.
I've seen some version of snake running on just about every computer I've ever encountered. The above screen is a picture taken on an early Nokia Phone. It's a fun programming exercise to write a simple version of the game. It can be used as a great example to teach young students the concept of code optimisation – when rendering the snake, it's not necessary to redraw all the snakes each time; you simple have to draw the new position of the head and take the last segment of the tail away!
So why all this reminiscing about snake?
The other day, a few of my facebook friends forwarded me this little animiated GIF, showing an exceptional player beating the game.
I hope you agree, it's pretty awesome to watch!
At various times, it looks like he's going to get trapped, but just at the last second the tail passes by and creates space for the head to move into!
If you watch the video all the way to the end, before it loops back, you'll see a short message in Russian.
The translation is:
“And now we'll show you a cartoon.Connecting to server.No connection. Thank you, everyone can go.”
(I'd love to give credit to the author of this GIF. Please contact me if you know the true creator and I'll be sure to add his/her name here).
If you wanted to write a computer program to solve Snake, how would you go about doing it?
When the puzzle is very small, it's a pretty trivial exercise to aim directly for the food, using simple avoidance techniques if it looks like you are going to hit something.
However, as the snake gets longer, things get more complex. Not only because the longer snake gets in the way, but also because, unless you plan ahead, you can paint yourself into a proverbial corner. It's pretty easy to trap yourself into a location when you don't have sufficient unused space to get yourself out.
Compounding this is the lack of knowledge of where the next piece of food will land. If it's the wrong side of your body you might not be able to get to it.
We need a better plan …
Instead of trying to aim for the food, we can simply ignore it!
Take a look at the grid to the left. Here I have traced out a path around a 6 x 6 grid in such a way that not only is each square only visited once, but the path never crosses itself.
This path traces out a tour that visits the entire board.
If we set our snake running around this race track, by definition, it can never eat part of itself (the path never crosses), and eventually it will eat the next piece of food (it passes through every square on the grid).
There are many ways to generate such a path (providing the board has an even number of squares).
It's not a terribly efficient algorithm, infact, it's pretty dumb. It has no intelligence at all and blindly races around the preset path on autopilot.
It is, however, guaranteed to win the game irrespective of how the random food is generated.
Here is another animated GIF showing code I wrote to solve a 10 x 10 version using this algorithm.
To make it a little clearer what is going on, the head of the snake is drawn in red, and the food is shown in yellow.
It's a little infuriating to watch in some places because the snake glides right past the food on a couple of occasions, and could have easily taken a short detour to snag the food without causing a problem, but as we know, it's just not that smart …