Haunted Light – Redirection

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…

Some Terminology

  • Agent
    An agent is the object that you have the path-finding for. In this case it’s enemies.
  • Node
    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.


This is a screen-capture of the demo supplied with micro-pather, the “i” is where the player is. And a “D” means that there’s a door there.

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

One thought on “Haunted Light – Redirection

  1. Interesting blog post! It’s nice that you tell those who read your blog the reason as to why you are not writing about the thing you told them you would work on last week. It is also really nice that you explain some of the workings of A-star path-finding as well as some of the more unintuitive terms you are about to use as well as giving a link to the library you were referencing throughout the post.
    On the other hand the image you have tells me absolutely nothing about your code or your project. What is it even exactly? You tell me that it is a screen-capture of the demo supplied by the library but if this is the case does it really have any relevance to your code? On the other hand I can understand how hard it would be for you to provide an image that shows me some of the path-finding, I have similar problems myself, and showing pure code is pointless when you could just have copied and pasted the code into the post. It would also be nice if you had expanded upon the explanation of the constructor, I can not quite get a proper grasp of how it is supposed to look.
    Oh well, good luck with the project!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s