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

[Hans-Henrik Staerfeldt]

On Wed, 5 Jun 2002 Daniel.Harman at barclayscapital.com wrote:
> From: Dread Quixadhal
 
>> 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.

The speedup would be when objects (players etc) move, you would
delete/insert the moving objects in a smaller tree containing only
the most mobile objects, resulting in a speedup, since the
delete/insert function otherwse would be on the full set of
objects. The less mobile objects would then be located in a
(hopefully) larger structure, that would not be updated frequently.

Making two lookups and catenating the result for each 'sensing'
might give a speedup, depending on your ratios of movement and
sensing events.

Of 'm' is the size of the set of moving objects and 's' be the size
of the set of static objects, the runtime for a move and a sense
would be;

  seperate structures:

    sense event: O(log(m)+log(s))
    move event: O(log(m))

  one structure:

    sense event: O(log(m+s))
    move event:  O(log(m+s))

So the feasability of this method depends on the ratio of moving and
static objects as well as the ratio of sense and move events, but it
could become feasable, if you have a small number of moving objects
and/or a large number of move events.

Hans Henrik Stærfeldt   |    bombman at diku.dk    | work:  hhs at cbs.dtu.dk      |
Address:                |___  +45 40383492    __|__       +45 45252471     __|
DTU, Kemitorvet,        | Scientific programmer at Center for Biological     |
bygn 208, CBS.          |  Sequence Analysis, Technical University of Denmark|

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