Creating a matchmaker for your multiplayer game
mas-bandwidth.com
mas-bandwidth.com
This is actually something I hate about multiplayer games with matchmaking nowadays. I made the majority of my childhood friends only because we stayed on the same server and played together for hours on end. I don't think it's a stretch to say that a key reason for why we play multiplayer rather than single player games is to socialize. This has become increasingly more difficult when you just get a new set of people every 10-30 minutes.
Turns out several lived near the server's location, in Texas, and at one point my friends and I just happened to be going there to visit a friend who was stationed at the nearby military base, and so I ended up meeting up with them for lunch. Nice guys.
Also ended up in a similar situation multiple times (bunch of randoms found some server we liked, sticked around for matches across weeks, eventually became regulars and eventually figured out we lived nearby). Sometimes we'd bump into each other on other servers too.
After a couple of times of hanging out we've found out why (probably at least) we came across each other, we all default to sorting the server list based on ping (latency), and since we were all geographically close, we tended to end up on the same servers.
Also it was very consistently up and low latency compared to other servers, so that's why I kept going there at first. Later on I kept showing up because I got to know people on the server.
Getting grouped with the same bad team mates repeatedly would just make me quit the game.
Thanks for helping us, Glenn.
Our matchmaker needs a rewrite, and these posts are nice.
That's awesome! Well done
What do you sell that isn't already solved by XDP?
(not sure what GP meant, just providing the reference)
1. Let the game client apply to servers in datacenters where they will get low latency if that's relevant for your game
2. Wait 1 second on the server, then shuffle the list of clients and group every set of 4 into a match.
3. If no match is found after 10 seconds, add the client to servers in suboptimal datacenters
4. If still no match after another 10 seconds, put them in all the queues and join them to the first game it finds so they can at least play at all, even if they'll have lag no matter where they go
5. Determine latency either using the same IP:port as the game server will have because the route might differ from another port (citation needed imo. The author links another blog post for further info which is mainly a statistics lecture about averages hiding outliers and doesn't back up this claim that the port number makes a significant difference for latency in any but the most exceptional of situations where you're sent eastward instead of westward around the globe or so) or by collecting statistics to find which server was best for a given location and ISP over the past 30 days (seems over-engineered with extra downsides, like that you will have gaps in the data and that it might have changed)
Did I miss anything? The whole thing seems somewhere between "do the most naïve implication" (1–4) and doubtful (5). It's useful for devs to confirm the intuition they might have for the simplest implementation is correct but other comments saying this is a great blog surprise me when looking at these two posts
The hardest part about matchmaking seems to me finding players well-matched in skill without making them wait long, especially during off-peak hours, or having off-putting loss streaks because they (50% chance for each game) got matched against a slightly stronger or equal team and lost. The article doesn't even mention these aspects exist, let alone offer advice on tackling them
No citation, but here's some things to think about.
You can easily have two servers in the same facility, in the same rack, with very different ip addresses. Most of the time you'll get the same general route for all destinations within a /24 (v4) or /48 (v6), but not always. Two /24s at the same facility might get different routes, especially if there are capacity issues on the better route at any point.
From same IP to same IP, anywhere there's a redundant link, which link to use is generally selected with a hash on the 5-tuple {protocol, destination ip, sender ip, destination port, sender port} (sometimes on a smaller tuple). If traffic is unbalanced or if one link is lossy, you can get drastically different experiences with a change in port number.
If you've done traceroutes and seen multiple similar ips at a given hop number, it's probably the second effect; this is pretty common. Typical traceroute sends udp packets to the destination and modulates the sending port number. Sometimes, rarely, you can see drastically different routes within a traceroute. It's easier to do traffic engineering on a /24 level though.
Traffic on redundant links is balanced by hashing flows rather than on a per packet basis so that packets within a flow tend to arrive in order; out of order arrival is very expensive for endpoints, so it's better to ocassionaly have unbalanced usage than to regularly have out of order arrival.
Source: Ran a network accelerator with more than 50 million unique players for 5 years. Bad network performance is much more pervasive than you think. https://networknext.com
The reason you use the maps in the matchmaker is so you can look up the latency from client to datacenter in constant time and you don't have to waste any time on the client pinging ping servers to get the results.
Plus, it costs money to run pings through the network accelerator, and they always (from experience) converge to the latency map anyway.
And you're about to send 50 packets per second for an hour during the game. Is sending one packet per datacenter really a cost worth mentioning?
Given lat,long is a guess and even if it is accurate, doesn't correspond very well to network latency, why wouldn't you use something like the source /24 or /48 rather than lat,lon. You don't get a pretty picture that way, I guess.
Samy Duc wrote a really good deep dive into Apex Legends matchmaking that covers skill and team balancing: https://www.ea.com/games/apex-legends/news/matchmaking-2023
In terms of overall experience, the best approach in general is a purely random one. This is how you avoid the experience of getting trapped in a 20 game losing streak, even if you are a really good player.
If you allow the natural balance of good players winning more often and bad players losing more often, you will find things get a lot less messy in between. This also provides your bad players an opportunity to occasionally witness what they could become. When you only play someone 1% stronger than yourself, you probably don't have a great idea of what the upper bound actually feels like. This can become a serious trap for players who are seeking to grow their skills.
While I also have fond memories of pre-SBMM Halo/CoD from the 2000s, they're more focused on pure shooter mechanics rather forcing players to work together to win an objective, so doing well but losing still feels fine. I find SBMM is needed in more objective focused esport games like overwatch, because the game is designed such that it's harder to do well individually (and thus have any fun) if your teammates aren't doing well.
Perhaps this is the actual cursed aspect. In a free-for-all context (i.e. a team size of one), you would never have this kind of a problem. As you increase the mandatory team size to six, you are creating an entirely new universe of effects to compensate for.
In my experience, 99.99%+ of the frustration in Overwatch and League of Legends emerges from dealing with your own teammates, not your opponents.
For a few of the games I worked on, random matchmaking like you describe is a non-starter. If you're a 90th percentile player in one of our games, you effectively never lose to a 70th percentile player or below. Your rating will be so high that we can't give you any rating system points for the win. So the person who won got no reward other than the feeling of winning, and the person who lost played a match they had no hope of winning. It ends up feeling pointless to play as a top player because only 1 or 2 matches in 10 on average have any meaning for you. Needless to say, it also feels worse as a low rated player because you simply lose more often.
You don't want to have the users ping the servers themselves because those pings could be inaccurate or noisy, so you use historical average data for users in that region instead to get a nice simple number. But... how do you know where the user is? IP Geolocation? Can't that be wrong also?
Isn't it better to have a direct measurement which could be a little wrong than an average of a guess which could be really wrong?
EDIT: No, it seems that it's literally grouping players together in multiplayer games (but doing so in a way where latency between players is minimized.)
The example here is really simplified to focus mostly on the finding datacenters with low latency problem, but it could also include things like matching players of similar skill together, finding a set of players that would make balanced teams, making sure that players who are partied up together play in the same match and so on.
Basically, just like matchmaking in real life. It's the thing that works out groups of players who should play together in a match.
You can turn off shuffling if you want.