Sunday, 1 March 2020

How we made particles twice as fast through cache optimisation

Cache optimisation is one of the most hardcore, low-level topics in game programming. It's also a topic that I haven't been very successful with myself: I tried optimising for cache efficiency a few times but never managed to achieve a measurable improvement in those specific cases. That's why I was quite intrigued when our colleague Jeroen D. Stout (famous as the developer of the experimental indie game Dinner Date) managed to make our particles twice as fast. What's the trick? Jeroen was kind enough to tell me and today I'll share his approach. Since it's such a hardcore topic, I'll start by giving a general overview of what cache optimisation is in the first place.



Let's have a look at computer memory, or RAM. Computers these days have gigabytes of very fast memory that's used to store whatever the game or program needs to use on the fly. But is that memory truly so fast? Physically, it's a separate part of the computer. Whenever the processor needs to get something from memory, it needs to be transported to the CPU. That only takes a tiny bit of time, but a modern processor can perform billions of operations per second. At those kinds of speeds, a tiny bit of time is actually a lot of operations that the processor could have done during that time. Instead, it's waiting for something to come out of memory.

This is where cache comes in. Cache is a small amount of even faster memory that's directly on the processor and is thus a lot faster to access than normal memory. So whenever something is already in cache, the processor doesn't have to wait for it (or at least not as long) and can keep working. According to this article cache can be up to 27 times faster than main memory.



As programmers we generally don't have direct control over what's in cache: the processor tries to utilise the cache as efficiently as possible by it's own volition. However, depending on how we access memory, we can make it a lot easier for the processor to use cache efficiently. This is where cache optimisation comes in.

The goal of cache optimisation is to structure our code in such a way that we use cache as much as possible and need to wait for memory as little as possible. Whenever the processor needs to get something from memory and it's not already available in cache, that's called a cache miss. Our goal is to avoid cache misses as much as possible.

To be able to avoid cache misses, we need to know a little bit about how cache works. I'm no specialist in this field, but we only need a small bit of knowledge to already understand how a lot of cache optimisations work. These are the basic ideas:
  • Data is transferred from memory to cache in blocks. So whenever you're using something, the memory directly around that is likely also already available in cache.
  • Cache is often not cleared immediately. Things you've just used have a good chance of still being available in cache.
  • The processor tries to predict what you'll use next and get that into cache ahead of time. The more predictable your memory access, the better cache will work.

These three concepts lead to a general rule for writing code that's efficient for cache: memory coherence. If you write your code in such a way that it doesn't bounce all over memory all the time, then it will likely have better performance.

Now that the basics are clear, let's have a look at the specific optimisation that Jeroen did that halved the CPU usage of our particles.



To avoid dumping huge amounts of code here, I'm going to work with a highly simplified particle system. Please ignore any other inefficiencies: I'm focusing purely on the cache misses here. Let's have a look at a very naive approach to implementing a particle system:

struct Particle
{
   Vector3D position;
};

class ParticleSystem
{
   std::vector<Particle*> particles;

   void update()
   {
      for (int i = 0; i < particles.size(); ++i)
      {
         particles[i]->position += speed;
         if (shouldDestroy(particles[i]))
         {
            delete particles[i];
            particles.erase(particles.begin() + i);
            --i;
         }
      }
      while (shouldAddParticle())
      {
         particles.push_back(new Particle{});
      }
   }
};

This code is simple enough, but if we look at it from a cache perspective, it's highly inefficient. The problem is that every time we create a new particle with new, it's placed in a random free spot somewhere in memory. That means that all the particles will be spread out over memory. The line particles[i]->position += speed; is now very slow, because it will result in a cache miss most of the time. The time the processor spends waiting for the particle's position to be read from memory is much greater than the time that simple addition takes.



I knew that this would give performance problems, so I immediately built the particles in a more efficient way. If we know the maximum number of particles a specific particle system can contain, then we can reserve a block of memory for that on startup and use that instead of calling new all the time.

This results in a bit more complex code, since we now need to manage that block of memory and create objects inside it using placement new. In C++, placement new allows us to call a constructor the normal way, but use a block of memory that we already have. This is what the resulting code can look like:

struct Particle
{
   Vector3D position;
};

class ParticleSystem
{
   unsigned char* particleMemory;
   std::vector<Particle*> particles;
   int numUsedParticles;

