For a game like Where Shadows Slumber, the most basic interaction you have is to tell the character to move to a spot. If he’s a good boy, he’ll do what you say, deftly dodging pillars and chasms as he winds his way toward the destination. You don’t even have to tell him how to get there – he’ll figure it out!

This leads us to the topic of pathfinding, the process by which the character figures out where to move. Pathfinding is very common in game development, and can be summed up with a single question:

How do you get from point A to point B? Rather, what’s the best way to get from point A to point B?

This is the question that encapsulates the idea of pathfinding. In the real world, I tend to take whatever public transit is available, and walk the rest of the way. Some people open up their GPS, hop in their car, and follow the directions. You could even simply determine the direction you’re going, grab a compass, and just start walking.

Each of these is an example of a pathfinding algorithm. The algorithm is a set of instructions which determines exactly how to get somewhere. Pathfinding algorithms in games are a little different from the ones listed above, but the concept remains the same. Given a starting point, a destination, and some information about the surroundings, how should you get there?

 

Finding a Path in the Darkness

Pathfinding is a pretty common concept in computer science, even outside of gaming. It has received a lot of attention and study in the computer science world, so I won’t get into the intricate details and just stick to the broader points. If you want more details, there are plenty of pathfinding intros and tutorials out there.

Some number of years ago, a cool bro by the name of Dijkstra came up with a good pathfinding algorithm, appropriately dubbed Dijkstra’s Algorithm. Years later, a variant known as A* Pathfinding is still a favorite among game developers, and is the algorithm I decided to use for Where Shadows Slumber.

The basic idea behind A* is to divide your map into a set of areas, which I have taken to calling ‘nodes’. For each of these nodes, you determine which other nodes it’s connected to, and how hard it is to move between the nodes.

What do I mean by that? Imagine you’re standing in front of a fence, and you want to cross to the other side. In this case, the best path is probably just to climb over it. However, if there’s an open gate in the fence a few feet away, that might be the best route to take. Even though you’re travelling more distance, that path is faster, or at least easier. In the same way, each node has a ‘pathfinding cost’, indicating the difficulty to cross it. Our ground node might have a cost of 1, whereas the fence node could have a much higher cost of 10 or so, since it’s so much more difficult to cross.

Once you know what your nodes are, and how they’re connected, the A* algorithm will efficiently loop through and figure out which nodes you should travel over. After that, all you have to do is move the character from one node to the next, and you have pathfinding!

 

Nodes

I kind of glossed over the whole idea of nodes earlier. A node is a representation of a point in which the character can stand. He cannot stand anywhere where there isn’t a node, or in between two nodes, and he can only travel from node to node. Every path in the game is made up of nodes.

A node consists of three parts:

• The node position, shown as a dark sphere in the center of the node, indicates the position the character will be in when he is on this node. This position is usually the same as the node’s position, but there are some cases where it needs to be different.
• The click detector, shown as a blue cube, is simply a big box with a collider on it. That way, we can detect when you click on the node, and start the pathfinding. Different types of nodes can have different colliders – a normal node has a cube collider, but a ramp node might have a triangular prism collider or something.
• The boundaries, shown as small pink spheres, determine which other nodes this node is connected to. Since nodes are appearing and disappearing throughout the game, we need to be able to know which nodes should be connected. If two boundaries are in the same location, that means their nodes are connected. In the image, each node along the path is connected to the next, because their boundaries are in the same spots.

With these three parts, the nodes are able to fit together and provide all of the information necessary to, at any point, determine what path the character should take.

 

Follow the Path

Once we determine the path, then what? How do we follow it? A path is a series of steps: move from Node A to Node B, then move from Node B to Node C, and so on. To this end, the nodes each have another property: nextNodeInPath. Each node stores a reference to the next node in the path. In every frame, the character checks his current node. If it has a next node, the next node is still enabled, and the two nodes are still connected, then he starts moving there!

In this way, the character will make his way along the path determined by the algorithm. If he comes to a node which he can no longer get to, then he’ll stop. This allows us to create a path, and we don’t have to think about it too much after that. The player will automatically follow the path, and, if the path somehow becomes broken, he’ll stop at the end of it.

 

Unity’s Pathfinding

If you’re familiar with Unity, you may have heard that, being a nice little game engine, Unity provides its own pathfinding. In fact, the earliest versions of Where Shadows Slumber used Unity’s pathfinding.

However, Unity’s pathfinding didn’t end up being what we wanted for this game. In the same way that Unity’s Standard Shader was too detailed for out game, we found that Unity’s pathfinding gave the player too many options. Where Shadows Slumber was designed to be grid-based, whereas Unity’s pathfinding allows the player to roam around within different areas.

While this isn’t too bad – it wouldn’t be hard to use Unity’s pathfinding, but restrict it to a grid space – there is a reason we decided against using it. One of my professors always told me that ‘you can never know how efficient – or inefficient – a piece of code is, unless you wrote it yourself’. This is a piece of advice I have carried with me ever since, as I find it to be fairly accurate. Therefore, unless Unity’s pathfinding provides exactly what I want, it makes more sense to implement my own pathfinding system. That way, I can know exactly what’s good or bad about my system, what sacrifices I can make, and how best to use it.

Don’t get me wrong – Unity’s pathfinding is pretty cool, and if it makes sense for your game, you should use it. It’s just not the exact solution we needed, so we decided to implement our own.

So, that’s how pathfinding is implemented in Where Shadows Slumber! As I mentioned, I skipped over a lot of the finer details, but I hope this was a good, quick intro to the way that we implemented pathfinding and some of the choices we made.

If you have any questions or comments about pathfinding (or anything else), you can always find out more about our game at WhereShadowsSlumber.com, find us on Twitter (@GameRevenant), Facebook, itch.io, or Twitch, and feel free to email us directly with any questions or feedback at contact@GameRevenant.com.

 

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

Jack Kelly is the head developer and designer for Where Shadows Slumber.