Originally by: Ambo

---

x,y,z distances are pretty useless when working out number of jumps because some jumps are waaaay longer than others.

Personally I didn't use an A* algorithm but I'd think H should be the number of inter-region jumps and, if you're already in the right region, then the number of inter-constellation jumps. If you're in the right constellation then a complete search will take virtually no time at all.

---

Originally by: Ambo

---

I'm not sure if it has a name or not... I used a recursive procedure that stars from the destination and works backwards.

First I do regions, I then use that list of potential regions in the route to get the route through constellations, finally, I do the same for systems.

I suppose it's essentially a restricted bredth-first search with a lot of cacheing to speed things up, prevent back-tracking, etc. Frankly, I think it's over complicated and a little slow... I really should re write it as an A* algorithm.

---

h(a, b)
{
 if (a == b)
 {
 return 0; // if input is SolarSystemID
 return 1; // if input is ConstellationID or RegionID
 }
 else if (b < a)
 {
 return h(b, a);
 }
 else
 {
 return lookup[a][b];
 }
}

Originally by: Jethro Jechonias

---

Edited by: Jethro Jechonias on 05/11/2008 22:24:42

You could try using a lookup table has a heuristic guide.

Given that distances are symmetrical, you could halve the size of your lookup table by ordering the query elements.

For example:

h(a, b)
{
 if (a == b)
 {
 return 0; // if input is SolarSystemID
 return 1; // if input is ConstellationID or RegionID
 }
 else if (b < a)
 {
 return h(b, a);
 }
 else
 {
 return lookup[a][b];
 }
}

The size of the jagged array (lookup[][] in the pseudo-code above) would depend on what level of detail you use with the array.

If you limit it to just regions, the array would contain 2,016 elements. Using constellations it would contain 281,625 elements. If you go right down to the solar system level, you would need 13,522,600 elements.

Given that the maximum distance between any two systems is 99 jumps, you could use a single byte as the array element. Thus the size of array needed for a region / constellation / solar system lookup table would be 2KB / 276KB / 13MB.

The lookup table could be loaded from the same source as your jump table. Either a file or database. Given that you would be hard pressed to get the Jumps table down to less than 58KB, the regional lookup table is probably quite reasonable for any application and even the constellation lookup table doesn't look too bad.

---

Originally by: Jethro Jechonias

---

What language are you developing in?

Your question has got me think that A* might be a huge improvement over my current methods, so I am starting to build something that works along those lines in C#.

The table is not too hard to put together in SQL. The catch is that the SQL version is much larger than the memory structure that you can use in C#, and that is why I am working on putting one together.

---

Originally by: Alvaliella

---

I dunno how you could get over the memory limitation in C#... if you're using the A* algorithm then maybe you could use SQL to split up all of the jump information into separate tables for each region/constellation and only pull in the data for the region/constellation that you're currently in.

---

Originally by: Alvaliella

---

Does anyone know how CCP make the AutoPilot work?

---

Originally by: Jethro Jechonias

---

Originally by: Alvaliella

---

Does anyone know how CCP make the AutoPilot work?

---

CCP's implementation of the autopilot is very ineffiencient. I wouldn't recommend using that as a guide on how to build an autopilot.

---

Originally by: Kazuo Ishiguro

---

Originally by: Jethro Jechonias

---

Originally by: Alvaliella

---

Does anyone know how CCP make the AutoPilot work?

---

CCP's implementation of the autopilot is very ineffiencient. I wouldn't recommend using that as a guide on how to build an autopilot.

---

It does a good job at finding the quickest route between any 2 systems. It'd be better if it settled for a compromise with longer routes rather than trying to find an optimal solution.

---

Originally by: Kazuo Ishiguro

---

Are the locations of stargates within systems available as part of the data dump? If so, someone could come up with a route planner that minimises time in warp as well as jumps...

---

Originally by: Kazuo Ishiguro

---

Are the locations of stargates within systems available as part of the data dump? If so, someone could come up with a route planner that minimises time in warp as well as jumps...

---

Originally by: Kazuo Ishiguro

---

I've done a fair bit of research on how much distance ships cover during warp - you accelerate exponentially for 10 seconds and slow down exponentially for 20 seconds. Thus a lower bound for each jump is 30 seconds (this is also enforced by the session change timer).

During this time, excluding any additional ground covered while at full warp, you typically cover a distance equivalent to travelling at full warp speed for 1.33 seconds.

Also, it's worth finding your average grid load time (leave the log window open while on autopilot for 10-20 jumps and all the relevant data will end up in a single text file).

---

Originally by: Alvaliella

---