   ParticleSystem():
      numUsedParticles(0)
   {
      particleMemory = new unsigned char[maxCount * sizeof(Particle)];
      for (unsigned int i = 0; i < maxCount; ++i)
      {
         particles.push_back(reinterpret_cast<Particle*>(
            particleMemory + i * sizeof(Particle)));
      }
   }

   ~ParticleSystem()
   {
      delete [] particleMemory;
   }

   void update()
   {
      for (int i = 0; i < numUsedParticles; ++i)
      {
         particles[i]->position += speed;
         if (shouldDestroy(particles[i]))
         {
            //Call the destructor without releasing memory
            particles[i]->~Particle();

            // Swap to place the dead particle in the last position
            if (i < numUsedParticles - 1)
               swap(particles[i], particles[numUsedParticles - 1]);

            --numUsedParticles;
            --i;
         }
      }
      while (shouldAddParticle() && bufferNotFull())
      {
         //Placement new: constructor without requesting memory
         new(particles[numUsedParticles]) Particle{};
         ++numUsedParticles;
      }
   }
};

Now all the particles are close to each other in memory and there should be much fewer cache misses when iterating over them. Since I built it this way right away, I'm not sure how much performance I actually won, but I assumed it would be pretty efficient this way.

Nope.

Still lots of cache misses.

In comes Jeroen D. Stout, cache optimiser extraordinaire. He wasn't impressed by my attempts at cache optimisation, since he saw in the profiler that the line particles[i]->position += speed; was still taking a disproportionate amount of time, indicating cache misses there.

It took me a while to realise why this is, but the problem is in the swap-line. Whenever a particle is removed, it's swapped with the last one to avoid moving all particles after it one forward. The result however is that as particles are removed, the order in which we go through the particles becomes very random very quickly.



The particles in our example here are really small: just a single Vector3D, so 12 bytes per particle. This means that even if we go through the particles in random order, we might occasionally still be staying in the same cache line. But a real particle in the Secret New Game (tm) that we're developing at Ronimo has much more data, like speed, scale, orientation, rotation speed, vibration, colour, and more. A real particle in our engine is around 130 bytes. Now imagine a particle system with 100 particles in it. That's a block of memory of 13,000 bytes. Hopping through that in random order is much more problematic for cache!

Thus, Jeroen set out to make it so that updating particles goes through memory linearly, not jumping around in memory at all anymore.

Jeroen's idea was to not have any pointers to the particles anymore. Instead we have that big block of memory with all the particles in it, and we store the indices of the first and last currently active particles in it. If a particle dies, we update the range of living particles and mark the particle as dead. If the particle happens to be somewhere in the middle of the list of living particles then we simply leave it there and skip it while updating.

