> entirely. (When your CPU performs 1 million *complex* > operations per second - for example-, is it really > necessary to shave 100K operations down to 50K > operations? Yes you save half the processing time, but > we're talking about milliseconds here.)
I'm going to pretend I didn't see that. > This really isn't that complex an algorithm. :-) ...once again, > coding style can easily obfuscate even a simple algorithm. > Here's my stab at what track.c is doing: The algorithm isn't complex in the sense that it's difficult to follow, it's complex in that the number of operations required to complete it increases exponentially as the number of nodes and paths increases. Also, what you are describing is an in-order traversal of the rooms. So you find the FIRST path, which could be far longer than the BEST path. What you need to do is expand to each room one path in depth from where you are, see if any of those are the room you're looking for.. then expand one path from each of those rooms, and so on.. By looking at rooms at each depth instead of traversing them with simple recursion, you are assured that you have the shortest path to every room present in each iteration. Of course you'll have to keep track of searched rooms to avoid getting stuck in a cycle.. I think a bit vector like unlimited affect bits would work well for that. I will try to put some code together tonight, see what kind of performance hit it gives compared to the snippet, and post it to the list if I figure out anything interesting. --Palrich.
