[MUD-Dev] FW: A question of message propagation

[Joe Kingry]

I'm having trouble figuring out how to do message propagation. I believe
that is what I want to do. Well let me present a detailed example to
demonstrate what I want to accomplish:

|
E----D-
|    |
C--A-B-
|    |
F--G-H
   |

I've mapped a small section of a simple room system. I'll just assume each
link is two-way for now, but it should be possible to have one-way links as
well.  The problem is given a message event raised at location A, propagate
it to all it's surroundings.

Note that there is also the possibility of propagating up and down a
hierarchical tree within each location/node. For example the sending the
message to a mouse contained in a box in a location. This is simple though.
My problem arises with graph systems.

Now, as best as I can determine you could do this propagation with BFS
(Breadth-First Search) algorithm. This though requires a 'visited' flag.
Obviously it would be inefficient to make this boolean, so if each message
could some how have a unique identifier then each location/object could have
a last_message field which is used as the 'visited' flag of BFS algorithm. I
think this will work fine, assuming you have a system where all the
propagation is done by a single process.

I would rather do this recursively though, as this would allow each
subsequent location modify the message as they see fit and then propagate if
necessary.  I suppose I could still accomplish this in the iterative BFS
algorithm though.

There is also the problem if there are simultaneous processes trying to do
these propagations then a single last_message field is not going to work.

So I have two questions. The more important one: Is a BFS a good method to
handle propagation? I'm certain that I'm missing out on some standard way to
do message handling.. but I haven't been able to puzzle it out.  Less
critical is the question of how to do propagation given simultaneous
processes. I'm not very concerned over this problem as it is most likely I
will be dealing with a single process, but it might be the case that a good
progation "pattern"? solves this issue as well.

Thanks,

Joe




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