Whenever we create a new particle, we just use the next bit of memory and increment the index of the last living particle. A tricky part here is what to do if we've reached the end of the buffer. For this we consider the memory to be a ring buffer: once we reach the end, we continue at the start, where there's room since those particles will have died by now. (Or, if there's no room there, then we don't create a particle since we don't have room for it.)

The code for this isn't that complicated, but it's a bit too much to post here. Instead, I'm just going to post this scheme:



Compared to my previous version, Jeroen managed to make our particles twice as fast with this approach. That's a pretty spectacular improvement and shows just how important cache optimisation can be to performance!

Interestingly, my first hunch here is that this optimisation is a bad idea since we need to touch all the dead particles in between the living ones to know that they're dead. Worst case, that's a lot of dead particles. In fact, when looking at computational complexity, the worst case has gone from being linear in the number of currently existing particles, to being linear in the number of particles that has ever existed. When I studied computer science at university there was a lot of emphasis on Big O Notation and complexity analysis, so to me this is a big deal.

However, as was mentioned above, accessing cache can be as much as 27 times faster than accessing main memory. Depending on how many dead particles are in the middle, touching all those dead particles can take a lot less time than getting all those cache misses.

In practice, the lifetimes of particles don't vary all that much. For example, realistic particles might randomly live between 1.2 seconds and 1.6 seconds. That's a relatively small variation. In other words: if there are dead particles in between, then the ones before them will also die soon. Thus the number of dead particles that we need to process doesn't become all that big.

The big lesson this has taught me personally, is that cache optimisation can be more important for performance than Big O Notation, despite that my teachers at university talked about Big O all the time and rarely about cache optimisation.

EDIT: Several commenters on Twitter and Reddit suggested an even simpler and faster solution: we can swap the dead particles towards the end of the list. This removes the overhead of needing to skip the dead particles and also removes the memory that's temporarily lost because dead particles are in the middle. It also simplifies the code as we don't need to handle that ring buffer anymore.

For further reading, I would like to again recommend this article, as it explains the principles behind cache lines very well and shows some clever tricks for optimising to reduce cache misses.

As a final note, I would like to also stress the unimportance of cache optimisations. Computers these days are super fast, so for the vast majority of code, it's fine if it has very poor cache behaviour. In fact, if you're making a small indie game, then it's probably fine to ignore cache misses altogether: the computer is likely fast enough to run your game anyway, or with only simpler optimisations. As your game becomes bigger and more complex, optimisations become more important. Cache optimisations generally make code more complex and less readable, which is something we should avoid. So, use cache optimisations only where they're actually needed.

Have you ever successfully pulled off any cache optimisations? Are there any clever tricks that you used? Please share in the comments!

Sunday, 16 February 2020

New song: Approach of the Derelict Research Station

Here's my newest song: Approach Of The Derelict Research Station! This one is not just my newest song, but also one of the oldest: it's an evolution of a song that I wrote some tens years ago, then called Space War X9.

Two years ago, when I decided that the songs I was writing at that time should form an album together, I wondered what else should be on it. I've always been quite fond of Space War X9 and wanted to include it, but it was lacking an important ingredient: cello! On my album I want all the songs to feature my cello in a prominent role. However, back when I made Space War X9 I had no idea how to record my cello in a way that made me happy with the results, so I mostly composed purely electronic music.

Adding cello was an interesting challenge: the tonality of Space War X9 turned out to be rather odd and none of it had been written with an additional instrument in mind. Still, somehow the cello ended up being the lead instrument through most of it. Listening to the new version, it now feels weird that it once lacked cello, since the cello is now the lead instrument during most of the song.

This song is also the first one to be released with narration. On my album all the songs will tell a story together. Voice actor Chris Einspahr has graciously lent his voice and I love how he acts. His voice also blends very well with the music. Check it out:



At the end of the song there's a bit of crazy cello improvisation. I often do these kinds of intense gliding notes during jam sessions but this is the first time I dared include one in a real song. I'm quite happy with how that turned out, and it nicely captures the craziness of the fight portrayed at the end of the song.

If you'd like to play this song yourself and give your own twist to the crazy ending, you can find cello sheet music for it on music.joostvandongen.com, as well as a version of the song without the cello, to play along it.

The art in the video is by Karen Papazian, who allowed me to use her existing piece "Not much left". While it wasn't originally drawn for this song, it perfectly fits what I imagined the setting to be.

Finally, I should mentioned the samples I used here. I found these samples on FreeSound.org and it's great that most audio on this website requires nothing more than attributing the original artists and then you can use it. The samples used in Approach Of The Derelict Research Station were made by 211redman112, foxraid, lezaarth, TMPZ_1, Ideacraft, Deathscyp, rene___, steshystesh, jonccox and lollosound. (Gotta love the kinds of named people give themselves on the internets!)

This leaves only one song to finish for my album, almost there!

Sunday, 2 February 2020

Five important realisations about game balance

The games we've so far made at Ronimo have all featured a heavy emphasis on competitive multiplayer. Designing, testing and iterating these games, especially our biggest hit Awesomenauts, has taught us many things about balancing. Today I'd like to share some of the most important lessons we've learned along the way.

1. Overpowered is much worse than underpowered


At first glance one might think that in game balance, underpowered and overpowered are equally bad: they both mean something is badly balanced and needs to be improved. This is true, but in practice overpowered things turn out to have way more impact than underpowered ones.

The reason for this is that players tend to flock to whatever is strongest and use only that. For example, Awesomenauts has 34 characters. If 3 of those would be underpowered, then most players wouldn't play those, leaving 31 valid characters. That's still plenty of choice and variation. On the other hand, if 3 characters were overpowered, then players would play only those 3 and would ignore the rest. That would make the game very repetitive and turn stale quickly.

This knowledge can be used as a crude tool in cases where no better solution is available. For example, if something is overpowered but only under certain circumstances, then you might choose to nerf it until it's okay under those circumstances only and is underpowered in all other situations. This way at least it isn't dominating the game anymore.

2. Variety always adds imbalance


A game with just one weapon on just one symmetrical map will pretty much automatically be balanced. Even if only because all players are in exactly the same situation. Such a game would however probably not just be balanced, but also be boring. So we need to add variety: more weapons, more maps, more items, more builds, more everything. Maybe even asymmetrical maps. The key thing to realise when doing this, is that as the game becomes more complex, 'perfect' balance becomes ever more difficult to achieve. This quickly gets to the point were 'perfect' balance is impossible, and every bit of variation you add makes the game a bit more unbalanced.

Let's look at a really simple example: walking speed. Let's say some characters are fast and others are slow. This gives the slow characters a disadvantage that can be balanced by giving them more health and damage. However, now we also add maps of different sizes. On a bigger map, the disadvantage for the slow characters will be bigger than on a small map. This is because if the arena is small, slow characters can get to the other side fast enough anyway. No amount of health or damage tweaks will fix this, since it differs per map.



One solution to this can be found in our game Swords & Soldiers 2. There in matchmade online matches, we only use certain maps: the ones that we feel are most balanced. On the other hand, when you invite a friend to play, you can choose from all maps, including a bunch of pretty weird ones. Those might be less balanced, but they add a lot of spice and fun. Depending on how much you want to appeal to players with a competitive mindset, you can choose to include those varied but imbalanced maps, or not.

3. Competitive players often dislike randomness and luck


When Awesomenauts launched, the game had random crits, which dealt a lot of extra damage. This added surprise and suspense: every hit might be extra strong! It also means that even if the opponent is better than you, you might occasionally win because you got lucky. This makes a game a lot more friendly for beginners. An extreme example of this can be found in Mario Kart: this game includes a lot of randomness. Combined with a bunch of catch-up mechanics, Mario Kart is a game where occasionally a n00b can beat a pr0.

However, randomess also adds bad luck: sometimes you clearly outplay an opponent and still lose, because the enemy got lucky and landed several crits in a row. In a sense this might feel nice: since the opponent clearly just got lucky, you don't need to blame yourself for losing. Many competitive players however don't want this to factor into the equation. They want a very simple thing: the best player should win. "If I practice more and get better, then I should always win." In the years after release many players in the Awesomenauts community got better and more competitive, to the point where a lot of players really wanted the random crits to be removed from the game. For this reason we ended up changing crits into a predictable system where simply every third hit deals more damage.



4. Balance automatically becomes worse over time


Even if you think the balance in your game is in a good place, by simply leaving it as it is for a while, it will deteriorate. The reason for this is that as time passes, players get better at the game, learn new tricks and talk to each other. This changes how the game is played, thus also changing how the balance is experienced. Usually not for the better: as time progresses and no balance tweaks are made, balance usually becomes worse.

One example we've seen with Awesomenauts was that at some point after a few months of stable balance, one specific team discovered a new tactic that was super strong. This tactic had been possible for months, but somehow no one had found it yet. This tactic was then first used in a tournament, where that team gloriously beat everyone else and won. After the tournament, news spread like wildfire and suddenly this tactic was used in almost every match. We had no choice but to quickly do a balance patch specifically to nerf this one particular tactic. (The fact that our game is deep enough that players can discover new tactics this way is one of the things I'm most proud of in all of my career as a gamedev.)

