Factorio Forums

Mylon wrote:Deconstruction is limited by only being able to look at nearby entities and checking if they've been marked for deconstruction. If there's too many entities nearby, the game can't check them all without taking a serious performance hit. Unfortunately it's a limitation of the engine and I have to make concessions for the sake of performance. Long reach in particular can make the problem worse, as it increases the search area.

Therax wrote:

Mylon wrote:Deconstruction is limited by only being able to look at nearby entities and checking if they've been marked for deconstruction. If there's too many entities nearby, the game can't check them all without taking a serious performance hit. Unfortunately it's a limitation of the engine and I have to make concessions for the sake of performance. Long reach in particular can make the problem worse, as it increases the search area.

I've been working on a plan to track entities by listening for on_marked_for_deconstruction events. With a proper data structure that should be much better for performance than polling every entity in a large search radius.

Mylon wrote:I thought that too. But iterating over a list of 1000 entities to see which are marked for deconstruction is quite performance intensive as well.

Therax wrote:

Mylon wrote:I thought that too. But iterating over a list of 1000 entities to see which are marked for deconstruction is quite performance intensive as well.

Hence "proper data structure."

I was thinking of something like splitting the world into 128x128 chunks, storing entities marked for destruction by chunk, and then iterating only those chunks that are adjacent to the one the player is in. That's enough for default Long Reach (125 tiles).

It's also a lot faster to check a Lua table of 1000 items than it is to check 1000 entities to see if they're marked for deconstruction. The slowest part of scripting is interacting with the mod API to reach back into C++ land.

Mylon wrote:I updated Bluebuild with the "revive=true" flag.

I also added a new mod: Enhanced Biters.

mrvn wrote:On the other hand catching every "marked for destruction" event means that marking 100k alien artefacts somewhere on the map will stop the game for a long time while you update your cache. And then when the bots collect all the artifacts it will cost a lot of cpu again to update the cache. All that with the player nowhere near it.

Therax wrote:

Mylon wrote:I updated Bluebuild with the "revive=true" flag.

I also added a new mod: Enhanced Biters.

I just realized that you use "revive" while Nanobots uses "revived" (with a 'd'). Could you change yours to match?

I still think Bluebuild shouldn't raise on_put_item at all. The only way to know what item was "put" is to look at player_index and check the cursor_stack, which is worse than useless in Bluebuild's case.

mrvn wrote:On the other hand catching every "marked for destruction" event means that marking 100k alien artefacts somewhere on the map will stop the game for a long time while you update your cache. And then when the bots collect all the artifacts it will cost a lot of cpu again to update the cache. All that with the player nowhere near it.

I tested marking 100k entities for deconstruction with a script recording each one by 128x128 chunk. It took 6 ms on my 5 year-old machine: half a frame at 60 FPS. I think that's probably acceptable for such a large and rare case.

Mylon wrote:Can you share your code for recording deconned entities? It would be handy for peppermint mining. The code I'm using causes serious lag when I record the decon-selection of 1k ore entities.

