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.
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:
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