Walkboxes and pathfinding in KIAVC

In any adventure game (in any game, really), one of the most challenging functionality to implement is often pathfinding, that is the ability for the engine to figure out which path a character should follow to go from point A to point B. In fact, in a land full of pixels you can walk on, you may want some of them to be avoided, e.g., because they’re a pool of lava, or a wall, meaning the character should go around them rather than go in a straight line. Needless to say, for the novices (as I am) pathfinding can be quite complex, as there are different ways to solve the problem, and all of them require you to change your perspective of how you’d go around finding a path yourself.

In this blog post, I’ll explain how I did it in this first iteration of KIAVC, by sharing some info I found across the way as well. As you’ll see, I did make a few assumptions to simplify the domain (which comes with some disadvantages), but as a first step I was quite happy with the result anyway: in the future, I plan to revisit the implementation so that it’s made a bit more generic and flexible.

What is pathfinding?

As we anticipated, it’s the ability to find a walkable path from point A to point B. While it’s overwhelmingly used in videogames of any kind, we actually see similar applications of the same concept in other domains as well, e.g., in network routing or whenever you use the navigator in your car. In point and click adventures it’s particulatly important, as it’s what dictates what path a character follows any time you click somewhere on the screen: it’s even more important when the destination you want to get to can’t be reached by just walking in a straight line, but you have to go around something, or follow a more complex path. All these considerations have to be taken into account when working on a pathfinding algorithm.

Of course, the first thing I went to check was how they did it in SCUMM, which is how I encountered “walkboxes” for the first time. In a nutshell, every room in SCUMM could be configured with a set of walkboxes, that is, boxes you could walk on, which would overlap the room screen background: points outside of those boxes were areas you could not walk on (e.g., the water in the Melee docks). Considering that each walkbox was a polygon determined by four points (so a rectangle or something more complex than that), multiple walkboxes were needed to provide some flexibility in drawing the walking areas, since a single walkbox would not be able to do that. A simple example is the set of walkboxes you can see in the screenshot below, which represents the walkbox of the Melee Island jail from the first game (extracted and rendered using the popular SCUMM Revisited tool):

You can already picture the big walkbox on the left following the line of the jail cells. SCUMM was configured to figure out where different walkboxes would overlap, as they’d provide a connection from one walkbox to another: if two walkboxes were not directly connected, you’d have to check if there were one or more intermediate walkboxes that provided a connection between the two, thus allowing for a walking path; again, not that different from how routers work in networking, for instance. Considering how CPU intensive a pathfinding algorithm can be, though, these paths were not computed in real-time back then: when a set of walkboxes was assigned to a room, SCUMM would compute a map of connections and store that in memory, so that it could be easily referred to when needing a path in the game.

This was a clever and effective approach, but this is not really needed anymore. CPUs are powerful enough today that pretty much every game out there finds paths in real-time, using algorithms that have been refined over time.

Study time!

Once I had a better understanding of the root problem, I started looking into the possible ways of addressing them in KIAVC. A very good resource to start from was, once more, the excellent Groebelshoot blog, which had not one but even TWO posts dedicated to pathfinding.

In the first posts, it generalized the concept of the 4-point walkboxes used in SCUMM to generic polygons, highlighting the main challenge that comes with that: the fact that, while in a polygon with all convex angles pathfinding is easy (all points in a polygon are visible to each other), the same can’t be said when concavity is involved as well. The same concept is explained in the as usual very informative Thimbleweed Park blog as well, which is where this clarifying picture comes from:

The main lesson I got from that was that (long story short), rather than considering the whole pixel space in a map as a walkable vs. non-walkable area (which could result in a huge dataset the pathfinding algorithm would have to go through each time), all you really need are the vertices of those polygons, and how they’re connected to each other. This concept is explained in much better detail in this very interesting Stanford lesson on map representations, which introduces concepts like polygonal maps and navigational meshes (which, if you’re familiar with Unity, is what that engine uses for pathfinding), and the importance of visibility graphs.

While this helped me greatly understanding how to reduce the problem space to something manageable, I still had to figure out what algorithm would be best suited to then handle the data and give me a result.

The Groebelshoot blog posts were once again my gateway to this, as they’re what first introduced me to the so called A* (A-star) algorithm, which is pretty much the standard de-facto (modulo different optimizations that have been made over the years) when it comes to pathfinding. If you’ve had to deal with network routing in the past (whether as part of your work, or because you’ve studied them), you may remember depth-first, breadth-first and Dijkstra’s algorithm as some that would very often be used to find paths between two nodes. Dijkstra’s algorithm in particular is quite suited to find the shortest path between two nodes, and the above mentioned A* is an improvement on that. Without going too much into the details of how the algorithms differ from each other, I’ll just point to this excellent article that explains it quite clearly, and in a visual way as well. There’s another very interesting article that focuses more on A* itself and how it works, using visual aids (shown below, and borrowed from the article) to highlight the improvements it provides on Dijkstra’s algorithm for pathfinding purposes:

Digging more for a better understanding, I kept on finding other resources that provided some additional information, like this interesting intro on A*, this other informative overview, and more, often with pseudo-code that helped figure out the steps needed to replicate the algorithm. All those results further confiirmed that A* was indeed the algorithm I needed to use in KIAVC as well, so I just needed to understand how to represent the domain space and work on it.

Implementing pathfinding in KIAVC

Figuring out how to represent walking areas was the first big challenge. In fact, while I was intrigued by the large polygon approach presented in the Groebelshoot blog, I felt it was a bit too compex; besides, I was intrigued by how simply Ron Gilbert had implemented a walkbox “trigger” in his Thimbleweed Park blog post, something that in my understanding could only be done using a set of smaller, and connected, polygons instead (so something closer to the way SCUMM handled walkboxes). Reading the amazing overview on how Flight of the Amazon Queen was made further pushed me in that direction, especially when they explained how they also used walkboxes as ways to automate scaling (e.g., to reduce the size of your main character as they walk towards the sunset).

As such, I eventually decided to represent walkable areas as a set of rectangles that can overlap the background. As in the SCUMM times, a connection between rectangles meant a way to go from one to the other. You may be wondering why I chose rectangles as a walkbox unit, rather than a generic 4-point polygon as SCUMM did, and the reason was, to be blunt, to make it as simple as possible, as:

  1. it’s very easy to detect whether a point is in a specific walkbox, when the walkbox is a rectangle;
  2. I’m lazy;
  3. it’s also very easy to detect when and where rectangles overlap, to figure out connections among walkboxes;
  4. I’m lazy :mrgreen:

This gross simplification means it’s harder to properly represent walkboxes sometimes (e.g., you can’t have the smooth diagonal line we saw before in the Melee Island jail example, or even have a single diagonal line BE the walkbox), but again, my main purpose at this initial stage was getting something done quickly and that worked. There will be time in the future to make those polygons more generic.

As an algorithm, as anticipated I decided to implement A*, referring to existing pseudo-code examples as a reference. Using the information I studied from the resources linked above, I decided to use some specific points as nodes to be used in the A* algorithm, determined by the overlap area of walkboxes. Specifically, I decided to use the vertices of the rectangles that come out of overlapping walkboxes, as shown in the diagram below:

In fact, if we need to find a way to go from a point in Walkbox #1 to a point in Walkbox #2, we don’t really need to consider ALL the points in their overlap area (that could add way too many nodes to pass to the A* algorithm, and take a long time to resolve), but just some key ones, and the vertices of their interaction is a good enough simplification. This is described as “Polygon vertex movement” in the Stanford lesson we introduced before. Just to make the process a bit smoother, I decided to also add the central point of each side of the overlap rectangle as well (which that lesson calls “Hybrid movement”), as shown below:

Of course, walkboxes don’t necessarily create a rectangle when they overlap, and will sometimes only overlap on a single line. In that case, the process remains largely the same, except we only take into account the overlap line, rather than all four sides of a rectangle that isn’t there:

KIAVC is configured to create a list of all this points (and the connections they make) just once, that is when you configure the walkboxes for a room. Then, whenever we need a path found, the engine does the following:

  1. a new list of nodes, that we’ll pass to the algorithm is created;
  2. we add the starting point (where the actor is now) to the list;
  3. we add all the computed walkbox nodes to the list;
  4. we add the target point (where the actor needs to go to) to the list;
  5. we run the algorithm.

As you can see, we’re having A* run on a list of nodes that represent our walkable space, where start and target points are nodes as well. Of course, this first of all means smoothing the start and end point so that they wall in one of the walkboxes (if you click on the sea, we’ll change the target point to the closest one you can walk to). Besides, it also means figuring out which walkbox a specific point is in, so that the proper connections can be created for both start and end nodes (which A* needs to do its work). As a heuristic for A* (which I didn’t explain for the sake of simplicity, you can learn more in the links I shared before), I kept it simple and just chose the euclidean distance between.

The end result of the process is a sequence of points that connect the start to the target, where each point is connected to the next in a straight line (e.g., because they are in the same walkbox). The KIAVC engine then consumes this list of point connections in sequence, so that we can see the actor following a path to their destination. Eureka!

Let’s see this in action

While the wall of text I’ve thrown at you may have been interesting to the most curious, I understand it can feel boring and too “academic”, so let’s see how it actually works in practice in KIAVC. This will help highlight where it’s working fine, the tweaks we added that could be very helpful when scripting a game, and most importantly the areas where the current implementation unfortunately falls short (we’ve anticipated the limitation of using rectangles, but there’s more!).

First of all, let’s see how we can configure a set of walkboxes in KIAVC. We haven’t introduced how Lua scripting works (that will come in a later post), but, spoiler alert, a Lua script is indeed how you do that: when you create a room you want the engine to manage, you also pass the coordinates of all walkboxes for that room. If you check the street.lua file in the repository, which is where we initialize the main street in the demo, you’ll see walkboxes are defined like that:

	walkboxes = {
		{ x1 = 127, y1 = 146, x2 = 172, y2 = 150, scale = 0.5 },
		{ x1 = 118, y1 = 150, x2 = 180, y2 = 154, scale = 0.6 },
		{ x1 = 106, y1 = 154, x2 = 190, y2 = 158, scale = 0.7 },
		{ x1 = 80, y1 = 158, x2 = 200, y2 = 162, scale = 0.8 },
		{ x1 = 60, y1 = 162, x2 = 216, y2 = 168, scale = 0.9 },
		{ x1 = 0, y1 = 166, x2 = 14, y2 = 180, name = 'barrier1' },
		{ x1 = 14, y1 = 166, x2 = 580, y2 = 180 },
		{ x1 = 580, y1 = 166, x2 = 608, y2 = 180 },
	},

Let’s skip the scale and name properties for now (I’ll address them in a minute), and let’s focus on the coordinates instead. As you can guess, those are the coordinates that define each walkbox as a rectangle: since we’re only dealing with rectangles, we only need two points, namely the top-left corner (x1, y1) and the bottom right corner (x2, y2). That’s all the KIAVC engine needs to import those walkboxes and automatically figure out if/how they’re connected.

The KIAVC engine comes with a pathfinding debug mode, that allows you to visualize all those concepts as an overlay on top of the screen. In the demo that’s shipped out of the box, you can enable that mode pressing F11, which will display something like this:

Quite simply, we’re actually drawing the walkbox rectangle on top of the screen, so that it’s immediately visible where you can actually walk to. This already highlights on of the limitations of our use of rectangles: the sides of the street would be better served by diagonal lines, but we have to “approximate” that by using rectangles that are, step after step, larger than the other.

The debugging mode also shows us the path that is calculated any time we click somewhere on the screen. An example coming from the demo is provided below:

If you remember the discussion we made on how we compute the nodes out of walkboxes overlap areas, it’s easy to see this in the path the algorithm resulted with: the actor was in one specific walkbox, and the first step was towards the closest walkbox to get to the destination, which they traversed in the central point of the overlap between those walkboxes; the same happened with the walkbox below, and for the last one, where we went for the vertical side of the overlap instead; finally, it was a straight line to the destination, since we eventually ended up in the walkbox containing the target point.

This does show the algorithm doing its job properly, but highlights another problem: why the changes in direction, when we could have gone in a straight line instead? The short answer is that my pathfinding algorithm doesn’t really take into account the so-called “line of sight” yet: it’s true that those are different walkboxes, and so the decisions the algorithm makes definitely make sense had we needed to go around something, but when there is line of sight between some points (even when they’re in different walkboxes) it would save some steps (and be smoother) to just walk a straight line. That’s indeed something I plan to address in the future, but it’s not there yet, meaning you can get some even weired calculations like this:

Again, definitely room for improvement! But it does its job, and works nicely when you’re actually going around things too.

What’s particularly interesting, though, is the additional things you can do with walkboxes. Looking at the animations above, you may have noticed how the size of the actor changes automatically while going up and down the road: this is a consequence of some additional properties we can add to walkboxes, and that the engine understands. If we check the walkboxes definition again:

	walkboxes = {
		{ x1 = 127, y1 = 146, x2 = 172, y2 = 150, scale = 0.5 },
		{ x1 = 118, y1 = 150, x2 = 180, y2 = 154, scale = 0.6 },
		{ x1 = 106, y1 = 154, x2 = 190, y2 = 158, scale = 0.7 },
		{ x1 = 80, y1 = 158, x2 = 200, y2 = 162, scale = 0.8 },
		{ x1 = 60, y1 = 162, x2 = 216, y2 = 168, scale = 0.9 },
		{ x1 = 0, y1 = 166, x2 = 14, y2 = 180, name = 'barrier1' },
		{ x1 = 14, y1 = 166, x2 = 580, y2 = 180 },
		{ x1 = 580, y1 = 166, x2 = 608, y2 = 180 },
	},

you can see that some walkboxes have a scale property: as the name suggests, that indeed tells the engine that, for any actor walking on that specific walkbox, that scale factor must be applied to the (possibly already scaled) actor. In this example, we start from telling to scale the actor to half their size, and then slowly increase them as they go down. Where a scale property is not provided, the default is 1.0. Notice that this does not replace a scaling we may have done on the actor already, but acts on that: in the demo, for instance, the main actor is scaled at 0.76 in the streets, which means that a 0.5 in the walkbox means “half of the scale the actor is currently in”. I stole this “use walkboxes to scale” concept from the Flight of the Amazon Queen blog post, which really opened my eyes when I read it, since it once again showed how you can actually use a thing that may seem to only have a single purpose for other objectives too.

Another interesting property walkboxes have is the ability to be named. This doesn’t seem to be much (walkbox has a name? yeah cool, who cares!), but is actually quite important in KIAVC, because if a walkbox has a name, the engine will tell your script any time an actor enters that specific walkbox: this opens the door to interesting opportunities, because it allows you to script a specific behaviour for when a walkbox is triggered by a specific actor. In the demo, we have a single walkbox that has a name, which is called “barrier1”, and is the walkbox on the far left of the screen. Let’s see what happens when we walk on it, with debugging enabled so that we can see when the actor hits the box:

In the demo, we handle the walkbox trigger by starting a script: the script stops the actor, makes them say something, and then automatically walks them back to a point in the previous walkbox. This is an interesting way to add triggers to a room (e.g., a bouncer that stops you on your feet until you solve the puzzle to get in), and since the actor ID is provided as well it can be configured to react differently (e.g., the bouncer letting every NPC actor in except you). Nothing fancy or crazy complex, as you see, but still quite effective in its simplicity!

That’s all!

I hope you enjoyed this little insight on how pathfinding works in KIAVC! As you’ve seen, it’s quite basic right now (complexity of A* aside), and definitely needs work (which I hope I’ll be able to put in next, in the future), but still it does its job despite its limitations, and the scaling/trigger tweaks make walkboxes quite interesting from a scripting perspective. At the very least, I hope I provided some context and resources on pathfinding for those that wish to learn more.

Next step now is working on a blog post to introduce how scripting works: that’s going to be interesting, but also quite challenging, as there’s so much to say! See you in a few weeks for some info on that 😀

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 )

Connecting to %s