Matchmaking with SpatialOS

14 June 2019

Matchmaking is a crucial part of every multiplayer game. But it's difficult to build from scratch.

Matchmaking systems not only need to know which matches to assign players to based on player preferences, but they also need to smoothly communicate with the game worlds, keep track of all players and parties, and scale dynamically based on demand. Whilst third-party solutions exist in the market today, they often force developers to make compromises on their matchmaking design or spend precious development time building their own solution.

At Improbable, we want developers to spend more time on gameplay and less on custom backend systems. To do this, we’re building a flexible matchmaker, which will provide an easy way for developers to move players into SpatialOS game instances. This SpatialOS matchmaker provides a framework for developers to write their own completely customizable matchmaking logic (or build completely different tools related to getting players into game instances, such as players transferring between worlds or entering dungeons).

The first iteration of the SpatialOS matchmaker will be coming in July 2019 and will take the form of an open-source code base developers can download, edit and deploy to a public cloud. It is important to note that the SpatialOS matchmaker will not be a managed service at launch. Whilst we provide the codebase as a starting point, developers will need to deploy, host and manage the matchmaker themselves. This is so we can provide as much flexibility as possible to developers to tailor how the matchmaker works.

NB: in our documentation, we refer to our matchmaker as ‘gateway’ because it is not specific to matchmaking, instead it provides a generic way to get your authenticated players into the correct SpatialOS instances. However, for the rest of this blog, we’ll refer to it as the matchmaker.

How it works:

The SpatialOS matchmaker is at its heart:

  • An in-memory database storing the player and party queue;
  • Customisable docker containers providing accessible APIs for the assignment of players and parties in the queue to active matches.

This all runs in the public cloud, using Kubernetes and Redis, scaling the resources it needs appropriately. The system diagram below explains how this works after the system has been deployed to a public cloud:

matchmaking diagram

  1. Players are assigned to parties by the party service. Parties can be as small as one player - there is one party leader for every party and if a leader leaves a party then a new one is randomly assigned. The party leader can use the “invite” service to send invitations to players, who then need to accept or reject the invitation. Once assigned to parties, the party details are logged in Redis.

  2. The party registers with the matchmaker and is queued. When ready, the client of the party leader (a player) makes a single request on behalf of their party to a “gateway”. Gateway docker containers log the request in Redis in a party requests table, which represents the queue.

  3. A ‘matcher’ takes parties from the queue, finds or creates matches via the Platform SDK, and matches them. A matcher is a docker container that runs custom logic created by a developer. It requests waiting parties from the Redis via “gatewayinternal” and then assigns these parties to active matches. (Gatewayinternal exists to minimise calls to Redis by handling the requests between the matchers and Redis). These parties are removed from the Redis queue when passed to a matcher so they can’t be called multiple times.

You can have different matchers for different game types, each pulling from different queues in Redis.  The logic provided by the developer, running in the matcher, then ensures that the parties end in the optimal matches based on other factors, for example, rank or ping. For example, a simple approach would be to call ‘x’ parties from Redis and “y” active matches from the SpatialOS Platform SDK, then loop through them to assign parties to the matches, using the developer’s logic.

Matchers can interact with the Platform SDK to start and stop instances directly. However, we envisage that our forthcoming instance pooling service would use developer-customised logic to start matches, to prevent players from having to wait for one to spin up. This way, a minimum number of matches are always available and matchers can connect players directly to them.

  1. Redis is updated with the matcher results. If a matcher matches a party to a game it sends a “matched” command to gatewayinternal. If it doesn’t, it can send a “re-queue” or “error” command. Gatewayinternal then updates that party’s entry in Redis; if a match has been found the party is popped off the queue. 

  2. The gateway sends game match details to the clients. The gateway could also send login tokens to the players in said parties. These tokens contain the authentication details and address needed to connect clients to the relevant game instance. The game developer provides the logic to then connect the clients to the game instance using this token. The result is a fully customizable matchmaking system that takes advantage of Kubernetes to scale, whilst the game developer has only had to provide the logic for the matchers and clients.

A note on matchers:

The matchers rely on metaproperties associated with the waiting parties and matches in order to make assignments. By default, waiting parties have a “game type” label, party structure, and min/max size. Developers can assign additional custom labels as well, so they can have complete flexibility over how their matchmaking logic works.

For example, a developer might want to consider the combined metagame ranks of the party by querying an external database. Alternatively, the developer might want to measure the ping of each player to ensure a smooth experience. We explore this more deeply in examples below.

What do game developers need to do?

