Sunday, 27 July 2014

Using throttling to reduce network errors

Recently we managed to reduce the number of network errors in Awesomenauts by 10% by improving our throttling algorithm. While automatic throttling by a router is killing, smart throttling by the game itself can be a good tool to make the game work better on crappy internet connections. Today I would like to explain what throttling is and how we approached this topic.

(Note that the throttling improvements were in Awesomenauts patch 2.5.3. This post is unrelated to the bandwidth optimisations in patch 2.5.4 that are currently being tested in beta.)

The basic idea of throttling is that if you detect that an internet connection cannot handle as much as you are sending, then you start sending less. This can happen on the side of the game, or on the side of the connection itself (by the modem or router, for example). If we keep sending more than the connection can handle, then either we lose a lot of packets or, even worse, the internet connection is lost altogether, causing a network error. Throttling is intended to keep this from happening.

The basic idea may sound simple enough, but actually implementing this is a lot more difficult. There are two problems: how can we reduce bandwidth dynamically, and how can we detect whether we need to throttle?

Lets start with how to reduce bandwidth. Modems usually have an approach to this that is simple enough: they just throw away some packets. This is a very efficient way of reducing bandwidth, but completely killing to any game. If a packet with important data is dropped then it needs to be resent. We cannot do this immediately as the internet connection doesn't notify the game that a packet was dropped. The only thing we can do is just wait for the acknowledgement to come in. If after a while we still haven't received an acknowledgement, then we conclude that the packet has probably been lost and needs to be resent.

Resending based on acknowledgements is the best we can do, but it is a pretty imperfect solution: the acknowledgement might still be under way. We cannot know whether it is, so we just need to pick a duration and decide to resend if that much time has passed. If we set this duration too long, then it takes very long before the packet is resent, causing extra delay in the gameplay if the packet was really dropped. If we choose a very short resending duration, then we will probably be sending a lot of data double that had actually already arrived. This wastes a lot of bandwidth and is not an option either.

Since we cannot pick such a short resending time, we need to wait a little while before resending. This means that dropped packets arrive in the long run, but with an enormous delay. If for example the packet contained information on a player's death then he might die one second too late, which is really bad for the gameplay experience.

In other words: we never ever want the modem to throttle. We want to decide ourselves what gets thrown away, so that we can make sure that the really important packets are never dropped. If we need to throttle, then we want to at least throttle data that is less important. The problem with this is that if we could get away with sending less, then we would always do that instead of only when throttling. After all, an important goal in multiplayer programming is to use as little bandwidth as possible. This means that throttling comes with a drawback and we don't want to do it unless necessary.

In Awesomenauts we reduce bandwidth and packet count when throttling by sending less position updates. During normal gameplay Awesomenauts will send the position of a character 30 times per second. This way if a player turns around quickly, other players will know about it as soon as possible. If we send position updates less often, then we essentially add a bit of lag: we don't send the latest information as soon as we know it. We would prefer not doing that of course. However, if the alternative is that the modem is going to throttle by randomly throwing away packets that might be important, then our hand is forced and we prefer sending less position updates.

Now that we know how to throttle we get to the much more important question: when to throttle. How can we know whether we need to throttle? It is not possible to just ask an internet connection how much bandwidth it can handle. Nor do you get notifications when the connection starts dropping packets because it is too much. We therefore can never know for sure whether throttling is needed and have to deduce this somehow.

Our initial approach to this was to throttle if the ping was too high. The idea is that if a connection cannot handle the packets it needs to send, then latency will increase and we can detect this. This works fine for connections that normally have low ping: if the standard ping is 50ms and suddenly it rises to 300ms, then it is extremely likely that we are sending too much and need to throttle to keep the connection from being lost altogether.

This approach is too simplistic however: internet connections are a very complex topic and can have all kinds of properties. Some people might indeed have a fast connection and a painfully low maximum bandwidth. However, if an Australian and a European player are playing together and they both have a really good internet connection, then their ping will still be high because the distance is so large. In this case throttling won't help at all. In fact, since our throttling essentially increases lag by sending less often, throttling in this case will actually decrease the quality of the connection!

This brings us to the change we recently made in Awesomenauts patch 2.5.3. Instead of looking at ping, we now look at packet loss. Awesomenauts uses UDP packets and we have our own manual reliability system, since various parts of the game require various degrees of reliability. This means that we send and receive our own acknowledgements and thus know exactly how many packets are lost. This is a much better indicator of connection problems than ping. If a lot of packets are dropped by the connection, then apparently we need to throttle to keep from sending too much over a limited internet connection.

