Search code examples
algorithmsortingmobileservermultiplayer

Best way to "pair with opponent" in a match-making multiplayer game

This question isn't really language specific, it's more about the logic behind ALGORITHMS that would be used in pairing players in a 1v1 match-making game.

This is a two part question.

If I have a game that's match-making 1v1 type game and you open your phone's app, select "play" and it finds an opponent for you, what's the best way to go about this?

Let's say in my database of players I have a key called "pairing" with a BOOL value YES/NO.

Someone opens the app, clicks play, so I need to pair them, so I flip this BOOL to YES and then we look for someone else with a YES value and make a confirmation and then they play?

What happens if the first user closes the app while they were waiting to paid up because they got bored and left, the server value would stay as "Yes" because I can't switch it to NO because the app is closed. So this won't work.

So instead I have a key "Pairing" with an int value and 0 = no and anything other than 0 is yes, so every second I increase this value by 1 from the client, to the server. At any given time if this value has not changed after 10 seconds or so (server side) I assume the user closed the app and left, so we flip the value to "0".

Okay so now we have proper pairing-mode detection (Question 1: Is this the best way to detect proper pairing mode? A dynamic variable)

But, now that I have 10,000 players on a server all in pairing mode, what's the best way to make matches? What if I end up with 5 players (Players A,B,C,D,&E) all getting paired to the same player (Player F), sure I just use some simple rand() tie breaking algorithm, but it seems someone could end up in ties ALL the time and keep getting tossed around, it could take 20 seconds just to make a confirmation that two players are set to battle each other. The optimal algorithm would pair everyone efficiently, any thoughts? I have a feeling it will involve a queue of some sort, in order of how long you've been waiting to be paired. (That's question 2)

Solution

  • The way I would implement this is as follows:

    1. Every player has a unique player_id in the database.
    2. When a player connects to your server (it should not be connecting to the database itself), add them to a list of active sessions.
    3. Have a specific interval as the timeout. The client should send a ping packet to the server every second (or whatever time period you would like). If the server has not received a ping from the client after a specified amount of time, disconnect the client. If the player was in a game when this happened, notify the other user that their opponent has disconnected, and consider the match void.
    4. If you would like to prevent void matches, you could save the current game session state to the database (or other external source) and when both players are ready again, notify each of them that the match is ready.

    At this point, we've solved the connectivity issue. Now, to your question about if multiple users get paired up to the same person. The easiest thing to do would be something like

    while server is running
    if player is not currently in a match
        if there are available opponents
            set the first player's opponent to the opponent
            set the opponent's opponent to the first player
            remove each of them from the list of available players
        else
            wait for an opponent to become available

    You should also remove the player from the list of available players if the server has not received a ping packet after n time from the client.