When we at Ronimo Games first started development of the bots for Awesomenauts, we started with the most complex parts: path finding and movement.
When people think of path finding, they usually think of A*. This well-known standard algorithm indeed solves the finding of the path, but in a platformer the step after finding the path is much more complex: doing actual movement over the path. Awesomenauts features a ton of different platforming mechanics, like jumps, double jumps, flying, hovering, hopping and air control. We also have moving platforms and the player can upgrade his jump height. How should an AI know which jumps it can make, how to time the jump, how much air control is needed? This turned out to be a big challenge!
Our first guess was to record tons of gameplay by real players and generate playable path segments from this. But this solution turned out to be too much work to implement. We needed a simpler approach.
Looking for a better solution we started experimenting. Programming intern Bart Knuiman made a small level that included platforming but no path finding, because there were no walls or gaps. Bart’s goal with this level was to make an AI that was challenging and fun to play against, using only our existing behaviour tree systems. In less than a week he did just that. Most Ronimo dev team members lost their first battle against this AI and took a couple of minutes to find ways to win. We concluded that for movement and combat, the behaviour trees were good enough after all.
The only thing really impossible with the systems we had back then was path finding in complex levels. We designed a system for this and Bart built this as well. The important choice we made here was to split path finding and movement into a local solver and a global solver. For finding the global route towards the goal we used path finding nodes and standard A* to figure out which route to take over them. The nodes are spaced relatively far from each other and the local solver figures out how to get to the next node.
The local solver differs per character class and can use the unique properties of that type of character. A jumping character presses the jump button to get up, while one with a jetpack just pushes the stick upwards. The basics of a local solver are pretty simply, but in practice handling all the complexities of platforming is a lot more difficult, yet still manageable.
How do we generate the nodes and edges that A* needs to find a route from A to B? The answer is quite simple: our designers place them by hand. Awesomenauts has only five levels and a level needs well below one hundred path finding nodes, so this is quite doable.
While placing the pathfinding nodes we need to take the different movement mechanics into account. Each class has his own local solver to handle its own movement mechanics, but how do we handle this in the global solver? How do we handle that some paths are only traversable by some characters? Here the solution is also straightforward: any edge we place in the path finding graph can list included or excluded classes. When running A* we just ignore any edges that are not for the current character type.
To me the most surprising lesson from this is how simple our final solution is. There are a lot of things I had expected would be really complex that we ended up mostly just ignoring in the bots. For example, remember that jump height upgrade I mentioned at the beginning? It is handled by simply not placing any paths on the few jumps that are only doable with it. Simple and works well enough!
