The next version of Airships will focus on improvements to troops. In this post, I'm going to write about the performance and pathfinding problems that large numbers of boarding troops face, and how they have been resolved for the next version. When I originally wrote the code for air marines and grenadiers to find their way from one ship to another, I had in mind that there would be maybe a dozen or so boarding troops in a given combat. But of course, there was actually nothing stopping players from using hundreds, and this made for some big performance problems, with the game freezing for several seconds at a time as it tried to figure out the pathing for all those troops at once. Why was the performance on this so bad? After all, plenty of games have units pathing from one place to another, and they don't have your computer freeze up trying to figure things out. Airships is a bit of a special case, though. In most games, the shape of the environment is more or less static, and so a navigation mesh can be pre-calculated for each level. In Airships, everything is constantly changing: ships and floating rocks are in motion against each other and the ground, and parts break off and new holes get shot into ships. What is one of those little air marines actually trying to do? It's just exited from the hatch of its own ship, and it wants to get inside of its target ship. To do this, it has to execute a series of leaps and drops between ships, rocks, and the ground. In a simple case, it just has to walk over to the target building. But in a more complex case, it has to jump between multiple things before it reaches its target. Within each of those ships or rocks, it then has to move to find a spot from which it can jump to the next place.
So there are two levels of pathing, a coarse one between things, and fine one within them. The coarse pathing already works pretty well, since there aren't that many different entities to consider. But the hard bit is the precise planning of where to go to be able to jump to another ship.
To figure out the jump, the marine has to consider a number of different places to jump from, and for each of them, a number of different places to jump to. And this information can go out of date very rapidly as ships move. So if there are hundreds of marines, and dozens of tiles to potentially jump from, and dozens of tiles to potentially land on, that's a hundred thousand or more jumps to consider. That's where the computer freezes up, while trying to process all this information in a single frame. I was able to optimise some of the code, but this wasn't really enough. The real fix is what I ended up calling the "conch of cleverness". Instead of all troops doing these calculations simultaneously, there is now exactly one unit each frame which gets to do jumping calculations and other CPU-intensive tasks. Because the problem was less with the total amount of calculation needed, and more with how it was all happening at once. With the "conch of cleverness" passing between troops, the performance cost of doing these pathing and jumping calculations gets evened out. This does mean that large numbers of troops now take slightly longer to figure out where they're going, but this is fine, and even kind of realistic: a crack team of four air grenadiers can move faster than a squadron of a hundred marines. And we're still talking one full calculation per frame, so at 60 FPS, a group of sixty units takes no more than a second to get organised. It turns out that it even makes the movements of very large numbers of troops look quite nice: groups of troops will move together to a location and then wait there until it's their turn to figure out the next leg of their journey. So they automatically divide themselves into what looks like squads commanded by a leader.
Apart from performance, the other nagging problem boarding troops had was that they sometimes got stuck, unable to find their way to the entry hatch of a ship they wanted to board. The reason for this was that they simply tried to move towards their target in a straight line. As anyone who's ever moved in the physical world knows, this is not guaranteed to get you where you want to go. In particular, it was this type of scenario, where the only way to the destination is to first go further away from it, that defeated them utterly.
And so as much as I'd tried to avoid it, it was time to put in some pathfinding for troops on the outside of ships and rocks. (I'm going to talk about ships from now on, but the same applies to floating rocks.) But pathfinding is, again, really computationally expensive if you can't pre-calculate a nice navigation mesh. So I had to come up with a way to quickly (re-)calculate an... acceptable navigation mesh. I realised that we needed a set of tiles from which all tiles on a ship were directly visible in a straight line. That way, the pathfinding could find its way to a tile from which its destination was visible. These tiles are the concave points of the shape of the ship, and conveniently, they're very easy to calculate. This means it's OK to do it every time a tile is destroyed or added.
Together, they form a network of tiles from which every corner of the ship is visible, but there are far fewer of them than total tiles on the ship. In fact, a rectangular ship has zero of them, as any tile can be reached in a straight line from any other tile. With this network in place, I wrote a first version of the pathing code, a simple depth-first search of the concave tiles. I created a weird labyrinth of a building and let some marines find their way through it. And indeed, it worked! But it took an eighth of a second for a marine to find a path through the labyrinth, which was way too much.
So I sat down, opened Wikipedia, and with a few hours of cursing and head-scratching implemented A* search - the standard, traditional pathfinding algorithm. The time to solve the labyrinth went down to one millisecond. And indeed, now it was quite possible to have hundreds of marines all navigating this labyrinth with the game running smoothly.
Problem solved.
Next up, I'll be writing about introducing flying troops - Suspendium Bees, Aerial Hussars, and other delights.