BETA Release - Factory Loop Delivery Software - v0.12

The place to discuss scripting and game modifications for X²: The Threat.

Moderators: Moderators for English X Forum, Scripting / Modding Moderators

User avatar
Burianek
Posts: 2981
Joined: Mon, 29. Dec 03, 03:29
x3tc

Post by Burianek » Sun, 24. Apr 05, 20:08

After you activate the script editor, you need to save and reload the game for the scripts to launch.
Cheers.
"Nature's first green is gold" . . . stay golden.

User avatar
Nystalux
Posts: 19
Joined: Sat, 29. Jan 05, 18:41
x2

Post by Nystalux » Sun, 24. Apr 05, 20:34

Of course! I did find out when i came to play again.


Many thanks.



Ny . . . . . :)

Mattrog
Posts: 58
Joined: Wed, 6. Nov 02, 20:31
x3

Post by Mattrog » Tue, 17. May 05, 12:26

Just a quick one:

If i put 2 Power Plants in a FLDS managed system will it deliver power from one plant to another if one is running low?

Mattrog
Posts: 58
Joined: Wed, 6. Nov 02, 20:31
x3

Post by Mattrog » Tue, 17. May 05, 14:08

Oh and just had another thought

I am thinking of seting up a few loops in the unknown sector east of wastelands ... If i linked them all on one fds system - could it cope with sorting out all of the routes without killing the rest of my game?

Looking at about 60 facts:

6 x Power
6 x Crystal Fabs
11 x Raster Refinerys
11 x Chelt Aquariums
7 x Silicon mines
8 x Ore mines
4 x GPPC Forges
1 x LazerTower Forge
ish ...

Aye Capn
Posts: 2611
Joined: Sat, 15. Feb 03, 07:17
x3tc

Post by Aye Capn » Thu, 26. May 05, 06:24

Hey, I love FLDS, enough to reluctantly return to the forum, in fact, but there is one issue it seems to deal poorly with: multiple sources.

Say I have an array of silicon mines of varying yields which I want to bind into a seamless flow of silicon (like say I wanted to serve 6 factories with Silicon mines yielding 64, 30, 30, and 26).

If I assign all 4 mines to all 6 factories FLDS will only grab silicon from the first mine, so long as any factory is "critical". The delivery ship will waste all its time moving 6 wafers at a time from the first mine in its list while massive stocks of unused silicon build up in the remaining 3. Assigning additional ships doesn't really help, because the problem is in the route-priority algorithm.

Speaking of that, I looked at your code and found the problem: the need at the destination is the sole basis for the priority calculation. Supply is not included in the base priority calculation at all (small loads get a veto, but that only tangentially addresses the source inventory issue, and even that veto gets overruled if a destination goes critical.)

All other things being equal, a 100-unit delivery of a ware is preferable to a 6-unit delivery. The priority calculator should take this into account.

I'm actually wondering whether basing the priority ENTIRELY on load size (as a percentage of destination capacity) wouldn't be the best algorithm. It would certainly be simple.

Speaking of simple, I absolutely LOVE your interface! It is a model of extensibility: to add a station to a delivery route, add it to the hub. To add a ship (or replace a destroyed ship), assign a homebase and give one command. Awesome design!

If FLDS handled multiple source issues elegantly I wouldn't have to make every single silicon mine a hub, and that would make FLDS even better! ;)

sacq
Posts: 5
Joined: Wed, 6. Nov 02, 20:31
x4

Post by sacq » Thu, 26. May 05, 22:34

Any chance this script will ever be signed?

Cheers,

sacq

Aye Capn
Posts: 2611
Joined: Sat, 15. Feb 03, 07:17
x3tc

Post by Aye Capn » Fri, 27. May 05, 00:44

I've been doing some more thinking (that's what that burning smell is, if you were wondering).

"Need" is indeed a top priority. It doesn't matter if I can move a full load of unneeded ecells when what I really need to move is half a load of wheat.

