Automatic Pumpjack Beacon Placement

[Lindor]

Hello,
i've just had the idea to automize the most optimal beacon placement for pumpjacks.

I have written a very bad command line lua script for this as a proof of concept. The rough idea is:

1. create an object that can hold placed pumpjacks, placed beacons and possible beacon places (i call that object a "board")
2. figure out all possible places for beacons that affect at least one pumpjack in the board and save them
3. pick a possible beacon place and remove it from the list in the board
4. create a copy of the board and place the picked beacon in the copy
5. remove all possible beacon places in the copy that would overlap with the placed placed beacon
6. in the copied board, repeat from step 3 recursively

This gets me all possible beacon configurations without any duplicates. I only save those configurations that are most efficient. Currently to get a metric for the efficiency of a configuration i'm just adding the number of influencing beacons for each pumpjack, in the future that would need to get adjusted of course. It's just a proof of concept. If two configurations have the same efficiency, i take the one where the summed distances between all buildings is smaller.

Here's the code:

Code: Select all

--[[
local createStringArray = function(width, height)
    local self = {}
    do self.width = width end
    do self.height = height end
    
    local s = ""
    for i = 1, width, 1 do
        do s = s.." " end
    end
    do self.array = {} end
    for i = 1, height, 1 do
        do (self.array)[i] = s end
    end
    
    do self.setWidth = function(width)
        local newArray = {}
        if width < self.width then
            for idx, line in pairs(self.array) do
                do newArray[idx] = line:sub(1, width) end
            end
        else
            local append = ""
            for i = self.width + 1, width, 1 do
                do append = append.." " end
            end
            for idx, line in pairs(self.array) do
                do newArray[idx] = line..append end
            end
        end
        do self.array = newArray end
        do self.width = width end
    end end
    
    do self.setHeight = function(width)
        local newArray = {}
        if height < self.height then
            for i = 1, height, 1 do
                do newArray[i] = (self.array)[i] end
            end
        else
            local fill = ""
            for i = 1, self.width, 1 do
                do fill = fill.." " end
            end
            for idx, line in pairs(self.array) do
                do newArray[idx] = line end
            end
            for i = self.height + 1, height do
                do newArray[i] = fill end
            end
        end
        do self.array = newArray end
        do self.height = height end
    end end
    
    do self.insertStringArray = function(stringArray, left, top)
        local mw = (left + stringArray.width) - 1
        local mh = (top + stringArray.height) - 1
        if mw > self.width then
            do (self.setWidth)(mw) end
        end
        if mh > self.height then
            do (self.setHeight)(mh) end
        end
        
        for i = 1, stringArray.height, 1 do
            local idx = (i + top) - 1
            local old = (self.array)[idx]
            local insert = (stringArray.array)[i]
            local new = (old:sub(1, left - 1))..insert..(old:sub(mw + 1, self.width))
            do (self.array)[idx] = new end
        end
    end end
    
    do self.get = function()
        local result = (self.array)[1]
        for i = 2, self.height, 1 do
            local line = (self.array)[i]
            do result = result.."\n"..line end
        end
        do return result end
    end end
    
    do return self end
end
--]]

-- Dimensions box with coordinates. Better handle as if it was immutable.
local createDimensions = function(left, right, top, bottom)
    local self = {}
    
    do self.logicBox = {
        left   = left,
        right  = right,
        top    = top,
        bottom = bottom 
    } end
    do self.width  = (self.logicBox.right  - self.logicBox.left) + 1 end
    do self.height = (self.logicBox.bottom - self.logicBox.top) + 1  end
    
    do self.check = function()
        if self.width < 1 then
            do error("Dimensions width is smaller than 1!") end
        end
        if self.height < 1 then
            do error("Dimensions height is smaller than 1!") end
        end
    end end
    do self.check() end
    
    do self.getCenter = function()
        if type(self.center) == "table" then
            do return self.center end
        end
        do self.center = {} end
        do self.center.x = (self.logicBox.left + self.logicBox.right) / 2 end
        do self.center.y = (self.logicBox.top + self.logicBox.bottom) / 2 end
        do return self.center end
    end end
    
    do self.overlaps = function(otherDimensions)
        local isContained = function(xSmall, xLarge, ySmall, yLarge)
            if yLarge < xSmall then
                do return false end
            end
            if xLarge < ySmall then
                do return false end
            end
            do return true end
        end
        local horizontal = isContained(self.logicBox.left, self.logicBox.right,  otherDimensions.logicBox.left, otherDimensions.logicBox.right)
        local vertical   = isContained(self.logicBox.top,  self.logicBox.bottom, otherDimensions.logicBox.top,  otherDimensions.logicBox.bottom)
        local result = horizontal and vertical
        do return result end
    end end
    
    do return self end
end

-- class for pumpjacks
local createPumpjack = function(left, top)
    local self = {}
    do self.dimensions = createDimensions(left, left + 1, top, top + 1) end
    --do self.stringArray = createStringArray(2, 2) end
    --do self.stringArray.array = {"⌜⌝", "⌞⌟"} end
    --do self.stringArray.array = {"OO", "OO"} end
    do self.stringArray = {"--OO", "OO"} end
    do return self end
end

-- class for beacons
local createBeacon = function(left, top)
    local self = {}
    do self.dimensions = createDimensions(left, left + 2, top, top + 2) end
    do self.influence  = createDimensions(self.dimensions.logicBox.left - 3, self.dimensions.logicBox.right + 3, self.dimensions.logicBox.top - 3, self.dimensions.logicBox.bottom + 3) end
    --do self.stringArray = createStringArray(2, 2) end
    --do self.stringArray.array = {"⌜-⌝", "|O|", "⌞-⌟"} end
    --do self.stringArray.array = {"XXX", "XXX", "XXX"} end
    --do self.stringArray = {"XXX", "XXX", "XXX"} end
    do return self end
end

-- class for configuration
local createBoard
do createBoard = function(pumpjacks, beacons, placeableBeacons)
    local self = {}
    
    -- variables --
    
    do self.pumpjacks = {} end
    do self.beacons = {} end
    do self.entities = {} end
    do self.placeableBeacons = {} end
    for idx, pumpjack in ipairs(pumpjacks) do
        do table.insert(self.pumpjacks, pumpjack) end
        do table.insert(self.entities, pumpjack) end
    end
    for idx, beacon in ipairs(beacons) do
        do table.insert(self.beacons, beacon) end
        do table.insert(self.entities, beacon) end
    end
    if type(placeableBeacons) == "table" then
        for idx, beacon in ipairs(placeableBeacons) do
            do table.insert(self.placeableBeacons, beacon) end
        end
    end
    
    -- methods --
    
    do self.check = function()
        for i = 1, #(self.entities) - 1, 1 do
            local first = (self.entities)[i]
            for j = i + 1, #(self.entities), 1 do
                local second = (self.entities)[j]
                if first.dimensions.overlaps(second.dimensions) then
                    do error("An entity overlap occured during board creation!") end
                end
            end
        end
    end end
    
    do self.copy = function()
        local board = createBoard(self.pumpjacks, self.beacons, self.placeableBeacons)
        do return board end
    end end
    
    do self.testBeacon = function(beacon)
        -- does it collide with other entities?
        for idx, entity in ipairs(self.entities) do
            if beacon.dimensions.overlaps(entity.dimensions) then
                do return false end
            end
        end
        -- does it have at least one pumpjack it influences?
        for idx, pumpjack in ipairs(self.pumpjacks) do 
            if beacon.influence.overlaps(pumpjack.dimensions) then
                do return true end
            end
        end
        do return false end
    end end
    
    do self.getPlaceableBeacons = function()
        do self.placeableBeacons = {} end
        if #(self.pumpjacks) == 0 then
            do return self.placeableBeacons end
        end
        
        local minLeft
        local maxRight
        local minTop
        local maxBottom
        for idx, pumpjack in ipairs(self.pumpjacks) do
            local left = pumpjack.dimensions.logicBox.left
            if (minLeft == nil) then
                do minLeft = left end
            elseif (left < minLeft) then
                do minLeft = left end
            end
            local right = pumpjack.dimensions.logicBox.right
            if (maxRight == nil) then
                do maxRight = right end
            elseif (right > maxRight) then
                do maxRight = right end
            end
            local top = pumpjack.dimensions.logicBox.top
            if (minTop == nil) then
                do minTop = top end
            elseif (top < minTop) then
                do minTop = top end
            end
            local bottom = pumpjack.dimensions.logicBox.bottom
            if (maxBottom == nil) then
                do maxBottom = bottom end
            elseif (bottom > maxBottom) then
                do maxBottom = bottom end
            end
        end
        
        -- x and y are the beacons center coordinates
        for x = minLeft - 3, maxRight + 3, 1 do
            for y = minTop - 3, maxBottom + 3, 1 do
                local beacon = createBeacon(x - 1, y - 1)
                if self.testBeacon(beacon) then
                    do table.insert(self.placeableBeacons, beacon) end
                end
            end
        end
        
    end end
    
    do self.getSources = function()
        if type(self.sources) == "number" then
            do return self.sources end
        end
        do self.sources = 0 end
        for idx, pumpjack in ipairs(self.pumpjacks) do
            for _, beacon in ipairs(self.beacons) do
                if beacon.influence.overlaps(pumpjack.dimensions) then
                    do self.sources = self.sources + 1 end
                end
            end
        end
        do return self.sources end
    end end
    
    do self.getSpreading = function()
        if type(self.spreading) == "number" then
            do return self.spreading end
        end
        do self.spreading = 0 end
        for idx, first in ipairs(self.entities) do
            for _, second in ipairs(self.entities) do
                local centerFirst = first.dimensions.getCenter()
                local centerSecond = first.dimensions.getCenter()
                local dx = centerFirst.x - centerSecond.x
                local dy = centerFirst.y - centerSecond.y
                local d = math.sqrt((dx * dx) + (dy * dy))
                do self.spreading = self.spreading + d end
            end
        end
        do return self.spreading end
    end end
    
    do self.placeBeacon = function(beacon)
        if not self.testBeacon(beacon) then
            do error("Beacon cannot be placed!") end
        end
        do table.insert(self.beacons, beacon) end
        do table.insert(self.entities, beacon) end
        local newPlaceableBeacons = {}
        for idx, placeableBeacon in ipairs(self.placeableBeacons) do
            if not beacon.dimensions.overlaps(placeableBeacon.dimensions) then
                do table.insert(newPlaceableBeacons, placeableBeacon) end
            end
        end
        do self.placeableBeacons = newPlaceableBeacons end
        do self.sources = nil end
        do self.spreading = nil end
    end end
    
    do self.getPossibleConfigs = function(onUpdate)
        local nBeaconsTotal = #(self.placeableBeacons)
        if nBeaconsTotal == 0 then
            do return {self} end
        end
        
        local nBeacons = nBeaconsTotal
        local percentage = 0
        local nExpBeaconsTotal = 2 ^ (nBeaconsTotal)
        local onSubUpdate = function(subPercentage)
            local beaconsTodo = nBeacons - (subPercentage / 100)
            
            local newPercentageFloatExponential = (nExpBeaconsTotal - (2 ^ (beaconsTodo))) / (nExpBeaconsTotal - 1)
            local newPercentageFloatLinear = (nBeaconsTotal - beaconsTodo) / nBeaconsTotal
            local newPercentageFloat = newPercentageFloatLinear / ((1 + newPercentageFloatLinear) - newPercentageFloatExponential) -- interpolation
            
            local newPercentage = math.floor(newPercentageFloat * 100)
            if newPercentage > percentage then
                do percentage = newPercentage end
                do onUpdate(percentage) end
            end
        end
        
        local result = {}
        local sources = 0
        while nBeacons > 0 do
            do onSubUpdate(0) end
            local beacon = (self.placeableBeacons)[nBeacons]
            do (self.placeableBeacons)[nBeacons] = nil end
            do nBeacons = nBeacons - 1 end
            local subBoard = self.copy()
            do subBoard.placeBeacon(beacon) end
            local subConfigs = subBoard.getPossibleConfigs(onSubUpdate)
            for idx, config in ipairs(subConfigs) do
                local cSources = config.getSources()
                if cSources > sources then
                    do result = {config} end
                    do sources = cSources end
                elseif cSources == sources then
                    do table.insert(result, config) end
                end
            end
        end
        do return result end
    end end
    
    do self.makestring = function()
        if #(self.entities) == 0 then
            do return "" end
        end
        
        local minLeft
        local maxRight
        local minTop
        local maxBottom
        for idx, entity in ipairs(self.entities) do
            local left = entity.dimensions.logicBox.left
            if (minLeft == nil) then
                do minLeft = left end
            elseif (left < minLeft) then
                do minLeft = left end
            end
            local right = entity.dimensions.logicBox.right
            if (maxRight == nil) then
                do maxRight = right end
            elseif (right > maxRight) then
                do maxRight = right end
            end
            local top = entity.dimensions.logicBox.top
            if (minTop == nil) then
                do minTop = top end
            elseif (top < minTop) then
                do minTop = top end
            end
            local bottom = entity.dimensions.logicBox.bottom
            if (maxBottom == nil) then
                do maxBottom = bottom end
            elseif (bottom > maxBottom) then
                do maxBottom = bottom end
            end
        end
        
        local width = (maxRight - minLeft) + 1
        local height = (maxBottom - minTop) + 1
        
        --[[
        local stringArray = createStringArray(width, height)
        for idx, entity in ipairs(self.entities) do
            do stringArray.insertStringArray(
                entity.stringArray,
                (entity.dimensions.logicBox.left - minLeft) + 1,
                (entity.dimensions.logicBox.top - minTop) + 1
            ) end
        end
        
        local result = stringArray.get()
        --]]
        
        local arr = {}
        for y = minTop, maxBottom, 1 do
            if type(arr[y]) ~= "table" then
                do arr[y] = {} end
            end
            for x = minLeft, maxRight, 1 do
                do (arr[y])[x] = " " end
            end
        end
        
        for idx, pumpjack in pairs(self.pumpjacks) do
            for y = pumpjack.dimensions.logicBox.top, pumpjack.dimensions.logicBox.bottom, 1 do
                for x = pumpjack.dimensions.logicBox.left, pumpjack.dimensions.logicBox.right, 1 do
                    do (arr[y])[x] = "O" end
                end
            end
        end
        
        for idx, beacon in pairs(self.beacons) do
            for y = beacon.dimensions.logicBox.top, beacon.dimensions.logicBox.bottom, 1 do
                for x = beacon.dimensions.logicBox.left, beacon.dimensions.logicBox.right, 1 do
                    do (arr[y])[x] = "X" end
                end
            end
        end
        
        local result = ""
        for y = minTop, maxBottom, 1 do
            local s = ""
            for x = minLeft, maxRight, 1 do
                do s = s..((arr[y])[x]) end
            end
            do result = result.."\n"..s end
        end
        
        do return result end
    end end
    
    do return self end