It doesn't end there though. I already mentioned that internet connections are a complex topic, and this new plan too is thwarted. Some internet connections are just inherently lossy. For example, maybe someone is playing on a wireless connection and has a wall in between the computer and the modem. Maybe this causes 10% of all packets to be lost, no matter how many packets are sent. I don't know whether wireless routers actually work like that, but we have definitely seen connections that always drop a percentage of the packets, no matter how few we send. Since throttling increases lag we only want to do it when it significantly improves the internet connection. If, like in this case, throttling does not reduce the number of dropped packets, then we do not want the throttle.

Ronimo programmer Maarten came up with a nice approach to solve this problem. His throttling algorithm is based on letting the game perform little experiments. If a player has high packet loss, then the game enables throttling and starts sending less. Then it measures the packet loss again. If packet loss decreased significantly, then we keep throttling. If packet loss remains roughly the same, then we stop throttling and start sending at maximum sending rate again.

The result of this approach is that we only throttle if it actually improves the internet connection. If throttling does not help, then we only throttle shortly during those experiments. These experiments take place automatically during gameplay, but are short and subtle enough that players won't actually notice this happening. If the connection is really good, then we never ever throttle: we don't even do those experiments.

The result of adding this throttling algorithm is that network errors due to losing the connection have been reduced by 10%. This is not a spectacular improvement that many players will have noticed directly, but it is definitely significant enough that we are happy with this result.

In conlusion I would like to stress that internet connections are extremely unpredictable. We have seen all kinds of weird situations: connections that are really fast but stop for a few seconds every couple of minutes, connections that send packets in groups instead of immediately, connections that have low ping but also low bandwidth capacity, and many other combinations of properties. The big lesson we have learned from this is to not make assumptions about properties of internet connections, and to assume any random weirdness can happen for anyone's internet connection. This why I like the approach with the experiments so much: instead of assuming throttling works, it just tries it.

Sunday, 20 July 2014

Evolving level art from Swords & Soldiers 1 to 2

In Swords & Soldiers 2 we are stepping up the quality of everything compared to the original. Level art is one of the areas where we are improving the game a lot. With our improved tools we can make them look a lot more detailed and varied. We also approach level art in a very different way now. Today I would like to discuss how the approaches in both games differ and why we switched to different techniques.

In the original Swords & Soldiers the levels were mostly procedurally generated. The only parts that were placed by hand were the ground itself and the small props on it, like grass and flowers. The foreground and background layers were randomly filled with objects. Since this is essentially a 1D game I simply wrote an algorithm that placed mountains (or trees, or houses) at varying distances from each other. Each layer had a bunch of different textures and settings for how densely it should be filled with objects.

There are many arguments in favour of procedurally placing objects like that, but at the time only one really mattered: we didn't have any tools to place objects by hand. I was the only full-time programmer on Swords & Soldiers 1 and I had to build all the gameplay plus the entire engine, so there was no time to create such tools. I did have a couple of interns helping with programming, but in total there was just way too little time to implement any real tools for level creation.

Levels therefore had to be created in Notepad, as I previously described in this blogpost. This worked surprisingly fast and simple for our artists and designers, but of course precise control over graphics is not possible this way.

Our artists had a limited palette of options to differentiate levels and create varied places. They made six different art sets they could use for parts of levels: desert, snow, grass, rocks, jungle and cherry blossom. They could set a gradient for the sky colour and a second gradient to modify the colour of background props. They could set the weather to rain or snow, modify the density of background props, foreground props and clouds and place smaller props on the landscape by hand.

While all of these options together may sound like a decent set of tools to create unique levels, in practice this is not the case. Levels in Swords & Soldiers 1 quickly blend together and start to look similar. One reason for this is that levels often contain more than one environment type. They might for example vary between rocks and desert. An environment type always randomly varies between all the textures it has. The result is that in only a few levels we can have seen nearly all level art in the game. In fact, the very long Berserker Run level contains all six settings and thus contains nearly all level art the game has.

Another problem is that randomly placed objects may stand in a different spot in every level, but they all feel the same. No matter at what distance the same set of mountains is positioned, it always feels like the same place. This could of course be done better with a more advanced procedural algorithm and a smarter set of textures, but in practice procedural content nearly always suffers from this.

