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

[Daniel.Harman at barclayscapital.com]

From: Dread Quixadhal

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

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

Well if your sense system is geographically based, then it makes
sense to have everything that can be sensed in your tree otherwise
you will have to deal with multiple look ups. I haven't tried to
implement anything like this yet but there is an article in Games
Programming Gems 2 which covers a technique. It was written by a
Verant programmer, but I have no idea which projects he's been
involved in and sadly I can't remember his name as its not in the
table of contents I just downloaded, but the article is called :

'Sphere Trees for Fast Visibility Culling, Ray Tracing, and Range
Searching', Games Programming Gems II, Charles River Media.

I confess that I didn't actually follow his description from the
article, but source is included which would probably help understand
his method. He does claim its pretty quick though, and theres a
decent chance its been tested in a highly loaded MMOG.

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