Mylon's Many Mods

Topics and discussion about specific mods
User avatar
5thHorseman
Filter Inserter
Filter Inserter
Posts: 776
Joined: Fri Jun 10, 2016 11:21 pm
Contact:

Re: Mylon's Many Mods

Post by 5thHorseman » Fri Mar 16, 2018 1:35 am

Thank you for your reply. What a choice, long reach or auto deconstruction! :D
"So you completed the game with a spaghetti factory? Well I hand crafted a rocket and threw it into space with my bare hands!"

Mylon
Filter Inserter
Filter Inserter
Posts: 456
Joined: Sun Oct 23, 2016 11:42 pm
Contact:

Re: Mylon's Many Mods

Post by Mylon » Fri Mar 16, 2018 5:06 pm

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

User avatar
Therax
Filter Inserter
Filter Inserter
Posts: 423
Joined: Sun May 21, 2017 6:28 pm
Contact:

Re: Mylon's Many Mods

Post by Therax » Fri Mar 16, 2018 6:22 pm

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.
Miniloader — UPS-friendly 1x1 loaders
Bulk Rail Loaders — Rapid train loading and unloading
Beltlayer & Pipelayer — Route items and fluids freely underground

Mylon
Filter Inserter
Filter Inserter
Posts: 456
Joined: Sun Oct 23, 2016 11:42 pm
Contact:

Re: Mylon's Many Mods

Post by Mylon » Sun Mar 18, 2018 4:22 pm

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

User avatar
Therax
Filter Inserter
Filter Inserter
Posts: 423
Joined: Sun May 21, 2017 6:28 pm
Contact:

Re: Mylon's Many Mods

Post by Therax » Sun Mar 18, 2018 6:38 pm

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.
Miniloader — UPS-friendly 1x1 loaders
Bulk Rail Loaders — Rapid train loading and unloading
Beltlayer & Pipelayer — Route items and fluids freely underground

mrvn
Smart Inserter
Smart Inserter
Posts: 3840
Joined: Mon Sep 05, 2016 9:10 am
Contact:

Re: Mylon's Many Mods

Post by mrvn » Mon Mar 19, 2018 12:09 pm

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

User avatar
Therax
Filter Inserter
Filter Inserter
Posts: 423
Joined: Sun May 21, 2017 6:28 pm
Contact:

Re: Mylon's Many Mods

Post by Therax » Mon Mar 19, 2018 9:01 pm

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. :)
Miniloader — UPS-friendly 1x1 loaders
Bulk Rail Loaders — Rapid train loading and unloading
Beltlayer & Pipelayer — Route items and fluids freely underground

Mylon
Filter Inserter
Filter Inserter
Posts: 456
Joined: Sun Oct 23, 2016 11:42 pm
Contact:

Re: Mylon's Many Mods

Post by Mylon » Tue Mar 20, 2018 2:58 pm

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. :)

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.

User avatar
Therax
Filter Inserter
Filter Inserter
Posts: 423
Joined: Sun May 21, 2017 6:28 pm
Contact:

Re: Mylon's Many Mods

Post by Therax » Tue Mar 20, 2018 10:31 pm

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.
Miniloader — UPS-friendly 1x1 loaders
Bulk Rail Loaders — Rapid train loading and unloading
Beltlayer & Pipelayer — Route items and fluids freely underground

Mylon
Filter Inserter
Filter Inserter
Posts: 456
Joined: Sun Oct 23, 2016 11:42 pm
Contact:

Re: Mylon's Many Mods

Post by Mylon » Wed Mar 21, 2018 12:18 am

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

User avatar
Therax
Filter Inserter
Filter Inserter
Posts: 423
Joined: Sun May 21, 2017 6:28 pm
Contact:

Re: Mylon's Many Mods

Post by Therax » Wed Mar 21, 2018 2:30 am

Mylon wrote: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
Miniloader — UPS-friendly 1x1 loaders
Bulk Rail Loaders — Rapid train loading and unloading
Beltlayer & Pipelayer — Route items and fluids freely underground

Mylon
Filter Inserter
Filter Inserter
Posts: 456
Joined: Sun Oct 23, 2016 11:42 pm
Contact:

Re: Mylon's Many Mods

Post by Mylon » Wed Mar 21, 2018 3:39 am

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

mrvn
Smart Inserter
Smart Inserter
Posts: 3840
Joined: Mon Sep 05, 2016 9:10 am
Contact:

Re: Mylon's Many Mods

Post by mrvn » Thu Mar 22, 2018 10:31 am

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.

User avatar
Therax
Filter Inserter
Filter Inserter
Posts: 423
Joined: Sun May 21, 2017 6:28 pm
Contact:

Re: Mylon's Many Mods

Post by Therax » Thu Mar 22, 2018 6:49 pm

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.
Miniloader — UPS-friendly 1x1 loaders
Bulk Rail Loaders — Rapid train loading and unloading
Beltlayer & Pipelayer — Route items and fluids freely underground

Mylon
Filter Inserter
Filter Inserter
Posts: 456
Joined: Sun Oct 23, 2016 11:42 pm
Contact:

Re: Mylon's Many Mods

Post by Mylon » Thu Mar 22, 2018 9:26 pm

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

User avatar
Therax
Filter Inserter
Filter Inserter
Posts: 423
Joined: Sun May 21, 2017 6:28 pm
Contact:

Re: Mylon's Many Mods

Post by Therax » Fri Mar 23, 2018 3:41 am

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.
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.
Miniloader — UPS-friendly 1x1 loaders
Bulk Rail Loaders — Rapid train loading and unloading
Beltlayer & Pipelayer — Route items and fluids freely underground

Mylon
Filter Inserter
Filter Inserter
Posts: 456
Joined: Sun Oct 23, 2016 11:42 pm
Contact:

Re: Mylon's Many Mods

Post by Mylon » Fri Mar 23, 2018 1:20 pm

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
Smart Inserter
Smart Inserter
Posts: 3840
Joined: Mon Sep 05, 2016 9:10 am
Contact:

Re: Mylon's Many Mods

Post by mrvn » Fri Mar 23, 2018 4:18 pm

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.
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
Manual Inserter
Manual Inserter
Posts: 1
Joined: Fri Mar 30, 2018 10:38 pm
Contact:

bluebuild mod causing lag

Post by naervig » Fri Mar 30, 2018 10:40 pm

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

aka13
Filter Inserter
Filter Inserter
Posts: 255
Joined: Sun Sep 29, 2013 1:18 pm
Contact:

Re: Mylon's Many Mods

Post by aka13 » Mon Apr 09, 2018 10:33 am

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.
Pony/Furfag avatar? Opinion discarded.

Post Reply

Return to “Mods”

Who is online

Users browsing this forum: Stargateur