| Pages: 1 2 [3] :: one page |
|
|
| Author |
Thread Statistics | Show CCP posts - 1 post(s) |
Azure Eyes
   |
Posted - 2006.10.21 13:41:00 -
[61]
 Originally by: Professional Troll
Except that would give you a table with 5000^4999 (simplified, approximately 1.416+10^18,491) rows in order to get the shortest path from each of the 5,000 systems to all 4,999 other systems. In other words there is not enough storage space on all computers all around the world combined to store a look-up table that big.
Sure? Remember if we have a route from A to B we don't need a route from B to A. The way I figure, you'd need to calculate the number of possible unordered combinations of two elements from a set of five thousand. That's 5000 choose 2 = 12 497 500, which isn't that large a table...
Mind you, I'm not actually proposing CCP does it this way, I was merely musing at alternatives.
|
Rorix Whitecloud
Caldari
Eve Defence Force
Ascendant Frontier
|
Posted - 2006.10.21 16:19:00 -
[62]
Originally by: Professional Troll
Originally by: Azure Eyes
Edited by: Azure Eyes on 21/10/2006 11:13:13
Given that the universe we live in small and discrete, i.e. there's only about five thousand possible places to be and those places have static and well defined connections, there's a roundabout way to solve this. There exist algorithms that solve so-called All-Pairs path finding. That means that upon completion, the algorithm leaves you with optimal routes from every point in the graph to every other point in the graph. This algorithm must be run once each time the map changes, and the results can be disseminated to the clients as a large lookup table. Whenever route planning is to be done, the client simply selects a solution from the table. Elegant, right?
Except that would give you a table with 5000^4999 (simplified, approximately 1.416+10^18,491) rows in order to get the shortest path from each of the 5,000 systems to all 4,999 other systems. In other words there is not enough storage space on all computers all around the world combined to store a look-up table that big.
Well, all that would do is give you the optimal route from point A to point B... what if you are at Point A, and you're going to B, C, D, E, but not necessarly in order?
Point B might be closer to A than any other point, so your auto pilot will select A, B, etc etc... while in reality, the shortest path for the ENTIRE route would be, for example, A, C, E, B, D? This is also why the Dijkstra's algorithem probably wont work for this situation.
Sig pic too old... and lost the template during reformatting (doh!)
Goal: To blaster-fit every Caldari ship that has a turret slot.
~I don't remember. That's the second thing they teach you. |
FireFoxx80
Caldari
E X O D U S
Imperial Republic Of the North
|
Posted - 2006.10.23 08:42:00 -
[63]
You can make it easier by ignoring all systems that don't have a station.
What I do the rest of the time - Vote for a Jita bypass! |
DeODokktor
Caldari
Dark Templars
The Fonz Presidium
|
Posted - 2006.10.23 09:50:00 -
[64]
Edited by: DeODokktor on 23/10/2006 09:50:57
all you guy's who say it's the traveling salesman issue
well, that's silly
ccp just need to allocate some time for a new search to be coded, and probably somehow get it out of python.
I used to play a game that had 20,000 systems
each system might have from 1 -> 6 warps in/out with some of those being non-return warps.
to calculate the most efficent paths I could do probably 300 a second.
I dont know how indepth the path calulator is. if it try's to figgure total warp distance and cap usage to find a time based travel time (vs a jump based travel time) then I can see it taking a lot more cpu.
It just needs some code luvvin and no effin descriptions of "traveling salesman" or other crap.
|
FireFoxx80
Caldari
E X O D U S
Imperial Republic Of the North
|
Posted - 2006.10.23 10:17:00 -
[65]
Its two problems though:
Route from A > B: Is simply A* or Dijikstra (depending on whether you are weighting distance+security, or just distance). Which yes, depending on how complex it is, runs fairly quickly (although setting up routes like A > B but try to stay as close as poss to 0.5; tends to slow things down)
TSP relates to multiple systems, with no fixed order. So the most efficient route between systems A, B, C, D, E.
What I do the rest of the time - Vote for a Jita bypass! |
Shiraz Merlot
Octavian Vanguard
RAZOR Alliance
|
Posted - 2006.10.23 10:34:00 -
[66]
Originally by: DeODokktor
It just needs some code luvvin and no effin descriptions of "traveling salesman" or other crap.
I know a manager like you.
|
Spanker
|
Posted - 2006.10.23 10:38:00 -
[67]
This is very cool stuff. Where can I download a data set of the eve map?
- Shpank |
Shiraz Merlot
Octavian Vanguard
RAZOR Alliance
|
Posted - 2006.10.23 10:41:00 -
[68]
Originally by: evistin
Honsetly, if you can fix this problem, the NP complete problem, you will be forever marked a maths God. This is how tough it is. I am suggesting using more metric in the caculation, such as queue lenght, system traffic, node load,etc,etc...via the DUAL alogrithem.
DUAL is patented and afaik is licensed only to Cisco for use in their EIGRP routing protocol. The inventor of DUAL (Prof. J.J. Garcia-Luna-Aceves, now at UCSC) has (along with his grad students) in recent years done some amazing research work with ad-hoc routing and multicasting. None of it, alas, geared towards solving a high-order TS problem.
/sm
|
Shiraz Merlot
Octavian Vanguard
RAZOR Alliance
|
Posted - 2006.10.23 13:22:00 -
[69]
Originally by: Spanker
This is very cool stuff. Where can I download a data set of the eve map?
Linky
|
Jessica May
|
Posted - 2006.10.23 14:12:00 -
[70]
Originally by: Kweel Nakashyn
Edited by: Kweel Nakashyn on 09/09/2006 09:52:03
Originally by: Lazuran
(...) these things run on low-power embedded CPUs (...)
No.
Most of GPS CPU are sized to handle more calculation than EVE client at the moment it were released. THey also can catch very high frequency/energy microwave. Don't even think you decypher something if you pulse slower than these. Also AsGA Asics are no way near of any of my definitions of low-energy CPU.
Second, GPS don't have to calculate a video game running backward.
Third, actually a friend n my corp use Dijkstra's for the very same problem and the result he had were slower than in game. He's a doctor in informatics so don't even think he can't code :)
Edit : the forth point is just search GPS + CPU on google, you'll see some cpu specs. (I didn't linked them because I don't know CCP's policy against other compagny commercial links). Consider these CPU are designed to specifically run route optimisation between two to five points (and no 13 waypoints like in this example) and voila :)
Originally by: Lazuran
(...) But hey, with your arrogance and ignorance, you made my day. ;-)
You're welcome in our club :)
So a Laptop running a game with Microsoft Auto Route in the background with a USB Sat Nav arial wouldn't be able to compute a route? (Think caurefully, you might be talking to someone who has tried this).
|
|
|
Kweel Nakashyn
Minmatar
Aeden
Tau Ceti Federation
|
Posted - 2006.10.26 17:39:00 -
[71]
Edited by: Kweel Nakashyn on 26/10/2006 17:39:54
Originally by: Jessica May
So a Laptop running a game with Microsoft Auto Route in the background with a USB Sat Nav arial wouldn't be able to compute a route? (Think caurefully, you might be talking to someone who has tried this).
Zomgeeze Necro (sorry again)
Why not ?
My purpose is to say GPS's chips are not game'n watch's, not to say GPS's chip are like modern mainframes's racks.
I underlined that the device that decypher the signal isn't made by a game'n watch, and the fact that you won't catch flies with a butterfly net (catching 15 GHz waves with a silicon chip that pulse @ 3.5 GHz : there's a chip in your usb thingy). Btw, usb is not in my book of low-power devices :)
If you have this device, please monitor the CPU/GPU activity while only computing/uploadinbg gps data, I would be curious if it's all computed on your usb or not.
|
|
|
| |
|
| Pages: 1 2 [3] :: one page |
| First page | Previous page | Next page | Last page |