Solving path finding and AI movement in a 2D platformer

When we started developent of the bots for Awesomenauts, we started with the most complex part: how to do 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, and in games like an RTS that is all there is to it, since the path can easily be traversed. In a platformer however the step after the finding of 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 big challenge!

Since there are so many potential subtleties in platforming movement, my first thought was that handling it in our behaviour trees might not be doable at all. Behaviour trees are good at making decisions, but might not be as good at doing subtle controls during a jump. Add to that that the AIs only execute their behaviour trees 10 times per second because of performance limitations, and I expected trouble.



The solution I came up with was to record tons of gameplay by real players and generate playable path segments from this. By recording not just the player's position but also his exact button presses, I figured we could get enough information to replicate real movement with precise control. Player movement would be split into short bits for moving from one platform to another. The game could then stitch these together to generate specific paths for going from A to B.

To perform movement this way, the behaviour tree would choose where it wants to go and then executes a special block that takes control and fully automatically handles the movement towards the goal. Very much like playing back a replay of segments of a players' previous movement. The behaviour tree could of course stop execution of such movement at any given time to engage in combat, which would again be controlled entirely by the behaviour tree.

While the above sounds interesting and workable, the devil is in the details. We would have to write recording and playback code, plus a complex algorithm to analyse the recorded movement and turn that into segments. But it doesn't end there. There were six character classes at the time, each with their own movement mechanics. They could buy upgrades that make them walk faster and jump higher. There are moving platforms that mean that certain jumps are only achievable in combination with certain timing of the platform position. All of these variations increase the complexity of the algorithms needed, and the amount of sample recordings needed to make it work. Then their would need to be a way to stich segments together for playback: momentum is not lost instantly, so going into a jump while previously going to the left is not the same as when going into that same jump while previously going to the right.

The final blow to this plan was that the levels were constantly changing during development. Every change would mean rerecording and reprocessing the movement data.

These problems together made this solution feel just too complicated and too much work to implement. I can still imagine it might have worked really well, but not within the scope of a small indie team building an already too complex and too large multiplayer game. We needed a simpler approach, not something like this.

Looking for a better solution we started experimenting. Programmer Bart Knuiman did an internship at Ronimo at the time and his internship topic was AI, so he started experimenting with this. He made a small level that included platforming, but that did not need path finding because there were no walls or gaps. Bart's goal with this level was to make a Lonestar AI that was challenging and fun to play against, using only our existing behaviour tree systems. Impressively, he managed to make something quite good from scratch in less than a week. Most Ronimo team members lost their first battle against this AI and took a couple of minutes to find the loopholes and oversights one needed to abuse to win. For such a short development time that was a really good result, so 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. I didn't know that terminology back then, but someone told me later that it was a common thing with an official name. 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 doable.



The complex recording system outlined at the start of this post was incredibly complex, while the solution with the local and global solvers is so much simpler. The reason it could be so simple is that although platforming mechanics in Awesomenauts are diverse, they are rarely complex: no pixel-precise wall jumps or air control are needed like in Super Meat Boy, and moving platforms don't move all that fast so getting on to them doesn't require super precise timing. These properties simplify the problem enough that creating a local solver in AI is quite doable.

One aspect that I haven't mentioned yet is how we get the path finding graph. 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 four levels and a level needs well below one hundred path finding nodes, so this is quite doable.



While placing the pathfinding we need to take the different movement mechanics into account. Some characters can jump higher than others, and Yuri can even fly. 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. This was originally mostly needed for flyer Yuri: all other classes were similar enough that they could use the same path finding edges.

A similar problem is that falling down from a high platform is possible even if it is too high to jump towards, and jumppads can also only be used in one direction. These things are easy to include in the path finding graph by making those edges only traversable in one direction.

Creating the path finding graph by hand has a couple of added benefits. The first is that we can exclude routes that may work but are too difficult for the local solver to traverse, or are not desirable to use (they might be too dangerous for example). Placing the nodes and edges by hand adds some control to make the movement look sensible. Another nicety is that we can add markers to nodes. The AI can use these markers to decide where it wants to go. For example, an AI can ask the global solver for a route towards "FrontTurretTop" or towards "HealthpackBottom".

The path finding nodes were placed by our designers and they also built the final AIs for the bots. Jasper had made the skirmish AIs for Swords & Soldiers and he also designed the bot behaviours for Awesomenauts.

