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

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

EVE Technology Lab

 
  • Topic is locked indefinitely.
12Next page
 

A* algorithm for route planner?

First post
Author
Previous Topic Next Topic
morrosis
Ministry of War
Amarr Empire
#1 - 2012-02-09 12:55:07 UTC
I'm in the middle of making a route planner, I've loaded the CCP data dump and am working around in it.

so far I have it doing

Quote:
Array
(
[Jita] => 0.95
[Ikuchi] => 0.99
[Maurasi] => 0.91
[Niyabainen] => 0.96
[Perimeter] => 0.95
[New Caldari] => 1
[Sobaseki] => 0.84
[Muvolailen] => 0.71
)


so it kicks out all the systems around Jita, but not the systems betwenn Jita and Amarr (testing area)

Now have people used the a* algorithm or have they used something else?

http://en.wikipedia.org/wiki/A*_search_algorithm
St Mio
Imperial Academy
Amarr Empire
#2 - 2012-02-09 13:17:10 UTC
Professor Alphane
Les Corsaires Diable
#3 - 2012-02-09 14:04:42 UTC
Interesting disscusion, shame a lot of the links are broken in that old thread.

Makes me wonder though what functionality the OP needs to implement that isn't already available somewhere?

[center]YOU MUST THINK FIRST....[/center] [center]"I sit with the broken angels clutching at straws and nursing our scars.." - Marillion [/center] [center]The wise man watches the rise and fall of fools from afar[/center]
morrosis
Ministry of War
Amarr Empire
#4 - 2012-02-09 22:33:32 UTC
Professor Alphane wrote:
Interesting disscusion, shame a lot of the links are broken in that old thread.

Makes me wonder though what functionality the OP needs to implement that isn't already available somewhere?


Yes, there are a million and one of these all over the net. Thing is not one of them were made by me! Nothing new will be done except it will be made by me and I can say that I have done it.

It's the same as saying why do anything as someone some place has already done it.

Not intended as a rage or anything, please to not read it as such, Simply a statement.
Petrus Blackshell
Rifterlings
#5 - 2012-02-09 23:46:43 UTC
This thread belongs in Eve Tech Lab?

A* is a good choice for a point-to-point search algorithm, as you can easily define a decent time heuristic, though seeing as how Eve is a closed universe I see no reason to not just use Dijkstra's algorithm to pre-compute the shortest route from every single system to every single other system. Sure it's a O(N^2 logN) solution and would take hell of a long time to run and a lot of space to store (some 10 million entries) but then every search would just yield an instant result.

Accidentally The Whole Frigate - For-newbies blog (currently on pause)
Akirei Scytale
Okami Syndicate
#6 - 2012-02-09 23:49:09 UTC
Nothing wrong with a personal project.

Good luck, wish I could be of more help.
morrosis
Ministry of War
Amarr Empire
#7 - 2012-02-10 00:09:06 UTC
Petrus Blackshell wrote:
This thread belongs in Eve Tech Lab?

A* is a good choice for a point-to-point search algorithm, as you can easily define a decent time heuristic, though seeing as how Eve is a closed universe I see no reason to not just use Dijkstra's algorithm to pre-compute the shortest route from every single system to every single other system. Sure it's a O(N^2 logN) solution and would take hell of a long time to run and a lot of space to store (some 10 million entries) but then every search would just yield an instant result.


Last night, I was playing around with Dijkstra's algorithm, I found a php pseudocode for it and played with it a little and yes it is very slow very very slow.
Professor Alphane
Les Corsaires Diable
#8 - 2012-02-10 01:03:30 UTC
morrosis wrote:
Professor Alphane wrote:
Interesting disscusion, shame a lot of the links are broken in that old thread.

Makes me wonder though what functionality the OP needs to implement that isn't already available somewhere?


Yes, there are a million and one of these all over the net. Thing is not one of them were made by me! Nothing new will be done except it will be made by me and I can say that I have done it.

