Ensure that each one way entrance (owl drop, spawn, or warp song) leads to a different region

[SlyryD]

Problem: Warp song entrance randomizer often results in many of the songs leading to the same region, especially in areas with many entrances, such as Kakariko Village and Market.

Solution: Attempt to spread out the warp song entrances (in the spirit of the vanilla game) by randomly sampling the target entrances for warp song ER such that each has a different connected region.

Pros: This fixes the examples in the problem statement.

Cons: It's still possible for warp song entrances to be nearby each other in several ways:

• A region is split into multiple regions (e.g., DMC is split into upper, lower, and central regions), so multiple warps lead to DMC
• Two warp songs lead to both sides of an entrance (e.g., KF and KF Sarias House) with or without interior or exterior ER

[matthewkirby]

So it looks like this is just making each warp song go to a different region. I am not sure we want to disallow multiple warp songs to the same region?

[SlyryD]

I don't think it's super interesting for multiple warp songs to go to the same region. And it's also not in the spirit of the vanilla game, where warp songs are intentionally spread out for convenience. As mentioned in the Cons section, even with this change, it's still possible for warp songs to lead to the same area, but in more interesting ways (e.g., DMC upper and lower, or outside and inside some house in Kak). We've had so many seeds where all warp songs lead to standing outside Kak or Market doors, and I would like to reduce how often that happens.

[matthewkirby]

Thats fair, I think it might be good to try to connect the indoors to the appropriate regions though.

[SlyryD]

Theoretical pro: before this change, warp song ER failed to place warps frequently due to 'No more valid entrances to replace with %s in world %d'. This may reduce the number of times it fails by reducing the pool of entrances it chooses from (while keeping the Graveyard Warp Pad, Desert Colossus, DMC Lower, and SFM regions that most frequently cause the ALR check to fail).

[SlyryD]

Indoors entrances may or may not be connected to vanilla regions depending on the ER settings. There's probably a lot of complexity here, so I think it's safest just to use the existing connected_region data for each entrance at the time of shuffling the warp song entrances (like I already do in this change).

[Roman971]

While I agree that having different warp songs leading to the same area isn't great, I don't think this is the best approach to the problem.

Selecting a random entrance for each region without logic, and before entering the shuffle algorithm, means you may select an entrance that can't be used at all, and thus prevent the area from being selected at all in this seed. One issue with this is it might increase the chances of failure, because once the entrances are picked they may not be enough to place every song, and since it's done before entering the shuffle algorithm, the program won't be able to retry other entrances and will just fail. Another issue is it creates a negative bias towards areas with entrances that can't be used as a target under the seed conditions, because those will be less likely to have a warp leading to them.

The approach I have been considering for a while is to simply check whether the area that we are trying to use as a target already has a warp leading to it, and skip it if that's the case. The check would probably be done directly during the loop in shuffle_entrances(), kinda like how check_entrances_compatibility() is performed. This does leave the existing bias towards areas with more entrances, but I don't think that's necessarily a bad thing, since one could argue they are more "dense" areas in terms of entrances so they should be more likely to have warps leading to them. In fact, it would be consistent with item shuffling, since an area with more locations is more likely to contain items. So I'm leaning towards seeing this is as the more natural option.

That being said, regardless of the approach, I'm thinking we can make use of the scene attribute of regions to apply this restriction, which is already used for the check preventing an entrance from being "connected to its own scene". This way we can avoid the first con you mentioned. Also, I think such a restriction should apply to all types of one way entrances (spawns, owls...) and not just warp songs. Tho the restriction would probably be limited to the pool itself, so we can still have a warp song leading to the same area as a spawn, which is even the case in vanilla for Prelude and the adult spawn.

[SlyryD]

Makes sense, updated!