**Next message:**Tonster: "adding god levels"**Previous message:**Franco Gasperino: "Re: [Code] User Counter"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]

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

**Next message:**Tonster: "adding god levels"**Previous message:**Franco Gasperino: "Re: [Code] User Counter"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]

*
This archive was generated by hypermail 2b30
: 12/08/00 PST
*