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

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

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?  Then again, I am not quite sure what the criteria for
visibility in a MUD context is. Is one tiny spot enough for a mountain to be
visible, or is the obstruction of a straight line the basic problem that
needs to be solved? The first case is basically what a (real time) 3D
rendering engine has to solve, and the second case is what a raytracer needs
to solve (for shadow rays). These two (apparently related) problems are
approached with rather different datastructure solutions. And, as always,
static data will benefit from precomputation (Potentially visibility sets,
BSP, etc).

I am personally in favour of good old grids wherever applicable. They are
hard to beat in practice for many scenes and operations, I think? There
exists rather snappy line tracing algorithms (the 3DDDA) for grids which is
a reason for why this class of simplistic datastructures is one of the
winning ones in raytracing. (See RTNews for some discussions)

Anyway the basic point is: you need to define the specific needs and context
before you look for a solution in the spatial domain...
--  
Ola




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