How can we handle prefilling?

[aspiwack]

After speaking with some in the of the alttpr community, it appears that the only place where the shuffle, there, is purposely non-uniform is Ganon's Tower.

In early version of the randomiser, Ganon's Tower frequently had quite a few good items (I've read that 3 swords was not uncommon!). So the alttpr devs devised a way to make Ganon's Tower less likely to have items: before shuffling items around, Ganon's Tower is pre-emptively filled with junk items (ruppees, and the like).

For us it seems to mean applying a mask: a number of locations are not allowed to have assignments (this is equivalent to prefilling). These locations are not known in advance (in the current v30, the number of prefilled location is random in a range, in v31, the number will be randomly selected but will also depend on the number of crystals required to open Ganon's Tower).

It's not really clear how to handle this. On the one hand it's fairly easy to apply this sort of modification to a ZDD, but that requires an efficient (path counting) ZDD library on the randomiser side. It's even easier to model in a SAT solver, but the randomiser is not capable of running online (generally speaking, running a SAT solver online is asking for all sorts of troubles).

So what would be a good way?

[aspiwack]

To confirm the fact that uniformity is otherwise a concern here is a quote from the v31 overview document:

This is the only intentional weighting we ever apply on item distribution because we believe maximum randomization is a priority goal for a randomizer.