Sunday 30 November 2014

Proun+ out now on iOS!

On 27 November Proun+ launched on iOS! The first reviews are extremely positive, both from the press and from users. We also got a big feature in the European App Store, so it seems like Apple itself also likes the game. :) Here are some quotes from the reviews and the launch trailer:

"A bright, searingly good twitch racer that takes the fundaments of the genre and builds something staggeringly entertaining on top of them."
9/10
PocketGamer.co.uk

"Previously a successful indie release on the PC, it deserves your attention and patience. [...] Throw in a funky jazz based soundtrack and Proun+ has a lot going for it."
4/5 stars
148Apps.com

"this self-styled “journey through modern art” exudes an endearing weirdness that sets it apart and nestles it in your brain. Like that off-beat game you used to play, that you’re convinced only you can remember, which you can’t possibly forget."
4.5/5 stars
Gamezebo.com



Proun+ is available in the App Store for iPhone and iPad for $3.99 here.

Saturday 22 November 2014

Why good matchmaking requires enormous player counts

Good matchmaking is an important part of creating an online multiplayer game. One thing you may not realise is that no matter how you build it, truly good matchmaking requires enormous numbers of players. Awesomenauts often has well over 1,000 people playing the game at the same time, which is very high and successful for an indie game. It certainly sounds like a lot to me, but this is only a fraction of what would be needed to do everything with matchmaking that we would want to do. Today I am going to explain why tens of thousands of concurrent players are needed for truly awesome matchmaking.

Matchmaking has two main goals. The first is to let people play together who will have a good internet connection to each other. We would like to avoid Australians playing together with Europeans because their ping will be very high. High ping decreases the quality of the game experience, especially in a fast and highly competitive game like Awesomenauts. Finding good connections is more complex than simply looking at distance: sometimes you have a worse connection to your neighbour than to someone on the other side of the continent. The internet is just very unpredictable and random when it comes to connection quality.

The second main goal of matchmaking is to let people play together who have similar skill. There is no fun in getting beaten by someone who is way better than you, and n00bstomping gets old really quickly as well.

Now that we know our core goals, let's try to estimate how much 1,000 concurrent players really is. I am going to simplify things and use a lot of assumptions, but I think the ballpark figures are realistic enough to communicate my point.

The first step is to look at how often these players are actually available for matchmaking. An Awesomenauts match takes on average somewhere around 20 minutes, so players are available for matchmaking once every twenty minutes:

1,000 / 20 = 50 players per minute

We don't want to matchmake with people who are too far away, and players are spread all over the globe. Let's say that the average player would have a good enough connection to one third of all players. In reality players are not spread equally, since Awesomenauts is more popular in some countries than in others, and because of time zones. Let's work with that one third though:

50 / 3 = 16.7 players per minute

Next step is skill. Let's say we consider one third of all players to be close enough in skill to make for a fun match:

16.7 / 3 = 5.6 players per minute

AUCH! We are already down from 1,000 concurrent players to only 5.6 suitable players per minute, and this is while looking at only the most basic of assumptions...

For perfect matchmaking I would want to split players further. A common request from Awesomenauts players is to have unranked and ranked multiplayer. If we would add this, the split between these modes would probably not be equal: one mode would likely get more players than the other. Let's assume one third of all players would play one mode, and two thirds would play the other mode. We need to split further from the already small numbers we have because even in unranked matchmaking we still want to match players based on similar skill to create fun matches. This is how few players we would have left in the smallest of the two modes:

5.6 / 3 = 1.9 players per minute

Another common request from the Awesomenauts community is to split pre-mades from solo-queuers. A pre-made is a group of people who form a team by hand in the lobby before the match, while solo-queuers are put together in a team with complete strangers by the matchmaker. Pre-mades potentially have a big advantage because they will likely do much better teamwork. In the ideal case pre-mades would therefore only play against other pre-mades. How many pre-mades there are varies wildly with the skill level of the players (highly skilled players generally play in pre-mades much more). Let's assume that on average one fourth of all players are in a pre-made:

1.9 / 4 = 0.46 players per minute

Since we are talking about perfect matchmaking, let's have another look at our skill-based matchmaking. Above I assumed that one third of all players is a good enough match in skill. In reality the top players are way too much better than the rest to make this ideal. The top 5% of players are an enormous amount better than the top 33% of players. The more precisely we could match based on skill, the better. I think we would need to do at least three times better than we did above for ideal matchmaking:

0.46 / 3 = 0.15 players per minute

I can imagine some more criteria for ideal matchmaking (like supporting more game modes in matchmaking), but I think the point is quite clear already. With 1,000 concurrent players it will take 30 minutes to fill a match! Obviously this is totally unacceptable. Here's a summary of all the criteria I have mentioned so far:



Let's say it is fine to let players wait for two minutes for a match to fill up, bringing us to 0.3 suitable players during the available time for matchmaking. To bring us to the required 6 we would therefore need 6 / 0.3 = 19 times as many concurrent players for good matchmaking. We started with 1,000, so we need 19,000 concurrent players. Of course there is a big daily fluctuation in the number of players (there are fewer players deep in the night and early in the morning), so to also have good matchmaking at the slow hours we would need three times more players still. Thus we would need 58,000 concurrent players at peak for good matchmaking. That probably equals over 5 million unique players each month. Holy cow that is a lot!

When building a multiplayer game it is important to think about this. Ideal matchmaking requires enormous player counts, and if your matchmaking is built assuming such player counts will be there you might make something that works really badly for more realistic numbers. Therefore the ideal matchmaking system is flexible: it brings perfect matchmaking when there are tons of players but also makes the best of a small player count.

Despite all of this we can still make big improvements to the matchmaking system in Awesomenauts. We are aware of this and are therefore rebuilding the entire matchmaking system from the ground up in a much smarter and much more flexible way than is currently in the game. I am sure this will bring a big improvement, but at the same time it is important to have realistic expectations: no matter how well we build our matchmaking, the player count required for 'perfect' matchmaking is unrealistic for all but the few most successful games in the world.

Saturday 8 November 2014

Using 2D daylight assets to create a night level

Changing the lighting in hand-drawn art is a challenge. While in 3D games you can simply modify the light, there is no such thing when using 2D assets. In our new game Swords & Soldiers II all the level assets have their lighting drawn in. Of course you can ask the artist the redraw the image with different lighting, but that costs a lot of additional time and texture memory. We managed to re-use our daylight textures to create convincing nighttime levels, so today I would like to explain the tricks used to achieve that goal.

Today's post is all about the artistry of Ronimo artist Ralph Rademakers. He uses images drawn by Adam Daroszewski* and Gijs Hermans to decorate the levels in Swords & Soldiers II. Ralph keeps surprising me with the unexpected tricks he manages to pull off with our internal tools.

