Interior Mapping: rendering real rooms without geometry

The recently released game Marvel's Spider-Man has interiors behind windows in many buildings. This looks great and it seems to be done using a rendering trick: the geometry for the interiors isn't actually there and is generated using a shader. I haven't seen any official statement by Insomniac regarding how they made this, but based on how it looks it seems very likely that they implemented interior mapping: a technique I came up with in 2007 as part of my thesis research. I've never written about this on my blog before so I figure this a good moment to explain the fun little shader trick I came up with.

Let's start by having a look at some footage from Marvel's Spider-Man. The game looks absolutely amazing and Kotaku has captured some footage of the windows in particular:



As you can see around 0:40 in this video the rooms aren't actually there in the geometry: there's a door where there should clearly be a window. You also see a different interior when you look at the same room from a different corner of the building. In some cases there's even a wall that's beyond a corner of the building. All of these suggest that the rooms are faked, but nevertheless they are entirely perspectively correct and have real depth. I expect the faults of these rooms don't matter much because while playing you probably normally don't actually look at rooms as closely as in that video: they're just a backdrop, not something to scrutinise. I think creating rooms this way adds a lot of depth and liveliness to the city without eating up too much performance.



Before I continue I'd like to clarify that this post is not a complaint: I'm thrilled to see my technique used in a big game and I'm not claiming that Insomniac is stealing or anything like that. As I stated in the original publication of interior mapping, I'd be honoured if anyone were to actually use it. If Insomniac indeed based their technique on my idea then I think that's pretty awesome. If they didn't, then they seem to have come up with something oddly similar, which is fine too and I'd be curious to know what they did exactly.

So, how does interior mapping work? The idea is that the building itself contains no extra geometry whatsoever. The interiors exist only in a shader. This shader performs raycasts with walls, ceilings and floors to figure out what you should be seeing of the interior.



The ray we use is simply the ray from the camera towards the pixel. The pixel that we're rendering is part of the exterior of the building so we only use the part of the ray beyond the pixel, since that's the part of the ray that's actually inside the building.

Doing raycasts may sound complex and expensive, but it's actually really simply and fast in this particular case. The trick is to add a simple limitation: with interior mapping, ceilings and walls are at regular distances. Knowing this we can easily calculate which room we're in and where the ceiling and walls of that room are. Ceilings and walls themselves are infinite geometric planes. Calculating the intersection between an infinite plane and a ray is only a few steps and eats little performance.



A room has 6 planes: a ceiling, a floor and 4 walls. However, we only need to consider 3 of those since we know in which direction we're looking. For example, if we're looking upward then we don't need to check the floor below because we'll be seeing the ceiling above. Similarly, of the 4 walls we only need to consider the 2 that are in the direction in which we're looking.

To figure out exactly what we're seeing, we calculate the intersection of the ray with each of those 3 planes. Which intersection is closest to the camera tells us which plane we're actually seeing at this pixel. We then use the intersection point as a texture coordinate to look up the colour of the pixel. For example, if the ray hits the ceiling at position (x,y,z), then we use (x,y) as the texture coordinate, ignoring z.

A nice optimisation I could do here at the time is that we can do part of the intersection calculations for each of the three planes at the same time. Shaders used to be just as fast when using a float4 as when using a float, so by cleverly packing variables we can perform all 3 ray-plane intersections simultaneously. This saved a little bit of performance and helped achieve a good framerate with interior mapping even back in 2007 when I came up with this technique. I've been told that modern videocards are faster with float than float4, so apparently this optimisation doesn't achieve much anymore on today's hardware.



For more details on exactly how interior mapping works, have a look at the paper I wrote on interior mapping. This paper was published at the Computer Graphics International Conference in 2008. Having a real peer-reviewed publication is my one (and only) claim to fame as a scientist. This paper also includes some additional experiments for adding more detail, like varying the distance between walls for rooms of uneven size and randomly selecting textures from a texture atlas to reduce repetition in the rooms. It also goes into more detail on the two variations shown in the images below.



Since we're only doing raycasts with planes, all rooms are simple squares with textures. Any furniture in the room has be in the texture and thus flat. This is visible in Spiderman in close-ups: the desks in the rooms are in fact flat textures on the walls. As you can see in the image below it's possible to extend our raycasting technique with one or more additional texture layers in the room, although at an additional performance cost.



After having published this blogpost one of the programmers of Simcity (2013) told me that interior mapping was also used in that game. It looks really cool there and they have a nice video showing it off. They improved my original idea by storing all the textures in a single texture and having rooms of varying depth. The part about interior mapping starts at 1:00 in this video:



If you'd like to explore this technique further you can download my demo of interior mapping, including source code. If you happen to be an Unreal Engine 4 user you can also find interior mapping as a standard feature in the engine in the form of the InteriorCubeMap function.

After all these years it's really cool to finally see my interior mapping technique in action in a big game production! If you happen to know any other games that use something similar, let me know in the comments since I'd love to check those out.

The Awesomenauts matchmaking algorithm

Matchmaking is a big topic with lots of challenges, but at its core is a very simple question: who should play with whom? A couple of years after releasing Awesomenauts we rebuilt our entire matchmaking systems, releasing the new systems in the Galactron update. Today I'd like to discuss how Galactron chooses who you get to play with. While the question is simple enough, the answer turns out to be pretty complex.



Many different factors influence what's a good match. Should players of similar skill play together? Should players from the same region or language player together? Should we take premades into account? Ping? Should we avoid matching players who just played together already? Should we use matchmaking to let griefers play against each other and keep them away from normal folks?

If the answer to all of these questions is 'Yes, let's take that into account!', then you'd better have a lot of players! I've previously written about how many players you need for that and the short answer is: tens of thousands of simultaneous players, all the time. That's not realistic except for the very biggest hits, so you'll usually need to do with fewer players and make the best out of your matchmaking.

