Core: Generic Entrance Rando

[BadMagic100]

What is this fixing or adding?

This PR implements a generic entrance rando approach which can be run by worlds before item fill. Features include:

• Shuffling with performant grouping, e.g. "only match right transitions with left transitions", "only shuffle transitions in some area of the map with each other" and so on, including ordered or unordered 1-to-many mapping
• Support for custom constraints by deriving the Entrance class, both by determining if a given exit is visible to randomization and by determining whether a proposed entrance placement is valid
• Client-friendly output of randomization results
• Coupled (A->B implies B->A) and uncoupled (A->B does not imply B->A) randomization modes

How was this tested?

Unit tests - ran all unit tests, including adding new ones to cover the new functionality in generic ER. Some helpers for setting up (multi)worlds for tests were moved from fill tests to __init__.py since there was utility here as well and could reasonably be needed elsewhere in the future Practical tests - Messenger, KDL3, and minit all have working or WIP implementations which have been able to generate as expected

I have not tested generation for games without an ER implementation (i.e., worlds which don't have unit tests), but this is mostly additions so I don't believe that is really needed; the only actual changed behavior is that CollectionState can now conditionally (default off) handle entrances without a connected_region.

Related PRs (non-blocking)

#2083 will impact the tests here. #2427 would improve performance; currently we use all_state which will slow down with multiworld size, but we only need a single world's state which could be provided by that.

[BadMagic100]

@Jouramie would be interested where you felt the gaps were, as it might be addressable by better docs especially if it's something user facing. Admittedly I probably ought to write up an actual explainer with examples, visuals, and faq but I wanted to get the PR out into the world so I haven't written it

[alwaysintreble]

i definitely think the docstrings need to be trimmed down to only the bare minimum and everything else moved into a separate doc with examples etc., but i don't think it's really a blocker atm and would be fine to be done at a later date.

[NewSoupVi]

I agree that an actual doc with example uses and stuff would be really really good for this instead of having it all in the docstrings

[Jouramie]

I do think having examples will be a good way to understand how the generic ER works. Right now, I have no doubt I could use it in Stardew from the docstring + trial and error, but it would be easier to see how others have integrated it.

I feed like the user facing API is well documented. It's more the internal of the algorithm that is hard to understand without going deep into it, maybe with a debugger.

[BadMagic100]

Regarding docstrings length, I think the docstrings are actually at just the right length, there are quite a lot of prerequisites to meet and they should be documented in the API ref. Honestly I would even venture to say it is quite short compared to some other docstring/javadoc/xmldoc I have seen especially if we plan to generate API reference from docstrings (which I understand is in progress currently), which tends to drive more verbose in-code documentation. I do also kind of suspect that at least berserker will be a fan of the current level of detail having stated a preference for thorough docstrings over external docs. I will add a doc with actual examples and visuals in my revision, a ton of discussion from the early design and implementations should probably be collated there and it seems like it is much needed

Regarding understanding the internals, I am not sure what to do about it but it does concern me a little bit, ideally someone other than me should be able to figure out what is going on reasonably easily. I regard this as similar complexity to fill which I was able to sit down and figure out within an hour or so. Though I also had a plain english explanation of how it should work, and from that perspective the above doc article may also be helpful

[alwaysintreble]

Honestly I would even venture to say it is quite short compared to some other docstring/javadoc/xmldoc I have seen especially if we plan to generate API reference from docstrings (which I understand is in progress currently), which tends to drive more verbose in-code documentation.

what i have so far is at #2909 and there's a thread in discord as well. plan is to add everything from our docs folder to it also, so i think it makes more sense to have explanations, examples, or detailed descriptions in docs instead of in the docstrings. i don't think the docstrings being long is necessarily an issue but i do think they should only give a brief overview of what the method does and requirements of the params etc.

adding a doc that explains how the fill methods actually work is probably a good idea too.

[BadMagic100]

i do think they should only give a brief overview of what the method does and requirements of the params etc.

Right, I agree but would argue that the current state is just about as brief as can be to summarize the expected inputs and behavior of the function. It's a complex function. There is certainly some stuff (clarifications such as the requirements for coupling to work) that could be trimmed with a separate doc but order of magnitude I expect it should end roughly the same size

[BadMagic100]

Quick link for being able to see the diagrams as diagrams (rather than markdown): https://github.com/BadMagic100/Archipelago/blob/generic-entrance-rando/docs/entrance%20randomization.md

[BadMagic100]

why get_target_groups is a callable

As discussed in discord, made this a dictionary of any hashable object (specifically allowing int groups) to improve performance. We also now no longer check/append the default group and allow failed gen instead. There is instead a convenience function which applies a callable to all observed groups in the world to pre-build the lookup

[NewSoupVi]

Hey! I'm going to be looking at this PR in the coming days.

I had a question about one way and two way entrances. Here's a condensed/cleaned up excerpt from a very chaotic Discord conversation that should explain it (ftr, this is all assuming coupled ER):

NewSoupVi: I just read the docs and saw this:

To ensure that all transitions can be accessed in the game, one-ways are only randomized with other one-ways and two-ways are only randomized with other two-ways.

Interesting! I believe OoTR (like normal, testrunner OoTR) does not do this in certain situations You can go through a loading zone that is two-way in vanilla, and be surprised by a one-way exit you're unable to go back through As I understand it, this function is intended to be overridable though, so if a world wants to do that, it can If this is not a supported use case that seems like a slight oversight to me, although probably not relevant for most devs

qwint: connect something with an entrance but no exit to a two way, what happens when they enter the two way side?

NewSoupVi: Ok so that one is actually fair So I guess I'd be ok with Two Way Entrances taking you to One Way Exits (perfectly well defined, an exit just becomes permanently unusable), but not One Way Entrances taking you to Two Way Exits (undefined what should happen when the two way entrance is taken on the other side) Does this make sense?

qwint: yes

NewSoupVi: In that case, is it something you can do with the current generic ER implementation? It's not at all a dealbreaker if not, this is a specific use case that most devs won't care about and they'll just be happy generic ER exists for them to make use of. But it would be nice

[NewSoupVi]

I now understand why this cannot work thanks to an explanation in Discord by BadMagic.

[NewSoupVi]

My experiment to implement GER into The Witness was successful, but with some big workarounds.

First of all, there is a genuine bug here where pre-placed items are never picked up. GER needs a call to sweep_for_events somewhere alongside the update_reachable_regions call. Inserting this fixed that bug.

However, there is a more insidious problem. If you have a starting region with one exit, and some of your other regions have only one exit that depends on a different region that hasn't been placed (or an item that is preplaced in the world), GER will happily go ahead and connect these up, and then immediately fail because the exit is not actually usable. These are "conditional dead ends", regions that act as dead ends until some item or region access has been acquired.

GER probably needs to actually check whether the new region has any currently usable free exits before it commits to the connection, especially when this it is currently placing the last available exit.

I was able to work around it in my case with a custom can_connect, but it was quite a hassle and I had to use a private member function of a class.

[BadMagic100]

Addressed various review comments/discord discussions in the most recent commit. It would be nice to have unit tests added for the 3 major behavior changes (speculative sweep, sweep for events, prog item count)

Summary of changes:

• Updated docs on various points, including the definition of one-ways and documenting the behavior on minimal.
• Added a missing sweep_for_events
• Correct how progression items are counted for minimal
• Cleanup of tests
• Implemented a speculative sweep in stage 1 which will help ensure that there are functionally-accessible exits after the last connection is made (covering for region/event-based rules on exits more carefully)
• Added dead_end: bool parameter to Entrance.can_connect_to as there are a variety of use cases where an implementer may be interested to know whether the current stage is placing dead ends (a trivial example would be "I need to ensure that no paths get too long so after some point only dead-ends are valid placements")

[NewSoupVi]

This PR is affected by the change from sweep_for_events to sweep_for_advancements and will fail unit tests when main is merged into it

Rather simple change though :)