Vue d’ensemble de la formation des correspondances
Lorsque vous soumettez un ticket à une file d’attente, le service de matchmaking le place avec les autres tickets en attente. Le service exécute en continu une boucle de mise en correspondance qui tente de regrouper des tickets compatibles en correspondances. Voici ce qui se passe à chaque étape :- Les tickets expirés sont supprimés. Les tickets qui dépassent leur délai d’expiration
GiveUpAfterSecondssont annulés. - Les tickets sont triés par temps d’attente : le ticket qui attend depuis le plus longtemps devient le ticket de départ (seed), c’est-à-dire le point de départ d’une correspondance potentielle.
- Les candidats sont classés par compatibilité : chaque ticket restant reçoit un score de distance basé sur le degré de concordance de ses attributs avec le ticket de départ, selon les règles de la file d’attente.
- Un groupe est constitué de façon gloutonne : en commençant par les candidats les plus proches, les tickets sont ajoutés au groupe un par un, jusqu’à
MaxMatchSize. - Chaque ajout est validé : lorsqu’un ticket est ajouté, chaque règle vérifie si le candidat est toujours compatible avec le groupe constitué jusque-là. Si une règle le rejette, le candidat est ignoré.
- Le groupe complet est validé : une fois qu’un groupe atteint au moins
MinMatchSize, une dernière passe de validation confirme que le groupe satisfait toutes les règles. Si c’est le cas, une correspondance est créée. - Retour arrière : si aucun groupe valide ne peut être formé, le service retire le dernier ticket ajouté et essaie le candidat suivant. Ce processus explore d’autres regroupements avant d’abandonner le ticket de départ actuel.
L’algorithme donne la priorité aux tickets qui attendent depuis le plus longtemps. Cette priorité garantit que les joueurs qui attendent le plus longtemps sont les premiers à obtenir une correspondance.
Influence des règles sur la mise en correspondance
Les règles remplissent deux fonctions lors de la formation des correspondances : le filtrage et le tri.Filtrage
Une règle peut empêcher un ticket de rejoindre un groupe. Par exemple, uneStringEqualityRule sur la version de build du jeu rejette tout ticket dont le build ne correspond pas à celui du groupe. Le service de matchmaking vérifie le filtrage chaque fois qu’il considère un candidat. Il ne s’agit pas d’une simple vérification ponctuelle au début.
Tri (distance)
Les règles contribuent également à un score de distance qui détermine quels candidats sont essayés en premier. Une distance plus faible signifie une compatibilité plus élevée.- Un ticket ayant une valeur d’attribut identique obtient généralement une distance de 0.
- Un ticket situé à la limite de la plage autorisée d’une règle obtient une distance proche de 1.
- Un ticket situé hors de la plage autorisée est filtré (distance effectivement infinie).
Validation
Certaines contraintes ne peuvent être vérifiées qu’après la formation d’un groupe complet. Par exemple, les règles d’équilibre des équipes (TeamDifferenceRule, TeamSizeBalanceRule) doivent voir le groupe complet avant de pouvoir évaluer si les équipes sont équilibrées. Ces règles s’exécutent lors d’une étape de validation finale.
Expansion et assouplissement
Pendant qu’un ticket attend, les règles assouplissent leurs contraintes pour élargir la recherche. Deux mécanismes contrôlent ce processus :- Expansion : une règle ajuste progressivement son seuil au fil du temps. Par exemple, une
DifferenceRuleavec un seuil de compétence de 0,2 peut s’étendre de 0,1 toutes les 5 secondes, pour finalement autoriser une différence de 0,5. - Secondes avant de devenir facultative : après une durée configurée, la règle cesse complètement de filtrer. La règle contribue toujours au tri (distance), mais elle ne bloque plus les correspondances.
L’assouplissement ne signifie pas que la qualité de la correspondance est ignorée. Même lorsqu’une règle devient facultative, elle contribue toujours à la distance lors de l’étape de tri. Les candidats qui satisfont la règle sont essayés avant ceux qui ne la satisfont pas.
Mise à l’échelle et partitionnement
Lorsqu’une file d’attente reçoit un volume élevé de tickets, le service partitionne les tickets en groupes qu’il évalue indépendamment. Le partitionnement utilise des attributs de règle qui divisent naturellement la population. Par exemple, uneStringEqualityRule sur le mode de jeu crée des limites de partition nettes.
Lorsque la charge diminue, les partitions fusionnent de nouveau. Ce processus fournit au service un plus grand ensemble de candidats et améliore la qualité des correspondances.
Pour plus de détails sur la conception de files d’attente qui évoluent bien, consultez Mise à l’échelle du matchmaking.