what is the best way to implement a matchmaking queue?
In the game im making, matches have 10 players. Players can be in parties of up to 4 other players. A party has a matchmaking score (integer) that approximates the average skill level of the players in the party. I don't want players to be in the queue for too long, but I want the matches to be as fair as possible.
This is my current implementation (pseudocode)
let gamequeue = binary heap of parties
// ... gamequeue will be populated by parties that join the queue
fn matchmake(gamequeue):
convert gamequeue to a sorted vector
let potential_games = BinaryHeap<Game>
for i in (0, gamequeue.size())
let potential_game = Game
// Greedily choose parties
for j in (i, gamequeue.size())
// Stop making the game if the player already has 10 players or if party j's matchmaking score
// is too large compared to party i. Reach is calculated based on the time the party has
// been in the queue. Note that since the parties are in a binary heap there is a break because
// all the next parties will exceed gamequeue[i]'s matchmaking score + its reach.
if gamequeue[j]'s matchmaking score > gamequeue[i]'s matchmaking score + gamequeue[i]'s reach, break
if the game has 10 players, break
// If adding this party will exceed 10 players, try adding the next party
if adding the party would make the game go over 10 players, continue
add the party to potential_game
if potential_game has 10 players, add to potential_games
if potential_game does not have 10 players, continue
// At this point, potential_games will be populated with games sorted by a value "fairness".
// How fairness is calculated is irrelevant to this question
// Note that the first game in potential_games must be valid.
let finished_parties = HashSet<Party>
while potential_games isnt empty
let f = pop front of potential_games
for parties in f check if they are in finished_parties
if all parties in f are not in finished_parties, the game is valid! start that game
if there exists at least one party in f that is in finished_parties, continue; // skip this potential game
add the parties in f to finished_parties and remove those parties from the gamequeue
The runtime of my matchmaking algorithm is O(n^2).
Is there a better way to structure a matchmaking queue? Or is there a way to speed up my algorithm?
Since the size of parties can vary, I don't think its possible to do something like a sliding window. I feel like any dynamic programming solution would probably be slower than my "greedy"-ish solution.