It's the same as saying why do anything as someone some place has already done it.

Not intended as a rage or anything, please to not read it as such, Simply a statement.



Fair enough just wondered if you'd found a new take on it is all, good luck with your project though Cool

[center]YOU MUST THINK FIRST....[/center] [center]"I sit with the broken angels clutching at straws and nursing our scars.." - Marillion [/center] [center]The wise man watches the rise and fall of fools from afar[/center]
Sable Blitzmann
24th Imperial Crusade
Amarr Empire
#9 - 2012-02-10 03:06:58 UTC
Petrus Blackshell wrote:
This thread belongs in Eve Tech Lab?

A* is a good choice for a point-to-point search algorithm, as you can easily define a decent time heuristic, though seeing as how Eve is a closed universe I see no reason to not just use Dijkstra's algorithm to pre-compute the shortest route from every single system to every single other system. Sure it's a O(N^2 logN) solution and would take hell of a long time to run and a lot of space to store (some 10 million entries) but then every search would just yield an instant result.


I did this once. Took 6 hours I think, and gave back 27,050,401 rows. Basically it had system A to system B and the shortest number of jumps. 27 mil rows since it's effectively 5201 systems * 5201 systems (excluding Jove space and, of course, WHs). It's fairly quick to look up tho.

The problem with it is you cannot define and parameters in the search. No "avoid lowsec, avoid highsec, avoid this system, only use nullsec, etc". That's where A* pathfinding truly shines.
CCP Spitfire
C C P
C C P Alliance
#10 - 2012-02-10 06:09:04 UTC
Moved from "EVE General Discussion".

CCP Spitfire | Marketing & Sales Team @ccp_spitfire
Trenker
#11 - 2012-02-10 10:51:58 UTC
Sable Blitzmann wrote:

The problem with it is you cannot define and parameters in the search. No "avoid lowsec, avoid highsec, avoid this system, only use nullsec, etc". That's where A* pathfinding truly shines.


I think you are confusing some algorithms. Dijkstra has those distances between nodes which can be used as weights instead of actual spatial distances. AFAIK CCP uses Dijkstra for the AP, so with it you'll be fine.

If you just want the shortest path, you can go with something more simple like Breath-fist. I did it once (http://blog.evepanel.net/eve-online/static-data-dump/calculating-the-shortest-route-between-two-systems.html) works like a charm. Just use the mapSolarSystemJumps table from the SDD to populate the $jumps array and you are good to go.
morrosis
Ministry of War
Amarr Empire
#12 - 2012-02-10 11:53:04 UTC
I cracked the code, I now have it reading the jumps. Only draw back is it is not optermized for high sec only.
Desmont McCallock
#13 - 2012-02-10 12:06:12 UTC
The question here is on what base you are calculating the shortest distance?

1. On shortest AU distance
2. On shortest jump distance

Personally I managed to do 1, but have no clue how to do 2. Anyone with inside please feel free to contribute.
Steve Ronuken
Fuzzwork Enterprises
Vote Steve Ronuken for CSM
#14 - 2012-02-10 13:46:16 UTC
I guess the way to manage high-sec only would be to filter the result set, based on the security level of the system.

You're already hitting the mapsolarsystem table for the name, so you should be able to drop in a security level where clause.

Woo! CSM XI!

Fuzzwork Enterprises

Twitter: @fuzzysteve on Twitter
Zifrian
The Frog Pond
Ribbit.
#15 - 2012-02-10 19:11:11 UTC
I have tried to do this with little success in the past. I also started with A* then went with dykstras but had issues. If anyone had a good walk through I'd appreciate it.

Maximze your Industry Potential! - Download EVE Isk per Hour!

Import CCP's SDE - EVE SDE Database Builder
Osku Rei
Pixel 6
#16 - 2012-02-12 17:04:41 UTC  |  Edited by: Osku Rei
I created a D* route planner for alliance jump bridges a while ago (i cant find the forum link, think it was on the old forum) Its still running, but obviously don't want to give out alliance JB's.

It took about 2 hours one night when i was bored :)

