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

[Chris Jacobson]

On 6/15/00 1:04 PM, Joe Kingry (jkingry at uwaterloo.ca) stated:

>You must be using a queue implementation I don't know about. The eating
>duplicate part is not something I have a problem with, it's just well, in
>queue's as I understand them queue::get is going to remove and return the
>end item off the queue.
...
>  Add A |Q:CA     Add B's exits, note since A is removed it's added again...
...
>Now, if queue simply reads the item and then moves some "end of queue
>pointer" to the next item, then it would work as the queue then is holding
>everything that has been visited. Though this seems to me as a strange way
>to operate as then you have all this extra data that you'll never read again
>hanging on the end of the queue.
>
>So, where have I gone wrong?

You haven't gone wrong in your interpretation of the problem.

Most queues would pop the front...  One possible solution would be to use 
a "visited" queue, instead, and get very recursive with the function, 
rather than a looping function...

For example, the implement you talk about would experience queue problems 
if it did:

while queue isn't empty
   go to first item of queue (popping it)
   process
   loop through exits
      if exit isn't in list
          add exit to queue

Instead, do the following:

function(room)
   push this function onto 'visited' queue (actually, list)
   process
   loop through exits
       if exit isn't in list
           function(exit room)

after topmost call to function, clear list

Even this isn't ideal: while the first will end up getting into loops, 
the second is very stack intensive and recursive at the function-call 
level.
The ideal solution is, in my opinion, to use a variation of the first 
solution, this time with a list rather than a queue:

iter = start of list
while iter isn't end of list
    process with iter
    loop through exits
        if exit isn't in list
            add exit to end of list
clear list

- Chris Jacobson



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