"Supply" is a necessary secondary priority -- a 100 silicon wafer transfer is preferable to 6.

What if ... your "Need" priority were calculated as "percentage empty" * 10^3 and your "Supply" priority were added in?

Let's say you had a factory that was out of silicon, and 3 silicon mines to choose from. None of the other fabs in the loop are out of silicon, so the only "100 * 10^3" priority is the empty factory:

100xxx <-- 100,000+ anything gets top priority

Your 3 silicon mines are at 2%, 25%, and 34% capacity. Their route ratings are thus:

100002
100025
100034

An SP in the loop has maxxed out, 100%, but the station that needs energy the most is only 60% empty:

60100 <-- 60,100 is less than 100,034

The smaller load of more-needed silicon is chosen over the larger load of less-critical energy cells.

So why not just break "source" into a separate step? Because integrating it into the priority calculation breaks a tie between different equally-needed goods. (It also makes the code more efficient.)

Take the case of a brand new crystal fab attached to the network:

100085 <-- rating for an ecell route
100080 <-- another ecell route
100030 <-- best rating for silicon
100002 <-- best rating for steak
100013 <-- another silicon route

In this case, 100085, the ecell route, is chosen, because it will fill a need AND move the most stock. It incidentally also picks ecells from the power plant that has the most, keeping it from filling up and shutting down.

The second trip will move the silicon.

By the third trip a few more steaks will be available, maybe double the original 2%, so the food run, by being delayed, becomes twice as efficient.

If the source is empty the route should be rejected: a 100000 priority route is, err, "overstated in value" to put it mildly. (This is already in your code.)

"Critical" might be best defined as 90% or more empty, so that a large shipment to an almost-empty factory is chosen over a tiny shipment to a truly empty one. In fact it may be best to "quantize" the entire demand domain in that way so that a large load in the 20-30% range is chosen over a tiny load at 22% versus a large one at 26%.

Hmm ... you could accomplish that by a smaller "weight factor" on the demand side. "Need * 12 + Supply" might be better than the adamantly inflexible "Need * 100 + Supply". That being the simplest solution I like it best.

Aye Capn
Posts: 2611
Joined: Sat, 15. Feb 03, 07:17
x3tc

Post by Aye Capn » Fri, 27. May 05, 11:05

I just made my first script edit, to FLDS.Main, and it seems to have worked out. FLDS will now load-balance multiple sources.

The line of code I changed was this:

223 $Route.Priority = $Route.Needed.Amount * 10000 / $Route.Priority

to this:

223 $Route.Priority = ($Route.Needed.Amount * 12 + $Route.Pickup.Amount) * 769 / $Route.Priority

The result on my test loop (SP, QT loop, Crystal loop, silicon imported) was encouraging. The transport always picked the source with the largest inventory and usually chose the destination with greatest need, unless it could make a much larger haul somewhere else.

It also made more ecell runs, which is important: no number of marginal runs of small quantities of steak will ever alleviate the endemic shortage, as steak is produced at the same rate it is consumed. It will always be in shortage. The transport ought not spend all its time hanging around the bakery moving miniscule cargoes of steak.

Using "$Route.Pickup.Amount", the quantity of wares to be picked up, isn't exactly the same thing as using the quantity of wares available at the source. Take the case of an SPP with 3000 ecells versus another with 4000. Since both will max $Route.Pickup.Amount to the TS' cargo bay, the 4000 inventory source isn't weighted any more heavily than the 3000, although it should be.

"$Route.Needed.Amount" just happened to be the low-hanging fruit. I'm lazy.

I'm also thinking maybe 12-1 still overly favors "need". A 4-1 bias would favor larger hauls even more. Heck, even equal weight might be best. The priority of an empty fab would exactly equal the priority of a full-size cargo run, so that even a little bit of available inventory of the needed item would tip the scales in favor of the needy factory -- assuming some other factory wasn't in dire need of the more plentiful resource.

Incidentally, to preserve Naz's 10000 scaling factor (needed because we're dealing with long integers, I assume?) divide 10000 by 1 + the "need bias" coefficient. For my bias of 12 I divided 10000 by 13 to get 769. For a 4-1 bias use 10000 / 5 = 2000.

I think I'm going to give the even bias a try, and see if I get more ecell runs without short-changing the food factories.

Aye Capn
Posts: 2611
Joined: Sat, 15. Feb 03, 07:17
x3tc

Post by Aye Capn » Sat, 28. May 05, 00:35

There's a problem with using $Route.Pickup.Amount ... to paraphrase Inigo Montoya, "I don't think it means what I think it means."

It seems to include volume, which really skews the priorities in favor of high-volume cargoes, or it would if the "need" factor were toned down (I only unmasked the error by making the two priorities even.)

I'll fix it, of course, but I've noticed something else about FLDS that seems troubling.

Ships running FLDS seem to spend a lot of time blocking on the critical section flag. Furthermore, the more ships you add, the more blocking takes place, regardless of what hub the FLDS ships serve. The more you use FLDS, the less efficient it becomes.

This seems to be global across all "hubs", that is, the critical section flag blocks ANY ship from ANY hub from looking for delivery routes. This would seem to be necessary to allow overlapping hubs, but it also means a ship running FLDS on one side of the galaxy can block dozens of ships on the other.

I've been thinking of a way to fix this. Critical sections are supposed to be short. I think I have a solution.

Keep a list of routes in a global array, a "job board".

Run a route-finding algorithm more-or-less continuously at the producing stations. Each producing station is responsible for posting its best send routes -- with attached priority -- to the job board. Route-finding does NOT get flagged as a critical section.

Ships only flag critical section when they scan for a job or update their job's status.

Producing stations only flag critical section when they update the job board.

Producing stations only keep as many entries on the job board per hub as there are ships running on that hub.

When a ship accepts a job, no other ship may take it. The station that "owns" the job may revise the job as part of its normal "job-posting" algorithm any time up until the ship picks up the cargo.

In my next post I'll give an example of how this scheme would work.

Aye Capn
Posts: 2611
Joined: Sat, 15. Feb 03, 07:17
x3tc

Post by Aye Capn » Sat, 28. May 05, 02:03

How It Might Work

Powering our factory complex we have 3 Crystal Fabs serving 2 SPP's. We'll call the 2 SP complexes Loop 0 and Loop 1 and the third Crystal Fab complex "X".

Our goal for one of our FLDS loops is to move crystals more-or-less evenly from the crystal fabs more-or-less evenly into the SPP's. We set up an FLDS loop to all 5 and assign a couple of freighters.

We would also like the freighters to handle support for the crystal fabs, except for silicon which is coming in from a separate load-balanced FLDS loop. We therefore add the steak and beef plants to the Crystal FLDS loop.

Total stations: 2 SP, 3 Crys, 3 Steak, 3 Beef

We're feeling lucky and think we can run the whole works on 2 freighters.

Our job board is going to be pretty large, so let's focus in on two contributors to the job board, SP 2 and Cahoona Bakery 1.

SP 2 has been quietly running its route-finder on its 9 possible routes for the past 5 minutes and is ready to post to the job board. It locks the job board and puts up 2 jobs -- one for each ship -- then unlocks the board.

There are a lot of competing jobs, but Crys Fab X was just installed and is running low on energy, so that job has a pretty high priority.

Cahoona Bakery 1 has been building up stock because the TL was late installing Crystal Fab X. It's jobs have been dropping in priority because the other Crystal Fabs are filling up from all the extra steak brought in from Cahoona Bakery X. CB1, however, happens to be the first to "notice" Crys X and along with another low-priority job posts a very high-priority job to the job board.

Freighter 0 just finished a job and locks the job board to find another. It picks the highest-priority job -- a full load of ecells from SP 2 to Crys X -- and flags it. The source and destinaton stations note the accrued inventory adjustments in local variables to make new route-finding calculations update properly. The freighter unlocks the job board and heads toward SP 2.

Freighter 1 does the same thing moments later (after a brief wait for the job board to unlock.) It takes up CB1's steak to Crys X route.

The only problem I see is one we've intentionally caused, a tradeoff to ease the pressure on the critical section flag: stale routes. But that's not as bad as it sounds, as they wouldn't be on the job board but in the individual stations' route-finding algorithms.

Since a job would be "verified" after locking the job board and before posting, the stale, incorrect "high priority" job info would get revised downward to a really lame low-priority job just as it posted to the job board. The actual "highest-priority" job from that station won't get posted until the next cycle of its route-finder.

If in our example CB2's route finder was going nuts over the CrysX delivery, its recalculation at the job board given CB1's claiming of the job revises its priority way downward, so that some other steak delivery might have been a better choice. We won't know until CB2's route-finder completes another cycle.

A final difficulty ... the route-finder algorithm might be the equivalent of line 1 of Elmer Fudd's simple recipe for rabbit stew -- "catch a rabbit". It's going to have to handle somewhat inobvious arcana such as treating changes to its inventory-accrual variables as a "restart calculations" semaphore.

Phew. My head hurts. What do you guys think? Is the "job board" method of minimizing critical section blocks a basically sound idea? Or is it one of those things that sounds simple but is in reality nigh impossible?

Aye Capn
Posts: 2611
Joined: Sat, 15. Feb 03, 07:17
x3tc

Post by Aye Capn » Sat, 28. May 05, 09:13

This is nuts: ASDS seems to strictly favor larger* loads first, followed by need only to break a tie. (Need indirectly becomes a factor when the destination fills up and the load size of that route is forced to shrink.)

Totally the opposite of FLDS.

I'm going to finish fixing FLDS to give both sides equal priority, and see how it works out. I suspect Ticaki knows something about this that I don't. ;)


* "Larger" and "smaller" in the context of cargo size means "as a proportion of the factory's total warehouse capacity", so transferring a tiny cargo of swamp plants which represent 40% of a Dream Farm's warehouse capacity is valued the same as a gigantic 40% cargo of majaglit from a jewelry factory.

User avatar
TSM
Not a Moderator
Posts: 2947
Joined: Thu, 1. Jul 04, 12:31
x4

Post by TSM » Sat, 28. May 05, 12:04

I assume you have actually contacted the Author of this script rather than just pull it to pieces on an open Forum?
FAQ's Egosoft Interactive FAQ
Egosoft Wiki

Aye Capn
Posts: 2611
Joined: Sat, 15. Feb 03, 07:17
x3tc

Post by Aye Capn » Sat, 28. May 05, 19:52

"Comments and bug reports are very very welcome."
-- Nazgutek

Aye Capn
Posts: 2611
Joined: Sat, 15. Feb 03, 07:17
x3tc

Post by Aye Capn » Sat, 28. May 05, 20:29

I do wish he were here, as he could tell me what the consequences would be of taking out the critical section flag entirely.

ASDS doesn't appear to use critical sections at all, and I remember from the "Atomic Coding" chapter of the MSCI Handbook that task-switching only takes place at task-switching points (marked "@").

That's a lot like a critical section.

Maybe FLDS could take advantage of that? Maybe not. Only Nazgutek could really know for sure.

Aye Capn
Posts: 2611
Joined: Sat, 15. Feb 03, 07:17
x3tc

Post by Aye Capn » Sun, 29. May 05, 09:27

The original fix I posted was correct. The odd behavior was a result of me misconfiguring my test bed.

Oops. :P

There is a problem with the original fix which I haven't "proven" in live testing but which is real: not all stations have the same inventory capacity for a given ware, so you can't add source and destination quantities and divide once.

