| Pages: [1] :: one page |
| Author |
Thread Statistics | Show CCP posts - 0 post(s) |
Wildthrust Mathilde
   |
Posted - 2008.01.07 19:48:00 -
[1]
I am trying to work out the logic of how best to find the shortest route between two points using the SQL Dump information. I know I can always do a long looping system that performs essentialy a radial search with a few things thrown in to get rid of some of the seaching, but is there a specific way to do it so its fairly fast. Im just looking for a description really of how to do it, that way I can write the code to access the database in whichever language I decide on (php, cfml, extjs, actionscript, etc)
Thanks
|
Sister Madeline
Amarr
Ka-Tet
|
Posted - 2008.01.07 21:23:00 -
[2]
mapRegionJumps , plot a course from startregion -> endregion
mapConstellationJumps, plot a course from startconstellation -> endconstellation where regions can only be IN OR NEXT TO the regions in the region path
mapSolarsystemJumps, plot a course from start -> end where constellation can ONLY be in the constellation map or X jumps around it.
If you'd only do the last one you'd be running totally not optimized, by checking regions and constellations you can rule out around 80% of the solarsystem list on your average route.
|
Wildthrust Star
|
Posted - 2008.01.07 23:36:00 -
[3]
Ya, thats what I had been thinking. Was hoping maybe there was some kind of search algorithim or something that could make it simpler. But this lets me feel better to stop looking and just do it that way. :)
|
Kalixa Hihro
|
Posted - 2008.01.08 02:06:00 -
[4]
 Originally by: Wildthrust Mathilde
I am trying to work out the logic of how best to find the shortest route between two points using the SQL Dump information. I know I can always do a long looping system that performs essentialy a radial search with a few things thrown in to get rid of some of the seaching, but is there a specific way to do it so its fairly fast. Im just looking for a description really of how to do it, that way I can write the code to access the database in whichever language I decide on (php, cfml, extjs, actionscript, etc)
Thanks
That is sooo funny I came here looking for the same info. Cosmic...
/*----------------------------------------------------------------------------------*/
My opinion in no way represents that of my corp or anyone I am associated with, and is probably entirely wrong. |
Dunedon
Ansillon Industries
|
Posted - 2008.01.08 14:26:00 -
[5]
Currently I believe that most people doing searches for shortest path jumps are using some variation of the A* shortest path algorithm.
You can find quite a few topics on it if you search the Technology Forum ... or check out the wikipedia article on A*.
- Dunedon
------
WYSIWYG: I don't post with an Alt ... if I die in game for having an opinion, at least I know someone listened. - Dunedon |
Ix Forres
Vanguard Frontiers
Imperial Republic Of the North
|
Posted - 2008.01.08 18:11:00 -
[6]
Originally by: Dunedon
Currently I believe that most people doing searches for shortest path jumps are using some variation of the A* shortest path algorithm.
You can find quite a few topics on it if you search the Technology Forum ... or check out the wikipedia article on A*.
- Dunedon
Dijkstra's algorithm also works but A* is the weapon of choice for most.
Blog |
Fink Angel
Caldari
The Merry Men
|
Posted - 2008.01.08 23:31:00 -
[7]
Another reference worth looking at is the Travelling Salesman Problem.
|
Henry Loenwind
|
Posted - 2008.01.10 18:18:00 -
[8]
Originally by: Ix Forres
Dijkstra's algorithm also works but A* is the weapon of choice for most.
A* won't help a bit, because there is no usable distance information for the nodes. And guess what an A* without that is---yeah right, a simple Dijkstra's...
|
Kalif Arnuex
Two Brothers Mining Corp.
|
Posted - 2008.01.11 19:33:00 -
[9]
For distance weight everything as 1. However, will eventually care more about lowsec vs highsec at that point some artificial weight of your own choosing will be the distance.
|
| |
|
| Pages: [1] :: one page |
| First page | Previous page | Next page | Last page |