Another example of balance getting worse over time might not even be caused by something actually being way too strong. Maybe there's something that's just slightly overpowered, so mildly that it really doesn't matter. As time passes, players write guides and talk about the best tactics. They will point each other at this subtle advantage, causing more and more people to use it. Even if the advantage is really small, or, even more extreme, even if the advantage doesn't exist and players are just imagining it, this still ruins the game for the simple reason that everyone starts doing the same thing. This makes the game predictable and boring.

Sometimes you get lucky and players start responding to that imbalance. Maybe an underpowered character happens to be really strong in that particular situation. Since that situation now happens so often, that underpowered character is suddenly super strong in most matches, causing lots of players to choose him. This makes the dominant strategy shift naturally from one thing to another, adding variation and fun. I've been told some games in the Super Smash Brothers series have balanced excellently for this: as soon as one character becomes dominant, its counter becomes extra interesting and lots of players start playing the counter, at which point the counter of the counter becomes useful, etc. This causes the balance to slowly but constantly shift.

5. 'Perfect' balance is impossible


The final point I'd like to share today is both soothing and intensely frustrating: for any game that has significant complexity and variation, perfect balance is impossible. This is a soothing thought in the sense that it makes you realise that even if you were the best game designer in the world, your game would still not have perfect balance. It's also frustrating, because of course the goal of the game designer is to make the balance really good. Knowing that the balance will never be truly fantastic makes balancing a frustrating experience.

