Matchmaking Logic and Approaches #

This topic provides an in-depth look at the Pragma Matchmaking service.

Matchmaking queue keys #

Each queue is defined by its unique Matchmaking queue key. A matchmaking queue key contains two pieces of information, both of which are set in the Party service: a GameServerVersion that splits queues by the version of the game server, and a custom ExtMatchmakingKey that provides a location for developers to define variables they want to use to split queues.

Different scenarios determine which queues parties enter:

  • If you only set one value (GameServerVersion or ExtMatchmakingKey), players with matching set values will enter the same queue
  • If you set both the GameServerVersion and ExtMatchmakingKey, only players with matching GameServerVersion AND ExtMatchmakingKey values will enter the same queue
  • If you do not set the GameServerVersion or ExtMatchmakingKey, all player will enter one global queue.

For example, consider a game that has multiple game modes: 3v3 Ranked, 3v3 Casual, and Co-op Adventure. We can configure the ExtMatchmakingKey proto to consider the game mode.

message ExtMatchmakingKey {
    GameMode game_mode = 1;
}

enum GameMode {
    Unspecified = 0;
    ThreeVsThreeRanked = 1;
    ThreeVsThreeCasual = 2;
    CoopAdventure = 3;
}
If the matchmaking queue only contains one Matchable, the matchParties()/matchPartiesWithGame() method is skipped and endOfLoop() is called.

Matchmaking logic #

Matching parties to form a new game instance #

When the matchmaking process begins, the Matchmaking service selects the oldest member of the queue as the anchor Matchable. This Matchable is compared with every other Matchable in the queue, starting with the next oldest member (relative to the current anchor), to check viability of combining parties into one Matchable. The Matchable being compared to the anchor Matchable is called the other Matchable.

Matchmaking loop overview

During each of these local comparisons, the matchmaking engine invokes the Matchmaking Plugin’s matchParties() method, which includes custom logic to determine whether to produce any of the following changes to the Matchables:

  • Produce a new game instance: If there’s a good enough match for players to begin playing a game, send them to the game via a NewGameInstance object.
  • Take parties from the other Matchable queue member: If adding some parties from the other Matchable to the anchor Matchable would improve the quality of the possible ensuing match, move those parties into your anchor Matchable.
  • Take parties from the anchor Matchable queue member: If removing some parties from the anchor Matchable would improve match quality, move the party to the other Matchable. This is usually performed in combination with taking some parties from the other Matchable, making an exchange of parties.
  • Continue matchmaking with new anchor: If, after comparing the anchor Matchable with all other Matchables in the queue, no NewGameInstance has been generated, the anchor position is moved to the next oldest Matchable in the queue. To add custom behavior at this stage, implement endOfLoop as described in Add custom behavior after a matchmaking loop.

Example

In the following image, Matchable 1 (M1), which consists of Party 1 (P1), starts as the anchor:

Match Parties Logic

  • a: M1 is compared to M2. Based on custom logic, M1 takes P2 from M2. M2 is removed from the queue because it no longer contains any parties.
  • b: M1 is compared to M3. Custom logic determines no party swapping is needed.
  • c: M1 is compared to M4. Based on custom logic, M4 takes P2 from M1. M1 has not exhausted the queue and the anchor advances to M3 (M2 was removed).
  • d: As anchor, M3 is compared to M1. Custom logic determines no party swapping is needed.
  • e: M3 is compared to M4. Custom logic determines a match has been found and the two Matchables are sent to the game service in a NewGameInstance object.
If a new party joins the queue, its Matchable is added to the end of the queue. The new Matchable will be compared to others in the queue the next time the anchor position advances.

Matching parties with active game instances #

When an active game instance enters matching from the Game Instance service, the Matchmaking service creates a Matchmaking.GameInstance object with game information required to make an appropriate match. A Matchmaking.GameInstance instance is similar to a Matchable in that it contains parties for comparison. Unlike a Matchable, a Matchmaking.GameInstance cannot have parties taken from it.

To make comparisons, the matchmaking engine invokes the Matchmaking Plugin’s matchPartiesWithGame() method. In this method the Matchmaking.GameInstance is the game and the Matchable in the queue that’s being compared to the game is the anchor.

