| Pages: [1] :: one page |
|
|
| Author |
Thread Statistics | Show CCP posts - 0 post(s) |
Crazy Carl
   |
Posted - 2003.07.23 17:43:00 -
[1]
Ok, how about adding an option that figures out the quickest route that hits all the selected waypoints? The other day I had to make a pilgramage from Tash-Murkon to several waypoints reaching up toward the Forge. 250 jumps, my autopilot said. A lot of map inspection and 15 minutes later... 147 jumps. I had to refine the order of my waypoints. WHY can't the software do this for me? THe travelling salesman problem is a notorious computer programming exercise and I'm positive that open-source code could be found and adapted to this purpose.
|
Motive
|
Posted - 2003.07.23 18:40:00 -
[2]
Edited by: Motive on 23/07/2003 18:40:32
It is notorious because it is unsolved in polynomial time, therefore it take a huge amount* of time to find the best answer.
Heuristics can be pretty quick however, they just are not guaranteed to to find the best answer.
* By huge amount I mean greater than the age of the universe for fairly small values of N (number of stars in our case).
|
Crazy Carl
|
Posted - 2003.07.23 18:45:00 -
[3]
But the most basic of solutions being finding the shortest path from A to Z including points B, C, D, E, F, G...
How hard can that be?
|
Ctaesis
|
Posted - 2003.07.23 23:05:00 -
[4]
Carl, setting waypoints already computes the shortest path from A to B to C to D. I'm not sure what your problem is then?
There is no need to solve TSP.
________________
"Warp to Desktop" -- American PCGamer
|
Ctaesis
|
Posted - 2003.07.23 23:14:00 -
[5]
Ok, I've reread your question, and I see that you want to select a bunch of points first, then get a plot that touches each of these points with the shortest path.
This navigation plot could be done clientside, but it may take a long while. I think you should just be clever and use your map navigational inspection skizzles to plot your own map. Clearly, you "beat" the computer by reordering your waypoints.
In fact, you've already got yourself an algorithm right there:
1) Choose all your waypoints
2) Put them into a list
3) Find the number of jumps that it takes to go through all the waypoints in the order they appear on the list.
4) Decide if the hop count is small enough, if so, you're done!
5) Reorder the list.
6) Go to step #3
________________
"Warp to Desktop" -- American PCGamer
|
|
|
| |
|
| Pages: [1] :: one page |
| First page | Previous page | Next page | Last page |