Fill rework

[fenhl]

This is a pair of related ideas I've been sketching out for a while now and I think it's time to post something more concrete and ask for feedback.

Motivation

The randomization currently happens in several distinct steps, the order of which is chosen to maximize the chance of successfully generating a beatable seed, to avoid retries. However, this order is very inflexible, making features like the requested smarter logic considerations for vanilla song locations (#1882 (comment)) impossible. The reliance on retrying also causes issues with features like mixed pools bosses or true mixed pools¹, which have such low chances of succeeding that they often exceed the retry count.

Proposals

Make fewer assumptions in assumed fill

Assumed fill is called that because it assumes that the player has access to all items for which no location has been chosen yet. Similarly, we assume that all unconnected entrances are reachable. Instead, I propose to only assume availability of an unplaced item if a location is reachable where that item could be placed given the selected settings. Similarly, an entrance should only be assumed reachable if an exit that could lead to that entrance is reachable. The latter in particular should hopefully help to more directly prevent the creation of isolated parts of the world that will never be reachable.

Replace the explicit ordering of randomization steps with a heuristic based on possible options

Simplifying a bit, the current fill order is as follows:

1. Dungeon rewards
2. Entrances
3. Shop items
4. Own-dungeon items
5. Songs
6. One major item per dungeon
7. Major items
8. Junk items

This order roughly corresponds to a progression from fewest to most possible combinations, e.g. there are only 9 locations for the dungeon rewards, but potentially over a thousand for junk items. This is good because having fewer possible combinations usually means that it's harder to find one that works. Instead of hardcoding this order, I propose to have the algorithm select an item, location, entrance, or exit to place/fill/connect based on how many corresponding locations/items/exits/entrances are still available for it within the constraints of the selected settings, choosing ones with the fewer options first. This also implies that entrances and items are no longer placed in distinct steps. Having the algorithm automatically figure out the order in which to randomize things would remove the need to special case things depending on settings. For example, adding logic to dungeon reward placement currently doesn't work as expected because entrances aren't disconnected yet, so the logic would incorrectly assume vanilla entrance layouts.

The separate steps currently each have their own retry loop in addition to the global one, which would no longer be possible with the proposed single-step algorithm. The strategy for retrying (i.e. how many steps to roll back when something can't be placed/filled) would have to be selected based on what gives the best results. I've been working on tooling for benchmarking the randomizer and plan to publish the code as part of this project.

Caveats

I have not implemented or tested any of this. It's possible that these ideas don't help with the given problems, e.g. because something about them causes a combinatorial explosion. We'll have to try it out and see if it works. And of course, this would be a big change to the core algorithm of the randomizer, so it would require extensive testing over a long period of time, potentially even multiple release cycles. It's also possible that these two proposals can be implemented separately — the second definitely requires the first to work, but I don't think the first requires the second. On the other hand, a big rewrite of the core may be an opportunity to make other semi-related changes that have been discussed for a while, such as the refactor of supplementary searches I mentioned in #2134.

Footnotes

1. A variant of mixed pools without entrance parity, to allow two interiors to connect to each other if they're reachable via a one-way entrance, for example ↩

[r0bd0g]

We do dungeon rewards first b/c we wanted which dungeons that are potentially required to be chosen as fairly as possible. I would suggest that property ought to be retained. We could use some logic for reward placement in case the user plando's something weird though, but I think they should still be placed ahead of everything. (I wouldn't say it's the main reason, but to some extent you could argue that own dungeon boss keys are being placed ahead of small keys for a similar reason.)

[fenhl]

With this proposal, dungeon rewards would still be placed first because there's only 9 locations for them. They would no longer have to be handled specially, which is part of the point. But if the heuristic described here is undesirable for any reason, it should be possible to modify it fairly easily without having to change the rest of the proposed system.

[r0bd0g]

I don't understand proposal 1, can you talk through an example of how it would affect things?

[fenhl]

Let's say true mixed pools exists (the proposal is relevant without mixed pools as well, this is just a simpler example) and you're starting in Link's house. The randomizer connects the exit to Dampé's house. In this situation, the current algorithm just keeps going, all the other regions are still reachable since they have unconnected entrances after all. Only after connecting the final entrance does it realize something's wrong. With the proposed change, connecting the Link's house exit immediately causes search to fail, since there's no unconnected exit that's reachable from spawn which can make all the unconnected entrances reachable.

[r0bd0g]

Is it just about performance, then?

[fenhl]

It's mostly about retries. If attempting to place an entrance immediately causes search to fail, it will just pick a different entrance to connect to the selected exit instead and continue on. With the current algorithm, creating an isolated part of the world almost always leads to a retry because at some point, all possible entrances to connect with an exit fail due to the earlier mistake.

[r0bd0g]

So I guess the hope is that it'd be worth the overhead to keep track of whether there are reachable unfilled entrances/locations left.

[fenhl]

Right, and that's one of the reasons I intend to do a lot of benchmarking for this.

[r0bd0g]

It'll probably depend on the settings chosen, the likelihood that they need retries.

[fenhl]

If that ends up mattering for which algorithm is faster, it would still be possible to add the current algorithm as a variant of the new one depending on settings.

[fenhl]

@cjohnson57 I'd be interested in your opinion on this as the resident abyss fill algorithm domain expert.

[cjohnson57]

Thanks for the ping, I skimmed this a while back but I forgot to go back and read it more in depth

I propose to only assume availability of an unplaced item if a location is reachable where that item could be placed given the selected settings

How do you define "reachable" here? Ex if we're starting from the beginning, we assume all items are available and therefore all location are reachable; do you mean reachable if we don't assume all the unplaced items are available? Or just the one that's about to be placed?

Similarly, an entrance should only be assumed reachable if an exit that could lead to that entrance is reachable.

So are you basically saying that we build out entrances starting from root, instead of the current system which mostly places them willy-nilly? That's worth a try imo. It would probably be slow af, but if it leads to more consistent successes it could save time overall.

Replace the explicit ordering of randomization steps with a heuristic based on possible options

This is a pretty neat idea. I'm not sure how effective it would end up being since it would probably still choose things in the same order, and then as more of those restrictive items are placed, they would become even more restrictive, and thus be chosen more. That being said, it could certainly help with some of those edge cases you mentioned. I'd be interested to see this implemented and see how often it ends up placing items in a different order than the hard-coded one.

Although are you implying that, with this system, entrances and items would be placed at the same time? If so I'll need to think more about that. That sounds like chaos to me right now haha

[fenhl]

I propose to only assume availability of an unplaced item if a location is reachable where that item could be placed given the selected settings

How do you define "reachable" here? Ex if we're starting from the beginning, we assume all items are available and therefore all location are reachable; do you mean reachable if we don't assume all the unplaced items are available? Or just the one that's about to be placed?

Yes, the idea here is to add an extra step to determine which unplaced items are available, instead of just assuming that all of them are.

Similarly, an entrance should only be assumed reachable if an exit that could lead to that entrance is reachable.

So are you basically saying that we build out entrances starting from root, instead of the current system which mostly places them willy-nilly? That's worth a try imo. It would probably be slow af, but if it leads to more consistent successes it could save time overall.

Not necessarily. The fill algorithm would still be allowed to connect exits/entrances that aren't already connected to root. This is the same “extra step” in the search algorithm to replace the assumption of everything unplaced being reachable, only for exits and entrances this time instead of locations and items. So you start your search from root, picking up placed items and entrances. If you encounter an unfilled location, you mark all unplaced items that could go there as available. Similarly, if you encounter an unconnected exit, you mark all unconnected entrances the exit could lead to as available.

are you implying that, with this system, entrances and items would be placed at the same time?

Yes.

[cjohnson57]

Yes, the idea here is to add an extra step to determine which unplaced items are available, instead of just assuming that all of them are.

How do you define if an unplaced item is available or not?

Not necessarily. The fill algorithm would still be allowed to connect exits/entrances that aren't already connected to root. This is the same “extra step” in the search algorithm to replace the assumption of everything unplaced being reachable, only for exits and entrances this time instead of locations and items. So you start your search from root, picking up placed items and entrances. If you encounter an unfilled location, you mark all unplaced items that could go there as available. Similarly, if you encounter an unconnected exit, you mark all unconnected entrances the exit could lead to as available.

I think I get what you're saying, although in effect wouldn't that make entrances need to be connected back to root? Or are you saying that's not the case because you're counting warp songs not as a normal connection?

Yes.

Hm, that seems like a pretty drastic change. I don't even know how you'd compare exits to items when determining which one is more "in need" of placement. I mean you could do it by raw number, i.e. comparing number of possible exits to number of possible item locations, but I don't know how well that would work because imo those aren't equivalent. Not shutting down the idea btw, it's just hard for me to imagine it right now

[fenhl]

How do you define if an unplaced item is available or not?

An unplaced item is available if there is a reachable unfilled location where that item could still be placed.

I think I get what you're saying, although in effect wouldn't that make entrances need to be connected back to root? Or are you saying that's not the case because you're counting warp songs not as a normal connection?

The idea is to avoid creating situations where connected parts of the world are no longer reachable due to isolated “islands” forming, i.e. either because there are no more exits from root or because there are no more entrances to that part of the world. So if you have an unconnected exit reachable from root, and an unconnected entrance into a part of the world, that's still fine. But if one of those things is no longer true, the proposed algorithm immediately recognizes that the world layout is not going to work (at least for ALR).

Warp songs may still need to be handled differently since an unplaced warp song would effectively tag everything as still reachable even though it can only lead to one entrance. A possible way to do this is to keep track of which checks are only reachable using a warp song, and prioritize placing a warp song if anything required for the Reachable Locations setting is only reachable via warp song at the end of the previous search.

I don't even know how you'd compare exits to items when determining which one is more "in need" of placement. I mean you could do it by raw number, i.e. comparing number of possible exits to number of possible item locations, but I don't know how well that would work because imo those aren't equivalent.

Raw number is what I'd try first, though if there ends up being a different way to do the comparison that ends up working better, that can obviously be changed.

[cjohnson57]

An unplaced item is available if there is a reachable unfilled location where that item could still be placed.

Do the unplaced items "take" locations from each other, so if one says "I can be placed here" then no other unplaced item (potentially including the one that's about to be placed) can be considered placeable there?

[fenhl]

I can't think of a way to do this without having to iterate through every possible combination of placements, which would amount to random fill, so no.

[cjohnson57]

Gotcha. I'm not sure how much that would actually end up changing things, since I feel like in 99% of cases, an item will be able to find at least one spot for it to be able to go. But maybe it could help for more restrictive cases, like keys in dungeons. Hell, maybe it could be the secret for fixing 1 major per dungeon lol

[fenhl]

The tool I'm planning to use to benchmark this is now public at https://github.com/fenhl/ootrstats