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

Ola Fosheim Grøstad <olag@ifi.uio.no> Ola Fosheim Grøstad <olag@ifi.uio.no>
Fri Nov 12 23:02:51 New Zealand Daylight Time 1999


Miroslav Silovic wrote:
> > 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.
> 
> Raycasting is done in time proportional to n^(1/D), where n is the
> number of objects you have to work with before you hit the first wall
> and D is the number of dimensions (2 or 3).

Why isn't it exactly O(n) ?  It doesn't make much sense that higher
dimensions scale better than lower? For a 3DDDA it certainly would be O(n+d)
where d is the distance to the object you hit. (dimensions does not matter)

Besides, wouldn't you have to do conetracing or simulate conetracing by
continuously spawning new rays the further you get away from the viewpoint
in order to sample the space at a reasonable resolution?

   viewpoint     
      / \ 
     /   \
    /  |  \
   /   |   \
  /    |    \
 /  /  |  \  \
/  /   |   \  \

This suggests that you will need to spawn (2^(D-1))^d rays. Warning: My math
is rusty...
--  
Ola





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



More information about the MUD-Dev mailing list