Here's Demo (but with no jump bridges as its a demo):
http://demo.evejb.com/index.php?from=Jita&to=Amarr

A player requested a tool to find all the connecting, when given a system. Here's my solution, its using my custom api:

https://forums.eveonline.com/default.aspx?g=posts&m=604378#post604378

I just finishing a up a A* route finder for a eve haulage company, that allows you to add waypoints, so go to A then B then C etc. Or find the quickest route stopping by each waypoint, so waypounts A.B.C. D.E the quickest route might actually be A,C,E,D,B :) + you can have a End point. Filter by security status etc + other fancy stuff.

Its on a local server atm so i don't have a link :(

Ok, so...


Quote:
Last night, I was playing around with Dijkstra's algorithm, I found a php pseudocode for it and played with it a little and yes it is very slow very very slow.


Then you code is poor/unoptimized, my D* algo is ~25 lines of code, it will do a 100 jump route (one side of eve to another) in ~0.2 seconds.

Quote:
A* is a good choice for a point-to-point search algorithm, as you can easily define a decent time heuristic, though seeing as how Eve is a closed universe I see no reason to not just use Dijkstra's algorithm to pre-compute the shortest route from every single system to every single other system. Sure it's a O(N^2 logN) solution and would take hell of a long time to run and a lot of space to store (some 10 million entries) but then every search would just yield an instant result.


No point, in the life of the tool, you will never get a player(s) wanting to find a route from every system in eve to every other system in eve, you are wasting a long time even just pre-calculating the route + wasting DB space/query time.

Just find the system on the fly (like normal) then cache the result in the db as a comma delimited string of system id's. So the table columns would be somthing like: fromSystemID, toSystemID, route. Then it's a simple SQl query just before every route request ("SELECT * FROM cache WHERE fromSystemID = '" . $fromSystemID . "' AND toSystemID = '" . $tosystemID)

Something like that (untested but you get the idea), if nothing is returned then you haven't calculated this route before so calculate it. Then you are not wasting space and you haven't got a ridiculous 27 mil record DB.

Here's some maths aswell :P
6 hours = 60x60x6 seconds = 21600 seconds
( you would also need to add on the time it would take to query that DB on each route request)
If a 100 jump route takes ~0.2 seconds to calculate, you can do minimum of 108,000 unique routes before you break even time wise (think you are going to be doing that many?). Even more routes when they are cached and non unique( like amarr -> jita)

Quote:
I guess the way to manage high-sec only would be to filter the result set, based on the security level of the system.

You're already hitting the mapsolarsystem table for the name, so you should be able to drop in a security level where clause.


When you grab all the system jumps from the SDD just add a 'WHERE' in t he SQL query to filter out all systems below a certain security status: WHERE fromSolarSystemSecurity >= " . $security. " AND toSolarSystemSecurity >= " . $security . "


Sorry if this is hard to read / messy but i'm rushing as i'm going out, hope this helps :)

P.s when doing A* stuff you can have a external cache, a database like explained above, and an internal cache in the form of an array (memory) which will make things even faster. So some psedo code:

