Implement more robust pathfinding and obstacle avoidance algorithm

[minkezhang]

Instead of the default A* algorithm, we should investigate ways to make path planning more robust.

We should follow the general API

func FindPath(layer Layer, src Vector2i, dest Vector2i) Array

Where each element in the array represents a discrete point in the tilemap.

In the case src or dest is not reachable from layer, the closest point to these tiles will be used. In the case that the destination tile is unreachable due to being completely surrounded by impassable tiles, the returned path will end at a sensible point close to the destination.

Possible candidates

• Potential Fields¹: Appears to be the easiest and most flexible of solutions
• Flow Fields
• Collaborative Diffusion²³⁴
• Continuum Crowds⁵

N.B.: Generating these fields may take a long time -- it is okay to recalculate in a separate thread while allowing for the field in the meantime to go slightly stale. Generating a new field (set) every 250ms is probably enough.

Misc Notes

• Primer from Stack Exchange
• follower avoidance strategy⁶⁷

Footnotes

1. https://web.archive.org/web/20190725152740/http://aigamedev.com/open/tutorials/potential-fields/ ↩

2. https://www.reddit.com/r/gamedev/comments/z98wvh/ ↩

3. https://ramblingsofagamedevstudent.blogspot.com/2013/11/for-my-honours-project-this-year-at.html ↩

4. https://github.com/glouw/pather ↩

5. https://howtorts.github.io/2014/01/09/continuum-crowds.html ↩

6. https://forum.godotengine.org/t/how-to-make-enemy-ais-follow-path-while-avoiding-their-fellows/25352 ↩

7. https://godotforums.org/d/34106-bunch-of-vehicle-stucks-themselves-after-astar-calculation ↩