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

[Ola Fosheim Grøstad <olag@ifi.uio.no>]

J C Lawrence wrote:
> > 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

I read/write mail offline. :/

I am not sure if I understand what the problem is. First of all, the premise
was that the average case was 12 objects in a 100x100 area. There certainly
are no optimal solutions for higher dimensions in the general case (assuming
all scenes, dynamics and operations are likely/desirable) as the computers
we use are rather "one dimensional" (like a Turing-machine)?

I didn't state what kind of primary datastructure to be used (only the
auxiliary one used for testing), but I accept the assumption you make about
using a grid (2d array). Let's then assume that you have a uniform 2D grid
of linked lists. Assume a granularity of one meter. I assume that you don't
intend to model things that it doesn't make sense to model explicitly, such
a swarm of mosquitoes. What would cause problems?  Big objects cause
problems, because the will cover multiple cells, and thus degrade
performance. (There are several ways to improve this, such as using multiple
grids with different resolutions, dirty hacks and such, but performance is
hard to assert without a data set)

>   Things start to get a little crazy, rabbits are hopping
>   everywhere...

This is not a problem anyway. A rabbit covers max 4 cells so the move() will
be almost constant and small. Large moving objects with lots of holes in
them are troublesome... (so don't allow them, or use another data structure
for them)

To make it fast even when there are lots of windows ("views") watching an
area makes  for some extra work though.


Anyway, for a MUD design, you are better off by thinking about what is
really essential. What does really make an impact on the user experience as
seen on the possibly very much delayed rendering on the user client. Which
is why I for now have abandoned this as well as physical interaction among
objects. It doesn't make as much sense when you get the response five second
late.

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

It is possibly better, but doesn't answer Allen's problem as described?

Anyway, I prefer to think more abstract and conceptually now than I used to
a couple of years ago. That is in the terms that match the resulting
experience rather than exact placements. For my own project I am still on
the thought stage, and have doubts to whether it will fly or be usable and
how to exactly do the implementation...

--  
Ola Fosheim Groestad,Norway      http://www.notam.uio.no/~olagr/




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