Pages: [1] 2 :: one page |
|
Author |
Thread Statistics | Show CCP posts - 2 post(s) |
Almir Kadric
|
Posted - 2011.08.03 15:35:00 -
[1]
Now I have found a few table dumps out there for this, however I was curious as to how people built it. I've currently tried a few ways but they all seem like they would take forever to finish (Months if not years).
So people like "Nikolai Kondratiev" and others who have accomplished this, I ask you nicely how you did it, and how long does it take to build this data? (ALL 60 MILLION+ ROWS OF IT).
Any info would be immensely appreciated!
|
Almir Kadric
|
Posted - 2011.08.05 08:14:00 -
[2]
*bump*
Maybe CCP can enlighten us as too how they do it for in game auto pilot?
Just tried Breadth First Algorithm, seems that my SQL Flood fill script is faster.
But still not fast enough to do all routes in a feasible time.
Anyone?
|
|
CCP Prism X
Gallente C C P C C P Alliance
|
Posted - 2011.08.05 09:09:00 -
[3]
We do not use a look-up table like this for the routes and distances, although CCP Atlas did use such a table in his Asset Buddy demo on the latest FanFest Dev Tracks. Perhaps that table is accessible somewhere on the interwebs but he's on vacation so I cannot ask him whether it fulfills your needs or where it is.
However, it's no secret that we use Dijkstra to calculate the routes in game. I believe the best third-party route calculators I've seen do the same.
Hope that helps.
~ CCP Prism X EVE Database Developer If anything in this post was informative or could be considered as 'good news' to you - chances are you've misread it. |
|
Almir Kadric
|
Posted - 2011.08.06 00:40:00 -
[4]
wait wouldn't this be inefficient as map edges (real distance between systems) don't have a weight as 1 jump is still 1 jump regardless of how far it takes you?
Wouldn't it be better to use Breadth First Algorithm as all edges are the same length?
So you're telling me that the in game autopilot relies purely on server cluster grunt and there's no caching for common routes?
|
Almir Kadric
|
Posted - 2011.08.06 00:42:00 -
[5]
Thought I would add some stuff I found last night.
This has been the most promising post I could find so far: http://www.eveonline.com/ingameboard.asp?a=topic&threadID=1486227
I've taken a look, that solution is still a tad inefficient but he promised 2 hour returns.
I've since then improved the algorithm greatly, waiting on return times now.
WILL LET YOU KNOW! (bound to be useful to someone right?)
|
Almir Kadric
|
Posted - 2011.08.06 06:31:00 -
[6]
Edited by: Almir Kadric on 06/08/2011 06:31:57 Edited by: Almir Kadric on 06/08/2011 06:31:19 SOLVED IT!!!
Got a solution to utilize my CPU @ 100% and knocked all high sec systems factorial in ONLY 10 MINUTES!
Something similar to last post except I used a queued Breadth First Factorial algorithm which had a few tweaks to ignore anything which didn't move down the tree (or I should say away from the origin). Then collectively inserted them to reduce insert lag.
Also spent some time on thread emulation to utilize as much CPU power as possible.
Worked out well ^_^
P.S. Will provide a link to the cache data sets after I've checked that the calculations have proven to be correct.
|
Shellac Brookdale
|
Posted - 2011.08.06 10:41:00 -
[7]
Precalculated routes will let you hit the wall when you need to be able to exclude certain waypoints or need to create routes based on user options (e.g. penalties based on sec status).
Originally by: Almir Kadric wait wouldn't this be inefficient as map edges (real distance between systems) don't have a weight as 1 jump is still 1 jump regardless of how far it takes you?
You can create edge lengths based on whatever you like. Eg. sec status, number of recent kills, or LYs.
Originally by: Almir Kadric
So you're telling me that the in game autopilot relies purely on server cluster grunt and there's no caching for common routes?
Who tells you its done on the server? Also dijkstra is freaking fast if done right. Probably faster on shorter routes than querying a database.
|
Almir Kadric
|
Posted - 2011.08.06 12:58:00 -
[8]
Edited by: Almir Kadric on 06/08/2011 13:01:54 CHECKED MY DATA, so far it's 100% accurate. Even generated 300k rows using the normal slower method and checked for differences and I got none ^_^
Currently working on a feature to this project with avoidance lists.
Originally by: Shellac Brookdale Precalculated routes will let you hit the wall when you need to be able to exclude certain waypoints or need to create routes based on user options (e.g. penalties based on sec status).
I've actually worked on this limitation (as stated above) and have a solution, currently checking for bugs. It should be much faster than remapping the route. It basically takes a pre-calculated route then builds only sister branches beside it, after which it find's an alternate route avoiding the systems flagged. I'm also introducing an 'avoid' field in the DB which I will use to cache the alternate routes after they have been calculated. This will ensure a speedy routing system.
Originally by: Shellac Brookdale You can create edge lengths based on whatever you like. Eg. sec status, number of recent kills, or LYs.
This is a very good point, I hadn't considered it to be honest. Will keep it in consideration with future designs. Thanks ^_^
Originally by: Shellac Brookdale Who tells you its done on the server? Also dijkstra is freaking fast if done right. Probably faster on shorter routes than querying a database.
Well read up, CCP Prism did Also I fail to see this, as querying for 1 row of data and less data at that vs querying for 1-5 rows of data (even if you cut some data) is just logically slower. You must have dealt with a un-optimized database. Unless you're speaking about a hard coded data map which is always held within memory which is just inefficient and unthinkable on so many levels for a website (production box for web servicing more specifically). Need to remember this isn't an eve cluster with all in game data held in memory (well close to anyway since the cluster may use HDD memory swapping XD).
|
Callean Drevus
Caldari Icosahedron Crafts and Shipping Silent Infinity
|
Posted - 2011.08.07 08:59:00 -
[9]
I think querying for 5 rows of data is faster in a table of 3000 rows, than querying for 1 row (depending on which it is) in a table of 30000000 rows :)
If you succeed in building this table however, I'd be very interested. --- "A fool flatters himself, a wise man flatters the fool."
Chief Developer of EVE Marketeer. |
Almir Kadric
|
Posted - 2011.08.08 09:26:00 -
[10]
Originally by: Callean Drevus I think querying for 5 rows of data is faster in a table of 3000 rows, than querying for 1 row (depending on which it is) in a table of 30000000 rows :)
If you succeed in building this table however, I'd be very interested.
True YET False, your statement is true, but the application is false. To build the route using the algorithm you need to pull up 1-3k rows of data (all jumps highsec/lowsec/both) then have to run a loop on the data (5-10 seconds). Seems fast, however in comparison to 1ms it isn't ^_^
I have built the table successfully, and have also got it working really fast (builds in about 10 mins). Also it only takes shortest routes so currently high sec only has less than 1mill rows (it automatically purges systems which are not accessible without crossing low sec). The actual cache look up times are really fast as I said. This means now with every static data dump I can have a fresh cache table ^_^
Just got my new release up. Will create a dump file link soon.
|
|
|
CCP Prism X
Gallente C C P C C P Alliance
|
Posted - 2011.08.08 09:28:00 -
[11]
Edited by: CCP Prism X on 08/08/2011 09:30:36
Originally by: Almir Kadric
Originally by: Shellac Brookdale Who tells you its done on the server? Also dijkstra is freaking fast if done right. Probably faster on shorter routes than querying a database.
Well read up, CCP Prism did
I did? Well I didn't mean too. It's true that in some edge cases the server needs to do some basic jump calculations but it's mostly done on the terminal computer as if you hack your client to give you a weird route.. all you end up with is a weird route, not a game advantage.
Therefore this is clearly a more efficient approach than a DB lookup as it never crosses the wire. Crossing the wire is bad and you should avoid it like the plague as you do not have any assurance on response time. Even if we did go this way it would still be a better idea to cache it on the server to avoid the DB dip, at which point we're caching systemCount*systemCount records which doesn't scale that well. It would also be better for us to never query this to the servers but ship it precalced as a part of our bulk data. I've long forgotten the actual size of such a datachunk but it was rather excessive.. so efficient calculation is, looking at the big picture, optimal.
But you're right, if you only think about the processing time on a local DB single row lookup vs Dijkstra then the lookup table is optimal. But when is life ever simple like that?
Edits: Fixing spelling, typos and generally trying to sound smarter!
~ CCP Prism X EVE Database Developer [i]If anything in this post was informative or could be considered as 'good news' to you - chances are you've misread it. |
|
MFG Overload
Minmatar Republic University
|
Posted - 2011.08.09 09:49:00 -
[12]
Originally by: Almir Kadric
I have built the table successfully, and have also got it working really fast (builds in about 10 mins). Also it only takes shortest routes so currently high sec only has less than 1mill rows (it automatically purges systems which are not accessible without crossing low sec). The actual cache look up times are really fast as I said. This means now with every static data dump I can have a fresh cache table ^_^
Just got my new release up. Will create a dump file link soon.
Highsec dump would be awesome :)
|
Callean Drevus
Caldari Icosahedron Crafts and Shipping Silent Infinity
|
Posted - 2011.08.09 11:44:00 -
[13]
Almir!
Your registration is not working (or has an obscure requirement). It keeps complaining about 'alphaNumeric' even if I only enter lowercase letters for my name. --- "A fool flatters himself, a wise man flatters the fool."
Chief Developer of EVE Marketeer. |
Osku Rei
|
Posted - 2011.08.11 02:29:00 -
[14]
Probably not exactly what you are looking for but, I created a simple API for doing this job:
http://api.evejb.com/?from=Jita&to=Amarr
Results returned in XML, msg me if you want any more features / data returned.
|
Shallow Joe
|
Posted - 2011.08.11 04:11:00 -
[15]
Originally by: Almir Kadric So people like "Nikolai Kondratiev" and others who have accomplished this, I ask you nicely how you did it, and how long does it take to build this data? (ALL 60 MILLION+ ROWS OF IT).
I built a table that returned the distance from any system to every other system using Djikstra. In my application, a had one row for each source system - a lookup of that row returned an array of tinyints that represented the distance to every other system. I also calculated a second distance using only hisec routes, which is returned in a second array.
This information serves a multitude of decision-making purposes, and then I rerun the djikstra only when I need every step along the route.
The table-building app ran in under an hour.
|
Callean Drevus
Caldari Icosahedron Crafts and Shipping Silent Infinity
|
Posted - 2011.08.11 08:36:00 -
[16]
Originally by: Osku Rei Probably not exactly what you are looking for but, I created a simple API for doing this job:
http://api.evejb.com/?from=Jita&to=Amarr
Results returned in XML, msg me if you want any more features / data returned.
Until the table has been released however, this is of immense use to me, and possible others. --- "A fool flatters himself, a wise man flatters the fool."
Chief Developer of EVE Marketeer. |
Almir Kadric
|
Posted - 2011.08.11 13:38:00 -
[17]
Edited by: Almir Kadric on 11/08/2011 13:38:43 Edited by: Almir Kadric on 11/08/2011 13:38:15
Originally by: MFG Overload Highsec dump would be awesome :)
SORRY FOR THE DELAY!!!
I've put up the dump here: EveSystemRoutes.sql.bz2
Let me know if there are any errors with it.
Originally by: Callean Drevus Almir!
Your registration is not working (or has an obscure requirement). It keeps complaining about 'alphaNumeric' even if I only enter lowercase letters for my name.
WOW that was fast lol, didn't expect anyone to use it yet XD I just tested it, and put up a few fixes. It seems my frameworks internal alphanumeric validator was busted and kept return false. But the weird thing is, it only happens on my production environment...=_= so i wrote my own.
Well now it's all fixed
I noticed you implemented feedback as well XD
It seems there are a few users already using your site. I haven't bothered marketing my website yet. Want to get a working product before I bother telling too many people about it.
|
MFG Overload
Minmatar Republic University
|
Posted - 2011.08.11 14:07:00 -
[18]
SQL structure would be good =) I don't know what's the third and forth column.
Thanks Almir!
|
Almir Kadric
|
Posted - 2011.08.11 14:56:00 -
[19]
Edited by: Almir Kadric on 11/08/2011 14:56:10
Originally by: MFG Overload SQL structure would be good =) I don't know what's the third and forth column.
Thanks Almir!
Sorry about that XD, I wrote my generator script to either dump sql statements to a file (for debugging purposes) or to import it directly into the database. Totally forgot about the SQL table structure.
This is the create statement my script uses:
CREATE TABLE eve_system_routes_new ( fromSystemID BIGINT UNSIGNED NOT NULL, toSystemID BIGINT UNSIGNED NOT NULL, highsec TINYINT(1) NOT NULL, lowsec TINYINT(1) NOT NULL, throughSystems VARCHAR(1024) NOT NULL, jumps INT NOT NULL, PRIMARY KEY (fromSystemID, toSystemID, highsec, lowsec) ) ENGINE = MyISAM DEFAULT CHARACTER SET = utf8 COLLATE = utf8_unicode_ci;
The 3rd and 4th column are boolean values which determine if the routes passes highsec or lowsec (can be both). The dump I provided contains highsec only rows as that's all I need at the moment. Later on I will probably generate lowsec only rows and both highsec and lowsec rows which are shorter than the highsec only or lowsec only counter parts (which would be the most complete data set). I will also begin collecting the most avoided systems at some point and incorporate them into the automatic generation scripts at some point as well.
|
Callean Drevus
Caldari Icosahedron Crafts and Shipping Silent Infinity
|
Posted - 2011.08.11 18:10:00 -
[20]
Originally by: Almir Kadric WOW that was fast lol, didn't expect anyone to use it yet XD I just tested it, and put up a few fixes. It seems my frameworks internal alphanumeric validator was busted and kept returning false. But the weird thing is, it only happens on my production environment...=_= so i wrote my own.
Well now it's all fixed
I noticed you implemented feedback as well XD
It seems there are a few users already using your site. I haven't bothered marketing my website yet. Want to get a working product before I bother telling too many people about it.
Yay, I created an account. Now I cannot log in :P And I can't use the feedback form to report it. So sorry, another post hijacking your thread for feedback.
I have to keep up with your changes. And feedback seemed like a very important thing to have ;) especially since I have a tendency to forget what is important :) --- "A fool flatters himself, a wise man flatters the fool."
Chief Developer of EVE Marketeer. |
|
MFG Overload
Minmatar Republic University
|
Posted - 2011.08.11 18:46:00 -
[21]
Edited by: MFG Overload on 11/08/2011 18:46:22 Edited by: MFG Overload on 11/08/2011 18:45:46 There are a couple of broken lines in the dump:
('30005229', '30005029', '1', '0', '30005301,30005204,30005203,30005024,30005025,30005026,30005029',INSERT IGNORE INTO eve_system_routes_new VALUES
('30002508', '30001718', '1', '0', '30002509,30000004,30000005,30000002,30002973,30002969,30002974,30002972,30002971,30002970,30002963,30002964,30002991,30002994,30003545,30003548,30003525,30003523,30003522,30002187,3INSERT IGNORE INTO eve_system_routes_new VALUES
|
Osku Rei
|
Posted - 2011.08.12 00:55:00 -
[22]
Originally by: Callean Drevus
Originally by: Osku Rei Probably not exactly what you are looking for but, I created a simple API for doing this job:
http://api.evejb.com/?from=Jita&to=Amarr
Results returned in XML, msg me if you want any more features / data returned.
Until the table has been released however, this is of immense use to me, and possible others.
Looking at the other posts, remember this does not consider sec status, it's only interested in the shortest route. If people want to use this full-time, give me a mail/convo and ill work with you to get the data / features you need. :)
|
Almir Kadric
|
Posted - 2011.08.12 02:21:00 -
[23]
Originally by: Callean Drevus
Yay, I created an account. Now I cannot log in :P And I can't use the feedback form to report it. So sorry, another post hijacking your thread for feedback.
I have to keep up with your changes. And feedback seemed like a very important thing to have ;) especially since I have a tendency to forget what is important :)
What part of the login you getting stuck on? I just tested it and its working fine. Perhaps it's because I haven't actually put up anything letting you know you're logged on that you're getting confused? I'm working on logged on features atm (a whole bunch of them) haven't moved them all to production yet (not even the feedback view/comment section similar to what you have). Quite a big release I got happening atm and the bad thing is I'm looking at making my own fitting tool which is kinda side tracking me as I discover or think up nice ways to do it. Like you i easily forget what's important XD
Originally by: MFG Overload
There are a couple of broken lines in the dump:
('30005229', '30005029', '1', '0', '30005301,30005204,30005203,30005024,30005025,30005026,30005029',INSERT IGNORE INTO eve_system_routes_new VALUES
('30002508', '30001718', '1', '0', '30002509,30000004,30000005,30000002,30002973,30002969,30002974,30002972,30002971,30002970,30002963,30002964,30002991,30002994,30003545,30003548,30003525,30003523,30003522,30002187,3INSERT IGNORE INTO eve_system_routes_new VALUES
I feel so embarrassed for this. You know how I mentioned I forgot about the table structure. Well apparently I didn't. When I looked into the code, its the first thing the script dumps since it dumps whatever it queries to the server. Then I dug deeper and realized I accidentally gave you an old dump. It was in the same folder but I guess I never ran the script again to dump to file since I knew it was working (remember I said for debugging purposes) XD The thing is when I first implemented the thread emulation to speed up the script I hadn't implemented thread safe writes (which is what you are seeing) anyways I reran the script and viola no issues ^_^
Let me know if you find any though as I could be wrong XD
Originally by: Osku Rei
Looking at the other posts, remember this does not consider sec status, it's only interested in the shortest route. If people want to use this full-time, give me a mail/convo and ill work with you to get the data / features you need. :)
Well the dump yes, but actual script no. I've retested it and it seems the longest route only takes me 10 seconds to calculate regardless of how complex it is. So i will be implementing this directly on my site as a feature. As for ETA not entirely sure as I probably will do this when I start implementing route planning or trade route planning.
|
Osku Rei
|
Posted - 2011.08.12 02:55:00 -
[24]
Originally by: Almir Kadric
Originally by: Callean Drevus
Originally by: Osku Rei
Looking at the other posts, remember this does not consider sec status, it's only interested in the shortest route. If people want to use this full-time, give me a mail/convo and ill work with you to get the data / features you need. :)
Well the dump yes, but actual script no. I've retested it and it seems the longest route only takes me 10 seconds to calculate regardless of how complex it is. So i will be implementing this directly on my site as a feature. As for ETA not entirely sure as I probably will do this when I start implementing route planning or trade route planning.
Sorry i'm confused and didn't quite get what you meant. I was talking about my API.
What is the dump and the script? Retested? retested my API or your stuff?
I tested http://api.evejb.com/?from=QYZM-W&to=ZDYA-G Those 2 systems are opposite ends of the Eve universe, not sure if its the furthest distance or the most complex route but its still 94 jumps. That route was calculated in: "Query took 0.103969097137 seconds" Not sure about the 10 seconds you got?
Quote: So i will be implementing this directly on my site as a feature
My API or your stuff?
I'm just curios, maybe i'm being dump lol.
|
Almir Kadric
|
Posted - 2011.08.12 03:23:00 -
[25]
Originally by: Osku Rei
Sorry i'm confused and didn't quite get what you meant. I was talking about my API.
What is the dump and the script? Retested? retested my API or your stuff?
I tested http://api.evejb.com/?from=QYZM-W&to=ZDYA-G Those 2 systems are opposite ends of the Eve universe, not sure if its the furthest distance or the most complex route but its still 94 jumps. That route was calculated in: "Query took 0.103969097137 seconds" Not sure about the 10 seconds you got?
Originally by: Osku Rei
My API or your stuff?
I'm just curios, maybe i'm being dump lol.
Sorry I thought you were talking about my data dump which I provided.
As for the 10 seconds I was talking about, that was how long it takes my script to map every route possible between 1 system and all other systems. Thus in essence I should get the same time result you got when I only calculate shortest route between 2 systems.
Hope this clears things up ^_^
|
MFG Overload
Minmatar Republic University
|
Posted - 2011.08.12 11:13:00 -
[26]
The new dump works ok :)
Thanks Almir!
|
Callean Drevus
Caldari New Eden Law Enforcement
|
Posted - 2011.08.13 09:09:00 -
[27]
Quote: What part of the login you getting stuck on? I just tested it and its working fine. Perhaps it's because I haven't actually put up anything letting you know you're logged on that you're getting confused? I'm working on logged on features atm (a whole bunch of them) haven't moved them all to production yet (not even the feedback view/comment section similar to what you have). Quite a big release I got happening atm and the bad thing is I'm looking at making my own fitting tool which is kinda side tracking me as I discover or think up nice ways to do it. Like you i easily forget what's important XD
Mostly, I'm finding that nothing happens after entering my details on the login form :P I click submit, and it loads a bit, then I'm back at the login form, even though I wanted to go to feedback :P this might be just no notification that I'm logged in though :) --- "A fool flatters himself, a wise man flatters the fool."
Chief Developer of EVE Marketeer. |
Almir Kadric
|
Posted - 2011.08.13 11:13:00 -
[28]
Originally by: Callean Drevus
Mostly, I'm finding that nothing happens after entering my details on the login form :P I click submit, and it loads a bit, then I'm back at the login form, even though I wanted to go to feedback :P this might be just no notification that I'm logged in though :)
Hmm ok, well i think i might break off a part of my release early then to help with the situation. All user management screens and notifications etc. May as well put them up early to at least show things are kind of working. I'll let you know when to try again.
|
Callean Drevus
Caldari New Eden Law Enforcement
|
Posted - 2011.08.13 12:52:00 -
[29]
Originally by: Almir Kadric Hmm ok, well i think i might break off a part of my release early then to help with the situation. All user management screens and notifications etc. May as well put them up early to at least show things are kind of working. I'll let you know when to try again.
Sorry if I'm being annoying, I'm not trying to push you to fix it, it was just meant to let you know.
I'll just sit and wait till you tell me it's done and THEN I'll go look, I'll just have to keep my curiosity in check for now --- "A fool flatters himself, a wise man flatters the fool."
Chief Developer of EVE Marketeer. |
Dragonaire
Caldari Corax. PURgE Alliance
|
Posted - 2011.08.14 07:06:00 -
[30]
Found this while looking around at some other stuff and thought you might find it interesting. http://openquery.com/graph/doc and what lead me to it. http://kb.askmonty.org/en/what-is-mariadb-52
It seems to be made to do what you need and lets you use Dijkstra or Breadth-first searches etc. I only understand the stuff in general since I haven't played with path finding but thought anyone doing so might be interested in it. -- Finds camping stations from the inside much easier. Designer of Yapeal for Eve API.
|
|
|
|
|
Pages: [1] 2 :: one page |
First page | Previous page | Next page | Last page |