B Info Module System Tidbit Tuesday: Stochastic Triggers

Currently viewing this thread:

motomataru

Squire
M&BWBVC
Best answers
0
I thought I'd share a few bits from Viking Conquest. If there is something particular you'd like to see, let me know.

For this inauguration, I present stochastic triggers, a probabilistic technique for reducing lag. It helps with larger mods, as many triggers require exponentially more processing power as material grows. For example, faction AI requires each faction to consider every other -- an unavoidable nested loop. In Native, with six factions, this meant under forty loops. This is run seventy times to randomize the start for new games, or about 2500 loops. In Brytenwalda, with thirty two factions, the same script looped about 72000 times. Hence the infamous "wait five minutes" message in early versions of that mod.

The idea in triggers is, instead of running all instances once every so many frames, spread the processing evenly over all frames. An observant coder would notice this doesn't reduce processing, but it keeps it from happening all at once and potentially causing a lag.

Stochastic triggers have the added benefit of injecting a bit of controlled chaos into the game. With them, one never knows the exact result, but can control the expected, overall result.

Take for example, this weekly trigger:
Code:
  # Refresh merchant inventories
   (168,
   [
      (try_for_range, ":village_no", villages_begin, villages_end),
        (call_script, "script_refresh_village_merchant_inventory", ":village_no"),
      (try_end),
    ]),
Instead of looping through all the villages every week, we'll split them over the entire week. If we want every village to take an average of a week to refresh its inventories, we simply divide that period by the number of villages. So say one has 110 villages, as in VC. We simply replace the loop for a random function and put in our new interval.

Code:
  # Refresh merchant inventories weekly ON AVERAGE
   (1.5,
   [
      (store_random_in_range, ":village_no", villages_begin, villages_end),
        (call_script, "script_refresh_village_merchant_inventory", ":village_no"),
      # (try_end),
    ]),
Now neither we nor the players will know exactly WHEN a village might have new items. It might be in 1.5 hours. It might be in four weeks. But on AVERAGE it will be in one week. Plus all the villages are not processed together at the very moment every OTHER weekly trigger in the game is firing. In fact, the same technique applied to the other triggers of the same period virtually guarantees they will no longer be doing their processing at the same time.

Many of these loops are buried in scripts which are easy enough to restructure to place the loop in the trigger and pass in the loop parameter.

There are situations for which one shouldn't apply this technique.
1. The function depends on some sort of aggregation/summary/averaging/initializing. This is typical of AI functions, where data on all the actors is collected first.
2. The function causes lag even when split up. We found this true of faction AI. Instead of one big lag every six hours, we were getting 21 small lags every .29 hours. We decided the one big lag was better.
3. Minimum interval seems to be one game minute (.017 hours). Beyond that level, one must apply loops.
4. For some other reason, one would like all instances to be considered together. Wages for example. But then, is it really a problem that one lord collects four wages one particular week while another collects none for four weeks? Or is that something that adds variety and interest to the game?

Results...
Before: https://www.adoberevel.com/shares/61c959a60ddd4b64bf9b368aac4b796a/albums/8240968356ff4dd8bd8ac2d111b42681/assets/6c83b1852b2c4017a839f66a0e722969
After:
https://www.adoberevel.com/shares/61c959a60ddd4b64bf9b368aac4b796a/albums/8240968356ff4dd8bd8ac2d111b42681/assets/2441e2fe38994982b3416060ad7af0ce

There is a problem with stochastic triggers: team members without a degree in something requiring statistics have trouble fully understanding or trusting them.  :smile:
 

fladin

Baron
M&BWBWF&SNWVC
Best answers
0
In addition to performance improvements, I  really liked  the concept of random events ...
Thanks
 

Lav

Sergeant Knight at Arms
M&BWB
Best answers
0
The problem is, team members with sufficient knowledge of statistics might have trouble trusting these methods either. :smile:

When it comes to AI, it is not a good idea to randomize AI recalculation times without providing lower and upper intervals for such recalculation.

Because you don't want an AI to oscillate meaninglessly between two (or more) possible courses of action without committing at least some time and effort to at least one of them.

And neither do you want an AI to stupidly follow some course of action that has long been rendered obsolete by the ever-changing situation simply because the randomizer for some reason consistently failed to pick that AI for a long time.
 

Cozur

Grandmaster Knight
WB
Best answers
0
What are the main causes of lag when you have A) more factions and B) more parties? Which triggers?
 

