surface.find_entities_filtered() hangs for large radius

[mrvn]

Both the Bluebuild and Autobuild mods hang the game when you start a Sandbox. Both are very similar code so I only looked at Bluebuild to see where it hangs and this is where it hangs:

Code: Select all

local areaList = builder.surface.find_entities_filtered{position = pos, radius = builder.reach_distance, type = {"entity-ghost", "tile-ghost"}, force=builder.force, limit=200 }

In Sandbox mode reach_distance = 4294967295 so it searches a basically infinite area.

But if I change that to

Code: Select all

local areaList = builder.surface.find_entities_filtered{type = {"entity-ghost", "tile-ghost"}, force=builder.force, limit=200 }

then the game searches the whole surface and finishes with no delay as barely any area is generated.


It looks like find_entitites_filtered with an area to search iterates over the whole area while searching the whole surface only goes through the generated chunks. This problem could be avoided by checking the radius against the number of generated chunks on the surface and picking a smarter iterator:

Code: Select all

if (M_PI * radius * radius > surface.num_generated_chunks) {
    iterate_over_generated_chunks(...);
else
    iterate_over_area(...);
end

The API for find_entities_filtered does not specify any order for the returned entites so changing the order in which chunks are checked would not violate the API contract.

PS: same problem probably exists when searching for tiles, when counting entities/tiles, find_non_colliding_position, ...

[Rseding91]

Thanks for the report however I don't consider the current behavior incorrect. If your goal is to search the whole surface simply don't give a radius or search area. If you give a radius or search area that specific area will be searched regardless of current surface generation status.

[mrvn]

I, or rather Bluebuild, doesn't intent to search the whole surface. The Sandbox mode just has an insane reach.

I still consider it a bug that the game just hangs for what basically amounts to forever. You have to switch back to the console and CTRL-C the game twice to kill it. At a minimum the game could limit the reach to something that finishes under a minute. Anything larger must be a mistake by the mod.

PS: sandbox mode used to work with Bluebuild so I believe the reach must have changed to UINT_MAX at some point in factorio developement and break mods that use the reach unchecked.

[lyvgbfh]

Is there a use case for searching ungenerated areas?

[boskid]

Is there a use case for searching ungenerated areas?

If the generated map looks like a donut, then entity search has to go through entire search area. If a chunk does not exist the search quickly sweeps to the end of line but because entity searches are always scanning surface row by row (advanced tile wide, which means 2 tiles wide strips) an ungenerated chunk may be seen up to 16 times. There could be some tiny optimization by checking what is the lowest and highest Chunk's X coordinate and clip the search area in width to that value but this starts going into non game state since Surface is implemented as InfiniteVector of InfiniteVectors of pointers to chunks and we do not care if those infinite vectors are trimmed or not so their size may be larger on the server after chunks were deleted than it would be on the client which loads only existing chunks.

[mrvn]

Is there a use case for searching ungenerated areas?

There isn't. The problem is: How do you know the area is not generated? At a minimum you have to check once per chunk if you go by area.

If the area is (much) larger than the number of existing chunks it becomes faster to check if the generated chunks are inside the area. That was my proposal for a fix.

[robot256]

Problem

Because I've discovered this behavior accidentally myself more than once, I just want to throw my two cents in before 2.0 releases. The interesting thing for me is not that the game hangs when asked to infinitely search a surface with no generated chunks. It's that it does so while consuming all available memory. This command will cause factorio.exe to stop responding and continuously allocate about 100MB/sec (on my machine) until you allow Windows to kill it.

Code: Select all

/c game.print(util.positiontostr(game.create_surface("test1", {terrain_segmentation=1, water=0, autoplace_controls={},default_enable_all_autoplace_controls=false, autoplace_settings={}, cliff_settings=nil, seed=0, starting_area=0, starting_points={}, peaceful_mode=true, property_expression_names={}}).find_non_colliding_position("car",{0,0},0,1)))

In my case, factorio.exe went from using 550MB to using over 10GB of memory in a couple of minutes. I assume this is because the game is keeping a list of all the positions in non-generated chunks that it has already checked. One question would be that if you're going to intentionally allow an infinite loop in the code, maybe it would be possible to prevent infinite memory consumption along the way?

FindNonColliding_memory.png (20.54 KiB) Viewed 407 times

FindNonColliding_Overflow.png (103.57 KiB) Viewed 407 times

Solutions

It is possible to determine that a surface has zero chunks generated and avoid initiated a guaranteed-infinite search with the following code:

Code: Select all

local k=0;
for chunk in game.surfaces["test1"].get_chunks() do
  k = k+1
end
if k > 0 then
  -- Search surface
else
  -- Return nil
end

Therefore, the game absolutely can know where the generated chunks are and if there are none. By and large, the behavior of meticulously searching non-generated chunks--without generating them--is not one that users would expect or ask for. It is still possible to not find a valid position if all chunks are impassible, but the search should always be finite because there are a finite number of chunks generated.

If the official position is that infinite execution and memory consumption are a risk you take when calling a search function with very large/no area boundary, then a warning is required on each such method, and I think it would make sense to simplify the above check with a "surface.is_empty()" operator--or remove boundless searches from parts of the API altogether. If people want to search the whole map, or search a donut map, and the API functions won't constrain themselves to generated chunks, then you should force the mod author to constrain it themselves with the chunk iterator.

(I know this has been brought up before as well back in 0.18 and was always declared not a bug, see viewtopic.php?f=23&t=82023&p=483184 )

Thank you for reading