NPCs and pathfinding

First things first, I’m sorry for the long delay since the last post. It’s been over a month, and my only excuse is that New Year happened in the meantime – which was quite disruptive for my work.

So, anyway, what did I do during this month? One of the interesting things, that was mostly done back in december, was adding actual NPCs to the game. They don’t do much for now, but the two most important items are checked now: pathfinding and NPC activities.

I never thought I’d have to spend much time on pathfinding: I’ve had already implemented it countless (that is, at least five) times in various games. In most games, including Xenos, pathfinding is based on a popular algorithm called A* (pronounced A-star). You can read about it just about everywhere, and I’ll just explain the basic idea behind it. Which is: suppose we have a grid (square, in case of Xenos) where each cell can be passable or not. To find a path from one point to another on this grid, we basically have to examine all possible paths, until we either find one that reaches our target, or conclude that target is unreachable. To do that, we look at grid cells: beginning with the nearest neighbours of our starting point, then their neighbours, then theirs, and so on, until target is reached; in every cell we store link to “previous” cell – these links form a path. The key insight in A* is that when we have several possible neighbours to look at, we start looking with the one that is closest to the target point (more exactly, the one where distance to the target point+length of path so far is minimal). This seems a really obvious idea, and it is; what’s more, it actually works (which is more than you can say about many obvious ideas). It turns out that in many situations A* almost never even considers points that are not part of the final path.

See how A* path (cyan) looks unnatural because it follows grid lines

So, this was the algorithm I implemented immediately after I put NPC models in the game. But it turned out to have two problems. First: it was slow, but not every time. With 20 NPCs walking around randomly around the village, pathfinding sometimes would take 20-30 ms to complete – which is unacceptably slow for a game with many NPCs. Second problem is easier understood with a picture. Remember how in A* all paths only go from grid cell to adjacent grid cell, never “skipping” any in-between? It turns out that this looks quite unnatural in mostly-open spaces, like my village: real humans don’t go along grid lines, they just turn directly to their goal.

Starting with the second problem, I decided to use an additional trick with A* called θ* (pronounced theta-star). It’s pretty simple: in addition to normal A*, whenever we examine new grid cell, we also look if a line from previous-previous cell (i.e. two steps back on path) to current cell is free of obstructions. If it is, we remove previous cell from path, and go directly from previous-previous to current. In other words, we just corners whenever we can. This algorithm is pretty fast, and it produced paths exactly like I wanted to see… almost always.

A path can go directly through the grid corner – which should not be passable. To prevent this, all cells in the yellow square were checked.

To understand problem with my first implementation of θ*, look at the picture. Sometimes, when checking for obstructions, the line-of-sight would go right through the grid corner, and narrowly miss one or both obstacles along the way. I struggled with this problem, trying first to check for obstacles “a little to the side”, then checking several parallel lines some distance from each other, but then I settled on a very simple, but effective, rule: when checking this line-of-sight for obstacles, whenever a new grid cell is entered, I check that the whole 2×2 square, made by this cell and its neighbours along the line, is empty. This is easy, fast, and ensures that NPCs only cut corners where they can actually fit through. It’s a bit counter-intuitive, because it seems like this algorithm would break near doors – after all, doors are only one cell wide, and the line checking would surely stop at the doorway. But that’s not a problem, because there’s still “normal” A* going along grid lines, that can fit through narrow places just fine. In fact, it even looked better: NPC would go directly to a point close to the door, then turn and go through the doorway, then turn again toward their next destination.. sort of human-like.

With unnatural movement out of the way, I still had my performance problem. I tried many different optimisations, until I found, to my embarrasment, that I completely forgot to ever check the distance to target! That’s the main point of A* and I somehow managed to miss it. So, all this time, this wasn’t even A* at all. I felt really stupid, but also relieved… however, even fixing this didn’t solve the performance problem completely.

After some checking, I determined that the slow searches (they were down to 10-15 ms by now) happened when there was no path to destination. No matter how clever, in this case any algorithm has to examine all paths, before concluding that there’s no solution. And with the size of Xenos maps, it was going to be slow no matter what.

I know how to deal with this problem, but for now it’s left as-is. Occasional 10-15 ms slowdowns are not really noticeable with current frame rate (which is over 1000 on my, admittedly pretty beefy, machine), and I can fix this if and when it becomes a problem.

In the next post, I’ll probably talk more about NPC activities and life simulation – or maybe something else entirely.