open All Channels
seplocked EVE Technology Lab
blankseplocked MySQL & graph algorithms (route finding)
 
This thread is older than 90 days and has been locked due to inactivity.


 
Author Topic

Bostaka
Posted - 2010.07.22 18:35:00 - [1]
 

Edited by: Bostaka on 22/07/2010 18:37:13
Edited by: Bostaka on 22/07/2010 18:35:32
Heya,

I failed my degree in computer science so ...

Using the Tyrannis SQL datadump, what's the easiest way of finding the quickest route between two systems and the like? If someone could give me something to Google as a starting point that would be great! It's been 10 years since I touched this algorithm and I dont think it would have worked on a database anyway...

I'm prepared to get my hands dirty, in fact that's the idea, I can handle a bit of mysql/php but please bare in mind I failed miserably at the mathematical side of things and algorithms like this at the best of times so pls go easy on the terminology!!

Ty :))

Gar Karath
Caldari
Posted - 2010.07.22 18:42:00 - [2]
 

Edited by: Gar Karath on 22/07/2010 18:54:31
Originally by: Bostaka
Edited by: Bostaka on 22/07/2010 18:37:13
Edited by: Bostaka on 22/07/2010 18:35:32
Heya,

I failed my degree in computer science so ...

Using the Tyrannis SQL datadump, what's the easiest way of finding the quickest route between two systems and the like? If someone could give me something to Google as a starting point that would be great! It's been 10 years since I touched this algorithm and I dont think it would have worked on a database anyway...

I'm prepared to get my hands dirty, in fact that's the idea, I can handle a bit of mysql/php but please bare in mind I failed miserably at the mathematical side of things and algorithms like this at the best of times so pls go easy on the terminology!!

Ty :))


There are several possibilities.
The easiest one might be: Dijkstra's Algorithm
Another option is the A star search algorithm

With a star you can use the system coordinates for the cost function. Have fun reading ;)

Edit: Eve Forum Link Fail .. here are the links:
http://en.wikipedia.org/wiki/Dijkstra's_algorithm
http://en.wikipedia.org/wiki/A*_search_algorithm

CCP Atropos

Posted - 2010.07.22 19:47:00 - [3]
 

This has come up a bunch of times before, so just put Dijkstra into the search box in the top right up there Cool

Flammard
Caldari
The New Era
C0NVICTED
Posted - 2010.07.25 00:56:00 - [4]
 

Edited by: Flammard on 25/07/2010 01:18:05
A simple breadth first search will find you the shortest hop count, if you want to start with something simple. It's easier to understand than Dijkstra's algorithm or A*.

If you want to take security status into account then you will need to use Dijkstra's algorithm, which is slightly more complex.

TBH I wouldn't bother with A*. It's a lot more complex than what is required.

About a year ago I slapped together a small C program that did a BFS search to find the shortest hop count between two systems as an exercise, but once I got it working I never really developed it further. If anyone wants it I can search for it and post it somewhere.

Ambo
I've Got Nothing
Posted - 2010.07.25 07:12:00 - [5]
 

Edited by: Ambo on 25/07/2010 07:35:53
My final solution was to do some pre-processing of the data and then use Djikstra's algorithm:

This MSSQL code creates two new tables, SolarSystemJumps and SolarSystemDistances. It takes a few seconds to executes and only needs to be run once (and then each time the map is updated from the datadump.)

Quote:
-- Thanks go to 'Jethro Jechonias' for the original version of this code.


/* Create tables for distance calculation Drop and recreate tables if they already exist
[dbo].[SolarSystemJumps] [dbo].[SolarSystemDistances]*/
if exists (select * from dbo.sysobjects where id = object_id(N'[dbo].[SolarSystemJumps]') and OBJECTPROPERTY(id, N'IsUserTable') = 1)
drop table [dbo].[SolarSystemJumps]

CREATE TABLE [dbo].[SolarSystemJumps]
(
[FromSolarSystemID] [int] NOT NULL ,
[ToSolarSystemID] [int] NOT NULL ,
CONSTRAINT [PK_SolarSystemJumps] PRIMARY KEY CLUSTERED
(
[FromSolarSystemID],
[ToSolarSystemID]
)
)

if exists (select * from dbo.sysobjects where id = object_id(N'[dbo].[SolarSystemDistances]') and OBJECTPROPERTY(id, N'IsUserTable') = 1)
drop table [dbo].[SolarSystemDistances]

CREATE TABLE [dbo].[SolarSystemDistances]
(
[FromSolarSystemID] [int] NOT NULL ,
[ToSolarSystemID] [int] NOT NULL ,
[Distance] [int] NOT NULL,
CONSTRAINT [PK_SolarSystemDistances] PRIMARY KEY CLUSTERED
(
[FromSolarSystemID],
[ToSolarSystemID]
)
)

/* Find accessible jumps so that inaccessible jumps can be ignored in latter calculations
Jita (30000142) is used as the root system Records are stored in a new table for faster access */
INSERT INTO SolarSystemJumps
SELECT fromSolarSystemID, toSolarSystemID
FROM mapSolarSystemJumps
WHERE fromSolarSystemID = 30000142

WHILE @@ROWCOUNT > 0
BEGIN
INSERT INTO SolarSystemJumps
SELECT fromSolarSystemID, toSolarSystemID
FROM mapSolarSystemJumps
WHERE fromSolarSystemID IN
(
SELECT ToSolarSystemID
FROM SolarSystemJumps
)
AND toSolarSystemID NOT IN
(
SELECT ToSolarSystemID
FROM SolarSystemJumps
WHERE FromSolarSystemID = mapSolarSystemJumps.fromSolarSystemID
)
END

-- Populate distances table with inital values for 1 jump range.

INSERT INTO SolarSystemDistances
SELECT FromSolarSystemID, ToSolarSystemID, 1
FROM SolarSystemJumps


RETURN


Had to put my code in paste bin since it won't ft into the character limit here.


Stored proc 'SolarSystemJumps' is just this:

Quote:

SELECT *
FROM SolarSystemJumps
RETURN


This solution is very fast indeed. I use it to calculate multi-waypoint routes in my EMMA application. (Note that this does not solve the problem of multi-waypoint routes in itself but it is an important component.)

It can handle different weights for high-sec, low-sec and no-sec. It also has a few optimizations compared to a 'clean' Djikstra implementation.

I spent a long time working on this and doing LOTS of profiling of various different methods and this solution is as good as I could make it. If you have any questions, just give me a shout.


 

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