Awesomenauts launched with only six classes and only four of them had a bot AI. Since then many more characters were added, but they also never received bot AIs. Now that modders are making AIs for those we will probably have to update the edges to take things like Swiggins' low jump and the hopping flight of Vinnie & Spike into account.

To me the most interesting aspect of pathfinding in Awesomenauts is that after prototyping we ended up with a much simpler solution than originally expected. This is a good reminder that whenever we think about building something complex or something that is too much work, we should spent some time prototyping simpler solutions, hoping one of them might work.

PS. The AI tools for Awesomenauts have been released for modders in patch 2.5. Modders and interested developers can try them out, including our pretty spectacular AI debugging tools. They are free to use for non-commercial use, check the included license file for more details. Visit our basic modding guide and modding subforum for more info on how to use these tools.

The AI tools for Awesomenauts

With the next Awesomenauts patch (patch 2.5) we will release our AI editor and enable players to load modded AIs in Custom Games. The editor is in beta right now and a surprisingly large amount of new AIs have already popped up. Other game developers can also use our AI editor for non-commercial purposes, or contact us to discuss the possibility of using our tool in a commercial product. This all makes for a great occasion to discuss how we made the AIs and what kinds of tools we have developed for this.



Anyone who wants to give making AIs for Awesomenauts a try can check this little starting guide that explains the basics.

I have previously discussed in two blogposts how we made the AI for Swords & Soldiers (part 1 and part 2). Since then we have changed some of the fundamentals and those blogposts are well over three years old now, so I will write this blogpost assuming you didn't read them.

When people think about "AI" they usually think about advanced self-learning systems, maybe even truly intelligent thinking computers. However, those are more theory than practice and attempts in that direction are rarely made for games. AI that really comes up with new solutions is incredibly difficult to build and even more difficult to control: what if it uses lame but efficient tactics and thus kills the game's fun? The goal of game AI is not to be intelligent, but to be fun to play against. As a game developer you usually need control over what kinds of things the AI does. Nevertheless, some games have used techniques that can be described as real AI, especially Creatures and Black & White are known for this. I suppose for them it worked because the AI is at the very core of the game.

What almost all games use instead is an entirely scripted AI. The designer or programmer creates a big set of rules for how the AI should behave in specific circumstances and that's it. Add enough rules for enough situations, plus some randomness, and you can achieve a bot that seems to act very intelligently, although in reality it is nothing but a big rulebook written by the developer.



Awesomenauts is no different. The AI system is a highly evolved version of what we made for Swords & Soldiers. The inspiration for it came from an article Bungie wrote about their behaviour systems in Halo 2. Something similar was also presented at GDC years ago as being used in Spore and a couple of other games that I forgot the names of.

The basic idea in our AIs is that they are a big if-else tree, connecting conditions and actions. If certain conditions are met, certain actions are done. For example, if the player is low on health and enemies are near, he retreats to heal. If he also happens to have a lot of money, he buys a bunch of upgrades.

These big if-else structures are shaped like a tree and are quite easy to read. Certainly much easier than reading real code. The whole principle is best explained by a screenshot from the AI editor:



Before we made our AI editor we tried some other approaches as well. In an old school project I programmed the AI in C++, and for our cancelled 3D action adventure Snowball Earth we used LUA scripting. We were quite unhappy with both: although programming gives the most flexibility, creating such big sets of if-then-else rules is just very cumbersome in a real programming language. The endless exceptions and checks quickly become an enormous amount of confusing code.

So we set out to make a tool specifically for making AIs. Our AI editor is structured entirely around these combinations of conditions and actions and makes the problem a lot more workable. It is true that our AI editor is less flexible than code and cannot do certain things (most notably for-loops), but being faster and clearer to work with makes it possible for us to make much better AIs in the same amount of time.

Each type of action and condition in our AIs corresponds to a class in C++. For example, the condition "canPayUpgrade" corresponds to a C++ class called "ConditionCanPayUpgrade". This class looks up the price of the upgrade and the amount of money the player currently has to determine whether the player has enough money to buy the upgrade.

Since the blocks are programmed in C++ they can do very complex things. A core principle is that we try to hide the complexity and performance inside the blocks. If we need to do something in an AI tree that is not possible with simple if-else trees, then we can always add a new type of block that can do that. A great example of this is our block "isCharacterInArea", which under the hood does a collision query and checks for things like line of sight, class and health. There is quite a bit of code behind that block, but to the AI designer it is a simple and understandable block.

