I've been working on a site that can match players together recently and I can't figure out what the best way to go about the algorithm would be. All players that try to play are assigned a unique lobby that they are in, they can queue either solo or with someone else. For example we have and 2 on 2 game, 1 player enters the queue playing alone then 2 players enter the queue being in the same lobby(being in the same lobby means that when they get a match they will play on the same team) so currently there is 1 player queing solo and 2 players in a team, the total amount of players needed to to make a match would be 4, so a match wouldn't be found yet, then another solo player enters the queue at this point he should get matched with the other solo player and face the 2 players in a team. Every lobby also has parameters for example gamemode and region and only the players with the same parameters can get matched against each other. There are at least 3 regions and 3 gamemodes for example 1 on 1, 2 on 2, 3 on 3 etc. Currently I am pushing all lobbies that enter the queue into an array

{
    "size":2,
    "id":"id",
    "region":"US",
    "mode":"2v2",
    "players":[
        {
            "username":"test1",
            "id":"id1"
        },
        {
            "username":"test2",
            "id":"id2"
            
        }
    ]
} 

this is what one 2 on 2 lobby would look like and there can be thousands of these types of lobbies in the array all searching for game. I am unsure of how I would make a algorithm that is the most effective and dynamic and would match all lobbies in the array even tho they have different parameters.

I haven't gotten very far with coding this.

  if(activeUsers[i].mode == "2v2"){
    test = []
    test.push(activeUsers[i])
    n = 0
    for(j = 0; j <test.length; j  ){
      
      if(test[j].region == "US"){
        n  = test[j].size
      }
      
    }
    console.log(n)
} 

}

I am just stuck at this point and I have no idea how to go further or what do to for example matching players playing together against players that are separated.I was also thinking if it's better to have a separate array for each region with and parameter. I am using Node.js to accomplish this.

CodePudding user response：

If you kept all lobbies in an array of objects like your first code example, you could loop over that array every few seconds and process each lobby like this:

1. Does lobby have enough users for a match? (You might want to add according information somewhere, s.t. the system knows the right amounts of players)
2. If so, take first n users, construct match and delete them from the lobby; go back to step 1
3. Done, go to next lobby

However, I agree: All answers to this question are inherently opinion-based

CodePudding user response：

This doesn't sound very challenging algorithmically. I would expect the array of lobbies to serve as something akin to a FIFO queue. When a new player is added, we check the lobbies in order, adding the player to the first matching lobby with an available space. If we now have enough players to start the game, we create a new game and remove the lobby. It might look something like this:

const onPlayerEnter = ({games, lobbies, ...rest}, player) => {
  let lobby = lobbies .find (playerFits (player))
  if (lobby) {
    let updatedLobby = addPlayer (lobby, player)
    lobbies = replaceLobby (lobbies, lobby, updatedLobby)
  } else {
    lobby = createLobby (player)
    lobbies = addLobby (lobbies, lobby)
  }
  if (gameReady (lobby)) {
    games = games .concat (makeGame (lobby))
    lobbies = removeLobby (lobbies, lobby)
  }
  return {games, lobbies, ...rest} 
}


const playerFits = (player) => (lobby) => {
  // Your logic on whether this player matches the lobby requirments, return boolean
  // This would have to do with number of players, the mode, the region, maybe ratings ranges...
}
const addPlayer = (lobby, player) => { /* ... */ }
const replaceLobby = (lobbies, oldLobby, newLobby) => { /* ... */ }
const createLobby = (player) => { /* ... */ }
const addLobby = (lobbies, lobby) => { /* ... */ }
const gameReady = (lobby) => { /* ... */ }
const makeGame = (lobby) => { /* ... */ }
const removeLobby = (lobbies, lobby) => { /* ... */ }

This would take a system state and a new player and return an updated system state, which has that player added to an existing lobby or starting a new one, and if the lobby is full, converting it to a game.

I would suggest that your mode property should be more sophisticated than just a plain string, perhaps something like:

mode: {
  display: '2v2',
  teams: [
    {minPlayers: 2, maxPlayers: 2},
    {minPlayers: 2, maxPlayers: 2}
  ]
}

This would be easily expandable to allow additional features.