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.

---