Replace mine/turret/gate polling with non-blocking (detect-only) collision layers

[klobor]

Disclaimer

I could be wrong in some of my assumptions here, but this is based on what I've gathered from forums and API docs. Please correct me where I'm wrong, though

TLDR

Polling expensive.
Collision cheap.
Detect stuff via special collision layer or special mask, that doesn't affect/impact/block anything, only detects and emits an event. Doesn't block movement or placing. Only notifies.

LR

My assumption is that collision check is less expensive (UPS-wise) than polling, especially if we get into hundreds or thousands of polls every tick.

Mines use polling to detect nearby enemies (even if it's once every 20 ticks, it's still polling. Unnecessary (often) polling. Avoidable polling).
Turrets use polling to detect nearby enemies (even if there are no more biters left to kill. Like, at all. Turrets will still be polling like crazy).
Gates use polling to detect incoming entities.
Bots use scheduled checks "are we there yet?" that fire with increasing frequency the closer they are to their target (if I recall corresponding FFF post correctly).

Instead of polling, add a flag to collision layer (or introduce a new type of layer, or add a flag to collision mask definition) that would not block pathfinding, would not block movement, would not block placing, would not block anything, zero impact whatsoever - it would only do one thing and one thing only: trigger an event(*).

That way mines won't have to poll: biter pathfinding ignores trigger layer, biter runs over a mine, biter collides with trigger mask, mine explodes.
Turret doesn't have to scan all the time - make trigger mask slightly larger (say, 20% larger) that targeting range (mask is rectangular, targeting is circular), and activate target scanning only when something collides with turret's trigger mask.
Same with gates. Even if the player/car/train is never coming to this station, gate will still be polling. Why? With trigger mask you don't have to poll if there is an incoming train nearby, it will tell you about it when it's close enough. Or maybe just make gate trigger mask large enough to account for fast entities, and only activate polling when an entity is within the gate's trigger mask - like with turrets.
Same with bots. You don't have to schedule checks "are we there yet" for every bot, you just give bot a direction, speed, and wait until it collides with a trigger mask. (well, in case of drones you still probably need a safeguard check in case destination got removed midflight, so drone doesn't overshoot too far).

And, most importantly, it will finally allow me to build a scalable, low-impact, fully event-based (instead of poll-based) stateless logistic delivery system, where delivery bots are made of tiny cars controlled entirely by traffic signs, have no state (no source, no destination, no schedule, no "are we there yet"), and "read" the traffic signs when they "collide" with them instead of having to poll next tile every tick

----

(*) trigger an event -- at minimum, trigger it once when two trigger masks collide for the first time.
Though ideally, there would be 3 events:
1) two masks collide for the first time
2) two masks that were previously intersecting are no longer intersected (Elvis has left the building!).
3) two or more masks are currently intersecting (triggered every N ticks, just like `on_tick` and `on_nth_tick`)

Additionally/optionally, a handy shortcut method could be added to an entity/object, a shortcut to/similar to `surface.find_entity/find_entities/find_entities_filtered` - "is there anything colliding with my trigger mask right now?"

----

That's it. Thanks for reading . Would love to hear some feedback on this.

[BraveCaperCat]

Note that collisions themselves have to be polled for (checked for collision) on every tick. it would only affect entities that poll for multiple different things at the same time, so it very likely wouldn't affect the base game. For mods, it would allow an increase in performance in some situations, but likely not very significantly when compared to entity caching methods.

[klobor]

Yes, but that's still faster than performing an entity search. And significantly faster than performing entity search using LUA. Well, at least I think it is only devs can say for sure

Besides, collision check is something that is already happening anyway. We're just getting a (almost) free piggyback ride on it.

[boskid]

Disclaimer
I could be wrong in some of my assumptions here, but this is based on what I've gathered from forums and API docs. Please correct me where I'm wrong, though

TLDR
Collision cheap.

Indeed you are wrong. Collisions are not cheap. There are 2 parts to collision checks: first is entity registering its presence in an area, this is proportional to the area entity wants to be "visible", and it must be updated every time entity moves. Second part is checking what entities are in the area - this is roughly proportional to the amount of entities in the area.

This proposal is completly detached from how collisions work and as such i am not seeing it being applicable.

[klobor]

Indeed you are wrong. Collisions are not cheap. There are 2 parts to collision checks: first is entity registering its presence in an area, this is proportional to the area entity wants to be "visible", and it must be updated every time entity moves. Second part is checking what entities are in the area - this is roughly proportional to the amount of entities in the area.

This proposal is completly detached from how collisions work and as such i am not seeing it being applicable.

Alright, thank you for clarifying this, really!

In that case, could you, please, clarify two more things:

