Working with generic room-based matchmaking

When creating matchmaking for a game you can either build it all yourself, or use a generic system provided by the platform you're releasing on. Steam, Microsoft, Sony and Nintendo all offer similar room-based systems. The basic idea is that clients can create, search for and join game rooms, and the actual decision which room to join is entirely made by the client. There's very little actual logic happening in those matchmaking servers. Today I would like to discuss how they work and what benefits and limitations they come with.

As far as I know most smallish games build their matchmaking using these generic room-based systems. The big triple-A developers seem to usually build everything themselves from scratch, but that's too much work and too much server maintenance to be feasible for most smaller developers.

Our own game Awesomenauts initially launched using these basic room-based systems. We didn't develop our own matchmaking system Galactron until years later when we concluded that the requirements for a genre as demanding as a competitive MOBA don't sit well with the limitations of such generic room-based systems.



The specifics of the systems that Steam, Microsoft, Sony and Nintendo offer aren't public and thus can't be discussed here, so I'm not going into any detail on how they each differ from the generic ideas described here. However, they share enough that I feel this post is very relevant if you ever make matchmaking for any of these platforms, or another platform that's built on similar ideas.

The basic concept is that the platform holder runs servers that handle rooms. A room usually represents a single match with a bunch of players in it. For example, in Awesomenauts a room would have the 1 to 6 players in it that are playing together in a match. If a player wants to join a match then the game will ask the server for a list of all rooms that have a spot left for at least one more player. The game then chooses which room is the best fit and requests the server to join it. Upon joining the game receives a list of the other players in that match and can make a connection with them and start playing.

It's important to realise that the room doesn't actually run the game. It's not a gameplay server. Usually one of the players is the gameplay server. All that the room does is keep a list of who's in the match and allow players to search for matches to join. The room is only intended for finding and maintaining lists of matches and can do very little else.

Since the room doesn't handle the actual gameplay it can often be closed once the match has started and the players are connected. Only if you support drop-in do you really need to keep a room up once the match has already started. Whether closing the room once the match has started is actually how it works depends on the platform though.

The server that handles the room can do some basic logic, but generally not much. One of the most important things it does is limit how many people can be in the room. You usually set a limit and if two players try to join at the same time while there's only space for one, then the server will make sure only one actually succeeds. This solves one of the more hairy race conditions around matchmaking.

Rooms aren't just usable for matches: you can also use them for some other things. A simple example is a chatroom. This is simply a room that players use to exchange chat messages, for example if you have global chat somewhere in your game's menus. Whether rooms scale to large numbers of players for a true global chat varies per platform. This case also shows another use of rooms: often it's possible to send messages to other players in the same room through the rooms server, without actually connecting to other players.

Also, if the client is in a room it will get notifications of changes to the room and of messages being sent through the room. You shouldn't expect rooms to be able to handle high numbers of messages or send them quickly, but something like a chatroom where lag isn't really an issue might be suitable, depending on the platform.

A more common use of rooms outside gamerooms and chatrooms is setting up a party to play with: this is also usually a room. This kind of room starts out with just one player in it, and if that player invites friends to play together then they join her party. The party leader then does matchmaking to find a room with enough free spots for the entire party.



Joining a gameroom with a partyroom of several people is often a hairy thing to develop. If the platform holder didn't supply anything for this particular situation then there are a lot of things that can go wrong that you need to solve. For example, what if a party of 3 players starts joining a room that has 3 empty spots, but by the time two of the players in the party have joined someone from outside also joins that room, taking up the final spot? In that case you need to roll back the joining for the two players who already joined and go back to searching. The number of edge-cases that might occur here is pretty horrible and is just one example of why developing an online multiplayer game is so much more work than developing a single player game. (For some more reasons check this blogpost on why adding multiplayer makes game coding twice as much work.)

Another interesting challenge when using generic room-based matchmaking is what supposedly happened to one of the Gears of Wars games at launch. Rumour has it that their matchmaking broke down because lots of clients all decided that the same room was the best one to join. Only a few got in before it was full, and then the remaining players all tried joining the same next room. Since each time most would fail it often took so many tries to actually get into a room that the matchmaking took forever. This particular situation is difficult to test without a large playerbase and definitely something to consider during development.

Rooms allow for additional data to be stored in the room. This data can be used in any way the developer sees fit and will probably contain information on the game mode, the skill of the players in the match and the map on which the match takes place. This way when a player is searching for a specific game mode the game can look through the list of rooms for one that's the desired game mode. This also allows the game to check whether the other players in the room are at a similar skill level as the player. Rooms can hold arbitrary data as the developer sees fit, but they generally don't allow for a large amount of data, so only the essential stuff is stored here.

While it's often relatively easy and quick to use the matchmaking systems that platform holders provide, there are some downsides to this approach. One of the most important ones is that if you make a multiplatform game then you'll need to build this again for each platform. If you're doing simultaneous launch on 3 platforms then this is going to take a serious amount of programming work.

You might think you can reuse a lot of your code since the basic ideas behind these rooms are so similar, but in our experience the platforms have just enough differences that this approach quickly becomes a horror story. The old version of the Awesomenauts matchmaker supports 5 platforms: Steam, X1, X360, PS4 and PS3. We tried to abstract away the platform-specific details as much as possible, but adding code for all the weird edge cases each platform introduces has turned our old matchmaking codebase into one big tangled mess where any change might break any of the platforms. Designing a good architecture for handling the differences between these systems is a tough challenge, especially if you're doing it for the first time.



