hint: within a system, the shortest path between 2 objects is a direct line
outside that, calculating shortest path over several systems is a classical computer-science classes problem.
| Forums de Wizou http://wiz0u.free.fr/forum/ |
|
| Routing data http://wiz0u.free.fr/forum/viewtopic.php?f=10&t=715 |
Page 1 of 1 |
| Author: | Heliomance [ Thu 09 Feb 2012, 12:07 ] |
| Post subject: | Routing data |
Hi, I'm starting work on a similar trading companion project, and one major hurdle I'm running into is calculating travel times between bases. I input the data manually for VanillaFL, but that's no use for mods - and took forever anyway. You've proved it's possible to extract the data to calculate shortest paths from the files, and I wondered if you could tell me how you did it? Thanks! |
|
| Author: | Wizou [ Sat 11 Feb 2012, 00:07 ] |
| Post subject: | Re: Routing data |
hint: within a system, the shortest path between 2 objects is a direct line outside that, calculating shortest path over several systems is a classical computer-science classes problem. |
|
| Author: | Heliomance [ Mon 13 Feb 2012, 11:59 ] |
| Post subject: | Re: Routing data |
Oh, I know the standard algorithms for calculating shortest paths given distances between neighbouring nodes, but that data's not in the files, not directly. Add to that the complexity of things like trade lanes meaning the space is non-Euclidean, and you can't just calculate everything by relative position. |
|
| Author: | Wizou [ Tue 14 Feb 2012, 21:10 ] |
| Post subject: | Re: Routing data |
well you're right about trade lane making it a bit more complex (you need to compare going without tradelane vs using the various tradelanes), but that's what I implemented.. XYZ Coordinates of objects and trade lanes are all in the files |
|
| Author: | Heliomance [ Wed 15 Feb 2012, 14:23 ] |
| Post subject: | Re: Routing data |
Is the info on how fast you can travel under each mode (standard, thrusters, cruise speed, trade lane) in the files as well? If so, where? |
|
| Author: | Wizou [ Wed 22 Feb 2012, 14:07 ] |
| Post subject: | Re: Routing data |
I ask for full engine speed & trade lane speeds in FL Companion settings so no, I was not able to find this info in the files. If I remember correctly, they could be found somewhere in the EXE file but it is not reliable. |
|
| Author: | Heliomance [ Tue 17 Apr 2012, 10:29 ] |
| Post subject: | Re: Routing data |
How on earth did you get the route calculating so fast? I've managed to pull the positions from the ini files, and build a matrix of paths within each system and the links between systems, but using that to calculate a complete shortest path graph takes far too much computation time. I'm running Floyd's algorithm on it to calculate the shortest path between each pair of objects, but it takes minutes every time it runs. |
|
| Author: | Wizou [ Tue 17 Apr 2012, 16:30 ] |
| Post subject: | Re: Routing data |
IIRC, my algorithm maintains for each waypoints (= stations & jump gates/holes) a list of the shortest distance to every other waypoints and the associated next waypoint to take to reach the final destination. It starts by filling, for each system, the shortest distance for in-system waypoints. Then for each jumpgates/holes, I also adjust the shortest distance / next waypoint associated with their matching gates/holes in other systems (taking the jump time in account) After that, it's a simple loop of propagating the shortest distances to other systems, by arbitrating over the various in-system possibilities and then adjusting again the matching gates/holes. That loops ends when no more arbitrage was required. It doesn't seem to me I was using some tricky algorithm, just a classic shortest distance propagation approach. |
|
| Page 1 of 1 | All times are UTC + 1 hour [ DST ] |
| Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |
|