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

[J C Lawrence]

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:

  http://www.kanga.nu/archives/MUD-Dev-L/1997Q2/msg01271.html
  http://www.kanga.nu/archives/MUD-Dev-L/1997Q2/msg01515.html

Quoting from the former:

--<cut>--
  - 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
  everywhere...

  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] -
  #4[11, 12]

  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.
--<cut>--

<<Yes, I'm still trying to figure out how to effectively use the
neighborhood concept>>

--
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
http://www.kanga.nu/lists/listinfo/mud-dev