search

sunjay / snake

Snake Game AI
http://sunjay.github.io/snake/
MIT License
1 stars 0 forks source link

AI Process Has Weird Lag #2

Open sunjay opened 7 years ago

sunjay commented 7 years ago

Intermittently, the AI will start to lag and just completely die. This is visible on the debug path being rendered because the path's yellow line begins to move unexpectedly even after the snake has died.

Typically this happens after the snake has reached a length of 100.

Demonstration

sunjay commented 7 years ago

Easily reproducible by setting pendingGrowth to 100 in snake.js. This results in the snake growing to over 100 size on start.

sunjay commented 7 years ago

Noticing this happens when astar takes way too long. Seeing times of over 300 ms sometimes. That's usually when this happens.

Log screenshot: screenshot from 2016-07-11 01 49 07

The extra time causes the messages sent to the AI process to build up. This then completely throws off the algorithm.

Here's an article about message lag, though really this is a problem with the algorithm taking too long.

sunjay commented 7 years ago

Another interesting link: MessageChannel API

sunjay commented 7 years ago

Idea to solve this: debounce processing of updates until a later time. Then process all updates at once, running the actual AI actions after the fact.

This may result in the AI missing a critical turn. If more than one message is being processed after the debounce, scrap the path and generate a new one from the current state. This may result in cascading events like this one, but it's worth a try. I think it might cascade because this problem is caused by a path find taking too long. Refinding the path will likely take even longer. It might be faster to just find a way back on to the previous path if possible, though this is getting complex.

Do not debounce for longer than 5 ms. 0 ms would be preferred if that is even possible.

sunjay commented 7 years ago

If more than one message is being processed after the debounce, scrap the path and generate a new one from the current state. This may result in cascading events like this one, but it's worth a try.

To solve this, when applying each update, check if the head is the first turn in the already planned path. If it is, and if this is not the very last update, scrap the path and recalculate since we clearly missed a turn.

With this, we won't always have to scrap the path in case of lag.

sunjay commented 7 years ago

Proposed message queue implementation:

https://github.com/sunjay/snake/commit/8e4e041675aa30dd1d6704693f5501e70db80468

As feared, the message queue simply causes the lag problem to cascade. This is because the first turn in the path is always the next tile and if messages build up, this always causes a complete recalculation of the path. Since the calculation was expensive to begin with, throwing away all that effort and trying again is resulting in the same message build up and further failures.

sunjay commented 7 years ago

If we can figure out a good enough representation of traversable space (as defined in https://github.com/sunjay/snake/issues/5#issuecomment-234030009). It may be possible to solve the lag issue through an entirely new path finding method.

Newly Proposed Method: Pathfinding Through Traversable Space

Rather than traversing each tile, if we can represent the traversable space efficiently, we can make it possible to do the pathfinding in two small and fast stages.

  1. to get to a general path and then
  2. find a more specialized path through that

The idea here is to first find a path to the goal through the large rectangles of traversable space. Then, once you know exactly which sets of tiles you need to traverse, you can go through each rectangle of traversable space and figure out what the path should be.

traversable_space_path

traversable_space_specific_path

The interesting part about this is that you can now pathfind incrementally after finding the first general path through the traversable space. You don't need to find each specific path immediately. You have the option to take it one traversable space rectangle at a time (even lazily!).

traversable_space_specific_path_segments

This diagram shows how you could sequence each specific pathfinding step. You start by finding the path through 1. Then in the time it takes to traverse that, you find the path through 2. Then 3, then 4 to the goal. The exact traversable space rectangles would look somewhat different as the snake moved about, but the idea is the same. Running through the algorithm outlined above would produce the correct traversable space path for the snake to plan through.

sunjay commented 7 years ago

The revelation of this method is that you can break the problem down into these smaller problems of finding paths through traversable space. When you're in a traversable space segment, you know where you're coming from and where you're going. For number 2, you know where you'll enter from number 1 and you know that you're aiming for somewhere in number 3. This dramatically reduces the amount of pathfinding you have to do. It reduces the problem into a set of subgoals that can be solved much easier than finding the full path from the start in 1 and the goal in 4.

traversable_space_specific_path_segments_targets

sunjay commented 7 years ago

This new algorithm also informs step 2 of the main algorithm described in https://github.com/sunjay/snake/issues/5.

With the empty space representation, there should be a way to optimize for most open space when leaving the current goal.

sunjay commented 7 years ago

In order to save on memory and access costs, eventually it may be necessary to use JavaScript typed arrays. I don't actually think JavaScript can handle all of this in the largely immutable infrastructure I've setup, but I'm certainly going to try my best.