[DGD] Using r-trees to subdivide a world

[Shentino]

On Fri, Jul 27, 2012 at 8:15 PM, Jared Maddox <absinthdraco at gmail.com> wrote:
>> 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.

My world will be modelled after 3D.  Dragons can fly, xorn can dig,
and most of the action will be at sea level or so.

Since I don't have a clue what players will attempt to do, my system
would need to be a "can handle anything they try without going weird".

I also foresee possible expansion of my system to include
interplanetary and/or intergalactic travel in addition to intercity
and intercontinental within one world.

But it will also be room based, in that objects that completely
contain something hide it from view from outsiders that aren't peeking
inside that object.

So a castle will have a bunch of discrete rooms, but those rooms will
all have their own XYZ coordinates and if the castle were to suddenly
vanish into thin air and leave its contents behind, each object would
have first the room's and then the castle's XYZ coordinates added to
it as it was evicted into the open air.

> 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.

Basically it was planned to be a containment hierarchy of relative
coordinates, where each object's XYZ is expressed relative to the
"zero point" of its container.

The internal rtree nodes would be basically transparent containers
whose sole purpose is to split up the inventory into spatially grouped
nodes.

> 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).

I did have something like this in mind with "multiple containers"
where if an object crosses a boundary, it is considered neighbors of
everyone in both nodes.

And also to have events that propagate across such boundaries to do
their own grunt work of locating interested objects.

This also has the advantage that if an event cannot propagate across a
particular boundary, it can thumb its nose at the border and not even
disturb objects on the other side.  Example:  sound events versus
soundproof walls.

But I can't say I really have a mesh or grid system.

My "root" is just one big fat infinite plane/space of nothingness.
Outer space, basically.

> 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.

Indeed, which is one reason I voted against having a mesh/grid.
Instead, I just use a flat infinite canvas.

I managed to write a fairly optimized routine to take two objects and
derive the "common container" of them both.  If you're hopping from
one room to another in the same building, the common container would
most likely be the building.  OTOH, if you're trying to teleport from
beijing to seattle, you'd probably bubble up the tree a bit further
until you hit planet earth.

Once you do that, it's fairly easy to add up one branch and subtract
down the other to convert relative coordinates between the two nodes.
My default "move" handler does this automatically to adjust
coordinates.

In the odd case that two objects do not actually have a common
container, it can be implied that there is most likely interplanar
travel afoot that would need special handling anyway.  Ditto if during
the upscan of either object you hit a barrier that says in effect
"coordinates don't validate here"

> The
> spatial trees could be stuck 'on top' of them though, so areas could
> be made to serve LARGE areas.

I don't really plan on having a mesh so much as one big flat infinite canvas.

> ___________________________________________
> https://mail.dworkin.nl/mailman/listinfo/dgd