Behind the Scenes: Path Finding

In these Behind the Scenes blog posts, I’m attempting to give a bit of an insight into what goes into developing an Old Testament adventure game. This week I’m going to talk a bit about path finding – how I figure out how to move a character from A to B via a sensible route.

Let’s start with our basic scene, as per last week:

The first stage is that I have to mark the scene up with various “areas” that the player is allowed to walk in:

The white rectangle in the middle is the ‘active’ area; the yellow rectangles are directly neighbouring areas; the cyan rectangles are other areas that can’t be directly reached from the active area; and the pink rectangles are exits from the scene that the player can click on. Between each area you’ll notice a red line: these are “gates” and show the points where the player is allowed to pass from one area to the next. For convenience I’ve numbered the areas 1 through 6, and we’ll use the notation “x-y” to refer to gates if they’re between area x and area y (e.g. 1-2 is the gate from area 1 to area 2).

When the game first fires up, we need to calculate a cost matrix that specifies the shortest distance between any two gates, and (where applicable) which other gate you would first have to pass through in order to get from one to the other. I could explain how to calculate this, but I suspect I’d only bore you, so just take it for granted that it’s easy enough. You’d end up with a matrix that looked a little like this:

The next stage happens at the point where a route is required between two specific points. You begin by finding out which area the starting point and the destination point are in. Let’s say we want to walk between area 6 and area 5. We then test each gate in the first area against each gate in the second area (easy in this case because each area only contains a single gate) and look them up in the cost matrix to work out which is going to be the shortest route. In this example, we’d notice that the best route is going to be from Gate 1-6 to Gate 4-5 (both shown in green below), with a cost of 7.0, and we’re going to want to go via Gate 1-4 (shown in orange).

So that tells you the basic shape that the route is going to take. But exactly which point along each gate should we use? Our instinct might be to walk to the middle of each gate before continuing to the next one, but that might result in very inefficient routes that might look like so:

Sure it gets the job done, but it looks a bit cumbersome and unnatural. We can do better with a simple alteration: at each step, we’ll draw a line from our current position to the place we’re trying to get to. If that line directly crosses the gate we’re aiming for, then use that intersection point; if it doesn’t cross the gate, then we’ll use whichever end of the gate it comes closest to. That allows you to “cut the corner” and take a more obvious direct route:

And that’s it – job done!