Quote:
if( route doesn't exist in local cache)
{
if (route doesn't exist in database)
{
route = calculate route
}
else
{
local cache += route from DB
route = route from DB
}
}
else
{
route = route from local cache
}

Next generation of lottery tracker coming soon! http://evelotterytracker.com/

Please like my post if it has helped you :)
Sable Blitzmann
24th Imperial Crusade
Amarr Empire
#17 - 2012-02-13 19:11:18 UTC
Osku Rei wrote:

Quote:
A* is a good choice for a point-to-point search algorithm, as you can easily define a decent time heuristic, though seeing as how Eve is a closed universe I see no reason to not just use Dijkstra's algorithm to pre-compute the shortest route from every single system to every single other system. Sure it's a O(N^2 logN) solution and would take hell of a long time to run and a lot of space to store (some 10 million entries) but then every search would just yield an instant result.


No point, in the life of the tool, you will never get a player(s) wanting to find a route from every system in eve to every other system in eve, you are wasting a long time even just pre-calculating the route + wasting DB space/query time.

Just find the system on the fly (like normal) then cache the result in the db as a comma delimited string of system id's. So the table columns would be somthing like: fromSystemID, toSystemID, route. Then it's a simple SQl query just before every route request ("SELECT * FROM cache WHERE fromSystemID = '" . $fromSystemID . "' AND toSystemID = '" . $tosystemID)

Something like that (untested but you get the idea), if nothing is returned then you haven't calculated this route before so calculate it. Then you are


I precalculated it because I has a start system and many many end systems, and I wanted the shortest path to all. However, I also wanted to be able to sort by number of jumps... To be able to sort at the database level, the jump data needs to be there. To calculate it on the fly for many different systems takes too long (one system is fine, under a second. 20 systems takes many seconds), so I had to precalc everything.
Osku Rei
Pixel 6
#18 - 2012-02-14 23:17:33 UTC
Sable Blitzmann wrote:
Osku Rei wrote:

Quote:
A* is a good choice for a point-to-point search algorithm, as you can easily define a decent time heuristic, though seeing as how Eve is a closed universe I see no reason to not just use Dijkstra's algorithm to pre-compute the shortest route from every single system to every single other system. Sure it's a O(N^2 logN) solution and would take hell of a long time to run and a lot of space to store (some 10 million entries) but then every search would just yield an instant result.


No point, in the life of the tool, you will never get a player(s) wanting to find a route from every system in eve to every other system in eve, you are wasting a long time even just pre-calculating the route + wasting DB space/query time.

Just find the system on the fly (like normal) then cache the result in the db as a comma delimited string of system id's. So the table columns would be somthing like: fromSystemID, toSystemID, route. Then it's a simple SQl query just before every route request ("SELECT * FROM cache WHERE fromSystemID = '" . $fromSystemID . "' AND toSystemID = '" . $tosystemID)

Something like that (untested but you get the idea), if nothing is returned then you haven't calculated this route before so calculate it. Then you are


I precalculated it because I has a start system and many many end systems, and I wanted the shortest path to all. However, I also wanted to be able to sort by number of jumps... To be able to sort at the database level, the jump data needs to be there. To calculate it on the fly for many different systems takes too long (one system is fine, under a second. 20 systems takes many seconds), so I had to precalc everything.


Depends on the distance between systems i guess, finding 20 routes (randomly picked systems) ranging in 20-30 jumps each takes much less than a second for me :)

Also here's a tip-bit of an old implementation of A* for finding the fastest route between 8 way points. If way points are listed A,B,C,D its not just finding the route between A - > B then B - > C etc; its actually finding the fastest possible order + route. You can also set the start location and /or the end one (So could be B > A > D > C:)

Quote:

string 'calculate permutations: 0.628005027771' (length=38)
string 'average calculate route: 2.6805557701349E-5' (length=43)
string 'total calculate route: 0.78074598312378' (length=39)

Total Execute time: 1.4088230133057
Shortest Distance: 72
Shortest Route (waypoints):
array
0 => int 30001198
1 => int 30003862
2 => int 30002187
3 => int 30002510
4 => int 30002659
5 => int 30004993
6 => int 30004970
7 => int 30000142

