[DGD] Using r-trees to subdivide a world

[Jared Maddox]

> Date: Fri, 27 Jul 2012 21:10:55 -0700
> From: Shentino <shentino at gmail.com>
> To: All about DGD and Hydra <dgd at dworkin.nl>
> Subject: Re: [DGD] Using r-trees to subdivide a world
> Message-ID:
>

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

Yeah, you should subdivide the z dimension as well.


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

Possibly difficult if you'll have wizards. I wouldn't want to have to
write code to handle rooms with internal protrusions. If I had to do
it, I would probably do it from scratch and base principles though, so
you might not have that problem.

Assuming no internal protrusions (all points on the walls visible from
all other points on the walls; when I say 'walls' assume that I mean
"walls, floors, and ceilings") you just need to check that a point is
on the 'internal' side of all the walls. With walls that are always on
a plane perpendicular to a single Cartesian axis the tests boil down
to less than/greater than test-pairs. With flat walls at arbitrary
non-intruding orientations, you just add one (or two if you aren't
buffering wall info) quaternion-angle rotation before each of the
test-pairs (this I have actually worked on).

If you want to allow rooms with internal protrusions, then I suggest
just breaking them into multiple rooms instead. With builder-tools,
this sub-division can be done automagically.


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

Especially with this, you should sub-divide the z axis, that way you
don't have to deal with it later. Also, it'll improve the case of e.g.
rooms on different floors of a tower.

I'm going to suggest a Cartesian system, but a mixed system (Cartesian
for everything smaller than a world, spherical for everything else)
could work too, if you wanted to write the code.

Spherical seems awkward for ordinary rooms.

Don't forget to deal with e.g. gravity. You'll want to (at the very
least) have each room keep track of an acceleration-field vector.


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

Out of curiosity, are you planning to allow construction/wizards? If
so, how will you handle it, by allocating them a 'plane'/r-tree
node/room that they get to be wizard in, and simply not extending the
capability to them elsewhere?


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

The split planes being what I refer to as '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).
>
> 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.
>

I'm going to suggest adding a 'portal' array (or whatever else) to the
r-tree nodes, where each array node contains info on where it connects
to (specifically, the node & portal that it connects to). You can then
outsource the info on what can and can't cross the boundary to the
relevant portal nodes.

Thinking about it, having portals just be another r-tree node, that
happens to be a shared child of 1+ other nodes, could be a good idea.
Just stick a reference to it into your portal array as a note to the
code, and give the portal the logic to deal with 2+ parent nodes.

If there isn't a portal then NOTHING crosses between spaces (except
maybe to go 'down' a level?) because there isn't a route to follow.


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

I intended the nodes to correspond to in-game regions, with regions
dynamically sub-dividing to compensate for the flow of
players/NPCs/etc., so I suspect that your design priorities are
different from the ones I was following.


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

You sound like you're already playing with the trees, what did you
need advice with?