*By the way, note that Adam works as a freelancer these days. He drew most of the level props in this post and you can see some more of his amazing work here.

There is basically a whole series of tricks that Ralph uses to turn day into night. I'll let the images do most of the talking today:







Even in the night a form of atmospheric perspective can be used: in the video below the smoke in the foreground is much brighter than the smoke in the background to suggest additional depth. When I built the recolouring shaders and tools I never expected them to be used on almost every object in the levels. Also, note how the stars have been made using particles to make them blink and appear in random places for a more lively look.





As a starting point Ralph usually chooses one colour multiplier for all objects in the level. He tweaks the colour per object to make it look exactly right. In the end few objects use the same colour multiplier, but they all started from the same point.





It surprises me how often these gradients are reused. From fog to lights to lens-flares and even just for hiding objects that should not be visible from certain viewpoints. The big downside of this approach is that it results in a lot of overdraw, which is also the main performance bottleneck in Awesomenauts. Good thing modern videocards are so insanely fast...





The lights in the bar below blink to make the scene more dynamic. However, blinking lights attract the eye too much while the focus should be on the gameplay. Therefore the blinking is not between on and off, but between the more subtle slightly-bright and extra-bright. Also note how the blinking lights illuminate the barmaid's arm.



This bar is also a great example of Ralph adding tons of little animating details, like the drunk guy on the roof. Many of those details will likely not be seen by most players, but the total effect of having such a detailed world is very strong, even for players who don't look at it specifically.



As a programmer when thinking about lighting in 2D games I immediately start considering technical solutions. I would look at things like normal maps (very possible in 2D) or automatic rim lighting. However, more creative, art-driven solutions often work much better, especially when creating a visual style with such a painterly look as in Swords & Soldiers II. The simple yet clever techniques Ralph used to create this nighttime level are a great example of this.

Saturday 25 October 2014

Proun+ gets its first trailer!

We have released the first trailer for Proun+, the biggerbetter Proun that is coming to 3DS, iOS and Android! Proun+ is being made together with Engine Software and will have six new tracks and a completely new soundtrack: more songs and all the songs have now been recorded by real musicians for a much better sound. In this trailer you can hear the new version of one of the old songs and see one of the awesome new levels in action, plus footage from some of the original tracks. I am really hyped for the return of Proun, so I hope you like it!

Saturday 18 October 2014

Area based depth of field blur

While working on the visual style for my weird live performance game Cello Fortress I came up with a new technique for depth of field blur: area based depth of field blur. As far as I know this is not an existing technique so today I would like to explain how it works.

The visual style for Cello Fortress is far from finished at the moment, but I decided early on that I wanted strong depth of field blur to play a major role. I had already implemented depth of field blur for Proun (which by the way is coming to 3DS, iOS and Android soon!) and I copied that to Cello Fortress. Proun does not have blur on the foreground, so I added that and tried it in-game. The result turned out to not work at all, as you can see in this image (be sure to click the image for a larger version, since this is difficult to see in these small blog-sized images):


click for larger image


The problem is that with standard depth of field blur, only one specific distance to the camera is sharp. In Cello Fortress the camera looks down on the battlefield diagonally, which means that that specific distance looks like a circle. Even weirder is that the part of the screen that is closest to the camera is almost at the centre of the screen: that is the spot the camera hangs exactly above. The result is that both the edges of the screen and the centre are blurred. Of course it is totally undesired that the centre of the gameplay would be blurry.

A simple solution I then tried was to broaden the area that is sharp:


click for larger image



click for larger image


The goal was to have strong depth of field blur as a core part of the visual style for Cello Fortress. So far we either have depth of field blur that interferes with the gameplay, or no depth of field blur at all in the foreground. We need something better:



Once I drew where I wanted blur I realised that this is a simple shape: in world space this is just a simple axis-aligned box. So I implemented a shader that calculates the strength of the depth of field blur based on its distance to that 3D box, instead of distance to the camera. The result is exactly what I was looking for:


Click for larger image.
Note that the effect is exaggerated in the smaller screenshot above, the full-res version has the normal, slightly less extreme blur.

A big benefit of this technique is that tweaking it is really straightforward, and that it is independent on the camera. I can easily set the sharp area from code based on the gameplay situation. It also gives me precise control over the height at which the blur starts.

Technically area based blur is quite easy to do. The depth of field blur shader already uses a render-texture that contains the depth of each pixel to the camera. I don't use this depth for anything else, so I can put any value I like there. The pixel shader can easily be adjusted to calculate depth in a different way.



This concept can also be applied to other shapes than boxes. For example, you can also have a sphere within which everything is sharp, while everything outside that sphere is blurred. One can even have several such spheres. How about a visual style where everything is blurred except for the areas around the characters? I think some other interesting visual styles can be made this way, especially in combination with very strong blur.

I have seen some games that use non-distance based depth of field blur, like the beautiful Below, which seems to simply blur the top and bottom of the screen. I am not aware of games that use a 3D area as I use it. Let me know if there are other games that already do this.

The fun of writing your own shaders is that you can bend them to do whatever you want, including weird and unrealistic effects like doing my depth of field blur based on a 3D box area. Feel free to use this idea in your own games, and I'd love to hear from you if try it out!

Sunday 12 October 2014

Other developers on the ideal patching frequency

Last week I wrote a blogpost about how we think it is better to have a bigger patch once every one or two months than to have really small weekly patches. I was curious what other developers' experiences with this are, so I asked around for more opinions on this. Since patching on console and mobile is so different I looked for developers who have a game on Steam, which is the platform that enables regular patching best.

Someone also pointed me to the Valve talk where they explained the importance of communication around patches and how this helped them grow Team Fortress 2. This is an incredibly interesting talk, so be sure to check it out:



Here are the replies I got from fellow developers:

Jamie Cheng from Klei
developer of Don't Starve

"While I have lots of opinions, I think it comes down to "it depends". Personally I think many devs try to do it the Valve Way only to find they don't really, truly understand why it works for Valve."

Mark Morris from Introversion
developer of Prison Architect (currently in Early Access)

"I guess the update frequency is linked quite closely to the style of development. For us, we wanted to produce quite meaty chunks (the hope being that we would get press coverage for individual updates). A month gave us enough time to develop decent additions, but was at a frequency that would still be engaging for the players. I could see weekly working, but I think that each update would be a lot less polished and would have a much more iterative development feel about it."

Kimiko from Berserk Games
developer of Tabletop Simulator (currently in Early Access)