You need two seperate divisions to build two separate ratings, then you can average (or bias) them and be comparing "apples to apples".

The variable "$Temp.Source.Amount.Maximum" just happens to have what I need and "$Temp.Ship.Amount.Free" is safe to use here as a temporary variable:

222 $Temp.Ship.Amount.Free = $Route.Delivery.Amount * 10000 / Temp.Source.Amount.Maximum
223 $Route.Priority = $Route.Destination -> get max amount of ware $Route.Ware that can be stored in cargo bay
224 $Route.Priority = $Route.Needed.Amount * 10000 / $Route.Priority
225 $Route.Priority = ( $Temp.Ship.Amount.Free + $Route.Priority ) / 2

This handles the case in which the destination is a high-end factory with extra large inventory capacity.

I also changed to "delivery amount" instead of "pickup amount" because we want to get rid of cargo already in the cargo bay.

Aye Capn
Posts: 2611
Joined: Sat, 15. Feb 03, 07:17
x3tc

Post by Aye Capn » Mon, 30. May 05, 20:37

Ok, I have it! The perfected, flight-tested FLDS delivery priority formula!

New Delivery Rules:

1. Full sources and empty destinations have equal priority.
2. Full destinations (defined as less than the lesser of source inventory and a full ship cargo bay) revise the source priority down to the actual amount that can be delivered. (The original source inventory is still factored in so that even a route with a clipped source priority will pick the source with the largest inventory.)

Preserved Original Delivery Rules:

3. Transport docked at source gives route double priority.
4. Small loads of wares not in critical shortage are rejected.

Critical Section Tweaks (unwarranted paranoia officially cured):

1. Critical section check delay INCREASED to 1.2 seconds. Checking it 10 times per second spams the debugger log and needlessly burns CPU cycles. The ship's just sitting in port, anyway. A lazy check isn't going to kill anyone.

2. Between-job delay cut to 2 seconds. This compensates for the increased critical section delay. If we're going to wait it might as well be with an eye on the critical section flag.

***

On the topic of the critical section flag, the 100 ms delay was spamming the debugger log mercilessly, making it appear as if critical section blocking were a horrendous problem. It might become a problem if you had hundreds of ships running FLDS, but I'm fairly convinced I was making a big deal out of nothing.

The changes I made will cause less CPU time to be eaten up checking the critical section flag and eliminate the long delay between jobs, anticipating the "hundreds of ships" scenario in which 10 critical section blocks puts you at 14 seconds of total delay even with the shortened 2 second between-job delay.

***

The new priority scheme isn't perfect, but it's close. For instance, ideally highest priority should automatically go to the most-needed route which fills the ship's cargobay.

However ... the "equal priority to source stock and destination need" formula seems to mostly nail it. I've set up a large loop to push a single freighter to its limit, and it almost always makes smart choices about which cargo to move.

More importantly, a frieghter will more-or-less balance its efficiency to the demand placed on it. We actually want this, as freighter efficiency, which sounds good, is actually a tradeoff with inventory stockpile size.

What you'll notice in practice is that the harder you push your FLDS frieghters, the more "intermediate resources" will build up before delivery. This causes the end-stage fabs to shut down at first. That's the price you pay for using fewer ships.

Now ... about the revision code ... there are a lot of changes, so I'll post them in the next message. I won't distribute files -- only Nazgutek can do that -- but I've PM'd him with the message "come over here and check things out", so maybe we'll get word from the original author soon on whether or not he likes my proposed changes.
Last edited by Aye Capn on Mon, 30. May 05, 22:23, edited 2 times in total.

Aye Capn
Posts: 2611
Joined: Sat, 15. Feb 03, 07:17
x3tc

Post by Aye Capn » Mon, 30. May 05, 22:13

The code revisions:

File "plugin.FLDS.Ship.Start.xml"
Change 072:

