(Draft / request for comments) Graph-based logic

[CPColin]

Graph-based Logic (a modest proposal)

Let's organize some thoughts and concepts before we fall down a rabbit hole!

What do we have now?

Right now, we have what I'll call "region-based logic". Logic checks happen at the region level (e.g., Misery Mire, West Crateria), the room level (e.g., Hype Cave, Gauntlet Shaft), and the location level (e.g., Sick Kid, Blue Brinstar Ceiling). This sometimes has the effect of "smearing" the logic across multiple levels.

For example, the region-based logic for entering Misery Mire requires both region-level and room-level checks:

• Can the player enter the "Swamp of Evil" region in the Dark World?
• Does the player have the required medallion and a sword?
• Does the player have the Moon Pearl?
• Does the player have either Boots or Hookshot to get across the gap in the first room?

If we were updating this logic later, it would be easy to forget to do, say, the "Swamp of Evil" check and, oops, now the Flute is in Mire.

What is graph-based logic?

Hell, I dunno. Graph-based logic organizes the entire game world into a graph of nodes (places the player can be) and edges between them (ways the player can move to a new place). We would use graph-traversal algorithms to determine if, given the player's current inventory, a logical path existed between their current location and a given destination.

For example, Statues Hallway, shown above, could be a node in the graph and a "Blue Door" edge could link it to Green Pirates Shaft with another linking to Statues Room. Meanwhile, Green Pirates Shaft would be a node in the graph and a "Red Door" edge could link it to Statues Hallway. The player would need to have Missiles or Super Missiles in order to traverse a "Red Door" edge, but would always be allowed to traverse a "Blue Door" edge.

What might it get us?

This will be a lot of work, but what would we get out of it? The goal of the initial version should be graph-based logic that acts nearly identically to the current, region-based logic. (We could even enforce this via automated testing!)

Hopefully, we would end up with code that's easier to update without having to worry about breaking existing logic. For example, if some new trick were found that lets players traverse a certain room, we'd only have to update that one room and none of the rooms it connects to.

The hypothetical features we could implement later include:

• "Hey Tracker, how do I get to (Room)?"
• Advanced key logic could lock more keys behind themselves. (We know some players would prefer the current, static key logic.) Picture a Tower of Hera with its big key in the big chest, requiring Herapot!
• More Cas' options for rooms that might damage the player a lot. For example, the first check in Gauntlet currently requires one extra energy tank and the Gauntlet Shaft checks require two extra energy tanks. Things like this could be baked into the room definitions in more places, limiting how often low-health runs happen.
• Locations could be highlighted on the map when they're visible, but not yet in-logic (e.g., Lumberjack Ledge, Blue Brinstar Ceiling). The "is visible" logic could be very easy to add, when we can assume that the player is already in the necessary room.

What are the risks?

Things we have to watch out for:

• Don't logically require Bomb Torizo unless the player also has a logical way back out of Alcatraz
• Don't let players use Zelda dungeon keys in a way that gets them stuck
• Don't spend a ton of CPU or RAM on traversing the graph
• Don't use graph algorithms that explode when generating a multiworld game
• Don't go insane while coming up with room definitions for every room in both games
• Don't hard-code a bunch of special cases
• Don't make assumptions about dungeon state for things like the attic in TT and crystal switches
• Don't forget to write tests
• Don't commit a mess of spaghetti

How do we do it?

I don't know. I don't know yet. What I do know is that we'll have to be able to represent every room in both games, then link them to each other in a big graph. So we can start with figuring out how to define the rooms.

Above, I mentioned that Statues Hallway could be a node and two edges would link to the adjacent rooms. That might work fine for a simple room like this, but it might not stand up to more complicated rooms. Instead, we could define Statues Hallway as a room with a Blue Door to the west and a Blue Door to the east, all three objects being represented as nodes. The room would not define any edges of its own and the logic that constructs the graph would interpret this to mean all three nodes are connected to each other and require no items to traverse.

Let's try a more complicated example: Parlor and Alcatraz, pictured above. Taken together, it has seven total exits. If we defined every possible edge connecting all seven exits, in both directions, we'd have 42 edges in this one room. That's not very practical, so let's figure out how to simplify it.

In SMZ3, four of the exits are always accessible to each other (the one that goes to Hyrule is a Red Door in vanilla SM). We could define one room as "the main area of Parlor" and additional rooms for the areas near the exits that aren't always accessible. This room would only need to define edges to and from the three exits that aren't always accessible, with the rest being filled in as the code builds the graph.

The rooms could look like this:

• Parlor and Alcatraz main area
• Parlor top-left area
• Parlor middle-left area
• Alcatraz

And the edges could be something like:

