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

["Christopher Allen" <ChristopherA#skotos,net>]

Ola Fosheim Grøstad <olag#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. In
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 which
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 locations
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 LPC.

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.

You can then sort that list by actual linear distance, modified by height
and possibly the intervening terrain. Then only tell the player about those
that might be visible. If you wanted to add some more complication, you
could even have slightly different descriptions depending on the visibility
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 the
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#kanga,nu
http://www.kanga.nu/lists/listinfo/mud-dev