The matchPartiesWithGame() method includes custom logic to determine whether parties from the anchor Matchable should be added to the active game instance. If adding some parties from the queue would improve the quality of the match in the current game instance, add those parties to the game Matchmaking.GameInstance and return a GameInstanceUpdate object.

If no suitable match is found after comparing the game instance with all Matchables in the queue, matchPartiesWithGame() can return null.

You cannot remove parties from a Matchmaking.GameInstance.

Comparison data #

When comparing Matchables, the following information is available to the Matchmaking Plugin for consideration in your matchmaking logic.

  • parties: list of parties in the Matchable
    • partyId: unique party ID
    • ext (ExtMatchmakingParty): custom party data to inform the matchmaking process
    • preferredGameServerZones: list of the party’s preferred game server zones
    • players: list of player objects within the party
    • playerCount: number of players in the party
    • secondsInQueue(): number of seconds the party has been in the matchmaking queue
  • players: list of all the players in the Matchable
    • playerId: unique player ID
    • teamNumber: player’s team number
    • partyId: unique party ID for the party the player is in
    • gameServerZoneToPing: map of the player’s client-supplied ping map, keyed by gameServerZone ID
    • ext (ExtMatchmakingPlayer): custom player data to inform the matchmaking process
  • extMatchable (ExtMatchable): use this ext to store data calculated within the Matchmaking loop so you don’t have to recompute it on every matchParties call
  • matchmakingKey (ExtMatchmakingKey): custom data about the Matchable’s matchmaking queue
  • gameServerVersion: version of the game server the match would be played on

Matchmaking approaches #

When matchmaking, one must always consider a trade-off between matchmaking speed and match quality.

Matchmaking services tend to use either a streaming method or batching method when matchmaking. In general, streaming and batching methods differ in the way they apply party comparison logic. While both streaming and batching methods are valid and have been proven to work at-scale, Pragma implements a streaming approach to support matching players together into high-quality games quickly and at scale. The Pragma streaming-based matchmaking process focuses on developing a clear set of match criteria and tuning time-based envelopes.

Streaming-based matchmaking #

Streaming-based matchmaking involves selecting a single Matchable (a grouping of one or more parties) to compare, one-by-one, to each other Matchables in the queue.

As the anchor Matchable steps through the queue, logic defined in the Matchmaking Plugin determines if the Matchables should be merged or if individual parties should be moved between the Matchables. After iterating through the queue, the anchor position moves to the next Matchable in the queue.

This process happens in memory and thus is extremely fast. You can expect that each party will have its chance as an anchor hundreds or thousands of times per second. If at any point of time that grouping of parties forms a valid match, it should immediately be sent to start that match.

Envelopes #

To ensure high quality matches, we recommend using time-based envelope expansion to balance the competing concerns of producing matches as quickly as possible while also making the highest quality matches. In an envelope expansion approach, an envelope represents qualities of an ideal match at a point in time. Using time-based envelopes, you can modify the strictness of your acceptable match criteria as time progresses. That is to say, you can continue to broaden the criteria of what makes an ideal match the longer a party is in matchmaking. Early comparisons can restrict acceptable matches to only those considered ideal.

Given that envelopes are expanded in human time (for example every 10 seconds), while the loop itself is giving every matchable a chance to be an anchor hundreds or thousands of times per second, the ‘greedy’ nature of the architecture is able to produce extremely high quality matches.

Batching-based matchmaking #

The batching style of matchmaking is defined by viewing the entire set of parties in a queue at a single point in time. This application requires you to consider the number of comparisons necessary to produce high quality matches without introducing scaling issues. The potentially large number of required comparisons could make the process difficult to optimize, and often requires extensive modeling and testing.

While resulting matches may prove ideal, developing logic to compare the entire set of parties in a queue at a single point in time tends to be more difficult than comparing one Matchable to another, which happens in streaming-based matchmaking. Pragma recommends implementing a streaming approach to support matching players together into high-quality games quickly and at scale.

Testing #

Pragma Engine provides the MatchmakingTestFactory to test custom implementations of the MatchmakingPlugin. The test factory has methods to easily create a Matchable or MatchmakingGameInstance in various different states to test specific matchmaking scenarios.


Parties
Data Stores