One of the fun parts of adventure games is exploring locations: walking around them looking for clues or just for admiring the wonderful artwork (we’ll get to that, much much later…)

From walking around a small prison cell – looking for a way out – to chasing an elusive character hidden in a vast office building either takes a few footfalls in a single room or the equivalent of a marathon spread out over various locations.

So how do you implement this ‘walking around’?
How do you define which parts of the screen a character is allowed to walk? How do you handle mouse clicks outside of those areas? How do you find the shortest path a character could walk to its destination?

In this post, I describe the general approach on how I take on these issues. Searching on the web you can find many ways to deal with pathfinding in 2d games. As it goes, I also checked a couple out, until I figured out a solution that is both easy to implement and serves our purpose.

Let’s take a look at the simplest case of pathfinding to illustrate what’s basically involved:
Disclaimer: Because we have no artist in our team (yet), all art is either programmer-art (all static backgrounds and sprites) or animated sprites we temporarily “borrowed” in fair use.

So what do we see in the picture that moves all by itself?
It demonstrates realtime pathfinding in such that every frame – within the game loop – the shortest path is calculated from the position of the character (green dot) to the position of the mouse (red dot). The white line shows the shortest path from start to end.

The image also shows the walkable area (walk area) demarcated by the blue lines, which is in fact a polygon. This polygon is defined by an array of vertices. For this game’s purpose a vertex is defined as a point in 2d space, meaning it just has a x and y coordinate.
The blue polygon defined in Haxe code looks like this:

Because this particular polygon is a simple one, pathfinding is real easy here. As you can see, every point inside the polygon can connect to every other point (within itself) in a straight line. This is the case for all convex polygons.

In the first illustration you can also see that when the mouse cursor leaves the walk area, there is still a path for the character to walk on. The end point of the path is the point on the polygon closest to the mouse position.

But what if the polygon is not convex and therefore the walk path cannot always be a straight line because there is stuff blocking the path?

Let’s have a look at an example that reflects that:

So obviously there’s a lot more going on here. Not only is the walk area (blue polygon) more complex, but there are also yellow dots and green lines to boot. What is this all about?

First of all the walk area is complex, because the character has to walk around these…err…these puddles of water [radioactive goo?], or whatever those are (yeah, programmer art).

The walk area is no longer a simple convex polygon, but a concave polygon, which has one or more interior angles greater than 180°. As a result some vertices point inwards.
It’s clear here that not all points inside the polygon can connect to every other point in a straight line. I’d say we’re at the point we need some actual pathfinding!

So far, I’ve only discussed the definition of the walk area, but for pathfinding you need more than just that. Since I use the A* pathfinding algorithm, which is used a lot in games, this little extra goes in defining a graph of nodes and connections (edges) between those nodes. Using this graph and its nodes the algorithm can find the shortest path from a start node to an end node.

The tricky part here is: how do you define the graph?

In the given example you can see the graph visualized by the yellow dots and the green lines with also the starting point as the green dot and the end point as the red dot.
Here’s how the graph is constructed:

• Every ‘concave vertex’ (a vertex with an interior angle greater than 180°, so an inward pointing vertex) is a node
• The start position (position of the character) is a node
• The end position (mouse cursor in the example) is a node
• For every node an edge is made to another node only when there is a ‘line of sight’ to that node. A line of sight means a straight line from a node to another node inside the polygon without crossing an edge of the polygon.

Following these steps will give you a graph that you can feed into a pathfinding algorithm.
Of course this sounds easy, but it involves some maths that you have to implement. It’s not too hard, but not every programmer loves math. In a follow up post I’ll dive into these maths in detail.

Let’s have a look at another slightly different example:

In this example the walkable area is not one, but two polygons, or… you can see it as a polygon with a hole in it.
The construction of the graph is almost the same, except that all convex vertices in the inner polygon are nodes in the graph instead of the concave vertices.

The constructed graphs in both example are fed into the A* algorithm, which in turn calculates the nodes the character needs to travel to reach its destination unscathed.

For this post, I’ll keep it at this. So far, I’ve only scratched the surface of the subject of pathfinding here. Following up I’ll discuss the following:

• Math: how do you calculate
  • line of sight?
  • closest point on polygon edge?
  • if a vertex is concave or convex?
  • and more
• How do you implement all this in Haxe?
• How do you scale the character when he is walking into the distance?
• How can you trigger events when a character is in a specific area?
• How can you block/unblock parts of the walkable area from game logic?

Some of this is explained in part 2 and some will be in another follow up post.
If you can’t wait, you can check this post about polygonal pathfinding from David Gouveia, which I used heavily for inspiration, or this page which dives deeper into the implementation of the A* algorithm.

Let’s end this post with a capture from the game editor which shows the editing of the walkable area: