Aye Capn wrote:
CRITICAL SECTION
This one's a killer. Only one ship in the universe can run FLDS route-finder at a time, so any delay within a critical section will eventually bottleneck the whole system. It doesn't help that task-switching in MSCI is the equivalent of breaking for a 2-martini lunch.
Indeed, technically, the Critical Section is a bottleneck. However, it will bottleneck when the flight time of a ship performing a shipment exceeds the total amount of time every other ship spends processing route information. Before that point is reached, ships will collide on the CS, but not in a bottleneck scenario. Or at least, going from the top of my head (still not had a chance to review source), that's the intent at least.
1. Run the route-finder in "atomic time" and limit the number of linked stations to 20, that's 20^2 = 400 stations to check for routes before giving up a time slice (yes, that means you're the one taking the 2-martini lunch). This is in fact how I modified FLDS (except I didn't put a station limit in).
One nice idea. You'd have to ensure that when a given instance of FLDS re-enters on a new timeslice that it interrogates all the stations to update available and needed amounts, but workable for sure.
It is possible to move some chunks of the big critical section outside by breaking it into separate steps. For instance, the defining of routes isn't critical until they're quantified, so you could build your route array with well-behaved waits then in the atomic section load the array with actual quantities. (There are also fewer routes than the #/stations squared, so a good chunk of work is cleared away by this point.)
Now that's a great idea. A lot of grunt work is done by doing a N^2 search through the list of linked stations at a hub, and breaking into two stages works. The first stage can identify possible routes (where a route is defined, as you know, as a journey between a station that produces and a station that needs a specific resource) without grabbing available and needed amounts, and this means it can go outside the critical section. Then inside the critical section, we can go through the routes we found, grab the amounts, perform our checks and comparisons, decide on a route and exit the critical section.
I like it!
2. Run the route-finder continuously, like NASA plots telemmetry, and update results to a "job board" for the transports to pick from. The route-finders, one per hub, could run slowly and hold critical sections against other route-finders as needed, but the job board would never be locked. (Any job board updates would be atomic.)
Another workable idea. It would require a paradigm shift away from the ships back to the hub, but there's no reason why we couldn't have a 'manager' running on a Hub who maintains a list of necessary and efficient shipments. All the critical section would need to do is to lock access to the list whilst the manager updates or whilst a ship accepts a job.
3. Devise some other route-finding algorithm robust enough that it works most of the time without needing critical sections or an over-large block of "atomic code". A scheme using local variables at stations to create a virtual inventory might do the trick, although I'm strictly guessing here. ASDS doesn't use critical sections, but I don't know how well it actually performs.
With multiple ships, some sort of critical section is needed. One ship could be working out which route to take whilst "at the same time" another ship could accept a job. FLDS tracks current jobs, and jobs that are taken but en-route are figured into the available and needed amounts at stations.
The big problem in your route priority is that it doesn't take source inventory into account in the scoring algorithm. That's even true if one of two routes moves less cargo, unless the lesser route is so bad it gets vetoed and the veto wasn't overridden by the "critical shortage" exception.
I'm not a AI programmer, as the route prority rating system shows! There's definitely room for improvement, and taking into account source inventory is one aspect I didn't have time to fully account for. I decided on a simple 'veto' scheme just so I would have a script that worked. Using a weighted score which accounts for source inventory is definitely a way forward.
Another issue to be aware of is for routes that require pickup at the station where the ship is currently docked. These pickups save a lot of time because only one flight is needed to complete the shipment, not two. This starts to add complexity into the rating system, as does accounting for the current cargo on the ship.
I have my own theory about the "flashing yellow critical shortage problem". Consider this in the spirit of the Laws of Thermodynamics:
1. A maximally efficient freighter would make every trip fully loaded.
2. A minimal buildup of inventory requires constant shipping of tiny cargoes the moment they become available.
3. More efficient use of fewer freighters requires larger inventories; keeping smaller inventories requires more freighters carry smaller loads.
4. Buildup of inventory, necessary to run fewer freighters more efficiently, takes time, and it is this span of time that shows up as a blinking yellow factory.
5. Assuming sufficient overall transport capacity, a factory blinking yellow is normal, a sign that freighter efficiency has not yet reached equilibrium with transport requirements.
FLDS should ideally balance the competing goals of maximum efficiency and minimum inventory, increasing efficiency only as needed to offset increased demand. That's why I chose the balanced priority (full source and empty destination equal).
Well, FLDS considers a stalled factory as bad, hence that "critically low" formula. As MSCI doesn't have an easy way to obtain resources needed per cycle, I plumped for the 5% figure, up to 50% for factories that only stock 2 final products (I'm quietly chuffed with that little formula, in a few lines it knows if a factory is stalled, with some overflow for large volume producers which doesn't matter too much).
Once we've got all our factories running and not "critical", FLDS just moves stuff around based on need and efficiency. Again, it's a system that should take into account all the factors (need, supply, distance, ship capacity, danger and flashing-yellow-ness) but I didn't have time to come up with a numerical score that accounts for everything. Hence the rather simple priority system with the second-pass veto on crap shipments.
Really, how routes are rated and ordered is an AI task and is pretty hard to nail down in what I call "normal logic". As long as a set of rules result in FLDS being sensible, keeping things running and not making bad decisions (which is slightly different to "making good decisions"), then it works. But the way I see things, if a factory flashes yellow, we've lost possible production time. And as a player sets up factories to produce stuff, lost production time, in my eyes, is the absolute worst-case that we aim to avoid.
Final idea on this: I'm actually tempted, when I get the chance after incorporating suggestions and changes already mentioned (with permission of course), to move the whole rating system out of the main script into a separate script. That way, we can have any number of rating systems present, and a simple rename of the script (eg from "plugin.FLDS.Route.Rating.AyeCapt" to "plugin.FLDS.Route.Rating") will allow a user to swap between them at will. And with the typical dependency snafu, script calls are interrupt points, so we'll need critical sectioning still (I think).
Whatever changes I made consider yours. Feel free to use the modified "FLDS" and the modifications within in any way you wish. Let me know when / if you want DeadlyDA to take down his link.
Oh, and welcome back!
Ultimately, I designed FLDS to take all the setup pain out of player run factory loops. I think it succeeded. Yes, I admit it gets a bit ropey in certain situations, but as long as FLDS doesn't die, I'm happy.
Now, my time is limited these days, so I can't guarantee being able to update it. But, I don't mind others hosting it, or making changes and releasing those.
As a suggestion, those who make changes could clearly identify new versions. For now, I'll "own" the normal version number progression, but feel to spawn a new version number tree (eg, FLDS v0.13-AC) that clearly identifies in some way your versions from mine and others'. And when I get time, with your permission I can try to incorporate changes in other version trees into my version.
Ultimately though, I'm happy that people have shown this much interest in FLDS. Quietly proud, almost
)