"I think it would also depend on the game. For us in Early Access, we are one of those who patch every week or 2 weeks. Our game is a different spectrum compared to ones with stories, weapons, & what not. So patching each week works well for us. We're only doing this for Early Access though or for "bigger" updates, we'll spread it out a bit, like when we add in Oculus Rift or some of our other bigger stretch goals. Once we are out of Early Access, then we'll spread our updates out every month or so."

"There's only two of us and we work well putting out our patches each week, because it's usually about tweaking things, fixing bugs and implementing a feature. TTS is more for people to create their own games, so for us, it's better to get things out to help our users out more. Once we feel TTS is at the point where the community has the tools they need to create their own games to their fullest abilities, then we'd go out of Early Access and we wouldn't need to update every week anymore. But my point is, is that we'll still update after Early Access, but we won't have that greater need to do it each week like we do now, because it's at that "completed" stage and we'd focus on the bigger picture of adding in the bigger things from our Kickstarter stretch goals, and find ways to improve it in general."

"I think we probably spoiled our community because of our weekly updates and who knows what the uproar will be if we switch to monthly, but it's probably something we'd do gradually and we'd let our community know since we're pretty transparent. [...] As long as we keep our community in the loop, that's most important."

Pete Angstadt from Turtle Sandbox
developer of Cannon Brawl (recently released out of Early Access)

"I think the regularity of update scheduling, whether it's a week or a month is probably the most important part. That and communicating the schedule to your audience. [...] Vlambeer has a weekly schedule which they communicate to players with their livestream. Other games I think have done 'in-game' countdown timers to the next patch, or at least had the latest patch notes visible in game. If we had to do it over again, I would have gone with a very regular monthly patching schedule and included patch notes in game."

Roel Ezendam from Ragesquid
developer of Action Henk (currently in Early Access)

"We recently switched from bi-weekly to monthly updates for our Early Access game Action Henk. The biggest improvement that we have noticed is that we have far less overhead that's being spent on finishing and releasing the update. With a short update cycle the game constantly needs to be in a stable state, which makes it harder to work on larger features or a big overhaul. It also just takes time to publish the update and check if everything is working properly. These bi-weekly updates basically put us in a constant state of crunch, whereas the monthly updates give us a bit more breathing room."

Erik Johnson from Arcen Games
developer of AI War: Fleet Command and The Last Federation

"We've found that patching often isn't a bad thing if supporting your core community members (in effort to expand your core community) is your aim. [...] Anyway, I agree that this isn't a solid way to market the game in the main, but that's where our larger, more content-focused updates and DLC releases come in. I've found you can't tap the well too many times no matter how you slice it (unless you're in that fortunate position to have a sizable audience just begging for more) as far as reaching out to new players -- but a consistent stream of smaller updates keeps the community you already have established active and growing. That said, we do find that even our most popular games occasionally hit periods of patch ennui for both our community and our development team. :)"

Josef Vorbeck from Chasing Carrots
developer of Cosmonautica (currently in Early Access)

"We update Cosmonautica in 2 week cycles. We even did this before Early Access, because it's our standard rhythm with two week sprints. And we think, that we can deliver enough in two weeks to make these updates meaningful. Also we think that it's crucial for an Early Access title, that the players see constant progress during the development. These days Early Access has a mediocre reputation, because some devs are leaving their games or decide their games are finished, even though more features were planned. With our update cycles and constant communication we're trying to earn the trust of the players. It just works for us, the response so far is really great. And of course it's important for us to get the valuable feedback from our players on a regular basis. But after our final release we might switch our update rhythm to aim for larger content updates which deliver their own story, as Joost stated."

While digging for opinions I also got a replay on Gamedev.net from a user named Orymus3 who wrote a really interesting remark on the term "patch" itself:

"I would avoid using the term 'patch'. To most people this suggests you are fixing bugs, which also infers you develop bugs. What you really want to put forward is the fact you're actively working in the game, and are releasing new content. 'Content Push', 'Release', etc. are all better terms to refer to what you're doing. This may not appear like much, but imagine that a player comes across a post about your game (it's the only thing he's ever seen) and he sees 'Patch'. He's likely to think: here's another incomplete Beta filled with bugs, I'll give this a pass."

Sunday 5 October 2014

Why patching too often is a bad idea / The magic of the Vault

Recently I have seen quite a few games that launched with the plan to patch really often, especially Early Access games. Most of those games patch once a week or once every two weeks. This may seem like a good idea: iterate quickly and show clearly to the user that you really do the best you can to make good on the promise of improving the game. For a time with Awesomenauts we also tried to patch as often as possible, but by now we think that is actually a bad idea.

The main reason for this is that the more often you patch, the smaller the patches are. Lots of small patches means lots of hardly noticeable changes to the game. Why would a user come back to your game because of 5 balance tweaks, 3 bug fixes and improved graphics for 2 weapons? Why would a regular player be exited about this? The changes done in weekly patches are just too small to make an impact.

Combining a bunch of those smaller patches together creates something much more noteworthy. In a bigger patch once every one or two months you could overhaul the graphics of all the weapons instead of just two, do dozens of balance tweaks and fix a ton of bugs. Simply combining all the changes from a bunch of micro-patches into one bigger patch turns it from a bunch of uninteresting patches to one exciting patch that really improves the game significantly.

An important note here is that I am NOT suggesting that development should be slowed down. On the contrary: keep improving and extending that game as much as you can, just like we try to do with Awesomenauts! I am only suggesting to group the changes and release them together.



The goal of doing a games-as-a-service model where you are constantly improving the game is not only to improve the game, but also to excite the players. Keep them playing longer, bring back players who stopped playing and get new players. To excite players you need stories. Not literal stories, but things that players can discuss with their friends. Bigger patches are much more interesting to talk about.

Having bigger patches also allows you to create new 'stories' without additional development. You can give a patch a name and a theme simply by looking at the changes and finding some similarities. This way you can create a new story for the patch itself and make it feel like a big event.

Since December we have been doing active marketing for each Awesomenauts patch. We announce a patch beforehand and slowly reveal information about it. We have made a special website for this: Voltar's Vault.



A couple of weeks before a patch comes we open the Vault. At that moment it contains only locks. Then in the weeks up to the patch we gradually release more info on what is going to be in it. Usually we first give a vague hint, then a couple of days later we announce what it really is. This pushes anticipation for our patches enormously. Our community creates a Vault topic on our forum for every patch and posts hundreds of pages of discussion there, as you can see in this topic for patch 2.7. The more interesting the features are and the more suggestive (but cryptic!) the hints are, the crazier it gets.



The result is that we can create crazy hype for every patch and get big peaks in our playerbase whenever we release a patch. The day a patch launches we have twice as many players as on a normal day. Sometimes we can even create significant sales bumps ourselves. Those are small compared to the bump of a Steam sale, but Steam sales require getting lucky with Valve to get a slot. We can create sales peaks through hyped patches ourselves.

By increasing the size of the patch and adding a name, theme, Vault website and hints we can create real stories, worthy of discussing with your friends. In some cases even worthy to be picked up by press: a couple of big news websites (including Destructoid) often write about our patches. This only works because there is enough time in between patches to actually hype them, and because patches are big enough to make this worthwhile.

Note that if you look at our patch notes you might get a different impression. We do many more patches than I describe here. The reason for this is that we distinguish between major patches and hotfixes. A hotfix is a small patch that only fixes some immediate issues. Obvious bugs or even crashes should not be left in the game for a month, so we don't bunch up fixes for game breaking issues. Hotfixes generally don't add anything new: they just fix a broken game experience.

We started bunching features into bigger patches after we heard about how Valve went the same road with Team Fortress 2. Apparently they did weekly patches for quite a while, sometimes doing even two patches a week. They claim to have much more success with the patches since they bunch them up and give them a name and a theme. I tried finding the article where I read this but couldn't find it. Regardless, have a look at Team Fortress 2's patching history and you will see that Valve creates big patches with some time between (plus apparently a lot of small tweaking patches).



So far this post has mostly been about marketing. There is of course also a practical side to patching and continuous development. When we want to do big changes or add complex new features to Awesomenauts we need time to balance and tweak those. A big portion of that is done through semi-public betas on Steam. When we add a new character we need several weeks of beta to get his balance right for launch. This workflow is not very compatible with weekly patches.

Also, focussing on having something new ready every week probably requires incredibly short and focussed development cycles. This might sound good but I doubt production can be this focussed permanently for a year or more without burning developers out. Doing weekly patches requires really good management to keep it going and likely adds constant pressure on the dev team.

In the end patches are also a form of marketing: they need to create stories. Not literal stories, but things that are worthwhile to talk about. Things that press can pick up on, things that players can discuss.

PS: here's the follow-up blogpost to this one: Other developers on the ideal patching frequency

Sunday 21 September 2014

Relay servers

Last week I discussed the core network structures for games. There is one really important topic that I left out then: relay servers. Relay servers are especially important to understand since I have recently heard them confused with dedicated servers quite often. Today I would like to explain what relay servers are, and what they are not.

A relay server is essentially just a computer that sends and receives packets. It does not really process data and does not do any gameplay logic. All it does is that if player A sends a packet to player B, then instead of sending it directly player A sends it to the relay server. The relay server then sends it to player B. The relay server is essentially just a glorified router.



So why is this useful? Relay servers have two big advantages. The first is that players can practically always connect to them. Security measures in routers are a big problem in internet connections, causing many users to not be able to connect to each other directly. Usually this can be solved in the router settings by setting UPNP or port forwarding, but many users don't know how to do this. Techniques like NAT punch-through help, but still don't solve the problem in a lot of cases.

An important aspect of connectivity issues is that if one of the two computers that try to connect to each other is set up entirely right, then it is almost always possible to connect the two computers, no matter how badly the other computer is set up. This is where relay servers come in: the developer manages those and can thus make sure they are set up optimally. So even if two players cannot connect to each other directly, it is extremely likely that they can both connect to the relay server and send packets to each other through that.

The other big benefit of relay servers is that they can massively reduce packet count, especially in peer to peer situations. As I explained in a previous blogpost, packet count is an important factor in connection quality.

The internet does not allow multicasting, so if you want to send the same message to several other players, then you just need to send it several times. A relay server can work around this. Whenever a player wants to send to all other players, she sends only one packet to the relay server. The relay server then copies the packet and sends it to each client. If several players are all sending to the same player the relay server can also combine their packets into one bigger packet. These features greatly reduce packet count and bandwidth in a peer to peer situation, or for the host in a situation where a player is the host. This way relay servers theoretically make it possible to have a peer to peer game without dedicated servers.

Note that dedicated servers have these exact same benefits. Players can practically always connect to them and players only have to send packets to the dedicated server instead of to all other players. For this reason there is normally no point to having relay servers if you already have dedicated servers.

A big downside to relay servers is that sending all data through the relay server adds a little bit of latency to the connection. This is especially problematic if players from several continents are playing together in one match. You might think intercontinental play should never automatically happen, but you need thousands of simultaneous players to always avoid this. Even then international friends might send each other invites.

Let's say we have a match with four European players and two Australian players. The relay server for this match is in Europe. The connection between the Europeans will likely be a little bit slower but still fine because the relay server is close. The connection between a European player and an Australian player will also not be affected too much, because the data needs to be sent that far anyway. The problem happens between the two Australian players: since everything does through the relay server, their traffic now goes through Europe instead of directly, massively increasing their ping!

For this reason I would never want to use rigid relay servers for a game where latency matters. If players can connect directly and have a fast enough connection to handle the packet count, then it is probably faster to let them communicate directly. This also saves on the cost of running expensive relay servers. I think relay servers are mostly useful as a last resort for players who otherwise cannot connect at all, and for players whose internet is too slow for the number of players they need to send to.

Awesomenauts currently does not have relay servers. Instead it solves the problem of two players not being able to connect directly by sending through one of the other players. This often works fine but it is an imperfect solution: it increases the burden on that player's connection. Also, in extremely rare cases a player cannot connect to anyone in the match.

We are currently putting a lot of effort into improving the connection quality for players in Awesomenauts. Relay servers are a feature we are considering for the future, but right now we think we can gain more by improving matchmaking first. We are writing a completely new matchmaking system that will allow us to match players better based on their connection and location. Better matchmaking also brings many other benefits that are unrelated to connection quality. A big recent improvement is that we managed to halve (!) the average bandwidth and packet count used by Awesomenauts. In the long run we will need to research relay servers further to know how beneficial their trade-of of connection quality versus latency would really be.

To summarize I would like to stress that relay servers are not the same as dedicated servers. Relay servers are a tool for reducing bandwidth and packet count and for improving connection quality, potentially at the cost of latency.

Note: I have edited this post on 27-9-2014 to remove references to the Photon network library. It turned out they had added new features that I was not aware of and that made my analysis of what Photon offers incorrect and irrelevant to this post.

Sunday 14 September 2014

Core network structures for games

When starting to develop an online multiplayer game you need to choose how to structure the netcode. Especially important is the question which computer decides on what part of the gameplay. There are roughly four models in common use in games these days. Today I would like to explain which those are and what their benefits and downsides are.

Here are those four basic structures (of course all kinds of hybrids and variants are possible):



Client-server

In the two versions of client-server there is one computer who is alone responsible for the entire game simulation: the server. The clients cannot make real gameplay decisions. This means that if a player presses a button, it goes to the server, the server executes it and then sends back the results to the client.

