It’s usually the most productive time of the year, but hands up guv’nor, I’ve been a naughty boy. I spent a good deal of December replaying The Witcher 2: Assassins of Kings; that was going to be last week’s blog, but I actually hated the game so much that I didn’t want to wallow in all that negative emotion. I’ve got a negative attitude as it is, no point indulging it, especially in this season of goodwill.
I would also usually have a slightly longer festive break in which to play and develop, but I spent all my days off earlier in the year going to Canada in March (proper snow, almost too proper) and an OMD concert in the Museum of Liverpool at the start of November (can’t wait for the DVD release, I was jumping up and down all night so should be easily spottable).
But you’re not here for that chit-chat. No, you’re here for the story of bot AI in my game.
When I first began to lay my plans for this, I was convinced that I would need some kind of pathfinding mechanism so that my bots could travel around levels safely. Unity bestowed its Navmesh system on the free version around that time, and there’s always that fancy free A* implementation that’s been floating around a while.
My problem with pathfinding is that I don’t understand how it works, and it’s relatively computationally intensive. Individually, those factors are fine and can be dealt with, but I know I’m not the best at high-octane programming and if there’s anything that kills me in games it’s frame-rate drops. The bottom line is that I don’t trust myself to engage a full-scale pathfinding algorithm without nuking my performance. (Remember — I want to spend all the cycles that I save on artwork on high unit counts, lots of physics objects… Not janky programming.)
Well, there is another element to it too: I don’t really understand how to engage these systems properly. You must’ve seen my demo videos so far — the scratchpad level is just some random pieces of geometry scattered around.
But when I played with Navmesh in the 6-day feasibility study more than a year ago, as the name suggested, it required a mesh. That project level had a terrain mesh which seemed to sort of fit the bill, but it felt awkward and the terrain had more triangles in it than every other decoration put together.
Now, though, I don’t expect to focus my world on one unifying heightmap terrain mesh. Just like the collection of random cubes in my current scratchpad, levels will instead be artibrary chunks of natural and unnatural mesh jammed together. Hell, I spent enough time grappling with that cack in WC3, so I’m not going to voluntarily enforce the same constraint on this bright new future.
I suppose it’s also an issue of expectations. My first brush with bot pathfinding was making Unreal Tournament maps — not that I ever finished anything worthy of note, but the idea of plopping down pathing nodes to guide the bots over completely arbitrary geometry made plenty of sense to me then and seems a more natural fit for my plans now.
Attack-Move to Victory
Then it hit me: I’m not actually making a strategy game. Do my characters even need to be able to navigate between arbitrary points over arbitrary terrain with an expectation that they’ll actually get there?
Taking it back to Project Y4, I didn’t use as much of the built-in RTS pathfinding as you’d expect. I had patrol points at the corners of all the roads, and each of those would send bots reaching them along to the next patrol point on the route. They never deviated from these, except in pursuit of the player; at which point they would either be killed, or kill and return to the patrol route.
If you break it down, there’s no insane graph traversal required at all.
Place a set of patrol nodes in line of sight of each other and all you need to do is tell the bot to face each one and walk forwards. Plug in my existing jump-check code and they can even cope with minor obstacles along the way. On reaching the target node, just swap to the next one and repeat.
Pursuit is just the same — except instead of walking towards a patrol point they’re now walking towards a mobile enemy. Drop a series of new patrol point breadcrumbs to track the way home in case the enemy leads them on a merry dance, then make them retrace their steps when it’s time to give up or they win the fight.
Yes, the patrol routes make up a graph of sorts, but it’s not magical. Each node just contains knowledge of the next node on a particular named route.
Yes, the need to create and bake in dedicated patrol routes does place some additional load on level construction. On the other hand, content was always going to take up the bulk of development time here — and like I said, I spent a load of time in Project Y4 doing that already and it wasn’t too bad (it’ll be much easier with my own systems too, rather than WC3’s regions-and-if-statement-hell). Levels will require carefully crafted patrol routes anyway, so the time to needed to lay them down will be negligible compared to the time spent planning them out.
Naturally, I haven’t made a video of this yet because the theory is a lot less brain-melting than the actuality. Everything is a state machine but holy shit there are so many moving parts.
Of course, with Helios now on the scene I will be getting a stack of modern games for crimbo, so prepare yourselves for another development dry spell (but hopefully a review monsoon season).
Have a proper crimbo, everyone!