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.