open All Channels
seplocked EVE Technology Lab
blankseplocked Jumps between two systems
 
This thread is older than 90 days and has been locked due to inactivity.


 
Author Topic

Nomad Quento
Minmatar
Posted - 2011.07.14 22:15:00 - [1]
 

Edited by: Nomad Quento on 14/07/2011 22:16:00
Can anyone tell me how to calculate number of jumps between two systems - the shortest route?

Thanks,

// Nomad Quento

Quarantan
Caldari
Burning Napalm
Northern Coalition.
Posted - 2011.07.15 05:46:00 - [2]
 

Edited by: Quarantan on 15/07/2011 05:46:36
Originally by: Nomad Quento
Edited by: Nomad Quento on 14/07/2011 22:16:00
Can anyone tell me how to calculate number of jumps between two systems - the shortest route?

Thanks,

// Nomad Quento


im sure Dijkstra can help you with that :) hf!

Nomad Quento
Minmatar
Posted - 2011.07.15 18:04:00 - [3]
 

Originally by: Quarantan
im sure Dijkstra can help you with that :) hf!
And I am sure this cannot help me in any way ;-)

Isn't there any way, perhaps an API somewhere, where it is possible to calculate shortests jumps between two systems? I am going to use it in my market webpage, http://eve-profit.com/ where I hope to check if market orders are in conflict with my orders (with data from EVE-Central).

// Nomad Quento

Mintoko
Gallente
Taedium In Perpetuam
Posted - 2011.07.15 19:03:00 - [4]
 

Edited by: Mintoko on 15/07/2011 19:07:22
Unfortunately, it's not a simple formula, but a process by which a path is mapped from one system through all of its gates and then the gates of each of those systems, until you reach your destination. It can be a labor-intensive process that has been known to cripple the eve client if there are too many waypoints or some critical systems that were set to be avoided.

Osku Rei
Posted - 2011.07.15 21:17:00 - [5]
 

Mail sent

Trenker
Posted - 2011.07.15 21:23:00 - [6]
 

I use a very simple algorithm, posted it on my blog

Uses PHP but can easily be ported to any other language.

Osku Rei
Posted - 2011.07.15 21:37:00 - [7]
 

Originally by: Trenker
I use a very simple algorithm, posted it on my blog

Uses PHP but can easily be ported to any other language.


Surely that's a long winded approach? / not optimized? I did it in about 20 lines or so. How long does it take to do, say, 30-40 jumps ?

I assume $jumps is your collection of edges ?.. its somewhat hard to follow.

Sable Blitzmann
Minmatar
Massively Dynamic
Posted - 2011.07.16 18:05:00 - [8]
 

Long story short: look into pathfinding algorithms. Like previously said, it is not a simple concept to grasp. A modified A* algorithm would work...

I used to have a link to a PHP function that did this, I'll have to get back to you on that.

However, to be fast, I would recommend that you build a huge database table with the info:
fromSystem toSystem jumps

This would only account for shortest jumps and would not take into consideration sec status or avoided systems. However, it is much quicker to lookup than doing a pathfinding algorithm, especially if you need to find the path for many systems on 1 page. Also note that if you go this route, expect to have a huge database table. We're talking about millions and millions of rows and about 1 GiB of data because of all the possible system connections.

Come to think of it, there was a PHP class that used a custom binary file as a database that contained this info. Extremely quick lookups without database overhead. However, if you want to incorporate jump data into the database query (to, say, sort by jumps) you would have to use the database table method. I'll try to get you some links tho later today. =)

Osku Rei
Posted - 2011.07.16 19:11:00 - [9]
 

I implemented a PHP solution to solve this (took 2 hours) about a month ago when I was messing around with TSP / AI. I'm in the process of attaching an API ontop of it; which, after a talk with Nomad Quento he is going to use. I hope to release this to the public soonish.

The API can find a route of 30 jumps in about 0.2-0.4 seconds so its nice and fast, with little overhead :)

It uses the mapSolarSystemJumps static data dump.

A cache'ing feature will be added, which is what I think Sable Blitzmann is talking about.

Nomad Quento
Minmatar
Posted - 2011.07.16 22:42:00 - [10]
 

Originally by: Sable Blitzmann
Come to think of it, there was a PHP class that used a custom binary file as a database that contained this info. Extremely quick lookups without database overhead. However, if you want to incorporate jump data into the database query (to, say, sort by jumps) you would have to use the database table method. I'll try to get you some links tho later today. =)
Though I will take a closer look at Oskus API, then my goal is to host this service myself as I then am not depending on anyone elses server running and it should go faster when not querying over the internet.

