Implement main AI algorithm

[sunjay]

As described in a lot of detail in the README.md file, the main algorithm has three stages:

1. Hunt: Find a path to the next goal
2. Survive: Find the exact next step after the goal which will not kill the snake
3. Grow: Repeat step 1 and 2 for the next goal as soon as the current goal is reached

So far only Hunt has been implemented.

This issue is to track the development of the further two stages.

[sunjay]

On implementing Step 2: Survive:

The idea here is to just maximize the number of opportunities that the snake has. Since the board is often mostly empty, doing an exhausting depth first search of the board will take forever. Instead, do a smarter version of a breadth first search.

Go breadth first around the goal with the game state as it is at that point having followed the exact planned path. (Implementation Note: Will probably need to add a property to Turn)

Sort the open queue by maximum number of available adjacents found down each path. Finish when a definitive winner is found. Cache visited based on the situation (similar to what is planned for #4).

[sunjay]

The problem with doing breadth first search is that you need to visit each and every empty space every frame. This is a lot of spaces and so a very expensive check.

A better knowledge representation might be to (like we did with the snake), model empty space as a set of shapes.

Here the blue outlines represent rectangles (sometimes with zero width or height) that represent the areas that are traversable.

By optimizing for the maximum amount of traversable space, the snake can be reasonably expected to escape most situations.

One consideration here: these shapes would need to be updated every frame at both the head of the snake and the tail. Any shapes that get subdivided would eventually need to get merged again. There is a cost to calculating this well.

Experimentation is needed to see if this representation is in fact as optimal as it theoretically could be.

The shapes would need to know which other shapes are adjacent to them. That means that there should probably be a Rectangle and a ShapeNode for storing the shape and the shape's adjacents respectively.

[sunjay]

Idea for how to efficiently implement and maintain an accurate, time and space efficient traversable space representation:

Traversable space is defined as any space where the snake could potentially travel. That includes blank tiles and the goal node.

As before, the traversable space will be represented as a set of Rectangles wrapped in a ShapeNodes so that every shape knows its adjacents at all times. This part of the representation is straightforward. It begins as shown in the image above (reproduced below for your convenience).

The trouble begins when we try to update this representation every game tick. If that update is too slow, this will never work. Trying to naively split and merge each rectangle is extremely time consuming and inefficient.

This proposed method uses the assumptions of the game to prevent any of that overhead.

Since the snake is constantly moving in a single direction, we don't actually need to change all of the rectangles. We know which traversable rectangle it is going to run into next. Instead of splitting that rectangle or doing any other complex calculation, we can get by using a simpler operation: shifting (shortening). We can change the dimensions of the next traversable rectangle by shifting the side that will be hit by one space.

If the snake is travelling upwards into a rectangle, the bottom edge of that rectangle can get shifted up and the traversable rectangles below that one but beside the snake can be shifted up to take up the remaining space. Any space that ends up being leftover can be filled by a new traversable rectangle and node.

The costliest part of this will be adjusting the adjacency relations of the traversable rectangles. This will mainly occur when a new traversable rectangle is added and the adjacency relations need to be checked.

When a rectangles edges are shifted to the point where its area becomes zero, that rectangle can be completely removed and replaced by the rectangles around it; the same rectangles that would have shifted in this algorithm anyway.