[DGD] Using r-trees to subdivide a world

[Jared Maddox]

> Date: Fri, 3 Aug 2012 07:20:24 -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_qvgis0zb2e+aRrYGTEmNreaOzqiNo4w4ag61SL7LVRvA at mail.gmail.com>
> Content-Type: text/plain; charset=UTF-8
>
> I intend to have two different layers.
>
> The outer layer would be explicit geographic and political subdivisions.
>
> This would be the traditional cluster > galaxy > sector > star >
> planet and its moons > continent / ocean > nation > state > county >
> city > block / street > building > room > furniture > compartment >
> trinket.
>
> Here, objects that contain other objects would be named and listed in
> a directory of sorts and this is the primary layer that builders would
> be working on.  I intend for this part to be kept simple and abstract.
>
> I don't intend to use an rtree structure at this level to keep things
> simple for my builders, and also so that some other parts of my code
> won't have to deal with rtrees.
>

Ah, but how does this layer work? The individual 'nodes' would be
organized into a tree structure by virtue of some of them being
contained by others, correct? I suggest using an r-tree for this layer
simply because you're going to have a tree of volumes anyways, so (not
having used r-trees before) I assume that r-trees would map directly
to what you're wanting to do (basically, I understand them to be
'room' -trees).


> The inner layer would kick in if an object, such as a galaxy or an
> uncivilized stretch of wilderness, contained more inventory, such as
> stars or animals, than could efficiently be managed.  My cut-off would
> probably be about 50 objects or so before I shove everything into an
> rtree.
>
> This inner layer is where I'm most in need of an r-tree type thing to
> divide and conquer by physical location.
>

The reason why I recommend kd-trees for this layer is because I think
they would be simpler (basically, you just cut the 'overpopulated'
volume in half, and merge 'underpopulated' volumes). Depending on the
details of how you implement it, you could even use the location of
something to choose the dividing location.


> It's also intended to be a background sub-layer that is very much
> "under the hood" with interfaces that allow usage without worrying
> about the details.  Only geometry nerds would typically even be
> curious about it, but otherwise I want very much to keep the details
> at this level out of the way and neatly abstracted away as far as
> builders go.
>
> So I guess you could say that rtree-ing would act as a spatially
> specialized extension to inventory management.
>

Yeah, that sounds like the right way to think of it.


> I have thought about using rtrees for general geography, but how do I
> keep it simple for builders who don't care about rtrees?
>

I'd suggest a 'room' or 'allocated space' metaphor (note that this is
a metaphorical room: it shouldn't come standard with walls, a floor,
and a ceiling, though they should certainly be there if they were in
the right location before the 'room' was created). Basically, a new
geographic node is created by request (also, the request could be
refused, or an alternative offered, that sort of thing), and the
builder(s) are then assigned rights (I'd probably do it by giving them
a purpose-designed wiztool instance) that allow them to modify that
node. Thus, the builders don't really need to understand r-trees
particularly well, they just need to understand that they're dealing
with boxes of various sizes (and possibly orientations).



> Date: Fri, 3 Aug 2012 07:41:44 -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_qQU2rizBGxpSWFM4g=QdxFhM0BiwQYzLOfpe8JB6Rjwg at mail.gmail.com>
> Content-Type: text/plain; charset=UTF-8
>
> I do like your ideas btw, and I'm not trying to shrug them off.
>
> I just not sure about doing a complete rework of my design plans yet.
>

No problem. I'm trying not to be too forceful myself, since I'd
probably do things differently in various situations.