So if you can find anything that can help me doing this then I would appreciate it.

Note that I need this for my market webpage, http://eve-profit.com/ where I am considering getting EVE-Central data and check if my orders are uptodate so I need to see the jumps as the market does - shortest route and only in the same region.

// Nomad Quento

Ultran
Posted - 2011.07.17 00:33:00 - [11]
 

This gets complicated. I launched a fleet of Amazon EC2 instances to predetermine the distance from every system to every system in the galaxy then transfer the data for use in a map at www.evedot.com/map (I think it took about a day or so for 20 machines to crunch this, many failures before that). Without getting into too much detail, I recommend checking out Dijkstra's algorithm:
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Maybe I should release an API to look up jump distances? That could save a lot of people time and pain.

Ultran
Posted - 2011.07.17 00:38:00 - [12]
 

It looks like my jump database is 13.6 GB! (number of jumps plus jump paths) Confused

In the future it could probably be cut down with some optimizations in redundancy, but just trying to give an idea on the complexity and scope of your endeavor.

Zeta Zhul
Caldari
Preemptive Paranoia
Posted - 2011.07.17 03:04:00 - [13]
 

Or you can use a hierarchical query.

EvEToolbox
Posted - 2011.07.17 04:19:00 - [14]
 

you guys are making it sound way to complicated, its not!

Mintoko
Gallente
Taedium In Perpetuam
Posted - 2011.07.17 06:24:00 - [15]
 

Originally by: EvEToolbox
you guys are making it sound way to complicated, its not!


So, enlighten us. How simple is it?

Trenker
Posted - 2011.07.17 19:57:00 - [16]
 

Osku Rei - As I said in the blog post: I don't have a degree in computer science (so I'm not even sure what edges and nodes are), this was my very first contact with graph theory. So yes, it's not optimized in any way. Quite the contrary, it's more like a brute force attack. Yet, loading the jumps takes longer than the calculation itself. To get all distances from any system in EVE to every system where an agent is located (for the agent finder), takes 20 - 40 seconds (including some overhead). And that are 1700 routes to find.

I would be very interested though in implementations of optimal algorithms like Dijkstra or A*. Especially since you could add all the autopilot features of EVE. Someone like to share?

Osku Rei
Posted - 2011.07.17 20:28:00 - [17]
 

Originally by: Mintoko
Originally by: EvEToolbox
you guys are making it sound way to complicated, its not!


So, enlighten us. How simple is it?


I'm EVEtoolbox btw.

http://demo.evejb.com

Whole thing took about 2 hours when I was bored one night.

Uses D*.

Gets all the system jumps from the static mapSolarSystemJumps MySQl database then runs the algo.

Returns a 75 jump route in < 0.5 seconds.

Lowkey Asgaurd
Minmatar
Fluffy Carebears
Posted - 2011.07.18 13:52:00 - [18]
 

Are we allowed to post code on this forums ?

If so I've got a sql stored procedured I am prepared to share.
The stored proc runs off mapSolarSystems and mapSolarSystemJumps.

Osku Rei
Posted - 2011.07.18 15:07:00 - [19]
 

Originally by: Lowkey Asgaurd
Are we allowed to post code on this forums ?

If so I've got a sql stored procedured I am prepared to share.
The stored proc runs off mapSolarSystems and mapSolarSystemJumps.


People post code all the time, people welcome it :)

Sable Blitzmann
Minmatar
Massively Dynamic
Posted - 2011.07.18 17:23:00 - [20]
 

Originally by: Osku Rei
I implemented a PHP solution to solve this (took 2 hours) about a month ago when I was messing around with TSP / AI. I'm in the process of attaching an API ontop of it; which, after a talk with Nomad Quento he is going to use. I hope to release this to the public soonish.

The API can find a route of 30 jumps in about 0.2-0.4 seconds so its nice and fast, with little overhead :)

It uses the mapSolarSystemJumps static data dump.

A cache'ing feature will be added, which is what I think Sable Blitzmann is talking about.


Nice. There are many ways to do this, and many algorithms. It just takes a bit of reseqarch, especially if you've never studied this field before. Also, Oksu, any plans to release the source of your algorithm? ;)

If you ask me, the problem with doing on-the-fly calculations (rather than, say, a pre-calculated database table) is that they take quite a bit of time if you need to do many of them on 1 page. Take Osku's example of 30 jumps in 0.3 seconds (roughly) - if you have a page that is supposed to calculate the number of jumps of 30 market orders, that would be 30*.03 = 9 seconds. This will, of course, depends on the number of jumps. You also would not be able to sort by jumps on the database level.

