Sporadic updates for active items.

[kevingranade]

This is the higher-level solution to how much time the game spends updating active items.

Some active items, like bomb timers MUST be updated every turn, but others, like rotting food and regenerating zombies, can afford to wait 10 or even 100 turns between updates, and these items are much more common.

What we need to do is establish n containers, where n is the longest number of turns a "low priority" active item can go without an update, and evenly* distribute the low priority active items across them. Then each turn we update the items in one of these containers instead of all of them, cutting the update time by 10 or even 100 fold.

If necessary we can have several tiers of prioririty, or even an arbitrary number since each will just be assigned a number of turns that it can go without update.

*Especially if we end up with an arbitrary number of priority levels, the best option for distributing items within a level may be to chose a random container at each insertion, this would prevent a degenerate case where we have one item in each of several priority levels that share a common multiple, which will occasionally sync up, causing one really slow turn. Another mitigation for this is to only allow n to be a prime number.

[boydkr]

I've been thinking that you could split things out into N different priority groups, and have each group update every M turns, where M is a prime number

i.e. have groups that update every [1, 2, 3, 5, 7, 11, 13] turns

Super important things could update every turn, and stuff like food spoilage could update every 13 turns. You could potentially also randomly distribute items from the "13" bin into offset "13" bins, but even having them all update on the same turn would reduce/distribute loads of processing power (and it would be a lot easier to implement).

[kevingranade]

Having every food item update every 13th turn isn't much of an improvement,
it means every 13th turn lags noticeably, especially as we probably
continue to scale up the number of items that count as active (e.g. funnels
would go on here too)

[boydkr]

except if food was every 13 turns, funnels were every 11 turns, zombie revification was every 17 turns, etc, you would get much better performance than today where everything happens every turn.
Maybe even some foods could be in different bins based on rate of spoilage?

[BevapDin]

Considering that most of the time is spend copying/moving the item out and back into the items-vector, it might be enough to change that vector into a list (as already planned) and use std::list::splice to move the item into a temporary list.

That would remove the item copy/move operations entirely and only leave some pointer access.

Another thing: move all active items at the front of the list, so the loop can stop when it reaches the first inactive item.

Also regarding bins with items to be processed every N turns: how to reference the items in those bins? The item vector is available to every piece of code and can be changed from there, so an index won't stay valid, same with list-iterators. That btw. would be a good use for a i_at-wrapper that handles this.

Or should those bins replace the item vector as it is now? Than one has to change all code that uses it, which is quite a lot.

[kevingranade]

If the item vector becomes a list, we can store references into it.
(Either pointers, or better, iterators), then deletion just has to check
for active-ness as well.
This also requires other overhead, like adding/removing items from these
lists on map save/load, but that shouldn't be that big a deal, and can be
amortized if necessary.