Re: Breaking matchmaking deadlocks

Ah... I see what you are saying. I suppose that you want one of the hybrid keep looking if you initially paired up hybrids.

MSN
From: [email protected] [mailto:[email protected]] On Behalf Of Blair Holloway
Sent: Thursday, July 08, 2010 6:56 PM
To: [email protected]
Subject: Re: [Sweng-Gamedev] Breaking matchmaking deadlocks

If I understand you correctly, once the machines connect, regardless of the result, each machine goes into a passive state - the hunter no longer needs to hunt (it's connected), and the gatherer is, well, gathering. (Gathered?)

Let's say your target session size is four machines; once you're connected to someone, you stop being a hybrid, and you are either a gatherer, listening for more machines, or are essentially idle. How do you deal with these cases, where the machines have essentially "paired off", and you want to coalesce them into larger sessions? Would it not be more beneficial to keep some machines as hybrids?

On Fri, Jul 9, 2010 at 4:32 AM, Mat Noguchi <[email protected]<mailto:[email protected]>> wrote:
Why not have a separate task that is for the hunter/gather hybrid? When two hybrid tasks connect, you can then break the tie and convert one into a hunter and the other into a gather. If a gather connects to a hybrid, the hybrid should convert to a hunter, and if a hunter connects to a hybrid, the hybrid should convert to a gather.

MSN
From: [email protected]<mailto:[email protected]> [mailto:[email protected]<mailto:[email protected]>] On Behalf Of Blair Holloway
Sent: Thursday, July 08, 2010 1:02 AM

To: [email protected]<mailto:[email protected]>
Subject: Re: [Sweng-Gamedev] Breaking matchmaking deadlocks

For sure, rejecting a duplicate connection like this will work in cases where the connection is fully established. However, I'm not sure that it works if both machines join each other's games simultaneously. Let me demonstrate with ASCII!

(If the formatting is stuffed, try pastebin: http://pastebin.com/U1YP7Ain)

A -----a---c---*
        \ / \ /
         X   X
        / \ / \
B -----b---d---*

A = machine A's timeline
B = machine B's timeline

a = machine A sends request to join machine B's game
b = machine B sends request to join machine A's game
c = machine A receives request to join from machine B, accepts, sends back response
d = machine B receives request to join from machine A, accepts, sends back response

* = both machines suddenly realise that they are connected to each other's games

Because each machine is responding to each other's join requests in their "cone of silence" -- the time between their request to join a game and receiving the result -- they can't know to turn the other machine's request away; therefore, they end up becoming doubly connected to one another.

- Blair

On Thu, Jul 8, 2010 at 3:14 PM, Conor Stokes <[email protected]<mailto:[email protected]>> wrote:
Maintain a shared set of connections (in a hash or something) for both in-coming and out-going (hunting and gathering), protected by a lock and keyed by user. Then don't allow inserts/drop the connection into the shared set if you find a connection already there. It's a small relatively constant time operation and you should be able to set it up for the right order of operations such that you won't end up with an inconsistent set between players.

Cheers,
Conor

________________________________
From: Blair Holloway <[email protected]<mailto:[email protected]>>
To: [email protected]<mailto:[email protected]>
Sent: Thu, 8 July, 2010 10:50:25 AM
Subject: [Sweng-Gamedev] Breaking matchmaking deadlocks

Rather than taking the typical "join session/host session" approach with our upcoming title, we're going to adopt a matchmaking solution - the user selects the "find players" option, and under the covers the game deals with creating and joining as necessary.

We've been examining the matchmaking system described in "E Pluribus Unum: Matchmaking in HALO 3"[1], and decided to take a similar approach -- when matchmaking begins, a "gatherer" task hosts a session, and waits for players to connect to it, whilst a "hunter" task enumerates a list of sessions and tries to join each in turn.

Since these tasks happen simultaneously, it's possible to end up in a quasi-deadlock -- the hunter task from machine A can connect to the gatherer's session on machine B, whilst machine B's hunter simultaneously connects to machine A's gatherer; both machines would be simultaneously hosting two sessions, and each machine would be participating in both.

The easiest solution to this is perhaps to avoid the "deadlock" in the first place, and not simultaneously search and host. Indeed, the system described in Halo 3 seems to randomly decide at the start of matchmaking whether a machine is a hunter or a gatherer, and simply sticks to that choice until a timeout occur.

However, Halo has the advantage of a huge player base to make this work; we're expecting a few orders-of-magnitude less players, and are worried that when, say only a few tens of people are online at any given time, only gathering or hunting will make the matchmaking experience slow for the user. Therefore, we'd like to both gather and hunt at the same time, and try to avoid the deadlocks and "break" them when they occur -- i.e. when detecting simultaneous connections, choose one session to destroy, whilst keeping the other.

Does anyone have any suggestions for how to break these "deadlocks"?

Cheers,

- Blair

[1] http://www.bungie.net/images/Inside/publications/presentations/gdc2008_butcher_chris_matchmaking.ppt



_______________________________________________
Sweng-Gamedev mailing list
[email protected]<mailto:[email protected]>
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com


_______________________________________________
Sweng-Gamedev mailing list
[email protected]<mailto:[email protected]>
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com

_______________________________________________
Sweng-Gamedev mailing list
[email protected]
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com