This adds significant lag to all input, which is of course totally unacceptable and kills the gameplay feel. To make a game playable with this model all kinds of tricks are needed. The best trick I am aware of is described in this must-read article by Valve. The basic idea is this:

  • When the player presses a button, the client immediately processes it as if it has the authority to do so, starting animations and such. A message is also sent to the server.
  • The server receives the button press a little bit later, so the server rewinds to the time of the button press, executes it, and then re-simulates to the current time.
  • The server then sends the current state to the client
  • The client receives the latest state, but in the meanwhile more time has passed. So the client rewinds to the time at which the server sent the message, corrects its own state with what the authoritative server had decided, and then re-simulates locally to the current time.

In other words: both the client and the server rewind and then re-simulate whenever a packet is received. Implementing rewinding mechanisms is a complex task and very difficult to add to an existing game. As far as I know this is nevertheless the best and most used approach.

The difference between the two client-server architectures is who the server is. Either it is one of the players, or it is a computer that the game's developer/publisher manages. A dedicated server is usually better, but much more complex and expensive as the developer needs to manage a scalable amount of servers. The fiascos at the launches of Diablo III and Sim City showed how difficult this is to do. The more successful the game, the more difficult dedicated servers are to pull off. They are also simply expensive.

Peer to peer

The third architecture is pure peer to peer. Here no single computer is responsible for the entire game simulation. Instead the simulation is spread out over all of the players. The challenge then is how to divide responsibilities over the players. Awesomenauts uses this model and our distribution of the simulation is simple: each player simulates his own characters and bullets. This has a big benefit: player input can always be handled immediately. No rewinding structure are needed and there is never any input lag for the player. This also makes it much easier to add to an existing game.



Peer to peer has some heavy drawbacks though. The biggest one is that lag becomes much more unpredictable. While in a client server architecture only the lagging player suffers from his own lag, in a peer to peer game the other players will also notice if one player has a bad internet connection.

Peer to peer usually introduces complex synchronisation situations when the simulations of two players are not compatible. A good example of this can be found in my previous blogpost on Awesomenauts' infamous sliding bug. Care needs to be taken to recognise and handle such situations. In most game concepts few of these problems will pop up though: in Awesomenauts pushing other players is the only really complex part regarding conflicting synchronisation.

Another major downside of peer to peer is in the amount of network traffic needed. Since all players need to talk to all other players it requires many more network packets. In client-server only the server needs to talk to everyone, so only one player is affected instead of all of them. Even better for packet count is using dedicated servers: the entire burden falls on servers that the game developer provides.

Deterministic peer to peer lockstep

The fourth and final basic structure is deterministic peer to peer lockstep. This model is mostly used for RTS games. This is also a peer to peer model but here we don't need to worry about which player manages which objects. Instead every client simulates everything in the exact same way. The only thing that needs to be sent over the network is each player's actions. The game runs as lots of really short turns: every step the game collects the commands from all players over the network and then simulates the next step. This is not limited to turn-based games: by doing lots of really short steps it can feel like a real-time game.

Deterministic peer to peer has the enormous benefit that you hardly need to send anything. Only player actions need to be sent. If everyone starts the game in the same situation and runs the exact same steps, then the game will remain in synch without ever sending updates over the network. Therefore this model is highly suitable for RTS games, since they have so many units that synchronising everything is often infeasible. An old but still great article on implementing full determinism is this one: 1500 Archers on a 28.8: Network Programming in Age of Empires and Beyond.

A downside to this model is that it usually adds quite a lot of lag to controls, since actions cannot be executed until all players know about them. Such input lag can be hidden by playing sounds and visual effects immediately when the user clicks. This way the player won't notice that his units don't react immediately.

Note that deterministic lockstep can also be combined with a client/server connection model where the data always flows through the server instead of directly between all players.



Implementing full determinism is incredibly difficult. If any differences exist between the simulations on the clients, then these differences will grow over time and result in the desynchronisation of the game. Lots of tricks need to be used to achieve determinism. For example, floats cannot be used because of rounding errors: all logic needs to be build on integers. Random number generators can only be used if their seeds are synched and they are used in the exact same way. This might for example go wrong if one player runs on a higher graphics quality and thus has extra particles on his screen. Those particles might also use the random number generator and thus desynch it. A simple solution is to use a separate random generator for non-gameplay objects, but this is easy to forget, breaking the entire game.

Getting determinism right is such a challenge that many games that use it add a mechanism to check the correctness of the simulation. They regularly send a checksum of the entire gamestate over the network. Checksums are small so this uses hardly any bandwidth. If the checksums are not the same then the game has desynched. To fix a desynch we could pause the game, send the entire simulation over the network and then continue from there. In older games you might recognise this problem when you got kicked out of a game because of a "synchronisation error".

There are of course many more subtleties to network architecture than I have explained here. All kinds of hybrids are possible and there are many details that I have not mentioned, like vulnerability to cheaters and host migration. I cannot discuss them all today, but I hope this blogpost has given a good summary of the basics. One important topic that really needs to be explained in combination with the above information is relay servers so I will cover that next week.

Saturday 6 September 2014

The importance of packet count

When learning about online multiplayer programming I always read that it is important to keep the bandwidth usage low. There are tons of articles that discuss bandwidth optimisations and limitations. However, while developing Awesomenauts we learned that packet count can in some cases be equally important. Somehow I have rarely seen this mentioned in articles or books, so I figured it was about time to write a blogpost to tell the world: packet count is also important!

When we started development of Awesomenauts I though that packet count was only relevant because of the size of the packet headers. Every UDP packet has a UDP header (8 bytes) and an IP header (at least 20 bytes). This means that no matter how little data you send per packet, it always gets an added 28 bytes. This makes packet count relevent for bandwidth: if you send 200 packets per second, then you are sending 5600 bytes per second only in headers.

I thought this is where the importance of packet count ends. If I can somehow optimise my game to send only 30 bytes per packet, then it is okay to send 200 packets per second because the total bandwidth will still only be 200 * (20+8+30) = 11600 bytes per second, which is fine for a modern game.

It turns out that this is not true on the real internet. During development of Awesomenauts we found out that high packet count by itself is a serious problem. Quite a few internet connections that would happily send as much as 40 packets per second of 1200 bytes each (totalling 48kB/s) become problematic when they need to send 200 packets per second of 50 bytes each (totalling only 10kB/s).



