Senses & geographical events

Wout Mertens Wout.Mertens at rug.ac.be
Mon Jun 30 20:20:33 New Zealand Standard Time 1997


Yo!

I've been monitoring the threads about event sending to mobs that should
know about it based on their senses. (Neighbourhoods and stuff...)

Here's what I think:

You have a certain signal (auditory, visual, magical, ...), and a space in
which an event concerning this signal happens. Call it for example the
sensory plane. For the rest of the discussion, let's assume it's 2D, 3D
is easily derived from it. The mapping of real world to the plane (or
space) is left as an exercise for the reader, what with all those private
coordinate spaces rooms get.

Now, I assume we're working with discrete senses (floating point is
discrete, assume that I mean the smallest possible number when I say
unit), and that at a certain point the signal strength is 0. (otherwise,
don't bother with this system, right?) The signal strength versus distance
function can be any function, as long as it goes 0 starting from some
distance.

Call r the radius of the circle (you can do any shape you want if you're
masochistic enough) where the signal strength is one unit.
Then the area covered by the circle with radius r is the only place where
the signal is above 0. Now assume that an object can detect a signal
strength of one unit at a distance R. Then all objects that should receive
the event are on a maximum distance r+R(object) from the event source.

Now the problem is: How do you find those objects?

Cover the plane with squares with sidelength 2R, centered around the
location of the objects in that plane. Then all the squares that are
overlapped by the square 2r around the source, are likely receivers, and
you only have to check those for the r+R rule.

The last problem is: How to efficiently represent such a plane?

I propose that all the objects that can sense that signal, are put in
sorted lists:

One list for the leftmost x-coordinate of the squares and one for the
rightmost x-coordinate.

Each entry contains a list for topmost y-coord and a list for bottommost
y-coord, and of course those entries refer to an object.

To find the aforementioned squares, get all the entries for which
((minx <= leftx <= maxx) OR (minx <= rightx <= maxx)) AND
((miny <= topy <= maxx) OR (minx <= boty <= maxx))
To do this in a way that you get a unique list of candidates, maybe use a
tag field and tag the entries you visited with a timestamp (so you don't
have to keep clearing the tags)

These candidates can then be checked for the radii and for obstructions
(raytracing etc)

The lists should be something that is efficient in searches, and inserts
can be priceier (sp?). Note that it is normally less pricey to move an
entry in the list than to insert it, so you insert when an object enters
the plane and move when the object moves or changes sensitivity.

Also note that the contained Y-lists are normally very small (at least
when your coordinates are sensitive (I can't find the correct word)
enough), so these can be implemented with a different list technology,
especially since inserts are going to be much more frequent there.

Also also note that the Z-coordinate mostly is less uniformly crowded than
the X and Y, so if you do the space solution, it is wise to NOT use Z as
the primary key.

Also also also note that this solution could also be used to model
permanent sounds, smells etc in the world; just use this the other way
round, ie use the object to check the sources.

Thoughts?

Wout.




More information about the MUD-Dev mailing list