| Pages: [1] :: one page |
|
|
| Author |
Thread Statistics | Show CCP posts - 0 post(s) |
Merrowinger
Caldari
   |
Posted - 2009.12.20 20:38:00 -
[1]
Hi there.
I wanna do a tool, which includes a jump planer.
I have worked on it for a while right now, but i dont get it faster than 4-8 seconds for a route.
I know the ISCS jump planer and know that it takes only 1-2 sconds with that one.
So i wanted to ask, if someone has some info, about how this works, or has
an algorithm to find jump routes. |
Night Doc
Majesta Empire
|
Posted - 2009.12.22 10:09:00 -
[2]
Dijkstra's algorithm
- Fit EVE to screen |
Merrowinger
Caldari
|
Posted - 2009.12.24 11:13:00 -
[3]
Edited by: Merrowinger on 24/12/2009 11:14:28
Hi.
Thanks, although i didn't knew about this algorithm, it is exactly what i have done.
The problem is, that it takes a lot of work to do the shortest path map for the ~4300 solar system in eve,
that can be used with jumpdrives.
The ISCS Jumpplaner uses something else. I think he optimized his algorithm for speed with some dirty tricks
because my jumpplaner finds shorter routes most of the time.
At least i got my planer to do paths in under 3 seconds. But thats still a lot.
So i have to look, if there are some dirty tricks, that still give the shortest path.
One way were to do the shortest way map once per possible start system, and save them.
But that would mean 4300(possible start systems)*4300(systems in map)* 2(id and distance) *4(byte for long/float var) = 141 Mb of Data. A bit much for a simple jump-planer app, or what do you think?
Anyone has a better idea? |
Imca
Gallente
Total Mayhem.
Cry Havoc.
|
Posted - 2009.12.24 19:24:00 -
[4]
Edited by: Imca on 24/12/2009 19:25:02
ive been working on something like that a while ago. What really cut down the loadtime for me was using the data as presented in the datadump and replace all the different ids for the names as final step. I dont know what you use to code with but in php it also saved me a lot of time with proper coding and only retrieve data from mysql when it was needed and as much in 1 query as possible. With the system names as input i used the following steps:
systemnames -> systemids -> systemdistances -> optimal route -> and back to the systemnames.
i also used A* instead of dijkstra and bidirectional search.
edit: what also helps to cut down loadtimes is storing every planned route in a database so you only have to calculate each route once, ever.
|
mric angel
Caldari
|
Posted - 2010.01.03 14:42:00 -
[5]
you may also proceed in 2 steps
calculate jumps between regions
then jumps between systems of regions in path
you could also use constellations but path within region is fast enough
i too use dijkstra
but sure, if you can cache that is good
|
Xeross155
Minmatar
Novadyne Dynamics
Veni Vidi Vici
|
Posted - 2010.01.03 15:13:00 -
[6]
Hmm if you cache all routes it will only take a while to generate for the first one, however the problem is there's a billion possibilities for the from and to systems.
---------------------------------------------
Xeross' ventures into EVE |
Celebrain
1st Steps Academy
Tread Alliance
|
Posted - 2010.01.03 19:51:00 -
[7]
I've thought a bit about optimizing for route planning through jump gates, and realized that it could be optimized for how there are certain "choke point" systems where traffic must go through to get in and out of an area, jumps gate distributions and end points are not truly random throughout eve. Some caching could therefore be done for route segments between such choke points.
It seems though that some people here are talking about using capital jump drives though (since the eve client doesn't provide a route finder for that), and that's a different story when it comes to optimization, but in general a similar problem.
Remember that dijkstra's algorithm is designed to work well when you can give a different "weight" to each path segment ("edge"). If all individual edges are equal weight (for example, takes the same amount of time to jump through a gate, or activate a jump drive), then it's not optimal. In other words, its not necessarily optimal to use solar systems as nodes and jumps between them as edges, unless you can figure out a way to predict ahead of time and assign priority to those edges. With all edges equal weight, dijkstra becomes a simple breadth first search.
A few ideas of ways to assign priority to edges: 1) for gate jumps, cache shortest routes between choke points, and use cached route segments as your edges for any longer route planning that goes through any such choke points, with their length as a weight (more jumps in them being worse). 2) for jump drive jumps, maybe use a distance/direction calculation as a weight (covering more distance toward target being better)? since your object is to cover the most distance the fastest so you can do it in as few jumps.
Of course bi-directional modification to any algorithm might easily save some time too...
I'll need to think about it more, but that's a start...
|
Sable Blitzmann
Minmatar
Eve University
|
Posted - 2010.01.03 20:01:00 -
[8]
Edited by: Sable Blitzmann on 03/01/2010 20:05:12
Try this:
http://blog.magicaltux.net/2008/11/30/eve-online-pathfinder/
It's a binary database that maps the shortest number of jumps from systemA to systemB. It's the fastest way to do it (a few milliseconds to calculate from point a to point b).
The problem with it is that it's hardcoded and not very dynamic, meaning it's only real function is to return the shortest route between two different systems without taking region, system security, etc into account. So if you want to pass parameters, such as only go through certain regions, then this won't support it, but it's the best at getting you the shortest route in the fastest time.
You could also try to convert it into a MySQL database, but it could prove difficult.
 Originally by: Xeross155
