Dijkstra/A* Searching

EVE Technology and Research Center Third Party Developers
1

Hey everyone! I’m working on creating a mobile app targeted for Wormhole Pilots.

Many of us have encountered the issue where we get a K-Space connection, and we have a cargo full of blue loot only to see that the nearest station with buy orders is 15 jumps away when in reality it’s only 2 (damn regional borders).

Anyways. I have been working on implementing Dijkstra/A* searching. I have gotten it to work, and I’m able to get routes that are 99% accurate most of the time. The problem I’m encountering now is performance. Some routes are taking upwards of ten seconds to generate. As of right now I’m using a Heuristic of 0, which essentially makes this a Dijkstra Algorithm. I’ve read through the old forums and some users have expressed success in implementing A* and/or getting results very quickly. I’m curious what it was they did to achieve such results!

I’m pretty much stuck on performance now; The program is searching all K-Space stations which offer buy orders of blue loot. My intermittent solution is to have the list dynamically update as it calculates routes. Which is currently working quite nicely.

Any help/guidance/insight would be greatly appreciated!

3 Likes
2

What language are you using?

3

I’m building the app with C#

4

Ah, can’t help you then. Well, actually - there’s no reason to use A* or Dijkstra, since all weights are 1. Use simple BFS. Evernus uses this to get paths between systems and it’s lightning fast.

5

Thank you! I’ll look into this!

6

I’m not seeing a huge improvement between previous implementations and BFS approach.

I modified my Priority Queue such that it’d operate in a Queue fashion instead of a Heap. I’m still getting 10+ seconds for some routes.

Tsuguwa <-> Zemalu

is one such example of a ‘slow’ route which took ~10 seconds to identify. Perhaps my approach is incorrect?

Pseudocode:

While (queue is not empty)
{
    Grab first item in queue (First in First out)

    If the system is the goal, trace back route.

    Grab a list of systems which have an origin of the current system.

    iterate through list of systems.
        if system exists in queue, move to the next system.
        if system doesn't exist, check to see if exist in visitedSystems
        if system doesn't exist, add it to the Queue and visitedSystems
}
7

Is worth mentioning there is an ESI endpoint for this:

https://esi.tech.ccp.is/latest/#!/Routes/get_route_origin_destination

Probably better to use the SDE export files to calculate it as you are, especially on mobile, to reduce number of HTTP requests (data usage).

8

I was originally using the ESI Endpoint, it was slow though, and I didn’t want to make CCP mad by hitting their endpoint 200+ times to calculate all of the routes.

I’m happy with it as it is, I just wish it were faster! Most of the routes take less than a second to calculate, but it adds up!

I’ll figure it out; this is more of a fun side project that a corpmate had mentioned as a ‘nice to have’ so far he’s happy with it!

9

You could start saving/caching the routes. So if they are done again they would be just as long as it takes to fetch it from cache. Or so that the more common ones are already calculated.

10

If you do caching, which you should, you can use ESI. 10s is suspiciously very long time. In C++ I get results in a fraction of a second.

11

I have just written a version in Perl, and it is blindingly fast. Less than 0.1 sec (running on a 2.5Ghz Pentium 4 processor) to calculate the shortest path between LX5K-W and M-VACR. About the same for your path between Tsuguwa and Zemalu. Admittedly I have not tried all possible paths, and I do not necessarily have all the tests that you might have (I was just looking at pure shortest path, not testing for system security level etc), but 10 seconds for one path would seem to be so far out of the ballpark that something must be amiss.

If your queue is implemented as an array, how sure are you that the language you are writing in isn’t shuffling all the values in the array when you “grab the first item”? Adding an O(N) operation like that to every step could easily cause a massive blow out in the time - specially on long paths.

My implementation does not rely on removing any elements from any arrays. Shuffling all the elements in an array on each loop iteration can be a real performance killer.
Instead, I either add elements to an array, or throw away the entire array (i.e. instead of “grab the first item”, I would step through each value of the array until I reach the end). Now if I just continually add to the end and never free up at the beginning my array would grow too big. What I do is, instead of adding new values to the end, I have a two arrays, always add to the second array and I have an extra outer loop that allows me to swap the arrays over.

Your pseudo code looks like this:

while (queue is not empty)
{
       remove first element
       for each jump from the current system
       {
               do some stuff
               exit if you have a solution
               maybe add a bunch of new elements to the queue
        }
}

Mine looks like this.

main_queue = create new array ( starting_location );
second_queue = create new array();
while main_queue is not empty
{
        for each element in main_queue
        {
                for each jump from current system
                {
                        do some stuff
                        exit if we have a solution
                        maybe add some new elements to second_queue
                }
        }
        main_queue = second_queue
        second_queue = create new array()
}

it might look like I’ve got three levels of loops compared to your two, but the outer loop is not actually doing anything, it’s just there to allow me to periodically get rid of the main_queue when I’ve processed all the values in it.
Another important thing, is my queue variables are actually references to arrays, so when I say “main_queue = second_queue” I’m not copying any data, just switching pointers.

12

I just noticed this:

I think this is significant.
Why do you need a priority queue? BFS (implemented non-recursively) does not need any sort of priority or any function calls, just an ordinary queue… and the trick I showed earlier using arrays means you eliminate any “shuffling” associated with a conventional array. The thing is, if you are using a heap, you are making a function call on each loop iteration to do the adding or removing. That typically involves pushing a whole bunch of stuff on the call stack, jumping to the library routine for the add/remove operation on the heap, and then popping the results of the operation back off the call stack. By comparison indexing into an array to store or access an element is “heaps” faster (sorry for the pun :slight_smile: )

