Sunday 28 January 2018

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.

Wednesday 24 January 2018

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.

Sunday 7 January 2018

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.