This week I spent a few days trying to figure out walk boxes and path finding algorithms, which led to a lot of frustration and wishing that I paid more attention in my freshman CS 367 class on data structures!

After doing a lot of research and finding very little code online to follow, I was finally able to stitch together a prototype that implements walk boxes and path finding!

Walk boxes are polygons that limit the areas that a player can walk in the world.  Path finding is finding the shortest path from a point in Polygon A to a point in polygon Z using those walk boxes to go around obstacles. If you have to walk through several polygons to get to a target, it will return a list of the polygons that has the shortest path.

Here is a really crude example.  Please excuse my horrible Photoshopping skills, but in this image the green arrow is what the algorithm, A* (pronounced A star), would calculate the path of the player should be if they were on A and wanted to get to H. It would then tell me the path should be through polygons A, B, C, D, E, F, G, H.

I found many good articles about the theory behind it, but I couldn’t find much code.  What I could find, wasn’t written in C++. The other issue was that a lot of the articles were written for a simplified version of A* using a grid system. This would be great if I was making a tile based game like Lumps of Clay or Super Mario Brothers, but it doesn’t really help much when it comes to polygons / nodes.

In the end I found a wonderful article written by Julian Ceipek. http://jceipek.com/Olin-Coding-Tutorials/pathing.html It describes path finding much better than I ever could.  It also describes in detail the  algorithm to find the shortest path between two nodes.  Perfect! That’s precisely what I wanted.  But the little code he had was written in another language.

It took a while but I was able to make my own node / graph class to store the node and edge data.  Then I was able to port his code over to C++ to analyze the graph data to find the shortest path between nodes. It seems to be working after some tweaks.

Now I need to find some time to implement the algorithm, “Simple Stupid Funnel”.  It is a smoothing algorithm which makes the path taken more direct instead of having the player walk to the center of each polygon before moving on to the next.

Without further ado, a short demo!