Num of possible routes: 40320
Total checks: 22937
Finding waypoint routes: 0
string 'DB Access Counter: 28' (length=21)
string 'DB Timer: 0.0004969664982387' (length=28)
string 'Cache Access Counter: 22909' (length=27)
string 'Cache timer; 6.4458459481715E-6' (length=31)
string 'GE-8JV' (length=6)
string 'V-3YG7' (length=6)
string 'B-3QPD' (length=6)
string 'U-QVWD' (length=6)
string '36N-HZ' (length=6)
string '9KOE-A' (length=6)
string 'WD-VTV' (length=6)
string 'SV5-8N' (length=6)
string 'HED-GP' (length=6)
string 'Keberz' (length=6)
string 'Lansez' (length=6)
string 'Bukah' (length=5)
string 'Agil' (length=4)
string 'Agil' (length=4)
string 'Hishai' (length=6)
string 'Geztic' (length=6)
string 'Osis' (length=4)
string 'Sehsasez' (length=8)
string 'Ervekam' (length=7)
string 'Masanuh' (length=7)
string 'Leva' (length=4)
string 'Kor-Azor Prime' (length=14)
string 'Amarr' (length=5)
string 'Amarr' (length=5)
string 'Sarum Prime' (length=11)
string 'Hama' (length=4)
string 'Bagodan' (length=7)
string 'Barira' (length=6)
string 'Yuhelia' (length=7)
string 'Hati' (length=4)
string 'Uadelah' (length=7)
string 'Esescama' (length=8)
string 'Odin' (length=4)
string 'Ohide' (length=5)
string 'Sasoutikh' (length=9)
string 'Gheth' (length=5)
string 'Mehatoor' (length=8)
string 'Eredan' (length=6)
string 'Lisudeh' (length=7)
string 'Lashesih' (length=8)
string 'Sasta' (length=5)
string 'Jark' (length=4)
string 'Odatrik' (length=7)
string 'Rens' (length=4)
string 'Rens' (length=4)
string 'Frarn' (length=5)
string 'Gyng' (length=4)
string 'Onga' (length=4)
string 'Pator' (length=5)
string 'Eystur' (length=6)
string 'Hek' (length=3)
string 'Uttindar' (length=8)
string 'Bei' (length=3)
string 'Colelie' (length=7)
string 'Deltole' (length=7)
string 'Aufay' (length=5)
string 'Balle' (length=5)
string 'Vylade' (length=6)
string 'Dodixie' (length=7)
string 'Dodixie' (length=7)
string 'Botane' (length=6)
string 'Erme' (length=4)
string 'Villore' (length=7)
string 'Villore' (length=7)
string 'Erme' (length=4)
string 'Du Annes' (length=8)
string 'Renyn' (length=5)
string 'Renyn' (length=5)
string 'Algogille' (length=9)
string 'Kassigainen' (length=11)
string 'Hatakani' (length=8)
string 'Sivala' (length=6)
string 'Uedama' (length=6)
string 'Haatomo' (length=7)
string 'Suroken' (length=7)
string 'Kusomonmon' (length=10)
string 'Urlen' (length=5)
string 'Perimeter' (length=9)
string 'Jita' (length=4)


In a pre calculated system, how would you search for routes that didn't go into a certain sec status ? Then what about the "only highsec", "only lowsec" etc, would you pre calc all of them as well and set a flag ?

Next generation of lottery tracker coming soon! http://evelotterytracker.com/

Please like my post if it has helped you :)
morrosis
Ministry of War
Amarr Empire
#19 - 2012-02-16 13:48:46 UTC  |  Edited by: morrosis
Still got a bit of work to do but in the mean time

^.^ My jump calc
Osku Rei
Pixel 6
#20 - 2012-02-16 14:00:21 UTC  |  Edited by: Osku Rei
morrosis wrote:
Still got a bit of work to do but in the mean time

^.^ My jump calc


As of the time of this post it doesn't work, I put in jita and amarr (or any other combination of systems) and it just says "loading..." and never returns a route. :(

Also tried with the system ids just in case and it threw an error.

*Edit*
Oh, it just returned a result for rens to amarr... it took a good few minutes though lol

Next generation of lottery tracker coming soon! http://evelotterytracker.com/

Please like my post if it has helped you :)
12Next page