Mylon's Many Mods

[5thHorseman]

Thank you for your reply. What a choice, long reach or auto deconstruction!

[Mylon]

You can have both! If you don't mind 30 UPS in mid game!

[Therax]

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]

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.

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]

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.

[mrvn]

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.

In case of long reach I would suggest only sorting entities by distance in the chunk the player is in (plus neighbour if near the border). For other chunks that are further away simply deconstruct the first in the cache. That should reduce the cost to near 0.

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]

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.

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]

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.

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.

Doh. All of that work and new bugs in Bluebuild and I didn't even add the right field.

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.

[Therax]

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]

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.

Oh, you're not recording a pointer to the actual entities. Currently, bluebuild does find_entities_filtered{force=player.force, limit=40, area=around_player} and iterates over that list to find entities marked for deconstruction. I thought I'd be cheeky and make the area proportional to player reach but... Clearly that causes problems!

[Therax]

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

Sure I am:

Code: Select all

        t[#t+1] = en

"en" is an actual entity pointer that comes in via the event, and it's stored for later retrieval.

Querying should be pretty straightforward:

Code: Select all

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

[Mylon]

Oh... I was thinking you were using a different event. I was using the deconstructed_area event in another mod.

[mrvn]

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]

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]

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.

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.

[Therax]

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.

I'll put my R* tree library up on github once it's debugged and I've added efficient nearest-neighbor searching to it.

I looked at the most recent version of the Peppermint Mining code and I see that the deduplication code you're talking about is all commented out already. You have a comment mentioning O(n^2) runtime, but the calls to add() look O(n) to me. I assume the comment is referring to the commented out code. If you're finding that mark() is too slow, there are a couple of other suggestions I could make:

• 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.

[Mylon]

Thanks for your help. I'll switch to a table-copy method and see if that helps. The find_closest_logistic_cell could be refactored to simply cache the area and further calls can do a simple, "check if in area" since marked ore entities will probably be in the the same cell anyway.

[mrvn]

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.

That's fine then. I just didn't want the normal short reach to become slower just to make long reach usable. Spiraling through chunks for long reach doesn't cost much time while having an overlarge chunks size for normal does. Just wanted you to keep the balance in mind.

An R*-Tree sounds like a good data structure for this kind of problem. On the other hand I have my doubts that it will beat a simple chunk bases algorithm. Looking up a chunk in a lua table is such a trivial operation while you have a lot of code to create dynamic data structures. Don't forget the overhead for the GC you are causing and such. Only profiling will tell what is better.

[naervig]

your bluebuild mod is causing lag when i place a lot of blueprints

[aka13]

Hey, are you going to update your concreep mod? It lacks configurability and the new concrete.

If you are bored out of supporting it, I could try supporting it, if you like.