Re: 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]> 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]] *On Behalf Of *Blair
> Holloway
> *Sent:* Thursday, July 08, 2010 1:02 AM
>
> *To:* [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]> 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]>
> *To:* [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]
> 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
>
>

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