randomizers and bias (1/N)
So for the randomizer, I wanted to add a mode ("full") that assigns orbs to lands as close to 1:1 as possible. Some pairings of orbs/lands are not allowed, and there are a lot of special cases in this logic. I wanted to place them such that they are unbiased, i.e. every possible placement has equal probability. That is surprisingly difficult.
randomizers and bias (2/N)
The naive algorithm would be to shuffle the orbs completely at random. If this results in an invalid configuration, try again until it works. That would be unbiased, but in this case, certain lands and orbs accept only a few pairings, so there'd be a lot of retries.
randomizers and bias (3/N)
One could adjust that by checking pairs during the process and rerolling any invalid pairs. However, this would introduce bias. Early on, each pairing is equally likely, but these pairings eliminate different numbers of possibilities later. If I place a more "restricted" orb that can go in only a few lands, that eliminates relatively few possibilities for it, compared to other orbs that could go anywhere.
randomizers and bias (4/N)
And this algorithm can still hit dead ends, if an orb or land has no valid pairings left.
randomizers and bias (5/N)
The algorithm I settled on is.. maybe more understandable if you start from the end.
Let's say I have N orbs left to place in N lands. Naively, I could check all N permutations, store the valid ones, choose one at random, and I'm done. Of course, there are N! permutations, and I start out with N = 60, so this would take an impossible amount of computation and memory.
randomizers and bias (6/N)
Except, if I check the permutations in a random order, I don't have to test all of them. I can just choose permutations until I find one that works. That's my naive algorithm from earlier that rerolls way too often and takes too long. But we can build off of that.
viridian
re: randomizers and bias (6/N)
@madewokherd 🐍 ooh! how many orbs are restricted in what ways? (we remembered that we like math puzzles)
re: randomizers and bias (6/N)
@viridian Here's the function that decides it: https://github.com/zenorogue/hyperrogue/blob/master/orbgen.cpp#L216
Orbs that are useless, forbidden, dangerous, or burn are not allowed.
re: randomizers and bias (6/N)
@madewokherd so, functionally, for each orb/land combination there is exactly one orb-land-relationship, and at this stage we only care about "allowed" vs. "not allowed" (and later logic determines whether the orb gets placed as a "collect 25" thing or a prize or just laying around somewhere or something?)
my thought is — I don't know if this has a name, but it's an algorithm that I've used before to great success — is to build out a tree where at each node you branch off of whichever orb / land has the fewest options*, until you get to a point where you can calculate the number of remaining legal combinations (as n! or something), then sum those back up the tree as total number of combinations under each branch (so if orb 1 going in land A leaves 10 legal combinations and orb 1 going in land B leaves 23 combinations, choose A1 10/33 times).
*which is kind of getting at "whichever choice locks in the most information"
(maybe) a key to this being computable is to recognize equivalence classes — if every [remaining?] orb that can go into A can also go into B, C, and D, then treat A-D as a group & say an orb that can go into A-E as having two options of {A-D, E} ? or just treat A-D as a zone that accept 4 orbs and has combinatoric mass 4!= 24?
or possibly more important is identifying subgraphs were placing orb A can't affect the placement of orb B, b/c then you can do those separately & just multiply… if group M and group P are mostly disjoint except that orb Z can go into either, choosing orb Z as either M or P as your next pic
once you get down to "these n orbs go in these n slots, these k different orbs can go into these k different spots, etc" you can compute that weight as n! * k!
there's probably a lot of things like that that don't help in the general case but might in the specific case depending on the shape constraints
my real answer is to start with a very restricted subset of your orbs, write test cases for "how many possibilities remain given these selections so far?", and TDD your way through it by adding orbs with more kinds of restraints; that should guide you to the most relevant optimizations / simplifications.
re: randomizers and bias (6/N)
@viridian Is this approach still going to work when I start randomizing land unlock requirements (which means I have to calculate reachability)?
re: randomizers and bias (6/N)
@viridian Oh, also, olrPNever is not allowed.