Navigating World of Tanks

World of Tanks is a fairly large online, "massively multiplayer" arcade tank shooter game. It's also a huge grind: the game features over 200 different tanks, each with their own unique characteristics and play style.

As you may or may not know, I've been working on a bot for the game called TankLeader. The single biggest challenge in writing that bot? Navigation, bar none.

You see, when you normally implement a mesh based navigation system you'll maybe have a handful of different agents you need to generate meshes for. This game has hundreds. Literally. What terrain is passable depends on your tank's size, your track rotation speed, your horsepower per tonne ratio, ground resistances, and maybe even a little bit of driver skill. That is without even mentioning gun depression, or general effectiveness of a tank in a given position.

Let's look at an example. Consider this position on Overlord:
Overlord

It may look a little off, but that's because it's not textured like it is in game. This would be a spot that I'd happily take my Comet or Centurion 7/1 to. Heck, I'd probably even drive my Object 140 to this position. They've got decent gun depression, can crest these hills effectively, and have a good chance to give the opponents a run for their money down on the east end of the map.

Would I take my 112 or Churchill there? I could, but I probably wouldn't want to. While the terrain is strictly navigable for both tanks, and we could take them to this position, it's very doubtful they'll do any good in it. The 112 won't be able to get its gun down on anything without exposing its lower plate, and the Churchill won't make it there before time runs out. Oh, and its armour will probably be useless too.

And that's a huge limitation we face in the current implementation of TankLeader's navigation: every tank uses the same navigation meshes. Take the four tanks I outlined above, they couldn't be more apart from each other. There's no way these tanks should be using the same positions.

What do we do about it then?

Well, we could make a Type 4 Heavy fit through this gap you can probably squeeze your ELC AMX through:
Gateway

But I don't think that's a very good idea. We'll need to make the bot somehow know that if it's playing an ELC AMX, it could use that route, but when it's driving a Tiger, it really can't.

One of the ways to tell the bot this is to have separate navigation meshes for each individual tank. That means instead of one mesh per map, we'll have over two hundred meshes of each map. With 38 maps currently in the game, we're looking at over 7,600 unique meshes.

Going from 38 meshes total to over seven thousand will require huge infrastructure upgrades, as our current tool set isn't capable of generating meshes on this scale, let alone serve those meshes on a per-tank basis. Upgrading those tools - which usually means rewriting them, as they weren't written with this purpose in mind at all - will take time. We're currently hoping to get a preliminary release supporting this new navigation system out around October 2016.

This new navigation system opens up a whole new world of possibilities. We'll be able to tweak navigation on a per-tank basis, and potentially even allow the bot to correct itself when it finds terrain it can't pass through, and thus, learn the terrain as well.

I'm amazed you got through all of this unscathed. I promise the next read will be slightly less dry.