Sample Rules Without Replacement to Avoid Repetitive Procgen
Learning This note is about something I’m learning about. It may be incomplete, oversimplified, only narrowly applicable, or incorrect.
If you want to avoid repetition during procedural generation, sample rules without repetition. Otherwise, Drawing the Same Item More Than Once is Surprisingly Likely.
If I had 100 items to choose from, and each game choose 20 items, there’d be a nearly 87% chance that at least one of those items would be picked more than once.
Should you continue to sample without replacement even across games? Do you want to guarantee the player sees all of your content in a certain number of playthroughs? Or is it more interesting if a few things don’t show up for a while, by chance?
When does it make sense to let the player see the procgen, so to speak? (For example, in a roguelike where some of the progression comes from the player learning the game’s procgen rules.)
Something about this feels vaguely like the tension you get between simple pseudo-randomness and partially controlled randomness:
- Bag Randomizers Create Semi-Predictable Random Sequences
- The Dota 2 Pseudo-Random Distribution Creates Semi-Consistent Effects.