Reminder: in October 2018, I’m pygame.org’s artist in residence. You can ask me questions about Trosnoth, support me in my Trosnoth development, and follow this blog for articles about Trosnoth and what I’m working on.
Dreaming of robots
Trosnoth was designed primarily as a multiplayer team game. The first playable version of Trosnoth had no computer-controlled players and nobody cared one whit.
But even in the early days of Trosnoth I remembered writing robots in C with PCRobots, and dreamt that perhaps one day we could use Trosnoth as an arena in which programmers could pit their bots against one another.
I couldn’t find any screenshots of PCRobots, but pybotwar is a modern variation on the same theme.
It turned out this dream wasn’t hard to realise. One year on Übertweak we ran an elective where camp attendees could program Trosnoth bots using the same kinds of controls that human players have: press jump key, release jump key, aim this way, pull trigger, and so on. The elective went fairly well; people coded robots that were able to kill other robots and often even kill human-controlled combatants.
But I wanted more. I wanted Trosnoth bots that could play a competitive game of Trosnoth. Bots that would capture territory, work together, and make decisions about when to attack and when to defend. In the end we achieved this, but it turned out to be a difficult endeavour.
Troubles with robots
The most difficult part of programming a competitive Trosnoth bot was path-finding. In order to capture territory, a bot needs to be able to move from its current location to the centre of the zone it wants to capture. But between those two points are all manner of obstacles and ledges. When should the bot jump? When should it release the jump key? And which way should it try to go to get around that big block in its way? These are the sorts of questions the bot needs to be taught to answer.
Now to a developer this may sound like a simple search problem: just use A* to find the shortest path and Bob’s your uncle. But there are three factors which make this more complicated for Trosnoth.
Factor 1: Infinite search space
Trosnoth obstacles and ledges are vector-based not tile-based, and Trosnoth physics calculations use floating point arithmetic. This means that there are practically infinite possible ways that a bot could get between two points on a Trosnoth map. Using A* with a naïve heuristic such as euclidian distance doesn’t work so well in this case: the search would need to perform a vast number of physics calculations as it explores possibilities. In practice this kind of search can run four hours and still not arrive at the best route.
We obviously needed to reduce the number of possible paths a bot can take. So instead of calculating every possible combination of key presses at every possible instant, we simplified the problem: we started from a position where the bot is stationary, and defined a finite number of actions like ‘hold down the jump and left keys until you hit something’, or ‘drop down through the ledge you’re on then wait until you land’. This approach reduced the number of possibilities to consider, but the resulting search was still far too slow for a real-time game.
Factor 2: Physics calculations are slow
In a previous article I mentioned that Python has always been a fast enough language for Trosnoth. This is true when Trosnoth only needs to calculate one set of potential collisions per player per frame. But searching for the fastest path between points involves calculating many many sets of collisions. It involves simulating what would happen if the bot went this way or that way or did any number of other things. It involves calculating several orders of magnitude more sets of collisions than would normally happen every Trosnoth frame. Even if we’d written Trosnoth in highly optimised C, finding the path this way would be slow.
I can hear your objections. ‘Other games don’t seem to have any trouble with path-finding! And Google maps gives me directions almost instantly. It can’t be that hard!’
There are a few things going on here. Firstly, path-finding in top-down games is a somewhat easier problem. In any given room in a top-down game, the shortest path between two points is a straight line. So for these games the problem is reduced to finding the best path between rooms. But secondly, even in complicated situations like a road network, search engines such as Google maps do most of the hard work before you even tell it where you’re going to and from. Google precalculates information that will help it make rapid decisions about best routes.
So we took this approach with Trosnoth. The precalculation phase involves doing a whole load of physics calculations and storing them in a database. We only need to do this once, and the resulting database can be shipped with a distribution of Trosnoth. During a game, the bot path-finding algorithm can then look up where it would end up if it took a certain action. (Doing this necessarily involved discretising possible bot positions so that the database didn’t have to be infinitely large.) The precalculation phase also includes precalculating some heuristic information about certain points to reduce the number of options that need to be examined to find the best route1. However, in Trosnoth’s case, there was a limit to the amount of precalculation we could do.
These bots know where they’re going and how to get there.
Factor 3: Dynamic map generation
Trosnoth maps are put together randomly, like a jigsaw puzzle2. You tell the game what size map you want, and the game follows an algorithm to piece map segments together into a complete map. This obviously limits the amount of precalculation that can be done. We could precalculate possible bot movements within a given jigsaw piece, but not across the map as a whole.
We did two things to overcome this challenge. Firstly, we precalculated possible bot movements between adjacent jigsaw pieces for every valid pair of adjacent pieces. This allowed Trosnoth bots to reliably predict where a given action would take it even when crossing segment boundaries. There are a lot of possible pairs, but it’s still a finite number so it was feasible.
Secondly, we calculated big-picture transition data for each jigsaw piece. For instance, we store information like, ‘it takes at least 37 frames to get all the way across this map segment from east to west’. This allows Trosnoth bots to make big-picture decisions about how to traverse a map before getting into the specific details. The resulting routes chosen are not necessarily the absolute fastest but they’re pretty good, and they’re quick to calculate.
The result
In January 2016 we released Trosnoth 1.8.0 which had a practise mode with bots which could actually find their way around the map and capture zones. Not only could they capture zones, but they were quite competitive.
Of course skilled players could still beat these bots. So we gave the bots the ability to notice and avoid enemy bullets as they found their way around the map. The resulting bot was so challenging that the change log for Trosnoth 1.9.0, released in January 2017, includes the item: ‘Made the default bots easier to defeat.’
Trosnoth 1.9.0 also came with a humans vs. machines game setting. It works just the way it sounds: a team of humans can pit their skills against a team of bots. In recent games the bots seem relatively evenly balanced against a team of experienced Trosnoth players3.
What I’m working on now
We’ve had highly competitive Trosnoth bots for over 18 months now, yet I’m once again working on the bot path-finding code. Why is that?
Trosnoth has always had a retro feel to its physics: if you hold the left arrow, you move left at a constant x-velocity4. But in the development branch of Trosnoth, we’ve changed the physics to be momentum-based. This is lots of fun to play, but it breaks some of the assumptions that the previous pathfinding code used. We’ve also updated the way collision detection works, which breaks some other assumptions.
At present we get around this by keeping both the old and the new physics systems around: human players get new physics and bots get old physics. But this violates Trosnoth’s foundational principle of scrupulous fairness. So I’m currently working on reimplementing the bot path-finding code and making it less tightly coupled to the physics engine. The aim is to have highly competitive bots that move with momentum. They will be nigh unstoppable!
And that’s the deal with Trosnoth bots for now. Don’t forget to watch out for the final article in this series coming later this month.
Notes
1 When I was working out how to do this I read numerous academic papers on path-finding. There are so many interesting and ingenious path-finding shortcuts that I’d like to write more about this some time.
2 Perhaps you don’t put your jigsaw puzzles together randomly. Trosnoth does.
3 I’m of the firm opinion that if a team of humans trained together regularly and played with consistently good teamwork and communication they could defeat the bots every time. I welcome anyone who would like to put this opinion to the test.
4 Unless you’re facing backwards, in which case you move left at a slower, but still constant, x-velocity. Obviously.