[MUD-Dev] Spatial datastructures and their application (Was Re: Hilbert Curves)
ChristopherA at skotos.net
Thu Nov 4 19:13:29 New Zealand Daylight Time 1999
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=
> > 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
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,=
well as a number of objects like cities, towers, mountains, etc., each wh=
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=
is near the player. In fact, it was so time consuming they had to modify =
kernel so that the search was in tightly coded C rather the intepreted LP=
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=
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=
that might be visible. If you wanted to add some more complication, you
could even have slightly different descriptions depending on the visibili=
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=
.. 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
More information about the MUD-Dev