So, why is 'perfect' balance not possible? I've already mentioned above that as more variation is added, it becomes impossible to make all options equally strong under all circumstances. But there's more. What about players of different skills? Some characters/weapons/maps are bound to be more difficult to play than others. The result is that for beginners, the balance will be different than for pros. And what about simply different tastes? Some players prefer fun and variation, while other players prefer predictability and skill. The balance can't make both groups perfectly happy. Combined, all of these elements make it impossible to achieve 'perfect' balance.

This post has shared some of the things we've learned through the years about balance. What are your most valuable or most surprising insights regarding balance?

PS. Some of the topics in this blogpost have been discussed in more detail in previous blogposts. If you'd like to read more, have a look at the following posts:

Sunday, 27 October 2019

New song: A Century Flies By

I'm slowly inching closer to finishing my album and today I have tangible proof of this: a new song is finished! This one is called A Century Flies By and, as the title suggests, it's an intermezzo on my album in between two time periods. This one brings the story from the middle of the 20th century to the 21st century.



The violin in this song was played by Mijnke van der Drift and the drums were played by John Maasakkers. I already knew that instruments like violin and my own cello need to be real, but now that I've worked with real drums on one of my songs I also know that computer drums are just unacceptable in comparison. Or at least, they are when I make them: making computer instruments sound natural and good is an art in itself and it's not one I've mastered or want to put the time in to master. I'd much rather work with real musicians and instruments. Mijnke and John did a great job and I thank them for their contributions. I expect you'll hear both of them in more of my songs later on.

Sheet music for cello and violin can be found at music.joostvandongen.com. This also includes recordings of the song without the cello, without the violin and without both, to play along to. If anyone ever happens to play one of my songs, then I'd love to hear from them as that would be really awesome!

This song is the brother of my previous one: A Century Sails By. I really liked that one and wanted to extend it into a longer song. Thus today's new song started out as the second half of A Century Sails By. However, I just couldn't get the two halves to feel like one song. Around the time when I was stuck on how to make both halves gel with each other I happened to listen to Arena's awesome album Songs From The Lion's Cage. In between the longer songs on this album there are shorter ones called Crying For Help 1 to 4. I really like this idea of having intermezzos on an album that are linked to each other and figured I could do something similar here. So I split the two halves of A Century Sails By and made them separate short Songs on the album.

Since they're so strongly tied to each other, here's A Century Sails By again for comparison:



Only two more songs left to finish for the album, and then a lot of work around making it a real album instead of just a list of songs. Things that still need doing include final mixing and mastering, the cover, making a little booklet and maybe hiring a narrator for the story bits. The two final songs that I still need to finish are among the most ambitious of the album and they have nice long names, so I figured I'd end today's post with a little teaser in the form of their titles:

  • Then the Halls Were Empty... and I Turned It On!
  • Approach of the Derelict Research Station

Friday, 16 August 2019

Beginner balance versus pro balance

Game balance is often approached from the angle of the pro-gamer: how strong are things when used by a skilled player? However, the balance as it's experienced by beginners is equally important, since a large portion of the playerbase will never reach pro skill levels but will still want to have a fun experience. Today I'd like to discuss three different approaches we've used in our games Awesomenauts and Swords & Soldiers II to make the gameplay fun for beginners but also balanced for experienced players.

The big challenge here is that in a complex game with varied characters/weapons/factions/etc. it's nearly impossible to achieve perfect balance under all circumstances. Balance is influenced by almost everything and if you want variation, then that variation is undoubtedly going to upset the balance. For example, if some characters are faster than others, then having maps of different sizes can greatly change the balance on one map compared to another. The alternative is to make all maps the same size, but that's boring. For this reason balance is a moving target that you're constantly trying to get closer to but a certain amount of imbalance is (grudgingly) accepted in almost every game.