This problem even shows in a game like Diablo III, which has high quality procedural world generation at its core. Blizzard spent enormous amounts of time on creating sophisticated algorithms and tons of art assets for random world generation, and yet when I played through Diablo III it felt like I was constantly visiting the same places. Either a place is uninteresting, with some random trees and bushes, or it is unique with some special big props. The number of unique props in Diablo III is large but not infinite, so they start to feel repetitive quickly.

I have not seen a single game with procedural worlds where the visuals did not become repetitive really quickly. In that sense I am slightly afraid for No Man's Sky: the game looks mindblowingly amazing, but I can hardly imagine they solved this problem well enough to keep planet discovery visually interesting. (I sure hope they did though, because that game looks soooooo good!)

In Swords & Soldiers 2 we therefore concluded that we did not want to use this approach anymore. We also don't need to work around a lack of tools anymore, since we now have the impressive toolset we created for Awesomenauts. All of that is at our disposal for Swords & Soldiers 2 as well.

By placing most objects by hand our artists can now create real compositions. The way trees are arranged can create forests, small clearings and green fields. This way even without additional assets it is possible to create places that feel much more real and unique than any procedural algorithm can. Of course one could add procedural rules to create such places, but there are limits to how much can be done this way, especially because every rule that creates a specific kind of place can be used only a couple of items if repetitiveness is to be avoided. With a good artist there really are no limits to how much variation and uniqueness can be created. Most of the levels in Swords & Soldiers 2 are filled with art by Ronimo artist Ralph and he is a true master at creating interesting compositions and little micro-stories through object placement.

Another big difference between Swords & Soldiers 1 and 2 is that in 2 we have much bigger props. In the original game mountains and trees were relatively small, so you always saw a lot of them. In the sequel we have scaled them much larger, so you might see only one or two really large mountains in the background, instead of dozens. This makes it all feel a lot larger, drawing the player more into the world instead of looking at funny miniatures. At the same time this makes the backgrounds look less repetitive: if you don't see ten mountains at the same time, then it is also much less obvious that several of them use the same texture.

This is strengthened by another big improvement in Swords & Soldiers 2: there are many more unique assets for specific levels. For example, one level plays in a Viking golf court and there are golf related objects everywhere. These props are not used in any of the other levels, making this level unique and memorable. This way the player will remember more specific things than in Swords & Soldiers 1, where all the levels looked quite similar. A level doesn't even need all that many unique props: since background objects are so much larger now, having one really big prop can sometimes already define a level.

Another improvement that I would like to mention today is the art style. The original game had a very simple cartoony look, while the sequel is much more detailed and painterly. Our artists went for a style reminiscent of French animation and it works beautifully. Most of the level art in Swords & Soldiers 2 is drawn by Adam Daroszewski. He worked as a freelancer for us and did an amazing job at creating a painterly and coherent look.

I have spent most of this blogpost explaining how Swords & Soldiers 2's level art is better than the original. There is however also one big downside: it is much more work to make. With the lack of proper tools and the simple style we had when we made Swords & Soldiers 1 it took very little time to decorate more levels. In part 2 everything requires much more work to do. It really shows, but it is an important trade-off to be aware of. Not having proper tools means that there are a lot of things that artists simply cannot do and this saves huge amounts of time.

Limitations like that are a very effective way of limiting the amount of time it takes to make a game. The better your tools, the bigger the risk of using them too much. We have already spent much more time making Swords & Soldiers 2 than originally planned and the game isn't even done yet. At the same time it is looking so good that spending so much time is totally worth it. I hope that when the game launches you will be as enthusiastic about it as we are! ^_^

In conclusion, I would like to say that I think procedural level generation is great for games that evolve around it, but for a designed experience having hand-made levels works much better. Levels in a game like Swords & Soldiers 2 look better when made by hand than when generated.

Sunday, 6 July 2014

Why composition is often better than inheritance

An important question in code structure is whether to make classes work together through composition or inheritance. The "has a" relationship versus the "is a" relationship. For example: a seat has a cushion and a seat is a piece of furniture. While in this example the difference is really obvious, there are in practice many cases where both could make sense. Does a character in a game have a collision box, or is it a collidable object? These are not the same, but each can be used as the main structure for collision handling (or even both together) and it is not always clear which is better. In my experience intuition often favours inheritance, but it gives so many problems that in many cases composition is better.

