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

[Jon A. Lambert]

> Joe Kingry wrote:
> 
> Now, as best as I can determine you could do this propagation with BFS
> (Breadth-First Search) algorithm. This though requires a 'visited' flag.

Not necessarily.  There's no need to store whether you visited the room 
if you use a container that eats duplicates.  Below is a C++ fragment,
but it can be done as easily in C as well.   queue::get reads the first
entry off the queue, while queue::put adds to the end of the queue
only if the item isn't a duplicate.  


/**
 @param r starting room
 @param m message
*/
void walkgraph(Room* r, Message* m) 
{ 
  queue<Room*> q; 

  q.put(r); 
  while (!q.empty()) { 
    r = q.get();	
    // visit would contain the actual message processing code
    // and could propagate messages to object and containers within room.
    r->visit(m);  
    // assumes room contains list of exits - list<Exit*> exits;
    for (ExitListIter ex = r->exits.begin(), ex != r->exits.end(), ex++) {  
      q.put((*ex).room))   // assumes room is ptr to the adjacent room 
    } 
  } 
} 

> 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.
>

The Message being an object can be modified during each iteration to
reduce it's effect.  For example, Patrick Dughi mentioned a bomb that
exploded in a limited area. 

    ...
    r->visit(m);  
    // A Bomb Message is reduced in effectiveness each propagation
    if (m->type == BOMB) m->counter--;
    if (m->counter == 0) break;

    for (ExitListIter ex = r->exits.begin(), ex != r->exits.end(), ex++) {  
    ...

> 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.
 
The above would be safe from recursion by making a copies of Message 
And by adding lock checking in the room implementation.  

Room::visit(Message* m) 
{
   Lock l;
   
   do stuff...
   Lock l is destroyed upon leaving.
}

> So I have two questions. The more important one: Is a BFS a good method to
> handle propagation? 

Yes.  I'll bet there are probably a few more interesting ways to 
store room nodes that make other navigation algorithms more attractive.
Spanning trees, Quad-trees, R-trees, etc. ??

--
--* Jon A. Lambert - TychoMUD        Email:jlsysinc at ix.netcom.com *--
--* Mud Server Developer's Page <http://tychomud.home.netcom.com> *--
--* If I had known it was harmless, I would have killed it myself.*--
 



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