Unifying and optimising delayed state changes.

[0xjove]

Is your feature request related to a problem? Please describe.
The code handling time based and delayed effects is ad hoc, inefficient and, most importantly, requires logic duplication in order to make things happen both inside and outside of the reality bubble, which has mostly lead to things only working in one or the other (e.g. fires, plants, bombs).

Efficiency wise we iterate through every active item every turn and most turns do nothing other than update their counters. This isn't a massive deal, I can't imagine it would be a problem in most games, but it does mean that merely having more items around you causes the game to slow down, even if they're not doing anything at the moment, and that a simple operation like "Do X in 40 turns" involves 40 updates of a counter. Worse, if there are multiple instances you have to update a separate counter for each one.

More importantly things like fires and plants should act consistently no matter where they are and a system that allows future developers of such features to write just a single piece of updating logic should be provided.

Describe the solution you'd like
A priority queue based implementation. Effects that are going to trigger something at some point in the future just add an event to the queue, with a priority of when it should occur. Each turn we check if anything in the queue is ready and perform that action. This removes the need to iterate through all the items every turn, replacing it with a simple heap peek, and means that each item doesn't need to store its own counter. Also, in removing the need for item_counter we remove the limitation that each item can only maintain a single counter.

Upon a map area leaving the reality bubble we remove its entries from the priority queue and store them. When the area is loaded again we merge this stored queue back with the main queue and then process events as normal. Because many of the events in the stored queue will have been set for turns that have already elapsed we'd expect to process multiple events at this point. Ephemeral effects (such as noise) should be suppressed while this is happening and care should be taken that some events don't spread beyond the confines of the newly loaded map. For instance if I create a line of flammable objects between two houses and set one on fire then stand in the other house with the fire just outside the reality bubble, stepping towards the flame should not cause the fire to catch up by suddenly engulfing the house I'm standing in. Better that it do something similar to what happens currently and pause the fire half way along the line.

Simple effects like plants growing are clearly trivial to model with this system. Effects like fire are likewise pretty simple, except you'd register events for both burning out and spreading and limit the effects as per above. Rotting is a little trickier in that you need to modify the priority of the rot event in response to temperature changes. If there are any other effects you anticipate may be a problem please, point them out and I'll explain how they'd be handled.

The system need not be used universally immediately. It can operate in tandem with the current systems and each effect moved over individually, though it's not until that's done that you'd get the efficiency benefits of not having to iterate through everything all the time.

Describe alternatives you've considered
None really. Delayed events is a very common and well understood problem. There are a lot of alternatives for little things, like how each individual event should operate, or if continual events (like funnels filling) should be folded together when a submap is loaded (more efficient but less accurate), but the general system is very standard.

I did consider modifying the event system found in event_manager and making it more general, rather than making a new system and eventually folding event_manager functionality into it, but the modifications required would basically amount to a rewrite and those events aren't high on the list of things as opposed to stuff like fire and plants that have noticeable effects.

Additional context
I'm quite happy to implement this. Part of the reason I'm interested in doing this is because #27226 looks very interesting, this provides the basis for an implementation of it, and it would be remiss not to fold other delayed state changes (of which the Gillespie algorithm is a special case) into the same system. This would mean a small extension to the above to allow for events that aren't removed and remerged as the reality bubble moves but that's hardly a problem.

I'm very busy slacking off at work atm but I'd be happy to come on discord or whatever later tonight to discuss it.

[kevingranade]

Efficiency wise we iterate through every active item every turn

You need to read the code more carefully, we do not iterate through every item every turn. it's not a timer wheel, but active items are inserted in different queues depending on their update frequency and most are only updated periodically.

a system that allows future developers of such features to write just a single piece of updating logic should be provided.

That would be nice, but fire in particular can't operate as a simple priority queue since it has the ability to spread over time. I outlined a system to manage it here.

Other systems also have various needs and constraints, making it unclear whether trying to force them to converge on a single system is worthwhile.

The Gillspie algorithm usage I proposed is a different thing entirely, it would be used to efficiently "catch up" map state, not schedule ongoing updates that occur while the player is nearby.

[0xjove]

we do not iterate through every item every turn

map::process_active_items. I understand this isn't EVERY item but any iteration is unnecessary here, especially as we only update counters on the vast majority of runs. There's also the iteration over fields, vehicles, factions events, missions etc. I only focused on items because it's a simple place to start. Also, now that I've actually profiled things I can say efficiency is not a concern here at all, things outside the reality bubble are more important.

Fire in particular can't operate as a simple priority queue since it has the ability to spread over time

That's not going to prevent it from being implemented like this. I'm not entirely sure where you see a problem so I'll just do some examples at the end.

The Gillspie algorithm usage I proposed is a different thing entirely, it would be used to efficiently "catch up" map state, not schedule ongoing updates that occur while the player is nearby.

That's what this is about! The key goal is to make catching up the map state and processing ongoing updates use the same system rather than requiring two implementations.

Examples, to keep it simple, we'll ignore everything else about fire and assume that it just repeatedly spreads once every 10 turns: I light a fire on turn 100. The fire adds an event for turn 110 to the queue. I run away from the fire and unload it, this causes any unloaded events, such as the one belonging to the fire, to be removed from the queue and stored alongside the map. I come back on turn 125. We merge the queues and process them. The top event is set for turn 110, that's less than 125 so we process it. It creates a new fire and that fire registers an event for turn 120. Then the event registers itself to happen again in 10 turns so that the initial fire keeps spreading. There are two events for turn 120 in the queue now. We process both, creating two new fires and adding the events for them for turn 130. That's greater than our 125 so we're done. At the end we have a fire that's spread to 4 squares and is ready to spread again in 5 turns time, just the same as if we'd stood next to it.

Of course that's a massive simplification. In reality fire will need events for fuel consumption, changing density etc. It should be noted that, like the Gillespie algorithm, events are not fired and forgotten. Changes to the state of the program can invalidate or reschedule them. This means that you have to be more active with regard to taking action on state changes, rather than waiting for them to be picked up, but that's not too difficult.

So let's look at a more realistic fire example. It still won't be describe everything about fire and I'll just guess the numbers but it gives an idea of how a more complex system would work: I start a fire. The fire registers an event for 1 turn from now to consume fuel. A density 1 fire has something like a 1/10 of spreading each turn. There's only one flammable tile next to it, so we'll consult the rng and decide that 12 turns is how long until it spreads there and register it as an event.

A turn passes and fuel consumption triggers, it grows to density two and so it reschedules its spreading event to be in just 6 turns time. There's no more fuel so we register a burnout event 50 turns in the future.

I pour a bottle of water on the fire. We're active about the fact that the state has changed so immediately we remove all of our fire's events and replace them with a burn out event for next turn. Likewise if I added more fuel or nearby flammable objects, we'd register consumption and spreading events then.

Note it's important for events to check for a valid state before they do anything. So for instance the spreading event should check that the fire is still burning and the tile is still flammable.

I will knock up a quick implementation for some of the stuff that's supposed to happen outside of the reality bubble. Fire should be the only thing that's at all a problem.