----------
From: Jeremy Elson [SMTP:jelson@CIRCLEMUD.ORG]
Sent: Monday, October 13, 1997 4:27 PM
To: CIRCLE@post.queensu.ca
Subject: Re: non-recursive tracking algorithm (that works)
Sean Butler writes:
>CODE:
>In Circle3 there is a graph.c file which contains the tracking algorithm for t
>he skill track. Although this algorithm may have at one time worked okay, aft
>er extensive changes to rooms, wilderness, etc., it doen't work now. I never
>liked it anyway. It is poorly commented and clumsily designed.
Clumsily designed? It's a completely straightforward implementation
of a BFS (breadth-first search) in less than 100 lines of code. In
the worst case it works in O(N) time on a world with N rooms.
Forgive me for not commenting it better; but I did write "now, do
classic BFS" assuming that anyone who wanted to know more would pick
up any algos or data structures book and read about how the BFS works.
If you could have even mentioned that BFS stood for breadth-first search anywhere in the code, I could have looked it up easily. If you don't know what BFS is, it's kind of hard to do much research on it. I was probably a bit harsh. After looking at it again I see that its design is not neccesarily clumsy. I think I was a bit peeved that it didn't work. But I will ask you this, why shouldn't it work if the data structures have remained the same where it counts. I am not even talking about cross-zone tracking, I mean I am 8 steps away in the same zone, and it doesn't work. The dirs have the same enumeration, the rooms still have the bit-vector and bit flag for marking, the zone is even flat with no overlap. It was a mystery to me. The recursive algorithm I wrote worked, but I am worried that when it is used in the wilderness, it will be too expensive. I will do more research on the BFS method and try to make it work.
>Does anyone have a decent idea as to how to do this the right way. For exampl
>e, one that doesn't mark the rooms as it goes. One that doesn't use an expens
>ive recursion.
Huh?? Where exactly does it recurse? (Since when is recursion
expensive, anyway?) And why isn't BFS "the right way"? How can any
graph-searching algorithm work without marking rooms as it goes, or in
some other way remembering what vertices it has visited already?
I wasn't saying that you used recursion. I have found a way to do tracking with recursion that is even smaller than 20 lines of code. I just didn't want someone to respond with a post about how to use recursion to do it. By the way, recursion is expensive if its not tail or head recursion. Each successive call uses up another stack frame, do this too many times and its expensive both in time and memory. A program only has so much stack.
>One that can be called a thousand times per minute without indu
>cing server lag.
If you find one, let me know. You could probably change the current
one to enqueue and dequeue the vertices without using malloc() and
free(), but other than that you won't do much better IMHO.
You are probably right.
>All I am looking for is a desgn, a theory, I don't need the actual
>code.
If you're looking for theory, I suggest you see the classic book
"Algorithms" by Cormen, Leiserson, and Rivest; in particular, Section
VI ("Graph Algorithms"). There, they present a number of algos for
computing the shortest path between vertices in various types of
graphs. However I think you'll find that on an unweighted directed
graph (e.g. a MUD world), when trying to find a point-to-point
shortest path (i.e. as opposed to all-pairs shortest path, or
vertex-to-everywhere), you can't do much better than BFS. Which is
why I implemented it as BFS.
Please get your facts straight before posting on this topic.
-Jeremy
+------------------------------------------------------------+
| Ensure that you have read the CircleMUD Mailing List FAQ: |
| http://democracy.queensu.ca/~fletcher/Circle/list-faq.html |
+------------------------------------------------------------+
+------------------------------------------------------------+
| Ensure that you have read the CircleMUD Mailing List FAQ: |
| http://democracy.queensu.ca/~fletcher/Circle/list-faq.html |
+------------------------------------------------------------+
This archive was generated by hypermail 2b30 : 12/08/00 PST