Concerns about entity.is_registered_for_* methods

[mrvn]

is_registered_for_construction() → boolean

Is this entity or tile ghost or item request proxy registered for construction? If false, it means a construction robot has been dispatched to build the entity, or it is not an entity that can be constructed.

is_registered_for_deconstruction(force) → boolean

Is this entity registered for deconstruction with this force? If false, it means a construction robot has been dispatched to deconstruct it, or it is not marked for deconstruction. This is worst-case O(N) complexity where N is the current number of things in the deconstruct queue.

Parameters
force :: ForceIdentification: The force construction manager to check.

is_registered_for_upgrade() → boolean

Is this entity registered for upgrade? If false, it means a construction robot has been dispatched to upgrade it, or it is not marked for upgrade. This is worst-case O(N) complexity where N is the current number of things in the upgrade queue.

is_registered_for_repair() → boolean

Is this entity registered for repair? If false, it means a construction robot has been dispatched to upgrade it, or it is not damaged. This is worst-case O(N) complexity where N is the current number of things in the repair queue.

First off O() notation is always worst-case so that part is redundant.

How come is_registered_for_construction does not take O(N) while all the others do? Is that an oversight?

I'm afraid of using these methods because with for example 10k deconstruction markers the worst-case would really sucks making my mod unusable. When is it not the worst case? What is a good case? Are entities listed per chunk so the worst case is only when all marked entities are in the same chunk? What is the deal there?

Unless the worst-case is really unlikely those methods would be useless and I can't believe there isn't a better method to check this. What do you do when an entity is mined, revived or deconstruction/upgrade canceled? I can't believe canceling deconstruction on entities would be O(n) as that would freeze the game for extended periods. I've marked and undone harvesting big forests and the game didn't freeze. I've placed and undone blueprints with 100k landfill before and the game didn't take longer to undo than do, certainly not 100000 times as long. Whatever method is used to quickly remove entities from lists should also be used to just check if they are in the list.

PS: I really just want to know if a bot is scheduled for a ghost or deconstruction. Knowing if it's a personal bot or not or how far away / where the bot is would be an added bonus.

[Rseding91]

is_registered_for_construction

This is O(1) because the only things which can be registered for construction are ghosts and item-request-proxies. Both of which have an intrusive list node that's used to have them be in the construction list. So checking if their node is linked (O(1)) is all that has to be done.

is_registered_for_deconstruction
is_registered_for_upgrade
is_registered_for_repair

These are all O(N) because virtually any entity can be marked for deconstruction and so we don't want to pay the memory overhead of making every entity include the intrusive list node when 99%+ of the time a given entity will not be marked for deconstruction. The same reasoning applies to things marked for upgrade and things to-repair.

What do you do when an entity is mined, revived or deconstruction/upgrade canceled? I can't believe canceling deconstruction on entities would be O(n) as that would freeze the game for extended periods.

That's what it is. Simply put: computers are really fast. A linear scan to find a given entity in the list and remove it is what happens when you cancel any of these operations.

PS: I really just want to know if a bot is scheduled for a ghost or deconstruction. Knowing if it's a personal bot or not or how far away / where the bot is would be an added bonus.

An entity being in one of those lists would mean "no". Once a robot takes the job it's removed from that list. The game does not need to do that operation (find which robot will work on a given entity) frequently (if at all from what I can remember).

[mrvn]

is_registered_for_construction

This is O(1) because the only things which can be registered for construction are ghosts and item-request-proxies. Both of which have an intrusive list node that's used to have them be in the construction list. So checking if their node is linked (O(1)) is all that has to be done.

is_registered_for_deconstruction
is_registered_for_upgrade
is_registered_for_repair

These are all O(N) because virtually any entity can be marked for deconstruction and so we don't want to pay the memory overhead of making every entity include the intrusive list node when 99%+ of the time a given entity will not be marked for deconstruction. The same reasoning applies to things marked for upgrade and things to-repair.

What do you do when an entity is mined, revived or deconstruction/upgrade canceled? I can't believe canceling deconstruction on entities would be O(n) as that would freeze the game for extended periods.

That's what it is. Simply put: computers are really fast. A linear scan to find a given entity in the list and remove it is what happens when you cancel any of these operations.

PS: I really just want to know if a bot is scheduled for a ghost or deconstruction. Knowing if it's a personal bot or not or how far away / where the bot is would be an added bonus.

An entity being in one of those lists would mean "no". Once a robot takes the job it's removed from that list. The game does not need to do that operation (find which robot will work on a given entity) frequently (if at all from what I can remember).

I was hoping that maybe there would be an alternative way other than scanning those lists.

What about the red "X" marks on the map when something is scheduled for deconstruction? Can't they have an intrusive list and be used as deconstruction proxy for the entity? Same for the yellow circle for upgrades.

I want to patch the bluebuilt mod, which automatically revive ghosts or deconstruct stuff near you, to not work on something that already has a bot assigned to it, at least not at first. That way personal roboports and bluebuilt could work together instead of fighting over ghosts. Checking every X in the players reach with an O(N) operation would be kind of costly.

PS: Every time an entity is deconstructed or destroyed that has a red X you have to check if it's in the list and if not find the bot that is assigned to it. Seems like an O(1) operation would speed up the game there.

[Rseding91]

What about the red "X" marks on the map when something is scheduled for deconstruction? Can't they have an intrusive list and be used as deconstruction proxy for the entity? Same for the yellow circle for upgrades.

Those are properties of the entity itself: 1 bit that says 'somebody has me marked for deconstruction' and 1 bit that says 'somebody has me marked for upgrade'. Who or if a robot has already been picked to do the work the entity doesn't know.

PS: Every time an entity is deconstructed or destroyed that has a red X you have to check if it's in the list and if not find the bot that is assigned to it. Seems like an O(1) operation would speed up the game there.

We have to check if it's in the list but we don't check what robot might be working on the entity. We just destroy the entity and the next time the robot updates it sees "oh my target vanished" and stops trying to do anything with it.

[mrvn]

What about the red "X" marks on the map when something is scheduled for deconstruction? Can't they have an intrusive list and be used as deconstruction proxy for the entity? Same for the yellow circle for upgrades.

Those are properties of the entity itself: 1 bit that says 'somebody has me marked for deconstruction' and 1 bit that says 'somebody has me marked for upgrade'. Who or if a robot has already been picked to do the work the entity doesn't know.

No space left for another bit that says a robot has it?

PS: Every time an entity is deconstructed or destroyed that has a red X you have to check if it's in the list and if not find the bot that is assigned to it. Seems like an O(1) operation would speed up the game there.

We have to check if it's in the list but we don't check what robot might be working on the entity. We just destroy the entity and the next time the robot updates it sees "oh my target vanished" and stops trying to do anything with it.

Do you at least just mark the entity invalid and the next time something goes through the list all the invalid entities are removed along the way? If not then that might be a simple optimization.