Run accessibility analysis to determine required items

[Zannick]

A typical access search involves maintaining a set of accessible nodes (Spots) and alternately trying edges outward from the accessible set and accessing locations inside the accessible set. We can't quite do this with a traversal graph and context parameters that could affect accessibility.

OoTR solves this for its context parameters in different ways:

• age: child and adult maintain different sets of nodes
• time of day: marks accessible nodes as combinations of the times of day available, using sources of time changes for a flood-fill-like algorithm

We can apply the same concept here, keeping track of combinations of modes for each Spot that is accessible in some mode. Edges will act as filters that only let certain modes through.

The challenge then comes in how to keep track of the combinations of modes available. For small context parameters (where there are only a few options) we can use bitflags. If there are too many options (say, more than 32) or it's an integer context variable, that might not be plausible or efficient. It would be better to say "we can achieve [these/all] values" based on the sources we have. Given access to a save point in AV2, for example, we can achieve any energy needs under 300, and any edges out that cost, say, 100 will mark the new nodes as achieving under 200, etc.

Essentially, we'll have to classify context variables based on how they're used. Here are some ideas so far, based on what we have in AV2:

• modals (enums) - when we typically set and test them for specific values and there aren't many
• loadouts - when we set combinations of specific values (or even separate enums/contexts)
• refillables - when sources exist to reset to a certain amount, usually used as prices or threshold checks
• points - prices or threshold checks, but there aren't reusable sources (i.e. they come from collecting items)
• positional - type is a Spot. Most likely these can only be set to the current position or specially. Warping to them might generally be a no-op, but it could allow for greater context accessibility, such as when in AV2 the drone can set a save point and Indra can warp there.
• map - easier to treat this like a location or item and "collect" it during the first sweep.

Even with all this, it might be useful to collapse nodes connected by mutual free edges.

[Zannick]

Here's an idea for an alternate algorithm: maintaining an AccessState per spot or per merged node (clique).

Each node would contain a struct that details the particular variances in context we might have whenever positioned at that node, and then edges become floodfill "filters" that translate to the state available in adjacent nodes. For instance, we might be able to reach a node whether we have a particular item or not, but the edge requires that we do, so the access state on the destination node is updated to show that we can reach that node with that item. We can read an access state's flags to see which items are always required to access that node. Locations are then treated as self-edges that modify state.

The algorithm's conclusion could then read the access state to see what items are required at the very end.

There are a few complications I haven't worked out how to deal with properly:

• Simple "can reach with"/"can reach without" flags alone don't really work for numeric contexts, multi-count items, or any explicit or implicit "or" rules. We could replace item references with canon locations to avoid multi-count items (and then define a count of those locations), but we'd still need to keep track with separate properties any rule more complicated than "and". (That is, we might be able to access a node with either of item A or item B, which would be recorded as "with or without A" and "with or without B" which on its own seems to imply that it could be done without both.)
• Ideally we also remember what we needed to get items that were required. For example, if obtaining an item C requires 7 flasks, we might want to remember that "C implies 7+ flasks". But this gets more complicated if those requirements are from alternate routes to the location where the item is obtained: what happens when we already have obtained C? Update the "C implies" rule to have an or condition? How do we know when to update it when the node containing the location is reached, including knowing whether we're depending on having already reached/obtained C? Do we track it in the AccessState to include that (can we do it without making it an open-ended list) or keep it global?
• We can't stop once we reach the goal as we might find other ways to reach it.

Keeping track of the item requirements in this way is kind of like mutating the access graph to a per-location list of global rules (how some randomizers write their logic rather than use a graph). And I worry at the same time whether trying to keep track of all the item requirements is the equivalent of a sphere search (the typical randomizer can-win check) but worse performance-wise due to the flood-fills and repeated location checking.

[Zannick]

My recent work has been writing code to merge spots into cliques and combine their rules together. It works to a decent level, but I wonder whether to optimize any of the rules. Some optimizations are simply removing redundant alternatives, like A or (A and B) can be reduced to just A, but others are evaluating data rules for global actions and warps. We have the following options for how to handle this:

1. Don't handle it at all. The rust compiler can handle redundant alternatives within the emitted rule function.
2. Don't handle anything beyond simply removing duplicates. The rust compiler can handle anything more complicated if it helps.
3. Write a python visitor to rewrite a combined AST that we can provide to the RustVisitor to emit. We could evaluate the data-specific rules by checking whether any spot in the clique fulfills the criteria and drop the edge if there's no way to perform it.
4. Only emit a rule that invokes the actual edge rules in a long OR statement and let the compiler deal with it.