Our AI editor evolved and changed significantly from Swords & Soldiers to Awesomenauts. The two biggest differences are the debugging tools and the general structure. At the time of Swords & Soldiers our designers could not see any information on a running AI. To find and debug AI problems they just had to play the game and observe what the AI was doing. AIs in Awesomenauts contain thousands of blocks, so better debugging tools became necessary. Therefore we added the AI observer, internally known as "the F4 editor", since it is opened by pressing F4. The AI observer shows the state of the AI, and we even added a real debugger that can be used to step through AI updates and see the exact path through the AI.



The structure of the AI changed as well when we adapted them for Awesomenauts. In Swords & Soldiers the AI trees where "priority trees", similar to those in Halo 2 and Spore. This means that the goal of the tree is to find one action to perform, for example "flee", "attack", "reload" or "seek cover". The top-most action that has all its conditions satisfied is always executed, and nothing else is.

Priority trees are great when an AI should do only one thing at a time, but they turned out to be way too rigid for us. In practice an AI might want to move somewhere and shoot at whatever it passes and observe the situation to make a choice later. Our designers wanted to perform more than one action per tick so badly that they ended up making all kinds of weird workarounds, so for Awesomenauts we ditched the whole concept of priority trees and instead turned it into simple if-else trees. These are not only more flexible, but also much easier to understand.