The good thing about on-the-fly calculations is that you could add conditions to it (ie: stay in hi-sec, avoid certain system, etc) by simply not loading those systems into the equations. A pre-calculated jump table would not be able to do this (because it's pre-calculated lol).

My database table only includes the fromSystem, toSystem, and # of jumps and it's 850MB with 27,050,401 rows of data (did not include things like Jove space and whatnot). It's an nPr function, so it has some redundancy to it (system 1 -> system2 is also system2 -> system1). It can be trimmed down by an nCr function to about 13,522,600 rows.

There's lots of good info in this thread already - might be time to revise my knowledge of this topic. It truly is a fascinating subject.

Also, thos links that I promised you are on a different computer unfortunately. I should be able to get them to you soon tho. ;)

Osku Rei
Posted - 2011.07.18 19:02:00 - [21]
 

Originally by: Sable Blitzmann
Originally by: Osku Rei
I implemented a PHP solution to solve this (took 2 hours) about a month ago when I was messing around with TSP / AI. I'm in the process of attaching an API ontop of it; which, after a talk with Nomad Quento he is going to use. I hope to release this to the public soonish.

The API can find a route of 30 jumps in about 0.2-0.4 seconds so its nice and fast, with little overhead :)

It uses the mapSolarSystemJumps static data dump.

A cache'ing feature will be added, which is what I think Sable Blitzmann is talking about.


Nice. There are many ways to do this, and many algorithms. It just takes a bit of reseqarch, especially if you've never studied this field before. Also, Oksu, any plans to release the source of your algorithm? ;)





Have a (basic) API :) Returns results in a XML format
api.evejb.com/?from=Jita&to=Amarr

It also includes a Query time, which includes all the validation and checking + the finding of a route. So the actual route finder is faster :)
Its all dynamic, nothing is cached or stored in a big database table (which allows for avoiding systems, security status etc), it just used the mapSolarSystemJumps.

From what I can tell (which is kinda obvious) it takes longer to send the produced html page / render it to the user than to do any of the algo's / 'code'.

Heres and example returned XML:

Quote:
<?xml version="1.0" encoding="utf-8"?>
<routefinder>
<infomation>
<from>Jita</from>
<to>Amarr</to>
<jumps>9</jumps>
</infomation>
<route>
<jump>Jita</jump>
<jump>Perimeter</jump>
<jump>Urlen</jump>
<jump>Sirppala</jump>
<jump>Inaro</jump>
<jump>Kaaputenen</jump>
<jump>Niarja</jump>
<jump>Madirmilire</jump>
<jump>Ashab</jump>
<jump>Amarr</jump>
</route>
</routefinder>
Query took 0.0707290172577 seconds






Nomad Quento
Minmatar
Posted - 2011.07.18 21:19:00 - [22]
 

Originally by: Osku Rei
Have a (basic) API :) Returns results in a XML format
api.evejb.com/?from=Jita&to=Amarr

It also includes a Query time, which includes all the validation and checking + the finding of a route. So the actual route finder is faster :)
Its all dynamic, nothing is cached or stored in a big database table (which allows for avoiding systems, security status etc), it just used the mapSolarSystemJumps.

From what I can tell (which is kinda obvious) it takes longer to send the produced html page / render it to the user than to do any of the algo's / 'code'.

Heres and example returned XML:

Quote:
<?xml version="1.0" encoding="utf-8"?>
<routefinder>
<infomation>
<from>Jita</from>
<to>Amarr</to>
<jumps>9</jumps>
</infomation>
<route>
<jump>Jita</jump>
<jump>Perimeter</jump>
<jump>Urlen</jump>
<jump>Sirppala</jump>
<jump>Inaro</jump>
<jump>Kaaputenen</jump>
<jump>Niarja</jump>
<jump>Madirmilire</jump>
<jump>Ashab</jump>
<jump>Amarr</jump>
</route>
</routefinder>
Query took 0.0707290172577 seconds

Spice it up with all region and constallation names, EVE database IDs on it all, security status and an advanced option on "shortest route" or "safest route" and it is pure gold (and a documentation somewhere)! :-) But even what you got now is really good work and could be useful to many if other services are allowed to poll data from you.

Keep up the good work,

// Nomad Quento

Lowkey Asgaurd
Minmatar
Fluffy Carebears
Posted - 2011.07.19 07:07:00 - [23]
 