To make a competitive game fun for players of all skill levels, the ideal situation is to make it balanced for pro players, intermediate players and beginners alike. An example of striving for this goal are the changes we've made to the Awesomenauts character Gnaw. At some point Gnaw was heavily overpowered for beginning players, but mediocre at best for pro players. That meant that if we had nerfed (weakened) Gnaw for the sake of the beginner experience, Gnaw would have become totally useless for pro players. If simple nerfing is not an option, then what to do instead?

When a character is overpowered specifically in matches with beginners, this is often either because the character is too easy to play well, or because the counters are too difficult to figure out and perform. The nice thing is that if we can change the difficulty, it won't matter much for pro players: if the character becomes harder to play, pros will still master it. And if the character becomes easier to counter, that also doesn't matter for pro players: their opponents already mastered the counters anyway. Realising this doesn't make fixing the balance easy, but at least it gives us a starting point for where to look for a fix.



To modify Gnaw's difficulty for beginners, our designers made a number of changes over the years. Most of these revolved around making it more work to be effective with Gnaw. For example, initially Gnaw's Weedlings (little creatures Gnaw can leave behind to attack enemies) would live forever. One of the changes we made was that Weedlings would die after a while, requiring Gnaw to place them again. Weedlings were also changed to start weaker and become stronger over time. The result of these changes is that the player needs to be a lot more active to keep their Weedlings in the right places. Also, if the enemy has destroyed the Weedlings, Gnaw can't just replace them with equally strong ones right away.



Of course these changes also influenced the balance for pro players, but combined with some further tweaks we managed to keep Gnaw about equally strong for pro players while making him harder to play well for beginning players. Hence the pro balance remained similar while the beginner balance was improved.

Another Awesomenauts character with a similar problem was Ayla. Here too we made changes to make her harder to play well and easier to counter. While our designers did manage to improve Ayla's balance for beginning players, she remained problematic to counter for beginners.

Therefore when going free-to-play we employed a different tactic. In the free-to-play version of Awesomenauts, characters need to be unlocked with Awesomepoints, which the player can collect by playing the game. Characters have different prices. For example, some characters are difficult to play so we made them expensive to keep beginners from unlocking them right away. Since we had a problem with Ayla not being so much fun to play against for beginners, we chose to make Ayla expensive as well. This way few beginners will have Ayla and thus few beginners will encounter other beginners who are playing Ayla. This feels like a crude solution, but sometimes crude is the best one can do.



An even cruder solution that might be considered is that if a character is too damaging for the beginner experience, then maybe it's worthwhile to nerf the character to the point where it's okay for beginners, despite that this makes the character not viable for pro play anymore. An important thing to realise here is that with a cast of dozens of characters, a single character not being viable in pro play doesn't make that big of a difference since there are so many other options. However, a single character being overpowered for beginners will mean that lots of beginners play this character and it will ruin many matches.



The third example of fixing beginner balance that I'd like to discuss today comes from our real-time strategy game Swords & Soldiers 2. This game has 3 wildly different factions (Vikings, Persians and Demons), which gives enough headaches in terms of balance already. However, on top of that there is also a tactic that may be balanced, but that's just not fun for beginning players: rushing.

Experienced Swords & Soldiers 2 players can have a lot of fun harassing each other's economy as early as possible, forcing the opponent to spend their gold on defence instead of upgrades, or maybe occasionally even winning the game in under a minute. However, beginning players rarely start a match effectively. They're likely still reading some upgrade descriptions or thinking about what to do next. The result is that if the opponent employs even a very ineffective rush tactic, a beginning player will still be overwhelmed and lose in less than a minute.

For beginners this is highly frustrating, but since rushing is so much fun for pro players we didn't want to remove rush tactics from the game altogether. Instead we came up with something that's just for beginners: Starting Gates. Starting Gates are gates in front of each player's base that need to be destroyed before the base can be reached. This slows down rush tactics a lot and gives the defending player quite a lot of extra time to respond once the enemy soldiers come into view. Starting Gates are truly only for beginners: in matchmade online matches they're not placed if both players have played a bunch of online matches already.



Making the balance as fun for beginners as it is for experienced players is a hard and sometimes nearly impossible challenge. In this post I've given examples of 3 different tricks we've employed to improve beginner balance: Gnaw was made more difficult to play without making him stronger, Ayla was made more expensive so that beginners would encounter her less, and rushing in Swords & Soldiers 2 was changed for beginners by introducing a new mechanic that only applies to beginner matches.