Let's first have a look at an example of how the same problem can often be solved in both ways. In Awesomenauts we have a separate class that handles the 'physics' of a character. This class handles things like gravity, knockback, sliding and jumping. Since a character is a physics object, it would make sense to say that Character inherits from PhysicsObject. It is also possible to say that a character has a PhysicsObject that handles its collision. Instead of has a we might also word this as uses a.

Let's see what this relation would look like in code. This is a highly simplified version, but it shows the basic concepts nicely:

class PhysicsObject
 Vector2D position;

 void updatePhysics();
 void applyKnockback(Vector2D force);
 Vector2D getPosition() const;

//Using PhysicsObject through inheritance
class CharacterInheritance: PhysicsObject
 void update()

//Using PhysicsObject through composition
class CharacterComposition
 PhysicsObject physicsObject;
 void update()
 void applyKnockback(Vector2D force)
 void getPosition() const
  return physicsObject.getPosition();

As you can see in this code, CharacterInheritance is shorter. It also feels more natural, since we don't have to write these extra accessor functions for applyKnockback and getPosition. However, after years of creating both of these kinds of structures I have learned that in a situation like this, using composition is actually more flexible, less sensitive to bugs and even more understandable than using inheritance.


Let's start with the flexibility argument. What if we want to make an enemy that consists of two blocks linked by an energy chain. This enemy does damage to anyone who touches the chain. The blocks can move separately, making for some interesting positional gameplay when fighting this enemy. The two blocks this object consists of move entirely separately and each have their own physics. Knocking back one block does not influence the other block. Yet they really are one character: they have one healthbar, one AI, one entry on the minimap and can only exist together.

With a composition structure it would be pretty straightforward to create this enemy, since we could just create a character that has several PhysicsObjects. With inheritance however we cannot make this as a single character, since we cannot inherit from PhysicsObject twice. We could probably work around this somehow and make it work with inheritance, but it quickly becomes much less simple and intuitive.

If you read this and think this is a far-fetched situation and not all that relevant, then you have probably never been in a project of significant size where gameplay was king. Game designers constantly come up with game mechanics that are exceptions to what you already programmed. Saying no to these just because your code structure cannot handle them will seriously damage your game quality, since in the end the only argument should be whether it is fun to play (okay, and maybe whether it is achievable within the scope of the project).

Just take a look at the diversity of the hundreds of upgrades in Awesomenauts and you will realise how many of those were likely exceptions to what our code could do. Our designers came up with those upgrades and the code had to make it work somehow. An important goal in game programming is flexibility: making your code in such a way that it is relatively easy to add whatever weird whim the game designers come up with today. In most cases composition is much more flexible than inheritance.


My next argument against inheritance is readability. "Readability" is always accomponied by "sensitivity to bugs", since if a programmer does not really understand how something works, then he will likely break it when working on it.

At Ronimo one of the more important rules in our coding standard is that we strive to keep the size of all classes below 500 lines of code. We don't always see ways to keep to that, but the goal is clear: keep classes relatively short so that they are easy to understand and a programmer can fit the workings of the entire class in his head.

Let's say our code has grown over time as more and more features were added to our game, and Character and PhysicsObject have both grown to 500 lines of code each. We have also added two more classes that use PhysicsObject: Pickup and Projectile. These are also 500 lines of code each.

In such a situation inheritance will usually make all of this very confusing. We might have strived to keep as much private as possible, but in the end inheritance almost always introduces a bunch of virtual and protected functions. In other words: PhysicsObject has become pretty intertwined with its three child classes Character, Pickup and Projectile. In my experience this nearly always happens: inherited classes work together to create complex behaviour and intertwine more and more over time.

By itself this might not be that much of a problem, but to really understand any of these classes we now need to know them all. If we restructure something in PhysicsObject because Projectile needs a new feature, then Character and Pickup will also be involved. To understand the entire situation, the programmer now needs to think about four different classes and fit all 2000 lines of code in her head simultaneously. In my experience this quickly becomes impossible: this is just too much code to really grasp it all at once without starting to mix things up. The result is that readability decreases and the programmer becomes more likely to introduce bugs because she overlooked something.

