Requesting O(1) lookup of entities by type or name

[sparr]

surface.find_entities_filtered{type=...} is so seductively simple, but the runtime seems to scale with the number of entities on the surface. I've lost count of the number of mods I've seen that end up watching for built/mined/etc events to maintain a list of the entities they care about in a global table to avoid needing to search for them. Maybe a mod could tell the game that it's going to be doing a particular kind of lookup with regularity, and that would prompt the game to maintain its own lookup table to make those filters O(1) instead of O(n)?

This would reduce mod complexity and save file size.

[Rseding91]

There's no way for the game to maintain O(1) anything when it comes to lookup tables that wouldn't have a constant memory and runtime performance overhead to implement.

[sparr]

Of course. But those memory and performance costs would be less than the same costs in a lua script. I am suggesting that a script be able to "register" some lookup needs, and then the game manages the lookup table, which would be faster than a hundred mods re-inventing the same wheel in a less efficient manner.

[bobingabout]

it does actually feel pretty limiting that you don't have access to say... game.entities[].

I would love to do things like, iterate through game.entities and do stuff, but at the very least, you could access game.entities[id], or filter game.entities by type="boiler", name="boiler", rather than having to scan the whole map to find them first, if, say, you wanted to apply a script to something.

Heck, even if it was game.entities.type.name[] it would be useful.
And game.surfaces[].entities... with the same structure to filter by surface.
Also game.forces[].entities... would be good too, filter everything owned by that force.


Honestly, when I first started scripting in my mods, I expected this to exist, and was confused and dumbfounded when I found the only way to access the information I was looking for was to try and do a full map scan...
Which in itself wasn't easy to do because you could only scan by area or chunk at the time, and didn't have any predetermined way to figure out how big the map actually was. I think I ended up doing a chunk scan, and iterating through all the chunks, but as a result of my comments at the time, the full map scan was added to the search function.

[sticklord]

Isn't that what find_entities_filtered does? Goes through a list of all entities and returns all matching entities?

[eradicator]

I'm not sure what exactly you're trying to achieve. If a mod uses on_built and on_mined (etc) to maintain an internal list of exactly the entities it needs then you already have a table that can be iterated in reasonable time. If the game supplied such a table, for example by entity name, then wouldn't that imply that the engine has to fetch all entity references from the c side and move them to the lua side on every iteration of the loop? (That is if you don't want to default store all those tables in the lua state of every mod.)
Furthermore from my personal experience i have not encountered any usecases where i just need a plain list of "entities of prototype name abc", in all cases where i need to iterate over such a list i also store additional data in that list related to each entity. And that usecase wouldn't benefit at all from your suggesteion as i understand it. The only edge case i've ever come across was when i wanted to fetch an entity by it's unit_number, but that would have the same c <-> lua transfer penalty as far as i understand even if it was possible.

[ratchetfreak]

Isn't that what find_entities_filtered does? Goes through a list of all entities and returns all matching entities?

He wants that its performance is better when the filter includes type (or other specific properties).

[sparr]

Furthermore from my personal experience i have not encountered any usecases where i just need a plain list of "entities of prototype name abc"

I promise you there are dozens, if not hundreds, of existing mods that do exactly that. A list of every inserter, a list of every belt+splitter+underneathie, a list of every chest, a list of every pipe, a list of every turret, a list of every [custom entity created by the same mod], ...

I'm not sure what exactly you're trying to achieve. If a mod uses on_built and on_mined (etc) to maintain an internal list of exactly the entities it needs then you already have a table that can be iterated in reasonable time. If the game supplied such a table, for example by entity name, then wouldn't that imply that the engine has to fetch all entity references from the c side and move them to the lua side on every iteration of the loop? (That is if you don't want to default store all those tables in the lua state of every mod.)

I'm trying to achieve a few things.

First, I want to eliminate cases where a mod author makes a mistake in reinventing this particular wheel. It's easy to get one of the "(etc)" wrong, if you aren't aware that you need to monitor the fifth or sixty event on that list.

Second, I want to handle cases where other mods create entities without raising an event, or when raising a script_raised_built with non-standard event data.

Third, I want to make it easier for mods to utilize this functionality without having to reinvent the wheel or copy/paste chunks of code from another mod they don't necessarily entirely understand.

Fourth, I want maintaining the lists to be faster, running in C instead of in Lua.

Fifth, I want to save cpu time when two different mods want the same list.

I am not proposing that the game preemptively maintain every possible lookup table. What I am suggesting is that a mod could register a request for a lookup table, and then the engine would build it and keep it updated, and use that table when responding to entity searches or possibly providing direct access to that table some other way.

[eradicator]

Furthermore from my personal experience i have not encountered any usecases where i just need a plain list of "entities of prototype name abc"

I promise you there are dozens, if not hundreds, of existing mods that do exactly that. A list of every inserter, a list of every belt+splitter+underneathie, a list of every chest, a list of every pipe, a list of every turret, a list of every [custom entity created by the same mod], ...

Ueer. Hundrets? Got any good examples? Maybe i'm just uncreative, but i can't think of that many reasons to keep a list of "every x" without any associated data. And if it turns out to be just "whoever wrote the mod had no idea what they're doing" then chances are they won't migrate to your new solution.

As for the actual feasibility of implementing this and if it would have any net performance benefits... i'll leave that to one of the devs to ponder.

[sparr]

https://mods.factorio.com/mod/BurnerLeech by none other than Klonan himself, keeps a list of every burner-inserter built

https://mods.factorio.com/mod/entity-symmetry by myself, needs a list of symmetry-center entities

Those are the two that were directly on my mind when I made this post. As to the others...

Here are some relevant hits from the first 2 out of 100 pages of results at https://github.com/search?p=3&q=global+ ... =%E2%9C%93 :

https://github.com/Daedeross/Factorio12 ... ua#L12-L36 tracks every "OilSteamBoiler"
https://github.com/cookta2012/ShadowCom ... ua#L11-L23 tracks every "hybrid-wall" and "hybrid-gate"
https://github.com/bloc97/Factorio_Vani ... lua#L8-L21 tracks every "wind-generator" and "tidal-generator"
https://github.com/FEIGN/feignaddons-wa ... ua#L10-L32 tracks every "feignaddons-water-powerstation"
https://github.com/gorre9090/gorre9090s ... ua#L14-L25 tracks every "item-destroyer", and the author forgot to handle robot built entities
https://github.com/Thalassicus/Factorio ... ua#L16-L28 tracks just positions for every "radar-outpost", which *might* be faster to use the system proposed here

As to "why?", the general use case is for a mod that adds some new ongoing behavior to a type of entity, which means iterating over all of those entities in on_tick or every_nth_tick, which are terrible places to use find_entities_filtered across a whole surface.

[sparr]

Still wishing for this feature. It would simplify so many mods, and eliminate bugs in a lot of them.