Algorithm for Fairly Sorting Players into Teams

Hello, i made a matchmaking systems for some PVP game modes and the queue work like this :
Imagine a 5v5 mode , you can only queue with your team with 5 or less people.

So I the game server I have a table like this

Local Partys = {


That an exemple of what I can get so here good teams would be :

{p1,p2,p3,p4,p5} and the others
Because they queue in party so they should be in the same party

For any given party, the parties they can be in a team with are those with (5 - #party) members or fewer. So a party of 2 needs a party of 3.

You can’t count on there being any parties of every different size though, so you might have to team up 3 or even 5 different parties (if everyone is queuing up alone). If the size you want isn’t available, use the next one down repeatedly, keeping track of how many slots are left. E.g.

--Removes a team of parties making up MATCH_NUM_PLAYERS players from the queue and returns it.
--A "team" consists of several parties. 
function TakeTeamFromPartyQueue()
    local nextPartyIndex = #Parties
    local team = { nextPartyIndex }
    nextPartyIndex -= 1
    local numPlayers = #Parties[team[1]]
    --Look for a party small enough not to go over MATCH_NUM_PLAYERS
    while usedSlots < MATCH_NUM_PLAYERS do
        local nextParty = Parties[nextPartyIndex]
        if not nextParty then
            error("Not enough players queued, can't match!")
        if #nextParty <= usedSlots then
            table.insert(team, nextPartyIndex)
            usedSlots -= #nextParty
        nextPartyIndex += 1
    --Remove team party indices from queue, and replace with actual parties.
    for i = #team, 1, -1 do
        local teamPartyIndex = team[i]
        local party = table.remove(Parties, teamPartyIndex)
        team[i] = party
    return team

This would work, but if you have 1000s of players it would probably be pretty slow. The issue is that even if there’s 4 players in a party, it will first look through all parties with 4, then all parties with 3, then all parties with 2 and finally the parties with 1 player. If you want to fix that, one way is to have separate Parties tables for each number of players in a party. That way it’s pretty much instant to find a team with a specific number of players. E.g.

local PartiesBySize = {
    [1] = { {p1}, {p2} },
    [2] = {},
    [3] = { {p3, p4, p5} },
    [4] = {},
    [5] = {}

Hi, thanks for your answer but i have a question what do you mean by UsedSlots ?

1 Like

Whoops, forgot that variable somehow. It tracks how many slots are used so far, so it should start at 0. Oh, and it should be incremented by #nextParty, not decremented

This topic was automatically closed 14 days after the last reply. New replies are no longer allowed.