Hmm if you cache all routes it will only take a while to generate for the first one, however the problem is there's a billion possibilities for the from and to systems.
Actually, taking only the systems into account (ie: leaving security, region and other crap out), it's only ~27 million possibilities (not including the unreachable Jovian regions).
|
Seidr
Amarr
Eternal Guardians Corp.
The Covenant Alliance
|
Posted - 2010.01.04 23:10:00 -
[9]
http://www.othala.co.uk/2008/02/05/route-finder-for-eve-online/
Check that out..I've not used it in a while, but the demo I have up somewhere still works perfectly fine with the most recent data dump and is pretty sharpish - ok, not as fast as the binary table previously mentioned..but this DOES work from a database, allowing for greater flexibility in your routes, returning systems selected on a thresh-hold (i.e. sec status).
If you have any trouble, drop me a line in game.
(and yes, I'm sorry about the site design..I will get around to changing it at some point!)
|
Wollari
Phoenix Industries
Wicked Nation
|
Posted - 2010.01.05 00:09:00 -
[10]
Edited by: Wollari on 05/01/2010 00:15:07
I can just speak about my jump planner. (on DOTLAN EveMaps)
* I'm using the A* algorythm to find a suiteable jump route.
* It's using s weighting algorythm to determe a good path (not the best).
* I'm using a precalculated table for all systems + systems in jump range + distance
* every calculated route will be cached in a seperated table and queried before the long calculation will be done.
My calculation time is also something between 1 to 6 seconds (depending on the distance) which is not too bad for a php script. Sure high level/standalone application should be a lot faster.
I can give a few tips if you like. About the initial graph. You don't have 27mil possible connections. It's only 2 millions. If you include highsec to highsec then 3.2. Why?
1) Cause you can limit it to the maximium jump range of a ship in eve. Carrier + JDC 5 is 14.625 LY. That cuts down the number of systems that are reachable and which needs to be calculated.
2) The method how you calculate a weight for each path. Depending on how you do the math you'll be somewhere between testing ALL systems and taking the shortest path possible or testing only a limited number of systems and get the best path concerned calculation time and precision. If you can get a good result with only 500 combinations in 1 second or the best result with 100000 combinations in over 60 seconds just to see that the way is 0.1 ly better is not really important. In the end the pilot will choose the safest route for him or the best for logistic, depending on standings, sovereigtny, hostiles and infrastructure.
3) Don't forget that you can jump out of highsec
4) Be aware of rounding issues of the jumprange of ships. --> Blog
---------
For the gate2gate planner I also started based on the route-planer link above, but I quickly realized that it won't last long. If you wanna take an avoid system into the calculation (avoid region/lowsec/system) you must do a weighted path selection. This won't work with just flood fill/run through the array until you reaced the system.
For the Route planner i'm using the A* as well. I've also added a feature internally to include the warping time into the calculation (for long warps) if you've redundant paths. But I haven't added the option to the frontend yet.
With this beeing said. Good luck
|
|
|
|
|
| |
|
| Pages: [1] :: one page |
| First page | Previous page | Next page | Last page |