For Awesomenauts we chose to let the matchmaker gather a lot of players and then once every couple of minutes match them all at once. This way the matchmaker has as many players as possible to look for the best possible combinations.



We'd like to match more than 100 people at the same time so that we have plenty of choice. More than that would be even better: our research shows that our algorithm keeps getting better up to as many as 300 people per round, because smaller distant regions (like Australia) don't have enough players for proper matchmaking until that many. However, the more players we wait for, the worse the player experience gets because the waiting times become too long.

Scoring the quality of a match

Okay, so we have 100+ players that all need to be put in matches, how do we decide what's the best match-up? For example, if we can choose between making a match where the players have equal skill, or one where the ping is low, which do we prefer? And which do we prefer if the difference is more subtle, like we can get slightly more equal skill or slightly better ping? Where do we draw the line? And how do we balance this against wanting to let premades play against each other? Etc. etc.

What we need here is some kind of metric so that we can compare match-ups. Somehow all of those matching criteria need to culminate in one score for the entire group. Using that, the computer can look for the best match-up: the one that gives us the highest score.

To calculate a total score we start by calculating the matchmaking score for each match. We do this be taking a weighted average of a bunch of factors:

• Equally skilled teams. This is the most obvious factor in matchmaking: both teams should be equally good. Turning this requirement into a number is simple: we take the average skill per team and look at the difference between those. The bigger the difference, the lower our score. Note that this does require some kind of skill system in your game, like ELO or Trueskill. This also means that beginning players are difficult to match, because you don't know their actual skill until they've played a bit.
• Equally skilled players. Even if the two teams are perfectly balanced, the match might not be. For example, if both teams contain two pros and one beginner, then the average skills of the teams are the same, but the match won't be fun. So we use a separate score that ignores teams and simply looks at the skill differences between all players. In a 6 player match there are 15 combinations of players and we simply average all of those. The bigger the difference, the lower the score.
• Premades. Ideally a group of 3 friends who coordinate together should play against a similar group and not against three individual players who don't know each other. Assigning a score to this is simple: if both teams have the same situation, then we have a 100% score. If there's a small difference (like for example a 3 player premade versus a 2 player premade + a solo player) then we get a 60% score. For a big difference (a 3 player premade versus 3 solo players) the score is 0%.
• Ping with enemies. For each player we check the ping with all 3 players in the enemy team. The higher the ping, the lower the score. There are 9 combinations of players this way and we simply average those 9 scores to get the total ping score for this match.
• Opponent variation. This is a subtle one that we added a while after launching Galactron. Since our matchmaker basically looks for players of similar skill with a good connection to each other, it tends to repeatedly put the same players against each other. We expected this to be rare enough that it would be fun when it would happen, but in practice our players encountered the same people too often. To counter this we give a match a lower score if players encountered each other in the previous match as well. If they encountered each other as opponents but are now teammates (or vice-versa) we give that a slightly better score than if they meet each other in the same situation (opponents before, opponents now; or teammates before, teammates now). This gives the matchmaker a slight tendency to swap teams around if despite this rule it ends up making another match with the same players. This rule has a very low weight since we value the other rules more, but still this rule improved the situation significantly and we got much fewer complaints from players about this.
• Two possible servers. Since Awesomenauts is peer-to-peer, each match should have a player who can connect with everyone in the match, so that this player can be the server. Ideally there is also a second player in the match who can connect with everyone. This way if the first server-player drops out of the match, host migration can happen and the match can continue for the remaining players. This rule is only needed for peer-to-peer games: in a game with dedicated servers or relay servers this rule is irrelevant.

There's one important factor missing here: ping with teammates. Why is this not taken into account? The reason for this is that for every factor we add, the others become a little bit less important. In Awesomenauts a bad connection with your teammates is usually not a big problem because you never need to dodge their bullets. A bad connection with an opponent is much worse, because dodging becomes really difficult if the ping is too high. By ignoring the ping with teammates, we make the ping with opponents a lot more important.

Something to think about when calculating scores is whether we want them to be linear. For example, is a ping improvement from 210ms to 200ms as worthwhile as one from 110ms to 100ms? Both are 10ms improvements, but the latter is relatively twice as big. In Awesomenauts we've indeed tweaked our scoring formulas to better match the perceived difference instead of the absolute difference.

Another consideration is limiting the range of the scores. For example, in Awesomenauts the highest ranked players have a skill of over 20,000, but only 0.3% of all players are above 18,000. In other words: there's a huge difference in skill score in the very top, but this is quite useless to the matchmaker since there are too few players with such a high score to actually take this into account. So before calculating the skill scores we cap them to workable ranges. This way the matchmaker will consider a match-up between two players with skill 18,000 to be as good as one between an 18,000 player and a 20,000 player. Ideally you don't cap anything, but since we have to balance between all the different matchmaking goals capping at some points will make other ranges and aspects more important.

Combining scores

For each of the above 6 rules we now have a score from 0% (really bad match-up) to 100% (really good), but we need 1 score, not 6. To get this 1 score we take the average of all the scores. We use a weighted average for this so that we can make certain things more important than other things. For example, in a fast-paced game like Awesomenauts, ping should be pretty important. Opponent variation on the other hand is a detail that we don't want to stand in the way of good ping, so that one gets a pretty low weight.

An interesting thing that happens here is that some of these scores react much more extremely than others. Getting a 0% skill score requires having 3 pro players and 3 beginners in a match, which is extremely rare. Getting a 0% premade score however happens much more easily, since all that's required for that is having a three player premade play against three solo players. Some scores reacting more subtly than others is something we need to take into account when choosing the weights: since premades react so strongly, we need to give them a lower weight to keep them from overshadowing scores that respond more smoothly, like skill and ping.

