[MUD-Dev] Spatial datastructures and their application (Was Re: Hilbert Curves)

[Ola Fosheim Grøstad <olag@ifi.uio.no>]

Christopher Allen wrote:
> A faster alternative is to do a Hilbert search to find those objects that
> are within 100x100 points around the player. This delivers a list of
> potential visible objects in a rectangle around the player. This typically
> is a relatively small list, say of a dozen objects.

How fast do you move? If you just move a few points per look, then you would
benefit from a windowing approach (slide a window over the landscape as the
player move and add/remove objects that cross the window border). The bad
news is of course that you now have to update the (cached) state within your
window when something inside dies etc.

You can speed up the testing of surounding areas by having two bitmaps for
the landscape, one vertically oriented and and one horisontally oriented. 1
means something is present in the cell, and 0 means empty. Moving one cell
north east with a 128x128 window on a 64 bit processor would then involve a
cheap initial test of six 64-bit words. You could do millions of these per
second.
--  
Ola Fosheim Groestad,Norway      http://www.notam.uio.no/~olagr/




_______________________________________________
MUD-Dev maillist  -  MUD-Dev at kanga.nu
http://www.kanga.nu/lists/listinfo/mud-dev