Note that the room systems on various platforms also can't connect to each other. So if you want to do cross-platform multiplayer then you basically need to write your own matchmaking servers.

Another problem of using these generic room systems is that they allow for very little server-side logic to be run. This is a huge limitation on how well you can match players. This is also the main reason we redid the entire Awesomenauts matchmaking code and built our own, called Galactron. This launched in 2016. The limitations on matchmaking imposed by a lack of server logic is a big enough topic that I'll write a separate blogpost about that soon.

The generic room-based matchmaking systems that platform holders provide make developing matchmaking a lot easier than without. They save you all the hassle of developing and maintaining your own servers, so unless you're doing a large production, chances are they are the best option to efficiently develop the matchmaking for your game.

Why adding multiplayer makes game coding twice as much work

Most gamers and reviewers these days expect almost any game to have online multiplayer. What they might not realise (or not care about), is that adding online multiplayer makes a game twice as much work to program. Most programmers who build this for the first time hugely underestimate how much work it really is. For those who have never made an online multiplayer game, here are some of the reasons why it doubles the programming effort needed.

Before I start, of course note that the real complexity of building multiplayer depends on the game. Adding a multiplayer match-3 minigame to Mass Effect probably wouldn't be much work compared to the main game, but that isn't realistic: big, complex games usually also have big, complex multiplayer features. Roughly doubling the time it takes to program a game when multiplayer is added is in most cases a good guideline.



Latency
The basic cause of all multiplayer complexities, is that it takes time for a message to travel from one computer to another. This might take anywhere between a few milliseconds and a few seconds. Whenever you need to know something about another player, you always have to take into account that you don't know when the answer will come. To make things worse, it's impossible to know exactly how long any specific messages takes and latency might vary wildly between packets.

Gameplay synchronisation
All players need to have the same view of the game world. When things happen on one computer, packets need to be sent to make sure all computers know about it. This adds a lot of complexity to an otherwise simple game, because the game suddenly needs to be able to put all the information about the game in packets and send those over the internet. And what to do if we want smooth animations while some packets take way longer to travel over the internet than other packets?

Waiting
In a normal game, when you want to start a match, you just do so. In a multiplayer game, computers first need to talk about that to make sure all computers go into the game together. Since sending messages takes time, you need to wait for answers to come back. But what if a message takes longer than expected? Is it indeed coming later and should we just wait, or was the other computer suddenly turned off and is the reply never coming? Basically, any communication you do needs a timer to keep track of how long you are waiting and to cancel communications if the answer takes too long. And, also important: you need to handle if the message unexpectedly comes in after you decided to continue and not wait for it any more!

Gameplay balancing
All the other topics in this list are about tech, but of course game design for a multiplayer game is also really complex, especially in the balancing department. Our game Awesomenauts now features 22 characters and a thousand upgrades, and more are underway. What if some very specific combination of characters and upgrades is way too powerful?

Even with thousands of hours of balance testing you can still be certain further balance issues will be found once your game launches. Even Blizzard, with their extensive beta periods, never manages to get balance completely right at launch. If your game involves any kind of balance, then be prepared to spend ages getting it right, and more ages to improve it after launch.

Bandwidth
Modern internet connections can handle lots of data, but not everyone has such fast internet, so any commercial game needs to be able to run on low bandwidth. Most games seem to settle for something around 10 to 20 kilobytes per second as the minimum bandwidth required to play the game. Awesomenauts is no exception. Updating dozens of characters lots of times per second without using way more bandwidth than that requires some really smart optimisation tricks.

Scalability
If your game uses any kind of servers, then those better be prepared for any number of players. What happens if all of a sudden a thousand players all try to join matchmaking? Writing scalable server code is incredibly difficult. Testing it is a challenge since you can't easily get thousands of people to run your game simultaneously, especially before launch.

With Awesomenauts we once had a free week in which the concurrent player count went from 1,000 to over 12,000 within 24 hours. If your netcode and servers can't handle success, then you won't have it. One workaround for this problem is to not have servers of your own at all: Awesomenauts launched using only the services that Sony/Microsoft/Valve provide. Since those are scalable, so was Awesomenauts. I expect that if it had been 100,000 instead of 12,000 it would still have worked, simply because Valve's system are used to much more. Still, we spent a lot of time before launch analysing and testing our code to make sure it really was as scalable as we thought.



Invites
One particular topic that may seem like a detail, but turns out to be horrible, is inviting people. On modern platforms like Xbox, Playstation and Steam players can invite their friends to play with them. The complexity here is that these platforms allow players to accept invites from basically anywhere. Not just while in the menu or while playing another match, but also during a loading screen, during the intro cinematic, from outside the game or even while joining a game based on an earlier invite!

To give a nice example of something that could happen on the Xbox 360: while a player is in the loading screen, another player on the same console might pick up the second controller, log in with another account, and accept an invitation to play with someone online. Now the first player's match should quit as soon as the loading screen ends, the second player should become the Active Player and should join his match. This particular situation is really cumbersome to handle, and it becomes way worse when you realise there is an enormous amount of similarly weird combinations of events and they all need to be handled correctly.

Console requirements
Which leads me to the final topic here. Modern consoles have long lists of requirements that games need to abide by to be allowed to launch, and this list gets a lot longer if your game has online multiplayer. If any of the weird combinations above goes wrong in the game then Sony, Microsoft or Nintendo might refuse to release it until it's fixed. Of course, console manufacturers are right to demand quality for all the games that launch on them, but it does take a lot of extra work to build.

