> > 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. >
I know, I know. The age-old battle between optimized and simple code - it's all a trade-off. As a professional contract programmer, I well know the difference between what's necessary and what's best. If it's not necessary to make the algorithm 100% efficient, then it's not necessary, but it is always best. In my line of work, you do what the customer wants an their dime, and what you want on yours. Basically I'm saying that in this case, since you are your own customer, you do what you feel is best. > > 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. > Ahh, I misunderstood the use of "complex" here. > 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. > This really is a more optimized method and could require a good bit more design and implementation code. I would agree that this is the "more correct" of the two. I hadn't put much effort into thinking of how best to optimize a search of this sort. This, however, would be awesome. I look forward to seeing the details of how you work it out! :-) Tony