Now that we have a single score for each match, we can calculate the totale score for the 100+ players we're matching. We do so by simply averaging the scores of all the matches. The result is one big megascore.



Since we look at the total score, the algorithm gets certain preferences. If swapping two players increases the score of one match by 5% but decreases the score of the other match by 10%, then it won't do that since in total that makes things worse. This sounds obvious, but in some cases one might want to deviate from this. For example, maybe you might prefer improving a match with a 50% score (which is really bad) to 55% at the cost of decreasing a 90% match to 80% (which is still pretty good). A way to achieve this might be to take the square root of all the match scores before averaging them. That way improving bad matches becomes relatively more important. For Awesomenauts we decided against this, because we think the individual scores already represent well enough how big a match quality improvement really is.

Finding the match-up with the best score

Now that we have a scoring system that defines what the best match-up is (the one with the highest score) we get to the algorithmic part of the problem: how to actually find that best match-up. With 100+ players the number of combinations we can make is insane so we can't brute-force our way out of this by simply trying all combinations.

I figured this might actually be a graph theory problem so I tried looking for node graph algorithms that could help me, but the problem turned out to be so specific that I didn't find any. Even after consulting a hardcore academic algorithmic expert nothing turned up, so I decided to look for some good guesstimate and just accept that the actual best match-up is probably not findable. The problem might even be NP-complete, but I didn't actually try to prove that. Finding a better algorithm might be a fun thesis topic for a computer science student somewhere.

The approach I ended up at is to first create a somewhat sensible match-up using a simple rule. I tried a couple of rules for this, like for example simply sorting all players by skill and then putting players in matches based on that sorting. So the top six players together get into one match, then the next six, etc. This is easy enough to build and produces the best possible skill scores. Since it ignores all the other scores entirely it performs really badly for ping and premades.

We now have 6 players per match, but we haven't decided who's in the red team and who's in the blue team yet. So the next step is how the six players in each match are divided over the two teams. Here we can brute-force the problem: we simply try every possible combination and select the best one. Here we take into account all 6 scores, so not just skill. The number of combinations is pretty low, especially since the order in which players are in each team doesn't matter. Since we try every combination we know for sure that the players will be split over the teams in the best possible way.

We now have a good starting point. The next step is to look for improvements: we're going to look for swaps of players that will improve the total score. We do this one swap at a time. Here we can again brute-force our way out of this problem: we simply try all swaps and then perform the best one. There are lots of different possible swaps and we also need to recalculate the split over the two teams for each swap, so this uses a lot of processing power. However, modern computers are super fast so with some optimisations we can do a few hundred swaps per second this way.

Especially the first swaps will improve the matches drastically, but we start seeing diminishing returns up to the point where no swaps can be found that are actually an improvement. There might still be some bad matches there, but no single swap will be an improvement overall. In other words: we've reached a local optimum. We almost certainly didn't find the best match-up possible for those 100+ players, but we can't improve this one any further with our current swapping algorithm.



To get out of that local optimum I tried a few things. The first thing I tried is to do a number of forced swaps where the players in the very worst positions are forced into other matches, despite the overall result becoming worse. After a dozen or so forced swaps we start doing normal swaps again. This indeed resulted in a slightly better score, but it did make the algorithm take much longer. Since processing is already taking seconds at this point, performance is very relevant. We don't want players to wait half a minute extra just for this algorithm to finish.

I then tried a different approach: I just leave the first result as it is, and start over again but from a different starting point. I semi-randomly generate a completely new match-up and start doing swaps on that. This will also bring us to a local optimum, but it will be a different one that might actually be better than the previous local optimum.

In practice within 5 seconds we can usually do a couple of retries this way (less if there are more players) and then we simply pick the best one we found. This turns out to produce much better results than trying to force ourselves out of a local optimum, so I threw away that approach and instead we just try a bunch of times. To limit waiting times we simply check how long we've been going so far and do another retry only if we haven't spent too much time yet.

To see how good this could get I tried letting my computer run for a whole night, constantly retrying from different starting points. This produced tens of thousands of different match-ups, all at different local optimums. It turns out that the difference between trying a couple of times and trying tens of thousands of times is actually surprisingly small. This showed us that doing just a couple of retries is already good enough.

Downsides

So far I've explained how we do matchmaking and why. Now that Galactron has been running for almost two years in this way it's also a good moment to look back: did our approach work out as nicely as hoped? Overall I'm pretty happy with the result, but there is one big choice in here for which I'm not sure whether it's actually the best one: matching everyone at the same time. Doing this gives our matchmaking algorithm the most flexibility to find the best match-ups, but it turns out that players are spread out over the world even more unevenly than I had estimated beforehand, causing problems here.

For example, if we look at a matchmaking round at 20:00 western European time, then the vast majority of those players will be from Europe and the rest of the players will be spread out over the rest of the world. That means that in a matchmaking round of 100 players, there are only a few Australians or South Americans. Those players won't get a good match in terms of ping because there simply aren't enough players in their region in that round.

Solving this requires having even larger numbers of players per round: I think around 300 would be ideal. However, this means either having extremely long waiting times, or having a gigantic playerbase. We'd love to have a playerbase as large as League of Legends, but unfortunately that's not realistic for all but the biggest hit games. The result is that we chose a middle ground: we wait for those 100 players, which can take 5 minutes or even more, and then we just perform matchmaking and accept that the result won't be as good as we'd want for some people. If the number of players is too low then at some point we just perform matchmaking anyway so that waiting times never go beyond a maximum.

While building Galactron we've found very little information on how the big multiplayer games do their matchmaking exactly, but a talk by a designer of Heroes of the Storm (which I unfortunately can't find anymore on YouTube) suggested that at some point in that game, the system was that a match would be started as soon as it could be created with a good enough match quality. In our case this would mean that if there are 6 players who are similar enough in skill and have a good ping with each other, then the match is started immediately. If it takes too long to fill a match, then the requirements are gradually decreased. At some point a player who has waited too long becomes top priority and just gets the 5 most fitting players that the matchmaker can find, even if match quality is lower than desired.



