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.
>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?
>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.
>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 |
+------------------------------------------------------------+
This archive was generated by hypermail 2b30 : 12/08/00 PST