Of course a composition based structure does not magically fix all of this, but it does help a lot in keeping this structure simple and understandable. With composition there is no virtual or protected, so the separation between PhysicsObject on the one side and Character, Projectile and Pickup on the other is much clearer. This keeps the classes from intertwining over time and makes it easier to keep them truly separate. While they could in theory also have been kept separate with inheritance, in my experience this is too difficult to maintain, while composition enforces it. We have numerous cases in our code where an inheritance structure of classes that all grew too big is hardly understandable any more.

Diamond problem

Any discussion of inheritance versus composition is incomplete without mentioning the famous diamond problem. What happens when a class A inherits from two classes B and C that both inherit from a single parent D? A now has a D twice and chaos ensues.

There are several solutions to the diamond problem in C++. For example, you might just accept that A has double D. (Haha, double D! Ahum.) Or you might use virtual inheritance to solve it. However, both solutions cause all kinds of problems and potential bugs, so just avoiding the diamond problem altogether is highly preferable.

This problem is usually not around in the initial design of a gameplay code structure, but as features are added it might pop up occasionally. The problem is that when it does, it can often be very difficult to come up with a good solution for how to get rid of it without doing a lot of refactoring.

Nevertheless, the diamond problem has only popped up a couple of times in my 12 years of object oriented programming, so I don't think the diamond problem is a very strong argument against inheritance.

(By the way, even without the diamond problem complex multiple inheritance structures tend to get a little sleazy, as I explained in this previous blogpost about why this is not always this.)

Use inheritance, but use it less

Does all of this mean that I am against inheritance in general? Nope, absolutely not! Inheritance is very useful for a lot things, for example in polymorphism and in design patters like listeners and factories. My point is just that inheritance is not as generally useful as it might seem. There are lots of cases where inheritance may seem the cleanest solution, while in practice composition would be better. So use inheritance, but don't overuse it.

Saturday, 28 June 2014

Finding bugs through autotesting

Some bugs and issues can only be found by playing the game for ages in a single play session, or by triggering lots of random situations. As a small studio we don't have the resources to hire a ton of people to do such tests, but luckily there is a good alternative: a fun method is to hack automated controls into the game and let the game test itself. We have used this method in both Swords & Soldiers and Awesomenauts and found a bunch of issues this way.

Autotests are quite easy to build. The core idea is to let the game press random buttons automatically and leave it running for many hours. This is very simple to hack into the game. However, such a simplistic approach is also pretty ineffective: randomly pressing buttons might mean it takes ages to simply get from the menu to actual gameplay, let alone ever actually finishing any levels. It gets better if you make it a little bit smarter: increase the likelihood of pressing certain buttons, or even just automatically press the right button in certain menus to get through them quickly. With some simple modifications you can make sure the autotesting touches upon many different parts of the game.

This kind of autotesting has very specific limited purposes. There are a lot of issues you will never find this way, like if animations are not playing, texts are not displaying, or characters are glitching through walls. The autotester does not care and keeps pressing random buttons. Basically anything that needs to be seen and interpreted is difficult to find with autotesting, unless you already know what you are looking for and can add a breakpoint in the right position beforehand.

Nevertheless there are important categories of issues that can be found very well through autotesting: crashes, soft-crashes and memory leaks. A soft-crash is a situation where the game does not actually crash, but the user cannot make anything happen any more. This happens for example if the game is waiting for a certain event but the event is never actually triggered. Memory leaks are when the game forgets to clean up memory after usage, causing the amount of memory the game uses to keep rising until it crashes. Especially subtle memory leaks can take many hours before they crash and are thus often never found during normal development and playtesting.

Another category of issues that can be found very well through autotesting is networking bugs. This one is very important for Awesomenauts, which has a complex matchmaking system and features like host migration that are hard to thoroughly test. Our autotesting automatically quits and joins matches all the time, potentially triggering all kinds of timing issues in the networking. If you leave enough computers randomly joining and quitting for long enough, almost any combination of timings is likely to happen at some point.

Recently we needed this in Awesomenauts. After we launched patch 2.5 a couple of users had reported a rare crash. We couldn't reproduce the crash, but did hear that in at least one case the connection was very laggy. Patch 2.5 added Skree, a character that uses several new gameplay features (most notably chain lightning and spawnable collision blocks). This made it likely that the crash was somewhere in Skree's netcode.

We tried reproducing the crash by playing with Skree for hours and triggering all kinds of situations by hand. To experiment with different bad network situations we used the great little tool Clumsy. However, we couldn't reproduce the crash.