The benefit of such an approach is flexibility: in areas with lots of players one would get matches much more quickly, while areas with fewer players would get longer waiting times. This kind of flexibility is also nice for pro players: one can make them wait longer so that they only play against others of almost exactly the same skill. Our own algorithm can't diversify like that since players from the whole world are matchmade simultaneously at fixed moments.

In comparison I expect our own method produces slightly better results, because it can juggle with a lot more players at once to find the best match-ups. However, this benefit might not be big enough to weigh up against the benefit of having lower waiting times.

There is one really nice benefit that we get from our fixed matchmaking moments: we can tell the player beforehand exactly how long they'll have to wait for matchmaking to happen. I think waiting is more endurable if you know how much longer you have to wait. Showing how much longer you need to wait is a really nice touch that few other games have.

A direct comparison between the live matchmaking algorithms of Awesomenauts and Heroes of the Storm is unfortunately not possible because Heroes of the Storm has so many more players. Any matchmaking algorithm will do better with more players, so it is to be suspected that regardless of the algorithm, the matchmaking quality in a big game like Heroes of the Storm will be much higher than in Awesomenauts anyway.

Conclusion

Building a matchmaking system starts with defining what good matchmaking is. No algorithm can produce good match-ups if you don't give the computer rules for what that actually means. In this post I've discussed the rules we use, which are mostly based around skill, ping and premades. Depending on what's important for your game you can add more rules or define them differently.

Just keep in mind that the more rules you have, the less important the other ones become, and every rule you weigh heavier makes the others less important. Restraint and balancing are key here. Also, you probably need a while to finetune the rules further once your matchmaking is live, like we've done with the Galactron matchmaker in Awesomenauts by adding the 'opponent variation' rule later on.

New song: Tensor

I've finished recording a new composition! It's a cello trio inspired by minimal music (Philip Glass and such).



Sheet music can be found at music.joostvandongen.com. This contains the version for cello trio and also an arrangement for violin, viola and cello.

This composition started out as something I was improvising while warming up for a Cello Fortress performance in Dublin last year. I had a lot of fun playing repetitive parts with varying rhythms and afterwards I heard from some people who were sitting nearby that it sounded really tense. Good music provokes some kind of emotion so I figured I should turn that little improvisation into a real song.

Recording this one was a challenge since it needs to be so rhythmic and precise to work. It took me a lot of practice and editing but in the end I'm happy with the result. :)

I also had fun making an image for this one: I combined a photo of my own cello with a photo of machinery I found online. Unfortunately I couldn't find the name of the photographer of the machinery, so I'm not able to give credit for that. The picture was creative commons though so using it should be fine.

Now 8 out of 13 tracks for my album are finished. Only 5 more to go and those are all already quite far along. Finishing the album some day, before I'm old and wise, seems doable!

The challenge of finding enough playtesters

I recently watched Jan Willem Nijman's great talk on The Art of Screenshake and noticed an interesting YouTube comment to that video by someone named SquidCaps. SquidCaps mentions that for an unknown developer, it's really hard to find playtesters who actually test regularly. I agree that this gets a lot easier the more well-known you are, but I think it might also help to try a different approach to playtesting. So I figured it would be interesting to discuss how we approach playtesting at Ronimo and how to find playtesters.

Let's start by having a look at SquidCaps' comment. It's quite long so I've selected only the parts that I'm going to reply to:

Heh, "let people play your game and iterate".. quite a bit easier to say when you have plenty of gametesters already in the office.. For solo, unknown developer, having just ONE game tester that suffers 10 minutes per week is too much.. What you need is full game, with menus, high scores save games etc, basically a beta before you get any testers and then you get plenty of them.. When it's still in alpha and the biggest, most revolutionary stuff is happening, then you are alone. Something that developers who are already successful almost always forget; you get plenty of free resources at one point. [...] The truth is that your mates play for a while but without actual team behind you, you can't support them enough, interest dies down and soon, you see that no one downloaded latest build.. [...] I've been on half a dozen playtesting groups with hundreds of members and they all fail.. The sad truth is that no one cares until you are almost done. big teams have people who they employ that can do playtesting and can even afford to pay for playtesting.. [...]"

Playtesting versus QA

Before actually getting into SquidCaps' comment, I'd like to start with making a clear distinction between playtesting and QA (Quality Assurance, not to be confused with Q&A which means Questions & Answers). QA is all about finding bugs, while playtesting is all about making the game more fun, more understandable and finding the right difficulty curve and balance.

QA is usually an extremely boring and repetitive task. For example, in our game Awesomenauts we've had cases where we hired people to systematically test whether all upgrades in the game function correctly. Awesomenauts has around 1200 different upgrades, so you can imagine that systematically testing them all is not a fun job. Another example of something that's done in QA, is trying to walk into walls to see whether collision is correct everywhere. This usually involves running into all walls in a game and is an incredibly monotonous thing to do. Since QA is so little fun, it's usually not done by volunteers or friends, but instead by professional testers who get paid to do this. Often QA is outsourced to specialised companies in low-wages countries. An alternative is of course that the devs do such testing themselves.

The goal of playtesting on the other hand is to figure out whether the game is fun to play, whether players understand how to play the game and whether the difficulty and balance are right. This is a completely different way of approaching testing. Someone who systematically goes through all 1200 upgrades in Awesomenauts is never going to have fun, so QA's way of testing is not going to tell you anything about how fun individual upgrades are to play with. To find out whether something is fun, you need to let testers play in a more natural, unforced way. You can then just observe how they play and ask them afterwards which things they liked and which they didn't.



