Since I am way too tired and not having read through all things I''ll still give an attempt to help you out.
Assuming your paths are connected through waypoints. That is, *not*, drawing a path through unknowns. Then you get the shortest path. Remove the path (mark it) run again etc... Now when you are finished there will be no way of reaching the target. With the accumulated list you do a sort according to length. Think of vectors. Then you will have a full list of paths to the target with distance. Then you can build on this of course (which I will not go into here) to allow the AI to choose which way is more economical. The *economy* is decided on what requirements your map has.
Hope this gives some ideas.
____________________________________________________________
Try RealityRift at www.planetrift.com
Feel free to comment, object, laugh at or agree to this. I won''t engage in flaming because of what I have said.
I could be wrong or right but the ideas are mine.
Dijkstra's Algorithm
quote:
I'm assuming here that an alternative path than the one given by Djikstra, but with the same weight, qualifies as a 2nd-best path. (Technically it's 1st equal, but I am assuming that calling it 2nd would be what is desired by cryo75.)
Okay, then i think your method is probably sound enough, and i know there are some decently fast algorithms out there for this problem.(just search for k shortest simple( or loopless) paths).
I was just under the impression that what was being requested was a solution to 3 or 4(not that i understood why you would want a strictly longer alternate path ).
I agree that in the real world there will probably be very few paths with exactly equal distances, but it would be "prettier" to have a more general solution
To Cryo75:
I actually dont think the Eppstein technique is that complicated, but it can yield alternatives paths that contain cycles(but you can just remove those and hope there are some left
.Btw, were you actually in need of the 2nd best simple path striclty longer than the optimal one, or just the second best simple path?
[edited by - ziphnor on October 27, 2003 12:54:42 PM]
Author
I think I came up with an idea on how to overcome the problem. Look at
the following:
A
B C F E
F 25 G
21 F
22
I want to go from A to F, so I have:
ACF = 21
AF = 25
AEGF = 22
Dijkstra will give me ACF which is correct. But from the above we see
that A has 4 neighbours which can lead to F. So what I could do is
iterate through each of A''s four neighbours like this:
Iteration 1: Set B as not visited, C, F, E as visited. Run Dijkstra.
Will give me no results.
Iteration 2: Set C as not visited, B, F, E as visited. Run Dijkstra.
Will give me ACF, store the results.
Iteration 3: Set F as not visited, B, C, E as visited. Run Dijkstra.
Will give AF, store the results.
Iteration 4: Set E as not visited, B, C, F as visited. Run Dijkstra.
Will give me AGEF, store the results.
Sort the results according to length, ie. 21, 22, 25 and return the
paths to each and every one.
I think this should work.
Ivan
the following:
A
B C F E
F 25 G
21 F
22
I want to go from A to F, so I have:
ACF = 21
AF = 25
AEGF = 22
Dijkstra will give me ACF which is correct. But from the above we see
that A has 4 neighbours which can lead to F. So what I could do is
iterate through each of A''s four neighbours like this:
Iteration 1: Set B as not visited, C, F, E as visited. Run Dijkstra.
Will give me no results.
Iteration 2: Set C as not visited, B, F, E as visited. Run Dijkstra.
Will give me ACF, store the results.
Iteration 3: Set F as not visited, B, C, E as visited. Run Dijkstra.
Will give AF, store the results.
Iteration 4: Set E as not visited, B, C, F as visited. Run Dijkstra.
Will give me AGEF, store the results.
Sort the results according to length, ie. 21, 22, 25 and return the
paths to each and every one.
I think this should work.
Ivan
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