I really wanted to find this issue, so I reinvigorated Awesomenauts' autotesting system. We had not used that in a while, so it was not fully functional anymore and lacked some features. After some work it functioned again. I made the autotester enter and leave matches every couple of minutes. Since I didn't know whether Skree was really the issue I made the game choose him more often, but not always. I also made the autotester select a random loadout for every match and made it immediately cheat to buy all upgrades. The autotester is not likely to accidentally buy upgrades otherwise, so I needed this to have upgrades tested as well.

I ran this test on around ten computers during the soccer match Netherlands-Australia. While we beat the Australians our computers were beating this bug. Using Clumsy I gave some of those computers really high artificial packet loss, out-of-order and packet duplication.

Watching the computer press random buttons is surprisingly captivating, especially as it might leave the match at any moment. Simple things like a computer being stuck next to a low wall become exciting events: will it manage to press jump before quitting the match?

Here is a video showing a capture of four different computers running our autotest. The audio is from the bottom-left view. Note how the autotester sometimes randomly goes back to the menu, and can even randomly trigger a win (autotesters are not tactical enough to destroy the base otherwise):

And indeed, after a couple of hours already three computers had crashed! Since I had enabled full crash dumps in Windows, I could load up the debugger and see exactly what the code was doing when it was crashing.

The bug turned out to be quite nice: it required a very specific situation in combination with network packets going out of order in a specific way. When Skree dies just after he has started a chain lightning attack, the game first sends a chain lighting packet and then a character destroy packet. If these go out of order because of a really bad internet connection, the character destroy packet can arrive first. In this case the Skree has already been destroyed when his lightning packet is received. Chain lightning always happens between two characters, so the game needs both Skree and his target to create a chain lightning.

Of course we know that this kind of thing can happen when sending messages over the internet, so our code actually did check whether Skree and his target still existed. However, due to a typo it also created the chain lightning if only one of the two characters existed, instead of if they both existed. This caused the crash. Crashes are often just little typos, and in this case accidentally typing || ("OR") instead of && ("AND") caused this crash.

Once we knew where the bug was, it was really easy to fix it (the fix went live in hotfix 2.5.2). Thus the trick was not in fixing the code, but in reproducing the issue. This is a common situation in game programming and autotesting is a great tool to help reproduce and find certain types of issues.

Saturday, 14 June 2014

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.

Sunday, 1 June 2014

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.

Tuesday, 6 May 2014

Proun cloning controversy: why indies should complain less about clones

My game Proun was recently 'cloned' by an iOS game called Unpossible. Unpossible isn't the first 'clone' of Proun: games like Synesthetic and Polyrider also copy the core gameplay and many obstacle shapes. Polyrider even goes so far as to copy-paste my main marketing text (DOH!). However, the timing of Unpossible is much more painful as Proun itself is also finally coming to iOS (and Android and 3DS): together with Engine Software I am working on a bigger and better Proun+. Proun+ coming to iOS means that it will be a direct competitor of its alleged clone Unpossible. I saw quite a bit of controversy online about whether Unpossible is a clone or not and whether that would be bad or not, so here is my own take on the matter.

I think most people are worrying way too much about most clones. The only clones that should be considered a big problem are direct rips that add nothing and are clearly only intended as a moneygrab. Most infamous clones are not of this type and indie developers should complain less and instead spend that time making more and better games.

One aspect that seems completely absent from how indie developers react to clones is pride. Usually your game will only be cloned if you make something very good and different from what already exists. Somehow most indies seem to only notice the negative and don't realise what a fantastic compliment being cloned really is. One of the things I am most proud of in my game development career so far is that Swords & Soldiers and Proun have both been 'cloned' many times and that De Blob has directly inspired other games. Indies should focus more on this positive side of cloning!

I think there are three types of clones:

-The "Asset Ripper" is the worst. These are clones that not just copy game mechanics, but even go so far as to rip assets directly from a game. Graphics, sounds, animations: they are just copied directly. We have actually encountered these ourselves once: a Swords & Soldiers clone had used some of our sound effects in their game. However, this was a small Flash game that was played by hardly anyone so we ignored it and didn't take any action. The "Asset Ripper" is the only type of clone that is definitely illegal, since it violates copyright laws.

