In the previous post I wrote that I was going to go through how our level generation worked, but due to missed deadlines we’ve been forced to push the implementation of that feature to later when we have a working path-finding since we prioritize having a challenging game rather than a fancy level-generation. Because of that unfortunate turn of events I’ll now write about how our A-star implementation currently works instead.
Before I even began working, I did some research on what the easiest way of implementing A-star were. After a while I finally settled on using the “Micro-Pather” libriary which is a lightweight and easy-to-use library containing only two single files;”micropather.h” and “micropather.cpp“.
Before I begin here’s…
An agent is the object that you have the path-finding for. In this case it’s enemies.
Nodes are each coordinate which an agent are allowed to move to. E.g. this can be a grid of squares, hexagons or a network of points.
Micro-pather consists of two main parts. The first one is the “graph” which calculates all the costs of moving from one node to another. The second one is the “solver” which takes a start-position and a destination and then returns a path in the form of points in a vector array.
In our game we have an object which knows where all the objects are (in Haunted Light I currently use the LevelSystem class which I covered last week). For the sake of explanation, I call that object the “map-object“. The map-object inherits all of the pure virtual functions from the class:”Graph“. That way I can implement my own algorithm (or use the one supplied in the demo of micro-pather) which take into account what type of terrain it is or whether there’s a closed door on the current node. By doing so I make sure that the agent adapts and takes the most effective route possible.
When I create the map-object I also create the solver which I mentioned earlier. The solver takes three arguments in its constructor, the first one is a pointer to a graph object. By having the map-object inherit from the graph, it’s now possible to send a “self-pointer” into the constructor of the solver. And by doing that you practically tie all the systems together. The second argument is how much cache memory the pathfinder is allowed to use. A higher value means that the calculations will be faster but will take up a larger space on the RAM memory, while a smaller value makes the calculations take longer but with a smaller RAM usage. The final argument defines how many directions you can take from each node.
That’s the basic gist of it and now all that remains is giving all the paths to each object to follow. Next week I’ll cover another part of our development!
~Lead Programmer, Per “Gimmic” Johansson