In our experience sending more than 100 packets per second is problematic for some connections, resulting in packet loss, lag spikes and ultimately losing the connection altogether. We recently decreased the average send rate in a full Awesomenauts match from 150 packets per second to 75 and this seems to have decreased the number of connection errors by around 25%. In that same patch we also decreased the average bandwidth by 50%, so I cannot say for sure whether decreasing just the packet count would have had the same effect. However, based on earlier experiments with this I think the packet count decrease was more important than the bandwidth decrease. Our impression is that packet counts above 100 per second are a problem while below 100 packets per second it is not very relevant to optimise further

The internet in general is a weird topic because it behaves so unpredictably on some connections. For example, we have seen that some routers always bunch our packets: they constantly arrive two at a time even though there is 33ms between sending.

Note that there is more to packet headers and overhead than the UDP and IP headers I mentioned above. For example, I recently learned that when on a DSL line an extra DSL header is added. This is all hidden from the game code, but it means that having lots of packets can on some connections also mean using more bandwidth than you realise.

So there you have it: be mindful of your packet counts! Sending lots of small packets is not a good idea and should be avoided if possible. This is especially relevant for peer-to-peer games, since everyone in the game talks to everyone else and packet counts thus rise quickly.

Friday 29 August 2014

A simple trick for fast high quality bokeh on lights in Cello Fortress

Bokeh is an effect that pops up in a lot of new games. It is one of those effects that makes a game instantly feel a lot more "next-gen". It is also an effect that usually eats up a lot of performance. For Cello Fortress I came up with a simplified version of bokeh that looks really high quality, is very fast to render and even very easy to implement. My implementation also has some severe limitations, but I think it can work really well for many games.

Bokeh is a part of focal blur, which is also known as depth of field blur or DoF. DoF is the effect that only objects at a certain distance are sharp, while everything closer and further away is blurred. This is an effect that every lens has, and the larger the lens is, the stronger the blur is. Focal blur has been done in many games for quite a while now, but with the normal DoF rendering techniques the bokeh effect is usually lost. Bokeh means that extremely bright spots grow with the blur and appear as clearly recognisable circles (or hexagons or other shapes, depending on the shape of the lens).


Image from HDWallSource.com.

The problem with rendering bokeh in games is that a naive implementation requires high dynamic range (HDR) rendering and an extremely large amount of blur samples. HDR has become quite common in games by now, but taking enough samples to get good sharp bokeh is impractical. For bokeh as large as in the image above, you would probably need many hundreds of samples to get it look smooth. I actually tried that exact thing in Proun two years ago, as a fun little experiment.

Proun already had really high quality DoF (as I described in this blogpost). I added bokeh by simply making some pixels extremely bright. This is a quick dirty trick that was needed because Proun only has limited fake HDR, but the effect looks pretty convincing, as you can see below on the left image. However, if the blur is increased the bokeh becomes extremely noisy, as you can see on the right. It looks noisy despite that it already uses a quite insane 128 samples per pixel! You can find more images of this approach in this blogpost.



This makes this naive approach unusable if strong blur is wanted. We need something smarter. The most common approach in current games seems to be to render actual polygons with a bokeh circle texture on them. To do so we need to find all the bright pixels in the image and then generate a quad for each one.

According to this article The Witcher 2 was ahead of its time by having bokeh all the way back in 2011. The Witcher 2 did this by generating a quad for every pixel and then discarding the ones that are not blurred enough. That's a whole lot of sprites to render! Needless to see this only worked in real-time on the very fastest PC videocards.

Most games that have bokeh these days seem to use a smarter approach, using newer shader models: first they look for all the pixels that are so bright that they would get a clear bokeh circle, and then they generate quads for this. An example of this approach can be found here. Unlike The Witcher 2's technique this creates only the bokeh itself, not the general focal blur, so with this technique the depth of field blur needs to be done separately.

Even with this clever technique the performance hit is still heavy. It requires analysing all the pixels on the screen to find the ones that are much brighter than the ones next to it. It also produces temporal artefacts: if the source of the bokeh is really small it will flicker because it is smaller than a pixel. Normally this is not that much of a problem because it is only a pixel, but if a big bokeh sprite flickers on and off this becomes much more noticeable. These temporal artefacts might already show with slight camera movements. I don't know what technique Star Citizen uses, but the kind of flickering this would result in can clearly be seen in this video in the bright spots in the background.

Now that we roughly know how bokeh is usually rendered, let's look at that simple and fast trick that I use in Cello Fortress. My idea comes from that the most pronounced bokeh is often from actual lights, not just random bright pixels. If you are looking directly at a light, but the light is in the blurred background, then it will generate a very clear bokeh circle. In general a game engine already knows where all the lights are, so this means that we can skip the searching for bright pixels entirely and directly create one screen-space quad for every light. To do so I first render the scene, then apply normal depth of field blur, and finally render the bokeh sprites on top of that.

Not only does this method skip the expensive step of finding the bright pixels that need bokeh, it also fixes all the issues with temporal artefacts. We always know exactly where the lights are so no matter how small they are, the bokeh will never flicker when the camera moves. It just moves along with the light correctly.



To get a good-looking effect I scale the bokeh with how blurred the light should be. This can simply be calculated based on the focal settings of the camera and the distance to the camera. I also fade out the bokeh sprite a bit as it gets larger, since the larger the blur, the less bright the bokeh circle should be (unless the light is infinitely bright). Here is a video that shows the bokeh in action in Cello Fortress. The bokeh is mostly visible at the bottom of the screen.



An important part of bokeh is the actual shape of the bokeh effect. This shape is created by the shape of the lens. I often like hexagonal bokeh best, but I recently discovered that in photography this is generally considered ugly. When reading reviews of a new camera lens I wanted to buy I learned that the more expensive lenses have circular bokeh while cheaper lenses have hexagons. Still, in the end the only thing that matters is what looks good aesthetically in your game. Since most bokeh rendering techniques use those textured sprites the bokeh shape can be modified really simply by using a different texture.



Note that this all does not look as good as it can yet because I have so far spent too little time on the actual visual design of Cello Fortress. I mostly focussed on the gameplay and some cool shaders. Once I start working on proper graphics I should also tweak the brightness, size and colour of the bokeh to make it look better. I should probably also try adding a bit of chromatic aberration to the bokeh texture then.

My bokeh technique does not solve occlusion at the moment. If a light disappears behind an object then it should not still get a bokeh sprite. I didn't solve this yet because it does not occur in the current version of Cello Fortress. However, several solutions can be implemented easily. For example, I already have a depth texture for the depth of field blur, so I can do a look-up in that on the screen position of the light to see whether there is an object in front of it.

The big downside of my method for rendering bokeh is that you need to know where the bokeh will appear beforehand. This means that more subtle bokeh sources like reflections and strong speculars are not practically doable. I can imagine some tricks to get for example bokeh in planar reflections working (if you know where the reflecting planes are), but beyond that it quickly becomes infeasible. The standard technique of searching for the bokeh pixels of the image handles this much better, so if you really need bokeh on speculars, then you will probably need to resort to such techniques.


