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.
 

[PHP] Fast jumps from-to-system calculation?
Author
Previous Topic Next Topic
Gaius Henry
The Scope
Gallente Federation
#1 - 2013-07-13 00:29:00 UTC  |  Edited by: Gaius Henry
I'm using a converted MySQL eve toolkit dump (from MSSQL) to explore the game's data. I'd like to create a light algorithm to calculate the jumps needed from the solar system A to the solar system B. I'm actually using PHP for fast prototyping (but if it works, it could be set as part of an API).

My problem actually is that the algorithm I've made is heavy (using a recursive graph-like system to "walk" all the possible ways down to the target system).

I'm actually ignoring minimum and maximum security choices, but it'd be very easy to include in the SQL query. I've tried to calculate a ~20 jumps path and it took around 2 seconds on a power computer (CPU i7-2600k overclocked). As I'd like to serve it on mobile phones, I'd like to reduce the load, if possible, without having enormous system-to-system pre-loaded data.

Any hint on how to make it lighter? I wish the algorithm was as fast as the game's!

Link to the PHP class on HASTEBIN

Thanks :)
Steve Ronuken
Fuzzwork Enterprises
Vote Steve Ronuken for CSM
#2 - 2013-07-13 00:38:28 UTC  |  Edited by: Steve Ronuken
It's not the world's most efficient code, but for an A to B route, it'll do it in less than a second.

https://github.com/fuzzysteve/Eve-Route-Plan

This version depends on a pregenerated table of jumps out of systems, but you could eliminate that requirement /fairly/ easily. It would slow down the set up a little, but I suspect it wouldn't be too severe. just plug the table generation sql's select statement into the code directly, with any filtering that you want to put on it.


It generated a whole eve route map in about 3 days. But that's 25 million routes for you (actually 12.5 million. As the route back can be the same as the one forward)

That's around 5GB of data (including the routes themselves, which I suspect I won't bother storing the next time I build it)

Woo! CSM XI!

Fuzzwork Enterprises

Twitter: @fuzzysteve on Twitter
Gaius Henry
The Scope
Gallente Federation
#3 - 2013-07-13 00:51:43 UTC  |  Edited by: Gaius Henry
Well, TBH from a fast view of your code... seriously, why do you use single-character labels for variables? It makes it very hard to read (by who don't know the logics behind it).

May you please tell me in few words what is your logic flow? It's a little bit... cryptic. Thanks.
Gaius Henry
The Scope
Gallente Federation
#4 - 2013-07-13 10:42:44 UTC
I've tried a different approach, still it will take an exponential time to calculate far systems (is there even a linear graph search?).

The different approach doesn't compare all the results, but tries the less jumps possible looking for the simpliest solution, then returns the first one. Also, this class implements the security preferences (obviously the wider the preferences are, the more systems it will analyse).

Still... have you tried planning a 30+ jumps route with your system?

Version 2 (Depth-Limited Search)
Steve Ronuken
Fuzzwork Enterprises
Vote Steve Ronuken for CSM
#5 - 2013-07-13 12:38:55 UTC  |  Edited by: Steve Ronuken
If I remember correctly, it's an A* search. https://en.wikipedia.org/wiki/A*_search_algorithm

Just generated a route between 30045334 and 30001306
0.07008 seconds. And that's using a full jump list, which isn't the world's best idea, as it also included jove space, which increases the data set a little.

The route is:
30002760,30002759,30002756,30002757,30002758,30001388,30001356,30001361,30001383,30001385,30001445,30001447,30000848,30000846,30000861,30000863,30000864,30000865,30000867,30000871,30000894,30000895,30000896,30001348,30001344,30001322,30001315,30001305,30001306

As for why the code is labelled like that, as it says in the Readme, it's not actually mine. It's just hosting code so it remains available.

Original source, also in the readme, is http://web.archive.org/web/20070316001615/http://www.asenski.com/archives/7

Woo! CSM XI!

Fuzzwork Enterprises

Twitter: @fuzzysteve on Twitter
Gaius Henry
The Scope
Gallente Federation
#6 - 2013-07-13 12:47:21 UTC
Thanks for the reply. I'm slowly understanding the code (even if these algorithms are brain-breakers :P - I've seen the BFS algorithm too, and that's similar to the code you're hosting.

I've found probabily the cause of the slowliness of my system: it always re-calculates the before-depth routes, that consumes lots of time. I'm gonna R&D more to find a solution I understand 100% :)