Implement pathfinding for enemies

[pserwylo]

I'm familiar with the A* algorithm from reading on GameDev over a decade ago - seems like it is still relevant. Misc reading directed me to this amazing set of resources which really helps explain it in a way that I kind of get:

http://www.redblobgames.com/pathfinding/a-star/introduction.html

The thing about this vs all other explanations is that it goes into great detail about how to break down a map into a graph so that it can have the A* algorithm applied to it:

http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.html

For reference, there is also a bunch of other great notes here: http://www-cs-students.stanford.edu/~amitp/gameprog.html

[pserwylo]

Making progress in the pathfinding branch. Not performant, but accurate:

The screenshot above is tile-based. You can either travel on the tile or not, depending on if there is any collision objects in it. Crude, but no extra work in adding pathfinding navigation meshes to the tiled map. Not performant yet, because of the large number of nodes in the graph that need to be searched, but can be improved in a few ways.

Worth noting, the path traced out in the white line here is not for the tank to go somewhere (you are responsible for driving the tank with the controller / keyboard still). Rather, it is to simulate pathfinding from enemies to the tank.

Other approaches tried include manually specifying a navigation mesh in the tiled map editor, but this has a bit of a way to go before it works the way I'd like.

[pserwylo]

My hunch on how to improve performance over long distances is backed up by this well written article outlining clearly several ways to improve pathfinding performance in a CPU-intensive game loop. This branch currently is way too naive just for testing purposes, in that it does pathfinding every single frame. In general, you should only re-calculate pathfinding when required.

[pserwylo]

Performance improvements done. Last step is to hook up enemies to the pathfinding, rather than the current "pathfind from the tank to the mouse as an example" approach used for debugging.

Note the debug rendering now also includes the edges of the pathfinding graph which were examined as part of the search. You can see how it correctly hedges its bets by going around the building on both sides, because it doesn't know which will end up giving a path to the destination. Once it successfully gets around, it spends less time on the left side, and makes a direct route to the mouse with minimal deviation.

[pserwylo]

Still has a lot of improvement opportunities, but fixed in #11.