[MUD-Dev] Spatial datastructures and their application (Was Re: Hilbert Curves)
J C Lawrence
claw at cp.net
Tue Nov 9 18:38:01 New Zealand Daylight Time 1999
On Sat, 06 Nov 1999 03:11:32 +0100
olag <Ola> wrote:
> 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.
This gets pathalogical when object density rises, especially when
objects are more dense than your search array's granularity. Now
cosider the following scenario, taken from the Neighborhood thread:
Quoting from the former:
- Shoehorn and the magic hat -
Shoehorn and a dozen other characters are in a room. Shoehorn takes
off his magic hat and puts out a rabbit. Then he pulls out another
rabbit. And another. Dozens and dozens of rabbits.
We start with one neighborhood, [Shoehorn, 1, 2, 3, .. 12]. If we
limit the maximum number of object in a set to 13, then adding a
rabbit will require us to split this neighborhood into two (or more)
sets. Eight characters are standing near Shoehorn (hm, some bad
graphics might be useful here, oh well) and the other four, plus 7
and 8, are near a corner.
After trick #1:
#1[Shoehorn, 1, 2, 3, 4, 5, 6, 7, 8, rabbit1] - #2[7, 8, 9, 10, 11, 12]
Only the folks in Shoehorn's group see the next three tricks...
After trick #4:
#1[Shoehorn, 1-8, rabbit1-rabbit4] - #2[7-12]
Things start to get a little crazy, rabbits are hopping
After trick #5:
#1[Shoehorn, 1, 2, 3, 4, rabbit2, rabbit3, rabbit5] -
#2[4, 5, 6, 7, rabbit1, rabbit3] -
#3[7, 8, 9, 10, 11, rabbit4] -
Character 7 starts attacking rabbit1. Everyone in set #3 can see
the attack clearly. The folks in set #3 can see that 7 is attacking
_something_. Otherwise the room is too crowded for everyone to see
everything that is going on.
Well, I've spent too much time on this message. Some extensions
might deal with differently sized objects, or a clever method for
splitting up the neightborhoods.
<<Yes, I'm still trying to figure out how to effectively use the
J C Lawrence Internet: claw at kanga.nu
----------(*) Internet: coder at kanga.nu
...Honorary Member of Clan McFud -- Teamer's Avenging Monolith...
MUD-Dev maillist - MUD-Dev at kanga.nu
More information about the MUD-Dev