Now that we have a clear distinction between QA and playtesting, let's get back to SquidCaps' comment. SquidCaps talks about getting people to play new versions of the game every week. For most purposes of playtesting I think you shouldn't just let the same people play every week. Of course it's helpful, since you can ask them questions like "Is the game more fun now than it was last week?", but you won't get a wide diversity of opinions from a small group. Also, these playtesters play with a preconceived notion of the game based on previous playtests, so their opinions will not represent what fresh players will experience.

For these reasons for Swords & Soldiers 2, spread out during development we invited around 120 people into our office so that we could observe them playing. Every few weeks half a dozen people would come in on a Saturday, play for a few hours and share their opinions. We made sure these were different people every time, so that we would get fresh, unbiased opinions.

For figuring out whether the mechanics and tutorial are clear you also need fresh players every time. Anyone who has already played the game can't truly judge whether the tutorial explains it well, since they already know how it works beforehand. Same for difficulty: after practice you get better, so you can't judge anymore whether it's playable for someone who's new to the game. This is also why the devs themselves are horrible playtesters: they know exactly how the game is intended and are usually really good at it, so they can't judge difficulty and clarity.



When to playtest

This is where I totally agree with SquidCaps: playtesting should start early on: "When it's still in alpha and the biggest, most revolutionary stuff is happening." I regularly encounter developers who think you need complete and bug-free gameplay to do your first playtesting, but there's no reason to wait that long. As soon as you've got something playable, you can let others play it.

Sure, in an early stage you probably need to sit next to the tester to explain a lot of stuff, but you can still learn a ton about which parts of the game are fun and which are not. It might even happen that the playtesters don't enjoy the core but really enjoy some other aspects of the game and this might lead you to change the direction of the game altogether. Or maybe they share some great ideas that you didn't think of yet. If you're wondering "Should I wait for the game to be more complete before testing?", the answer is almost always "Nope, just test anyway and see what you can learn!"

Finding playtesters

This is SquidCaps' main point: it's really difficult to find playtesters if you're not successful. I'd like to add to this that it's even difficult to find playtesters when you are successful: at Ronimo we've sold millions of copies of our games, but finding playtesters is still sometimes hard and takes time.

I think the best playtesting happens in person. That way you can see what the other person is doing and ask questions or help out if needed, especially when testing an early version of a game that doesn't contain a tutorial yet and might be full of bugs. That's why SquidCaps' approach of sharing builds online and joining playtesting groups is not something we'd consider until very late in development. We usually only share builds online for players to test in case of betas, like we do with Awesomenauts updates.

Instead, we mostly search in our local communities. For example, I occasionally talk at game dev schools here in the Netherlands. Whenever I do that, I end my talk with asking people to sign up for playtesting. Usually around 20% of the students in the audience do so, so we now have a significant number of email addresses of potential playtesters we can invite. Unfortunately in practice few of them actually respond, but it's still enough to get dozens of playtesters for a game, usually spread out over a bunch of Saturday afternoons.

When our mailing list runs dry, we look further. We've asked around at local game development schools, where students are often eager to visit a real game dev company and play a secret, unannounced game. We've also asked on social media, hoping enough gamers from the Netherlands follow us to actually get some visitors.

In total these usually get us enough playtesters. However, you can go further than that when needed. Here are some examples:

• I know a game company where the devs took an iPad version of their game, went to Gamescom and let people who were standing in line for some big triple-A game play their game. Queuing people don't have anything better to do so it's rather easy to get them to play for as much as fifteen minutes or more.
• Similarly, you can go to a random public space with a laptop and just ask people to play. If you're a student this could be the hall of your own school, or it could be a station, or anywhere really. This requires getting over some awkwardness when approaching strangers, but really, this is very doable.
• If you've got some budget you can also get a booth at a game event like Gamescom or PAX. Booths are not just nice for marketing but also for playtesting. Lots of different people will play your game and you'll get the most honest feedback in the world: the moment they don't like it anymore, they'll just walk away. Painful, but very useful information.
• You can organise local playtesting events together with other devs. Here in the Netherlands Adriaan de Jongh organises PlayDev.Club, which is simply a gathering of local devs who play early versions of each other's games and share feedback. If there's nothing like that in your community, you can organise something like that yourself, as long as you're in an area that has enough game devs.

None of these approaches will easily get us people who play our game for a huge number of hours. However, if our game isn't that fun yet then maybe that shouldn't be our focus and the focus should be on making that first hour super awesome. Once the core game is a lot of fun, it becomes easier to find playtesters who are willing to come back and invest more hours to get to the advanced tactics and pro skills.

While all of these ideas are easier if you're a more well-known developer and are better connected, with enough effort an unknown dev can also find playtesters in such ways. Before we released our first game Swords & Soldiers we also managed to find playtesters, despite being an unknown studio at the time. Finding playtesters takes initiative, creativity and effort, but in most cases it's doable even for those of us who aren't well-known.

These were some of the things we do at Ronimo and that I've heard from other developers. How do you find playtesters? What are your challenges and have you got any clever tricks?

Here's how I made my computer write music

One of my current hobby projects is creating a procedural music system: a computer program that composes and performs music all by itself. It's still a work-in-progress in its early stages, but some recent improvements have gotten it to produce quite interesting music already, so I figured it's about time I share some of my thoughts around how it works. Let's start with a little video that lets you hear the amount of variation it can currently do:



Note that this video contains a selection of the nicer pieces, so it isn't all this good. Most of the other music it currently produces is a bit more boring, or too similar to these fragments. The program is a work-in-progress and it should improve a lot as I spend more time on it.

I started programming this for a rather odd reason: I wanted to practice improvising on my cello over complex chord schemes and figured a program that automatically produces those would do the trick. As usual with this kind of thing, it got out of hand and I've so far spent my time making it cooler instead of playing along to its tunes on my cello. I hope I can expand it to the point where it can be a game soundtrack, or a live streaming radio channel on Youtube that constantly produces new music.