Image from this article by MJP

I looked up a bunch of articles on bokeh implementations and couldn't find any mention of something similar to what I am doing. This surprises me because the idea is so simple and obvious. If anyone knows of any articles or games that already do this, then please let me know so that I can add a link.

That's it! My bokeh technique is simpler and much faster than most commonly used methods of rendering bokeh and it even fixes problems with temporal artefacts. It is also a limited technique that does not handle all bokeh effects, but in many cases it will probably be good enough. It definitely is for Cello Fortress!

Sunday 24 August 2014

Tips and tricks for a successful convention booth

Last week we were at Gamescom, showing Swords & Soldiers II and Awesomenauts to the public. Gamescom is the biggest game convention in the world, drawing in a whopping 400,000 people. We have had booths at several conventions in the past years so I figured it might be interesting to share some tips and tricks based on our experiences.

Our booth at Gamescom was part of the Indie Megabooth. The Indie Megabooth is an awesome initiative where a lot of indies hire a big area together and fill it with their games. Since the Indie Megabooth has been so successful in recent years it is now a real organisation with dedicated people to manage it all.

There are several advantages to being part of the Indie Megabooth. For starters it is quite affordable and they take care of a lot of the organisational complexities. More importantly it gives gamers who like indie games a clear spot to go to, hopefully making indie thrive more on a big convention where most booths are gigantonormous monsters from the big publishers. Another good reason to join the Indie Megabooth is that it is great to meet other indies and hang out with them. For example, we were next to Capybara Games, creators of Below, Super Time Force and Sword & Sworcery. Since I really look up to them it was inspirational for me to meet them and discuss game development.

As with all good things there are also some downsides to the Indie Megabooth, in this case mostly because it is so good. The Indie Megabooth is very popular among developers so they get way more requests for booth spots than they can handle. The result is that not everyone can get a booth. It also makes them not very flexible if you want a bigger booth.



To decorate our booth we used big cloth banners. This works really well: they weigh little and unlike posters they hardly tear or damage. You can just roll them up and bring them along. Banners are also a really cheap solution: the type we use costs only around €20 per banner (we got them at Drukwerkdeal.nl). The only downside to the banners we use is that they are slightly transparent, so if the surface behind the banner is coloured or uneven then you might see this through the banners.



The most important thing to us is that as many people as possible get to actually play our games. For this reason we put four screens in our booth: two for Swords & Soldiers 2 and two for Awesomenauts. Since both games support local multiplayer we could have up to ten people playing in our booth. This is quite a lot more than any of the other indie booths, where some could have only one player at a time since they brought just one computer for a single player game. Since players could also play single player on our screens we had between four and ten players at any given time. We rarely had unused computers for longer than a couple of minutes.



While we tried to cramp as many players as possible into our small booth, our friends at Two Tribes had a different approach that I also really liked. They had only two screens for their new game Rive but had a slick design for the booth. They put in nice chairs and beanbags, giving players a very relaxed playing experience. They clearly focussed more on giving each player the best possible experience than on reaching as many players as possible. (Rive is also a great game, by the way, playing incredibly smoothly.)



If audio is important to your game then be sure to bring along some big headphones. There is a lot of noise on game conventions, especially from big booths. We were near an AMD stage where people received free stuff if the crowd shouted "AMD" loudly. At other moments they just played really loud dance music. The Indie Megabooth crew even gave all the indie exhibitors earplugs because of this. One of the other exhibitors had even brought along a microphone to talk to his players without having to shout. When I talked to him it felt quite awkward that he answered me through a microphone while I was right in front of him so I wouldn't personally use this method. Still, I totally understand why he solved the sore-throat-from-talking-loudly-all-day problem this way.



The goal of going to a convention is of course marketing and business. We had a lot of good business meetings and we had many players at our booth, but unfortunately we didn't reach as much press this time as we had hoped. We asked around and most indie devs said the same thing: it was difficult to get a ton of meetings with press going this year. This might be because Gamescom doesn't show as much new stuff as E3, so it is a bit less interesting to the press.

A couple of developers did have a lot of press meetings. One had hired a PR agency to set up the press meetings. While our experiences with PR agencies have so far been very bad, this one had apparently done really well and set up a lot of interviews for them. Another dev said they had started to contact press four weeks in advance. We only started contacting press two weeks before the convention, so we might have also been too late for maximum reach. In general though most devs said they didn't meet as much press as they had hoped, so it seems like Gamescom might also just not be the best spot for this. Of all the conventions we have visited so far we had the most success at Eurogamer Expo a couple of years ago. I have no idea whether that was accidental or whether Eurogamer is actually better for reaching out to press.

From press we go to another exciting topic... utensils! It is a really good idea to bring along a bag of random utensils. My colleague Robin had brought along things like scissors, pins, several types of tape, screwdrivers and pens. Several of our neighbours borrowed them during the convention, so apparently not everyone brings such things along. You never know what might be wrong with your booth so it is good to pack these even if you don't expect to actually need them.



Convention visitors love button badges. They often stick them to their bag right away, hopefully triggering a tiny bit of extra word of mouth and definitely making sure the player remembers the game when he gets home. Buttons are really cheap to order in large batches so we just doled them out freely.



To my surprise our flyers were quite popular. I even saw quite a lot of visitors grab a flyer without playing the actual game.



If you are making a console game then be sure to ask the platform holder for permission to bring along testkits, or borrow special exhibition kits from them for your booth. Travelling with devkits is generally not allowed and you definitely don't want the risk of having to explain to Nintendo, Microsoft or Sony that a devkit was stolen from your luggage... We even got lucky and received two of these awesome exhibition stands from Nintendo. They look really professional and take up less space than a table with a television, so this was really cool.



Really important when exhibiting at a big convention is to never let your booth remain unattended. Always have someone there to look after your stuff. Theft happens a lot at these conventions. The worst time for this is during the night. We knew this beforehand so we brought small computers and carried them to the hotel every evening to be sure they were never left unattended at the booth. Several other indie devs apparently were not aware of this, resulting in two console testkits being stolen from the booths during the night. Never leave stealable stuff at your booth when you are not there, and don't trust convention security to keep your booth safe.

Another tip is to bring a couple of extra people and not have everyone at the booth all the time. Standing at the booth for five days is incredibly exhausting, especially with days like Gamescom's Saturday that last from 9:00 to 20:00. We were with three Ronimo devs and didn't realise until the last day that we could have let one person sleep late every day. This would have helped a lot since getting up at seven every morning and working such longs days is simply too tiresome. Maarten and Robin even had blisters on their feet after a couple of days...

