5
\$\begingroup\$

I'm looking for matchmaking algorithm for a 1 vs 1 online game. Players must not be matched by their skill level, but instead by some specific filters set by the players.

Each player sends a request that specifies some set of parameters (generally, 2-4 parameters). If some parameter is specified, the player can be matched only with those who had sent this parameter with exactly the same value or those who haven't specified the parameter at all.

I need this algorithm to be thread-safe and preferably fast. It would be great if it worked with 3-4 or even more parameters, but even one is alright (in my case, it's a game bet). Also, I'd appreciate ideas on how to implement or improve this algorithm on my server platform - ASP.NET.

One more problem I'm facing is that match finding can't be executed right after the user sends request, because if another user sends a request before a previous matching is finished, they won't be matched even if they possibly could. So it seems that match finding should be started on schedule. I need help on how to optimize it and how to choose time interval for starting new match finding.

P.S. I've also posted this question on stackoverflow

\$\endgroup\$

2 Answers 2

2
\$\begingroup\$

The easiest method that performs well and gives a lot of flexibility is to use a SQL database, e.g. an in-memory SQLite database.

Using such, you can trivially find all pending matches that meet some criteria, insert a pending match, and remove "stale" matches that are too old (indicating no match was found).

Define a table that has a column for your match criteria and metadata, like so:

| id | username | created  | gamemode | gamesize | gamelength |
| 77 |    bob52 | 08:17:23 |      ctf |       16 |         15 |
| 63 | johnny77 | 08:16:59 |       dm |       32 |         15 |
| 59 |  theboy1 | 08:16:49 |      ctf |       32 |         30 |

When you get a request for a new match, do a query for rows matching that pattern, limiting yourself to the oldest match (depending on the sophistication of your criteria and how you select "good" matches, you may end up with a queue building up, e.g. where two players A and B don't match each other but C matches both, and you want FIFO behavior in these cases). Form a match on that pair. If there are no matches, insert the request into the table to be paired with the next matching request.

You can periodically clean out old entries that might accumulate. In general you don't need a timeout, though you do need a way to cancel match-making (and remove any rows for that client). There's no reason to always time out at 30 seconds an dmake a player resubmit their request over and over, especially as it might just be that matches could be found by just waiting a bit. If you are having long match-making times, that means your algorithm is bad, or your game is unpopular. Or you have unpopular game modes; if very few people play 32-person ctf with a 30min timer, just remove that as a valid option. The more game modes you have the more your playerbase is spread apart and the harder it is to make a match.

One nice advantage of SQL is that you can easily make some criteria less explicit. If a player has no preference on match length, that column simply isn't queried when looking for matches, and a value of NULL can be created for that column if the request is queued. Matches can have a "gamelength IS NULL or gamelength=:length" to the query so folks who don't care about game length can be matched with those who have a preference, which is a fine match.

A query from a user looking for any ctf match thus might look like:

SELECT id FROM matches WHERE gamemode IS NULL or gamemode='ctf' ORDER BY created ASC LIMIT 1;

(note that LIMIT is a non-standard extension, but a lot of DBs support it.)

Replace the id as appropriate. This might be the IP of the host user, a unique id for a dedicated server instance, or a per-match id used to coordinate users while spinning up a dedicated server instance. Whatever.

You can also keep matches in the queue for running games and have columns to track how many players are in the match (on each team) already and how old the match is, making is easy to selectively place someone into an in-progress game if a desired team color/type/whatever is in need of more people.

Using a SQL database also makes it easy to just move from in-memory SQLite to a full RDBMS if ever your game needs such. While I recommend strongly to avoid using a single SQL database for an entire world-wide game, you could easily having a single DB environment for each region of a game. RDBMS are not the most efficient ways to implement queues but they work well enough for most games, especially if you have a lot of match criteria.

Another option that can work a bit better in some cases is to create a list of queues. Create one queue for each game configuration choice. Eg. a ctf 32-player queue, ctf 16-player queue, ctf don't-care-how-many-people queue, a dm 32-player queue, etc. When a request for a match comes in, try each appropriate queue. Take the oldest match found (again, maintain FIFO ordering).

This works well if there are a smaller finite number of game mode configurations, and it can be scaled in some interesting ways, but in general is more work to do (especially to do well) than just using a SQL database.

\$\endgroup\$
1
\$\begingroup\$

The simplest way to do this is with a dictionary. That provides fast access to specific keys.

So, from each player you'll generate a dictionary with the parameters he set and fill in the dictionary. When the matchmaking is required to be done, you just check if the keys from one dictionary match any existing ones in the other one. If there is no such key, you just continue searching for the remaining keys.

Since you mentioned ASP .NET, here is a quick code that could do the matchmaking (it uses LINQ). Basically, what it does is it counts the number of conflicts (both have set a specific parameter and it's different).

Dictionary<string, string> player1Settings, player2Settings;
int conflicts = player1Settings.Keys.Count(k => player1Settings.ContainsKey(k) && player2Settings[k] != player1Settings[k]);
if (conflicts != 0)
{
     // OK
}

Of course, you can use a simple for loop and optimize the process by using TryGetValue to prevent double look-ups, if you really want.

With regards to the matchmaking interval, what I suggest is to allow the process of matchmaking to be a continuous process. For example, if I start finding a match, I should be allocated a specific time (like 30 seconds), and at intervals of 2-3 seconds to check again if any matches could be found. If in that period of time no match was done, then you'll just let the user quit or retry a new matchmaking process. You can even let the user see a progress bar based on the time left to find a match.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .