Jump to content
  • Advertisement
Sign in to follow this  
theflyingorc

Matchmaking

This topic is 3409 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!