chunks = {}
script.on_event(
    defines.events.on_marked_for_deconstruction,
    function (e)
        local en = e.entity
        local p = en.position
        local x = math.floor(p.x / 128)
        local y = math.floor(p.y / 128)
        if not chunks[x] then chunks[x] = {} end
        if not chunks[x][y] then chunks[x][y] = {} end
        local t = chunks[x][y]
        t[#t+1] = en
    end
)

game.surfaces.nauvis.spill_item_stack({0,0}, {name="iron-plate", count=100000})

Therax wrote:

Mylon wrote:Can you share your code for recording deconned entities? It would be handy for peppermint mining. The code I'm using causes serious lag when I record the decon-selection of 1k ore entities.

Sure. It's not anything particularly sophisticated though:

Code: Select all

chunks = {}
script.on_event(
    defines.events.on_marked_for_deconstruction,
    function (e)
        local en = e.entity
        local p = en.position
        local x = math.floor(p.x / 128)
        local y = math.floor(p.y / 128)
        if not chunks[x] then chunks[x] = {} end
        if not chunks[x][y] then chunks[x][y] = {} end
        local t = chunks[x][y]
        t[#t+1] = en
    end
)

I then spawned in 100k iron-plates via something like:

Code: Select all

game.surfaces.nauvis.spill_item_stack({0,0}, {name="iron-plate", count=100000})

and selected them all with a deconstruction planner.

Mylon wrote:Oh, you're not recording a pointer to the actual entities.

        t[#t+1] = en

local pos = player.position
local cx, cy = math.floor(pos.x / 128), math.floor(pos.y / 128)
local entities = chunks[cx][cy]
if not entities or not next(entities) then
  -- no entities in current chunk, check adjacent chunks
  entities = {}
  for x=cx-1,cx+1 do
    for y=cy-1,cy+1 do
      if chunks[x][y] then
        for _, entity in ipairs(chunks[x][y]) do
          -- if only interested in the first valid entity within build range,
          -- no need to build entities array, just return first entity encountered
          entities[#entities+1] = entity
        end
      end
    end
  end
end

mrvn wrote:I would suggest making the chunk size smaller though. Why not use 32x32 chunks like the game itself. With 128x128 chunks you might have to search a 256x256 area while the players reach is normally way less than that. With smaller chunks there would be less items to check f they are even in reach.

With long reach you then might have to check more chunks but you can check them in order of distance so you get items in smaller groups pre-sorted by distance making everything else faster.

Therax wrote:

mrvn wrote:I would suggest making the chunk size smaller though. Why not use 32x32 chunks like the game itself. With 128x128 chunks you might have to search a 256x256 area while the players reach is normally way less than that. With smaller chunks there would be less items to check f they are even in reach.

With long reach you then might have to check more chunks but you can check them in order of distance so you get items in smaller groups pre-sorted by distance making everything else faster.

128x128 was chosen just for simplicity of description. With 32x32 chunks, you have to search up to 81 chunks when build distance is 128. You could search them in a spiral pattern around the player, which isn't difficult, but is also more code than would be easy to read and understand in a forum post.

I actually spent a few evenings this week implementing a 2-D R* tree in Lua, which should be a very efficient data structure for storing ghosts and entities marked for deconstruction. It's possibly overkill from an implementation complexity perspective.

Mylon wrote:I'd be interested in how you did your R* tree.

If you look at Peppermint Mining, I store a table of every ore ever marked by a deconstruction planner. And when I mark more, I check the list to make sure there are no duplicates. It's a very expensive process and maybe an R* tree could help make it more efficient.

• Looping over a table and filtering out invalid entries using table.remove() is O(n^2), so I'd recommend an approach that instead copies over the desired items to a new table in O(n) time.
• I would guess that calling find_logistics_networks_by_construction_area() for every resource entity might be using up quite a bit of time. Caching the LuaLogisticNetworks and their cells as you find them might help quite a bit. This is something that an R*-Tree might be quite useful for: storing the bounding boxes of the construction areas of each cell, and then (quickly) querying the tree to if each resource entity is inside one of the cells without invoking the Factorio API again.

Therax wrote:

mrvn wrote:I would suggest making the chunk size smaller though. Why not use 32x32 chunks like the game itself. With 128x128 chunks you might have to search a 256x256 area while the players reach is normally way less than that. With smaller chunks there would be less items to check f they are even in reach.

With long reach you then might have to check more chunks but you can check them in order of distance so you get items in smaller groups pre-sorted by distance making everything else faster.

128x128 was chosen just for simplicity of description. With 32x32 chunks, you have to search up to 81 chunks when build distance is 128. You could search them in a spiral pattern around the player, which isn't difficult, but is also more code than would be easy to read and understand in a forum post.

I actually spent a few evenings this week implementing a 2-D R* tree in Lua, which should be a very efficient data structure for storing ghosts and entities marked for deconstruction. It's possibly overkill from an implementation complexity perspective.