Steve <[EMAIL PROTECTED]> 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 /* PLUG: http://plug.org, #utah on irc.freenode.net Unsubscribe: http://plug.org/mailman/options/plug Don't fear the penguin. */