Edited by: Alvaliella on 23/11/2008 16:57:45
Thanks for all the replies & discussion- some points raised pre-emptively answer a few other questions that I was wondering about

I just wanted to give some "closure" to my original question in case anyone has similar concerns in the future.

After much research & musing I gave Dijkstra a try using the method described here.

When I first implemented this in Excel VBA, it took around 6.5 seconds to solve for a node (i.e. work out the shortest paths from the starting node to all other nodes in the system).

After code tweaking, pruning of the Eve data (e.g. removal of systems below a security threshold etc.) and optimising/preprocessing the remaining data, I got the solution time down to ~1.5 seconds for starting node to all others, and ~0.5 seconds for starting node to a particular destination node.

I'm pretty happy with this solution time and I don't think that A* would offer any major time savings (for this particular application)... I also like the fact that Dijkstra guarantees the shortest route so I know that my routes will match those of the autopilot.

My conclusion: Use Dijkstra over A*

---

 1st run 2nd run
My algorithm 4.5 3.7
Dijkstra 5.9 2.6
A* (constellation jumps) 40.5 38.6
A* (actual distance) 4.2 3.3
Best first (constellation jumps) 2.5 1.1 
Best first (actual distance) 3.0 2.1 (Result was a 104 jump route!)

 1st run 2nd run
My algorithm 1.4 0.4
Dijkstra 2.1 0.6
A* (constellation jumps) 3.5 1.1
A* (actual distance) 1.5 0.5
Best first (constellation jumps) 1.7 0.6
Best first (actual distance) 1.2 0.2 (Result was a 7 jump route)

Originally by: Ambo

---

The times are in seconds.

System is a P4 2.8 with 1 gig RAM running Windows XP.

---

private static List<int> GetSystemRouteDijkstra(int startSystemID, int endSystemID,
 List<int> constellations)
{
 Dictionary<int, int> indexToId = new Dictionary<int, int>();
 Dictionary<int, int> idToIndex = new Dictionary<int, int>();
 int nextFreeIndex = 0;
 short[] distance = new short[10000];
 int[] previous = new int[10000];
 bool[] vistited = new bool[10000];

 indexToId.Add(0, startSystemID);
 idToIndex.Add(startSystemID, 0);
 nextFreeIndex = 1;
 bool complete = false;

 distance[0] = 0;
 for (int i = 1; i < 10000; i++)
 {
 distance[i] = short.MaxValue;
 previous[i] = int.MaxValue;
 vistited[i] = false;
 }

 if (startSystemID == endSystemID) { complete = true; }

 int iterations = 0;
 while (!complete)
 {
 iterations++;
 //int minIndex = 0;
 short minDistance = short.MaxValue;
 for (int i = 1; i < 10000; i++)
 {
 if (distance[i] < minDistance && !vistited[i]) { minDistance = distance[i]; minIndex = i; }
 if (distance[i] == short.MaxValue) { i = 10000; }
 }

 vistited[minIndex] = true;
 foreach (int system in GetNeighbourSystems(indexToId[minIndex]))
 {
 if (SolarSystems.InConstellation(system, constellations))
 {
 if (!idToIndex.ContainsKey(system))
 {
 idToIndex.Add(system, nextFreeIndex);
 indexToId.Add(nextFreeIndex, system);
 nextFreeIndex++;
 }
 short possible = (short)(distance[minIndex] + 1);
 if (possible < distance[idToIndex[system]])
 {
 distance[idToIndex[system]] = possible;
 previous[idToIndex[system]] = minIndex;
 }
 // This optimisation can only be made because the distance between each node is 
 // always 1
 if (system == endSystemID) { complete = true; }
 }
 }
 }

 List<int> route = new List<int>();
 int systemId = endSystemID;
 route.Add(systemId);
 while (systemId != startSystemID)
 {
 int prevId = indexToId[previous[idToIndex[systemId]]];
 route.Add(prevId);
 systemId = prevId;
 }

 route.Reverse();
 return route;
}

Originally by: Ambo

---

The performance bottlenecks are GetNeighbourSystems and, to a lesser extent, InConstellation. The vast majority of the execution time (around 96%+) is taken up by calls to the database. I cache data as much as possible but many calls simply must be made and several hundred of them are always going to take a reasonable length of time.

---

Originally by: Ki Tarra

---

Originally by: Ambo

---

The performance bottlenecks are GetNeighbourSystems and, to a lesser extent, InConstellation. The vast majority of the execution time (around 96%+) is taken up by calls to the database. I cache data as much as possible but many calls simply must be made and several hundred of them are always going to take a reasonable length of time.