end end

local jacks = {}
while true do
    io.write("Place another pumpjack (y/n)?: ")
    io.flush()
    local input = io.read()
    if input == "n" then
        do os.execute("cls") end
        do print("Done with Setup!") end
        do break end
    elseif input == "y" then
        io.write("x (left): ")
        io.flush()
        local x = tonumber(io.read())
        io.write("y (top): ")
        io.flush()
        local y = tonumber(io.read())
        local jack = createPumpjack(x, y)
        do table.insert(jacks, jack) end
        do os.execute("cls") end
        do print("Placed!") end
    else
        do os.execute("cls") end
        do print("Invalid Answer!") end
    end
end
do print("Creating board...") end
local theBoard = createBoard(jacks, {}, {})
do theBoard.check() end
do print("Calculating beacon spots...") end
do theBoard.getPlaceableBeacons() end
do print("Calculating optimal configurations...") end
local configs = theBoard.getPossibleConfigs(function(percentage)
    do print("  "..tostring(percentage).."%") end
end, true)
do print("getting optimal config by spread...") end
local optimalConfig = configs[1]
for idx, config in pairs(configs) do
    local spreadingOld = optimalConfig.getSpreading()
    local spreadingNew = config.getSpreading()
    if spreadingNew < spreadingOld then
        do optimalConfig = config end
    end
end
do print("making string...") end
local s = optimalConfig.makestring()
print(s)

It's fine for memory, but it has horrible runtime.
Maybe my attempt to misuse functions to mimic a kind of object-oriented-ness in lua slows it down too much, or maybe it's just a problem that cannot be solved efficiently within acceptable runtime.
Is there a way to optimize the code so that it's practical ingame? Or is the problem just too difficult to solve efficiently?

I've also noticed that there already exists a mod for this, and i wonder wether it's the most optimal beacon placement or just something that's "good enough".

[Coppermine]

I'm the author of OilOutpostPlanner (the above-linked mod).

It uses a simple greedy algorithm to place beacons: Rate every potential beacon location, choose (one of) the best, put a beacon there, and repeat. It does correctly take into account the reduced effect of multiple beacons.

This is certainly not optimal. From watching the sort of mistake it makes, I think there is a simple heuristic that would substantially improve it: when there are several equally-good best locations, choose one which places the beacon 'in a corner'. In other words, add a tie-breaker for the beacon effect where we count the number of orthogonally adjacent positions to the potential beacon location where a beacon *cannot* be placed. More is better.

However, there's also another more serious (but less often relevant) issue with the beacon placement algorithm: on Aquilo it doesn't run heat pipes to the beacons. If you only place a small number of beacons, this usually just works out OK, but for higher numbers of beacons it will place them in locations which cannot be heated.

I would like to fix both these issues, but I haven't figured out a sufficiently nice way to write the code yet, so I haven't.

[Lindor]

I see. Well thanks for the reply!
I can see your heuristic significantly improving your aalgorithm, but i don't think that it would always find the best solution.
While my algorithm does always find the best solution, i figured that, if i did not make a mistake, time complexity would be roughly O(2^n), which is pretty bad.
I wish my code could be improved somehow. Currently i see only one possibility: figuring out which which beacon blocks which and saving it in a lookup table beforehand. While it could save a bit of calculations, i don't see it bringing it down to polynomial or constant runtime. There are too many possibilities to check.

[Lindor]

Uh uh - just as i replied, i've had a new idea inspired by your algorithm. Pseudocode:

Code: Select all

