[MUD-Dev] Space partitioning, R-Trees?

[Dread Quixadhal]

Hi all,

I had an idea a few days ago, and of course went poking through the
archives here to see what 50 other people already did that 3 years
ago. :)

The short question I have, which my initial perusal of the web
hasn't answered yet, is about R-Trees and friends.  An R-Tree
partitions space into a hierarchy of minimal bounding rectangles and
allows you to quickly find the bounding rectangle for a given point.
Is it also efficient at finding sets of overlapping rectangles?

Here's why I want to know.

My idea was a variant of the neighborhood watch idea put down in
this list several years ago by J C Lawrence back in 1997.

  http://www.kanga.nu/archives/MUD-Dev-L/1997Q2/msg01559.php

My variant on the idea was to have each object present a
sense-broadcast radius, and have each living thing have a
sense-reception radius.  A small mouse would have a small broadcast
radius, a tree would have a much larger one, and a mountain would
have a broadcast of many miles.

If your sense-radius (bounding rectangle) overlaps the
broadcast-radius (bounding rectangle) of an object, then you are
close enough to resolve the object with that sense.  You then would
need to check for line-of-sight or other algorithms based on the
sense in question to verify that the object is indeed detected.

I think that provides an effective way to handle things like humans
and orcs being near each other at night.  They're both about the
same size and would be visible the same distance away in daylight,
but the human's night-vision radius is far smaller than the orc's.

Another question that comes to mind (might as well, while I'm
typing) is this.  Would it be cheaper to hang terrain data
(descriptions, etc.), objects, and living things all on the same
data structure and have it be more full, or would be better to put
all the living (and thus moving) things in one tree and all the
terrain in a seperate one that shares the same coordinate space?
I'm wondering on insert/update cost for the movers vs. search-cost
for the terrain/objects?

Thoughts welcome!

-quix.

_______________________________________________
MUD-Dev mailing list
MUD-Dev at kanga.nu
https://www.kanga.nu/lists/listinfo/mud-dev