[MUD-Dev] Geographical space paritioning

[ceo]

Peter "Pietro" Rossmann wrote:
> "ceo" <ceo at grexengine.com> wrote:

>> They tend more often to coalesce into huge clumps in small areas
>> (too big for a single server to handle) or into lots of small
>> clumps

> which is why it appears to be good think to solve by
> cell-rebalancing. if a cell, which is handling a city, gets too
> high load, it need to shrink to get less load (less players). the
> surrounding cells will take the players. if it's too much even for
> them, more surrounding cells will divide the space (which
> countains out unlucky not-willing-to-lag players) take any space
> partitioning algorithm (quadtree, r-tree, even b(sp)-tree).  they
> will recursively partition the space until some condition is met
> (the number of players in the cell is less than max-allowed, for
> example)

I think you're missing my point; I didn't make it too explicit, so
that's probably my fault. I'm not sure (so forgive me if I've
misunderstood you), but you seem to be ignoring the working-set
issues. If you cannot fit a complete working-set on a single server,
you have to perform some form of synchronization or shared-time
between the servers sharing the set. Vector clocks and other
techniques from distributed systems are perfectly capable of
maintaining shared time, but at the cost of additional overhead for
every single game-action (which tends to be O(n) for the number of
players with a BIG constant hidden in there). Whenever you have so
many players in one area that a single server cannot process them
all, you probably have too many to be able to afford a vector clock.

This is just a theoretical statement - in practice, you may have a
particularly low-latency network available, or perhaps you can
absorb the extra cost of the synchronization some other way without
problems.

> but such design would be truly overdesigned, as there would be too
> much dynamic there and the system would be too easy to get to
> turbulent (chaos) state.  we can do better.

Yes, this can also be a problem, but if it's your only worry it's
very easy to solve. Just make sure the dynamic decisions are made
infrequently. You can get clever and use things like
hysteresis/damping/Knuth's feedback equation to give cells an
"affinity" for certain areas of space, but it's usually not
necessary.

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