Debugging
Just starting the game to test your code isn't good enough for an online multiplayer game. Instead, you need to start several instances of the game, make them connect to each other, and then test whatever you just programmed. Also, the number of possible combinations of events explodes in online multiplayer situations, so not only does testing become much more cumbersome, it also requires many more tests.

I could easily have added dozens of other items to this list, but I think you already get a clear picture of how complex creating a multiplayer game really is. Many programmers think they can add online multiplayer to their game in just a month or two, but for a game of significant size it generally takes way longer than that, especially the first time you do it!

Our experience with crowdsourcing translations

When we developed Awesomenauts for console, we had the benefit of working with a publisher that helped us with QA (Quality Assurance, also known as testing) and translations. However, on PC we have self-published Awesomenauts, and that means that we had to take care of these things ourselves. Being low on budget and time, we decided to take the more radical route: we crowdsourced large parts of both.

For those who don't know the term: crowdsourcing means asking the public to help you, outsourcing to the crowd. So we did a beta where people could play the game before launch, and tell us if they found any bugs. And we asked players to help us translate all the new texts to German, Italian, Spanish and French. Since crowdsourcing is such a hot topic these days, I figured it would be interesting to share our experience with the translations.

At first, I was quite reluctant about letting players do translations. Despite our budgetary problems a few months ago, I was in favour of paying a translation company to do it, thinking that would be faster, more reliable and better quality. However, my colleagues wanted to give crowdsourcing a try, and so we did. And know what? Crowdsourcing turned out great, way better than even the biggest optimist at Ronimo had expected!

To find translators, we opened up an email-address for players to sign up for translating to a specific language. We promoted this on our Facebook, Twitter and forum. Within a week, we got several dozen reactions, meaning we had enough translators to have backup if someone bailed out at the last moment. It was also enough to have them double-check each other's texts.

Since we had some new and (at the time) secret features (like the new character Gnaw that is coming this week), we asked each of the translators to sign a short NDA (Non-Disclosure Agreement). An NDA is a small contract that simply states that any secrets we share are to be kept secret. I generally dislike the formality of putting everything under contract, but for something like this it is nice to make it very clear to the testers that we really don't want any unreleased information to leak. For an indie studio, the most important marketing tool there is, is which information is revealed when. So keeping that under control is very important for us.

Once that was taken care of, we simply put our spreadsheet with texts on Google Docs and gave them access. From there, the magic happened... I was absolutely baffled to hear that the very next day, everything had already been translated. No commercial translation company we previously worked with ever worked that fast! And they took their job very seriously: in the following days, they checked each other's work (marking what had and what had not been checked), and extensively discussed how to translate some of the genre-specific words. They even made some improvements to the existing console translations!



Awesomenauts has been out for over two weeks now, and we have not heard any complaints about bad translations. So despite that I don't speak Italian and thus cannot check the Italian translations to see whether they are any good, I think I can conclude that the translators did a great job. Players are quick enough to complain about any other issues in the game, so if they didn't complain about this, then it must have been good enough! ^_^

Another benefit of how this turned out is that if we have any new texts, we can just send them to the translators and they usually have new translations for us within a day. Compared to the formal requests for new translations that we had to do to commercial translation companies in the past, and the time it took for those to come back in all languages (usually one to two weeks), crowdsourcing is just incredibly easy and fast!

Of course, we also wanted to give something back to our translators, so we gave all of them a free copy of the game on Steam. More importantly, we also gave them a special icon in the game: the Golden Duck! (This may sound silly, but I think it is important to officially honour people who help us, and what in the world is cooler than a Golden Duck?!?!)



This blogpost so far obviously suggests that crowdsourcing is a great idea. I think it is, and I wonder: wouldn't it be possible to take this a lot further? Why not let players design puzzles for a puzzle game, for example? Looking at how much user-generated-content has been made for games like Portal 2 and Little Big Planet, I think a lot of players would be honoured to contribute a couple of puzzles to a game! Why not ask users to design puzzles before release and include them in the game? In a sense, this might feel like abusing their time, so maybe some kind of compensation would have to be figured out for that. But then again, I think if they got a chance to contribute to a game they love, lots of players would feel honoured, not abused! Making games is one of the most fun jobs in the world, and quite a few gamers would love to be a bit closer to that by contributing to an actual game.

After all this jubilant talk about crowdsourcing, it is time to mention some of the downsides. For one, I think rallying players becomes a lot more difficult if you don't have an existing playerbase yet. Quite a few people already knew Ronimo from Swords & Soldiers and De Blob, and we already had a ton of Awesomenauts players on console. I guess for your first game, it is a lot more difficult to find enough translators who are willing to really help you.

Another problem is that on console, there are a lot of certification requirements. Console manufacturers think it is necessary to define whether a button is pressed or clicked, and if you use the wrong word, your game might fail certification. (This example is not made up, one of the current consoles actually has this exact requirement...!) Working with players is a risk for these kinds of requirements, since they might not know about them. Professional translators know all the certification rules (or at least, they should...).

There is also the risk of a malicious person putting in weird texts. This happened to Minecraft, where an official release contained a racial slur in the translation to Afrikaans. Having translators double-check each other's work helps against this, but it is always a risk that someone changes a text at the last minute and this kind of horror ends up in an official release...



Despite these potential downsides, crowdsourcing has so many benefits, that I feel it is a great idea. It turned out that it is not just cheap for the developer, but also incredibly fast and a fun way to interact with the community and have them add something of their own to the game.

To conclude, we would like to thank our community translators for their great help and support!

