Automatic Pumpjack Beacon Placement

[Lindor]

I am personally the kind of player that would place 20 more beacons if it resulted in +1oil/second, even if i don't need it

[Xcone]

On the other hand, it is not a great player experience to have to think of a good threshold for each different fluid. It would be nice if there were a simple metric we could use which was independent of the fluid being pumped.

And of course there's the extra complication of the pumpjacks on Aquilo which can fully exhaust their resource patches, rather than diminishing to some minimum flow rate. Should they be handled differently?

Yea, .. Aquilo with its litium and heatpipes .. pain in the a##

I believe there's the aspect of modding the game away. It's one thing to provide tooling to take away tedium. It's another if the player doesn't even have the consider things anymore. I think for this reason I'd safely consider only current production, and not depletion production. Also keeping in mind there's a lot of mods out there that add additional resources. Having to figure out for each if they deplete or not. And then there's also mods that track resource depletion. So people can use that to get notified to re-plan their oil fields after a while.

But this is of course very much personal opinion area.

I am personally the kind of player that would place 20 more beacons if it resulted in +1oil/second, even if i don't need it

Thanks for clearing that up!
Yea, this whole conundrum might be more interesting to solve when taking that approach.

Additional question; you as an oil-squeezer .. would you re-plan your oil field later on; or go straight for depletion rates as not to have to worry about it anymore?

[Lindor]

If you want this for a mod (or added to an existing one); calculating all possible layouts, then comparing them, from within the game, .. that's just unacceptably slow. It'd freeze the game completely. Unless you separate all the math in batches and run it as some sort of spread out routine (for instance, calculate 1 or 2 possible layouts per in-game frame). But then the process would take unbearably long. That's not a good player experience.

I agree, but for different reasons than you might think.

I think you're underestimating the calculation intensity of the greedy approach. The binary tree approach is both faster and more reliable since it has been proven that it always finds the best solution. And it's also better in memory complexity.

The reason to choose greedy over binary tree is because we can limit the number of iterations at the cost of sacrificing accuracy.

I might be able to improve greedy further and make it more comparable in time complexity with binary tree. A lookup table for already calculated scores might be able to achieve that. But i'm not completely sure.

However i still think that for the audience of factorio it would make sense to at least give them the option to use the binary tree algorithm to calculate the optimal result. We could let it calculate in the background using coroutines. I can also provide some sort of progress bar data. We'd just need to make sure to be able to save the calculation state in-between game sessions.
I myself would want to use that feature.

On the other hand, it is not a great player experience to have to think of a good threshold for each different fluid. It would be nice if there were a simple metric we could use which was independent of the fluid being pumped

Maybe when the amount of electricity it would consume to place another beacon outgrows the amount of electricity you would gain by burning all the additional oil/second?

Additional question; you as an oil-squeezer .. would you re-plan your oil field later on; or go straight for depletion rates as not to have to worry about it anymore?

Excellent Question
I would go straight to optimize for the minimum / lategame.

Unless i'd be playing with that mod that lets you automize laying down blueprints. Maybe i'd use logic then to automatically update the blueprint once it's depleted.

And of course there's the extra complication of the pumpjacks on Aquilo which can fully exhaust their resource patches, rather than diminishing to some minimum flow rate. Should they be handled differently?

Yes. If there is no minimum, we can only optimize for the maximum.

[Xcone]

I think you're underestimating the calculation intensity of the greedy approach. The binary tree approach is both faster and more reliable since it has been proven that it always finds the best solution. And it's also better in memory complexity.

I am not sure what to make of that. I thought you were having problems with the speed of it?
My routine currently takes milliseconds instead of seconds. So I am not entirely sure what I am underestimating?
I am also unsure what you are referring to with `binary tree approach`.

... (your post with code)

I haven't checked your code earlier. I don't do well with other people's code usually. But just had a peek, and I think the base premise between your code and mine isn't even that different. So it might just boil down to a difference in understanding the meaning of `greedy`. I too compute beacon coverage for each spot and put it in a lookup table. And then compare the positions which has the most affected pumps.

Code: Select all

local score = #(self.affectedPumpjacks)

Where they differ is that that's good enough for me (being greedy), while you do 1 line of extra code (to keep away from being too greedy):

Code: Select all

score = score - beacon.score(seen)

