[DGD] Using r-trees to subdivide a world

[Jared Maddox]

> Date: Tue, 31 Jul 2012 20:38:33 -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:
> 	<CAGDaZ_oMu0p7hZUQEETwm8U93J5QMv4DViiDhVBxwSEuhAiaGg at mail.gmail.com>
> Content-Type: text/plain; charset=UTF-8
>
> On Tue, Jul 31, 2012 at 7:56 PM, Jared Maddox <absinthdraco at gmail.com>
> wrote:

>> But I also think I'd use a kd-tree, or maybe a splay-tree equivalent
>> inspired by a kd-tree (probably I'd use a separate tree for each axis,
>> instead of just one tree, since you could trivially implement this
>> with any binary tree implementation), so my advice may be off the
>> mark.
>
> As long as I can handle all three dimensions *at the same time*
>
> If I'm close in X and Y, but mr dragon is hovering a dozen miles above
> ms delicious deer and looking west, there is no way that the deer can
> be scented.
>
> I haven't yet tested having separate trees for each axis but I have a
> hunch it could wreck locality.  It's just an uneducated hunch though.
>

Depends on how you do it. I would be testing every one of the trees
(basically, 1-axis-per-tree would be to make the logic simpler,
nothing more) to find locality.

More importantly, I would technically use a nested-tree structure. It
would probably be something along the lines of having one tree
structure of regions, where the region nodes can themselves use
whatever implementation methods they want. Nodes would correspond
strictly to locations, so e.g. a tiger instance would contain a
pointer to the node it was in, and possibly other near-by nodes, and
those nodes would point to the tiger, but instead of the tiger being
in a "child node" pointer, it would be in a "data node" pointer.

I would also want everything that could be a data-node to have a
function for location-nodes to call when the data-node was being moved
to a different location-node. That way I could do density-compensation
(splitting & combining location-nodes) without having to worry about
breaking things.


>> Why are you wanting to use r-trees specifically? Is it in some way
>> important that the sub-divided spaces correspond to explicit rooms?
>
> Not at all, quite the opposite actually.
>
> The only "visible" subdivision intended is raw containment.
>
> Here's a good example case:
>
> In the case of a ginormous stretch of landscape with many many animals
> running about (perhaps a full thousand), I neither know nor want to
> care how the animals are grouped spatially, so long as I can find them
> efficiently when I need to see how much electrical damage they suffer
> if a bolt of lightning happens to strike, which would be a set finding
> operation that gathers up all animals close enough to be affected,
> followed by a standard distance calculation to assess how close they
> were.  And since animals are sentient beings, I really would rather
> allow them to roam where they please within that landscape and not
> play games with invisible fenching
> n
>
> Logically speaking, I have one landscape object containing hundreds or
> even thousands of animal objects.  In the implementation though there
> may be a few r-tree type layers between the landscape and the animals
> which take care of the tedium of making things efficient for
> searching, and also not overflowing the landscape's inventory array.
>

For this, I would probably use something kd-tree-ish, since I'm pretty
sure that would be the easiest option (among other things, using
r-trees for the area-inventory would require dynamic "room"
allocation).


> However, that landscape object may itself be part of my general
> terrain patchwork, which would be mroe of the explicit type of
> containment as I group it geographically and perhaps even by name.
> That geographical grouping wouldn't use R-trees.
>

Actually, I think that r-trees could potentially be a good option
here. As I understand it, r-tree nodes simply control a specific
volume of space. For example, a city could logically correspond to an
r-tree node, a nation's r-tree could have some "magical land" spell
effects permanently applied to it that are stored in the r-tree
node(s), etc. If you want more complex shapes than r-trees provide,
then allow each r-tree to point to a "region" object, and when
appropriate have multiple nodes point to the same region.