Forums de Wizou

Pour discuter des programmes de Wizou
It is currently Fri 29 Mar 2024, 01:34

All times are UTC + 1 hour [ DST ]




Post new topic Reply to topic  [ 8 posts ] 
Author Message
 Post subject: Routing data
PostPosted: Thu 09 Feb 2012, 12:07 
Offline

Joined: Thu 09 Feb 2012, 11:27
Posts: 4
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!


Top
 Profile E-mail  
 
 Post subject: Re: Routing data
PostPosted: Sat 11 Feb 2012, 00:07 
Offline
Site Admin

Joined: Sat 06 Aug 2005, 16:35
Posts: 719
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.

_________________
Le site Web de Wizou: http://wizou.fr


Top
 Profile  
 
 Post subject: Re: Routing data
PostPosted: Mon 13 Feb 2012, 11:59 
Offline

Joined: Thu 09 Feb 2012, 11:27
Posts: 4
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.


Top
 Profile E-mail  
 
 Post subject: Re: Routing data
PostPosted: Tue 14 Feb 2012, 21:10 
Offline
Site Admin

Joined: Sat 06 Aug 2005, 16:35
Posts: 719
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

_________________
Le site Web de Wizou: http://wizou.fr


Top
 Profile  
 
 Post subject: Re: Routing data
PostPosted: Wed 15 Feb 2012, 14:23 
Offline

Joined: Thu 09 Feb 2012, 11:27
Posts: 4
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?


Top
 Profile E-mail  
 
 Post subject: Re: Routing data
PostPosted: Wed 22 Feb 2012, 14:07 
Offline
Site Admin

Joined: Sat 06 Aug 2005, 16:35
Posts: 719
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.

_________________
Le site Web de Wizou: http://wizou.fr


Top
 Profile  
 
 Post subject: Re: Routing data
PostPosted: Tue 17 Apr 2012, 10:29 
Offline

Joined: Thu 09 Feb 2012, 11:27
Posts: 4
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.


Top
 Profile E-mail  
 
 Post subject: Re: Routing data
PostPosted: Tue 17 Apr 2012, 16:30 
Offline
Site Admin

Joined: Sat 06 Aug 2005, 16:35
Posts: 719
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.

_________________
Le site Web de Wizou: http://wizou.fr


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 8 posts ] 

All times are UTC + 1 hour [ DST ]


Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group