However, that one line is a very expensive one, as it adds sooo many additional iterations. (as you already addressed in the post after you posted your updated code).
So no, .. I believe I am not not underestimating the calculation intensity (or lack thereof) of taking the greedy approach.

I am still figuring out the dynamics of `seen` and `ignore`; and wonder if they are essential to repeat every time (recursively), or can be computed once.
So if for each beacon position you could check which other positions are in range and sum the affected pumps of all of them and use that as some sort of penalty for that position. But I think you explained earlier that's not possible. So I need to read that bit again.
Maybe once you pick a beacon position, iterate all positions in range again, and reduce their penalty by the number of pumps the new beacon affects.

Interestingly; I don't see any code that reflects the yield of the pumpjack is taking into account. Am I missing something?

However i still think that for the audience of Factorio it would make sense to at least give them the option to use the binary tree algorithm to calculate the optimal result.

I do agree that audience probably exists within the Factorio community. But I can't be sure how sizable it is. Based on the kind of feedback I've received on my mod over the years, I don't think they're using my mod.

We could let it calculate in the background using coroutines. I can also provide some sort of progress bar data. We'd just need to make sure to be able to save the calculation state in-between game sessions.

Factorio's Lua is modified, and doesn't support lua-native coroutines. I've looked at that before.
Instead you need to mimic it by storing state, and subscribing to an event that triggers every frame. You can peek at https://mods.factorio.com/mod/Constructron-Continued for an example of that. I know they did something similar.

Alternatively, you could consider not making it a mod at all. There's also this site: https://factorio-tools.vercel.app/oil-field which works with copy/pasting blueprint data. In fact, that website might already have the solution you looking for. It claims to try a layout with various algorithms and picks the best one between them for that specific request.

Maybe when the amount of electricity it would consume to place another beacon outgrows the amount of electricity you would gain by burning all the additional oil/second?

That wouldn't work with sulfuric acid, lithium brine and fluoride. And the various other modded resources. I've done some reading about how the yield is calculated and what it means. And that percentage should be just fine to keep using, as it already represents the amount of oil (or other liquid). See: viewtopic.php?p=574243#p574243

Additional question:
Have you considered the output pipes
I notice your code doesn't do anything with pipes. So all the perfect layouts you're currently computing are not representative, since they have no means of carrying liquids outside of the field.
What's your expectation with those? Because I am very confident that where the pipes are, also affect where the beacons can be.
It seems a shame to figure out near-perfect beacon coverage, only to learn that had the pipes been put down differently you could put down even more beacons. But the pipe routine is a much bigger @#$%^ then the beacon routine, and I'm not really getting excited by the prospect of having to rework it for a few drops of oil.

[Lindor]

I am also unsure what you are referring to with `binary tree approach`.

I mean the approach to check every possible layout.
I call it the "binary tree" approach because that's what it builds. For every possible beacon to place, the final result either has this beacon placed or it doesn't. So it makes two copies, one where it places the beacon and one where it doesn't. Then repeat for each copy.

I am not sure what to make of that. I thought you were having problems with the speed of it?
My routine currently takes milliseconds instead of seconds. So I am not entirely sure what I am underestimating?

Well, there's the "correct" greedy approach, there's the "intermediate" and there's the "lazy" greedy approach.
The "correct" greedy approach with an unlimited number of iterations is extremely slow.
The "intermediate" greedy approach with a limited number of iterations is a balance between speed and accuracy.
The "lazy" greedy approach where we ignore beacon blockage is extremely fast and inaccurate.

When you wrote that case 1 is off the table and we should focus on case 2, i basically read that as "greedy is always faster than binary tree". But the "correct" greedy approach is very very much slower than the binary tree approach. That is what i wanted to express.
But i may have misunderstood you.

I haven't checked your code earlier. I don't do well with other people's code usually. But just had a peek

That's awesome!

Where they differ is that that's good enough for me (being greedy), while you do 1 line of extra code (to keep away from being too greedy):

Code: Select all

score = score - beacon.score(seen)

