| Pages: [1] :: one page |
|
|
| Author |
Thread Statistics | Show CCP posts - 1 post(s) |
Covert Kitty
Amarr
Hedion University
   |
Posted - 2009.01.20 23:12:00 -
[1]
This may not be exactly the right forum to ask this is, however I couldn't find a forum for "3rd party app development". At any rate, I'm working on an app, and part of it requires that I can determine how to get from one system to another. I have the eve database, could someone give me a general overview of how a course is determined without a massive amount of guesswork?
Thanks.
|
Covert Kitty
Amarr
Hedion University
|
Posted - 2009.01.21 00:27:00 -
[2]
oh! i just found the right forum, reposting there. |
SengH
Black Omega Security
Pandemic Legion
|
Posted - 2009.01.21 02:00:00 -
[3]
Edited by: SengH on 21/01/2009 01:59:55
Dijkstra's algorithm |
Rakshasa Taisab
Caldari
Sane Industries Inc.
Ursa Stellar Initiative
|
Posted - 2009.01.21 10:47:00 -
[4]
Interesting question is... How willing would they be to include the distance between gates in their calculation of the weight of each edge. |
Mskpath3
|
Posted - 2009.01.22 02:30:00 -
[5]
 Originally by: SengH
Edited by: SengH on 21/01/2009 01:59:55
Dijkstra's algorithm
It is absolutely not Dijkstra's algorithm. Dijkstra's is a solution to the "travelling salesman" problem, which is completely different from the shortest-path problem. To find the shortest path, you simply use breadth-first search, and ignore any systems below your security threshold ("prefer safer" vs. "prefer shorter"). One of the simplest graph algorithms there is. |
Chum Tea
Janitors of the Empire
|
Posted - 2009.01.22 12:43:00 -
[6]
More likely something resembling the A* search algorithm.
|
Enthral
|
Posted - 2009.01.22 15:33:00 -
[7]
I don't think their route finding algorithms are particularly advanced. I believe they manually create the routes within each constellation to adjoining constellations, and from adjoining constellations to adjoining regions.
This would allow them to very quickly generate routes, because they've essentially reduced the number of nodes they need to check dramatically.
-Enthral
|
Xodd Hil
Gallente
Anunnaku
The Wrong Alliance
|
Posted - 2009.01.22 17:40:00 -
[8]
Originally by: Enthral
I don't think their route finding algorithms are particularly advanced. I believe they manually create the routes within each constellation to adjoining constellations, and from adjoining constellations to adjoining regions.
This would allow them to very quickly generate routes, because they've essentially reduced the number of nodes they need to check dramatically.
I would go with this, but with the avoidance system, this is not really true. Yes, they can still use it in any other case, but if an avoided system is in the path, it must create a new one in that region at least. The other problem is the lowsec-avoidance and security-weight setting, which could be done with precomputed paths, but would need at least a couple of separate paths.
|
Enthral
|
Posted - 2009.01.23 07:28:00 -
[9]
Originally by: Xodd Hil
Originally by: Enthral
I don't think their route finding algorithms are particularly advanced. I believe they manually create the routes within each constellation to adjoining constellations, and from adjoining constellations to adjoining regions.
This would allow them to very quickly generate routes, because they've essentially reduced the number of nodes they need to check dramatically.
I would go with this, but with the avoidance system, this is not really true. Yes, they can still use it in any other case, but if an avoided system is in the path, it must create a new one in that region at least. The other problem is the lowsec-avoidance and security-weight setting, which could be done with precomputed paths, but would need at least a couple of separate paths.
I wonder if when a system is added to the avoidance list, they recompute the routes within that constellation and then cache the results for that player. Then "all they would need to do" is substitute the cached constellation for the default one.
This might explain how they deal with avoiding systems where "podkilling has recently occurred". Avoiding lowsec systems can probably be explained by each constellation having two sets of internal paths: a safe and a fastest.
Have I mentioned how much I appreciate the new "avoid system" feature? :)
-Enthral
|
TecHead 197701
|
Posted - 2009.01.23 14:44:00 -
[10]
Try using the A* algorithm, should do the trick for you. No idea if this is the one used by ccp.
http://en.wikipedia.org/wiki/A*_search_algorithm |
|
|
Verlic
|
Posted - 2009.01.23 14:55:00 -
[11]
Edited by: Verlic on 23/01/2009 14:55:38
I have written a program that calculates jump distances myself. I'm using the A*-algorithm to do it (it was mentioned some times already).
The following site has helped me very much in implementing the algorithm:
http://www.policyalmanac.org/games/aStarTutorial.htm
|
Uhr Zylex
Ginnungagaps Rymdfarargille
Blade.
|
Posted - 2009.01.23 19:26:00 -
[12]
CLRS to the rescue!
|
Ephemeron
North Eastern Swat
Pandemic Legion
|
Posted - 2009.01.23 19:52:00 -
[13]
Maybe it's same algorithm that is used to direct network traffic |
PirceHat
|
Posted - 2009.01.23 19:58:00 -
[14]
Oh you mean Dijkstras? |
|
CCP Explorer
|
Posted - 2009.01.24 16:43:00 -
[15]
Dijkstra.
Erlendur S. Thorsteinsson
Software Director
EVE Online, CCP Games |
|
|
|
| |
|
| Pages: [1] :: one page |
| First page | Previous page | Next page | Last page |