Skip to content

Idea: graph cut analysis to find required items or paths #228

@Zannick

Description

@Zannick

For example, with the Any% objective for AV2, the default victory condition only includes 4 items, and we only list those because we know they're strictly required in all cases. Even so, we don't really need to be listing them all technically, but listing required items is helpful because it helpfully affects the time estimation by including it as a goal.

We should be able to build a subgraph around an item (around a canon location) to find item requirements. For example, in glitchless logic:

  • Escape locations always require Apocalypse_Bomb. The only routes that reach Escape from Apocalypse_Bomb require either Ledge_Grab and no Separation, Ledge_Grab and Anuman, or Remote_Drone and Slingshot_Hook.
  • Apocalypse_Bomb locations always require Infect.
  • Routes to Apocalypse_Bomb always require Nanite_Mist (or by warping to the save room which also requires access to the save room)
  • Routes to Nanite_Mist always require entering through a portal, and therefore, Breach_Attractor. (In part because we can eliminate the edges that need Nanite_Mist as well.)

And so on.

In part I am trying to improve time estimations to guide the algorithm along, but also the actual route to get Nanite_Mist in AV2 is not easily found even with the greedy searches.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions