Character movement turned out to be one the more complex systems in The Necromancer’s Tale, perhaps unexpectedly (to me). I’ve been working with A* pathfinding for nearly 20 years now (having first discovered it when working on Darkwind), and have taught it to my undergrads for the past 10+ years. It’s at the core of both in-combat and out-of-combat movement of the characters in TNT.

Hexgrids

Hexes are often considered better than squares for turn-based combat games, since hexes are the same distance from each of their neighbours. My code for building these starts from a seed position, which is manually set at a walkable location, and then it searches in all 6 directions using raycasts to see which ways can be walked from this location (i.e. which directions are clear of obstacles). This adds more hexes which are then also searched – we “flood” outwards until all reachable hexes within our predefined region have been added, along with their connectivity to their neighbours.

This produces a graph of connected nodes, which is perfect for the A* algorithm. We also need to be able to quickly gather hexes within an arbitrary region of space (without the inefficiency of having to search outwards from the seed location to find them), so hexes are also inserted into buckets which are configured as a sparse 3D array based on 1m x 1m x 1m size. The overworld has 70,000 connected hexes, and each interior/underground location has its own hexgrid. All A* grid loading and pathfinding is performed by multiple threads.

Less Need for Invisible Walls

The player has several options for how to control movement, including mouse-clicking (which uses A* pathfinding to figure out a route around obstacles) and direct WASD or joystick-based control (which does not).

Direct movement (WASD/joystick, where movement is constrained only by collisions) has a problem whereby players might wander away from where you want them to go, and off into the empty wilderness. By cross-referencing the player’s position with the hexgrid, I constrain the player to stay close to the nearest hex – this means there’s less need for invisible walls to stop them wandering off into the wilderness where there is no game content, or from walking inside solid objects when Unity’s rather suspect physics mesh-collisions fail.

Nice things you can do with the G (‘cost’) component of A*

A* is a pretty elegant algorithm for efficiently finding the shortest path between two locations. At its core is a calculation F = G + H, which estimates the distance that a possible solution might take through a given node. The G part of this is interesting: it’s the cost of getting from a node to a neighbour. Often this is simply chosen as the Euclydean distance between the nodes, but it doesn’t have to be.

We can make the G cost higher, for example, when crossing difficult terrain. This discourages the algorithm from picking a route without actually forbidding it. In TNT, I quickly found that the townsfolk loved taking a shortcut through a graveyard, which was often a slightly shorter way of crossing the river between the north and south of the city. This didn’t feel right: the cemetery path is visibly narrow and not well-worn, and crosses a narrow bridge, while the ‘standard’ route is a wider stone bridge leading through the marketplace.

So I added penalty areas – regions of space for which the G cost between hexes is artificially inflated. The cemetery is an obvious place where this works well, but this approach let me fix other areas too, for example narrow gaps between pairs of houses. I also add a per-terrain-texture penalty, so that NPCs tend to walk on cobblestones in preference to grass or sand. This stopped them from taking shortcuts all the time, and kept them to routes that they visibly ‘should’ be using.

By the way, if you’re wondering about all those white and blue boxes, they are named location markers – NPCs often move between specific locations so this was a good way to lay them out. These markers are also used in the cutscene system, allowing ‘stage directions’ to control character movements synchronised to a conversation or scene. [I wrote a bit about the cutscene system here.]

Believable Pedestrian Movement in Crowded Environments

Once I had a town full of wandering villagers, I needed to make them aware of each other so that they weren’t colliding all the time. Over the several years I was working on this, l had written various last-minute avoidance approaches (basically, over-riding their current A* path trajectory when they were about to collide) so that characters didn’t walk right through each other. It worked okay, but not great: avoidance tended to look very unaware and last-minute.

Here in debug mode they’re telling me about random path modifications they make when there’s other pedestrians nearby:

But then I discovered the RVO (Reciprocal Velocity Obstacles) algorithm: see discussion [here] and [here].

This provides a more elegant simulation of all moving characters, each of whom registers their intended trajectory. The paths taken by characters are then modified to avoid collisions several seconds into the future.

One Size Does Not Fit All

I had put a lot of effort (3+ years) into massaging my code and its parameters so that it worked well in all circumstances while overcoming recurring problems such as NPCs falling into holes or getting stuck on stairs (are stairs a hole when you’re going down? Are they a cliff when you’re going up?) Given the different sizes and speeds of characters, and the different steepnesses of terrain and stairs, this was a difficult task and perhaps ill-posed, i.e. lacking any single correct answer given the constraints.

My breakthrough came in a very simple form: I started to demarcate areas where the rules behaved differently. When walking on stairs, a character could turn off its hole-avoidance and steep ground avoidance. When going through busy narrow archways, characters could temporarily make their RVO objects thinner, so they don’t get in a muddle all trying to avoid each other. These are simply done as Triggers in Unity. When a character is inside a certain type of trigger, it runs alternative code for specific sections of its movement function.

Other Things I Have Written about Pathfinding

I’ve done some other interesting things with the A* algorithm over the years. [Here’s one from 15 years ago] with [an academic paper I wrote]. I captured data from players in order to make computer-controlled vehicles take ‘sensible’ routes.