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)