There are three main things developers need to do to set up the SpatialOS matchmaker for their game:

  • Write the logic for the matchers to assign parties to matches. (Today, the SpatialOS matchmaker is only documented for C# logic for the matchers.)
  • Write the client-side logic to organize parties and send requests to join a match. This includes setting up the menu interface that players actually interact with.
    • Our services are all exposed through gRPC endpoints, requiring your clients to use a gRPC library to perform the calls. This is our preferred solution.
    • Alternatively, if gRPC is an issue for your client, we also expose HTTP endpoints that can be used for the same result.
  • Download our matchmaking codebase and deploy it to a scalable public cloud. This includes setting up public IP addresses so clients can talk to the service, and setting up a DNS if so desired.

Example pseudocode for matchers:

Code for the matchers can be as simple or complex as the developer needs. Let’s have a look at a couple of examples written in pseudo-code:

Example 1:

We want to take ‘n’ parties and place each one in the single busiest match that can fit them (i.e. drop them into running matches). If the matcher can’t find a fit immediately, it should return the party to the queue. We want to control for:

  • Game type
  • The average rank of the party (within +-2 ranks of the match)

def do_match(gametype = “battle royale”):

# Gives a  list of parties wanting the correct game type, which are then removed from the Redis queue
parties = gateway_internal.get_waiting_parties(gametype = “battle royale”, n_parties)

# Query a database holding the rank of all players (set up by developer)    
parties.get_rank()

matches = match_service.get_match(gametype = “battle royale”, game_rank)

# Get the number of spare seats for each match, and reserve them so other matchers don’t try to fill them at the same time
    for match in matches:
        match.tag(“reserved by “ & matcher_id)
        match.get_seats() as n_spare_seats

# Get matches and sort by space remaining ascending for desired assignment of players
matches.sort(asc by n_spare_seats)    

assignments = [] # Start a list of all assignments

for party in parties: for match in matches: if abs(average(party.rank) - match.rank) <= 2 and match.nspareseats <= party.n_players: assignments.append(party.partyid, match.matchid, type = "matched") match.nspareseats = match.nspareseats - party.n_players break # Party assigned and match updated, move to the next party

# If a party is not assigned to a match, tell gateway_internal to requeue them in Redis
for party in parties:
        if party.party_id not in assignments:
            assignments.append(party.party_id, type = "requeue")
        # Makes the pairings in Redis                
gateway_internal.assign_matches(assignments)
  

In this example we can see how common matchmaker logic is using both the existing labels (gametype, nplayers) and others needing to be defined by the developer (rank, spare_seats):

  • For the matches, rank can be assigned as custom labels. Spareseats can be calculated from the maxplayers (custom label) and the current player count (available through the Platform API).
  • For the parties, rank would need to be read from an external database to avoid the player cheating (for example, the leaderboard table). This system could be adapted so the wait-time of a party is taken into consideration, for example, if a party has been waiting longer then the rank condition is ignored.
  • The developer would need to create the functions to do this, as the requirements are very game-dependant.

Example 2:

Now let’s take a look at a slightly different example. In this one, we want to take ‘n’ parties and place each one in the most empty active match. If the matcher can’t find a game for a party at first, the matcher keeps trying until 30 seconds have passed. We want to control for:

  • Game type
  • Only accepts parties where all players have pings below 80ms

    def do_match(gametype = “capture the flag”): starttime = gettimestamp()

      # Gives a  list of parties wanting the correct game type, which are then removed from the Redis queue
      parties = gateway_internal.get_waiting_parties(game_type = “capture the flag”, n_parties)
      
      

    matches = matchservice.getmatch(game_type = “capture the flag”)

      # Reserve matches so other matchers don’t try to fill them at the same time
      for match in matches:
      match.tag(“reserved by “ & matcher_id)
      #Sort by space remaining descending so we fill up empty matches first
      

    matches.sort(desc by nspareseats) assignments = () while (gettimestamp() - starttime) < 30: for party in parties: if party.party_id not in assignments: for match in matches: match.getseats() as nspare_seats if match.nspareseats <= party.n_players: for player in party: # Send a ping measurement to the players (set up by developer)
    player.getping(match.proxynode_ip) as ping

                          if max(party.player.ping) <= 0.08:
                              assignments.append(party.party_id, match.match_id, type = "matched")
                              break # Party assigned, move to the next party            
      #If a party is not assigned to a match, tell gateway_internal to requeue them in Redis
      

    for party in parties: if party.party_id not in assignments: assignments.append(party.party_id, type = "requeue")

      # Makes the pairings in Redis
      gateway_internal.assign_matches(assignments)

    Again, this example uses a mix of standard labels and custom ones assigned by the developer. The new input is ping, needing to be measured for each player. The developer would need to create a function to measure this.

We are also making use of the time that the matcher has been holding players, simply by keeping the matcher looping through matches until this time passes 30 seconds. However, we could make use of time for the matcher, or a timestamp on when the party made a request to join, to relax other criteria (e.g. rank) to check whether a party has been waiting too long.

Can it scale?

SpatialOS is not just for big, persistent worlds; many of our partner games are small, match-based games running across tens of thousands of concurrent instances. Our SpatialOS matchmaker is no exception. Because the entire system runs in Kubernetes containers and uses a Redis database, any matchmaking system built on top of the SpatialOS matchmaker will be able to scale on proven technologies.

We’ll be building out the feature set with our partners in 2019, and will hopefully see it supporting live games with hundreds of thousands of concurrent players in early 2020. Developers can use our matchmaker confident that it can scale to support breakout successes.

Summary

Our open source matchmaking system, coming July 2019, will provide developers with a solution that is:

  • Easy to use: Just download the codebase, tailor to your requirements, and deploy to the public cloud
  • Fully customizable: Developers can create custom logic for the matchmaking system
  • Scalable & reliable: Utilizes proven technologies in Redis and Kubernetes, and will be used by our customers for live games early next year

The SpatialOS matchmaker is just the first of a broader suite of online services we’re creating for SpatialOS.

For the rest of 2019, we’re investigating tools that will work alongside our matchmaker, including match- and player-lifecycle management tools. This will involve building a service to manage and scale game matches. We are building an out-of-the-box analytics solution, which will provide a configurable way to move data from inside a match to an external database, such as GCS. We are also investigating instrumenting our other online services, including the matchmaker, so you will be able to automatically get statistics regarding the number of matches, times in queues, or other performance metrics.

You can read about our broader vision here.