-The "Art Replacer" is the next step: practically all game mechanics are copied directly and the only things that are changed are the visuals and audio. This is still clearly a clone, but we are already entering a grey area here. If the visuals are changed from a happy fairytale to gritty sci-fi, then the feel of the game itself also changes a lot. It is still lame to copy mechanics directly like that, but this isn't a complete clone anymore and might cater to a different audience. A famous example in this category is Yeti Town, which ripped Triple Town. They switched to a different setting, but the happy feel remained the same. Add that to a literal copying of every game mechanic and rule in Triple Town and it becomes extremely lame.

-Finally there's the "Mild Changer". This is the category Unpossible belongs to, as do famous 'clones' like Ninja Fishing. Mild Changers have a lot of similarities to another game, but add not just their own visuals: they also change the gameplay in some small ways. The core game keeps feeling the same, which is why people cry 'foul' so often for these kinds of games, but they do change things and thus create something new.

Unpossible is a clear example of this latter group. At first glance this game seems to play exactly like Proun, but it does change some things. The camera goes from third person to first person. This doesn't really make the game feel very different, but it is a real change nevertheless. The cable is thicker in Unpossible, so it is more difficult to see what is coming around bends and what is at the other side of the cable. And most importantly: in Unpossible the game immediately restarts when you hit something, while in Proun you can keep racing. This changes the game quite a bit.

I think developers should complain much less about such "Mild Changers". Genres evolve by copying from existing games and improving and adding to that. This is how we as an industry grow and discover new places. Truly new things are hardly ever made without grabbing lots of elements from existing things, in games as in most other subjects. Classic RTS Dune II lacked group control and regrowing fog of war. It is a good thing that other games 'cloned' Dune II and added these crucial elements, bringing the genre forward. A clone that is significantly better than the original is a great evolution and should not be frowned upon. (Not that I feel Unpossible is significantly better than Proun, but it still is an evolution.)

Strangely, if a game is part of a genre with lots of existing games, it is considered okay to only change some small things. But if a type of game has so few games that it can hardly be called a genre yet, then suddenly it is cloning and considered problematic. It seems like the general public thinks 'clones' are a problem if few games do it, but if lots of games all do it for years, then we call it a 'genre' and it is okay.

An interesting question in such cases is whether the developer of a clone knew the original at all. On the Touch Arcade forums Acceleroto claims to not have know Proun until Unpossible was already playable: "I didn't know about Proun until I shared an Unpossible build with some dev friends." My first inclination is to believe him: when I started working on Proun I also didn't know about F-Zero's Cylinder Wave track. (In case anyone is wondering about 2009's Boost 3D: Proun's first versions are way older than that, as can be seen in this forumpost from 2006.) Despite Acceleroto claiming to not have known Proun, when I actually played Unpossible I started to strongly doubt that. The similarities in types of obstacles and game feel are so incredibly strong that I really doubt whether Acceleroto really didn't play Proun until most of Unpossible was designed, especially considering how 'original' his other games are.

At Ronimo we are currently developing Swords & Soldiers II. Do I worry about the many similar games and even clones out there? No, I don't. We are trying to make Swords & Soldiers II better and more fun than the others. If we succeed at that, then the clones won't hurt us. If we don't succeed at that, then we should have made a better game and have only ourselves to blame. Ridiculous Fishing is a great example of this: Vlambeer made their sequel to Radical Fishing so incredibly good that it became a gigantic hit despite so-called 'clone' Ninja Fishing launching much earlier.

Another part of handling clones is that indies should simply make better business decisions. Unpossible will compete with Proun+ on iOS, but this is entirely my own fault: Proun has been out for three years now so I should have jumped on iOS ages ago. Had I done that, then Proun+ would have released well before Unpossible and the whole issue would not exist. This is a situation that often arises around clones: the original developer is very slow at bringing his game to other platforms and when he finally does, he complains that clones have sprouted in the meanwhile. This is especially important with games that are simple to build, like Proun. Ronimo's Awesomenauts and my own Cello Fortress are technically so complex that clones are much less likely to come quickly, if at all.

Before we learned of Unpossible we were already adding more variation and originality to Proun+ by introducing new game modes, more music and new visual styles. Seeing Unpossible can only strengthen our resolve to make the best game we can. If we fail at making a better game, then that is entirely our own fault. If we succeed, then I doubt the existence of so-called 'clones' will be all that relevant to sales of Proun+.