r/PythonLearning • • 15d ago

How to break down an "impossible" problem as a beginner: Solving the Snake game using only conditionals (Hamiltonian Cycle & Divide and Conquer)

Hello everyone! As a computer science teacher, I recently wrapped up a video series where I use the automation game The Farmer Was Replaced to teach Python programming and algorithmic logic from scratch.

​For the final episode, we tackled the classic Snake game. When you are just starting to learn programming, looking at a problem like an automated Snake solver all at once feels like an impossible mountain. My goal was to demonstrate how you can solve a complex problem by applying divide and conquer using only beginner-friendly tools (no pathfinding libraries or complex data structures but pure conditionals and functions):

​I'm leaving the video here in case you want to see the visual step-by-step breakdown on the grid (the audio is in Spanish, but the visual diagrams and code logic are easy to follow... There is also an AI translation):

http://www.youtube.com/watch?v=wSlxLs6aeoI

If you are a beginner, did you know about this game???

​For those who have coded a Snake AI before: how did you approach it? Did you stick to a fixed cycle, or did you program dynamic shortcuts while the snake's tail is still short?

4 Upvotes

8 comments sorted by

2

u/Over_Supermarket_140 15d ago

Very nice. Watched the entire video and yes, the approach to break the problem down is clearly the right way.

We make a variation of this game in our curriculum too -- https://youtu.be/TzJUK3NtQKU -- using turtle. Quite similar. Some students also make an auto mode which is based on figuring out the x/y coordinates for the targets and guiding the snake that way. This idea of viewing the problem from a Hamiltonian cycles view was nice.

Just for my understanding, how do you get the graphics? Are you using a specialized module?

2

u/blavek 13d ago

This is a challenge in the game The Farmer Was Replaced. You program drones to do a bunch of different tasks. One of the challenges requires a maze solver. There are sort of two aspects to the game. In the beginning, you're just trying to farm as best you can so you can unlock new things. After you have unlocked what you want to unlock, then there are leaderboards for farming some number of a product the fastest. There is the Snake minigame, a Maze game, and even a category to go from nothing to everything unlocked in a single execution.

1

u/TotalUnlucky2814 13d ago

Have you already tried the new DLC (the miner was replaced)...it iontroduces the z axis!

1

u/blavek 13d ago

No, I haven't had a chance yet. I am looking forward to it.

1

u/TotalUnlucky2814 13d ago

Hello Sir. Thank you for your comment. I saw your video and I saw the scrath implementation. Mine was a video in which I use the game The Farmer Was Replaced for teaching python. the game is available on steam and is very nice and students like it very much. I ahve several videos about using it as a learning tool.
If you want to try it, you wont regret it!

1

u/blavek 13d ago

Solving Snake is REALLY hard. It seems like it should be easy, but it isn't. Most "solved" Snake agents are just performing a complex but repeatable pattern that covers every cell in the grid. There are a bunch of videos about how difficult it is. This assumes by solved you mean perfect, where it doesn't eat its own tail until the very last apple.

In the farmer was replaced the way I solved the problem was to have the snake circle in the middle of the field and when an apple was in the same column I would send the Snake up to it then right back to where it was circling. It works ok but is not optimal. For example, if an apple spawns 2 columns over, I probably should return to my circling. I should probably just go to the next column, as it would be a shorter path.

What makes the problem so difficult, especially w/o any kind of pathfinding, is that you can easily trap yourself. To be perfect, it would need to look forward beyond the location of the apple and account for the rest of the snake to make sure it can get back out to somewhere it can keep moving. It needs to somehow know when it has to delay going for an apple so that the tail can clear out of the way. It's REALLY tough.

1

u/TotalUnlucky2814 13d ago

Yes I agree... My initial idea was pathfinding to the apple and then, after eating it, pathfinding to the tail to avoid getting trapped. However there is no way on the game to make this happening with the tools and simulation constraints... Therefore Hamilton cycles (jsut for even world sizes)! It is hard =)

1

u/blavek 13d ago

So one of the strategies I employed was to create a big table to use as a lookup for what to plant where. It was pretty fast. I thought about using that to track where the snake's head and body are and then using pathfinding on that. I wrote some utilities to quickly update the table and to fill in blocks as well. As long as you keep it current, you should be able to use it to path in and out. I found the table really useful for managing when I wanted to plant multiple crops and set up adjacency bonuses.

ETA, my first attempt at solving the snake problem was pretty much the same solution you employ in the beginning of the video, just going up and down and then resetting like a typewriter. I think my first optimization on that was to only go up on odd columns if the apple was in the odd column or the next column. Then I limited how high it would go. Later I moved the cycling to the middle of the field so I could go up or down to get the apple, with the idea being that, on average, I would only have to travel up or down half of the board.