My approach to procedural music is mostly based on my own ideas about composition. I'm deliberately steering away from a lot of common composition 'rules' since I expect that's been done already. I think I'll get something more interesting and more personal if I start from my own ideas instead. While I don't ignore music theory either, I do try to avoid rules like ending a chord progression with the dominant and then going back to the tonic or anything like that.

Just to be clear: my music generator is not an AI or a self-learning system or anything like that.

The procedural music generator consists of a bunch of elements that together produce the music:

Chords, rhythms and scales
To 'teach' my program basic music theory I've created a bunch of text files that define a lot of common and less common chords, rhythms and scales. You can see which it's using in the video: it might for example choose to play a C major chord in 3/4 rhythm.



Structure generators
The first thing needed to create a piece of music, is a basic structure. This part of the program randomly chooses the chord progression, the rhythm and the scales. It also chooses how individual instruments are allowed to deviate from the rhythm, so that there's some consistency between instruments without requiring them to do the exact same thing.

Instrument layer generators
These generate the notes for specific instruments. Each category of instruments has a role to fulfil and its own specific algorithm for that. For example, the generator for drums is completely different from the generator for bass. Most of these generators are still very basic so there's plenty of room for improvement there. A lot of the variation in the video above comes from having different combinations of instrument layer generators. For example, some have drums, others do not. I expect that having a lot of layer generators is where my procedural music will get most of its variation. Currently I have five, but I'd like to create at least a dozen. The most important missing layer at the moment is one for actual melodies, which is probably also the most challenging one to get right.

VST instruments
Actually performing the music is done using VST instruments. VST is a standard for digital instruments that is used by a lot of programs on Windows. A VST file is basically just a DLL and I've coded a simple music player that can handle them. For each instrument layer I'd like to have several VST instruments that can play that layer, so that I can get different sounds. Currently most of it sounds very digital, so it would be nice to also have VSTs for other types of instruments, like acoustic drums and guitars.

Song structure
This is an element that's currently completely missing: at the moment all music played by my music generator is simply a loop of 4 to 12 bars. I want to program systems for song structures with verse/chorus/bridge, but also for endlessly progressing music and for music that for example slowly builds up to a climax.

Carefully restricted randomness
All the systems in this generator contain a lot of randomness, but the randomness is limited to specific rules I've come up with. If those rules are too free then the result is noise, not music, while if the rules are too strict then the resulting music will always seem same, so carefully balancing the randomness is a big challenge here.



For future improvements I'd like to add more instrument layers and refine the current ones, add song structures and add more VST instruments. Since I've recently become a dad I don't have a whole lot of time to work on this, so I expect progress will be very slow. I hope to include a first basic version of my procedural music generator as a bonus feature in the home edition of Cello Fortress, whenever that's actually finished.

Let's conclude with a question: do you know any communities for open source or free VSTs? There are plenty of VSTs that can be downloaded for free, but in many cases they just specify that they're free to use, not free to distribute with commercial software. I've so far had a hard time finding usable instruments or getting into contact with (hobby) instrument programmers who might be willing to allow me to include their instruments. Leave a comment if you've got suggestions or are a digital instrument programmer yourself.

Entertaining players while waiting for matchmaking

In a game where high quality matchmaking is important (like competitive team-based games), waiting times to find suitable opponents are often unavoidable. Today I'd like to discuss the problems we had in Awesomenauts with our initial approach to this and how we made waiting a bit less boring later on.

Until the launch of the Galactron update in 2016, this is how it worked in Awesomenauts: when you started searching you got into a matchroom right away. You selected your character, and then you had to wait in the loading screen until the match was full with 6 players. This could take several minutes and there was no interaction possible whatsoever: just a loading screen that says the match isn't full yet. To show progress we did have six tickboxes that showed how many players had joined and whether they had already selected their characters, but that was it.



A static screen with no interaction possible is probably the most boring type of waiting imaginable. Compare this to current Awesomenauts, where you wait in the menus instead of in a loading screen. Still not ideal, but this means that while waiting you can chat with other players, check out the skills and items of all characters and watch replays and live matches. Awesomenauts has a system where it lists the ten most exciting matches happening right now and also automatically selects a match of the day that you can watch. We hardly advertise watching replays while waiting though, so I think many players don't realise that you can watch a live match or replay while waiting for matchmaking.

An important thing to realise when thinking about waiting times is that on PC, players can simply alt+tab and browse the internet while waiting. This isn't possible on console, but there's always that other option: mobile phones. I don't have any statistics on this, but I wouldn't be surprised if a lot of players ignore menus, replays and chat during waiting times and just randomly browse the internet instead.