---

Have you thought about making just one call to the database to get the jump table and storing it in a jagged array?

While it might be an expensive intial operation, it would likely save you a lot of long latency database operations later on.

If you structure the array properly, you could also avoid the frequent calls to a Dictionary object as those also carry a higher overhead than a basic array.

I'll see about drafting up some code to show you what I mean.

---

Originally by: WolfSinger SilverShadow

---

I wrote soemthing like this in PHP about a month back using a varriant of Dijkstra's algorithm. A* works great if you can estimate distances between nodes in some way - you realy can't do this in EVE easily because of the way jump gates are laid out.

With mine, I was able to adjust "movement costs" so that it would try to avoind lowsec and 0.0 if you want. I never really got around to optimizing it, so each tiem you refresh the page, its gawd-awful slow as it reloads the the compelte universe system and node list from the static-dump DB. I also never beutified the outputm so it currently just dumps the best path array to the screen, displaying system numbers. Since I don't even look at contellations or regions, it should automaticly find a best path, even if it leads outside the region.

http://www.wolfsinger.com/~wolfsinger/eve/paths.php

---

Originally by: Amida Ta

---

I think you are doing wrong something ;)

I am using a simple breadth-first search and even for the longest paths my application does not need longer than 0.02 seconds to calculate them.
On the other hand I'm using my EveAI data structures and no Database.

---

Originally by: Alvaliella

---

Edited by: Alvaliella on 26/11/2008 22:37:23

Originally by: Amida Ta

---

I think you are doing wrong something ;)

I am using a simple breadth-first search and even for the longest paths my application does not need longer than 0.02 seconds to calculate them.
On the other hand I'm using my EveAI data structures and no Database.

---

Any chance you could elaborate please? Granted I'm not a proper programmer but I simply can't think of how this is possible- I mean surely you have to crunch through masses of route data at some point?


Edit: Just had a thought- if you can add up the "jumps per hour" statistic over a few days for each system then that might be good to use as an A* heuristic? You'd chose whichever system had the highest number of jumps per hour (indicating that it's on a well travelled highway) rather than physical distance... it should eventually filter you onto the most commly used AutoPilot routes

---

public List<SolarSystem> FindRoute (SolarSystem start, SolarSystem end)
{
Queue<SolarSystem> openRoute = new Queue<SolarSystem> ();

start.Tag = start;
openRoute.Enqueue (start);

while (openRoute.Count > 0)
{
SolarSystem current = openRoute.Dequeue ();
if (current == end)
{
List<SolarSystem> way = new List<SolarSystem> ();
while (current != start)
{
way.Add (current);
current = (SolarSystem)current.Tag;
}
way.Add (start);
way.Reverse ();
return way;
}

foreach (SolarSystem system in current.Jumps)
{
if (system.Tag != null)
continue;
system.Tag = current;
openRoute.Enqueue (system);
}
}
return null;
}

Originally by: Alvaliella

---

Any chance you could elaborate please? Granted I'm not a proper programmer but I simply can't think of how this is possible- I mean surely you have to crunch through masses of route data at some point?

---

Originally by: Amida Ta

---

magic code

---

Originally by: Ki Tarra

---

First draft can load all of the data it needs form the database in ~0.13 second, and can calculate a 50 jump route in ~0.07 seconds.

---

Originally by: Amida Ta

---

Btw: The route (9S-GPT in Outer Passage to XG-D1L in Cloud Ring) with 50 Jumps takes 0.0156250 sec to calculate using the method above on my Athlon 3500+ (2,2GHz).

---

Originally by: Ki Tarra

---

Originally by: Alvaliella

---

Any chance you could elaborate please? Granted I'm not a proper programmer but I simply can't think of how this is possible- I mean surely you have to crunch through masses of route data at some point?

---

There really isn't that much crunching, atleast not for a computer.

I am working on building my own C# route generator.

First draft can load all of the data it needs form the database in ~0.13 second, and can calculate a 50 jump route in ~0.07 seconds.

I figure that I still have plenty of room to optimize that further as my current code still needlessly copies arrays in a few places.



As for possible heuristics for A*, don't forget the vital detail that the heuristic must never overestimate the distance to the destination. If the heuristic can over estimate its distances, then it may fail to find the proper route.

---

Originally by: Ambo

---

Indeed, if I pre-load all the data I'll need then any of the methods I use will be blazingly fast.

However, loading everything into datatables when the app starts takes up too much memory and loading it all before calculating a route is too slow.

I think that my problem might be my use of the VS generated data access stuff. I'll try writing some stripped down access routines with more basic data structures and see where that gets me.

---