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

[Christopher Allen]

Ola Fosheim Gr=F8stad <olag at ifi.uio.no> wrote:
> Christopher Allen wrote:
> > The problem that Hilbert curves solve are when you have a number of
items in a
> > 2D space, and you want to find all the other items that are nearby. I=
n
mud
> > terms, these problems include how far you a shout can be heard,
determine if the
> > tower in the distance is visible, etc.
>
> I can see how it might help area/neighbourhood searches in sparsely
> populated areas. But I don't quite see how this would help visibility
> determination?

I see it used in the context of text games.

For instance, some MUDs now implement a single LPC 'virtual room' which
serves as an outdoor location. Players exist on an x,y grid in that room,=
 as
well as a number of objects like cities, towers, mountains, etc., each wh=
ich
also have an x,y coordinate as well as a height. One game I know of has a
virtual room of 32,000 rooms by 32,000 rooms.

The most time consuming operation is to determine which of those location=
s
is near the player. In fact, it was so time consuming they had to modify =
the
kernel so that the search was in tightly coded C rather the intepreted LP=
C.

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 typicall=
y
is a relatively small list, say of a dozen objects.

You can then sort that list by actual linear distance, modified by height
and possibly the intervening terrain. Then only tell the player about tho=
se
that might be visible. If you wanted to add some more complication, you
could even have slightly different descriptions depending on the visibili=
ty
and distance. These functions do not take that much time.

The result: "You see a house not too far to the north, an unusual rock
outcropping far to the west, and the top of tower beyond the horizon to t=
he
southeast."

------------------------------------------------------------------------
.. Christopher Allen                                 Skotos Tech Inc. ..
..                           1512 Walnut St., Berkeley, CA 94709-1513 ..
.. <http://www.Skotos.net>               o510/649-4030  f510/649-4034 ..




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