CODEWITHSUNDEEP
algorithmdata-structurescomputer-sciencecomputer-science-theory
Sandy Leach
Sandy Leach

Reputation: 85

Most efficient way to repeatedly pair up a group of users for a quick game

I have an application where users sign on to play a quick 1v1 game (20 seconds duration). I would like to know the most efficient way to pair each user up with another user to play the game and move onto the next user without playing the same user multiple times in a row.

My first idea was to have two queue's containing the user id's of each online user. Whenever a new user goes online I would add them to whichever queue is the shortest and constantly be popping one person off the top of each queue to play each other. After the game I would simply add each user to the same queue to avoid them playing each other again. This seems good but I would like to see if there are any other more efficient ways to do this concept without needing to keep a list of previous users played on the server.

Upvotes: 2

Views: 866

Answers (3)

Geff
Geff

Reputation: 52

You need to matchmaking system that will prioritize players who have been waiting the longest.

You only need 1 queue and you also need to keep track of users history using a table. The table can either be temporary session data or a database table if you want permanent data across multiple sessions or if the match making server crashes. The table should have the playerID and an array of previous playerIDs that they previously played against. It can be best to limit the size of the array and use LIFO as you might not want to just store the players most recent match ups i.e. match history. Also the player could run out of players to play against if they already played against everyone else online. The table should look like this:

  • playerID (integer)
  • previousPlayerIDs (array of integers)

When a match starts you can update the the previousPlayerIDs for all the players in the match. You need to listen to an event when a player has joined the queue lets call it onPlayerJoin(). If the queue has more than 1 player you should take longest queuing player and compare their playerID against the previousPlayerIDs of each player until you find no history of a match up. 

const historyLimit = 10;

function onPlayerJoin(Player newPlayer){
  playerQueue.push(newPlayer);
  if(playerQueue.length > 1){
    for(let a=0; a<playerQueue.length-1; a++){
      Player player = playerQueue[a];
      for(int i=a+1; i<playerQueue.length; i++){
        Player otherPlayer = playerQueue[i];

        //if the player have not played before
        if(otherPlayer.previousPlayerIDs.indexOf(player.id) > -1){

          //save match up
          player.previousPlayerIDs.push(otherPlayer.id);
          otherPlayer.previousPlayerIDs.push(player.id);

          //limit matchup histroy
          if(player.previousPlayerIDs.length > historyLimit){
            player.previousPlayerIDs.removeAt(0);
          }
          if(otherPlayer.previousPlayerIDs.length > historyLimit){
            otherPlayer.previousPlayerIDs.removeAt(0);
          }

          //create lobby and remove players from the queue
          createLobby(player, otherPlayer);
          playerQueue.removeAt(a);
          playerQueue.removeAt(i);
        }
      }
    }
  }
}

It is possible for a player to have played everyone else and they are waiting for someone to come online that they haven't played against before. You will need a reoccurring event to check if the longest waiting player has been waiting too long. If this is the case just ignore the matching of previousPlayerIDs and create a lobby for the the player up with another potentially long waiting player.

If you want you could add more columns to the table such as a timestamp when they joined the queue and their match making rank (elo). But if you just want to prioritize the most recent player you don't need these other columns.

Also this solution might not scale up very well if you have massive amounts of concurrent user but it should be fine if you have less than 1,000-10,000

Upvotes: 1

Jim Mischel
Jim Mischel

Reputation: 134085

Your idea doesn't work. Eventually (possibly very quickly), you'll end up in a position where two players who have played previously end up in separate queues. You can't guarantee that they'll never be selected to play together again.

Imagine this simple case:

Queue 1       Queue 2
   A            B
   C

A and B play, and get added to Queue 2:

Queue 1       Queue 2
   C            A
                B

A and C play, and get added to Queue 1:

Queue 1       Queue 2
   A            B
   C

Now A and B play again. C never got the opportunity to play B.

This particular example is unlikely to occur, true. But something similar can happen even with larger queues as the space between player X and all the players he's played over time increases. The likelihood of ending up with two players playing each other again without having played every other potential player is quite high. I suspect the probability is similar to the birthday problem.

Upvotes: 1

Sam Bokai
Sam Bokai

Reputation: 548

Your solution seems fine, but you should just use a single queue.

Upvotes: 0

Related Questions