Lionheart2

Veteran
Best answers
0
Interesting. I was already planning to drastically increase randomization in Reborn, and now I know that it increases performance as well.  :grin:
 
Best answers
2
Very interesting, brings me back to my days of studying weird curves and greek letters.  :razz:

I'd considered something like this but never got the kind of lag to justify restructuring all those scripts, but i thought (at the time) it'd be better to cycle through the towns over time rather than at random to increase efficiency. So some sort of global variable per cycle that increases by one each time the trigger's fired, and reset at the end of the range.

Staggered intervals might help too -- having small differences between the intervals would keep the stutter on key frames below noticeable amounts, assuming the player isn't holding ctrl-space.
 

Somebody

Code Pope
Baron
WBWF&S
Best answers
1
There might be immersion problems where the player is involved, wondering why their village only grows cabbages. When players don't rampage around the countryside collecting taxes and butter it would be best to only apply the trigger to villages outside the immediate sphere of influence of the observer - they won't ever need to see what a village produces if they aren't in that part of the map. Entropy counters as some of the posters recommended would be good, using long fixed cycle that apply bias in addition to shorter randomized ones.
 

Lav

Sergeant Knight at Arms
M&BWB
Best answers
0
jacobhinds said:
Very interesting, brings me back to my days of studying weird curves and greek letters.  :razz:

I'd considered something like this but never got the kind of lag to justify restructuring all those scripts, but i thought (at the time) it'd be better to cycle through the towns over time rather than at random to increase efficiency. So some sort of global variable per cycle that increases by one each time the trigger's fired, and reset at the end of the range.
This is exactly how lord AI is processed in Native. :smile:

Somebody said:
There might be immersion problems where the player is involved, wondering why their village only grows cabbages. When players don't rampage around the countryside collecting taxes and butter it would be best to only apply the trigger to villages outside the immediate sphere of influence of the observer - they won't ever need to see what a village produces if they aren't in that part of the map. Entropy counters as some of the posters recommended would be good, using long fixed cycle that apply bias in addition to shorter randomized ones.
There is actually no need to waste processing cycles on merchant inventories at all. Merchants only exist for player's sake, their inventories do not participate in any economy calculations. So the solution is to scrap those triggers entirely and only regenerate merchant inventory the moment player arrives to town/village. Just keep track of the last time player arrived and use the time passed to determine the degree to which the inventory must be refreshed.

Lionheart2 said:
Interesting. I was already planning to drastically increase randomization in Reborn, and now I know that it increases performance as well.  :grin:
Read motomataru's post carefully. Tricks he's describing do not improve overall performance, in fact they probably slightly reduce it. But they make the game run smoother and with less hiccups, resulting in more pleasant playing experience.
 

motomataru

Squire
M&BWBVC
Best answers
0
Cozur said:
What are the main causes of lag when you have A) more factions and B) more parties? Which triggers?
Because I changed almost everything, I only noticed the gorilla in the code: faction AI -- due to the fact that it already has plenty of debug messages in it. If one judges impact by the number of lines of code, then many of the simpler triggers probably do not have much of an impact -- but even then, if several are piled up on the same interval, this technique would help. Another beast is the 1 hour #process alarms trigger, the effect of whose modulus technique is undone by adding on two more unrelated loop functions.

By the way, speaking of faction AI, the 7 hour # Decide vassal ai trigger is redundant. It probably made a little sense back when script_recalculate_ais was being called only every 23 hours. I decided to eliminate the independent one, as it would be strange to have the faction call off a siege but then have the lords stick around.

jacobhinds said:
I'd considered something like this but never got the kind of lag to justify restructuring all those scripts, but i thought (at the time) it'd be better to cycle through the towns over time rather than at random to increase efficiency. So some sort of global variable per cycle that increases by one each time the trigger's fired, and reset at the end of the range.
This is used for the half hour #Individual lord political calculations. The downside is, one then has the overhead of managing a global like this for every loop treated.

Another technique in Native is to use modulus. This is applied in the very expensive 1 hour  # Process alarms trigger. It also depends on managing a global, so it is basically the same at the extreme of modulus = instances as tracking which instance was called last.
 

Swyter

Grandmaster Knight
M&BWBWF&S
Best answers
0
Great, great. Fantastic read, a nice surprise for once.
Also... Hi, motomataru!

I didn't know that you were in charge of the Viking Conquest coding. Kudos.