Code: Select all

072 @ = wait 2000 ms
File "plugin.FLDS.Ship.Main.xml"
Change 067:

Code: Select all

067 @ = wait 1200 ms
REPLACE lines 222-223 with the following:

Code: Select all

222 $Route.Priority = 0
223 $Temp.Ship.Amount.Free = $Route.Available.Amount
224 $Temp.Destination.Amount.Product = $Temp.Ship.Amount.Maximum
225 skip if $Temp.Ship.Amount.Maximum < $Route.Available.Amount
226  $Temp.Destination.Amount.Product = $Route.Available.Amount
227 if $Route.Needed.Amount < $Temp.Destination.Amount.Product
228  $Temp.Ship.Amount.Free = $Route.Needed.Amount
229  $Route.Priority = $Route.Available.Amount * 20 / $Temp.Source.Amount.Maximum
230 end
231 $Temp.Ship.Amount.Free = 10000 * $Temp.Ship.Amount.Free / $Temp.Source.Amount.Maximum
232 $Route.Priority = $Route.Priority + $Temp.Ship.Amount.Free
233 $Temp.Destination.Amount.Product = $Route.Destination -> get max amount of ware $Route.Ware that can be stored in cargo bay
234 $Temp.Ship.Amount.Free = 10000 * $Route.Needed.Amount / $Temp.Destination.Amount.Product
235 $Route.Priority = $Route.Priority + $Temp.Ship.Amount.Free
The variable names I used for temporary calculations are confusing and not self-descriptive. I did this so as to keep the changes as minimal as possible, including not declaring extra variables.

Aye Capn
Posts: 2611
Joined: Sat, 15. Feb 03, 07:17
x3tc

Post by Aye Capn » Tue, 31. May 05, 04:04

Well you knew I couldn't leave it alone for long.

More tweaks:

1. Lowered the "bad job" threshold to 7000, based on no solid theory other than a gut feel for when my silicon distribution ships should move. 7000 seemed about right.

Code: Select all

216 $Temp.Critical.Limit = 7000
2. Added a 45s shutdown if no job was "good enough" to run. This saves CPU cycles and critical section usage.

Code: Select all

425 else if $Highest.Index < 0
426 @  = wait 45000 ms
That last bit doesn't have enough context. There's an error "if" block right at the end of the delivery module, and that "else if" tacks onto the end of the error "if" block: "[if error ...] else if no work was done, wait 45s". "$Highest.Index" is -1 if no suitable route was found.

I put the code for the 45s wait at the tail end of the function in case Nazgutek wanted to make a "No Suitable Route Found" return value to the command dispatcher module which would in turn handle the delay. That's where the between-job delay is, so it seems natural to have the "no job" delay there as well.

Nath
Posts: 14
Joined: Sat, 31. Jul 04, 22:24
x2

Post by Nath » Sat, 4. Jun 05, 20:44

I've been using this script for awhile now, and one ship per loop makes me very happy :D

Thanks for taking it upon yourself to improve it :)

Aye Capn
Posts: 2611
Joined: Sat, 15. Feb 03, 07:17
x3tc

Post by Aye Capn » Sun, 5. Jun 05, 06:54

No problem. Since I had never seen a line of MSCI code before FLDS Nazgutek's verbose style was a huge benefit.

I actually downloaded FLDS to solve a specific problem with high-yield silicon mines that SDS could only solve with a massive complex of overlapping orders.

FLDS should have solved that problem easily, but strangely it didn't, so I picked at it until it did. The "load balancing" algorithm isn't primarily a tweak to save on ships. It solves a specific problem.

I'm going to make one more change to FLDS: add rejection of invalid cargoes so I can make FLDS work with TP's. I want my Argon Express!

I wish Nazgutek were here. He seems to have left the X2 scripting scene, or at least taken an extended vacation.

Post Reply

Return to “X²: The Threat - Scripts and Modding”