[OT] This feels wrong (pthreads question)

Levi Pearson levi at cold.org
Mon Jan 29 12:56:53 MST 2007


Steve <smorrey at gmail.com> writes:

> The SceneGraph object turned out to be the easiest thing to code :D
> Essentially, it's a std::map objects called xline (originally there
> were yline and zline as well but as you'll see it turned out to not be
> nessecary).
>
> When we want to find out what objects are within x,y,z of another
> object first we search the xline map for all objects within n meters
> of our object.
>
> We then check the entitys y and z against each other for range (x,y,z
> coords are stored on the entity and the graph is indexed by x).
>
> If the objects turn out to be in range of one another, we create a new
> mini scenegraph and add all the objects that pass these 3 tests and
> return the new mini graph.

Well, that sounds reasonable, but there are some conceivable practical
situations where it might have unfortunate runtime behavior.  Consider
if a large number of objects happen to be clustered on the x axis, but
dispersed on the y and z axes.  This would lead to a large number of
excess y and z dimension checks.

The data structure closest to what I was partway along to inventing
was an octree, which is a 3-dimensional variant of a quadtree.
They're commonly used in such applications as collision detection and
visibility detection for 3d graphics, where you want to be able to
avoid drawing hidden surfaces.  This would be appropriate for you,
since presumably you want to avoid propagating messages through
barriers.

Another common data structure for proximity indexing is the R-tree,
which stores objects as hierarchically nested and possibly overlapping
minimum bounding rectangles.  There are also variants that use
circles/spheres instead of rectangles.  This sort of structure is
commonly used in GIS systems, where you often want to see what objects
are within x miles of a given location.

Do some wikipedia searches for those data structures to find some good
resource links dealing with learning and implementing those
structures.  For some good general MUD design references and
discussion, check the Wayback Machine archives of
http://agora.cubik.net/ which had a lot of excellent MUD-building
resources.  Unfortunately, it doesn't seem to be active anymore.

                --Levi
                      



More information about the PLUG mailing list