1
\$\begingroup\$

I was thinking about how to implement snake today, in particular, how to ensure the snake moves optimally from one target to the next.

This seems like a shortest path problem, but it's a bit tricky because you have to keep track of the snake's body positions for every node in the BFS traversal, which could take up a lot of memory. Is there a better approach than what I'm envisioning here?

\$\endgroup\$
2
  • \$\begingroup\$ If you use Unity game engine, they have the "AI Navigation" that automatically finds the shortest path and moves the character on this shortest path. This "AI Navigation" is a free package. Unity is also a free game engine (for companies that has a revenue less than certain amount. \$\endgroup\$ Dec 30, 2023 at 8:20
  • \$\begingroup\$ @Job_September_2020 That probably wouldn't solve the problem explained here of having an agent with a dynamic body shape that restricts its own movement in certain situation. \$\endgroup\$
    – Philipp
    Jan 2 at 10:23

2 Answers 2

5
\$\begingroup\$

The problem isn't getting to the apple, it's making sure you have an escape route after eating the apple.

[Edited for clarity, comments may not make sense]

What you're looking for is a Hamiltonian cycle (a single, continuous path that passes through every square on the board). It's the only way to guarantee you won't trap yourself, but finding an optimal one is non-trivial.

The YouTube channel AlphaPhoenix has a fantastic video detailing the various problems and optimisations.

AlphaPhoenix: How to Win Snake

At a high level, you need to ensure you always have a Hamiltonian path, so you can never get stuck.

Then you need to

  • Aim for the apple (whilst preserving a valid path)
  • Minimise the amount of time you spend filling up space "waiting"
  • Try to avoid scenarios where you have to do a whole circuit of the board to progress

To explain why you always need the cycle, here's part of two frames from the linked video

To start with, heading straight to the apple makes sense.

enter image description here

But when you actually turn in to bite it, you can trap yourself in a dead-end. enter image description here

If you're using a pure BFS approach, the obvious move is "down", directly to the closest apple.

Unfortunately, that would be a game-over situation in 2 more moves.

For a BFS-approach to work, you'd need to find paths that lead not only to the apple but also to every free square on the board (accounting for snake movement in the interim) and track/choose the one with the shortest distance to the apple.

To be explicit: Any path that can't also reach every square after collecting the apple has to be rejected before you can pick a safe path.

That means your breadth-first search has to reach maximum depth in all cases.

I believe you'll find that's computationally infeasible in anything even close to real-time.

\$\endgroup\$
8
  • \$\begingroup\$ Thanks, I will check out the video later today. I think BFS will guarantee an optimal solution right? \$\endgroup\$
    – atl123
    Dec 29, 2023 at 15:04
  • \$\begingroup\$ To start with, when the snake is very short, yes. As soon as you're able to trap yourself in your own tail, no... you'll head straight for the apple, even if it means heading into a dead-end. \$\endgroup\$
    – Basic
    Dec 29, 2023 at 15:33
  • \$\begingroup\$ Edited in some screenshots of the problem from the linked video \$\endgroup\$
    – Basic
    Dec 29, 2023 at 15:47
  • \$\begingroup\$ Hmmm, but I think you're thinking of a different BFS than I am. In my BFS, the state of a node is the location of the entire body (I think in your you're only thinking about the head). If you store the entire body, then your BFS trajectory should find the optimal path \$\endgroup\$
    – atl123
    Dec 29, 2023 at 23:01
  • 1
    \$\begingroup\$ Just watched it. This is so much harder than I thought it would be. \$\endgroup\$
    – atl123
    Dec 30, 2023 at 1:53
2
\$\begingroup\$

For every node occupied by the snake, you can compute in how many steps it will be freed. So if you keep track of how many steps you are doing in your path search, you can compare that to know if the node would be occupied when the snake reaches it.

Addendum: You might be worried about nodes occupied by future movement of the snake, but if your reach algorithm does not create paths that repeat nodes to begin with, then that is not a concern.

\$\endgroup\$
5
  • \$\begingroup\$ "if your reach algorithm does not create paths that repeat nodes to begin with" I think the question here is whether the shortest path requires a repeat nodes and I think it could, so I don't think this will work? \$\endgroup\$
    – atl123
    Dec 29, 2023 at 1:51
  • \$\begingroup\$ @atl123 I don't think it does. I'm aware that the snake might need to stall until the path is open, but if in doing so it passes a node, that node would take longer to be passable than whatever the snake was stalling for. Yet, I'm open to be corrected, do you have an example? \$\endgroup\$
    – Theraot
    Dec 29, 2023 at 1:56
  • \$\begingroup\$ hmm, actually maybe I don't understand what you mean by "repeat nodes." Do you mean the snake head won't reach a position where its body previously occupied? \$\endgroup\$
    – atl123
    Dec 29, 2023 at 2:09
  • \$\begingroup\$ @atl123 The path I'm talking is the path from the head to the target. If you represent the path as the list of nodes, it would not repeat nodes. So, yes, the head of the snake might have to cross a node that was previously occupied by its body as a step to reach the target, but not a node that was occupied by the body of the snake as it moves towards the target (i.e. only the nodes that were occupied by the snake before searching for the path are relevant). \$\endgroup\$
    – Theraot
    Dec 29, 2023 at 2:15
  • \$\begingroup\$ ah I see. I misunderstood previously, but it's not obvious why there can't be a repeat node. hmmm i think this would require some mathematical proof that the optimal path doesn't require a repeat node \$\endgroup\$
    – atl123
    Dec 29, 2023 at 2:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .