2020-09-24 (4.75 h)
Manually defining the parts of the logic graph that cannot be automatically generated.
The automatically generated logic assumed that every location in a stage is reachable from every other. I went through and marked the edges that require certain items or hover, and removed the impossible edges. Here's an example of the logic in LAKE2. The first line (automatically generated) says how LAKE2 connects to the adjacent stage LAKE1. The next three lines (automatically generated) tells where the doors lead. The remaining lines are manually written. They say that there is an obstacle in the center of the stage that separates
lake2_rb and
lake2_door1 from
lake2_door0 and
lake2_door2. You can move freely on either side of the obstacle, but getting over it requires the Boots, the Wand, or a hover. The notation for defining item/hover requirements is not good and I am planning to improve it.
Language: python
connect(lake2_rb, lake1_lb, How.BOUNDARY)
connect_all([lake2_door0, cave0_door0], How.DOOR, need([Item.KEY]))
connect_all([lake2_door1, space0_door0], How.DOOR, need([Item.KEY]))
connect_all([lake2_door2, base1_door0], How.DOOR, need([Item.KEY]))
# 2 locations on the right side of the hill.
connect_all([lake2_rb, lake2_door1], How.GO)
# 2 locations on the left side of the hill.
connect_all([lake2_door0, lake2_door2], How.GO)
# To get over the hill requires Boots, Wand, or hover.
connect_sets_all(
[lake2_rb, lake2_door1],
[lake2_door0, lake2_door2],
How.GO,
pred_or(need([Item.BOOTS]), need([Item.WAND]), need([], True)),
)
It was interesting to watch the route evolve as I filled in the logic. The route in
my last post finished the game without collecting the Boots or the Wand—but it was doing a few things that are actually impossible to do, because of its incomplete logic. When I got finished the logic in BASE, the most complicated level, it caused the optimizer to change its route through CAVE to pick up the Wand, because the Wand helps get past the walls in BASE. Then when I had finished with the logic for CAVE, the route changed again to additionally pick up the Boots, because they make CAVE quicker.
With the logic fully defined, the optimizer finds a route that is different from both
Kabuto's proposed route and
my RTA route. Like Kabuto's route, it starts by getting the Crown in CASTLE, and does a hover from the pit in CAVE1. Like my route, it takes a detour into BASE to grab the Boots before going into CAVE. (Actually, if I artificially remove the Boots from the logic, the optimizer finds what is essentially Kabuto's route, and the difference in total estimated time is only 12 ticks (1.3 s)! Sot it's quite possible that the route will settle on a different minimum as I tighten up the state transition costs.) This route takes 6 intentional deaths, 3 to activate hover and 3 deathwarps to save time. A high-level description is:
- Collect the Key, then deathwarp on the way back to CASTLE.
- In CASTLE0, die and hover up to the Crown, then deathwarp back to the entrance.
- Traverse FOREST and LAKE. In LAKE2, die and hover over to the door that leads to BASE.
- Enter BASE, grab the Boots, exit, and enter CAVE.
- Take the door that leads to the bottom of the pit in CAVE1, die and hover out of the pit, go right and collect the Wand, deathwarp on the return and collect the Gold, then take the pit door back to the entrance.
- Re-enter BASE and use the Wand to save time moving to what would normally be the main entrance.
- Grab the Gems just outside BASE.
Keep in mind that this is the first step of the project. The optimizer is currently working with automatically inferred, lower-bound costs. The next step is to test in an emulator and measure how long the transitions
actually cost. It's also likely that there are errors in the logic graph at this point, because it is complicated in parts.
forest0_door0+1 R {} checkpoint:forest0_door0+1 hover:yes
≥240 ≥240 go forest0_rb+0 R {} checkpoint:forest0_door0+1 hover:yes
≥0 ≥240 boundary forest1_lb+0 R {} checkpoint:forest1_lb+0 hover:no
≥254 ≥494 go forest1_rb+0 R {} checkpoint:forest1_lb+0 hover:no
≥0 ≥494 boundary forest2_lb+0 R {} checkpoint:forest2_lb+0 hover:no
≥159 ≥653 go forest2_item-1 R {key} checkpoint:forest2_lb+0 hover:no
≥17 ≥670 die forest2_lb+0 L {key} checkpoint:forest2_lb+0 hover:no
≥0 ≥670 boundary forest1_rb+0 L {key} checkpoint:forest1_rb+0 hover:no
≥254 ≥924 go forest1_lb+0 L {key} checkpoint:forest1_rb+0 hover:no
≥0 ≥924 boundary forest0_rb+0 L {key} checkpoint:forest0_rb+0 hover:no
≥240 ≥1164 go forest0_door0+1 R {key} checkpoint:forest0_rb+0 hover:no
≥12 ≥1176 door castle0_door0+0 R {key} checkpoint:castle0_door0+0 hover:no
≥17 ≥1193 die castle0_door0+0 L {key} checkpoint:castle0_door0+0 hover:yes
≥2 ≥1195 go castle0_item+1 L {key,crown} checkpoint:castle0_door0+0 hover:no
≥17 ≥1212 die castle0_door0+0 R {key,crown} checkpoint:castle0_door0+0 hover:no
≥12 ≥1224 door forest0_door0+0 R {key,crown} checkpoint:forest0_door0+0 hover:no
≥241 ≥1465 go forest0_rb+0 R {key,crown} checkpoint:forest0_door0+0 hover:no
≥0 ≥1465 boundary forest1_lb+0 R {key,crown} checkpoint:forest1_lb+0 hover:no
≥254 ≥1719 go forest1_rb+0 R {key,crown} checkpoint:forest1_lb+0 hover:no
≥0 ≥1719 boundary forest2_lb+0 R {key,crown} checkpoint:forest2_lb+0 hover:no
≥238 ≥1957 go forest2_door0-1 L {key,crown} checkpoint:forest2_lb+0 hover:no
≥12 ≥1969 door lake0_door0+0 L {key,crown} checkpoint:lake0_door0+0 hover:no
≥119 ≥2088 go lake0_lb+0 L {key,crown} checkpoint:lake0_door0+0 hover:no
≥0 ≥2088 boundary lake1_rb+0 L {key,crown} checkpoint:lake1_rb+0 hover:no
≥254 ≥2342 go lake1_lb+0 L {key,crown} checkpoint:lake1_rb+0 hover:no
≥0 ≥2342 boundary lake2_rb+0 L {key,crown} checkpoint:lake2_rb+0 hover:no
≥17 ≥2359 die lake2_rb+0 L {key,crown} checkpoint:lake2_rb+0 hover:yes
≥178 ≥2537 go lake2_door2+1 R {key,crown} checkpoint:lake2_rb+0 hover:yes
≥12 ≥2549 door base1_door0+0 R {key,crown} checkpoint:base1_door0+0 hover:no
≥0 ≥2549 go base1_door2+0 R {key,crown} checkpoint:base1_door0+0 hover:no
≥12 ≥2561 door base2_door1+0 R {key,crown} checkpoint:base2_door1+0 hover:no
≥10 ≥2571 go base2_item-1 L {key,boots,crown} checkpoint:base2_door1+0 hover:no
≥0 ≥2571 go base2_door1+0 L {key,boots,crown} checkpoint:base2_door1+0 hover:no
≥12 ≥2583 door base1_door2+0 L {key,boots,crown} checkpoint:base1_door2+0 hover:no
≥0 ≥2583 go base1_door0-1 L {key,boots,crown} checkpoint:base1_door2+0 hover:no
≥12 ≥2595 door lake2_door2+0 L {key,boots,crown} checkpoint:lake2_door2+0 hover:no
≥0 ≥2595 go lake2_door2-1 L {key,boots,crown} checkpoint:lake2_door2+0 hover:no
≥52 ≥2647 go lake2_door0+1 R {key,boots,crown} checkpoint:lake2_door2+0 hover:no
≥12 ≥2659 door cave0_door0+0 R {key,boots,crown} checkpoint:cave0_door0+0 hover:no
≥31 ≥2690 go cave0_door1-1 L {key,boots,crown} checkpoint:cave0_door0+0 hover:no
≥12 ≥2702 door cave1_door0+0 L {key,boots,crown} checkpoint:cave1_door0+0 hover:no
≥17 ≥2719 die cave1_door0+0 R {key,boots,crown} checkpoint:cave1_door0+0 hover:yes
≥17 ≥2736 go cave1_rb+0 R {key,boots,crown} checkpoint:cave1_door0+0 hover:yes
≥0 ≥2736 boundary cave2_lb+0 R {key,boots,crown} checkpoint:cave2_lb+0 hover:no
≥63 ≥2799 go cave2_item-1 R {key,boots,wand,crown} checkpoint:cave2_lb+0 hover:no
≥17 ≥2816 die cave2_lb+0 L {key,boots,wand,crown} checkpoint:cave2_lb+0 hover:no
≥0 ≥2816 boundary cave1_rb+0 L {key,boots,wand,crown} checkpoint:cave1_rb+0 hover:no
≥6 ≥2822 go cave1_door0+1 L {key,boots,wand,crown} checkpoint:cave1_rb+0 hover:no
≥0 ≥2822 go cave1_item+1 R {key,boots,wand,crown,gold} checkpoint:cave1_rb+0 hover:no
≥7 ≥2829 go cave1_door0-1 L {key,boots,wand,crown,gold} checkpoint:cave1_rb+0 hover:no
≥12 ≥2841 door cave0_door1+0 L {key,boots,wand,crown,gold} checkpoint:cave0_door1+0 hover:no
≥0 ≥2841 go cave0_door1-1 L {key,boots,wand,crown,gold} checkpoint:cave0_door1+0 hover:no
≥20 ≥2861 go cave0_door0+1 R {key,boots,wand,crown,gold} checkpoint:cave0_door1+0 hover:no
≥12 ≥2873 door lake2_door0+0 R {key,boots,wand,crown,gold} checkpoint:lake2_door0+0 hover:no
≥63 ≥2936 go lake2_door2-1 R {key,boots,wand,crown,gold} checkpoint:lake2_door0+0 hover:no
≥12 ≥2948 door base1_door0+0 R {key,boots,wand,crown,gold} checkpoint:base1_door0+0 hover:no
≥111 ≥3059 go base1_door1-1 R {key,boots,wand,crown,gold} checkpoint:base1_door0+0 hover:no
≥12 ≥3071 door base0_door1+0 R {key,boots,wand,crown,gold} checkpoint:base0_door1+0 hover:no
≥23 ≥3094 go base0_door2-1 L {key,boots,wand,crown,gold} checkpoint:base0_door1+0 hover:no
≥12 ≥3106 door space2_door0+0 L {key,boots,wand,crown,gold} checkpoint:space2_door0+0 hover:no
≥0 ≥3106 go space2_door0-1 L {key,boots,wand,crown,gold} checkpoint:space2_door0+0 hover:no
≥19 ≥3125 go space2_item+1 L {key,boots,wand,gems,crown,gold} checkpoint:space2_door0+0 hover:no
Since the last session, I added a
facing field to the
State structure, which you can see as ‘
L’ or ‘
R’ in the listing above. Even at this point, the optimizer knows that it costs an extra tick to move in the direction opposite to where Comic is facing, so it applies optimizations like doing a zero-cost in-air turn before entering doors, so that Comic is facing the correct direction on the other side of the door. You can see this, for example, in the sequence
forest2_lb+0 R →
forest2_door0-1 L →
lake0_door0+0 L.
Just for fun, I tried removing hover from the logic, to see what the route would look like for Revision 5 of the game. (Revisions 1 and 5 are identical, I believe, in terms of logic graph, with the exception of the ability to hover.) The route it finds is the same as is used in
rockdet's 10:46 and
my 10:38, collecting the treasures in the order Gems, Gold, Crown, with no intentional deaths.
forest0_door0+1 R {} checkpoint:forest0_door0+1 hover:yes
≥240 ≥240 go forest0_rb+0 R {} checkpoint:forest0_door0+1 hover:yes
≥0 ≥240 boundary forest1_lb+0 R {} checkpoint:forest1_lb+0 hover:no
≥254 ≥494 go forest1_rb+0 R {} checkpoint:forest1_lb+0 hover:no
≥0 ≥494 boundary forest2_lb+0 R {} checkpoint:forest2_lb+0 hover:no
≥159 ≥653 go forest2_item-1 R {key} checkpoint:forest2_lb+0 hover:no
≥79 ≥732 go forest2_door0-1 L {key} checkpoint:forest2_lb+0 hover:no
≥12 ≥744 door lake0_door0+0 L {key} checkpoint:lake0_door0+0 hover:no
≥119 ≥863 go lake0_lb+0 L {key} checkpoint:lake0_door0+0 hover:no
≥0 ≥863 boundary lake1_rb+0 L {key} checkpoint:lake1_rb+0 hover:no
≥254 ≥1117 go lake1_lb+0 L {key} checkpoint:lake1_rb+0 hover:no
≥0 ≥1117 boundary lake2_rb+0 L {key} checkpoint:lake2_rb+0 hover:no
≥142 ≥1259 go lake2_door1+1 R {key} checkpoint:lake2_rb+0 hover:no
≥12 ≥1271 door space0_door0+0 R {key} checkpoint:space0_door0+0 hover:no
≥251 ≥1522 go space0_rb+0 R {key} checkpoint:space0_door0+0 hover:no
≥0 ≥1522 boundary space1_lb+0 R {key} checkpoint:space1_lb+0 hover:no
≥254 ≥1776 go space1_rb+0 R {key} checkpoint:space1_lb+0 hover:no
≥0 ≥1776 boundary space2_lb+0 R {key} checkpoint:space2_lb+0 hover:no
≥197 ≥1973 go space2_item-1 R {key,gems} checkpoint:space2_lb+0 hover:no
≥31 ≥2004 go space2_door0-1 L {key,gems} checkpoint:space2_lb+0 hover:no
≥12 ≥2016 door base0_door2+0 L {key,gems} checkpoint:base0_door2+0 hover:no
≥139 ≥2155 go base0_lb_low+0 L {key,gems} checkpoint:base0_door2+0 hover:no
≥0 ≥2155 boundary base1_rb_low+0 L {key,gems} checkpoint:base1_rb_low+0 hover:no
≥140 ≥2295 go base1_door1+1 R {key,gems} checkpoint:base1_rb_low+0 hover:no
≥12 ≥2307 door base0_door1+0 R {key,gems} checkpoint:base0_door1+0 hover:no
≥125 ≥2432 go base0_door0-1 R {key,gems} checkpoint:base0_door1+0 hover:no
≥12 ≥2444 door base2_door0+0 R {key,gems} checkpoint:base2_door0+0 hover:no
≥192 ≥2636 go base2_item-1 L {key,boots,gems} checkpoint:base2_door0+0 hover:no
≥0 ≥2636 go base2_door1+0 L {key,boots,gems} checkpoint:base2_door0+0 hover:no
≥12 ≥2648 door base1_door2+0 L {key,boots,gems} checkpoint:base1_door2+0 hover:no
≥0 ≥2648 go base1_door0-1 L {key,boots,gems} checkpoint:base1_door2+0 hover:no
≥12 ≥2660 door lake2_door2+0 L {key,boots,gems} checkpoint:lake2_door2+0 hover:no
≥0 ≥2660 go lake2_door2-1 L {key,boots,gems} checkpoint:lake2_door2+0 hover:no
≥52 ≥2712 go lake2_door0+1 R {key,boots,gems} checkpoint:lake2_door2+0 hover:no
≥12 ≥2724 door cave0_door0+0 R {key,boots,gems} checkpoint:cave0_door0+0 hover:no
≥145 ≥2869 go cave0_door2-1 L {key,boots,gems} checkpoint:cave0_door0+0 hover:no
≥12 ≥2881 door cave2_door0+0 L {key,boots,gems} checkpoint:cave2_door0+0 hover:no
≥0 ≥2881 go cave2_door0-1 L {key,boots,gems} checkpoint:cave2_door0+0 hover:no
≥161 ≥3042 go cave2_item+1 L {key,boots,wand,gems} checkpoint:cave2_door0+0 hover:no
≥0 ≥3042 go cave2_item-1 L {key,boots,wand,gems} checkpoint:cave2_door0+0 hover:no
≥53 ≥3095 go cave2_lb+0 L {key,boots,wand,gems} checkpoint:cave2_door0+0 hover:no
≥0 ≥3095 boundary cave1_rb+0 L {key,boots,wand,gems} checkpoint:cave1_rb+0 hover:no
≥6 ≥3101 go cave1_door0+1 L {key,boots,wand,gems} checkpoint:cave1_rb+0 hover:no
≥0 ≥3101 go cave1_item+1 R {key,boots,wand,gems,gold} checkpoint:cave1_rb+0 hover:no
≥7 ≥3108 go cave1_door0-1 L {key,boots,wand,gems,gold} checkpoint:cave1_rb+0 hover:no
≥12 ≥3120 door cave0_door1+0 L {key,boots,wand,gems,gold} checkpoint:cave0_door1+0 hover:no
≥0 ≥3120 go cave0_door1-1 L {key,boots,wand,gems,gold} checkpoint:cave0_door1+0 hover:no
≥20 ≥3140 go cave0_door0+1 R {key,boots,wand,gems,gold} checkpoint:cave0_door1+0 hover:no
≥12 ≥3152 door lake2_door0+0 R {key,boots,wand,gems,gold} checkpoint:lake2_door0+0 hover:no
≥243 ≥3395 go lake2_rb+0 R {key,boots,wand,gems,gold} checkpoint:lake2_door0+0 hover:no
≥0 ≥3395 boundary lake1_lb+0 R {key,boots,wand,gems,gold} checkpoint:lake1_lb+0 hover:no
≥254 ≥3649 go lake1_rb+0 R {key,boots,wand,gems,gold} checkpoint:lake1_lb+0 hover:no
≥0 ≥3649 boundary lake0_lb+0 R {key,boots,wand,gems,gold} checkpoint:lake0_lb+0 hover:no
≥118 ≥3767 go lake0_door0-1 L {key,boots,wand,gems,gold} checkpoint:lake0_lb+0 hover:no
≥12 ≥3779 door forest2_door0+0 L {key,boots,wand,gems,gold} checkpoint:forest2_door0+0 hover:no
≥0 ≥3779 go forest2_door0-1 L {key,boots,wand,gems,gold} checkpoint:forest2_door0+0 hover:no
≥66 ≥3845 go forest2_door1+1 L {key,boots,wand,gems,gold} checkpoint:forest2_door0+0 hover:no
≥0 ≥3845 go forest2_item-1 L {key,boots,wand,gems,gold} checkpoint:forest2_door0+0 hover:no
≥149 ≥3994 go forest2_lb+0 L {key,boots,wand,gems,gold} checkpoint:forest2_door0+0 hover:no
≥0 ≥3994 boundary forest1_rb+0 L {key,boots,wand,gems,gold} checkpoint:forest1_rb+0 hover:no
≥244 ≥4238 go forest1_lb+0 L {key,boots,wand,gems,gold} checkpoint:forest1_rb+0 hover:no
≥0 ≥4238 boundary forest0_rb+0 L {key,boots,wand,gems,gold} checkpoint:forest0_rb+0 hover:no
≥230 ≥4468 go forest0_door0+1 L {key,boots,wand,gems,gold} checkpoint:forest0_rb+0 hover:no
≥12 ≥4480 door castle0_door0+0 L {key,boots,wand,gems,gold} checkpoint:castle0_door0+0 hover:no
≥0 ≥4480 go castle0_door0-1 L {key,boots,wand,gems,gold} checkpoint:castle0_door0+0 hover:no
≥226 ≥4706 go castle0_door2+1 R {key,boots,wand,gems,gold} checkpoint:castle0_door0+0 hover:no
≥12 ≥4718 door castle1_door0+0 R {key,boots,wand,gems,gold} checkpoint:castle1_door0+0 hover:no
≥0 ≥4718 go castle1_door1+0 R {key,boots,wand,gems,gold} checkpoint:castle1_door0+0 hover:no
≥12 ≥4730 door castle2_door0+0 R {key,boots,wand,gems,gold} checkpoint:castle2_door0+0 hover:no
≥237 ≥4967 go castle2_door1-1 R {key,boots,wand,gems,gold} checkpoint:castle2_door0+0 hover:no
≥12 ≥4979 door castle0_door1+0 R {key,boots,wand,gems,gold} checkpoint:castle0_door1+0 hover:no
≥14 ≥4993 go castle0_item-1 L {key,boots,wand,gems,crown,gold} checkpoint:castle0_door1+0 hover:no