• Main area to the area near the top-left exit: CanBombWalls or CanSafelyScrewAttackWalls or CanParlorBreakIn
• Top-left exit area to main area: CanBombWalls or CanSafelyScrewAttackWalls or HasSpeedBooster
• Main area to the area near the middle-left exit: HasMorphBall
• Middle-left exit area to main area: HasMorphBall
• Main area to the area near the middle-right exit (a.k.a. Alcatraz): HasMorphBall
• Middle-right exit area to main area (a.k.a. Alcatraz Escape): CanBombWalls or (HasMorphBall and WallJumpHard)

It's entirely possible there's a better way to represent this, though. We probably have to define each room's exits, too, so it could be cleaner for the four rooms listed above to be bundled into one "Parlor and Alcatraz" room.

As mentioned above, we have to account for when a player can get into Alcatraz, but can't logically escape. The region-based logic accounts for this, because it knows this path is a dead-end. Our goal with graph-based logic is for each room to stand alone, so additional logic would need to recognize the logical requirement to backtrack. (Note that solving this problem would allow for Bomb Torizo to have vanilla Morph Bombs, which is not possible with the region-based logic.)

[MattEqualsCoder]

I think I agree with everything mentioned here. Some general comments..

Additional Points of Potential Concern

• Hint Tiles - So I could see hint tile generation being potentially problematic. What it currently does when checking if a location is required or not is basically assume those locations have nothing, then see if a seed can be completed or not. It has to do this for each hint tile. This was already pretty slow in the old logic, but I was able to mitigate that by removing locations that just had junk. I don't know if that's really helpful here with graph logic. It would probably need to traverse the entire path no matter what. Though come to think of it, some hint tile generation can probably be short circuited if the items just have junk or something. That might help a bit.
• Removing Items - So adding new items is relatively easy to do efficiently. Take previously accessible rooms then check the edges to see if they can now be traversed. Probably not too difficult. I think removing items is a bit trickier, though. Though this happens less frequently, so if we end up having to rebuilt the navigation from scratch it may be fine.

Room Division

Another possible idea for figuring out room division is thinking of how navigation instructions can be divided into simple phrases similar to how you'd tell someone how to get around. So I could see an alternate way of splitting the parlor/Alcatraz area could be the following:

• Parlor Entrance - Top horizontal area
• Parlor Shaft - Left vertical area
• Alcatraz - Bottom right area going to Bomb Torizo

The edges could then be:

• Parlor Entrance
  • Alcatraz: Morph Ball
  • Terminator Room: CanBombWalls or CanSafelyScrewAttackWalls or CanParlorBreakIn
  • Parlor Shaft
• Parlor Shaft
  • Parlor Entrance
  • Old Crateria Shaft
  • Final Missile Bombway
  • Save Station: Morph Ball
  • Light World South
• Alcatraz
  • Parlor Entrance: CanBombWalls or (HasMorphBall and WallJumpHard)
  • Bomb Torizo Hall: Missiles

I think this could help if we do ever do a thing like "Hey Tracker, how do I get to X?" We could still add the extra side sections past the bomb wall / morph tunnel on the left side if we wanted to as well. I'm a bit mixed on that though as I don't think they necessarily add much to combining it with the normal room entrances.

Preventing Dead Ends

I'm not entirely sure of the best way of handling this either. The way I see it, there are sort of two options.

1. Make sure that when a location is seen as accessible that you can always get back to the ship from that location.
2. Add the logic to where you enter an area. For the above example, Parlor Entrance -> Alcatraz would also require CanBombWalls or (HasMorphBall and WallJumpHard).

I worry 1 would greatly increase the execution time. 2 goes against the general conventions we're trying to build up, and it requires us to identify each of those locations.

Probably a lot more to discuss, but those are some things that come to mind.

[Vivelin]

If graph-based logic ends up being slow (if hints are any indication), could we use graph-based logic to 'generate' more static logic? I think we can afford to make ROM generation slower if it speeds up everything else.

[Vivelin]

And a "Hey tracker, how do I get to (whatever)" would be incredibly helpful for people not already intimately familiar with the map and the logic. I've watched enough to know most things, but I don't intuitively know which routes are open to me because I never get far enough myself.

[MattEqualsCoder]

Another couple of spots which may make things weird. Just writing them down so when a solution is determined we can make sure it works with these.

1. Crocomire Escape Item

This one is really weird because the item is viewable from the left side but only accessible from the right side. So if items are locations inside of rooms, it may be hard to manage if the location is one side or another.

Might be able to solve by having 3 rooms in there. One for the top left, one for the main area, then one for the item?

2. PoD Balcony Chests

PoD has both the big chest and that one on the right side past the bomb wall. These are part of rooms, but those items are not accessible really from the main room itself.

These may just be easily solvable by splitting the room up into smaller rooms.

[CPColin]

Some thoughts to continue from your comments above:

Hint tiles and removing items