1. Is this statement inaccurate? - "collision check is something that is already happening anyway. We're just getting a (almost) free piggyback ride on it"? If it's indeed inaccurate, how far is it from being accurate?

2. is running `surface.find_entities_filtered` in the area have the same performance impact as collision checks/collision event? If it's not, if there is indeed a noticeable performance gain when these two things are compared, then, maybe, just maybe, my proposal is not that much detached?...

[boskid]

1. Is this statement inaccurate? - "collision check is something that is already happening anyway. We're just getting a (almost) free piggyback ride on it"? If it's indeed inaccurate, how far is it from being such?

If i am reading this correctly, you are assuming that all entities do collision checks with anything else all the time. This would be completly incorrect. Collision checks are expensive and as such they are only performed when they are needed. Primary 2 cases when they are performed is when entity is being built (collision check will stop entity from being built) and when entity is moving (collision check will cancel movement and may trigger entity damage). Stationary entities that do not move do not need any collision checks, they only serve a passive role if another entity is moving and may collide with them.

2. is running `surface.find_entities_filtered` in the area have the same performance impact as collision checks/collision event? If it's not, if there is indeed a noticeable performance gain when these two things are compared, then, maybe, just maybe, my proposal is not that much detached?...

Collision checks have roughly the same performance cost as running `surface.find_entities_filtered` because collision checks are searching for other entities that occupy the same space while having matching collision layers.

--

You may not be seeing the collision costs too often because most of the entities that are moving around have small bounding boxes and as such they only look for colliding entities in a small area. Most expensive is trains movement because it involves 2 operations: checking for other entities in the area about the size as cargo wagon followed by entity movement which requires it to reregister on a surface onto an area of the same size.

Proposed solution to use collisions to improve performance simply fails because it is not possible to make both operations (registrations and checks) cheap at the same time if collisions would be expected to happen at a large distance. If a turret was expected to check for enemies nearby using collisions, if the range was 32 tiles, then unit movement would have to register its presence on an area about 64x64, and this would be happening every tick entity moves. Opposite would be that entity would register only on a small area but the turret would be doing search over large area, which would have to be an area 64x64 which is also expensive if it was to happen each tick. We have other methods of detecting enemies at a distance (chunks scale) and if a turret is far from any enemies, it wont even update so your proposal tries to optimize something that does not need optimization to begin with.

[klobor]

If i am reading this correctly, you are assuming that all entities do collision checks with anything else all the time.

Oh no, no-no, of course not! What I meant by that is when, say, a tank moves across terrain, each tick you perform a check if an entity collides with anything. As you said, "when entity is moving". This means that current state of things is "entity moved -> collision checked" -- this is what I meant by "already happening anyway". So far so good, right?

The thing that I do not know, though, is if you're performing collision check once for every collision layer of the moved entity, or is this somehow optimised? What I mean is: a tank can collide with a biter, with water, an assembler, a player, or another tank, and since water tile isn't an entity, it's probably not returned in filtered entities list?... So I assume you're performing a separate check for each layer?.. Or at least two checks: one for entities, and one for terrain collisions, like water (again, I'm guessing here)?...

Now, you said, "collision check will cancel movement and may trigger entity damage" -- and here's where my suggestion fits in: when collision detected on a special layer (just like water, but invisible, virtual layer) instead of cancelling movement, fire an event. Just for collisions that happen on that layer. That's it. Really. Sounds simple enough?..

Collision checks have roughly the same performance cost as running `surface.find_entities_filtered` because collision checks are searching for other entities that occupy the same space while having matching collision layers.

Yet collision checks happen at the engine level, which is by definition faster than calling `surface.find_entities_filtered` on the LUA level, is it not?

Oh, and water tile isn't an entity (at least I hope it isn't ), so just as a side note: you don't really need to retrieve a whole entity that matches the intersection box from the registry, just to know if collision have happened. You just need to know if there are any overlapping coord ranges, or even a bitmask (or, rather, thirty two 32-bit-sized bitmasks), as an early bailout. And only retrieve entity if there actually is something to retrieve at these. But I digress. You said:

Opposite would be that entity would register only on a small area but the turret would be doing search over large area, which would have to be an area 64x64 which is also expensive if it was to happen each tick.

That's actually what I thought was happening after reading this thread: viewtopic.php?t=101153! Though I admit, that was pretty silly of me to think it stayed that way for this long.
But still, I saw that a mine checks for entities every 10 ticks and I thought "huh?.. but why??.." - in my defence, it not clear if mines check for entities every 10 ticks all the time? Or only if there is a hostile force within 1-chunk radius? Or only if there is a hostile entity within `trigger_collision_mask`? Does the mine scans even if there is nobody within the `trigger_collision_mask`? How does `trigger_collision_mask` even works then?.. And what's it for? So many questions, so little answers...