These are all examples of looking at balance as a creative challenge, not just as a topic that's about spreadsheets and tweaking numbers. Have you used any nice tricks to improve balance? Please share in the comments!

Saturday, 3 August 2019

New Song: A Century Sails By

I've finished a new cello song! :D This one started out as a travelling theme for a game concept with a little boat, but will end up on my album as the intermezzo where the story jumps from the 1850s to the 1950s. The title reminds of both uses. I hope you like it!



Musically the idea behind this song was to play with delay/echo: two of the instruments get a rhythmic echo. This is a fun little musical effect with a big impact, as it results in these instruments constantly playing chords with their own previous notes. It's easy to mess this up by choosing the wrong progression of chords and making it sound dissonant and ugly (or to do this on purpose, if dissonance is the goal). During most of the song I steer away from this and choose notes that sound nice with the notes that came before. However, at the end of the cello melody (at 1:10 in the video) I go from C# to C. This is very dissonant but at the same time brings us back to the chords at the start of the song. I really like the tension this creates. This effect is so strong that I needed to keep the music in the same chord for four bars before starting the chord progression again, just to make it settle back in and feel good.

As with all my songs, sheet music for cello can be found at music.joostvandongen.com, including a recording of the song without the cello, to play along to.

I've also made an arrangement of the song for an acoustic quartet with two violins and two cellos. Since acoustic instruments can't do a real echo without additional equipment, I've added in some extra notes where possible to mimic the echo. This captures the feel of the song surprisingly well, as I experienced when I played this version with a couple of friends a few years ago. Sheet music for this version is also on music.joostvandongen.com.

Sunday, 3 March 2019

The psychology of matchmaking

Matchmaking is a touchy subject and this has previously made me somewhat hesitant to write about it in an open and frank manner. Today's topic especially so, since some players might interpret this post as one big excuse for any faults in the Awesomenauts matchmaking. However, the psychology of matchmaking is a very important topic when designing a matchmaking system, so today I'm going to discuss it anyway. For science! :)

While we were designing the Galactron matchmaking systems I did quite a lot of research into how the biggest multiplayer games approach their matchmaking. The devs themselves often don't say all that much about it, but there's plenty of comments and analysis by the players of those games. The one thing they all have in common, is that whatever game you look for, you'll always find tons of complaints from users claiming the matchmaking for that particular game sucks.



My impression is that no matter how big the budget and how clever the programmers, a significant part of the community will always think they did a bad job regarding matchmaking. Partially this might be because many games indeed have bad or mediocre matchmaking, but there's also a psychological factor: I think even a theoretical 'perfect' implementation will meet a lot of negativity from the community. Today I'd like to explore some of the causes for that.

The first and most obvious reason is that matchmaking is often a scapegoat. Lost of match? Must be because of the crappy matchmaking. My teammates suck? Must be the crappy matchmaking. Got disconnected? Definitely not a problem in my own internet connection, must be the crappy matchmaking. Undoubtedly in many cases the matchmaking is indeed part of the problem, but these issues will exist even with 'perfect' matchmaking. Sometimes you're just not playing well. Sometimes a teammate has a bad day and plays much worse than they normally do. Sometimes your own internet connection dropped out. No matchmaker can solve these issues.

There's a strong psychological factor at play here: for many people their human nature is to look for causes outside themselves. I think this is a coping mechanism: if you're not to blame, then you don't have to feel bad about yourself either.

Of course there is such a thing as better or worse matchmaking. That players use matchmaking as a scapegoat shouldn't be used as an excuse to not try to make better matchmaking. But it sure makes it difficult to asses the quality of your matchmaking systems. Whether your matchmaker is doing well or not, there will practically always be a lot of complaints. The more players you have, the more complaints.

For this reason it's critical to collect a lot of metrics about how your matchmaking is objectively doing. We gather overall metrics, like average ping and match duration and such, but we also store information about individual matches. This way when a player complains we can look up their match and check what happened exactly. This allows us to analyse whether specific complaints are caused by problems in the matchmaker, are something that the matchmaker can't fix (like a beginner and a pro being in a premade together) or whether the user is using matchmaking as a scapegoat for something else.



