[DGD] Using r-trees to subdivide a world

[Jared Maddox]

> Date: Thu, 26 Jul 2012 04:21:19 -0700
> From: Shentino <shentino at gmail.com>
> To: "All about Dworkin's Game Driver" <dgd at dworkin.nl>
> Subject: [DGD] Using r-trees to subdivide a world
> Message-ID:
> 	<CAGDaZ_rA8kNH0eid3xPvEL4+21MNi0EZ-+4tx9VJpO3O_pdB-g at mail.gmail.com>
> Content-Type: text/plain; charset=UTF-8
>
> I've been pondering making my main world a continuous world (possibly
> using spherical coordinates, possibly using cartesian, have not yet
> decided), and one thing I took a keen interest in looking at is the
> r-tree and x-tree and other spatially specialized b-trees.
>
> Does anyone have practical experience in dealing with these?
>
> I'm gunning for three dimensions.
>

I haven't done it myself, but for a (very) short time I was in a
hobbyist MMO project, so I have looked at this some.

I think the most important thing is to decide beforehand how your
world will be laid out. If you'll REALLY be using the z dimension,
then you will need to sub-divide that as well. If your layout will be
room-based then in most cases you can probably get away with making
each room into a separate node, with sub-nodes if it suits your room
or the particular mechanism you've decided on.

The easiest way to do the tests is to use cartesian coordinates with
an absolute reference frame, and walls that are always straight and
always aligned with two of the three axes. Walls that aren't always
aligned with the axes aren't that much harder (you can basically get
away with 1 quaternion for each wall), but walls that aren't always
straight (or even worse: walls that have holes or bumps) can greatly
increase the modelling difficulty (and time!). So, I would suggest
straight & flat walls.


Look at how different axes are represented. I suspect that in the
binary cases it works sort of like rb-trees, but with four (or six)
colors (to represent the relevant axis), but I don't really know.


Also relevant, I have considered using a 'mesh' system, where you have
a grid of neighboring areas that share information with each other.
When a character comes close enough to another area, the character is
registered with that area while staying registered with the one that
it's in. It is only unregistered from one or the other when it exceeds
some particular distance from the area that it's to unregister
(something like: register_distance + unregister_buffer, the idea is to
reduce spurious 'noise' from registering/unregistering).

The mesh has an odd advantage/disadvantage, in that it's intended to
be a multi-dimensional list structure. This would make e.g.
teleporting difficult, since you would potentially have to iterate
over quite a few nodes to find the one(s) you're looking for. The
spatial trees could be stuck 'on top' of them though, so areas could
be made to serve LARGE areas.