The absolute highlight of being at Gamescom for me were the fans visiting our booth. We met one player who had played Awesomenauts for 2000 hours. Realising that we have made a game that quite a lot of players love so much is incredibly cool! Another player, r0estir0bbe, even brought us a bag of Swiss candy as a gift for the team. Thanks r0estir0bbe! ^_^

Sunday 10 August 2014

The gross imperfections of tuning in music

As a cellist, one of my biggest challenges has always been to play notes at the exactly correct pitch. While the keys of a piano and the frets of a guitar make sure that those instruments basically always play notes at the right pitch (as long as the instrument itself is tuned correctly, of course), instruments like a cello and a violin allow the musician to play notes at any pitch, not just at the pitches of real notes. This gives endless possibilities, but it also means that if you put your finger just one millimeter too high or low, it already sounds out of tune and horrible.



Playing in tune has always been a big topic to me, always striving for that oh-so-difficult 'perfect pitch'. Not that I am horribly good at it, but that is exactly why I practice so much to get closer to it. This is why it came as such a shock to me to learn that there is no such thing as 'perfect pitch': several tuning systems exist and they all come with different opinions on what the exact frequency of specific notes should be. They are also all flawed in their own way. Our modern tuning system is called equal temperament and this is not because it allows for perfect pitch, but because it spreads the pain and problems equally everywhere, instead of having some parts perfection and some parts complete horror.

How can this be? Why is there no perfect system for tuning? To understand this, let's have a look at the frequencies of notes in our modern musical system, and how they relate to each other:

Note Frequency Difference with
previous note
Percentage higher
than previous note
A 440hz
A# 466.16hz 26.16hz 5.95%
B 493.88hz 27.72hz 5.95%
C 523.25hz 29.37hz 5.95%
C# 554.37hz 31.11hz 5.95%
D 587.33hz 32.96hz 5.95%
D# 622.25hz 34.92hz 5.95%
E 659.26hz 37hz 5.95%
F 698.46hz 39.2hz 5.95%
F# 739.99hz 41.53hz 5.95%
G 783.99hz 44hz 5.95%
G# 830.61hz 46.62hz 5.95%
A' 880hz 49.39hz 5.95%

What you can see here, is that each next note has a higher frequency than the previous, and A' is exactly twice as high as A. This way playing an octave (A and A' at the same time) sounds really good, because their frequencies are exactly double. In fact, it sounds almost like a single note.

What you can also see here, is that the distance between two notes grows the higher we get. This way every time we jump 12 notes for an octave, we get exactly the double frequency. Each next note is approximately 5.95% higher than the previous, so notes are spaced equally when measured relatively.

This all looks fine and dandy, and it is something I have known for years. However, it gets hairy when we look at the distance towards that base note, the A. Note the last column:

Note Frequency Percentage above A
A 440hz
A# 466.16hz 5.95%
B 493.88hz 12.25%
C 523.25hz 18.92%
C# 554.37hz 25.99%
D 587.33hz 33.48%
D# 622.25hz 41.42%
E 659.26hz 49.83%
F 698.46hz 58.74%
F# 739.99hz 68.18%
G 783.99hz 78.18%
G# 830.61hz 88.77%
A' 880hz 100.00%

This may look fine, but keep in mind that I previously mentioned that an octave sounds so pleasing because the frequencies are exactly doubled. This goes for other intervals as well. The second-best-sounding interval is at exactly 1.5x the base frequency, so that would be A (440hz) plus E (660hz). However, now look at the table again and note that E is not at 660hz, but at 659.26hz. Slightly out of tune! The same goes for the fourth interval (A+D): the D is not the pleasing 33.33% higher, but the slightly off 33.48%.

This may seem like a tiny difference, but it is actually quite audible, and these aren't even the worst: the major third (A + C#) is at 25.99% instead of at 25%, which is a much bigger difference.

To really understand the problem, you need to hear it. This video explains it quite well by putting perfect chords (50% higher, 33%, 25%) next to the chords of a normal modern instrument (49.83%, 33.48%, 25.99%). Listen carefully to note the difference:



So why don't we fix this up by changing the frequencies to allow for perfect intervals? We could indeed do this, but this would only fix the intervals on top of A. In fact, all intervals would become different depending on what the base note is, because we wouldn't be keeping that 5.95% interval from note to note. No matter how you try, there is no system that results in perfect intervals everywhere. I even tested this with other numbers of notes per octave (instead of the standard 12), but there is no system with perfect intervals.

Letting go of the requirement that all distances are equal, we can choose new tunings that make sure that certain intervals produce perfect chords, while others may sound much worse. This is indeed how tuning worked in the 18th century: some chords sounded perfectly in tune, while others sounded much worse than they do today, making them practically unusable. I guess this explains why baroque music with many sharps or flats is extremely rare: it just doesn't sound acceptable with the tuning used back then.

The system used in the 18th century is called meantone temperament, while our current system is called equal temperament, as all chords sound only a little bit off and none are completely broken. I guess the reason equal temperament replaced meantone temperament is that it allows for much more variation in chord progressions: equal temperament allows all chords in all positions, while meantone temperament only allows specific ones. Those specific ones do sound better though in meantone temperament.

Knowing that the western system with 12 notes per octave is not perfect also explains why other cultures have different numbers of notes. Arabian music for example has 24 notes per octave. This means that in between every one of our notes, they have one extra note. This creates a very different system of musical theory and a very different sound to Arabian music.



Most software for writing music makes it quite difficult to compose with more than the western standard 12 notes, but I have been told that some of the older Prince Of Persia games are notable because the composer abused the MIDI system to play real 24 tone Arabian music. I couldn't find any info on this online though, so I don't know whether that is true.

It is interesting to hear 24 tone music since it sounds quite alien and weird to the western ear, especially when used in a way like this on a special kind of piano:



So why is this all relevant today, now that equal temperament is the golden standard that nearly everyone in the wester world uses? First, it is important to realise that it is not perfect and thus pitch is also not perfect. Comparing a note I play on my cello to one other note might make it sound in tune, while comparing that very same note with another note might result in an interval that is slightly off. This is not because I am playing it wrong, but because the intervals are simply not perfect in our modern equal temperament system.

The second reason this is important to me is that until recently I played in the Kunstorkest, a small amateur orchestra that plays baroque music. Indeed, this is music from the age of meantone temperament, so knowing how it was originally intended is important to us! Not that a hobby musician like myself has the skill to play all the subtleties of this difference, but it helps to at least understand what is going on here and why sometimes the director wants a note played slightly differently. To conclude, here's a short recording of a piece we played with the Kunstorkest:

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.