While I think current Awesomenauts is a huge improvement in terms of diversions while waiting for matchmaking, I don't think it's ideal. Waiting times for a proper match can be rather long (which is unavoidable if you don't have a giant playerbase and prefer better match-ups over quicker matchmaking) and clicking through menus isn't the best entertainment in the world. I like the solution that PlayerUnknown's Battlegrounds has: players get thrown into a little area where they can walk and jump around, punch each other, voice chat and generally goof around a bit. It's still clearly a waiting area, but it's so much more fun and interactive than a menu or a replay.



Even better is to have some kind of mini-game while waiting. During early development of Awesomenauts we experimented with having a little death match arena where you played until the real match started. It's similar to what PlayerUnknown's Battlegrounds does, but even more game-like since it's real deathmatch. I can't quite remember why we decided not to put this into the game, but I imagine the mean reason was probably a lack of time: we were making a really big game with a small team and needed to cut features in order to finish it before funds ran out.

There might also have been concerns internally that it might be frustrating to be in a deathmatch game and then we thrown out into the main game all of a sudden. Knowing that it can end any moment might potentially make that deathmatch more frustrating than fun. In Swords & Soldiers we solved this frustration by letting the player do single player while waiting and storing the state of that single player as soon as an online match started. This way the player could continue the single player session after having finished the online match. However, this approach doesn't work with an online deathmatch. Still, I think having gameplay instead of menus is probably preferable anyway.



Despite all of this I do think we had some nice touches in the original waiting screen in Awesomenauts. One is that we showed the maximum waiting time left. Waiting for a few minutes is a lot more acceptable if you actually know how long you're going to be waiting than if you don't know whether you need to wait one more minute or ten. If after a few minutes the match was still not full, it would just start with fewer players and add bots to complete the teams. This way the player had a guarantee that when the timer ran out, gameplay would definitely start.

In the new matchmaking system we also want players to know how long they're going to wait, so we still show a number that says how long it takes until the next matchmaking round happens. Only now it's shown in the main menu instead of in the loading screen. This can be frustrating if the time is long (worst case it can be as much as 7 minutes), but at least you know what you're getting into.

In the waiting screen of the old version of Awesomenauts you also heard the theme song of the character you had selected. Every character in Awesomenauts has their own jingle and this adds loads of personality to the game. Since this was basically the only entertainment during this waiting screen we even made these songs longer: jingles for the initial characters were only around 20 seconds, while later on we started aiming for 1:30 minutes to reduce repetition.

In the current system where you don't select a character until the match is full we do miss this great opportunity to let the character jingles shine. Instead you now only hear a short bit of the character jingle after selecting the character. The other way to hear these jingles is in the menus while browsing character stats. Having less focus on these awesome theme songs is a pity.


Ideally your multiplayer game has an infinite number of players and you can find equally skilled opponents right away. However, very few games live in this ideal world, so everyone else needs to think cleverly about how their matchmaking works. Just building basic matchmaking and assuming it'll work out isn't going to cut it. If you're interested in reading more on this topic I recommend reading my previous post on designing matchmaking for non-gigantic communities as well.

In the end I think the main reason we ended up with that waiting screen in Awesomenauts for years is that we underestimated how hardcore our community would be. We had designed Awesomenauts as a casual, fun alternative to the other MOBA games. We thought starting with bots right away and adding players as soon as they came online was way more fun than waiting for a full match. Our players disagreed: joining a match that's already in progress is a disadvantage since the bots might have already lost some ground by the time you replace them. Matchmaking issues quickly became the number one complaint about Awesomenauts in our community, so we increased the waiting time before a match actually starts to 2 minutes (or less if the match is already full). This did increase the chance of everyone being there at the start, but we still got complaints about matches not always being full, so we increased the waiting time even further to 4 minutes.

Since we thought we were making a more casual game we hadn't anticipated that our players would prefer long waiting times to be able to play in a more competitive way. We did adjust the system based on this feedback, but the result was waiting in a loading screen. I'm glad we got to improve that situation when Galactron launched later on.

Sandrider

Here's my newest composition: Sandrider! It's a cello trio that revolves around fast arpeggios. At a whopping 5 minutes this one was a LOT of work to record and edit to get it to sound just right. But it was worth it: I'm really happy with the result. :)



Sheet music can be found at music.joostvandongen.com, including arrangements for violin, viola and cello, plus solo versions for if you don't happen to have a cello trio around.

This track was inspired by the way Ernst Reijseger plays in his beautiful song Strabismo Di Venere (from the album Colla Voche). He plays really fast arpeggios there by sweeping over the four strings. I experimented with this way of playing quite a bit and discovered that it also works really well when you play a bit louder than what Reijseger does in Strabismo Di Venere.

I played around with this technique in the live improvisations that djembe player Rene Derks and I did to the game Journey. I liked the sound of that so much that I decided to write a song around this. Hence the name: there's a lot of sandriding in Journey! You can hear the improvised version of this idea at 1:50 in this video of a live performance we did last year.

The limitations of matchmaking without server logic

I've previously explained how Steam, Microsoft, Sony and Nintendo all offer similar generic matchmaking systems based on rooms. These systems are great for quickly getting things going and are fine for most smallish games. However, if matchmaking is very important for your game and the requirements for matchmaking become more complex, these generic systems turn out to be pretty limiting. Today I'd like to discuss how we tried several approaches to get the best out of such generic systems in our game Awesomenauts and how the problems we encountered ultimately led us to develop our own matchmaking servers altogether.

Keep in mind that whether these problems are truly important depends on the game. If your game is a bit more casual, or has fewer players per match, or less focus on online multiplayer, or allows late-join, then the requirements for matchmaking become a lot less stringent. Depending on how demanding the matchmaking for your game is, none of these problems might be enough reason to skip the great convenience of using an existing matchmaking system.



The main problem is that these generic matchmaking systems don't allow serious logic to run on the server. The server keeps a list of gamerooms that the player might join, but the decision which room to actually join is made by the client. With this in mind, let's have a look at some of the client-based matchmaking algorithms we tried in Awesomenauts.

The 'growing search range' approach

The standard approach to client-based matchmaking is to have a growing search range. The client starts by asking the server for a list of all the rooms that can be joined and then checks whether any of those rooms are near geographically (to achieve low ping) and are similar in terms of skill. A good starting point might for example be that the other players in the matchroom need to be in the same country/state and differ by at most 500 skillpoints (in a system where 10,000 is the average skill of all players). If several suitable rooms are found, then we join the one closest.

This algorithm is simple enough, but the challenge is what to do when no suitable rooms are found. If you're adamant on always having high quality match-ups, then you might choose to simply wait for more suitable players to appear. However, unless your game has an enormous player count this probably results in really long waiting times for the user, or even in never finding a full match at all.

Therefore we increase the search distance over time. For example, we might double the allowed geographical distance and skill difference every 20 seconds. We keep doing this until we've found a suitable match. If at the biggest search range we still haven't found anyone to play with, then we simply keep waiting and searching.

An important note here is that while searching, the player also has her own room open for others to join. As soon as someone joins your room, you stop searching and just wait until enough players have joined for the match to be started. If you join someone else's room, you close your own room. To avoid problematic edge cases like two players joining each other's rooms simultaneously we add a simple rule: if the other room has only one player in it then we only join it if that room has a lower roomID than our own room. This may seem limiting but in practice doesn't matter much: if I can join your room because you have similar skill, then you can (eventually) join my room as well. It doesn't matter who joins who as long as we end up together.

This is roughly the matchmaking algorithm that Awesomenauts had at launch. What we didn't know back then, is that in many cases the result is little better than just joining a random room. For example, let's say a new player starts searching every 5 seconds. In a game with matches of 20 minutes, this means we have 240 concurrent players, which is pretty nice for a smaller indie game (multiplayer games that are an okay success on Steam are generally in the range of 400 to 2000 concurrent players). In the case of Awesomenauts a full match needs 6 players, which means it would take 30 seconds for a complete group to start searching. For decent matchmaking we don't want to play with just anyone though: we want a good match in terms of ping and skill. Only 1 in 4 players will be even remotely acceptable to play with (in practice probably even less), so we need to wait 2 minutes for enough players for a match. However, this won't happen: by the time we've waited that long we will have grown our search radius so far that we will have joined some other match already.

The result is that this algorithm isn't as good at finding a good matchup as one might think initially. We tried playing around with how quickly the search range grows and such, but we couldn't find a way that achieved a big enough improvement.

League-based matchmaking

Back then we got a lot of complaints about matchmaking not producing good match-ups, so we concluded that we needed something different. What we came up with was to add a league system to Awesomenauts and limit matchmaking based on that. We added this to the game in September 2012, a few months after launch. The idea is that we divide the leaderboards into 9 leagues, based on player skill. These leagues weren't just intended for matchmaking, but also for the player experience: it's cooler to be in league 2 than to be in place 4735, even though that might actually be the same thing.



The matchmaking rule we combined with these leagues is that players could only join matches in the 3 nearest leagues. So a league 4 player could join matches that are leagues 3, 4 or 5. A league 1 player (the top league) could only join matches in leagues 1, 2 and 3. Having such a hard limit should keep players from experiencing extremely big skill differences with their opponents or teammates.

For this to work you need to know the player's skill pretty well, so an important question is how well the game actually knows each player's skill. This is an important issue in any matchmaking system and is such a big topic that I'm not going to discuss this today. For today's blogpost let's just assume that the game has a somewhat decent idea what a player's actual skill is.

Another important issue is what to do if there are few players online. Having hard limits on who can join who means that in some cases you might not find opponents quickly enough. For this reason we stretched the allowed league range a bit further when few players were playing at that specific moment. The Steam API contains this information so implementing this is simple.

An easy mistake here is to simply split the leaderboards evenly. So for example if there are 90,000 players in the leaderboards, then numbers 80,001 to 90,000 are league 9. However, this doesn't work: some players play much more than others and players who stopped playing are still in the leaderboards. If these would be evenly spread out over the community this wouldn't be a problem, but of course they aren't: top players play much more than bottom players.

Our solution was that we measured how many matches were actually being played each day in each league and adjusted the league sizes based on that. Our implementation was bit clunky so we had to adjust this by hand occasionally, but it worked most of the time. The result is that league 2 is only a few percent of the leaderboards while league 9 is around 55 percent, resulting in equal numbers of matches being played every day in each league.



The league system was a big improvement for the matchmaking in Awesomenauts: not only did it make the matchmaker much better at matching similar players, it also provided a fun extra reward system, since wanting to be in a certain league is a fun challenge.

One specific problem with league based matchmaking is that going up a league makes too big a difference. If you go from the top of league 3 to the bottom of league 2 you suddenly get way better opponents, even though your own skill might have only marginally improved. Also, the skill difference between the top of a league and the bottom of that same league can be really huge, especially in the top leagues. While our matchmaker also looked for the best room to join in terms of exact skill (besides just the league requirements), it wasn't very good at this because of the problems with the growing-search-region algorithm I described earlier in this blogpost. A way to lessen this problem is to have more and smaller leagues, but we felt having dozens of leagues makes league climbing less fun for players.

The lack of server logic

While leagues were an improvement, this approach didn't fix the big problem that there's no logic running on the servers. Each client decides for themselves based on incomplete information. This is very limiting to how clever your matchmaking can be. There are lots of situations in which this algorithm will fail to produce optimal match-ups. Here's an example:



As you can see, in this case the algorithms described above fail to find the best possible match-up. Perfect matchmaking is impossible without huge player counts, but the matchmaker should do its best to find the best combinations with what's available.

Below is another example of a type of situation that this algorithm doesn't handle well. This one shows that this particular algorithm is particularly bad at matching premades with other premades: as soon as a single solo player joins, there's no room anymore for another premade that might start searching a little bit later.



Undoubtedly some super complex distributed algorithm is possible that can always find the optimal match-ups without any logic running on the servers. However, at that point the complexity of the algorithm becomes so high and debugging so difficult that I think running the matchmaking logic on a server instead is a much more viable solution. So we started developing our own matchmaking system (called Galactron) with our own servers. This was added to Awesomenauts in 2016.

In this post I've shown a number of problems we've encountered with generic room-based matchmaking systems and how we tried different approaches to work around those. However, not all of the issues with our early matchmaking approach were caused by the limitations of generic room-based matchmaking. Some issues were caused by how we had actually implemented our side of it. Those make for an interesting read by themselves so my next blogpost will be about the things we could have done better within the confines of generic room-based matchmaking.