If you are going for performance, I would recommend implementing the whole shortest-path routine all in one subroutine, with no library calls. BFS is not that complicated, and shouldn’t be more than a couple of pages.
I would strongly recommend using an array for the queue (using a heap without function calls would be a nightmare), and like I showed earlier, avoid shuffling all the values in the array each time you dequeue from it.

Similarly I’d check that all large data structures (like where you store which systems have jump-gates to which other systems etc) are either accessed via global variables or passed into the subroutine by reference, and the return results again, should be passed by reference if they are, or could be, of any decent size.

But there is one other thing I want to make sure of, is that you aren’t doing something like the following:

path_to_closest_station = undefined
for each station that buys blue loot
{
        path = find_shortest_path(current_location, station)
        if ((path_to_closest_station is undefined) or (length(path) < length(path_to_closest_station))
        {
                path_to_closest_station = path
        }
}
return path_to_closest_station

The point is you should be looking for multiple destinations at the same time.

any_blue_loot_station = ( station1, station2, station3 ... )
path_to_closest_station = find_shortest_path(current_location, any_blue_loot_station);

The reason I mention it is because when you gave your example of computing “Tsuguwa ↔ Zemalu” it made it sound like you are just computing point-to-point paths, when I think you should be computing Tsuguwa → nearest blue loot station.

Hopefully some of this is relevant, and I’m not just trying to explain things that you are already doing :slight_smile:

13

I originally was implementing the A* Algorithm, which is why I was using a Priority Queue, I then changed the Heuristic to always return 0 (Which then essentially turned it into a Dijkstra search (Which is what CCP uses for system pathing).

Currently what I’m doing is iterating through a list of blue loot stations and calculating the route from there. I then take the result and add it to a List which is sorted. The entire processing is done asynchronously :slight_smile:

You do make a good point though. I’ll have it just calculate the list and if it finds a match it’ll bubble that up.

Thank you for the ideas! I have much to work on now :smiley:

– Edit: I’m also displaying --all-- systems. Which permit the user the ability to select which system they want to fly to (Tapping on a system sets the in-game waypoint)

14

Don’t know if this will help you but I have worked on my own c# desktop app that includes a fairly decent path calculator. Takes about 20-40 ms to find a path. I just posted it to github you can check it out if you want.


Just look at the PathTest function in EVEAllMain for an example.
The loading is slow for a mobile app but if you have a pre-parsed data set of just the jumps you should be able to do it the same way.

BTW. It does sometimes generate slightly longer than necessary paths when doing high sec only routes, not sure on low sec routes. haven’t done that much testing.

15

Cwittofur Cesaille

If you get this working well one day you should think about integrating it with eve market. Would be awesome to be able to find the cheapest modules by distance.

1 Like
16

Thanks for the pointer! Looks like you’re doing a lot of your calculations differently than mine :slight_smile:

I got it working! Well more or less. The calculations get slower and slower the further away from the origination it is. With that being said, it grabs stuff pretty damn fast right now. I’m able to populate 98% of the list within a second.

I do have the app under alpha test on the Google Play store. I’m working on getting it published to the iOS App Store as well, but… Apple is not easy lol. Hopefully I’ll get it finalized this week. Need to make some rough images to satisfy the app requirements.

17

Fixed the longer routes problem. When doing high sec only routes I was checking security status >= 0.5 but since the server rounds up from 0.45 some systems that are technically high sec were being skipped.

It should work fine now. Just replace the generateDestinations() function with something else that fills the Dictionary systemDestinations (the key is a solarSystemID and the value is a list of system IDs that can be jumped to from that system.) This only needs to be done once!

Then remove or replace the part of getDistanceMap() function that checks the system security. (where the comment says //We want to stay safe!) The generated distance map could then be used to plot multiple routes from the same starting system.

The rest of the code should then work just fine in any other program.

18

I can’t recall what the exact method is called, but there is a type of tree/graph search that uses halves, and a pre-assigned table of distances to quickly narrow this stuff down, it’s often absurdly fast, if you can find that, it may be a good method.

19

Gonna necro this thread!

As I am sure the OP has moved on to other work, I am making the following points on performance for future readers who are looking at pathfinding in Eve.

If you’re always planning on doing pathfinding under similar rules (e.g. shortest-route, or shortest-hisec-route), you can precalculate all those paths in advance and then look them up instead of calculate them. This is easily done using the Floyd-Warshall algorithm, which generates a data structure that can let you find any path (in Eve-sized graphs) in just microseconds:

Class Path(System startSystem, System destinationSystem)
{
  int HopsToDestination;
  System NextHop;
}

Dictionary<Tuple<System,System>,Path> ShortestPaths;
Dictionary<Tuple<System,System>,Path> HiSecOnlyPaths;

Floyd-Warshall will generate the above Dictionaries in seconds to minutes, and lookups take microseconds. Store the results in a database or in-memory structure. Note that this approach won’t work if you need dynamic pathfinding rules (like user-definable avoidance lists!).

If pregenerating routes doesn’t work for you, then you might want to look at some very old threads on the forums that describe a 2-step approach to pathfinding that focuses first on inter-region paths followed by intra-region paths. This sounds promising, but a bit complex to implement.