The original version of our AI editor was programmed by Ted de Vries, who did an intership at the time and later joined us as a full-time programmer (he currently works on Assassin's Creed at Ubisoft). The AI observer and debugger were also programmed by an intern: Rick de Water.

Next week I will dive into a surprisingly complex aspect of AI: path finding and navigation in a 2D platformer. While standard path finding is pretty easy and can just use A* and that's mostly it, adding platforming mechanics and different movement mechanics per class made this topic much more interesting that we had expected beforehand. Double jumps, jetpacks, kites, moving platforms: we needed something that could handle all of it.

Introducing the editors of the Ronitech

If you don't feel like reading through this entire blogpost, be sure to scroll down to the video in the middle for a demonstration!

Those who read my blog from the very beginning, might remember a blogpost that went by the illustrious title Designing Levels Without Tools. When we made Swords & Soldiers, I was the only programmer at Ronimo, so I had to resort to drastic measures to be able to develop a complete console game in one year. The result was that our designers had a rather odd level design tool: Notepad... So much has changed since then! Awesomenauts was made with a larger team over a longer period of time and in this time we managed to make top-notch tools. So today, I would like to introduce the editors of the Ronitech!



We have three in-game editors, plus an in-game AI debugger, which can step through our AI trees. The in-game editors are a Level editor, a Particle editor and an Animation editor. Next to that, we also have an AI editor and a Settings editor. The latter is not in-game, but edits can be reloaded in-game at any time, thus still allowing for interactive gameplay settings editing. Note that the animation editor is not used for actual frame-by-frame animation (our artists use After Effects for that), but for adding particles, effects, sounds and game-triggers to animations.



At Ronimo we are firm believers in iteration. We think it is impossible to make final designs of any elements beforehand. Everything needs to be tried in the actual game, and then tweaked to make it work best in the game. Of course, if you make a clone of an existing game, it is possible to design everything on paper, but if you want to do any kind of innovation, then iteration is extremely important.

For this reason, one of the core principals of our tech team is that our designers and artist must be able to tweak everything as easily and quickly as possible. Now what is easier than tweaking during gameplay? With this in mind, most of our editors were implemented inside the game, instead of externally as is common for most editors.

When an editor is opened by simply pressing F1, F2, F3 or F4 while in a game, the game pauses and the editor overlays come up. Artists and designers can switch between our editors and the gameplay at any point, and can even continue playing while in the level editor. (This is of course disabled in the released game. We almost forgot about that: the editors were turned off in release versions only one or two days before we launched the beta of Awesomenauts on Steam...)

The editors were made over the course of four years, mostly by interns. I made the core components of the in-game editors myself, but from there our interns Ted, Niels, Bart, Thijs, Eric and Rick worked on them to really turn them into a useful and rich toolset. They did a great job, and Thijs and Ted actually now work at Ronimo.

Our editors have a ton of features, including:

• Game can be played while editing
• Several artists/designers can edit the same level at the same time over the network, seeing each other's edits in real-time
• Complete undo/redo
• Everything is animateable
• Edits to animations or particles are immediately reflected during actual gameplay
• Graphics look exactly the same on all platforms, so artists can comfortably work on their PC and don't need to use the more laborious console devkits
• AI debugger

Of course, none of this is as interesting as actually seeing the editors in motion, so here is a video that demonstrates the core features:



One of the funniest features is in the editing over the network. During a six-player match of Awesomenauts in our office, our designers can open the level editor at any given time and tweak some stuff. This is great to fix a misplaced platform or something like that, but it can also be abused nicely. At one point, one of our designers got bored and started to slowly rotate the entire level while the rest was still playing in it. Chaos and hilarity ensued...

Having the editors in the game does have its downsides. Gameplay code is more complex because editor and game are so intertwined. Another issue is that everything needs to be able to be updated at any time, which makes some optimisations impossible. Building our editors this way definitely cost us some performance, but with a lot of optimisation work I did manage to get proper framerate: Awesomenauts now mostly runs on 60fps on Xbox 360 and Playstation 3, and rather old PCs can still run it fluently.

I expect some Awesomenauts players who read this will wonder why these tools are not available to them to make mods with. The main reason for this is that modding doesn't really work without a proper modding infrastructure. You need to be able to share your levels online, and play with others online. Getting this exactly right is a lot of work, because we need to take care of things like people having different versions of the same level and such. So turning our in-house tools into a functional modding toolset would be an enormous amount of work...

In future blogposts, I will dive into some of the specifics of our editors, explaining the most interesting aspects of how these tools were made and how our artists use them to make animations and such.

As you might have guessed from the text in this post, I am incredibly proud of the tools we have today. I think in the world of 2D games, few companies have better tools than this (of course, the Rayman folks probably easily beat us there...).

AI in Swords & Soldiers (part 2)

Last week I explained how we ended up with Halo 2-style behaviour trees in Swords & Soldiers, but I didn't really dive into how they actually work. So now let's have a closer look at how we worked with them.



The small AI above gives a nice example of how our AIs work. The first thing to note here, is that behaviour trees are based on priorities. It is assumed that the AI will always want to perform the top-most action and will not look any further if that action can be executed. In this case, the action at the top is shooting lightning at a Necromancer (useAbility). Necromancers create lots of skeletons, so killing them first is usually a good idea.

To make this priority system work, the action at the top must have strong requirements, for otherwise the actions below it will never be executed. In this example, this is indeed the case: lightning is only used if an enemy Necromancer is actually near, and if you have enough mana to shoot lightning.

Since the AI must also mine gold, the action below that is building workers (createUnit). In Swords & Soldiers, players cannot have more than 10 workers, so as long as the AI has less then 10 workers (unitCount), and it has enough gold (goldAmount), it will build one worker every ten seconds (timeSinceLastUnit).

Finally, whenever not shooting lightning or building workers, this AI will just pump out as many Berserkers as possible (createUnit, at the bottom).

Now the fun of this system is that these behaviour trees are quite simple to work with, so you don't need a programmer to make them. You do need a designer who is good a logical thinking, but that is something I think every designer worth his salt should be good at in the first place.

The key to make keep these trees manageable, is to have enough blocks to work with, and to hide all complexities inside these blocks. A simple example is the unitNear block. The C++ code for this block looks for all the enemy Necromancers in the level and calculates the distance to each of them, to see whether there is a Necromancer near. The complexities of finding the Necromancers and such are hidden in a C++ class, and the designer doesn't have to know anything about that.

In Swords & Soldiers, I think we did not do this very well, though: our skirmish AI is incredibly large and complex. By having more and smarter conditions and actions to work with, I think our designers could have made some trees in half the size.



An interesting side-effect of these trees, is that they are also excellent for story scripting. Swords & Soldiers often triggers little cut-scenes with dialogues and such in the middle of a level. Deciding when the trigger those, can easily be done inside the behaviour tree, since the behaviour tree already has all these actions and conditions.

Initially, I was strongly against this idea, because I wanted to keep the AI clean and not mix it with cut-scenes. I thought this would get too messy and unclear. However, our designers convinced me to do it that way anyway. In retrospect they were completely right: it is very simple to trigger and play cutscenes with this system.



Finally, let's have a short look at a big change we made to the behaviour tree system for Ronimo's Secret New Game. While working on Swords & Soldiers, we struggled with how to make an AI do several things at once. It makes sense for an AI to build units while also casting spells at the same time. Because of the priority system, doing this kind of thing gets very messy. The priority system really only works if you always want to do exactly one thing at a time.

Working around this made the AIs pretty unreadable at some points, so for Ronimo's Secret New Game, we removed the priority system altogether. Instead, we now simply have a big if-else tree. It still has conditions and actions and looks very similar, but the AI does not stop when it has found an action it can execute. This is a lot more readable and also made it easier to add else-structures. In Swords & Soldiers, we essentially only had if-then structures, while we now also have if-then-else structures.

Let me conclude by saying that we are incredibly happy with our behaviour tree system and our own editor for it, and we will keep using this for several games to come.

In the end, this also means that the actual behaviour of our AIs is scripted by our game designers. For Swords & Soldiers this was mainly Jasper, but also a lot of it by Fabian and Tom. For me as a programmer, it is great to see how designers can make all kinds of awesome things with the tools we provide. Our designers constantly surprise me with how much more they can do with those tools than I myself considered even possible! So the real credit for the great AIs in Swords & Soldiers of course goes to our designers! ^-^

AI in Swords & Soldiers (part 1)

My blog has passed the 12,500 visitors mark! Awesome! And that in just the first four months! Thank you for visiting, and I hope my posts will remain interesting enough to visit here! ^-^

Creating good AI for a strategy game is a notoriously difficult task. AI design is of course never easy, but for strategy games, the complexity of options and situations is incredibly high. I think Swords & Soldiers is the first game for which we achieved really good AI in one of our games, so I figured it would be interesting to see how we got there.



When I was studying computer science, I had high expectations of how AIs worked. I expected there would be these awesome learning and analysis algorithms, and AIs would make incredibly smart decisions. Then I finally got to an actual AI course...

It turned out that the field of AI either solves really simple problems, like chess (yes, chess is incredibly simple in comparison to a realtime strategy game, let alone in comparison to the real world!), or only offers a huge number of nice and efficient helper algorithms, like pathfinding. Real decision making in complex situations is in essence an unsolved problem and as far as I can tell, it won't be solved any time soon.

Totally disappointed, I wondered how actual game AI was made. It turned out that most game AI is completely scripted. There is nothing intelligent about it. Just long rows of if-then-else-if-then-else. To spice it up and add some variation, some randomness may be put in, but that is not worth the term artificial intelligence either. Games where an AI can really make smart decisions, which were not explicitly scripted by an AI designer, are very rare (Black & White's Decision Trees spring to mind).

So, scripting. Swords & Soldiers is no exception. The trick to scripting an AI is to simply add as many specific situations as possible, and script a smart reaction to each of them. If you can define hundreds of different situations and their reactions, then you can achieve the quality of AI that is seen in most games today.

Now the trick is to script in a smart and manageable way. For a school project I have at some point scripted AI by programming long if-then-else structures in C++, but this was terrible. It takes a long time to program and it is incredibly difficult to have a good overview of this, so it is also very difficult to keep it free of bugs.



So for Ronimo's first official game as a company (which was cancelled, by the way), we wanted to do things differently, so we put in the LUA scripting language. Adding scripting to your games is all the hype and big games like World of Warcraft contain tons of script code like this. Scripting has the benefit that you don't have to compile any more, and that a game designer can write the AI scripts.

However, I have concluded that LUA is terrible for this purpose. Scripting complex AI in LUA is just as difficult as in C++, so you basically still need a good programmer to do it. Luckily, though, one of our designers has some serious scripting skills. But you still don't have any overview of the structure of your AI, and it is a lot of work to expose all the necessary data from C++ to LUA. As our enemies became more complex, it became more and more difficult to find and fix bugs in them. So that didn't work out either.

Around the time that I was totally fed up with LUA, I discovered a great article by Bungie on how they had built a Behaviour Tree system for Halo 2. At the time, Halo 2 was well known for its great AI, which would do things like flanking the player and working together as a team.



The basic idea of behaviour trees is that you have conditions and actions. If conditions are met, then certain actions are executed. In many ways, they are just a graphical representation of an if-then-else structure.

So, we set out to build a graphical behaviour tree editor. (Note that in this case, when I say "we built", I actually mean "an intern built". ;) )



We are really happy with using behaviour trees. Our designers make the coolest things with them, and as a programmer, I don't need to be involved in everything they want to make anymore. We are using them again in our Secret New Game, even though that is a game in a totally different genre than Swords & Soldiers!

Next week, I'm going to zoom in a bit further on how those Behaviour Trees work exactly in Swords & Soldiers and how they accidentally also became our story event scripting system.

Edit: here is part 2 of this blogpost: AI in Swords & Soldiers (part 2)