All that makes for a huge difference, and it isn't clear from that conversation what's actually _is_ happening under the hood, especially considering the age of that thread.

So, as I said, with the lack of knowledge about inner workings all we can do is guess...

If a turret was expected to check for enemies nearby using collisions, if the range was 32 tiles, then unit movement would have to register its presence on an area about 64x64, and this would be happening every tick entity moves.

Is that's the current implementation of collision detection? That's... rough. Ok, at this point perhaps it's better if I explain in more detail what I thought is happening during entity movement and collision detection process.

I thought it's pretty straightforward: I thought there is a bigger registry of boxes for static objects (infrequent updates, lots of data), and a smaller registry for entities that can move (frequently updates, smaller dataset). When entity moves, it's own collision box is checked against both registries. There are many different ways to organise it, of course: some are slow to write but fast to read, some are fast to write but slow to check, some are balanced, some are just plain O(n2) bananas. In any case, I assumed this check is simple and fast. Now, reading your answer with "if the range was 32 tiles, then unit movement would have to register its presence on an area about 64x64, and this would be happening every tick entity moves", this doesn't look like simple. This looks very opposite of simple, tbh. Maybe it's blazing fast, I don't know the implementation details, but it definitely doesn't look simple.

So, what I thought would happen in the context of my suggestion about trigger collision box/layer:

Let's say there is a turret belonging to player A and a tank belonging to player B that is moving towards the turret.
Tank has a trigger collision box of 3x3 tiles (I don't remember the exact values, so let's assume 3x3 merely for example purposes).
Turret has a trigger collision box of 64x64 tiles.

Tank moves towards the turret.
Tank checks if it's own trigger collision box intersects with any other trigger collision box.
Finds none.
Updates own box info in the registry.
Tick.
Tank moves closer.
Tank checks if it's own trigger collision box intersects with any other trigger collision box.
Finds none.
Updates own box info in the registry.
Tick.
Tank moves more closer.
Tank checks if it's own trigger collision box intersects with any other trigger collision box.
Check detects that there is, indeed, an intersection detected. No object info yet, just a boolean confirmation that some intersection exists.
Only then tank asks for the actual object whose trigger collision box intersects with tank's one, updates own box info in the registry, notifies that object via event: "Hey, I'm here!", and notifies the LUA subscribers for the corresponding event with appropriate message and payload.
Turret activates and starts scanning the surrounding area (because, well, boxes are rectangular and turret radius is circular).


As for the collision registry itself, again, I don't know the details of the current implementation, but this is something I've used in the past, and it proved to be extremely efficient for both writes and reads (sub-ns read/write and mere <20mb of memory for a 10k*10k map with thousands of units): so, the turret's box spans over multiple chunks. Each chunk is a grid of 32x32 tiles. This grid can be represented as a list of 32 bitmasks, each bitmask is 32 bits long. Each bit is a tile. I know that actual collision boxes (masks) are float-based, but for the purpose of "check fast, bail early" it can be denormalized and stored in the form of bitmask as merely an indicator of "is there anything at all in that tile worth checking?". There are 3 registries: smaller one for moving objects that updates more frequently (a plain spatial hash with tile int coords as keys and array of objects as values), same but bigger one for static objects, and another bigger one for static objects but bitmask-based. Yes, this adds an extra step to the "registration" process (I assume that by that you mean "changing the collision box entry of the entity in the collision boxes registry" or something like that?...), but for static objects it happens only when they are placed. And it also makes it significantly cheaper to check if there is anything to collide with in the first place. Only when there is, we get a list of colliding candidates from the spatial hash, and then compare their collision boxes at a float level - which happens orders of magnitude less frequently than a basic anything/nothing check. With all that said, when turret is placed, quickcheck-bitmask-map is populated with "1" for tiles where the turret's trigger collision mask reaches, and the rest kept as "0" (or whatever it was before turret placement). When tank moves, tank's trigger collision box is converted to a set of bitmasks too, then checked against the surrounding quickcheck-bitmask-map lines. This should typically compile to a single CPU bitwise AND instruction followed by a zero test for every 32-bit long bitmask. 3 rows (tank's size), 6 CPU instructions. Slightly more, if tank's coords span over multiple chunks. Sounds fast enough? . If & returned `0` - then you already know you didn't collide! If not, only then we get the object from spatial hash map, and compare it's intersection between the trigger collision box of the tank and trigger collision box of the turret - for float-level precision.

Anyway, I hope I made my suggestion at least a little bit clearer With all that said, do you still think my idea is not beneficial in any way? (though I do see at least one benefit in any case: it would finally give modders a reasonable way to tell when an entity arrived on a specific location! )