EVE Technology Lab

I was wondering if a tool exists, that can plan the shortest route between scattered assets?

For example, i have items in 40 different systems in The Forge, sorting them by distance and adding a waypoint at each systems creates a spiders web on the galaxy map, with a total of 190 jumps.

I would love a tool capable of telling me the most effective route between all of said systems (Tool would be able to fetch my asset list and make a route between the systems which i have assets in, with the option to exclude some systems)

Working out optimal routes for 2 systems out of 20 is fairly simple.
3 systems complicated it.
4 systems will make many things grind to a halt.



Each system pretty much multiplies the complexity by the number of systems remaining.

For people stating that 10+ systems is too computationally complex:
I agree that it is too computationally expensive to get an exact result, but you can get an 'educated guess' at an optimal route using AI techniques pretty quick. I have developed such systems in the past and a good example of such systems in place are the 'quest helper' router in WoW. You will sometimes notice that it will change the route even if you are standing still and doing nothing, this is because it has found a more optimal solution in time.

You would probably want to just ask the user for a set period of time to calculate for and then just return the best result found so far after that time period has expired. If you use php to retrieve the variables and dump them to a page and then write the ai logic in something like javascript, then you wont kill your server with calculations as the hard bit is done on the client's side, though it does mean the client can steal that part of the code if that matters to you. Will work on this myself when I find the time if someone doesn't do it already.

Here is a basic and visual of one of the possible AI techniques using what may sometimes be referred to as 'ant-colony optimization' and other names. Obviously you wouldnt waste resources/programming time displaying any visuals in calculation
http://www.youtube.com/watch?v=cZLGRzXm2y0&feature=player_embedded#!

and another which resemples the eve map in some ways:
http://www.youtube.com/watch?v=VK3ls-FiU4k&feature=related

@Daria Meridian Carlile
jEveAssets got a routing tool that will do what you ask.
Max for brute force is 13 locations - but, you can use nearest neighbor on as many jump you like and get a pretty good result.

I should note that I'm the author of jEveAssets.
Flaming Candle did the routing tool.

Well i would love to be able to choose a starting location but the ability to choose a final destination would be considered a bonus, not a necessity.
Reading your posts, i really look forward to seeing your project completed (or at least working in relation to the eve map), it is a very interesting one!.



Golden Gnu, I tried JEvEAssets and it does what i need of it to a good extend.
The route isn't optimal (which is obviously to be expected given the speed) and the fact that it sorts the waypoints alphabetically makes is a bit annoying, for example, both the start and end of my route through 32 systems, are both located at least 16 jumps from me.

Thank you for the link though, it is the best tool available at the moment :)

It would be fantastic if eve allowed you to import routes based on a specified structure so you got the yellow gates and everything. Too slow to manually check gate names every system

Yah I was thinking that. There are 14.x k systems. Strongly suspect something went wrong. I will be checking tonight. I checked the logs and didnt get any errors. I will post code if I cant find an issue. I must be adding systems to a closed list pre-maturely or something.

Was performing a standard breadth-first search for each system and using the data to populate a table with 'to' 'from' 'next-system' and 'num_jumps'.

ie A >> B >> C >> D
would result in
A to D = 3 jumps next system B
B to D = 2 jumps next system C
D to A = 3 jumps next system C

etc.

You don't need to pre compute every route now :)

Wow your amazing with interfaces! that looks pretty slick. I need an input field for the keyID, verification code, and character name.

When you said you have done the algo, you mean you have generated one of your own?

Sounds cool! Im running mine on just a 5hitty single-core 1.6ghz netbook. We shall have to race our algorithms when done. My netbook vs your i7. Ill let you know when my lookup-table which plays a crucial part in calculating routes is done. Please note that it doesn't pre-calculate every possible route there is, thats insane, it just tells you the next system you want between any two systems. There is a unique and subtle difference, the main one being that you save a lot more space for a performance penalty.

Stu