snek pathfinding

[kubikowski]

Affected Version: v0.4.3

Description:

The current snek auto solver makes directional decisions based solely on immediate availability. Once the snek gets to a length (I naively believe that it is currently around 20-50), the solver has a tendency of cordoning off enclosed regions, then turning in to them. This action, of course, ends the game.

Some optimizations could be made within the confines of directional immediacy, for instance the following:

• The solver could prefer moving adjacent to existing walls and snek nodes when available. The effect would be that the snek would follow its own body as much as possible, which would reduce the likelihood of creating enclosed regions at any given moment. This may increase the average game length to a certain extent, but it is not a viable late-game solution on its own.

Ultimately, any optimizations made for immediate directional preferences have a key flaw. They are making unfounded assumptions about future game states. The most viable long-term solution is to add some form of path-finding.

Suggested Changes:

Replace the existing solver with a snek path-finding service.

This service will create a tree of possible futures based on directional inputs, and weight each leaf node with some optimization and safety metrics. It will grow this tree until it has identified an optimal and safe path to the next fud node.

Upon choosing a path (or set of paths) to the fud node, it could continue path-finding for safety to a further depth, equivalent to the current length of the snek.

Once per game counter it will provide the next direction input, based on its current projection of the most optimal and safe path.

[kubikowski]

Implementation Notes:

A pathfinding algorithm could be implemented using Jordan Curves to evaluate whether a given path would create enclosed regions. And the pathfinding algorithm would thus generally prefer against paths which would create these regions.

Enclosed regions cause the majority of safety concerns for the board state. As mentioned above, the snek can become trapped in an enclosed region. If the snek length is greater than the total available space in any region, it can not escape that region. Which ultimately results in the game's ending.

Other things which should be evaluated if a path would create an enclosed region are:

1. The lifetime of the enclosed region.
   a. How many turns will it take before the region is no longer enclosed?
2. The size of the enclosed region.
   a. How large is the area of the region currently?
   b. Will it's area change over time?
3. The risk associated with the enclosed region.
   a. Is the snek head capable of & otherwise likely to return near that region while it still exists?

Jordan Curves present a solution for identifying enclosed regions. This would handle the prominent safety concerns associated with the pathfinding algorithm.