TD Pathfinding Demo
Hey, I haven’t posted in almost a year because I was quite busy with school and contract work. Now that school is out, I have some extra time to work on personal projects again. So without further adieu, here is something useful I whipped up. It’s a slightly optimized algorithm for generating all paths from every node to the destination node.
The algorithm itself is just a simple breadth first search. I think this algorithm is the best for this type of game because each edge has a constant weight thus eliminating the need for more complex algorithms. Furthermore, like Dijkstra’s algorithm, it generates the shortest path from all nodes to the destination (when initially called from the destination node). Optimizations include using a one dimensional array to represent the map and thus reduce access times as well as generating a border around the map. This border eliminates the need to check whether or not you are accessing an array element that is out of bounds. This check would normally be done many, many times so this simple optimization shaves off a couple milliseconds.
Using straight BFS has one drawback — it doesn’t handle diagonal paths by default. Thus I have created a simple “relax” method to determine whether a new edge can be relaxed to a diagonal. This slows things down a bit, but the performance is still quite good. In the current demo, the map is 35×35 and I get all square paths in 1-2ms and all paths with corner clipping in 2-3ms. That’s pretty darn fast!
View Pathfinding Demo.
Source: Main.as, BFSDemo.fla.
Also, here is a version which uses 2D arrays and Points which makes it slightly easier to understand but it runs about twice as slow (still pretty darn fast though 
).