[MUD-Dev] DGN/TECH: Implementing server side spatial partitioning

[Damion Schubert]

William Leader wrote:
> "Alistair Milne" <krug at krug.org.uk> wrote:

>> The problem with this LOS calculation is that when an player
>> moves so that an object appears around a corner, for the first
>> few frames it will be invisible until the LOS server catches-up
>> with where the player is located and starts sending the new
>> object with the update packets.  This "pop-in" is exactly why
>> servers send too much information, so that the client can fill-in
>> the gaps and keep the graphical experience consistent.

> Yeah thats the sort of problem I hadn't thought of. Most players
> wouldn't tolerated that sort of behavior and would probably
> precieve it as chronic lag, thereby lowering preceptions about
> they game. I don't see a solution to that off the top of my
> head. But who know something might come up in my Sleep.

Technical implementation of pathing, line of sight and obfuscation
are hampered by two key problems fundamental to online (and massive
multiplayer) game design.

The first is what you mention above, which is that we want an online
experience with the fluidity and movement of an offline game.  You
don't want objects popping in suddenly, nor do you want to see
monsters teleport across the landscape or experience rubber banding.
Fluidity of movement is extremely important to the player base, as
it determines the all-important 'feel' of the game experience.

Unfortunately, this fact leads us away, somewhat, from the golden
rule of 'never, ever trust the client'.  For example, you may set
your max rate of speed on your client to be 10 meters/second, but
set it on the server as 12-13 meters/second.  This is to allow for
the nature of the Internet, and ensure that the player who is forced
to play on a 28.8 connection on a mom-and-pop ISP in North Dakota
can play with no or minimal rubber banding.  It also opens up the
avenue for various speed hacks to occur.  But you have to find
solutions, because if the player rubber bands, he quits.

The other problem is sheer computation power.  Collision, Line of
Sight, Obfuscation, and Pathfinding are all computationally
expensive things.  They aren't horrible in single player games, but
if you have a world with 3000 players and 30000 mobiles, your server
will bog down.  Of course, if bodies in motion must check physics on
each other by doing so, you get some meaty computing when players
get together for a 100 vs 100 person siege.

As such, your programmers may be tempted to trust the client more,
such as doing a 'client compute and server confirm' scheme, or
having a more simplified collision system on your server than your
client.  How you deal with these issues is your call, but don't
forget to account for CPU load and net traffic when designing this
thing.

> "John Buehler" <johnbue at msn.com> wrote:

>> And for those looking for something for the client machine to do,
>> there's the whole task of keeping track of what the client has
>> ever seen from the server.  That can be tackled both for both
>> short-term and long-term objects.

>> If my character walked through a door into a room, the client
>> could record the appearance of everything in that room.  The next
>> time my character returns to the vicinity of that door (or simply
>> want to mentally review the contents) the client can show the
>> contents.  Perhaps they are shown in a faded color and/or with
>> translucency to indicate how old the memory is.

I've been privy to tech teams that have discussed solutions similar
to this, but to solve a different problem.  In Shadowbane, for
example, we don't worry too much about whether someone's hiding
inside of a shop with a closed door (it's not pertinent to our game
design).  However, we do have a very free-form world, where players
can build cities anywhere and decorate them how they like.  We've
talked about, in the past, timestamping cities and city assets so
that a city's data could be cached the first time you see it, and
updated only as necessary (thus, the goal was to reduce data
download).  But overall, the engineers were never convinced that the
benefits would outweigh the engineering cost - even city data
changes frequently enough to make lots of downloads likely.

Unfortunately, I'm just a designer trying to remember programmer
discussions within earshot, so all of the above is remembrances of
programmers theorizing over margaritas.

--d
_______________________________________________
MUD-Dev mailing list
MUD-Dev at kanga.nu
https://www.kanga.nu/lists/listinfo/mud-dev