These forums have been archived and are now read-only.

The new forums are live and can be found at https://forums.eveonline.com/

Player Features and Ideas Discussion

 
  • Topic is locked indefinitely.
 

New autpilot algorithm, 10+ waypoints
Author
Previous Topic Next Topic
Sir Substance
Sebiestor Tribe
Minmatar Republic
#1 - 2011-11-27 07:36:16 UTC  |  Edited by: Sir Substance
Hi CCP and all others. I'm currently watching my autopilot attempt to calculate the optimal route for a 19 waypoint route. Its taking a while, travelling salesman problem and all. However, for less then 10 waypoints, it solves it instantly.

I'd like to suggest an alternate algorithm, using this 10 point thing as a cap, for situations where more then 10 waypoints have been entered into the autopilot. This will generate a sub-optimal but still better then random in most cases route:

1. split all waypoints into regions.
2. if more then 10 regions, go to subpoint a)
3. order the regions into a minimal-backtrack route
4. arrange all waypoints within one region into a regional stargroup, if a region contains more then 10 waypoints, go to subpoint b
5. optimize all regional stargroups independantly
6. Hook each regional stargroup up to the next

a)
1. use clustering to sort regions into sufficient number of equal width groups by relative proximity, such that no group has more then 10 regions
2. Perform main tree for each region group, connect tail of each region group to head of next

b)
1. use clustering to sort systems into sufficient number of equal width groups by relative proximity, such that no group has more then 10 systems
2. continue at step 5

The idea behind this algorithm is that it is acceptable to have a less-then-optimal route between each region, as long as there is minimal dicking around within the region itself. The same sacrifice is necessary within a region if lots of intra-regional waypoints are required

The beatings will continue until posting improves. -Magnus Cortex

Official Eve Online changelist: Togglable PvP. - Jordanna Bauer
el alasar
The Scope
Gallente Federation
#2 - 2011-11-29 23:39:24 UTC  |  Edited by: el alasar
if we had a way to have some good route calculated with about 20 waypoints would be nice.
more ideas for travellers in my ideas section...

please also check

autopilot optimization: option to classify a system to be the LAST in route

check the moderated 10000 papercuts evelopedia page! http://wiki.eveonline.com/en/wiki/Little_things_and_ideas_-_low_hanging_fruit_-_10000_papercuts comment, bump(!) and like what you like
Mistress Hemah
Royal Amarr Institute
Amarr Empire
#3 - 2011-12-06 17:19:41 UTC
this is a real life use case. could we please get a possibility to optimize this?

http://www.picvalley.net/v.php?p=u/1753/29729297418318075161323188096fXOs23RN2a8VsUrwVL3W.PNG
Sir Substance
Sebiestor Tribe
Minmatar Republic
#4 - 2011-12-15 02:47:42 UTC
I am surprised there has been such a lack of interest for this, TBH.

The beatings will continue until posting improves. -Magnus Cortex

Official Eve Online changelist: Togglable PvP. - Jordanna Bauer
el alasar
The Scope
Gallente Federation
#5 - 2012-01-01 06:25:59 UTC
bump for travellers

check the moderated 10000 papercuts evelopedia page! http://wiki.eveonline.com/en/wiki/Little_things_and_ideas_-_low_hanging_fruit_-_10000_papercuts comment, bump(!) and like what you like
Droxlyn
School of Applied Knowledge
Caldari State
#6 - 2012-01-01 06:34:42 UTC
Wow. I think I can understand your problem, just not necessarily how you got to it. If you have that many jumps, figure out which ones are closest to you, get them sorted out, then start manually figuring the rest out while getting to the first few..
Mardero
#7 - 2012-01-01 10:37:37 UTC
LOL. 19-waypoint route. I'm afraid the lack of response might be due to you being an extremely small minority. Smile
Mars Theran
Foreign Interloper
#8 - 2012-01-01 10:47:20 UTC
Rather than rely on your auto-pilot; you could figure it out yourself. I remember doing that years ago with a huge amount of jumps and waypoints. You just set new waypoints in route and calculate nearest as you go. Final destination is generally your starting point, so try to make it a return route with pickups both ways.
zubzubzubzubzubzubzubzub
malaire
#9 - 2012-01-02 06:32:21 UTC
Instead of using custom algorithm, game could just use one of the well known algorithms which are known to give at most 50 percent or 100 percent longer route than optimal.

Wikipedia article Travelling salesman problem says that Christofides algorithm give at most 50 percent longer route than optimal.

If for some reason that algorithm is not feasible, first article above also mentions simpler one based on minimum spanning tree which gives at most 100 percent too long route (in section Special cases / Metric TSP).

New to EVE? Don't forget to read: The Manual * The Wiki * The Career Options * and everything else
Goose99
#10 - 2012-01-02 16:32:17 UTC
40 jump routes stretching from null to high calculate instantly for me, even with massive amount of system avoidance. Hint: it's done client side, not server side. Time to get a new computer.
el alasar
The Scope
Gallente Federation
#11 - 2012-01-02 16:58:06 UTC
yes, it is done client side. not the number of jumps but the number of waypoints are the deciding factor for the needed time. 12-13 waypoints is ok. above that you are lost.

having not-optimal optimization would still be far better than having no optimization at all above 13 waypoints. at least an abort button... show the progress of the optimization...

actually avoidance systems could reduce time needed as they reduce the number of routes to be checked? depends on the implementation i guess...

check the moderated 10000 papercuts evelopedia page! http://wiki.eveonline.com/en/wiki/Little_things_and_ideas_-_low_hanging_fruit_-_10000_papercuts comment, bump(!) and like what you like
Sir Substance
Sebiestor Tribe
Minmatar Republic
#12 - 2012-01-04 12:00:41 UTC
Goose99 wrote:
40 jump routes stretching from null to high calculate instantly for me, even with massive amount of system avoidance. Hint: it's done client side, not server side. Time to get a new computer.


Hint: jumps are different to waypoints, and the fastest computer in the world groans under the weight of a sufficiently large traveling salesman problem.

As for those asking how I get more then 19 waypoints, its by setting up large region wide buy orders.

Doing it manually is rather annoying when you have over 500 systems in your assets list, and you have to do them 10 at a time.

The beatings will continue until posting improves. -Magnus Cortex

Official Eve Online changelist: Togglable PvP. - Jordanna Bauer
Elindreal
Planetary Interactors
#13 - 2012-01-04 21:01:39 UTC
bump
it'd be nice to just provide waypoints and have the autopilot create an optimal route
i can only stare at and twirl the starmap around so much
Tidurious
Blatant Alt Corp
#14 - 2012-01-05 09:20:13 UTC
Got done with a 17 waypoint route just the other day. Auto had no problem optimizing the route very quickly (a few seconds). Not sure what all the whining is about.
el alasar
The Scope
Gallente Federation
#15 - 2012-01-06 06:24:08 UTC  |  Edited by: el alasar
Tidurious wrote:
Got done with a 17 waypoint route just the other day. Auto had no problem optimizing the route very quickly (a few seconds). Not sure what all the whining is about.

troll? i just set up a 15-waypoint route to optimize. i am running an i5-750 @ 3GHz. eve got it done after 25min...

check the moderated 10000 papercuts evelopedia page! http://wiki.eveonline.com/en/wiki/Little_things_and_ideas_-_low_hanging_fruit_-_10000_papercuts comment, bump(!) and like what you like
Elindreal
Planetary Interactors
#16 - 2012-01-08 01:38:28 UTC
don't think troll... i think reading comprehension is just low and people mix up waypoints and jumps