However, that one line is a very expensive one, as it adds sooo many additional iterations. (as you already addressed in the post after you posted your

Yep

So no, .. I believe I am not not underestimating the calculation intensity (or lack thereof) of taking the greedy approach.

Okay, i'm sorry

I am still figuring out the dynamics of `seen` and `ignore`; and wonder if they are essential to repeat every time (recursively), or can be computed once.
So if for each beacon position you could check which other positions are in range and sum the affected pumps of all of them and use that as some sort of penalty for that position. But I think you explained earlier that's not possible. So I need to read that bit again.
Maybe once you pick a beacon position, iterate all positions in range again, and reduce their penalty by the number of pumps the new beacon affects.

I see two unrelated ideas here.

First:

I am still figuring out the dynamics of `seen` and `ignore`; and wonder if they are essential to repeat every time (recursively), or can be computed once.

Clever thought, but it doesn't work. if A blocks B1 and B2, then seen is the same for B1 and B2. But if B2 blocks A and C1, while B2 blocks A and C2, then seen is not the same anymore for C1 and C2.
However the calculation of ignore can be sped up by making the beacons not the values, but the keys of seen.

Second:

So if for each beacon position you could check which other positions are in range and sum the affected pumps of all of them and use that as some sort of penalty for that position. But I think you explained earlier that's not possible. So I need to read that bit again.
Maybe once you pick a beacon position, iterate all positions in range again, and reduce their penalty by the number of pumps the new beacon affects.

That is the thing, the penalty is not just the affected pumpjacks of the subbeacons, it's the value you use by not being able to place the subbeacons, and that value does not only depend on the affected subpumpjacks, but also on the subsubbeacons that the subbeacons would block. And so on and so forth.
Your idea is basically limiting the number of iterations to 2. Which would still be a very inaccurate result. So far i found 5 to be the sweet spot.

Interestingly; I don't see any code that reflects the yield of the pumpjack is taking into account. Am I missing something?

No, you're correct. It's just a proof-of-concept-code where i only look at the number of affected pumpjacks. In an actual mod i'd calculate the oil per second gain.

Additional question:
Have you considered the output pipes
I notice your code doesn't do anything with pipes. So all the perfect layouts you're currently computing are not representative, since they have no means of carrying liquids outside of the field.
What's your expectation with those? Because I am very confident that where the pipes are, also affect where the beacons can be.
It seems a shame to figure out near-perfect beacon coverage, only to learn that had the pipes been put down differently you could put down even more beacons. But the pipe routine is a much bigger @#$%^ then the beacon routine, and I'm not really getting excited by the prospect of having to rework it for a few drops of oil.

That is a very good question
And i would probably just let the pipe routine run first to limit the amount of possible beacon places, and then the beacon afterwards, honestly. It's not gonna be optimal, it's gonna loose us efficiency. But figuring out the optimum with both pipes, heat pipes and beacons? Yeh i wouldn't even know where to start.

An alternative would be to first let the beacon routine run, then place the pumpjacks (to figure out their rotation), then let the pipe routine run, and if it doesn't work, then delete everything and fall back to swapping the routines. Possibly double as expensive to calculate though.

[Xcone]

The "correct" greedy approach with an unlimited number of iterations is extremely slow.
The "intermediate" greedy approach with a limited number of iterations is a balance between speed and accuracy.
The "lazy" greedy approach where we ignore beacon blockage is extremely fast and inaccurate.

Ah right. Good clarification/distinction!
I can confirm I use the "lazy" one.

That is the thing, the penalty is not just the affected pumpjacks of the subbeacons, it's the value you use by not being able to place the subbeacons, and that value does not only depend on the affected subpumpjacks, but also on the subsubbeacons that the subbeacons would block. And so on and so forth.
Your idea is basically limiting the number of iterations to 2. Which would still be a very inaccurate result. So far i found 5 to be the sweet spot.

Yea, this bit is a real headscratcher.

Another train of thought (which I haven't thought through, but maybe its something you can work with).
Since (in vanilla) a beacon is 3x3, can we somehow guarantee that means the whole math only has 9 outcomes; all other scores/placement rules being fixed?
If we were testing a 10th position, that's in a way identical as if we were testing of 1 of the 9 possible positions of another beacon?

If this is true, that means once the 1st beacon position is picked, and all the scoring in-between is stored, you should already know all beacon positions, and you should not have to repeat the math for the 2nd beacon, and the 3rd, and 4th, etc..

It's not gonna be optimal, it's gonna loose us efficiency. But figuring out the optimum with both pipes, heat pipes and beacons? Yeh i wouldn't even know where to start.

Right, .. me neither.