function self.grade(seen) {
    seen.append(self);
    
    // get the benefit value to all affected pumpjacks
    pumpjacks = self.getAffectedPumpjacks();
    grading = sum(array_map(pumpjacks, lambda pumpjack: pumpjack.getValue(self)));
    
    // subtract the grading of all beacons that cannot be placed if we place self
    overlappingBeacons = self.getOverlappingBeacons();
    foreach (beacon of overlappingBeacons) {
        if (not seen.contains(beacon)) {
            grading -= beacon.grade(seen);
        }
    }
    
    // out
    return grading;
}

self would be a beacon. We would place the beacon that has the highest grading until there are no more beacons left. If two beacons have the same grading, we can apply metrics like the distance to the center or smth like that. I think this would yield the best solution in O(n) time complexity where n is the number of possible beacon places.

I haven't proven it, but i think this would work.

EDIT: Actually i think it would be higher than O(n). We can't just append self to seen, we need to copy it first. Seen can't grow with every beacon, it can only grow with every new level of recursion depth.

[Coppermine]

Finding the optimal solution in the general case is probably NP hard, so I doubt an algorithm exists that's faster than exponential time in the worst case.

If I wanted to find the optimal solution, my first instinct would be to try to phrase this as an Integer Programming problem (https://en.wikipedia.org/wiki/Integer_programming) and try to use a well optimized library for those. Or maybe an SMT solver would be better (https://en.wikipedia.org/wiki/Satisfiab ... o_theories). That would get you a while bunch of heuristics for free and hopefully be pretty fast in almost all cases.

However, I doubt that we have access to a good Integer Programming or SMT solver library in this context. It would have to be written in pure Lua, which is a crazy thing for anyone to have done. (But I haven't actually checked)

[Lindor]

Yes the problem seems so simple at first, but even at the generalized one-dimensional case with arbitrarily large beacon influence areas i think it can't get better than exponential in the worst case. With small influence areas there are some tricks in the one-dimensional case that can be pulled off to make it linear though.
But i don't know how to proof that the problem is NP-complete.

...Any bored computer scientists out there?

[Lindor]

Uh uh - just as i replied, i've had a new idea inspired by your algorithm.
(...)
EDIT: Actually i think it would be higher than O(n). We can't just append self to seen, we need to copy it first. Seen can't grow with every beacon, it can only grow with every new level of recursion depth.

I have programmed both ideas. Doing it correctly by copying seen before passing it to the next beacons scoring function takes even longer than my first attempt!
But if we do it incorrectly by always passing the same table it gets results pretty quickly - the solution is not optimal, but it is good.
This is e.g. what it looks like with 5 pumpjacks, didn't take longer than a couple of seconds:

grafik.png (3.89 KiB) Viewed 663 times

Os are pumpjacks tiles and Xs are beacon tiles.

Here's my code:

Code: Select all

local pop = function(t, element) 
    for k, v in pairs(t) do
        if v == element then
            do table.remove(t, k) end
            do break end
        end
    end
end

-- Dimensions box with coordinates. Better handle as if it was immutable.
local createDimensions = function(left, right, top, bottom)
    local self = {}
    
    do self.logicBox = {
        left   = left,
        right  = right,
        top    = top,
        bottom = bottom 
    } end
    do self.width  = (self.logicBox.right  - self.logicBox.left) + 1 end
    do self.height = (self.logicBox.bottom - self.logicBox.top) + 1  end
    
    do self.check = function()
        if self.width < 1 then
            do error("Dimensions width is smaller than 1!") end
        end
        if self.height < 1 then
            do error("Dimensions height is smaller than 1!") end
        end
    end end
    do self.check() end
    
    do self.getCenter = function()
        if type(self.center) == "table" then
            do return self.center end
        end
        do self.center = {} end
        do self.center.x = (self.logicBox.left + self.logicBox.right) / 2 end
        do self.center.y = (self.logicBox.top + self.logicBox.bottom) / 2 end
        do return self.center end
    end end
    
    do self.overlaps = function(otherDimensions)
        local isContained = function(xSmall, xLarge, ySmall, yLarge)
            if yLarge < xSmall then
                do return false end
            end
            if xLarge < ySmall then
                do return false end
            end
            do return true end
        end
        local horizontal = isContained(self.logicBox.left, self.logicBox.right,  otherDimensions.logicBox.left, otherDimensions.logicBox.right)
        local vertical   = isContained(self.logicBox.top,  self.logicBox.bottom, otherDimensions.logicBox.top,  otherDimensions.logicBox.bottom)
        local result = horizontal and vertical
        do return result end
    end end
    
    do return self end
end

-- class for pumpjacks
local createPumpjack = function(left, top)
    local self = {}
    do self.dimensions = createDimensions(left, left + 1, top, top + 1) end
    do self.stringArray = {"--OO", "OO"} end
    do return self end
end

-- class for beacons
local createBeacon = function(left, top)
    local self = {}
    do self.dimensions = createDimensions(left, left + 2, top, top + 2) end
    do self.influence  = createDimensions(self.dimensions.logicBox.left - 3, self.dimensions.logicBox.right + 3, self.dimensions.logicBox.top - 3, self.dimensions.logicBox.bottom + 3) end
    do self.affectedPumpjacks = {} end
    do self.overlappingBeacons = {} end
    
    do self.addPumpjack = function(pumpjack)
        if self.influence.overlaps(pumpjack.dimensions) then
            do table.insert(self.affectedPumpjacks, pumpjack) end
        end
    end end
    
    do self.addBeacon = function(beacon)
        if self.dimensions.overlaps(beacon.dimensions) then
            do table.insert(self.overlappingBeacons, beacon) end
        end
    end end
    
    do self.removeBeacon = function(beacon)
        do pop(self.overlappingBeacons, beacon) end
    end end
    
    -- primary score. The higher the better.
    do self.score = function(seen)
        do table.insert(seen, self) end
        
        local score = #(self.affectedPumpjacks)
        for idx, beacon in ipairs(self.overlappingBeacons) do
            local ignore = false
            for seenIdx, seenBeacon in ipairs(seen) do
                if seenBeacon == beacon then
                    do ignore = true end
                    do break end
                end
            end
            if (not ignore) then
                do score = score - beacon.score(seen) end
            end
        end
        do return score end
    end end
    
    -- secondary score. The lower the better.
    do self.spreading = function(entities)
        local spreading = 0
        local centerSelf = self.dimensions.getCenter()
        for idx, entity in ipairs(entities) do
            local centerEntity = entity.dimensions.getCenter()
            local dx = centerSelf.x - centerEntity.x
            local dy = centerSelf.y - centerEntity.y
            local d = math.sqrt((dx * dx) + (dy * dy))
            do spreading = spreading + d end
        end
        do return spreading end
    end end
    
    do return self end
end

-- class for configuration
local createBoard
do createBoard = function(pumpjacks, beacons, placeableBeacons)
    local self = {}
    
    -- variables --
    
    do self.pumpjacks = {} end
    do self.beacons = {} end
    do self.entities = {} end
    do self.placeableBeacons = {} end
    for idx, pumpjack in ipairs(pumpjacks) do
        do table.insert(self.pumpjacks, pumpjack) end
        do table.insert(self.entities, pumpjack) end
    end
    for idx, beacon in ipairs(beacons) do
        do table.insert(self.beacons, beacon) end
        do table.insert(self.entities, beacon) end
    end
    if type(placeableBeacons) == "table" then
        for idx, beacon in ipairs(placeableBeacons) do
            do table.insert(self.placeableBeacons, beacon) end
        end
    end
    
    -- methods --
    
    do self.check = function()
        for i = 1, #(self.entities) - 1, 1 do
            local first = (self.entities)[i]
            for j = i + 1, #(self.entities), 1 do
                local second = (self.entities)[j]
                if first.dimensions.overlaps(second.dimensions) then
                    do error("An entity overlap occured during board creation!") end
                end
            end
        end
    end end
    
    do self.copy = function()
        local board = createBoard(self.pumpjacks, self.beacons, self.placeableBeacons)
        do return board end
    end end
    
    do self.testBeacon = function(beacon)
        -- does it collide with other entities?
        for idx, entity in ipairs(self.entities) do
            if beacon.dimensions.overlaps(entity.dimensions) then
                do return false end
            end
        end
        -- does it have at least one pumpjack it influences?
        for idx, pumpjack in ipairs(self.pumpjacks) do 
            if beacon.influence.overlaps(pumpjack.dimensions) then
                do return true end
            end
        end
        do return false end
    end end
    
    do self.getPlaceableBeacons = function()
        do self.placeableBeacons = {} end
        if #(self.pumpjacks) == 0 then
            do return self.placeableBeacons end
        end
        
        local minLeft
        local maxRight
        local minTop
        local maxBottom
        for idx, pumpjack in ipairs(self.pumpjacks) do
            local left = pumpjack.dimensions.logicBox.left
            if (minLeft == nil) then
                do minLeft = left end
            elseif (left < minLeft) then
                do minLeft = left end
            end
            local right = pumpjack.dimensions.logicBox.right
            if (maxRight == nil) then
                do maxRight = right end
            elseif (right > maxRight) then
                do maxRight = right end
            end
            local top = pumpjack.dimensions.logicBox.top
            if (minTop == nil) then
                do minTop = top end
            elseif (top < minTop) then
                do minTop = top end
            end
            local bottom = pumpjack.dimensions.logicBox.bottom
            if (maxBottom == nil) then
                do maxBottom = bottom end
            elseif (bottom > maxBottom) then
                do maxBottom = bottom end
            end
        end
        
        -- x and y are the beacons center coordinates
        for x = minLeft - 3, maxRight + 3, 1 do
            for y = minTop - 3, maxBottom + 3, 1 do
                local beacon = createBeacon(x - 1, y - 1)
                if self.testBeacon(beacon) then
                    do table.insert(self.placeableBeacons, beacon) end
                end
            end
        end
        
    end end
    
    do self.getSources = function()
        if type(self.sources) == "number" then
            do return self.sources end
        end
        do self.sources = 0 end
        for idx, pumpjack in ipairs(self.pumpjacks) do
            for _, beacon in ipairs(self.beacons) do
                if beacon.influence.overlaps(pumpjack.dimensions) then
                    do self.sources = self.sources + 1 end
                end
            end
        end
        do return self.sources end
    end end
    
    do self.getSpreading = function()
        if type(self.spreading) == "number" then
            do return self.spreading end
        end
        do self.spreading = 0 end
        for idx, first in ipairs(self.entities) do
            for _, second in ipairs(self.entities) do
                local centerFirst = first.dimensions.getCenter()
                local centerSecond = first.dimensions.getCenter()
                local dx = centerFirst.x - centerSecond.x
                local dy = centerFirst.y - centerSecond.y
                local d = math.sqrt((dx * dx) + (dy * dy))
                do self.spreading = self.spreading + d end
            end
        end
        do return self.spreading end
    end end
    
    do self.removeBeacon = function(beacon)
        do pop(self.placeableBeacons, beacon) end
        for idx, placeableBeacon in ipairs(self.placeableBeacons) do
            do placeableBeacon.removeBeacon(beacon) end
        end
    end end
    
    do self.placeBeacon = function(beacon)
        if not self.testBeacon(beacon) then
            do error("Beacon cannot be placed!") end
        end
        do table.insert(self.beacons, beacon) end
        do table.insert(self.entities, beacon) end
        local overlappingBeacons = {}
        for idx, placeableBeacon in ipairs(self.placeableBeacons) do
            if beacon.dimensions.overlaps(placeableBeacon.dimensions) then
                do table.insert(overlappingBeacons, placeableBeacon) end
            end
        end
        for idx, overlappingBeacon in ipairs(overlappingBeacons) do
            do self.removeBeacon(overlappingBeacon) end
        end
        do self.sources = nil end
        do self.spreading = nil end
    end end
    
    do self.solve = function()
        for idx, beacon in ipairs(self.placeableBeacons) do
            for pidx, pumpjack in ipairs(self.pumpjacks) do
                do beacon.addPumpjack(pumpjack) end
            end
            for bidx, secondBeacon in ipairs(self.placeableBeacons) do
                if beacon ~= secondBeacon then
                    do beacon.addBeacon(secondBeacon) end
                end
            end
        end
        
        while ((#(self.placeableBeacons)) > 0) do
            do print(#(self.placeableBeacons)) end
            local bestBeacon = nil
            local bestScore  = nil
            local bestSpreading = nil
            for idx, beacon in ipairs(self.placeableBeacons) do
                local score = beacon.score({})
                if bestBeacon == nil then
                    do bestBeacon = beacon end
                    do bestScore = score end
                    do bestSpreading = nil end
                elseif score > bestScore then
                    do bestBeacon = beacon end
                    do bestScore = score end
                    do bestSpreading = nil end
                elseif score == bestScore then
                    local spreading = beacon.spreading(self.entities)
                    if bestSpreading == nil then
                        do bestSpreading = bestBeacon.spreading(self.entities) end
                    end
                    if spreading < bestSpreading then
                        do bestBeacon = beacon end
                        do bestScore = score end
                        do bestSpreading = spreading end
                    end
                end
            end
            do self.placeBeacon(bestBeacon) end
        end
        do return result end
    end end
    
    do self.makestring = function()
        if #(self.entities) == 0 then
            do return "" end
        end
        
        local minLeft
        local maxRight
        local minTop
        local maxBottom
        for idx, entity in ipairs(self.entities) do
            local left = entity.dimensions.logicBox.left
            if (minLeft == nil) then
                do minLeft = left end
            elseif (left < minLeft) then
                do minLeft = left end
            end
            local right = entity.dimensions.logicBox.right
            if (maxRight == nil) then
                do maxRight = right end
            elseif (right > maxRight) then
                do maxRight = right end
            end
            local top = entity.dimensions.logicBox.top
            if (minTop == nil) then
                do minTop = top end
            elseif (top < minTop) then
                do minTop = top end
            end
            local bottom = entity.dimensions.logicBox.bottom
            if (maxBottom == nil) then
                do maxBottom = bottom end
            elseif (bottom > maxBottom) then
                do maxBottom = bottom end
            end
        end
        
        -- local width = (maxRight - minLeft) + 1
        -- local height = (maxBottom - minTop) + 1
        
        local arr = {}
        for y = minTop, maxBottom, 1 do
            if type(arr[y]) ~= "table" then
                do arr[y] = {} end
            end
            for x = minLeft, maxRight, 1 do
                do (arr[y])[x] = " " end
            end
        end
        
        for idx, pumpjack in pairs(self.pumpjacks) do
            for y = pumpjack.dimensions.logicBox.top, pumpjack.dimensions.logicBox.bottom, 1 do
                for x = pumpjack.dimensions.logicBox.left, pumpjack.dimensions.logicBox.right, 1 do
                    do (arr[y])[x] = "O" end
                end
            end
        end
        
        for idx, beacon in pairs(self.beacons) do
            for y = beacon.dimensions.logicBox.top, beacon.dimensions.logicBox.bottom, 1 do
                for x = beacon.dimensions.logicBox.left, beacon.dimensions.logicBox.right, 1 do
                    do (arr[y])[x] = "X" end
                end
            end
        end
        
        local result = ""
        for y = minTop, maxBottom, 1 do
            local s = ""
            for x = minLeft, maxRight, 1 do
                do s = s..((arr[y])[x]) end
            end
            do result = result.."\n"..s end
        end
        
        do return result end
    end end
    
    do return self end
end end

local jacks = {}
while true do
    io.write("Place another pumpjack (y/n)?: ")
    io.flush()
    local input = io.read()
    if input == "n" then
        do os.execute("cls") end
        do print("Done with Setup!") end
        do break end
    elseif input == "y" then
        io.write("x (left): ")
        io.flush()
        local x = tonumber(io.read())
        io.write("y (top): ")
        io.flush()
        local y = tonumber(io.read())
        local jack = createPumpjack(x, y)
        do table.insert(jacks, jack) end
        do os.execute("cls") end
        do print("Placed!") end
    else
        do os.execute("cls") end
        do print("Invalid Answer!") end
    end
end
do print("Creating board...") end
local theBoard = createBoard(jacks, {}, {})
do theBoard.check() end
do print("Calculating beacon spots...") end
do theBoard.getPlaceableBeacons() end
do print("Calculating optimal configurations...") end
do theBoard.solve() end
do print("making string...") end
local s = theBoard.makestring()
print(s)

The magic happens in the scoring function in the beacon class. Above code contains the non-optimal but fast scoring function .
This is what the optimal but exponential runtime scoring function would look like:

Code: Select all

    -- primary score. The higher the better.
    do self.score = function(seen)
        local nextSeen = {}
        for k, v in ipairs(seen) do
            do nextSeen[k] = v end
        end
        do table.insert(nextSeen, self) end
        
        local score = #(self.affectedPumpjacks)
        for idx, beacon in ipairs(self.overlappingBeacons) do
            local ignore = false
            for seenIdx, seenBeacon in ipairs(seen) do
                if seenBeacon == beacon then
                    do ignore = true end
                    do break end
                end
            end
            if (not ignore) then
                do score = score - beacon.score(nextSeen) end
            end
        end
        do return score end
    end end

Maybe you can take something away from it for your mod? It's not Factorio-ready, just a proof-of-concept. It doesn't take the decreasing effectivity of multiple beacons on the same building or the different rates of the pumpjacks into account. But if you like the general idea, then i'd be very proud if i have been able to contribute something to your mod with my code

[Lindor]

I've had another idea to cut computation time at the cost of accuracy: By limiting the scoring function's max recursion depth. Well it's not really recursion, it's calling the same function on another object, but you get what i mean.
Here's the result for the same configuration with a max recursion depth of 5:

grafik.png (3.09 KiB) Viewed 658 times

And here's the code for the scoring function:

Code: Select all

    -- primary score. The higher the better.
    do self.score = function(seen, maxRecursionDepth, recursionDepth)
        local score = #(self.affectedPumpjacks)
        
        local depth = recursionDepth + 1
        if depth >= maxRecursionDepth then
            do return score end
        end
        
        local nextSeen = {}
        for k, v in ipairs(seen) do
            do nextSeen[k] = v end
        end
        do table.insert(nextSeen, self) end
        --do table.insert(seen, self) end
        
        for idx, beacon in ipairs(self.overlappingBeacons) do
            local ignore = false
            for seenIdx, seenBeacon in ipairs(seen) do
                if seenBeacon == beacon then
                    do ignore = true end
                    do break end
                end
            end
            if (not ignore) then
                do score = score - beacon.score(nextSeen, maxRecursionDepth, depth) end
                --do score = score - beacon.score(seen) end
            end
        end
        do return score end
    end end

Don't know which of the two solutions seems 'cleaner'

EDIT:
a max depth of 6 already takes like 20 times as long but makes the result sooo much better

Unbenannt.PNG (3.25 KiB) Viewed 644 times

[Lindor]

I think the entire problem of finding the 'best' can be boiled down to solving a system of linear equations. This can be done in O(n^3) in worst case. So for repeatedly finding the best beacon spot until there's no more left it's O(n^4). So i think the problem isn't NP-hard.

But i'd have to implement a matrix solver, and not just any, but one that can solve a huge Matrix in acceptable time. The smallest possible Matrix with only one pumpjack would be a 48x48 matrix. The example i used in the previous posts with 5 pumpjacks is already a 101x101 matrix.

Implementing that with only lua will be really difficult.

[Coppermine]

I'd love to see how you would convey the problem to longest equations. I don't see a way to do that. The decision of whether to place a beacon is inherently discrete, and solving linear equations (at least over the real numbers) is continuous. How do you avoid the solution suggesting that you place a fractional beacon?

[Lindor]

I'd love to see how you would convey the problem to longest equations. I don't see a way to do that. The decision of whether to place a beacon is inherently discrete, and solving linear equations (at least over the real numbers) is continuous. How do you avoid the solution suggesting that you place a fractional beacon?

It's assigning score to each beacon. Finding the score is continuous, but placing the best scored beacon (and therefore choosing the next matrix to solve) is discrete.

Suppose you have a beacon x which, when placed, would grant +3 oil per second, but would also block 2 other beacons a and b from being placed. That would result in the equation:
score_x = 3 - score_a - score_b
transforming gives
score_x + score_a + score_b = 3
which would be one line of the equation Av=b where A is the matrix and v a vector.
Each parameter of the vector v would be the score of a possible beacon to place. We then solve for v, choose the highest scored beacon and repeat with the next Matrix. This goes on until there's no more beacon left to place.

I'm just not sure wether the resulting equation has any solutions at all. That is the only possible fallacy of the idea.

My previous scoring method was slightly different:
score_x = 3 - score_a\{x} - score_b\{x}
Where score_b\{x} is the score of placing beacon b while ignoring beacon x. So if beacon b would grant 4 oil/s and block beacons x and c:
score_b = 4 - score_x\{b} - score_c\{b}
=> score_b\{x} = 4 - score_x\{b, x} - score_c\{b, x} = 4 - score_c\{b, x}
This recursively continues, with each new iteration there's one more beacon to ignore, until there's a beacon whose blocked beacons are all to be ignored:
score_x\{a,b} = 3
This scoring method definitely always has a unique solution, but i think it cannot be easily expressed as a linear equation. Or maybe it can and i just can't see how.

[Lindor]

This scoring method definitely always has a unique solution, but i think it cannot be easily expressed as a linear equation. Or maybe it can and i just can't see how.

Actually i did find a way to express the old scoring as a linear equation system as well. But the resulting matrix would be of size (2^n)x(2^n). This lacks any practicality. Maybe there's a way to reduce the size though.

[Xcone]

Just curious, what counts as "most efficient" layout?
Is the goal a few as possible beacons, or is the goal maximum beacons per pump? Or a sweet spot somewhere in the middle?

[Lindor]

Just curious, what counts as "most efficient" layout?
Is the goal a few as possible beacons, or is the goal maximum beacons per pump? Or a sweet spot somewhere in the middle?

In my "proof-of-concept" program i go for maximum influence count, so a beacon affecting three pumps is three times more worthy than a beacon affecting just one.

In an actual mod, it would probably be maximum oil per second. But since the yield decreases over time, i'd probably do mod settings to decide between maximum current yield and maximum estimated endgame yield. Actually i'm not even sure wether the difference would even affect the layout.

[Xcone]

In an actual mod, it would probably be maximum oil per second.

Yes, I read that in earlier posts. But max oil doesn't change between 1 beacon affecting 3 pumps, or 3 beacons affecting 3 pumps (1 pump each), no? It's the same amount of oil. Or do you mean something else with it?

So what remains is as few as possible beacons for the same effect?

But what if you need an additional beacon for that 4th pump that's just outside of reach.
Do you consider it more effecient if that beacon to cover the 4th then also covers one of the pumps already covered by another beacon.
Or is it more efficient if that beacon only covers the 4th pump, without also touching the earlier 3?
Or is it even more efficient to simply skip pumps that can't be covered by a beacon that can cover 2 or more pumps?
Or what if the same 4 pumps can be covered by 2 beacons. But you need to pick between a 3/1 or a 2/2 coverage spread?

It's a genuine question that has bothered me while making my own planning logic. I've not been able to figure out what people wanted and consider efficient; and have currently also settled for the greedy approach, by lack of knowing a better goal.

[Xcone]

Actually i'm not even sure wether the difference would even affect the layout.

I don't think it does? I don't see how. Speed is speed, regardless how dry the well is at any point. It scales linearly, no?

[Lindor]

What does "Most efficient" mean?

In an actual mod, it would probably be maximum oil per second.

Yes, I read that in earlier posts. But max oil doesn't change between 1 beacon affecting 3 pumps, or 3 beacons affecting 3 pumps (1 pump each), no? It's the same amount of oil. Or do you mean something else with it?

So what remains is as few as possible beacons for the same effect?

No.

Ask yourself: What do you want to score?
It is important to make a distinction between:

1. Out of a set of multiple pumpjack-and-beacon-layouts, choosing the best
2. On an already existing pumpjack-and-beacon-layout, choosing the next best beacon to place out of the set of all possible beacon places in the layout

Those are two completely different questions.

case 1: Best possible layout

But max oil doesn't change between 1 beacon affecting 3 pumps, or 3 beacons affecting 3 pumps (1 pump each), no? It's the same amount of oil.

That is not necessarily true. It is only true if those 3 pumpjacks are the same 3 pumpjacks in both scenarios. Otherwise it may be false. Different pumpjacks can have different yields.

If however two layouts both deliver, let's say 150 oil per second, but one has 1 beacon and 3 pumpjacks, and the other has 3 beacons and 3 pumpjacks, then those two layouts have the same primary score. They are equally efficient. It's simple as that.

I did use a secondary score for a layout: The spreading. I calculate the distances between all two distinct buildings in the layout and sum them up. If the buildings are closer together, i consider it more efficient. Because it is more space-efficient.

In my code so far, if two layouts also have the same secondary score, then there's really no difference in their efficiency and i just pick one at random.

So what remains is as few as possible beacons for the same effect?

It would be possible to introduce a tertiary score, the number of beacons being placed in the layout - the smaller the better.
It would also be possible to make that the secondary score and make the spreading the tertiary score.
I actually like that.

case 2: Best possible beacon
Warning: This is complex. It is not easy to understand.

First we need to establish that if there is a possible beacon to place that affects at least one pumpjack, it is always better to place it than to not place it.

If a layout can deliver 150 oil per second, and after placing a specific beacon X it could deliver 160 oil per second, then the difference of 10 oil per second would be the starting point to calculate the score of that beacon. However placing a beacon might also block other beacons A and B from being placed. So we need to subtract "the value we loose by not being able to place A and B" from the score. So we need to then calculate that value. But that value is not just the sum of the scores of A and B. That value is the sum of the scores that A and B would have, if X would not exist. So we go into the next round calculating these scores.
Let's say placing B would grant 5 more oil per second and block beacons X, A and C. But we ignore X. So we take 5 and subtract the score that C would have if X and B would both not exist. Then we subtract the score that A would have if X and B would both not exist. That's our final score for B if X would not exist.
This goes on until there's a beacon who does not block any other beacon that is not already ignored.

After all this (very computational expensive) calculation, all scores might end up being negative. Then it would still be better to place the "least negative" beacon than to not place one at all.

That is how you calculate the primary score. I am sorry for the complexity, but there is no way around understanding this if you want to answer the question of the best possible beacon.

Now to the secondary score. Again i used the spreading here. The sum of the distances from beacon X to all other buildings in the layout. The smaller the better.

But here is the catch: It is not possible to get the smallest amount of beacons for the same effect this way. If two beacons X and Y have both the same primary and secondary score, one might still be better than the other because by placing X you might be able to achieve a final layout with the same best possible effect but less beacons than by placing Y. But it's not possible to calculate that before knowing the end result.
If we want to make the smallest number of beacons for the same effect the new secondary score, then there would be no way around splitting it and calculating both possibilities to the very end.

Leftover questions

But what if you need an additional beacon for that 4th pump that's just outside of reach.
Do you consider it more effecient if that beacon to cover the 4th then also covers one of the pumps already covered by another beacon.
Or is it more efficient if that beacon only covers the 4th pump, without also touching the earlier 3?
Or is it even more efficient to simply skip pumps that can't be covered by a beacon that can cover 2 or more pumps?
Or what if the same 4 pumps can be covered by 2 beacons. But you need to pick between a 3/1 or a 2/2 coverage spread?

I think these questions have all been answered by my above explanations.

What about pumpjack yield decrease over time?

Actually i'm not even sure wether the difference would even affect the layout.

I don't think it does? I don't see how. Speed is speed, regardless how dry the well is at any point. It scales linearly, no?

I'm not so sure.
There are three stages of base yield:

1. the initial (maximum) yield
2. the intermediate yield
3. the final (minimum) yield: max(20% of the initial (maximum) yield, 2 oil / second)

The intermediate layout at a given moment in time would most probably differ from the other two layouts.
But let's ignore it.
The question is: would the minimum yield layout be any different from the maximum yield layout?
If the initial yield would be larger than 10 oil / second for all fields, then probably no.
But as soon as that minimum possible value of 2 oil / second kicks in, the ratios start to change.

[Xcone]

Thanks for the elaborate reply. It's been helpful; and I do think I understand (most of) it. I will have to read it a couple more times to be sure.

After 1600 hours of playing I'm still a rookie, as it would seem. Only now after your explainer have I learned that not all oil wells in a field are created equal. I always assumed equal starting yield for each one. Now that I know they don't, .. there's sense in trying to get the best beacon coverage for the higher yield ones at the expense of the lower yield ones.

Power and material costs are also a factor for a lot of players though. Legendary items are expensive, especially in the mid-game. A player might not want to cram their field with as many beacons as fit. Also considering the diminishing returns. Where's the point where you stop adding more beacons? Or would you always go for as much oil (and therefor, beacons) as possibly fit?

I've been looking at my test layouts. Assuming players will usually be happy with at least 1 beacon per pump, there's (usually) just so much space for more beacons to add, that I wonder how much difference it really makes if I'd take the greedy approach or the super-smart approach. That is, unless you go for the double or triple coverage, or even beacon cramming?

Here's a typical test case for me. Look at all that available space :

01-05-2026, 13-41-43.png (224.9 KiB) Viewed 185 times

Or I can cram it; but that seems so, ... excessive?:

01-05-2026, 13-41-32.png (259.73 KiB) Viewed 185 times

[Xcone]

To clarify where my thinking is coming from;

At this point I'm still curious what you consider to be "most optimal". And I am trying to already bring in some "it depends on the player, the planet, and the phase of the game" nuances.

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.

That means `case 1; best possible layouts`, or, comparing all the possible layouts is off the table. (that's at least not something I would be interested in, both as a modder as well as a player).
Then remains `case 2; best possible beacon`, which is basically what the current mods are doing. Although the heuristics might differ. But that can be tweaked/expanded upon.

So I think based on your elaborate explanation I have a sense what you find important oil-wise and how to prioritize between picking beacon positions. But still I am wondering, in your eyes, where the line is between as much as oil as possible, and as few costs (beacons/modules/power) as possible. At some point the routine should say "no next beacon position". And that might not be same moment as "all possible build locations being exhausted".

[Coppermine]

The way I chose to handle this trade off between more beacons and more fluid in OilOutpostPlanner was to let the player specify the minimal marginal value of a beacon and place all beacons which were at least that valuable.

This conversation has made me realize that I wasn't measuring marginal value correctly, because I am just measuring it in terms of percentage boost to pumjack speed, but, as discussed above, some pumpjacks are more valuable than others. So the value should be computed as additional oil (or whatever fluid) added.

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?