Rare specials accidentally became too frequent

[hexagonrecursion]

Is your feature request related to a problem? Please describe.

Specials with UNIQUE or GLOBALLY_UNIQUE flag define how frequently they should spawn. For example "occurrences": [ 2, 100 ] means the special should spawn in about 2 put of 100 overmaps. This allows some specials to be relatively rare and others to be relatively common.

overmap::place_specials() used to simply roll x_in_y(...) (e.g. 2 in 100) for each UNIQUE or GLOBALLY_UNIQUE special to decide whether to attempt to place it on the current overmap or not. This attempt is not guaranteed to be successful and the success chance depends on how picky the special is - some specials find valid places to spawn easier than others.

There were two issues with this implementation:

1. The overmap_terrain_coverage test only generates 300 overmaps. By my calculations there is about 2% chance that at least one spacial will fail all 300 x_in_y rolls (an outlier, but more common than we would like):

   git switch --detach cdda-experimental-2024-05-10-0048
   shopt -s globstar
   jq -n 'reduce (inputs | .[] | select(.flags // [] | contains(["UNIQUE"])) | .occurrences | select(.[0] > 0) | .[0]/.[1] | 1 - . | pow(.; 300) | 1 - .) as $item (1; .*$item)' data/json/overmap/overmap_special/**/*.json
   0.9837840236159145

2. Because some specials are harder to place, their real frequency was lower than the intended frequency from their defenition.

#73339 attempted to improve this:

I'm tracking the rate of occurrence of the unique specials, and if they are occurring more often than specified, it dials down the chances of selecting that special again, and if the rate of occurrence is lower than configured it increases the rate of occurrence.

Here is the formula we are now using: x_in_y(X/special_count, Y/overmap_count) (i.e. rng_float( 0.0, 1.0 ) <= (X/special_count) / (Y/overmap_count)), where the intended frequency is X in Y (e.g. X=2, Y=100), special_count is the number of times the special was successfully placed (or 1 if the number is zero to avoid div by zero), overmap_count is the number of overmaps generated so far (or 1 if the number is zero).

A bit of algebra:

(X/special_count) / (Y/overmap_count) == (X/Y) * (overmap_count / special_count)

I see two issues in the current implementation:

1. Despite 73339 claiming that the chance of occurrence is dialed down for specials that happen to spawn more frequently than intended, it never dials the chance of occurrence below X in Y. Proof:

   overmap_count >= special_count (because we place at most one unique special per overmap)
   overmap_count / special_count >= 1
   (X/Y) * (overmap_count / special_count) >= X/Y
   

2. This change had accidentally rebalanced rare specials to be much more common than intended:

   Notation: X_eq/Y_eq is the rate of occurrence of the special at equilibrium
   
   To determine the relationship between X_eq/Y_eq and X/Y
   we replace overmap_count with Y_eq and special_count with X_eq
   and make the observation that the resulting probability has to be X_eq/Y_eq:
   
   X_eq / Y_eq == (X/Y) * (Y_eq / X_eq)
   (X_eq*X_eq) / (Y_eq*Y_eq) == X/Y
   X_eq / Y_eq == sqrt(X/Y)
   i.e. the equilibrium of the rate of occurrence is actually square root of the intended rate of occurrence
   
   This means that (after a large enough number of overmaps are generated) the
   rate of occurrence of a spacial that is supposed to spawn in 1 out of 100 overmaps
   will actually be 1 in 10
   

@kevingranade

Solution you would like.

1. I propose we associate three counters with each special:
   • x_remains (initially X)
   • y_remains (initially Y)
   • to_place (initially 0)
2. This counters should be global and persist from the generation of one overmap to the next
3. overmap::place_specials() will roll x_in_y(x_remains, y_remains) On success both x_remains and y_remains are decremented by one and to_place is incremented by one. On fail y_remains is decremented by one. This is equivalent to drawing without replacement from a deck of Y cards out of with X contain the special and the rest are empty
4. If y_remains is zero, we reset x_remains and y_remains to their initial values
5. If to_place is not zero, we try to place one instance of the special on the current overmap. If the placement is successful, we decrement to_place by one

• Unlike the current solution, this implementation would achieve the intended rate of occurrence
• If we can count on Y to never be more than 100, random failures from the overmap_terrain_coverage test should become a thing of the past. Even a 1 in 100 special is guaranteed to be drawn within the first 100 overmaps generated by the test because we draw without replacement. After that we will stubbornly try to place the special on each of the remaining 200+ overmaps until we succeed.

Describe alternatives you have considered.

Another approach I have considered was to adjust the current formula to have the correct equilibrium:

rng_float( 0.0, 1.0 ) <= (X*X)/(Y*Y) * overmaps_plus_1 / specials_plus_p
where overmaps_plus_1 is the number of overmaps generated so far plus one
and specials_plus_p is the number of times the special was successfully placed plus X/Y

This should have:

1. Probability of success on first spawn == X/Y
2. Equilibrium == X/Y

The downsides:

1. The success of the overmap_terrain_coverage test is not guaranteed

2. This approach reduces, but does not eliminate the effect that the probability of successful placement has on the real distribution of the specials making it harder for content creators to correctly balance the specials:

   Let p_success be the probability of a successful attempt to find a place for the special on one overmap
   X_eq / Y_eq == p_success * (X*X)/(Y*Y) * Y_eq / X_eq
   (X_eq*X_eq) / (Y_eq*Y_eq) == p_success * (X*X)/(Y*Y)
   X_eq / Y_eq == sqrt(p_success) * X/Y
   

Additional context

No response

[I-am-Erk]

Oh no... @kevingranade already went into a strange mood over this once

[hexagonrecursion]

Should we also ping the one who reviewed and merged the pull request - @Maleclypse ?
Edit: Oops. I already did.

[PatrikLundell]

So, the difference between UNIQUE and GLOBALLY_UNIQUE would be that the former would continually roll chances to place and add new entries to the "to be placed" pool, while the globally unique would have a fixed count to place, and once that number has been rolled, it's a matter of placing the remaining ones as soon as possible?

It might be suitable to issue a debug warning if the "to be placed" count starts to climb, as that would indicate the thing is too picky (or too many are requested).

I might have missed it, but there needs to be something to ensure the complete backlog isn't dumped onto the same overmap (say you've got something that needs to be away from cities, but the first 10 overmaps generated are all cluttered with cities, and then you generate a plains one, and suddenly dump 11 overmaps' worth of the thing onto it).
I'd suggest something in the range of 100 - 150% of the X value. 100% means you can never recover from something that matches the placement probability 100% of the times if no suitable spot was found for one of them, while 150% means you'll never get 2 of something that's supposed to be at most 1 per overmap (assuming you're not using proper rounding to the closest even number on x.5, but C truncation).

[hexagonrecursion]

So, the difference between UNIQUE and GLOBALLY_UNIQUE would be that the former would continually roll chances to place and add new entries to the "to be placed" pool, while the globally unique would have a fixed count to place, and once that number has been rolled, it's a matter of placing the remaining ones as soon as possible?

As far as I understand a special with the GLOBALLY_UNIQUE flag is supposed to spawn only once per world. It would indeed try to draw it from the deck once per overmap until it succeeds. Once successfully drawn the GLOBALLY_UNIQUE special would be placed as soon as possible. I.e the "fixed count" of a globally unique special is (to the best of my knowledge) always 1.

[hexagonrecursion]

I might have missed it, but there needs to be something to ensure the complete backlog isn't dumped onto the same

Already taken care of (emphasis mine):

5. If to_place is not zero, we try to place one instance of the special on the current overmap.

[github-actions]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions. Please do not bump or comment on this issue unless you are actively working on it. Stale issues, and stale issues that are closed are still considered.

[kevingranade]

Oh crap missed this with the flood of other issues, and not particularly watching for mentions. Having said that I did finally see it because I checked my mentions.

Thanks for this, I very much missed that we were only placing one unique per overmap, that explains a lot of things that were frustrating me. I can try and tackle implementing your proposal, algorithm and data wise it's not all that different from what I already attempted.

[github-actions]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions. Please do not bump or comment on this issue unless you are actively working on it. Stale issues, and stale issues that are closed are still considered.