[MUD-Dev] Room-based vs. coordinate-based

[Miroslav Silovic]

> At 09:24 AM 6/12/97 PST8PDT, you wrote:
> >I'm working on R-tree based rooms (but I suspect I'll have to move my
> >current R-tree implementation into the driver, since it's both complex
> >and critical).
> 
> Interesting. Care to define an R-Tree, miro? The data structure for some
> reason is pulling up a blank for me.
> 

Okay, it's similar to B-tree, and it's similar to what CJL is talking
about right now. It's a ballanced tree where all leafs are on the same
depth, and each of the upper nodes has between 2 and N children (good
number is N=5).

Each node has an associated rectangle, and rectangle associated with a
non-leaf node contains rectangles of its children. Now to add a node to
a tree, you go through the node's children, calculate the size increase
for each rectangle, and pick one with minimal volume (although this
part can be optimized - volume doesn't always work best). Then you
recursively add to the tree. Now, adding to a tree can return two nodes,
and if that happened, you list them both in your children list, and if
you got above N, split in two and return both. Finally, on top of the
tree, construct a new root if needed.

Deletion involves recursive merging of the nodes - if you're masochistic
enough, but you can simply delete empty subtree, and it'll still work
reasonably well.

The good point of this structure is that it can be dynamically updated
as leaves get deleted and inserted, and that dynamic update will only
examine a small percentage of all objects (if the number of objects is
sufficiently large).

	Miro