+- Discovery Gaming Community (https://discoverygc.com/forums)
+-- Forum: Discovery Development (https://discoverygc.com/forums/forumdisplay.php?fid=7)
+--- Forum: Discovery Mod General Discussion (https://discoverygc.com/forums/forumdisplay.php?fid=37)
+--- Thread: Shortest path calculations and other data parsing (/showthread.php?tid=74459)
Shortest path calculations and other data parsing - Heliomance - 02-08-2012
I'm a third year maths student, and for my dissertation I decided to write a program that will calculate optimal trade circuits in Freelancer based on what planets and systems you have available, and what factions you're friendly with. This turns out to be a very interesting and complex algorithmic problem. The trouble is data entry.
I need shortest paths between every pair of bases in the game, to accurately calculate profit to time ratios for various routes. I've finished data entry for VanillaFL, but I did it by hand, using the star maps to eyeball distances between neighbouring bases then running a shortest path algorithm to get the rest. The process of manual data entry was tedious in the extreme, and I really don't want to go through it again.
The trouble is, while looking for the starmaps to work out the distances, I stumbled across the Discovery mod. The active userbase here means that my program will be a lot more useful and widely used if I adapt it for the new systems, trade routes, and suchlike in the mod. But I'm blowed if I'm going to go through and do it all by hand.
The game can already calculate shortest paths to fly from one base to another, so the functionality I need must be in the data files somewhere. The trouble is, I'm a complete newbie to modding, and I have no idea how to extract it. So, if anyone could tell me how to get the following information in a usefully parsable form, it would be very helpful.
Things I need to add Discovery functionality:
- Time of shortest paths between every pair of bases. Units don't matter, as long as they're consistent, but I would ideally like the option to choose whether or not to use trade lanes in the calculations. Also, I want to be able to route through jump holes.
- Commodity prices at every base, and which bases sell what
- For every base, a unique ID, the system it's in, and the faction it belongs to
- Preferably, information on what commodities are contraband in what places, but that won't make it into the first version
Hopefully this can all be pulled out of the data files somehow. If so, over the next year and a half I'll be developing the program for Vanilla and Discovery in tandem, and I'll let you all know how it goes!
Shortest path calculations and other data parsing - Echo 7-7 - 02-08-2012
Sorry to disappoint you, but a very similar program already exists. Google "Freelancer Companion".
There are certain points of data it can't handle, namely diplomacy, but you can manually exclude any given faction's bases from a trade route. It also doesn't handle the legal status of commodities, since those are subject to mod/server rules, but once again particular commodities can be excluded from calculations.
Importantly, the program reads the game files itself (rather than the data needing to be copied across manually), so that it can be used with nearly any Freelancer mod.
Shortest path calculations and other data parsing - Heliomance - 02-08-2012
' Wrote:Sorry to disappoint you, but a very similar program already exists. Google "Freelancer Companion".And the problem with competition is..?
There are certain points of data it can't handle, namely diplomacy, but you can manually exclude any given faction's bases from a trade route. It also doesn't handle the legal status of commodities, since those are subject to mod/server rules, but once again particular commodities can be excluded from calculations.
I'm currently on a uni computer, so I can't download it and see what functionality it has, but I'd be surprised if it was exactly the same as what I envisage. But the fact that a tool already exists in no way means I can't try and make a better one, nor does it mean I'm going to abandon my dissertation:P
Especially as my supervisor thinks I might eventually be able to get a publishable paper out of this - the problem as I've modelled it is not one that seems to ever have been studied before.
Shortest path calculations and other data parsing - Echo 7-7 - 02-08-2012
' Wrote:And the problem with competition is..?
Nothing at all.
I'll care to note that a compatibility issue exists, preventing Freelancer Companion v2.02 (the latest) from reading the Discovery Mod's game files, since some files are updated server-side post release of the latest Mod version in order to more carefully control the game's economy. Solving this problem could see your project garner a lot of interest. Companion v2.01, however, does not suffer from this issue.
Shortest path calculations and other data parsing - Heliomance - 02-08-2012
Having looked through the FLCompanion features, I'm pretty sure I was right about the comparative features. As far as I can tell, Companion, given a starting point, will show you various places you can sell the commodities from that point, and calculate the routes for it - it calculates a single leg from a buying point to a selling point.
That's a very easy calculation to do. With the data I've already got, I could probably write a program to do that for VanillaFL in less than an hour, a bit more to have it actually give you each stage of the route. Obviously it wouldn't be as full-featured as FLCompanion is at the moment - I have no idea how to generate the starmap to illustrate the route on, for example, and I don't have actual co-ordinates for the bases - but that's a programming challenge, not a mathematical one.
What I'm planning is to find an entire repeatable circuit, without a given starting point. You can tell it what bases you have access to, and it will find the best possible circuit maximising overall profit per unit time - accepting unprofitable legs if it means a greater overall profit. That's a much, much harder problem to solve in general - in maths jargon, it's a variant on the Travelling Salesman Problem, and is NP-hard.
From what I gather, Discovery has commodities that take up more than 1 inventory slot - that makes the problem even harder and more interesting, as it means the optimal cargo isn't necessarily to fill your hold with only one commodity on each leg. I plan on doing this for my Master's thesis as well, so it will be getting very advanced.
But I do need to be able to pull the data I need from the game files, especially if I'm going to try and tackle dynamic economy, and I have no idea how to do that. Any and all advice would be welcome!
Shortest path calculations and other data parsing - AeternusDoleo - 02-08-2012
' Wrote:
- Time of shortest paths between every pair of bases. Units don't matter, as long as they're consistent, but I would ideally like the option to choose whether or not to use trade lanes in the calculations. Also, I want to be able to route through jump holes.
Can't help you there. You can read out the location of lanes, bases and gates/holes from the various system files in /universe/systems/ but the algorithm you will want is yours. Bases have a base = BASENAME line to their object entry. Lanes have a previous and next lane, unless you have the start and end node. Anything with a "goto =" line in the object definition indicate a transition, usually to another system. How you measure distance is up to you.
- Commodity prices at every base, and which bases sell what
Read these out from the market_commodities.ini file in the \data\equipment folder
- For every base, a unique ID, the system it's in, and the faction it belongs to
Read these out from the universe.ini file in \data\universe. All bases have a short internal nickname, IE Li01_01_base means Liberty 01 (New York system), Base 01 (Planet Manhattan).
- Preferably, information on what commodities are contraband in what places, but that won't make it into the first version
discoverygc.com/wiki/ -> Commodities.
Shortest path calculations and other data parsing - Ursus - 02-08-2012
One thing FL Companion lacks is the ability to specify a destination and then list the commodities near me or on the way that will make decent profits. For example, I need to go to New Tokyo, I am in California now, what should I buy here or on the way that I can sell when I reach New Tokyo or some station along the way.
Also, on a wholly separate thing, the in-game navigation system is server-side, as are the player maps and base lists. I think the code that does the route calculations can be replaced with a plugin. We need a better one of those. Aeternus might be able to provide more information about the interfaces and stuff.
Shortest path calculations and other data parsing - Linkus - 02-08-2012
If you want to help code, help with FLHook.
It would be a far far more useful use of your time, at least in terms of benefit for the mod.
Plus we'd love you unconditionally =3
Shortest path calculations and other data parsing - Alex. - 02-08-2012
' Wrote:preventing Freelancer Companion v2.02 (the latest) from reading the Discovery Mod's game files, since some files are updated server-side post release of the latest Mod version in order to more carefully control the game's economy.The changes made by the server are done in memory, and are not saved to your files. Freelancer Companion reads from Discovery 4.86's (all beta releases so far) game files perfectly. v2.02's memory-reading feature is broken with 4.86 however.
' Wrote:But I do need to be able to pull the data I need from the game files, especially if I'm going to try and tackle dynamic economy, and I have no idea how to do that. Any and all advice would be welcome!Actually, the files are useless when dealing with dynamic economy.
Shortest path calculations and other data parsing - Heliomance - 02-08-2012
' Wrote:One thing FL Companion lacks is the ability to specify a destination and then list the commodities near me or on the way that will make decent profits. For example, I need to go to New Tokyo, I am in California now, what should I buy here or on the way that I can sell when I reach New Tokyo or some station along the way.That was a feature that I already planned to put in, I think I can do that with just the knowledge I already have.
Also, on a wholly separate thing, the in-game navigation system is server-side, as are the player maps and base lists. I think the code that does the route calculations can be replaced with a plugin. We need a better one of those. Aeternus might be able to provide more information about the interfaces and stuff.
And if the navigation system is server side, how does FLCompanion calculate its routes?
' Wrote:If you want to help code, help with FLHook.I'm not doing this to benefit the mod, I'm doing it because it's interesting and to get my degree. I'm trying to expand it to be compatible with the mod because it'll give it wider usage and application. Also I have no idea what FLHook is.
It would be a far far more useful use of your time, at least in terms of benefit for the mod.
Plus we'd love you unconditionally =3
' Wrote:The changes made by the server are done in memory, and are not saved to your files. Freelancer Companion reads from Discovery 4.86's (all beta releases so far) game files perfectly. v2.02's memory-reading feature is broken with 4.86 however.
Actually, the files are useless when dealing with dynamic economy.
Oh? How do you get at the info for the dynamic economy then? And won't that make anything based on it incompatible with any non-dynamic economy mod?