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

[Brandon J. Rickman]

On 10 Nov 1999, Miroslav Silovic wrote:
> J C Lawrence <claw at cp.net> writes:
> >   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>--
> 
> Ummm. The size definitely matters. For example, if you were a human
> with another human, in a room full of rabbits, you'd see the other
> human attacking a rabit even with hundreds of rabbits - you're both
> above the little critters.

It is a matter of what is interesting, what is drawing the attention of
a given observer.  Let's equate one human with a dozen rabbits: The
human is interesting only while there are less than a dozen rabbits.
After that, the collective action of the rabbits would become the primary
focus, maybe because they have started to attack you and have the 
advantage of numbers.

Any such construction is intended as a shortcut for all those expensive
computations like collision detection, animations, multicast events. Given
ideal conditions - high bandwidth and fast machines - the existence of the
neighborhoods would become transparent and you would be allowed to see
everything at once.  (But there is nothing particularly valuable about
being able to see everything at once, you _have_ to focus on something.)

> I think sight should be resolved using raycasts, accelerated by
> dynamically updated BSP or octrees. Any decent raytracer does
> thousands of raycasts per second in scenes with much more than 100
> objects (following Nathan's ideas, you'd just approximate rabbits with
> spheres). All relevant algorithms can be found in Graphics Gems (guess
> what I used for my raytracer :) )

Sure, groupings could be resolved by some kind of line-of-sight
computation, but the purpose of the groupings is on a more abstract level.
Now that you have a set of neighborhoods that are relevant to a character,
you can do all the BSP calculations you need to render the scene.  Your
raycasting is going to bog down after a few tens of thousands of checks,
though, so if that happens you'd want to limit the processing to a smaller
subset of neighborhoods, &c.  

- B!




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