Optimisation lessons learned (part 3)

To finish my little series on CPU optimisation (here were part 1 and part 2, today I bring out the big guns: threading and timing! This is where optimisation really shines as a form of pure entertainment and delight. I can honestly hardly imagine why anyone ever does Sudokus or crosswords. Puzzling to find the best optimisations is so much more fun!



Hiccups are horrible without the right tools

Framerate hiccups are a special case. This is when the game is running at a high enough framerate, but once in a while a single frame takes a lot longer. Hiccups cause that a game running at 55fps might look a lot less fluent than one running at 30fps, if every second the 55fps consists of 54 smooth frames and one really long one.

The difficulty here is that when you gather performance data, the time spent in each function will usually be averaged. This means that if a function runs really fast most of the time and is really slow only once per second, then it will look like a normal function in a profiler. So to fix hiccups, you will need an overview of all the frames captured, and the option to analyse them individually. Not all profilers are capable of doing this, but if you have one that does (like the excellent Playstation 3 profiler), then finding the cause of hiccups isn't all that difficult.

The important thing here is the realisation that preventing hiccups is at least as important for having a smooth feel to the game as having a high framerate, so you really need to make sure hiccups are rare enough. In the Awesomenauts Beta that is currently running, the most important hiccups are when new players join (both when they enter character select and when they enter the actual game). We are working on decreasing those hiccups, but the good thing here is that they only happen once every few minutes. Beware of hiccups that happen once every second!

CPU time versus real time

This is an oddity in some profilers that caused me to make some seriously wrong judgements on where performance was going. An extreme example is the following. I was calling SDL_GL_SwapBuffers, which finishes rendering a frame and shows it on the screen. According to my profiler, 0% of the time was spent there, so I concluded I didn't have to worry about it. This was totally wrong. It turned out that the profiler measured actual time spent using the CPU, so when a function simply waits or sleeps, then this profiler would not count that. When I discovered this, I quickly learned that SDL_GL_SwapBuffers was actually using 50% of the time in my game. This function was waiting for the videocard to finish rendering, and the solution was to massively decrease the overdraw. (Note that the videocard usually does not wait for the last frame to finish, but an earlier one, as I explained in this previous blogpost.)

So be aware that sometimes profilers show the time spent using the CPU, and sometimes they show the actual time on the clock that it took for a function to finish. Keep this in mind!

Multi-threading makes everything very complex

This also brings us to the one thing that makes optimisation truly complex: multi-threading. Again, this is best explained through an example. The Ronitech (our 2D multi-platform game engine) has two main threads running: the rendering thread and the game thread. At the end of every frame, these threads wait for each other to finish. The threads never take exactly the same amount of time, so in practice one thread waits a bit every frame. This means that on a multi-core processor, optimising the fastest thread does not increase the framerate at all.

So before optimising a multi-threaded game, you should always get a clear view of who is waiting where and for what, and then you should only optimise the things that cause the waiting.



Luckily, modern consoles are so fast that for smaller games, you often won't need a lot of multi-threading. Everything relevant in Swords & Soldiers was done in just one thread. Awesomenauts is a lot larger and more complex, though, so we now have three threads running at all times. In general, unless you are making something relatively big and are in a larger coding team (Ronimo currently has five programmers), you won't need a lot of threading and can thus skip this kind of complexity.

Which brings us to the end of this series of the most interesting lessons I learned while doing optimisation! For posts somewhere in the future I still have two more optimisation topics that I would like to discuss: one with practical examples of (simple) optimisations that worked well for me, and the other with a detailed look at our memory manager, which turned out to improve the framerate a lot without being very complex to make. For now, I hope this was an interesting wall of text about the sensual joys of optimisation!

Optimisation lessons learned (part 2)

Last week I talked about some rather general things that I learned about CPU optimisation, when spending a lot of time improving the framerates of Awesomenauts, Swords & Soldiers, and even Proun. Today I would like to discuss some more practical examples of what kind of optimisations are to be expected.

Somehow I like talking about optimisation so much that I couldn't fit it all in today's blogpost, so topics around threading and timing will follow next week. Anyway, forward with today's "lessons learned"!

Giant improvements are possible (at first)

The key point of my previous blogpost was that you should not worry too much about optimisation early in the project. A fun side-effect of not caring about performance during 'normal' development, is that you are bound to waste a lot of framerate in really obvious ways. So once you fire up the profiler for the first time on a big project, there will always be a couple of huge issues that give giant framerate improvement with very little work.

For example, adding a memory manager to Swords & Soldiers instantly brought the framerate from 10fps to 60fps. That is an extreme example of course, and it only worked this strongly on the Wii (apparently the Wii's default memory manager is really slow compared to other platforms). Still, during the first optimisation rounds, there is bound to always be some low-hanging fruit, ready to be plucked.

The real challenge starts when all the easy optimisations have been done and you still need to find serious framerate improvements. The more you have already done, the more difficult it becomes to do more.

Big improvements are in structure, not in details

Before I actually optimised anything, I thought optimisation would be about the details. Faster math using SIMD instructions, preventing L2 cache misses, reducing instruction counts by doing things slightly smarter, those kinds of things. In practice, it turns out that there is much more to win by simply restructuring code.

A nice example of this, is looking for all the turrets in a list of 1,000 level objects. Originally it might make most sense to just iterate over the entire list and check which objects are turrets. However, when this turns out to be done so often that it reduces framerate, it is easy enough to make an extra list with only the turrets. Sometimes I need to check all level objects, so turrets are now in both lists, and when just the turrets are needed, the longer list doesn't need to be traversed any more. Optimisations like this are really simple to do and can have a massive impact on performance.

This is also a nice example of last week's rule that "Premature optimisation is the root of all evil": having the same object in two lists is more easy to break, for example by forgetting to remove the turret from the other list when it is destroyed. In fact, the rare bug with purple screens that sometimes happens in Awesomenauts on console recently turned out to be caused by exactly this! (Note that the situation was extremely timing specific: this only happened when host migration had happened just before a match was won.)

In my experience, it is quite rare to find optimisations that don't make code at least a little bit more complex and more difficult to maintain.

Platforms have wildly different performance characteristics

This is quite a funny one. I thought running the same game on different platforms would have roughly the same performance characteristics. However, this turned out to not be the case. I already mentioned that the default memory manager is way slower on the Wii than on any of the other platforms I worked with, making implementing my own memory manager more useful there than elsewhere. Similarly, the copying phase of my multi-threading structure (which I previously discussed here) takes a significant amount of time on the Playstation 3, but is hardly measurable when I run the exact same code on a PC.

So far I have seen that all the optimisations I have done have improved the framerate on different platforms with wildly differing amounts. They did always improve the performance on all platforms at least a bit, just not with the same amounts. So I think it is really important to try to always profile on the platform that actually has the worst performance problems, so that you can focus on the most important issues.

Truly low-level optimisations are horribly difficult

The final lesson that I would like to share today is actually a negative one, and cause for a little bit of shame on my side. I have tried at several occasions, but I have hardly ever been able to achieve measurable framerate improvements with low-level optimisations.

I have read a lot of articles and tutorials about this for various platforms. I tried all kinds of things. To avoid cache misses, I have tried using intrinsics to tell the CPU which memory I would need a little bit later. I have tried avoiding virtual function calls. I have tried several other similar low-level optimisations that are supposedly really useful, but somehow I have never been able to improve the framerate this way. The only measurable result I ever got this way was a 1% improvement by making a set of functions available for inlining (the Playstation 3 compiler does not have Whole Program Optimisation to do this automatically in more complex cases).

Of course, this definitely does not mean that low-level optimisations are impossible, it just means that I consider them a lot more complex to get results with. This also means that it is possible to make a larger project like Awesomenauts run well enough without any low-level optimisations.

We've got a big announcement coming up next week, and next weekend I will be back with the last part of my mini-series on optimisation. Stay tuned!

(Muhaha, are you curious what we are going to announce? Feel free to speculate in the comments!)

Optimisation lessons learned (part 1)

Optimisation is a very special art form, with lots of tricks and realisations that give it a place of its own in the programmers toolbox. Until I had to do it for the first time on Swords & Soldiers for the Wii, I had never done any optimisation. At university I had already learned a lot about time complexity (big O notation, like O(n)), but optimising an actual game with a big codebase is a different beast entirely. I was like a virgin that had never been seduced by a handsome profiler yet.

I just started fooling around with optimisations, reading tutorials and articles on Nintendo's dev website and the internet in general, and learning as I went along. Since no pro ever taught me how to optimise, I guess I might still be unaware of some really important tricks. Yet somehow I managed to get Swords & Soldiers from an initial 10fps to 100fps on the Wii (if VSync is turned off), and Awesomenauts from 10fps to 70fps on the Playstation 3.

In past five years I spent some six months in total on several kinds of optimisation. Quite a lot of that was on bandwidth optimisations, but also a lot on framerate and loading-times optimisations, so I have quite a bit of experience with it by now. There is a lot of interesting stuff to say about it, so in the coming weeks I would like to share the most important lessons that I learned. Today's concepts are rather general, next week I will share some more detailed pieces of (hopefully) 'wisdom'. ^_^

Don't make any assumptions
This is by far the most important one. When I want to optimise something, I always have a some ideas in my head about which parts of the game must be causing the low framerates. In practice, however, it turns out that I am hardly ever right. When I fire up a profiler and analyse where time is really spent, the big optimisations almost always turn out to be somewhere else than expected. This is still the case, even though in the past five years I have spent so much time full-time on optimisation (especially Awesomenauts was a really complex beast to tame), optimising code for Wii, PS3, Xbox360 and PC. So much experience, yet my expectations are still usually wrong.

So the rule I derive from this, is to never take any action based on assumptions. Always let go of your assumptions. Take real measurements and work from there. And once something has been changed, measure again to see whether it really works. As Dutch physics teachers often say: "Meten is weten" ("Measuring is knowing").

Profilers are awesome
Which brings me to the best part: profilers (measuring tools) are awesome! They give insane amounts of detail on all kinds of things. The core for me is the hierarchical view. This starts in your main() function and tells you it is using 100% of the time (oh really...). From there you can keep opening function calls in a tree-like form, to see in ever more detail where the time is spent. Beyond this, profilers have all kinds of nifty tools. If you ever want to do any optimisation, be sure to start by getting a proper profiler!



I have to say, though, that I have not been able to find a really good, affordable profiler for PC. Wii, PS3 and Xbox360 all have excellent profilers that only work on that platform, but on PC, most profilers I have seen are either incredibly expensive (like the one in Visual Studio Team Edition), or lack the concept of a "frame" and thus don't allow me to find framerate hickups. The best one for PC I have seen so far is Very Sleepy, even though it completely destroys the framerate while running and doesn't know what a frame is either. But Very Sleepy is easy to use and the hierarchical tree-view is really clear. So if anyone has any recommendations for a better profiler for optimising games that are written in C++, then please let me know!

Premature optimisation is the root of all evil
I already mentioned that you should not make any assumptions, and this also leads to another important point. "Premature optimisation is the root of all evil" is a quote from the famous computer scientist Donald Knuth, and it is all too true. Most optimisations make code more complex, more difficult to maintain and evolve, and more sensitive to bugs. Also, in practice, 99% of the code is completely irrelevant to performance. A couple of hotspots take up most of the CPU's time, and the rest just doesn't occur often enough to be relevant to optimise. So my conclusion is to not really care about performance and just write the cleanest, most readable code I can. Until the profiler says otherwise.



To give a simple example from C++: sometimes using a const char* is a lot faster than an std::string. However, the latter is so much safer to use, that I never use const char* until the profiler tells me I have a problem, and then I change it in that specific spot.

Modern consoles are ridiculously fast
When you look online for optimisation tips, or when you talk to hardened industry veterans, you will learn a lot of things that I dare claim are just not relevant any more. Consoles and PCs these days are so fast, that you can just waste performance on all kinds of things and still get a good framerate. Of course, I am not talking about the big games here: if you are working on the next Uncharted and need to squeeze every last bit of power out of the Playstation 3, then it probably becomes really important to look after every little performance detail, but in general: modern consoles are so fast that you can waste most of your processor time on inefficient code and still easily get a good framerate.

To give an example: a rule that some studios have is that dynamic allocations are forbidden. So calling new or malloc during gameplay is not allowed. Everything that is going to be used, must be allocated during loading, and then kept in pools for quick usage. This helps against memory fragmentation, but is also supposedly necessary to achieve a good framerate. I personally think this limits the code design way too much. It makes code more difficult to manage and extend during development, so I never do this. It turns out that even the Wii, supposedly the slowest of the current generation, can easily run 60fps with 100 characters walking around in Swords & Soldiers.

(Note that I did end up making my own memory manager to speed up allocations on the Wii, which I will discuss in a future blog post. But calling new tons of times each frame was not a problem in the end.)

My point here is not that everything is always possible, but I do think it is important to realise that unless you are making a triple-A console game, you should not worry about performance too much, definitely not early in development.



I personally find optimisation a lot of fun to do, so there is a lot more I would like to say about it. Next week I will be a bit more specific and follow this post up with some lessons that I learned about timing, threading, hiccups, and where the biggest performance improvements can be made.

An easy solution to the safe frame problem

One of the things I hated most while developing Swords & Soldiers for the Wii, was the safe frame. CRT televisions (you know, those old, big televisions that some people still have) don't show the entire screen: they simply leave out the screen's edges. I don't know exactly why this is traditionally done, but the amount of screen that is left out varies per television and can be pretty large on some of the worst TVs.



Surprisingly, many modern LCD/LED/Plasma televisions are by default set to also leave out the edges. They just zoom in a bit. However, since there is no technical reason why this is, these televisions come with a setting to turn that irritating behaviour off.

Now the good thing, is that there is a limit to how much of the edges a television actually cuts off. The area that you can be sure will be shown on every television, is called the safe frame or safe area.



Since games need to be playable on any television, Xbox, Playstation and Wii all have requirements that the game should be playable even if everything outside the safe frame is cut off. So crucial information or interface elements can not be positioned outside the safe frame. It is of course a good thing that Microsoft, Sony and Nintendo force developers to make games that are playable for everyone, but this is pretty horrible for us as developers: usually you want the interface to be as far to the sides of the screen as possible to leave lots of playing field, but that is not possible any more.



Luckily for me, our art team had to deal with this and not me. So they moved the interface elements further from the edges of the screen. Now the total screen (as is seen on televisions that don't cut off the edges), looks like this:



Note that it actually takes quite a lot of time and effort to do this correctly: in our office we have no television that has the worst possible safe frame, so instead we made a paper frame to put in front of the screen and 'emulate' the worst possible safe frame. Everything needed to be tested with this piece of paper in front of the screen.

Moving the interface away from the edges works, but it is pretty limiting for interface design, and it is also irritating work. While making Swords & Soldiers, we thought we had to do this, but right after the game was done, we discovered that some games solve this in a much easier way. So easy, that at the time it almost felt like a trick.

So, to keep you, the reader, from spending a lot of time on the safe frame, here is the simple trick that our new game Awesomenauts and some other games use instead:

Allow the user to set the zoom of the screen.



That's it. In OpenGL and DirectX, you can just create smaller viewports and leave the borders of the screen black. So on televisions that cut off a lot of pixels at the borders, you just render the game to a smaller part of the screen. Everything outside that is black. As long as the user sets this correctly (which he is forced to do when he starts the game for the first time), everything will always be shown, so you can put your interface elements wherever you like.



The only real downside this solution has, is that the resolution of the game is now pretty much dynamic. So rendering pixel-precise effects becomes a bit more difficult now. On the other hand, it also has a hidden benefit: since you render to a smaller portion of the screen, people with CRT televisions might get a better framerate...

This really is a simple trick, but for those who didn't know it yet: be glad you do now! ^_^

Making an HD 2D game look good on an SD television

Awesomenauts and Swords & Soldiers are both 2D games that have been designed for high resolution HD screens. So how do they look on old CRT televisions with their low SD resolutions? The obvious answer seems to be that they should automatically look great: the art is super crisp, because it was designed for a higher resolution. However, what you may not realise, is that too crisp is not a good thing!

The problem lies in anti-aliasing, and in graphical details. Anything that the artists have drawn that is only 1 pixel wide in HD, will start to flicker on an SD screen. This happens for the simple reason that not every pixel will be shown on an SD TV. The art has been made for 1920x1080 pixels on the screen, and only 720x576 of those will be shown on an SD television. As a character moves over the screen, his details will flicker in and out of view as they are sometimes on a pixel, and sometimes in between two pixels.



This is especially problematic for anti-aliasing: in a 2D game, anti-aliasing of edges is drawn in Photoshop and doesn't require any work from the game. But on an SD television, the pixels that make the anti-aliasing may fall in between two screen pixels, meaning that anti-aliasing is often entirely lost.



(Note that this is a problem that is specific to 2D games: in 3D mipmapping is used to solve this problem, and anti-aliasing is rendered in real-time by the videocard.)

So when we render our HD 2D graphics to an SD television, they look noisy and too crisp. Now how do we solve that?

The solution is actually pretty simple. To get an image that is both smooth and sharp in SD, we use an easy trick in both Awesomenauts and Swords & Soldiers: on SD televisions, the game is rendered at a higher resolution than what is shown on the screen, and then sampled back to the lower screen resolution. This is a standard technique in non real-time rendering and is called supersampling.

So first we render the game at a higher resolution (1080x864 instead of 720x576). Then this high resolution image is rendered to the screen by sampling the area beneath each screen pixel. For each screen pixel, I take four samples from the high resolution image and use the average of that. This way really small details are not lost. Instead, they become more subtle, since they are averaged with the pixels around them.



So what resolution do we use for the high resolution image that we sample from? Easiest would be to use twice the screen resolution, but that requires rendering at 1440x1152, which is really high and wastes a lot of performance. I experimented a bit, and it turns out that rendering at 1.5 times the resolution is already enough to get smooth graphics.

This is a good thing, because twice times the resolution does tend to become quite expensive. In fact, at some point SD TVs had a lower framerate than 720p HD TVs, which is why I started experimenting with the exact resolutions to find a better trade-off between performance and quality. At 1.5 times the resolution, the framerate is smooth again.



The results look good, and they mean that I don't have to bother with storing all textures on different resolutions for HD and SD televisions, which keeps our art pipeline simple.

This post may seem to be about a really minor detail, but on old SD televisions, this really makes a big difference. Without this technique, both Swords & Soldiers and Awesomenauts didn't look good on low resolutions.

I find it really interesting that if you want to make a quality game, you really need to worry about all kinds of seemingly small details. All those little things in coding, art, sound and design are what makes a game polished, and this post has been about just one little example of the kind of polishing we do on our games.

Next week, I expect to have something really cool to show here, so see you then! ^_^

The Bouncy Stick Problem

Awesomenauts has really fast controls: if you push the stick in a direction, your character immediately faces in that direction. Many games have smoothing animations in between, making the game look more realistic, and adding a bit more weight to the character's movement. However, this also slows down the game a bit and adds some delay to your input, since the character isn't immediately doing what you tell it to. For Awesomenauts we chose to have really quick controls and not do those in-between animations too much.



However, we discovered an interesting problem with reacting so quickly. It turned out that quite often, when a player walked to the right and then let go of the stick, he ended up facing to the left. Even though he was pressing right. Depending on the controller and the way the player handled the stick, this may never happen, or happen 30% of the times. When this happened it was quite annoying, especially when it happened in the shop: the player would accidentally buy a different item than he wanted once in a while.

So we investigated this issue and my colleague Machiel (of Paper Cakes fame) discovered what was happening: whenever you let go of the stick, it bounces back to its centre position. But the spring that causes this bounce is so strong, that the stick actually bounces beyond the centre position for a very short amount of time. This GIF animation shows what I am talking about:



Note that this doesn't only happen on the Playstation's controller: it also happens on the Xbox 360 controller.

So this explains why the player sometimes ends up looking in the wrong direction: for just one frame, the stick bounces back beyond the neutral position. Awesomenauts reacts to input so quickly, that this results in the player immediately turning around. In slower games, this would not be a problem, but in Awesomenauts, it is.

So I made some measurements on the exact output that the stick is giving each frame. In some cases when you let go of the stick, it just springs back to the neutral position. In other cases, it indeed bounces beyond that.



This doesn't always happen, though. So why is that? As you can see in the measurement, the spring back happens extremely quickly, usually within one frame. My guess is that the bounce beyond neutral actually always happens, but is so fast that it often happens in between two frames. So I can't always measure it and thus the game quite often isn't influenced by this bounce.



I tried this a lot of times, and it turns out that the stick can bounce quite extremely. When in the neutral stick position, the stick has position 0. All the way to the left is -1 and all the way to the right equals 1. Now when I let go with the stick all the way to the right (1), I have seen it bounce back to as far as -0.72 before getting back to 0. So that bounce is almost entirely to the left! This greatly depends on the controller, though: it seems like the bounce becomes worse when the controller is older, so apparently it increases with use.

The solution

So, how to solve this? The first thing that comes to mind is to increase the deadzone: ignore small stick input and hope the bounce falls within the deadzone and thus isn't used. However, since I sometimes measured a bounce of up to 0.72, I would have to increase the deadzone to almost the entire range of the stick, which means the game would only react to stick input when the stick is entirely to the right or left. Not cool.

Another solution also seemed reasonable: since the bounce happens for only one frame, an easy solution would be to ignore input that takes only one frame. However, the game cannot know this until one frame later. So to ignore single-frame input, I would have to introduce a one-frame delay in handling the player's controls. That sucks, because it takes away a little bit from the instant controls that make Awesomenauts play so well.

Now if you look at the graphs, you can see that the user never moves the stick all the way to the right in a single frame: he takes several frames to do this, even on 30fps. Users think they react instantly, but in practice they usually take around 0.1 seconds to move the stick in a certain direction. I tried this a lot and even when I tried to move the stick extremely fast, I am still only very rarely able to move the stick all the way to the right in a single frame. During normal use, this never seems to happen.

The evil bounce, however, always happens practically within a single frame. It is much faster than any real user input. So Machiel came up with a solution that uses this. I implemented his solution and it which works great:

When the change in the stick's position is bigger than 1.05, ignore it for one frame. *

This eliminates all the bounces that I have seen. And in my measurements, it practically never ignores or delays actual real player input. When the player moves from neutral to all the way to the right, that is a movement from 0 to 1. That is smaller than 1.05, and thus always used immediately. When the user moves all the way from the left to the right, so from -1 to 1, then he takes several frames for this. So the movement per frame is still less than 1.05, and is thus not ignored.

So, I implemented this, and we have not been able to reproduce the Bouncy Stick Problem in Awesomenauts ever since. Win! :)

* Edit: As Ben suggested in the comments below this post, it is probably best to use stick position 0 when the output is large, since using the previous frame adds some delay to stopping walking.

The horror that is PC development

Swords & Soldiers is now out on PC and Mac on Steam! Buy it from SwordsAndSoldiers.com and use the coupon-code "sinterklaas" before December 5th to get a 30% discount!

In the past two years I have released my first games as a programmer on the Playstation 3 and Nintendo Wii. As I was told beforehand, the most evil part of console development are the certification requirements. Sony, Nintendo and Microsoft have long lists with hundreds of demands that you must meet in order to be allowed to release your game on their platform. These are all purely technical and are about topics like: "Pause the game if the controller runs out of batteries", or: "Show this message when the harddisc is corrupted."

Going through those lists and implementing all of it is incredibly boring work and has little to do with making cool games. However, last week I learned that PC development is actually a lot worse! On consoles, at least all of the requirements make sense, and since you know exactly on what hardware your game will run (all Playstation 3s are essentially the same), it is quite easy to test for. How unlike PC development...

Last week we launched Swords & Soldiers on the PC and the amount of things that can go wrong on all these different combinations of videocards, drivers, Windows versions and user settings is just terrible. Knowing the hardware on consoles suddenly makes them seem incredibly simple to develop for!



The main culprit on PC is the videocard, so I figured it would be interesting to have a little look at the kind of issues we came across during development of various games.

One thing most graphics programmers know, is that you should use power of two (PoT) textures, so resolutions should be like 128, 256, 512, 1024 and 2048. However, this is only relevant for pretty old videocards, since all modern videocards can handle other resolutions as well. Because of our animation system, we often have to round values up, so an animation sheet of 600*512 pixels becomes 1024*512 pixels. That is a huge waste! So to save a lot of space, we don't use power of two textures in HD. Since older computers also need to run Swords & Soldiers, we added a low-res SD mode where all textures are power of two.

Now I would like to detect whether the videocard can run in HD, and then hide that setting if the videocard cannot handle non power of two textures. But how do we detect that? There are some OpenGL extensions related to it, so I tried checking for those. However, some videocards don't have these extensions, yet they can run in HD anyway. I wasn't able to find a definite way to detect this (although I guess greater minds will know one), so I ended up allowing everyone to select HD and showing a message that tells the user to play in SD if the game looks broken otherwise. Pretty lame, but at least it is a clear solution!



A weird issue I came accross while working on Proun, is that certain really old onboard Intel videocards cannot handle objects with more than 65536 vertices. This only happens on some very specific old Intel cards and is okay anywhere else. Since Proun is a hobby project and splitting meshes for this would be quite some work, I ended up not fixing this one.

One of the simpler hardware differences to work with is shader versions. Vertex and pixel shaders can have all kinds of features, depending on the videocard and the DirectX version. However, programming for these isn't that difficult, because shader versions are always backwards compatible. So if for example you would write a shader for version 2.0, then it will definitely also run on 2.x, 3.0 and 4.0. There are no weird combinations here!



However, there are those videocards who think it is okay to lie. While developing De Blob, I learned that there are videocards that claim to be able to do shader 2.0, while they really don't. So I asked that videocard, "Can you do shader 2.0?" and the videocard said: "Yeah, sure, no problem!" I then tried to load the shader, and the videocard simply refused. How is one to program for that kind of weirdness?



The final example I would like to discuss here is one that I am a bit ashamed of, because Swords & Soldiers actually launched with this issue and I had to release a patch on Steam yesterday to fix it. Swords & Soldiers has a dynamic font rendering system, which means that we only load those characters that the game actually uses into video memory. This way we can handle the enormous number of characters needed for languages like Japanese and Chinese. Now we only implemented this after we did extensive tests on all kinds of videocards and we totally forgot to test again, so it turned out about 1% of users could not see any texts in the game at all. Pretty lame.

I haven't been able to figure out why this happened on those videocards, but I do know that the OpenGL function glTexSubImage2D was the cause. So in yesterday's patch I built a workaround that doesn't use that function. For more technical details on this problem, have a look here.

So, I conclude that PC development is actually more difficult than console development!

If you have any fun or interesting examples of rare hardware/driver/OS differences that break games, then please share them by commenting beneath this post. I'd love to hear about your experiences! ^-^