[DGD] Using r-trees to subdivide a world

[Shentino]

On Tue, Jul 31, 2012 at 7:56 PM, Jared Maddox <absinthdraco at gmail.com> wrote:
>> Date: Mon, 30 Jul 2012 04:55:04 -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_pN6sg1DfdOiqO_a-ZS1VCQNJ6j2y+T5OVH6zA21cBU9A at mail.gmail.com>
>> Content-Type: text/plain; charset=UTF-8
>>
>> Anyway, what I needed advice with was a good r-tree type setup that
>> generally avoids linear time operations for inventory management,
>> allows me to locate an object by its XYZ coordinates, and can handle
>> objects scooting around pretty much arbitrarily in 3 dimensions.
>>
>> I've looked at the r-tree article on wikipedia, and so far r*-tree
>> looks good, but I have zero practical experience with r-trees in
>> general.
>>
>> Most of the stuff I've found on r-tree setups assumes that the points
>> aren't moving.
>
> For moving points, I think I would just run a validity test (if the
> point's new position is still inside it's container, it passes), and
> on failure remove the point, and reinsert where appropriate.

Hmm...sounds good.

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

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

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.

As for why I wanted R-trees...well, to be blunt it was the first thing
I found on wikpedia that organized things spatially.

it was more of a "this looks kinda good, now how do I use it?"

To be quite blunt, I have zero experience dealing with them, but I
have a hunch it's what I'm looking for.

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