Please note this was written with help from a friend, I not a SQL specialist.

-- Runs Dijkstras algorithm from the specified node.
-- @StartNode: Id of node to start from.
-- @EndNode: Stop the search when the shortest path to this node is found.
-- Specify NULL find shortest path to all nodes.
CREATE PROCEDURE dbo.usp_Dijkstra (@StartNode int, @EndNode int = NULL)
AS
BEGIN
-- Automatically rollback the transaction if something goes wrong.
SET XACT_ABORT ON
BEGIN TRAN

-- Increase performance and do not intefere with the results.
SET NOCOUNT ON;

-- Create a temporary table for storing the estimates as the algorithm runs
CREATE TABLE #Nodes
(
Id int NOT NULL PRIMARY KEY, -- The Node Id
Estimate decimal(10,3) NOT NULL, -- What is the distance to this node, so far?
Predecessor int NULL, -- The node we came from to get to this node with this distance.
Done bit NOT NULL -- Are we done with this node yet (is the estimate the final distance)?
)

-- Fill the temporary table with initial data
INSERT INTO #Nodes (Id, Estimate, Predecessor, Done)
SELECT solarSystemID, 9999999.999, NULL, 0 FROM dbo.mapSolarSystems

-- Set the estimate for the node we start in to be 0.
UPDATE #Nodes SET Estimate = 0 WHERE Id = @StartNode
IF @@rowcount <> 1
BEGIN
DROP TABLE #Nodes
RAISERROR ('Could not set start node', 11, 1)
ROLLBACK TRAN
RETURN 1
END

DECLARE @FromNode int, @CurrentEstimate int

-- Run the algorithm until we decide that we are finished
WHILE 1 = 1
BEGIN
-- Reset the variable, so we can detect getting no records in the next step.
SELECT @FromNode = NULL

-- Select the Id and current estimate for a node not done, with the lowest estimate.
SELECT TOP 1 @FromNode = Id, @CurrentEstimate = Estimate
FROM #Nodes WHERE Done = 0 AND Estimate < 9999999.999
ORDER BY Estimate

-- Stop if we have no more unvisited, reachable nodes.
IF @FromNode IS NULL OR @FromNode = @EndNode BREAK

-- We are now done with this node.
UPDATE #Nodes SET Done = 1 WHERE Id = @FromNode

-- Update the estimates to all neighbour node of this one (all the nodes
-- there are edges to from this node). Only update the estimate if the new
-- proposal (to go via the current node) is better (lower).

UPDATE #Nodes
SET Estimate = @CurrentEstimate + 1, Predecessor = @FromNode
FROM #Nodes n INNER JOIN dbo.mapSolarSystemJumps e ON n.Id = e.toSolarSystemID
WHERE Done = 0 AND e.fromSolarSystemID = @FromNode AND (@CurrentEstimate + 1) < n.Estimate

END;

-- Select the results. We use a recursive common table expression to
-- get the full path from the start node to the current node.
WITH BacktraceCTE(Id, Name, Distance, Path, NamePath)
AS
(
-- Anchor/base member of the recursion, this selects the start node.
SELECT n.Id, node.solarSystemName, n.Estimate, CAST(n.Id AS varchar(8000)),
CAST(node.solarSystemName AS varchar(8000))
FROM #Nodes n JOIN dbo.mapSolarSystems node ON n.Id = node.solarSystemID
WHERE n.Id = @StartNode

UNION ALL

-- Recursive member, select all the nodes which have the previous
-- one as their predecessor. Concat the paths together.
SELECT n.Id, node.solarSystemName, n.Estimate,
CAST(cte.Path + ',' + CAST(n.Id as varchar(10)) as varchar(8000)),
CAST(cte.NamePath + ',' + node.solarSystemName AS varchar(8000))
FROM #Nodes n JOIN BacktraceCTE cte ON n.Predecessor = cte.Id
JOIN dbo.mapSolarSystems node ON n.Id = node.solarSystemID
)
SELECT Id, Name, Distance, Path, NamePath FROM BacktraceCTE
WHERE Id = @EndNode OR @EndNode IS NULL -- This kind of where clause can potentially produce
ORDER BY Id -- a bad execution plan, but I use it for simplicity here.

DROP TABLE #Nodes
COMMIT TRAN
RETURN 0
END


 

This thread is older than 90 days and has been locked due to inactivity.


 


The new forums are live

Please adjust your bookmarks to https://forums.eveonline.com

These forums are archived and read-only