I think these are related—you've got the graph and the player's inventory and you take one item out of the inventory and see how it affects the available locations. I agree that this could be horribly slow if we have to traverse the graph a bunch while calling logic functions like HasMorphBall dozens of times and I'm worried the only solution might be "just be fast". Maybe we could cache the results of the logic functions as we traverse the graph and get a speed boost from that? We might have to do some experiments with the debugger running to profile whatever algorithms we come up with.

Room divisions

Yeah, it would be good to keep "How do I get to X?" in mind when dividing things up. And maybe we'd also want a boolean flag in some of the sub-rooms that are only there to make the graph connect properly, to stop Tracker from confusing the player with things like "From Parlor Entrance, go to Tiny area next to the exit to the save room"?

Dead ends

Option 1 is probably the way to do this and yeah it might turn out to be slow. We could hopefully speed it up by caching the nodes we've already confirmed as being able to reach back to the ship, so we're not repeating work.

Using graph-based logic to generate static logic

I like the idea of using the graph-based logic in the code to generate something simpler in memory that's faster to process. Hopefully we don't have to get too aggressive on optimizations like this!

[CPColin]

And I'll see what I can come up with for room definitions for Crocomire Escape and the PoD Arena. Those are good ones to think about!

[CPColin]

Here's what I came up with for those two rooms:

Crocomire Escape

Exits:

• Left (blue door)
• Right (blue door)

From the area near left exit, behind the green gate, the player can't reach anything, but can see the item. From the right exit, the player can reach the upper platform with the item if CanFly or HasGrapple or (HasHiJump and HasSpeedBooster and CanWallJumpHard). From the upper platform with the item, in front of the green gate, the player can fall back to the main area or open the green gate if HasSupers.

Sub-rooms:

• Upper platform, left of green gate
  • Visible: Crocomire Escape
• Upper platform, right of green gate
  • Location: Crocomire Escape
• Main area

PoD Arena

Exits:

• Top-left (small key door)
• Top-right (one-way shutter)
• Right-middle (open)
• Right-bottom (open)
• Bottom-left (open)
• Bottom-right (open)

From the top-left, top-right, and bottom-left exits, the player can hop down to the middle section. From the bottom-right exit, the player can hop down and, depending on the state of the crystal switch, can either turn left or climb the stairs and hop down to reach the middle section. (This means the state of the crystal switch doesn't actually matter for this edge.) From the right-middle exit, the player can only reach the middle section if they can flip a crystal switch elsewhere in the dungeon. (Region-based logic knows there's one in the next room.)

The bottom-right and right-bottom exits are accessible only from themselves (logically, that is; players can bonk across the gap to the bottom-right exit). The bottom-left exit is always accessible from the middle section. The remaining three exits are accessible if the player can hit the crystal switch (i.e., the player is not a bunny, since we assume they always have Bombs).

Sub-rooms:

• Middle
• Behind the blue blocks
• Arena Ledge
  • Location: Arena Ledge Chest
• Arena Bridge
  • Location: Arena Bridge Chest

[MattEqualsCoder]

All the above sounds good to me. I wonder how easy it would be to guestimate the amount of rooms/subrooms/exits and sort of generate a fake mock-up to do some testing with and see how well it performs.

[CPColin]

Oh yeah, that would make for a good experiment. From this page, it looks like SM has 250 "official" rooms, with us being likely to have to add sub-rooms to many of those to make the logic work. Meanwhile, this page shows one of the Z3 underworld maps having 256 supertiles containing between zero and four rooms each.

Fortunately, most of these rooms should be connected just by a pair of edges where you can always traverse them. Maybe we could do something incrementally and define rooms for, say, only Brinstar at first. Or define rooms and exits, but no logic yet or something.

For the hint system, I'm wondering if we could do a graph search for the shortest path from the start of the game to the end of the game and look at the resulting path to see what the mandatory items are.

[CPColin]

Okay, next steps:

• Pick a region and try defining its rooms and item locations (maybe West and Central Crateria?)
• Define the layout for how each of those rooms' exits connect to each other
• Write the algorithm that takes the above definitions and constructs a graph out of them

At this point, we'll likely want to implement a way to visualize the graph, so we can verify our definitions make sense. We'll probably also want to stop and assess how we're doing before we dive into writing the first of the traversal algorithms. It would be good to condense what we've learned so far into a big graph-based-logic.md document, too.

[MattEqualsCoder]

Yeah, I'd agree those are some reasonable next steps. I wonder if there are some tools out there that could help with something like this...

For the hint system, I'd agree that makes sense. Basically try to make all the actually required go mode items in one go, then use that for the hints. It would probably be way more efficient than the current system.

[CPColin]

(Note that solving this problem would allow for Bomb Torizo to have vanilla Morph Bombs, which is not possible with the region-based logic.)

It occurred to me that we can't actually do this, because we'd have to mark the location in green on the map and that would be a shining beacon of a spoiler because players would quickly realize the only way it could be green is if it held progression to get back out.