Sign in to follow this  
theflyingorc

Matchmaking

Recommended Posts

I was wondering if anyone had any ideas how to make a matchmaking queue that would, given groups of variable size, assemble them into a team for multiplayer deathmatches. World of Warcraft does this for its battlegrounds. I want players to be able to sign up to play as a group - and they will always play together. For my first attempt, we will have 2 teams of size 5 playing each other. Players can therefore sign up in groups from size 1 to 5 to get on a team. These are stored in an array as such: 1, 3, 5, 4, 1, 0, 0... In this situation, OPTIMALLY I would like to choose the 1, the 3, and the second 1 to form a group of 5. It would also be acceptable to get the 1 and the 4. However, the 5 would not be acceptable for our first pick. In THIS situation: 1, 5, 5, 5, 0 .... I do not want the 1 to permanently block the legitimate groups of 5 from going. In the long run, my queues could theoretically be several hundred groups large, so searching for every possible combination is very inefficient and would bog the system down too much. Does anyone know of a way to make this efficient?

Share this post


Link to post
Share on other sites
This sounds like the bin packing problem which is NP meaning there is not an optimal solution to be found. An efficient way would probably to use winner trees and do first fit. Also using a priority queue and keeping the elements in descending order will.

Share this post


Link to post
Share on other sites
Given that a major company like Blizzard does exactly what I'm describing, there must be some sort of heuristic used to do this in reasonable amount of time.

It's not QUITE the bin packing problem, as my objective is to find 1 set that totals up to 5, not fill as many games as possible. (it's useless to find all the possible games I can make for Alliance when I don't know how many I can make for Horde, to continue using WoW as an example).

Share this post


Link to post
Share on other sites
keep two lists one sorted by time of arrival and one by group size. sort the group size list by group size then start at the mostly full groups and try to complete them. When a group becomes complete match them and push them out the door. If the group at the head of time of arrival queue is older than X and can't be filled then try to match them with a group of the same size.

You want to be efficient in using your resources so sticking a couple of singles together to match with a group of three is a bad thing to do right off the bat because then you don't have any singles to match with a group of four. And while first come first serve seems nice you will run into problems where groups get hung out to dry waiting for just the right number to show up, so taking a match the group perspective first with a priority inversion for long waiting groups will work better.

[Edited by - stonemetal on March 13, 2009 5:26:07 PM]

Share this post


Link to post
Share on other sites
Assuming 5 is the maximum size:

If the first item on the queue is a 5, make that group 1. Otherwise, starting at the front of the queue, try to build up a 5. If you come across a 5, put that into group 2. If you come across a group which doesn't fit into group 1, see if it would fit if some of those already there are kicked. If you come across another 5, pair the two 5s off against each other and start that game, and return to the beginning.

That should work, I think.


Share this post


Link to post
Share on other sites
Quote:
Original post by Bob Janova
Assuming 5 is the maximum size:

If the first item on the queue is a 5, make that group 1. Otherwise, starting at the front of the queue, try to build up a 5. If you come across a 5, put that into group 2. If you come across a group which doesn't fit into group 1, see if it would fit if some of those already there are kicked. If you come across another 5, pair the two 5s off against each other and start that game, and return to the beginning.

That should work, I think.


I'm apparently not describing my situation well. Again, think Warcraft.

People who approach the game are either Alliance or Horde when they get there. We cannot start a game unless we have both teams ready.

I must check if I can form an alliance team, then check if there's a horde team, then, if I found both, commit both.

edit: Thank you guys for quick responses, though. This problem has been driving me nuts for 2 weeks or so.

Share this post


Link to post
Share on other sites
Quote:
Original post by theflyingorc

I must check if I can form an alliance team, then check if there's a horde team, then, if I found both, commit both.


Don't worry about having a team of A and a team of B just build teams then set them aside as teams ready to go. Then look at weather or not they are of teams of type A or teams of type B before you put them in the game.

Share this post


Link to post
Share on other sites
Quote:
Original post by stonemetal
Quote:
Original post by theflyingorc

I must check if I can form an alliance team, then check if there's a horde team, then, if I found both, commit both.


Don't worry about having a team of A and a team of B just build teams then set them aside as teams ready to go. Then look at weather or not they are of teams of type A or teams of type B before you put them in the game.


This doesn't deal with people dropping out very well, which is another concern.

Share this post


Link to post
Share on other sites
Quote:
It's not QUITE the bin packing problem, as my objective is to find 1 set that totals up to 5, not fill as many games as possible.

So, to restate your problem: given a list of positive integers <= k, find the first set of numbers (first come, first served) that adds up to k.

You could reduce the problem from an insane O(n!) brute force algorithm (which would quickly choke on a few groups of only size 3 or 4) by sorting groups into bins by size. Thus a group of size x would only be looking through bins of group size <= k - x, checking combinations until it finds a valid match.

So you have these bins (empty to start with), and a list of groups. For each group, try to match with other groups in the appropriate bins. If no valid match can be found, put it in the right bin, and move onto the next group.

That should be sufficient, I think.

Share this post


Link to post
Share on other sites
"Think Warcraft" isn't that helpful since I have never played ;)

But that means that instead of getting two teams off one queue, you are taking one team off each of two queues. The same method should work I think.

People dropping out is an entirely separate issue I think, and there isn't really a good way to deal with it in the general case.

Share this post


Link to post
Share on other sites
For people dropping, that happesn either before you make the decision (at which point the "ready" 5-team turns into an "unready" 4-team), or it happens after match-up, which really is no different from happening 10 minutes after match-up -- you have to have a game design for that.

Thus, the code can easily just do:

1) Assemble as many teams of 5 as possible out of the current waiting groups, for each side.
2) Pair up one team from each side, and call it a match, until one side is empty of full teams.
3) Repeat.

You may want to assemble teams by keeping a FIFO queue per group size, and trying to find a match for the oldest waiting group first, then second oldest, ... until you run out of possible matches in each round. All of this is done in a few milliseconds, so if someone drops *right* when you do the matching doesn't matter -- treat it as a drop after doing the match.

Share this post


Link to post
Share on other sites
Quote:
Original post by hplus0603
For people dropping, that happesn either before you make the decision (at which point the "ready" 5-team turns into an "unready" 4-team), or it happens after match-up, which really is no different from happening 10 minutes after match-up -- you have to have a game design for that.

Thus, the code can easily just do:

1) Assemble as many teams of 5 as possible out of the current waiting groups, for each side.
2) Pair up one team from each side, and call it a match, until one side is empty of full teams.
3) Repeat.

You may want to assemble teams by keeping a FIFO queue per group size, and trying to find a match for the oldest waiting group first, then second oldest, ... until you run out of possible matches in each round. All of this is done in a few milliseconds, so if someone drops *right* when you do the matching doesn't matter -- treat it as a drop after doing the match.


This does make a lot of sense. I seems like it would be very difficult to truly prioritize based on arrival time - I'd almost certainly have to give preference to a certain team size, so people would occasionally get passed in line, but if we have a pretty steady stream of people playing, it should work fine.

Thanks to all of you for your help.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this