Posted March 22, 2018 by eragnarok
#path finding #ai #dijkstra #nodes
First post!
Finally, after a few days of tinkering around with the algorithm, looking up pseudo-code online, fighting with C++ and getting some help from friends, I've managed to properly implement path finding.
In the images I've uploaded, the purple lines are the 'connections' to each and every single node that doesn't cross over a tower, and the green line is the path from the bottom right point, to the top left point.
Basically how it works, is whenever you place down a tower, 4 'nodes' are created just outside of each corner of the tower. Then these nodes are connected to every other node where it can (basically it connects to another node if there isn't a tower in the way). Then, the path is figured out from all of the nodes.
Specifically, the Dijkstra's path finding algorithm is used here that also implements priority queue for the nodes. There's still a lot of optimization to be done (it slows down a bit once you add too many towers), but it's an ongoing process.
I'm glad I finally got it working :) Once it's nice and snappy I can start making the actual game.
-eragnarok