Another problem for matchmaking is that player's don't have a single, predictable skill level. The matchmaker matches a player based on their average skill, but how well they actually play varies from match to match. One match they might do really well, and then the next they might do badly. For example, maybe the player gets overconfident and makes bad decisions in the next match because of that. Or maybe the player is just out of luck and misses a couple of shots by a hair that they would normally hit. Or maybe the player got home drunk from a party and decided to play a match in the middle of the night, playing far below their normal skill level. These are things that a matchmaker can't predict. This will often make it seem like the matchmaker didn't match players of similar skill. Sometimes this might result in a teammate who would normally be as good as you but happens to play like a bag of potatoes during this one match in which they're in your team.

While this problem is not truly solvable by matchmaking, there are some things developers can do to improve on it. For example, in Heroes Of The Storm you select your hero before you go into matchmaking. This allows the matchmaker to take into account that you might be better at some heroes than at others. If it detects that you're playing a hero that you haven't played in a long while, then maybe it should matchmake you below your skill level. I have no idea whether Heroes Of The Storm actually does this, but it's certainly a possibility. This would allow detecting some of the cases in which a player is normally really good, but is currently trying something new that they haven't practised yet.



However, this particular trick comes at a heavy cost, which is why we decided not to put it into Awesomenauts: if players select their hero before matchmaking happens then matchmaking is severely limited in who can play with whom, which damages other matchmaking criteria. (I've previously discussed this in my blogpost about why you need huge player numbers for good matchmaking.)

A very different kind of psychological aspect is that players are often bad at estimating their own skill level. The following example of this is something that I have no doubt will be recognised by many people who play multiplayer games. A while ago I played a match in which a teammate was constantly complaining about how badly I was playing and how I was causing us to lose the match. However, looking at the scoreboard I could see that he was constantly dying and was by far doing worst of all players in the match. Apparently that player didn't realise that he was much less good at the game than he thought he was.

There's more to this than anecdotal evidence however. The developers of League of Legends have described that on average, players rate their own skill 150 points higher than their real MatchMaking Rating. (That part of the post has been removed in the meanwhile, but you can still find it here on Wayback Machine.) As they also mention there, psychology actually has a term for this: it's called the Dunning-Kruger effect. A League of Legends player analysed a poll about this here and gives an excellent explanation of how it works:
"According to the Dunning-Kruger-Effect people overestimate themselves more the more unskilled they are. This isn’t caused by arrogance or stupidity, but by the fact that the ability to judge a certain skill and actually being good at that skill require the same knowledge. For example if I have never heard of wave management in LoL I am unable to notice that I lack this skill, because how would I notice something if I don’t even know it exists? I would also not notice this skill in other people, which is why I would overestimate my own skill if I compared myself to others. This it what causes the Dunning-Kruger-Effect." - Humpelstilzche

As some readers suggested, all of these psychological factors invite an interesting thought: would it help to give players more control? After all, if you have no control you blame the system, while if you do have more choice, you also have yourself to blame and maybe accept the results more. Giving players choice over matchmaking is in many ways old-fashioned and reminds me of the early days of online multiplayer, where you selected your match yourself from a lobby browser. The common view these days seems to be that players expect a smooth and automated experience. They don't want to be bothered and just want to click PLAY and get a fun match. Or at least, most devs seem to assume that that's what players want.

For Awesomenauts I've actually been curious for a while what would happen if we removed the automated matchmaking and instead relied entirely on opening and selecting lobbies. The modding scene would surely thrive a lot more that way, but how would it affect player experience and player counts? It would be a risky change and also too big a change to just try though so I doubt we'll ever get to know the answer to that question. Also, I'm not sure whether our current lobby browser provides a smooth enough experience for making it that important.

I do think it's interesting to explore this further though. I wonder what would be the result if matchmaking were from the beginning designed around being a combination of automation, communication and player control.

Before ending this blogpost I should mention one more psychological aspect of matchmaking: the developer's side. As a developer it can be really frustrating to get negative comments on something you've spent a lot of time on. Understanding why can help in coping with this frustration. Just like matchmaking can be a scapegoat for players after losing a match, the psychology of matchmaking can be a scapegoat for developers after getting negative feedback from players.

None of the psychological factors discussed in this post are an excuse to just claim that the matchmaking in a game is good despite players complaining. However, for a developer it's really important to realise that these factors do exist. Understanding the psychology of matchmaking allows you to build better matchmaking and helps to interpret player comments. I have no doubt that I've only scratched the surface of this topic, so I'm quite curious: what other psychological aspects influence how matchmaking is experienced by players?