Post by Sand

Showing items [1 - 22] of 22

Posted: 6/3/2020 11:45 PM

Post subject: The Adventures of Captain Comic

Quote

Sand

He/Him

Player (125)

Joined: 6/26/2018
Posts: 154

In the past months I've been working on a randomizer for Captain Comic. A necessary component of a randomizer is a logic graph that defines what game locations connect to what other locations, and what items are needed to use each connection. You can see the logic graph used by the randomizer here:

I think that, using a logic graph like this one, we can find an optimal route for this game, under mild assumptions. The main idea is to expand the logic graph, whose vertices are game locations and whose edges are tagged with inventory requirements, into a larger "virtual graph," in which a vertex is a "state" that combines a game location and an inventory, and whose edges are tagged by a time cost. Then run a shortest-path algorithm on the virtual graph to find the lowest-cost (fastest) path to any state that has in its inventory the three items needed to win the game: Gems, Crown, and Gold. In many games this approach would be infeasible, because the size of the expanded graph is up to exponential in the number of possible inventory items, but in Captain Comic there are few enough locations and items that I'm sure it's doable. I say "virtual graph" because the expanded graph does not have to be constructed explicitly—it's implicit in the structure of the underlying logic graph. You can think of the virtual graph as making a copy of every game location, one for every set of inventory items it is possible to have at that location. For example, you would have a state for (forest0_door0, {}), one for (forest0_door0, {Door Key}), one for (forest0_door0, {Door Key, Boots}), one for (forest0_door0, {Door Key, Gems}), one for (forest0_door0, {Door Key, Boots, Gems}), etc. An outgoing edge in the logic graph exists in the virtual graph only if the state's inventory permits it; for example the edge (forest0_door0, {Door Key})→(castle0_door0, {Door Key}) exists, but the edge (forest0_door0, {})→(castle0_door0, {}) does not, because you cannot use a door without holding the Door Key item. There are only 6 items that matter for a TAS: Door Key, Boots, Teleport Wand, Gems, Crown, and Gold, so there are at most 2⁶ = 64 copies of each item location. And there are only about 70 game locations, so we're looking at around 5,000 vertices in the virtual graph, well within the capabilities of a shortest-path algorithm. And many of the states included in this estimate are impossible and thus are never considered; for example every stage past the forest level requires the Door Key to access, so states like (lake0_door0, {}) don't exist. Besides vertices and edges, a shortest-path algorithm requires a cost for every edge. For a TAS, the "cost" is the time it takes to get from one state to another. We presume that the true cost of an edge can be known by having a human actually TAS that short segment of the game. With a virtual graph of 5,000 vertices and, let's say, average outdegree 2, there are far too many edges to annotate manually. I propose to deal with this problem by tweaking the shortest-path algorithm to permit each edge cost to be marked as being either lower bounded or measured (i.e., TASed by a human). A lower bound is an automatically determined value that is as fast or faster than whatever the measured value could be. For example, it takes a fixed amount of time to go through a door—that can be an automatic lower bound for door transitions. Comic's maximum horizontal speed is 1.17 units / tick, so a lower bound on any edge between two locations separated by horizontal distance d units is d/1.17 (rounded down). A lower bound may be set to 0 if nothing tighter is certain. The first time you run the shortest-path algorithm, all edges have an automatically determined lower-bound cost. The total cost of the shortest path is thus itself a lower bound on the time that any TAS can achieve. Now, the TASer then needs to select one or more of those lower-bound edges on the shortest path, and TAS them, replacing the lower bounds into precisely measured values. Then, run the shortest-path algorithm again. The edges on the new shortest path will have a mix of lower-bound costs and measured costs—it may be that by measuring some edges and increasing their cost, the TASer has made other paths look more attractive to the shortest-path algorithm. Again the TASer must select one or of the lower-bound costs to measure, and then find a shortest path again. The process is finished when the shortest-path algorithm returns a path that consists only of measured costs (no lower bounds); this is the algorithm saying that the path found is the fastest possible, even if you were able to TAS the remaining unmeasured edges down to their lower bounds, so there is no need to actually measure them manually. Certain other optimizations are possible; for example the three treasure items—Gems, Crown, and Gold—do not affect mobility, so those items can be ignored when looking up time measurements. To summarize the overall algorithm:

Automatically assign a lower-bound cost to all edges.
Set P to be a shortest path in the virtual graph, given current bounds on edge costs.
If every edge in P has already been measured, exit. This is the route.
Otherwise, manually measure one or more of the edges in P and update edge costs.
Go to step 2.

I mentioned that the resulting route would be optimal under certain assumptions. The assumptions are that the logic graph is complete and correct, the algorithm is implemented correctly, and lower bounds are actually lower bounds; that the human TASer finds the precise minimum time for each short state transition; and that there are no glitches we don't know about that change the logic graph or movement speed. There is a small amount of global state in the game, for example a cyclic counter that controls enemy spawns, and so it may be the case that doing one segment fast makes another segment slow, violating the assumptions baked into the virtual graph. I have a feeling that it will be possible to work around difficulties of this kind. There are five revisions of The Adventures of Captain Comic. The randomizer uses Revision 5. I propose to TAS Revision 1. The most important difference is that Revisions 1 and 2 have the hover glitch, which allows for some interesting skips, for example getting over the wall next to the rocket in lake2, and flying up into the item chamber in castle0. I simplified a bit above when I said that a "state" in the virtual graph represents a location and an inventory. In order to allow death warp transitions, a state will also have to store Comic's most recent checkpoint: for example (cave2_item, {Door Key, Teleport Wand}, cave2_leftside) would mean "I am at the item pedestal in cave2, holding the Door Key and Teleport Wand, and if I die I will respawn at cave2_leftside (where I entered)." We can initially assume that HP and enemy management is easy enough that a death warp is possible from anywhere—and if that turns out not to be the case, we can exclude that edge from the virtual graph. Besides death warping, the hover glitch can only be activated by dying and respawning, so a state will have to store whether a hover is currently possible. For example, you'll be at state (cave2_leftside, {Door Key}, cave2_leftside, cannot hover) immediately upon entering cave2, but after collecting the Teleport Wand and death warping, you'll be at (cave2_leftside, {Door Key, Teleport Wand}, cave2_leftside, can hover). I think the state will additionally have to record what direction Comic is facing, because it costs 1 tick to change direction while Comic is on the ground, and facingness is preserved through doors and respawns. Finally, I suspect it will be necessary to create multiple pseudo-locations for doors and item pedestals, because doors can be entered from the left, right, or center, and similarly items can be picked up from the left, right, or center. So, my estimate of 5,000 vertices above may be low, but even if it's off by a couple of orders of magnitude I think the idea will still work. TASVideos has a great Wiki: GameResources/DOS/CaptainComic page, originally written by Kabuto. If I follow through with making a TAS for this game, I would like to offer Kabuto co-authorship, because I'm not sure I would have found the hover glitch on my own, despite analyzing the game pretty thoroughly in the course of making the randomizer. I have not been able to find any existing speedruns that use the hover glitch, to compare. The current 1st place run by rockdet on speedrun.com uses Revision 4. So I did an RTA run myself using Revision 2 (which practically the same as Revision 1 but lets you remap keys). The route I used was (some edges omitted):

forest0_door0 → forest2_item (collect Door Key) → forest2_door0 → lake0_door0 → lake1_leftside → lake2_rightside → lake1_leftside (set checkpoint and die) → lake1_leftside (respawn and hover) → lake2_door2 → base1_door0 → base1_door2 → base2_door1 → base2_item (collect Boots) → base2_door1 → base1_door2 → base1_door0 → lake2_door0 → cave0_door0 → cave0_door2 → cave2_door0 → cave2_item (collect Teleport Wand) → cave1_item (collect Gold) → cave1_door0 → cave0_door1 → cave0_door0 → lake2_door0 → lake2_door2 → base1_door0 → base1_door1 → base0_door1 → base0_door2 → space2_door0 → space2_item (collect Gems) → space2_door0 → base0_door2 → base0_door1 → base2_door1 → base2_door0 → lake2_door2 → lake0_door0 → forest2_door0 → forest0_door0 → castle0_door0 (set checkpoint and die) → castle0_door0 (respawn and hover) → castle0_item (collect Crown)

Kabuto has proposed a radically different route, requiring more meticulous HP management for quick deaths. I briefly tried one of Kabuto's ideas. Without optimization and practice, it is hard to say for sure, but it may be competitive with the route I used. I didn't record my test, but I believe I tried something like:

forest0_door0 → forest2_leftside (set checkpoint) → forest2_item (collect Door Key and die) → forest2_leftside (respawn) → forest0_door0 → castle0_door0 (set checkpoint and die) → castle0_door0 (respawn and hover) → castle0_item (collect Crown and die) → castle0_door0 (respawn) → forest0_door0 → lake0_door0 → lake1_leftside → lake2_rightside → lake1_leftside (set checkpoint and die) → lake1_leftside (respawn and hover) → lake2_door0 → cave0_door0 (set checkpoint and die) → cave0_door0 (respawn and hover) → cave0_door1 → cave1_door0 (set checkpoint and die) → cave1_door0 (respawn and hover) → cave2_leftside (set checkpoint) → cave2_item (collect Teleport Wand and die) → cave2_leftside (respawn) → cave1_item (collect Gold) → cave1_door0 → cave0_door1 → cave0_door0 → lake2_door0 → lake2_door2 → base1_door0 → base1_door1 → base0_door1 → base0_door2 → space2_door0 → space2_item (collect Gems)

Posted: 6/11/2020 8:46 AM

Post subject: Re: The Adventures of Captain Comic

Quote

Radiant

Player (26)

Joined: 8/29/2011
Posts: 1206
Location: Amsterdam

Go for it! This game is a milestone in PC video game development, and its DOS version deserves more attention. (its porting-disaster NES version does not; unfortunately that's all people talk about)

Indie game developer

Posted: 9/22/2020 4:44 PM

Post subject: Video series

Quote

Sand

He/Him

Player (125)

Joined: 6/26/2018
Posts: 154

I've started carrying out the plan I outlined in Post #495817. I'm documenting the process in narrated screen recording videos—which so far consist mostly of writing and debugging Python code. 2020-09-18 (3 h) Manually defining a subset of the full logic graph that includes only the FOREST and CASTLE stages, and requires only the Crown to win. Representation of a "state" in the virtual graph, and traversing all reachable states. 2020-09-20 (2.5 h) Implementation a shortest-path algorithm. Inference of lower-bound state transition costs between any two adjacent states. A trial run of the meta-algorithm, manually defining state transition costs with made-up numbers, until it terminates with all state transition costs exact. 2020-09-22 (3.25 h) Automatically generating the full logic graph, using level/stage connectivity information from the game executable. The logic graph still needs manual refinement to remove some edges that are impossible, and add inventory or hover requirements to others. Below is some sample output of the route optimization program. Each row represents a state transition in the virtual graph. The columns of the table are

edge cost, cumulative cost, how, state

Costs are shown with a ‘≥’ prefix for automatically inferred lower bounds, or a ‘=’ prefix for precisely measured values. Initially, all costs are automatically inferred lower bounds. The meta-algorithm terminates when all the ‘≥’ become ‘=’. The "how" column describes the nature of the state transition. boundary is a connection between horizontally adjacent stages. door is a door. die is a death and respawn at checkpoint (deathwarp). go is normal game movement, including hover. A state is made up of a current location (plus an x offset of −1, +0, or +1, for locations like items and doors that have a left side, center, and right side); an inventory enclosed in ‘{}’; a checkpoint location (plus an x offset); and a flag indicating whether hover is possible.

                          forest0_door0+1 {} checkpoint:forest0_door0+1 hover:yes
  ≥240    ≥240  go        forest0_rb+0 {} checkpoint:forest0_door0+1 hover:yes
    ≥0    ≥240  boundary  forest1_lb+0 {} checkpoint:forest1_lb+0 hover:yes
  ≥254    ≥494  go        forest1_rb+0 {} checkpoint:forest1_lb+0 hover:yes
    ≥0    ≥494  boundary  forest2_lb+0 {} checkpoint:forest2_lb+0 hover:yes
  ≥159    ≥653  go        forest2_item-1 {key} checkpoint:forest2_lb+0 hover:no
   ≥17    ≥670  die       forest2_lb+0 {key} checkpoint:forest2_lb+0 hover:yes
    ≥0    ≥670  boundary  forest1_rb+0 {key} checkpoint:forest1_rb+0 hover:yes
  ≥254    ≥924  go        forest1_lb+0 {key} checkpoint:forest1_rb+0 hover:yes
    ≥0    ≥924  boundary  forest0_rb+0 {key} checkpoint:forest0_rb+0 hover:yes
  ≥240   ≥1164  go        forest0_door0+1 {key} checkpoint:forest0_rb+0 hover:no
   ≥12   ≥1176  door      castle0_door0+0 {key} checkpoint:castle0_door0+0 hover:no
    ≥2   ≥1178  go        castle0_item+1 {crown,key} checkpoint:castle0_door0+0 hover:no
    ≥1   ≥1179  go        castle0_door0-1 {crown,key} checkpoint:castle0_door0+0 hover:no
   ≥12   ≥1191  door      forest0_door0+0 {crown,key} checkpoint:forest0_door0+0 hover:no
  ≥241   ≥1432  go        forest0_rb+0 {crown,key} checkpoint:forest0_door0+0 hover:no
    ≥0   ≥1432  boundary  forest1_lb+0 {crown,key} checkpoint:forest1_lb+0 hover:no
  ≥254   ≥1686  go        forest1_rb+0 {crown,key} checkpoint:forest1_lb+0 hover:no
    ≥0   ≥1686  boundary  forest2_lb+0 {crown,key} checkpoint:forest2_lb+0 hover:no
  ≥238   ≥1924  go        forest2_door0-1 {crown,key} checkpoint:forest2_lb+0 hover:no
   ≥12   ≥1936  door      lake0_door0+0 {crown,key} checkpoint:lake0_door0+0 hover:no
  ≥119   ≥2055  go        lake0_lb+0 {crown,key} checkpoint:lake0_door0+0 hover:no
    ≥0   ≥2055  boundary  lake1_rb+0 {crown,key} checkpoint:lake1_rb+0 hover:no
  ≥254   ≥2309  go        lake1_lb+0 {crown,key} checkpoint:lake1_rb+0 hover:no
    ≥0   ≥2309  boundary  lake2_rb+0 {crown,key} checkpoint:lake2_rb+0 hover:no
  ≥242   ≥2551  go        lake2_door0+1 {crown,key} checkpoint:lake2_rb+0 hover:no
   ≥12   ≥2563  door      cave0_door0+0 {crown,key} checkpoint:cave0_door0+0 hover:no
   ≥31   ≥2594  go        cave0_door1-1 {crown,key} checkpoint:cave0_door0+0 hover:no
   ≥12   ≥2606  door      cave1_door0+0 {crown,key} checkpoint:cave1_door0+0 hover:no
    ≥8   ≥2614  go        cave1_item+1 {crown,gold,key} checkpoint:cave1_door0+0 hover:no
    ≥7   ≥2621  go        cave1_door0-1 {crown,gold,key} checkpoint:cave1_door0+0 hover:no
   ≥12   ≥2633  door      cave0_door1+0 {crown,gold,key} checkpoint:cave0_door1+0 hover:no
   ≥31   ≥2664  go        cave0_door0+1 {crown,gold,key} checkpoint:cave0_door1+0 hover:no
   ≥12   ≥2676  door      lake2_door0+0 {crown,gold,key} checkpoint:lake2_door0+0 hover:no
   ≥63   ≥2739  go        lake2_door2-1 {crown,gold,key} checkpoint:lake2_door0+0 hover:no
   ≥12   ≥2751  door      base1_door0+0 {crown,gold,key} checkpoint:base1_door0+0 hover:no
  ≥111   ≥2862  go        base1_door1-1 {crown,gold,key} checkpoint:base1_door0+0 hover:no
   ≥12   ≥2874  door      base0_door1+0 {crown,gold,key} checkpoint:base0_door1+0 hover:no
   ≥23   ≥2897  go        base0_door2-1 {crown,gold,key} checkpoint:base0_door1+0 hover:no
   ≥12   ≥2909  door      space2_door0+0 {crown,gold,key} checkpoint:space2_door0+0 hover:no
   ≥30   ≥2939  go        space2_item+1 {crown,gems,gold,key} checkpoint:space2_door0+0 hover:no

Let's walk through a subset of this route and interpret it.

                          forest1_lb+0 {} checkpoint:forest1_lb+0 hover:yes
  ≥254    ≥494  go        forest1_rb+0 {} checkpoint:forest1_lb+0 hover:yes
    ≥0    ≥494  boundary  forest2_lb+0 {} checkpoint:forest2_lb+0 hover:yes
  ≥159    ≥653  go        forest2_item-1 {key} checkpoint:forest2_lb+0 hover:no
   ≥17    ≥670  die       forest2_lb+0 {key} checkpoint:forest2_lb+0 hover:yes

The first transition here is a go between forest1_lb and forest1_rb (the left and right boundaries of the FOREST1 stage). It takes 254 ticks to traverse a stage from left to right when there are no obstacles. In this case, I believe that the actual measured cost for this transition will be 1 or 2 ticks greater, because there is a tall tree that probably requires slowing down to get over (see map). The next transition is a boundary between forest1_rb and forest1_lb, which I've conservatively estimated to take 0 time. Notice that a boundary transition updates the checkpoint. Then there is a go transition over to the left side of forest2_item to collect the key. The left side of the item location is shown as forest2_item-1; the center would be forest2_item+0 and the right side would be forest2_item+1. Here the algorithm has decided that it is best to collect this item from the left side, because we are about to go back to the left. The next transition is a die deathwarp back to the current checkpoint, forest2_lb. 17 ticks is my current estimate for how long it takes to play the "too bad" jingle when you die; in reality the cost will be greater because you additionally have to find/manipulate an enemy to take damage from. Notice that a die transition restores the ability to hover. Keep in mind that the logic graph is still missing parts that need to be manually defined. It naively assumes that all locations within a stage are reachable from all others, which is not actually true in every stage. For instance, the transition from lake2_rb to lake2_door0 requires Boots, Wand, or a hover, but the logic doesn't know that yet. Similarly cave0_door→cave0_door1 requires Boots, Wand, or hover; and cave1_door0→cave1_item requires Wand or hover.

Posted: 9/25/2020 10:57 PM

Post subject: Logic graph

Quote

Sand

He/Him

Player (125)

Joined: 6/26/2018
Posts: 154

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

Posted: 9/27/2020 10:36 PM

Post subject: Re: Video series

Quote

Radiant

Player (26)

Joined: 8/29/2011
Posts: 1206
Location: Amsterdam

Thanks for posting! I actually know this game pretty well (albeit from decades ago) so it's interesting to see it being picked apart like that!

Indie game developer

Posted: 9/28/2020 7:32 PM

Post subject: Startup optimization

Quote

Sand

He/Him

Player (125)

Joined: 6/26/2018
Posts: 154

2020-09-27 (3.25 h) Compiling, configuring, and running JPC-RR. Optimizing the boot sequence with regard to HDA/HDD and fdconfig.sys/autoexec.bat. In this session I compile JPC-RR from source and go through the process of making BIOS and disk images. I'm installing from source because I'm fairly sure I'm going to have to add a feature to support frame advance according to the programmable interval timer (IRQ0), rather than VGA refresh. Captain Comic game ticks are not synchronized to the VGA framerate, but run on their own fixed schedule. Then I test the speed of various settings during boot. When I did [3888] DOS Mega Man by Sand in 01:46.94, I did not realize the importance of boot settings until I was almost finished. This time, I want to get it settled early. In Mega Man, spending extra time during boot made levels load faster later on (see Post #478237 and following). The fastest option, for that game, was to run fdconfig.sys, then decline every option. With Captain Comic, though, it seems the fastest option is to decline running fdconfig.sys entirely. I tested six configurations:

game disk on HDA, skip fdconfig.sys, skip autoexec.bat
game disk on HDA, trace fdconfig.sys and say Y to everything, skip autoexec.bat
game disk on HDA, trace fdconfig.sys and say N to everything, skip autoexec.bat
game disk on HDD, skip fdconfig.sys, skip autoexec.bat
game disk on HDD, trace fdconfig.sys and say Y to everything, skip autoexec.bat
game disk on HDD, trace fdconfig.sys and say N to everything, skip autoexec.bat

In each condition, I worked through the boot menus and ran the commands to start the game (buffering BIOS keyboard input as much as possible), then timed (1) entering CASTLE0 via the door, and (2) traversing FOREST0 and entering FOREST1. I used a hacked executable that gives the Door Key and Lantern at startup, to allow entering the castle immediately. I chose these actions to exercise code paths that access the disk. The title sequence loads .EGA file graphics, then the map, tile, and enemy files for FOREST; entering CASTLE loads maps, tiles, and enemies for that level; entering FOREST1 should not cause any additional disk accesses. F12 prompt is the time until the "Press F12 for boot menu" prompt. A:\> is the time until the command prompt appears. story is the time until the first frame of SYS001.EGA. movement is the time until the first VGA frame where Comic visibly moves, when buffering a Right input at start. castle0 is the time until the first VGA frame showing the interior of CASTLE0, when buffering an Alt input at start. forest1 is the time until the first VGA frame showing FOREST1, when immediately moving to the right at start without bonking.

game disk	fdconfig.sys	autoexec.bat	F12 prompt	A:\>	story	movement	castle0	forest1
HDA	skip	skip	486 ms	1228 ms	2883 ms	13085 ms	13955 ms	39566 ms
HDA	Y to all	skip	486 ms	1285 ms	2940 ms	13142 ms	14012 ms	39623 ms
HDA	n to all	skip	486 ms	1271 ms	2940 ms	13142 ms	14012 ms	39623 ms
HDD	skip	skip	101 ms	843 ms	2512 ms	12714 ms	13570 ms	39181 ms
HDD	Y to all	skip	101 ms	914 ms	2555 ms	12771 ms	13627 ms	39238 ms
HDD	n to all	skip	101 ms	886 ms	2555 ms	12771 ms	13627 ms	39238 ms

The table confirms that HDD is a better choice than HDA. Besides the choice of game disk, it's clear that skipping fdconfig.sys is the best option. It starts out ahead and stays ahead, even after several disk accesses. So I'm going to go ahead with those settings unless I get some specific evidence otherwise. I only measured times to the precision of VGA refreshes, but later on I plan to do an automated search to find the earliest times at which the F12 prompt and the title screen accept input.

Posted: 10/3/2020 6:01 PM

Post subject: Lua scripting

Quote

Sand

He/Him

Player (125)

Joined: 6/26/2018
Posts: 154

2020-09-30 (4.0 h) Writing a Lua script to optimize boot and game startup. 2020-10-03 (4.5 h) Writing a Lua script to see game variables, including enemy spawn scheduling. In the last post I found the best boot-time options. Now I wrote a script to do a binary search and find the earliest moment at which those options can be activated. Ultimately this turns out not to help, because of fixed delays during boot and the coarseness of the game's tick rate. After optimizing, the time of first movement remains the same at 12714 ms. I spent a lot of time trying to make the binary search script work using the current version r11.8-rc2, without success. I was able to get a Lua script to restore a savestate once, but not twice. I tried various things, including a more recent commit with the log message "Try to fix race condition in restart from stop via Lua", but eventually gave up and switched back to r11.6-WIP with the anti-deadlock patch. I wrote a script to display some internal game state in a window. I'm going to use this to optimize movement and manipulate enemy spawns.

I measured the cost of the first few state transitions recommended by the route optimizer, up to collecting the Door Key. The measured transitions are the ones whose cost in the first column is prefixed by ‘=’. One neat thing is that measured costs can sometimes be reused when backtracking is necessary. For example, the transition forest1_lb+0→forest1_rb+0 with an empty inventory and no hover is measured to take 255 ticks. Later, the same transition is used, but with an inventory containing the Door Key and the Crown. The optmizer knows that neither of these inventory items affect intra-stage movement, so it can re-use a previously measured cost.

                       forest0_door0+1 R {} checkpoint:forest0_door0+1 hover:yes
=240   =240  go        forest0_rb+0 R {} checkpoint:forest0_door0+1 hover:no
  =1   =241  boundary  forest1_lb+0 R {} checkpoint:forest1_lb+0 hover:no
=255   =496  go        forest1_rb+0 R {} checkpoint:forest1_lb+0 hover:no
  =1   =497  boundary  forest2_lb+0 R {} checkpoint:forest2_lb+0 hover:no
=159   =656  go        forest2_item-1 L {key} checkpoint:forest2_lb+0 hover:no
 ≥17   ≥673  die       forest2_lb+0 L {key} checkpoint:forest2_lb+0 hover:yes
  =1   ≥674  boundary  forest1_rb+0 L {key} checkpoint:forest1_rb+0 hover:yes
≥254   ≥928  go        forest1_lb+0 L {key} checkpoint:forest1_rb+0 hover:yes
  =1   ≥929  boundary  forest0_rb+0 L {key} checkpoint:forest0_rb+0 hover:yes
≥240  ≥1169  go        forest0_door0+1 L {key} checkpoint:forest0_rb+0 hover:yes
 ≥12  ≥1181  door      castle0_door0+0 L {key} checkpoint:castle0_door0+0 hover:no
 ≥17  ≥1198  die       castle0_door0+0 L {key} checkpoint:castle0_door0+0 hover:yes
  ≥2  ≥1200  go        castle0_item+1 L {key,crown} checkpoint:castle0_door0+0 hover:no
 ≥17  ≥1217  die       castle0_door0+0 R {key,crown} checkpoint:castle0_door0+0 hover:no
 ≥12  ≥1229  door      forest0_door0+0 R {key,crown} checkpoint:forest0_door0+0 hover:no
≥241  ≥1470  go        forest0_rb+0 R {key,crown} checkpoint:forest0_door0+0 hover:no
  =1  ≥1471  boundary  forest1_lb+0 R {key,crown} checkpoint:forest1_lb+0 hover:no
=255  ≥1726  go        forest1_rb+0 R {key,crown} checkpoint:forest1_lb+0 hover:no
  =1  ≥1727  boundary  forest2_lb+0 R {key,crown} checkpoint:forest2_lb+0 hover:no
≥238  ≥1965  go        forest2_door0-1 L {key,crown} checkpoint:forest2_lb+0 hover:no
 ≥12  ≥1977  door      lake0_door0+0 L {key,crown} checkpoint:lake0_door0+0 hover:no
≥119  ≥2096  go        lake0_lb+0 L {key,crown} checkpoint:lake0_door0+0 hover:no
  =1  ≥2097  boundary  lake1_rb+0 L {key,crown} checkpoint:lake1_rb+0 hover:no
≥254  ≥2351  go        lake1_lb+0 L {key,crown} checkpoint:lake1_rb+0 hover:no
  =1  ≥2352  boundary  lake2_rb+0 L {key,crown} checkpoint:lake2_rb+0 hover:no
 ≥17  ≥2369  die       lake2_rb+0 L {key,crown} checkpoint:lake2_rb+0 hover:yes
≥178  ≥2547  go        lake2_door2+1 R {key,crown} checkpoint:lake2_rb+0 hover:yes
 ≥12  ≥2559  door      base1_door0+0 R {key,crown} checkpoint:base1_door0+0 hover:no
  ≥0  ≥2559  go        base1_door2+0 R {key,crown} checkpoint:base1_door0+0 hover:no
 ≥12  ≥2571  door      base2_door1+0 R {key,crown} checkpoint:base2_door1+0 hover:no
 ≥10  ≥2581  go        base2_item-1 L {key,boots,crown} checkpoint:base2_door1+0 hover:no
  ≥0  ≥2581  go        base2_door1+0 L {key,boots,crown} checkpoint:base2_door1+0 hover:no
 ≥12  ≥2593  door      base1_door2+0 L {key,boots,crown} checkpoint:base1_door2+0 hover:no
  ≥0  ≥2593  go        base1_door0-1 L {key,boots,crown} checkpoint:base1_door2+0 hover:no
 ≥12  ≥2605  door      lake2_door2+0 L {key,boots,crown} checkpoint:lake2_door2+0 hover:no
  ≥0  ≥2605  go        lake2_door2-1 L {key,boots,crown} checkpoint:lake2_door2+0 hover:no
 ≥52  ≥2657  go        lake2_door0+1 R {key,boots,crown} checkpoint:lake2_door2+0 hover:no
 ≥12  ≥2669  door      cave0_door0+0 R {key,boots,crown} checkpoint:cave0_door0+0 hover:no
 ≥31  ≥2700  go        cave0_door1-1 L {key,boots,crown} checkpoint:cave0_door0+0 hover:no
 ≥12  ≥2712  door      cave1_door0+0 L {key,boots,crown} checkpoint:cave1_door0+0 hover:no
 ≥17  ≥2729  die       cave1_door0+0 R {key,boots,crown} checkpoint:cave1_door0+0 hover:yes
 ≥17  ≥2746  go        cave1_rb+0 R {key,boots,crown} checkpoint:cave1_door0+0 hover:yes
  =1  ≥2747  boundary  cave2_lb+0 R {key,boots,crown} checkpoint:cave2_lb+0 hover:yes
 ≥63  ≥2810  go        cave2_item-1 R {key,boots,wand,crown} checkpoint:cave2_lb+0 hover:yes
 ≥17  ≥2827  die       cave2_lb+0 L {key,boots,wand,crown} checkpoint:cave2_lb+0 hover:yes
  =1  ≥2828  boundary  cave1_rb+0 L {key,boots,wand,crown} checkpoint:cave1_rb+0 hover:yes
  ≥6  ≥2834  go        cave1_door0+1 L {key,boots,wand,crown} checkpoint:cave1_rb+0 hover:yes
  ≥0  ≥2834  go        cave1_item+1 R {key,boots,wand,crown,gold} checkpoint:cave1_rb+0 hover:yes
  ≥7  ≥2841  go        cave1_door0-1 L {key,boots,wand,crown,gold} checkpoint:cave1_rb+0 hover:no
 ≥12  ≥2853  door      cave0_door1+0 L {key,boots,wand,crown,gold} checkpoint:cave0_door1+0 hover:no
  ≥0  ≥2853  go        cave0_door1-1 L {key,boots,wand,crown,gold} checkpoint:cave0_door1+0 hover:no
 ≥20  ≥2873  go        cave0_door0+1 R {key,boots,wand,crown,gold} checkpoint:cave0_door1+0 hover:no
 ≥12  ≥2885  door      lake2_door0+0 R {key,boots,wand,crown,gold} checkpoint:lake2_door0+0 hover:no
 ≥63  ≥2948  go        lake2_door2-1 R {key,boots,wand,crown,gold} checkpoint:lake2_door0+0 hover:no
 ≥12  ≥2960  door      base1_door0+0 R {key,boots,wand,crown,gold} checkpoint:base1_door0+0 hover:no
≥111  ≥3071  go        base1_door1-1 R {key,boots,wand,crown,gold} checkpoint:base1_door0+0 hover:no
 ≥12  ≥3083  door      base0_door1+0 R {key,boots,wand,crown,gold} checkpoint:base0_door1+0 hover:no
 ≥23  ≥3106  go        base0_door2-1 L {key,boots,wand,crown,gold} checkpoint:base0_door1+0 hover:no
 ≥12  ≥3118  door      space2_door0+0 L {key,boots,wand,crown,gold} checkpoint:space2_door0+0 hover:no
  ≥0  ≥3118  go        space2_door0-1 L {key,boots,wand,crown,gold} checkpoint:space2_door0+0 hover:no
 ≥19  ≥3137  go        space2_item+1 R {key,boots,wand,gems,crown,gold} checkpoint:space2_door0+0 hover:no

Posted: 10/9/2020 6:39 PM

Post subject: Measured costs up to CASTLE

Quote

Sand

He/Him

Player (125)

Joined: 6/26/2018
Posts: 154

2020-10-05 (3.0 h) Adding the ability to advance by game ticks (110 ms) rather than VGA frames (14 ms). 2020-10-07 (4.5 h) Experimenting with movement, replacement of facing by x_momentum in State. 2020-10-09 (4.25 h) Removal of x_momentum from State, manual cost measurement up to CASTLE. The Captain Comic game loop is synchronized not with the VGA refresh, but with cycles of the programmable interval timer (IRQ 0). JPC-RR has a feature to advance to the next VGA frame, but not the next cycle of IRQ 0. I added a feature to the HUD script to advance the game to the next tick when I press ‘G’. Since the beginning, I have assumed that a state in the virtual graph would have to record what direction Comic is facing, because I thought it always cost at least 1 tick to change Comic's facing direction. That assumption turned out to be false—from a standstill, you can both change direction and move in the new direction in the same tick, by jumping backward. But this zero-cost turnaround technique is only possible when an internal variable, which I call x_momentum, is zero. x_momentum becomes positive when moving to the right and negative when moving to the left. Therefore I replaced facing ∈ {LEFT, RIGHT} with x_momentum ∈ {NEGATIVE, ZERO, POSITIVE} in the State structure representing a vertex in the virtual graph. Through further experimentation, I found that it is possible to reduce x_momentum to zero, even while moving, by releasing direction keys in the air. Since I now believe that it is almost always possible to change direction at zero cost, I removed x_momentum from State completely. This has the nice side effect of making the route optimizer faster: now it takes ≈3 s instead of ≈10 s.

Sand wrote:

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.

I found a bug in the automatic cost inference function that affects the route. When you have the Teleport Wand, you can move faster when going leftward by abusing the way the game snaps you to an even tile boundary. The cost inference function reflects this trick by making right-to-left transitions less expensive while you hold the Teleport Wand. The bug was that the left-teleport ability was being ascribed to the Boots, not the Teleport Wand. With the bug fixed, the route does not collect the Boots at all, and currently matches one of Kabuto's routes exactly. There are two variables that govern the enemy spawning schedule. enemy_respawn_counter_cycle loops through the cycle 20, 40, 60, 80, 100. It advances in the cycle every time an enemy despawns, and controls how many ticks will elapse before the enemy in that slot tries to spawn again. enemy_respawn_position_cycle loops through the cycle 0, 2, 4, 6. It advances every time an enemy tries to spawn. Enemies can only spawn (1) at a vertical position at or above the level of Comic's feet, (2) directly above a solid tile, (3) at a horizontal position enemy_respawn_position_cycle units past the edge of the playfield, in the direction Comic is facing. If an enemy is eligible to spawn but there is no position that satisfies all three conditions, enemy_respawn_position_cycle advances but the enemy remains unspawned. I optimized the first difficult enemy manipulation / deathwarp, after collecting the Door Key. There are no pits nearby, and nowhere to the right of the high platform for an enemy to spawn, so the fastest way to die is to run back and collide with an enemy to the left. The best technique I found was to allow an enemy to spawn up on the item platform as you approach, pass under the enemy as it flies to the left, and time the item grab so that the enemy bounces off the edge of the playfield and starts moving to the right, just as you turn back to the left. After collecting the Door Key, it takes 8 ticks to collide with the enemy, 8 ticks to play the death animation, and 17 ticks to play the death music and respawn, for a total cost of 33 ticks overall for the deathwarp.

Measured costs currently look like the following listing. In the example G["forest0_door0"], +1, True, forest0_door0 is the vertex, +1 is the x offset for "wide" vertices that have a left, middle, and right, and True is whether a hover is currently possible. I assign a cost of INFINITY to transitions that the virtual graph doesn't inherently know are impossible, such as those that try to maintain hover for too long.

Language: python
# Cannot maintain hover across all of forest0 and into forest1 (actually you can
# maintain it a little bit into forest1, but we will approximate and say it's
# impossible).
measure_cost(INFINITY, How.GO,
    G["forest0_door0"], ANY, True,
    G["forest0_rb"],     +0, True)
# 002.jrsr @0 comic_x == 14; @240 comic_x == 254
measure_cost(240, How.GO,
    G["forest0_door0"], +1, True,
    G["forest0_rb"],    +0, False)
# 002.jrsr @243 comic_x == 254; @244 comic_x == 0
measure_cost(1, How.BOUNDARY,
    G["forest0_rb"], +0, False,
    G["forest1_lb"], +0, False)
# 002.jrsr @244 comic_x == 0; @499 comic_x == 254
measure_cost(255, How.GO, # 1-tick bonk getting over the tall tree
    G["forest1_lb"], +0, False,
    G["forest1_rb"], +0, False)
# 002.jrsr @499 comic_x == 254; @500 comic_x == 0
measure_cost(1, How.BOUNDARY,
    G["forest1_rb"], +0, False,
    G["forest2_lb"], +0, False)
# 002.jrsr @500 comic_x == 0; @659 comic_x == 159
measure_cost(159, How.GO,
    G["forest2_lb"],   +0, False,
    G["forest2_item"], -1, False)
# 004.jrsr @659 comic_x == 159; @667 collision; @692 comic_x == 0
measure_cost(33, How.DIE,
    G["forest2_item"], -1, False,
    G["forest2_lb"],   +0, ANY)

Here is how the route stands currently. Costs prefixed by ‘=’ are empirically measured. Ones prefixed by ‘≥’ are automatic lower bounds.

                       forest0_door0+1 {} checkpoint:forest0_door0+1 hover:yes
=240   =240  go        forest0_rb+0 {} checkpoint:forest0_door0+1 hover:no
  =1   =241  boundary  forest1_lb+0 {} checkpoint:forest1_lb+0 hover:no
=255   =496  go        forest1_rb+0 {} checkpoint:forest1_lb+0 hover:no
  =1   =497  boundary  forest2_lb+0 {} checkpoint:forest2_lb+0 hover:no
=159   =656  go        forest2_item-1 {key} checkpoint:forest2_lb+0 hover:no
 =33   =689  die       forest2_lb+0 {key} checkpoint:forest2_lb+0 hover:yes
  =1   =690  boundary  forest1_rb+0 {key} checkpoint:forest1_rb+0 hover:yes
=254   =944  go        forest1_lb+0 {key} checkpoint:forest1_rb+0 hover:no
  =1   =945  boundary  forest0_rb+0 {key} checkpoint:forest0_rb+0 hover:no
=240  =1185  go        forest0_door0+1 {key} checkpoint:forest0_rb+0 hover:no
 =13  =1198  door      castle0_door0+0 {key} checkpoint:castle0_door0+0 hover:no
 =53  =1251  die       castle0_door0+0 {key} checkpoint:castle0_door0+0 hover:yes
  ≥2  ≥1253  go        castle0_item+1 {key,crown} checkpoint:castle0_door0+0 hover:no
 ≥17  ≥1270  die       castle0_door0+0 {key,crown} checkpoint:castle0_door0+0 hover:yes
 ≥12  ≥1282  door      forest0_door0+0 {key,crown} checkpoint:forest0_door0+0 hover:no
≥241  ≥1523  go        forest0_rb+0 {key,crown} checkpoint:forest0_door0+0 hover:no
  =1  ≥1524  boundary  forest1_lb+0 {key,crown} checkpoint:forest1_lb+0 hover:no
=255  ≥1779  go        forest1_rb+0 {key,crown} checkpoint:forest1_lb+0 hover:no
  =1  ≥1780  boundary  forest2_lb+0 {key,crown} checkpoint:forest2_lb+0 hover:no
≥238  ≥2018  go        forest2_door0-1 {key,crown} checkpoint:forest2_lb+0 hover:no
 ≥12  ≥2030  door      lake0_door0+0 {key,crown} checkpoint:lake0_door0+0 hover:no
 ≥17  ≥2047  die       lake0_door0+0 {key,crown} checkpoint:lake0_door0+0 hover:yes
≥119  ≥2166  go        lake0_lb+0 {key,crown} checkpoint:lake0_door0+0 hover:yes
  ≥1  ≥2167  boundary  lake1_rb+0 {key,crown} checkpoint:lake1_rb+0 hover:yes
≥254  ≥2421  go        lake1_lb+0 {key,crown} checkpoint:lake1_rb+0 hover:yes
  ≥1  ≥2422  boundary  lake2_rb+0 {key,crown} checkpoint:lake2_rb+0 hover:yes
≥242  ≥2664  go        lake2_door0+1 {key,crown} checkpoint:lake2_rb+0 hover:no
 ≥12  ≥2676  door      cave0_door0+0 {key,crown} checkpoint:cave0_door0+0 hover:no
 ≥17  ≥2693  die       cave0_door0+0 {key,crown} checkpoint:cave0_door0+0 hover:yes
 ≥31  ≥2724  go        cave0_door1-1 {key,crown} checkpoint:cave0_door0+0 hover:no
 ≥12  ≥2736  door      cave1_door0+0 {key,crown} checkpoint:cave1_door0+0 hover:no
 ≥17  ≥2753  die       cave1_door0+0 {key,crown} checkpoint:cave1_door0+0 hover:yes
 ≥17  ≥2770  go        cave1_rb+0 {key,crown} checkpoint:cave1_door0+0 hover:yes
  ≥1  ≥2771  boundary  cave2_lb+0 {key,crown} checkpoint:cave2_lb+0 hover:yes
 ≥63  ≥2834  go        cave2_item-1 {key,wand,crown} checkpoint:cave2_lb+0 hover:no
 ≥17  ≥2851  die       cave2_lb+0 {key,wand,crown} checkpoint:cave2_lb+0 hover:yes
  ≥1  ≥2852  boundary  cave1_rb+0 {key,wand,crown} checkpoint:cave1_rb+0 hover:yes
  ≥6  ≥2858  go        cave1_door0+1 {key,wand,crown} checkpoint:cave1_rb+0 hover:yes
  ≥0  ≥2858  go        cave1_item+1 {key,wand,crown,gold} checkpoint:cave1_rb+0 hover:yes
  ≥7  ≥2865  go        cave1_door0-1 {key,wand,crown,gold} checkpoint:cave1_rb+0 hover:yes
 ≥12  ≥2877  door      cave0_door1+0 {key,wand,crown,gold} checkpoint:cave0_door1+0 hover:no
  ≥0  ≥2877  go        cave0_door1-1 {key,wand,crown,gold} checkpoint:cave0_door1+0 hover:no
 ≥20  ≥2897  go        cave0_door0+1 {key,wand,crown,gold} checkpoint:cave0_door1+0 hover:no
 ≥12  ≥2909  door      lake2_door0+0 {key,wand,crown,gold} checkpoint:lake2_door0+0 hover:no
 ≥63  ≥2972  go        lake2_door2-1 {key,wand,crown,gold} checkpoint:lake2_door0+0 hover:no
 ≥12  ≥2984  door      base1_door0+0 {key,wand,crown,gold} checkpoint:base1_door0+0 hover:no
≥111  ≥3095  go        base1_door1-1 {key,wand,crown,gold} checkpoint:base1_door0+0 hover:no
 ≥12  ≥3107  door      base0_door1+0 {key,wand,crown,gold} checkpoint:base0_door1+0 hover:no
 ≥23  ≥3130  go        base0_door2-1 {key,wand,crown,gold} checkpoint:base0_door1+0 hover:no
 ≥12  ≥3142  door      space2_door0+0 {key,wand,crown,gold} checkpoint:space2_door0+0 hover:no
  ≥0  ≥3142  go        space2_door0-1 {key,wand,crown,gold} checkpoint:space2_door0+0 hover:no
 ≥19  ≥3161  go        space2_item+1 {key,wand,gems,crown,gold} checkpoint:space2_door0+0 hover:no

Posted: 10/16/2020 9:38 PM

Post subject: Measured costs up to LAKE2

Quote

Sand

He/Him

Player (125)

Joined: 6/26/2018
Posts: 154

2020-10-11 (5.0 h) Optimizing collecting the Crown and the escape from CASTLE. 2020-10-16 (2.5 h) Measuring costs from CASTLE to LAKE2, small enhancements to the optimizer. Collecting the Crown is a tricky operation that involves two intentional deaths.

Enter the castle, which sets Comic's respawn checkpoint to castle0_door0.
Take damage from an enemy and die. You respawn at castle0_door0, now with the ability to hover.
Hover upward and clip through a wall. Collect the Crown.
Take damage from enemies to die again, respawning at castle0_door0.
Exit the castle via the door.

Optimizing this process requires careful attention to enemy spawn variables—in fact the whole process is bottlenecked on how quickly we can collide with enemies and have them respawn.

Sand wrote:

There are two variables that govern the enemy spawning schedule. enemy_respawn_counter_cycle loops through the cycle 20, 40, 60, 80, 100. It advances in the cycle every time an enemy despawns, and controls how many ticks will elapse before the enemy in that slot tries to spawn again. enemy_respawn_position_cycle loops through the cycle 0, 2, 4, 6. It advances every time an enemy tries to spawn. Enemies can only spawn (1) at a vertical position at or above the level of Comic's feet, (2) directly above a solid tile, (3) at a horizontal position enemy_respawn_position_cycle units past the edge of the playfield, in the direction Comic is facing. If an enemy is eligible to spawn but there is no position that satisfies all three conditions, enemy_respawn_position_cycle advances but the enemy remains unspawned.

The first death is easy. Enter the castle with zero HP. (Comic dies not at zero HP, but when his HP goes below zero). Make sure enemy_respawn_position_cycle is 0, so that the first enemy to spawn will spawn as close as possible. Get as close to the edge of the playfield as you can without scrolling the screen, wait for the enemy to spawn, and run into it. Although it doesn't matter for this first death, for the next death you will want enemy_respawn_counter_cycle to be 100, so that it rolls over to its minimum value of 20 when you kill the enemy. After Comic respawns, it's a race to take 7 damage as quickly as possible, while still clipping into the item room and collecting the Crown. All four enemy slots in this stage are used, and the first and third enemies are fast, meaning they move on every frame, not every other frame. The first objective is to kill 3 enemies as quickly as possible (taking 3 damage in the process), thereby starting the respawn timer for the 7th enemy, the one that will kill Comic. In addition, you want the third enemy killed to be one of the fast ones, so that it reaches Comic quickly once it does respawn. All enemies try to spawn for the first time 21 ticks after Comic respawns, but only one enemy can spawn per tick, so the first three enemies spawn after 21, 22, and 23 ticks. After the first spawn, enemies respawn according to enemy_respawn_counter_cycle. You want enemy_respawn_counter_cycle to be 20, so that the first three enemies' respawn timers get set to 20, 40, and 60 ticks. Now you have 60 ticks in which to take a 4th point of damage from the surviving enemy, clip into the item room and collect the Crown, take 2 more points of damage from the enemies that spawn after 20 and 40 ticks, and await the final enemy spawn. During this time, you have the opportunity to advance enemy_respawn_position_cycle to 0, by spawn-blocking enemies. When the final enemy spawns, run into it as fast as possible. The castle is dark through all this, because we don't have the Lantern. Here is what it would look like with the lights on:

The fact that the roundtrip to collect the Crown is bottlenecked on enemy spawns, not Comic's movement, violates an assumption of the shortest-path meta-algorithm; namely, that state transition costs are independent. Getting up to the Crown and deathwarping out takes a fixed amount of time, because you are waiting on enemies during most of it. You can get the Crown faster, and you can deathwarp out faster, but you cannot do both; you can only split the cost between the two transitions differently. There was a similar situation with the deathwarp in FOREST2: dying quickly after collecting the Door Key requires manipulating Comic's HP and enemy spawn variables prior to getting there. The difference, there, is that the necessary manipulations can be done without losing time in a prior transition, which is not the case here. Speaking generally, this violation of assumptions means that the meta-algorithm is not guaranteed to find an optimum route. Conceivably, there could be an optimum route that uses one of these two state transitions, but its cost is not as low as it could be, because of the lack of independence in the route we are currently working on. But I don't think it's actually a problem, given what the logic graph looks like in CASTLE.


lake2_rb	lake1_lb

The rest of the optimization up to LAKE2 is straightforward. The most interesting part is how the algorithm optimizes the death into hover that's required in LAKE2. Before measuring the cost of dying, it asks to cross from LAKE1 into LAKE2, and die there:

=254  =2517  go        lake1_lb+0 {key,crown} checkpoint:lake1_rb+0 hover:no
  =1  =2518  boundary  lake2_rb+0 {key,crown} checkpoint:lake2_rb+0 hover:no
 ≥17  ≥2535  die       lake2_rb+0 {key,crown} checkpoint:lake2_rb+0 hover:yes
≥242  ≥2777  go        lake2_door0+1 {key,crown} checkpoint:lake2_rb+0 hover:no

The inferred lower bound cost for dying is 17 ticks. We experimentally measure the actual cost of dying in LAKE2, and find that it is actually 35 ticks, because you have to walk a short distance before you can fall in a pit.

Language: python
measure_cost(35, How.DIE,
    "lake2_rb", +0, False,
    "lake2_rb", +0, True)

Now the algorithm says, what if instead of dying in LAKE2, you went back into LAKE1, and died there?

=254  =2517  go        lake1_lb+0 {key,crown} checkpoint:lake1_rb+0 hover:no
  =1  =2518  boundary  lake2_rb+0 {key,crown} checkpoint:lake2_rb+0 hover:no
  ≥1  ≥2519  boundary  lake1_lb+0 {key,crown} checkpoint:lake1_lb+0 hover:no
 ≥17  ≥2536  die       lake1_lb+0 {key,crown} checkpoint:lake1_lb+0 hover:yes
  ≥1  ≥2537  boundary  lake2_rb+0 {key,crown} checkpoint:lake2_rb+0 hover:yes
≥242  ≥2779  go        lake2_door0+1 {key,crown} checkpoint:lake2_rb+0 hover:no

The pit is closer in LAKE1, so dying there takes only 27 ticks.

Language: python
measure_cost(1, How.BOUNDARY,
    "lake2_rb", +0, False,
    "lake1_lb", +0, False)
measure_cost(27, How.DIE,
    "lake1_lb", +0, False,
    "lake1_lb", +0, True)
measure_cost(1, How.BOUNDARY,
    "lake1_lb", +0, True,
    "lake2_rb", +0, True)

Even with the 2 additional ticks required to cross the stage boundary twice, it's faster overall.

=254  =2517  go        lake1_lb+0 {key,crown} checkpoint:lake1_rb+0 hover:no
  =1  =2518  boundary  lake2_rb+0 {key,crown} checkpoint:lake2_rb+0 hover:no
  =1  =2519  boundary  lake1_lb+0 {key,crown} checkpoint:lake1_lb+0 hover:no
 =27  =2546  die       lake1_lb+0 {key,crown} checkpoint:lake1_lb+0 hover:yes
  =1  =2547  boundary  lake2_rb+0 {key,crown} checkpoint:lake2_rb+0 hover:yes
≥242  ≥2789  go        lake2_door0+1 {key,crown} checkpoint:lake2_rb+0 hover:no

This is how the route stands currently. The total time can still only go up, but we're well past halfway finished.

                       forest0_door0+1 {} checkpoint:forest0_door0+1 hover:yes
=240   =240  go        forest0_rb+0 {} checkpoint:forest0_door0+1 hover:no
  =1   =241  boundary  forest1_lb+0 {} checkpoint:forest1_lb+0 hover:no
=255   =496  go        forest1_rb+0 {} checkpoint:forest1_lb+0 hover:no
  =1   =497  boundary  forest2_lb+0 {} checkpoint:forest2_lb+0 hover:no
=159   =656  go        forest2_item-1 {key} checkpoint:forest2_lb+0 hover:no
 =33   =689  die       forest2_lb+0 {key} checkpoint:forest2_lb+0 hover:yes
  =1   =690  boundary  forest1_rb+0 {key} checkpoint:forest1_rb+0 hover:yes
=254   =944  go        forest1_lb+0 {key} checkpoint:forest1_rb+0 hover:no
  =1   =945  boundary  forest0_rb+0 {key} checkpoint:forest0_rb+0 hover:no
=240  =1185  go        forest0_door0+1 {key} checkpoint:forest0_rb+0 hover:no
 =13  =1198  door      castle0_door0+0 {key} checkpoint:castle0_door0+0 hover:no
 =52  =1250  die       castle0_door0+0 {key} checkpoint:castle0_door0+0 hover:yes
 =48  =1298  go        castle0_item-1 {key,crown} checkpoint:castle0_door0+0 hover:yes
 =83  =1381  die       castle0_door0+0 {key,crown} checkpoint:castle0_door0+0 hover:no
 =13  =1394  door      forest0_door0+0 {key,crown} checkpoint:forest0_door0+0 hover:no
=241  =1635  go        forest0_rb+0 {key,crown} checkpoint:forest0_door0+0 hover:no
  =1  =1636  boundary  forest1_lb+0 {key,crown} checkpoint:forest1_lb+0 hover:no
=255  =1891  go        forest1_rb+0 {key,crown} checkpoint:forest1_lb+0 hover:no
  =1  =1892  boundary  forest2_lb+0 {key,crown} checkpoint:forest2_lb+0 hover:no
=238  =2130  go        forest2_door0-1 {key,crown} checkpoint:forest2_lb+0 hover:no
 =13  =2143  door      lake0_door0+0 {key,crown} checkpoint:lake0_door0+0 hover:no
=119  =2262  go        lake0_lb+0 {key,crown} checkpoint:lake0_door0+0 hover:no
  =1  =2263  boundary  lake1_rb+0 {key,crown} checkpoint:lake1_rb+0 hover:no
=254  =2517  go        lake1_lb+0 {key,crown} checkpoint:lake1_rb+0 hover:no
  =1  =2518  boundary  lake2_rb+0 {key,crown} checkpoint:lake2_rb+0 hover:no
  =1  =2519  boundary  lake1_lb+0 {key,crown} checkpoint:lake1_lb+0 hover:no
 =27  =2546  die       lake1_lb+0 {key,crown} checkpoint:lake1_lb+0 hover:yes
  =1  =2547  boundary  lake2_rb+0 {key,crown} checkpoint:lake2_rb+0 hover:yes
≥242  ≥2789  go        lake2_door0+1 {key,crown} checkpoint:lake2_rb+0 hover:no
 ≥12  ≥2801  door      cave0_door0+0 {key,crown} checkpoint:cave0_door0+0 hover:no
 ≥17  ≥2818  die       cave0_door0+0 {key,crown} checkpoint:cave0_door0+0 hover:yes
 ≥31  ≥2849  go        cave0_door1-1 {key,crown} checkpoint:cave0_door0+0 hover:no
 ≥12  ≥2861  door      cave1_door0+0 {key,crown} checkpoint:cave1_door0+0 hover:no
 ≥17  ≥2878  die       cave1_door0+0 {key,crown} checkpoint:cave1_door0+0 hover:yes
 ≥17  ≥2895  go        cave1_rb+0 {key,crown} checkpoint:cave1_door0+0 hover:yes
  ≥1  ≥2896  boundary  cave2_lb+0 {key,crown} checkpoint:cave2_lb+0 hover:yes
 ≥63  ≥2959  go        cave2_item-1 {key,wand,crown} checkpoint:cave2_lb+0 hover:yes
 ≥17  ≥2976  die       cave2_lb+0 {key,wand,crown} checkpoint:cave2_lb+0 hover:yes
  ≥1  ≥2977  boundary  cave1_rb+0 {key,wand,crown} checkpoint:cave1_rb+0 hover:yes
  ≥6  ≥2983  go        cave1_door0+1 {key,wand,crown} checkpoint:cave1_rb+0 hover:no
  ≥0  ≥2983  go        cave1_item+1 {key,wand,crown,gold} checkpoint:cave1_rb+0 hover:no
  ≥7  ≥2990  go        cave1_door0-1 {key,wand,crown,gold} checkpoint:cave1_rb+0 hover:no
 ≥12  ≥3002  door      cave0_door1+0 {key,wand,crown,gold} checkpoint:cave0_door1+0 hover:no
  ≥0  ≥3002  go        cave0_door1-1 {key,wand,crown,gold} checkpoint:cave0_door1+0 hover:no
 ≥20  ≥3022  go        cave0_door0+1 {key,wand,crown,gold} checkpoint:cave0_door1+0 hover:no
 ≥12  ≥3034  door      lake2_door0+0 {key,wand,crown,gold} checkpoint:lake2_door0+0 hover:no
 ≥63  ≥3097  go        lake2_door2-1 {key,wand,crown,gold} checkpoint:lake2_door0+0 hover:no
 ≥12  ≥3109  door      base1_door0+0 {key,wand,crown,gold} checkpoint:base1_door0+0 hover:no
≥111  ≥3220  go        base1_door1-1 {key,wand,crown,gold} checkpoint:base1_door0+0 hover:no
 ≥12  ≥3232  door      base0_door1+0 {key,wand,crown,gold} checkpoint:base0_door1+0 hover:no
 ≥23  ≥3255  go        base0_door2-1 {key,wand,crown,gold} checkpoint:base0_door1+0 hover:no
 ≥12  ≥3267  door      space2_door0+0 {key,wand,crown,gold} checkpoint:space2_door0+0 hover:no
  ≥0  ≥3267  go        space2_item-1 {key,wand,gems,crown,gold} checkpoint:space2_door0+0 hover:no

Posted: 10/30/2020 6:04 AM

Post subject: Mostly measured costs for a Boots-less route

Quote

Sand

He/Him

Player (125)

Joined: 6/26/2018
Posts: 154

2020-10-20 (2.25 h) Writing a Lua script to optimize the hover in LAKE2, measuring costs up to CAVE0. 2020-10-21 (3.25 h) Measuring costs through CAVE, with the exception of the deliberate death in CAVE1. 2020-10-28 (5.0 h) Working on (and then abandoning) making State more precisely represent the capacity for left-teleports. Measuring costs through collecting the Gems. Starting a Lua script to optimize the death in CAVE1. LAKE2 requires a hover over the wall, in order to access the CAVE level without going through SPACE and BASE. I had assumed that I would be able to do the hover without stopping horizontally, but when I tried it, I couldn't do it without bonking for at least one tick. I wrote a Lua script to brute-force inputs for the hover, and it found a tricky hover that abuses Comic's collision model and avoids bonking totally. Measuring costs through CAVE to get the Gold and Wand, and through BASE to get the Gems, is straightforward with one exception: the death to initiate hover from the pit in CAVE1, probably the hardest manipulation in the run. Here is the route, with all costs measured exactly except for one inferred ‘≥17’ to die in cave1_door0:

                       forest0_door0+1 {} checkpoint:forest0_door0+1 hover:yes
=240   =240  go        forest0_rb+0 {} checkpoint:forest0_door0+1 hover:no
  =1   =241  boundary  forest1_lb+0 {} checkpoint:forest1_lb+0 hover:no
=255   =496  go        forest1_rb+0 {} checkpoint:forest1_lb+0 hover:no
  =1   =497  boundary  forest2_lb+0 {} checkpoint:forest2_lb+0 hover:no
=159   =656  go        forest2_item-1 {key} checkpoint:forest2_lb+0 hover:no
 =33   =689  die       forest2_lb+0 {key} checkpoint:forest2_lb+0 hover:yes
  =1   =690  boundary  forest1_rb+0 {key} checkpoint:forest1_rb+0 hover:yes
=254   =944  go        forest1_lb+0 {key} checkpoint:forest1_rb+0 hover:no
  =1   =945  boundary  forest0_rb+0 {key} checkpoint:forest0_rb+0 hover:no
=240  =1185  go        forest0_door0+1 {key} checkpoint:forest0_rb+0 hover:no
 =13  =1198  door      castle0_door0+0 {key} checkpoint:castle0_door0+0 hover:no
 =52  =1250  die       castle0_door0+0 {key} checkpoint:castle0_door0+0 hover:yes
 =48  =1298  go        castle0_item-1 {key,crown} checkpoint:castle0_door0+0 hover:no
 =83  =1381  die       castle0_door0+0 {key,crown} checkpoint:castle0_door0+0 hover:no
 =13  =1394  door      forest0_door0+0 {key,crown} checkpoint:forest0_door0+0 hover:no
=241  =1635  go        forest0_rb+0 {key,crown} checkpoint:forest0_door0+0 hover:no
  =1  =1636  boundary  forest1_lb+0 {key,crown} checkpoint:forest1_lb+0 hover:no
=255  =1891  go        forest1_rb+0 {key,crown} checkpoint:forest1_lb+0 hover:no
  =1  =1892  boundary  forest2_lb+0 {key,crown} checkpoint:forest2_lb+0 hover:no
=238  =2130  go        forest2_door0-1 {key,crown} checkpoint:forest2_lb+0 hover:no
 =13  =2143  door      lake0_door0+0 {key,crown} checkpoint:lake0_door0+0 hover:no
=119  =2262  go        lake0_lb+0 {key,crown} checkpoint:lake0_door0+0 hover:no
  =1  =2263  boundary  lake1_rb+0 {key,crown} checkpoint:lake1_rb+0 hover:no
=254  =2517  go        lake1_lb+0 {key,crown} checkpoint:lake1_rb+0 hover:no
  =1  =2518  boundary  lake2_rb+0 {key,crown} checkpoint:lake2_rb+0 hover:no
  =1  =2519  boundary  lake1_lb+0 {key,crown} checkpoint:lake1_lb+0 hover:no
 =26  =2545  die       lake1_lb+0 {key,crown} checkpoint:lake1_lb+0 hover:yes
  =1  =2546  boundary  lake2_rb+0 {key,crown} checkpoint:lake2_rb+0 hover:yes
=242  =2788  go        lake2_door0+1 {key,crown} checkpoint:lake2_rb+0 hover:yes
 =13  =2801  door      cave0_door0+0 {key,crown} checkpoint:cave0_door0+0 hover:no
 =36  =2837  die       cave0_door0+0 {key,crown} checkpoint:cave0_door0+0 hover:yes
 =48  =2885  go        cave0_door1+1 {key,crown} checkpoint:cave0_door0+0 hover:no
 =13  =2898  door      cave1_door0+0 {key,crown} checkpoint:cave1_door0+0 hover:no
 ≥17  ≥2915  die       cave1_door0+0 {key,crown} checkpoint:cave1_door0+0 hover:yes
  =8  ≥2923  go        cave1_item+1 {key,crown,gold} checkpoint:cave1_door0+0 hover:yes
 =25  ≥2948  go        cave1_rb+0 {key,crown,gold} checkpoint:cave1_door0+0 hover:yes
  =1  ≥2949  boundary  cave2_lb+0 {key,crown,gold} checkpoint:cave2_lb+0 hover:yes
 =63  ≥3012  go        cave2_item-1 {key,wand,crown,gold} checkpoint:cave2_lb+0 hover:no
 =34  ≥3046  die       cave2_lb+0 {key,wand,crown,gold} checkpoint:cave2_lb+0 hover:no
  =1  ≥3047  boundary  cave1_rb+0 {key,wand,crown,gold} checkpoint:cave1_rb+0 hover:no
 =14  ≥3061  go        cave1_door0+1 {key,wand,crown,gold} checkpoint:cave1_rb+0 hover:no
 =13  ≥3074  door      cave0_door1+0 {key,wand,crown,gold} checkpoint:cave0_door1+0 hover:no
 =27  ≥3101  go        cave0_door0+1 {key,wand,crown,gold} checkpoint:cave0_door1+0 hover:no
 =13  ≥3114  door      lake2_door0+0 {key,wand,crown,gold} checkpoint:lake2_door0+0 hover:no
 =63  ≥3177  go        lake2_door2-1 {key,wand,crown,gold} checkpoint:lake2_door0+0 hover:no
 =13  ≥3190  door      base1_door0+0 {key,wand,crown,gold} checkpoint:base1_door0+0 hover:no
=111  ≥3301  go        base1_door1-1 {key,wand,crown,gold} checkpoint:base1_door0+0 hover:no
 =13  ≥3314  door      base0_door1+0 {key,wand,crown,gold} checkpoint:base0_door1+0 hover:no
 =37  ≥3351  go        base0_door2-1 {key,wand,crown,gold} checkpoint:base0_door1+0 hover:no
 =13  ≥3364  door      space2_door0+0 {key,wand,crown,gold} checkpoint:space2_door0+0 hover:no
 =17  ≥3381  go        space2_item+1 {key,wand,gems,crown,gold} checkpoint:space2_door0+0 hover:no

The only way to die from the pit in CAVE1 is by taking damage from enemies, 7 hits total. The first problem is that there's an unavoidable Shield (full HP refill) right in front of the door we need to use. Picking up a Shield at less than full HP effectively prevents Comic from taking damage over the next 6 ticks. But at full HP, the Shield becomes an extra life, and then Comic can take damage on the very next tick. I found some inputs that just barely avoid the Blind Toads, collect the Shield at full HP, and take 1 damage before entering the door. It may be possible to take more damage before entering the door, but the other three enemies are by this point already off the high platform, so it would require chasing them down (while maintaining hover) and returning to the platform. That leaves 6 hits to take in the CAVE1 pit. I see two options here. The first option is to take 3 damage, exit and re-enter the door, then take another 3 damage. The second option is to enter with enemy_respawn_counter_cycle = 20, take 2 damage as quickly as possible, hit the other 2 enemies, then wait for the first 2 enemies to respawn. The advantage of the first option is not having to wait for the enemy_respawn_counter_cycle respawns, which will be at minimum 40 ticks for the 6th enemy to appear. The advantage of the second option is that it's a race to take 2 damage, not 3; and a roundtrip through a door itself costs 26 ticks. I ran rough numbers and the costs are close, so I'll just have to try both. Both options will involve spawning enemies in specific places. There are four enemies in CAVE1: a slow Blind Toad, a fast Blind Toad, and two slow Killer Bees. There is only room for one enemy to spawn at the bottom of the pit with Comic. The other three spawn at the top and have to move down. You can choose which enemy spawns in the pit by manipulating enemy_respawn_position_cycle before entering the stage. For the first option, I think it's best to have a Killer Bee spawn in the pit, so as not to have to wait for it to descend, then hit the two Blind Toads, which fall much faster than Killer Bees. For the second option, it's probably best to put the slow Blind Toad in the pit, and hit both it and the fast Blind Toad falling from the top, then let the Killer Bees approach while waiting for the Blind Toads to respawn. I tried writing a Lua script to optimize the first option, but I couldn't get it to run to completion. It would deadlock after an hour or so, even with the anti-deadlock patch (without which it would only go a few seconds). The total cost for the above route is ≥3381 ticks. When I had added in enough measured costs to increase the total cost above ≥3349, the optimizer started suggesting an alternate route, going into BASE to collect the Boots before entering CAVE. That's because as far as the optimizer knows, some state transitions may be faster with the Boots, so it falls back to the lower, inferred costs for those transitions; the addition of Boots to the inventory makes them different states. A few of the transitions are indeed faster, though not as fast as the lower-bound inferred costs; the main one is that getting from cave0_door0 up to cave0_door1 can be done by jumping rather than dying and hovering. But seeing as the cost difference between the two routes is only 32 ticks and can only decrease (unless Boots somehow make the CAVE1 death faster), I suspect the Boots route will be discarded once I measure enough transitions to convince the optimizer it's not worth it.

                       forest0_door0+1 {} checkpoint:forest0_door0+1 hover:yes
=240   =240  go        forest0_rb+0 {} checkpoint:forest0_door0+1 hover:no
  =1   =241  boundary  forest1_lb+0 {} checkpoint:forest1_lb+0 hover:no
=255   =496  go        forest1_rb+0 {} checkpoint:forest1_lb+0 hover:no
  =1   =497  boundary  forest2_lb+0 {} checkpoint:forest2_lb+0 hover:no
=159   =656  go        forest2_item-1 {key} checkpoint:forest2_lb+0 hover:no
 =33   =689  die       forest2_lb+0 {key} checkpoint:forest2_lb+0 hover:yes
  =1   =690  boundary  forest1_rb+0 {key} checkpoint:forest1_rb+0 hover:yes
=254   =944  go        forest1_lb+0 {key} checkpoint:forest1_rb+0 hover:no
  =1   =945  boundary  forest0_rb+0 {key} checkpoint:forest0_rb+0 hover:no
=240  =1185  go        forest0_door0+1 {key} checkpoint:forest0_rb+0 hover:no
 =13  =1198  door      castle0_door0+0 {key} checkpoint:castle0_door0+0 hover:no
 =52  =1250  die       castle0_door0+0 {key} checkpoint:castle0_door0+0 hover:yes
 =48  =1298  go        castle0_item-1 {key,crown} checkpoint:castle0_door0+0 hover:no
 =83  =1381  die       castle0_door0+0 {key,crown} checkpoint:castle0_door0+0 hover:no
 =13  =1394  door      forest0_door0+0 {key,crown} checkpoint:forest0_door0+0 hover:no
=241  =1635  go        forest0_rb+0 {key,crown} checkpoint:forest0_door0+0 hover:no
  =1  =1636  boundary  forest1_lb+0 {key,crown} checkpoint:forest1_lb+0 hover:no
=255  =1891  go        forest1_rb+0 {key,crown} checkpoint:forest1_lb+0 hover:no
  =1  =1892  boundary  forest2_lb+0 {key,crown} checkpoint:forest2_lb+0 hover:no
=238  =2130  go        forest2_door0-1 {key,crown} checkpoint:forest2_lb+0 hover:no
 =13  =2143  door      lake0_door0+0 {key,crown} checkpoint:lake0_door0+0 hover:no
=119  =2262  go        lake0_lb+0 {key,crown} checkpoint:lake0_door0+0 hover:no
  =1  =2263  boundary  lake1_rb+0 {key,crown} checkpoint:lake1_rb+0 hover:no
=254  =2517  go        lake1_lb+0 {key,crown} checkpoint:lake1_rb+0 hover:no
  =1  =2518  boundary  lake2_rb+0 {key,crown} checkpoint:lake2_rb+0 hover:no
  =1  =2519  boundary  lake1_lb+0 {key,crown} checkpoint:lake1_lb+0 hover:no
 =26  =2545  die       lake1_lb+0 {key,crown} checkpoint:lake1_lb+0 hover:yes
  =1  =2546  boundary  lake2_rb+0 {key,crown} checkpoint:lake2_rb+0 hover:yes
≥178  ≥2724  go        lake2_door2+1 {key,crown} checkpoint:lake2_rb+0 hover:no
 ≥13  ≥2737  door      base1_door0+0 {key,crown} checkpoint:base1_door0+0 hover:no
  ≥0  ≥2737  go        base1_door2+0 {key,crown} checkpoint:base1_door0+0 hover:no
 ≥13  ≥2750  door      base2_door1+0 {key,crown} checkpoint:base2_door1+0 hover:no
 ≥10  ≥2760  go        base2_item-1 {key,boots,crown} checkpoint:base2_door1+0 hover:no
  ≥9  ≥2769  go        base2_door1+1 {key,boots,crown} checkpoint:base2_door1+0 hover:no
 ≥13  ≥2782  door      base1_door2+0 {key,boots,crown} checkpoint:base1_door2+0 hover:no
  ≥0  ≥2782  go        base1_door0+0 {key,boots,crown} checkpoint:base1_door2+0 hover:no
 ≥13  ≥2795  door      lake2_door2+0 {key,boots,crown} checkpoint:lake2_door2+0 hover:no
 ≥63  ≥2858  go        lake2_door0+1 {key,boots,crown} checkpoint:lake2_door2+0 hover:no
 ≥13  ≥2871  door      cave0_door0+0 {key,boots,crown} checkpoint:cave0_door0+0 hover:no
 ≥31  ≥2902  go        cave0_door1-1 {key,boots,crown} checkpoint:cave0_door0+0 hover:no
 ≥13  ≥2915  door      cave1_door0+0 {key,boots,crown} checkpoint:cave1_door0+0 hover:no
 ≥17  ≥2932  die       cave1_door0+0 {key,boots,crown} checkpoint:cave1_door0+0 hover:yes
 ≥17  ≥2949  go        cave1_rb+0 {key,boots,crown} checkpoint:cave1_door0+0 hover:no
  ≥1  ≥2950  boundary  cave2_lb+0 {key,boots,crown} checkpoint:cave2_lb+0 hover:no
 ≥63  ≥3013  go        cave2_item-1 {key,boots,wand,crown} checkpoint:cave2_lb+0 hover:no
 ≥17  ≥3030  die       cave2_lb+0 {key,boots,wand,crown} checkpoint:cave2_lb+0 hover:no
  ≥1  ≥3031  boundary  cave1_rb+0 {key,boots,wand,crown} checkpoint:cave1_rb+0 hover:no
 ≥22  ≥3053  go        cave1_item+1 {key,boots,wand,crown,gold} checkpoint:cave1_rb+0 hover:no
  ≥7  ≥3060  go        cave1_door0-1 {key,boots,wand,crown,gold} checkpoint:cave1_rb+0 hover:no
 ≥13  ≥3073  door      cave0_door1+0 {key,boots,wand,crown,gold} checkpoint:cave0_door1+0 hover:no
 ≥27  ≥3100  go        cave0_door0+1 {key,boots,wand,crown,gold} checkpoint:cave0_door1+0 hover:no
 ≥13  ≥3113  door      lake2_door0+0 {key,boots,wand,crown,gold} checkpoint:lake2_door0+0 hover:no
 ≥63  ≥3176  go        lake2_door2-1 {key,boots,wand,crown,gold} checkpoint:lake2_door0+0 hover:no
 ≥13  ≥3189  door      base1_door0+0 {key,boots,wand,crown,gold} checkpoint:base1_door0+0 hover:no
≥111  ≥3300  go        base1_door1-1 {key,boots,wand,crown,gold} checkpoint:base1_door0+0 hover:no
 ≥13  ≥3313  door      base0_door1+0 {key,boots,wand,crown,gold} checkpoint:base0_door1+0 hover:no
 ≥23  ≥3336  go        base0_door2-1 {key,boots,wand,crown,gold} checkpoint:base0_door1+0 hover:no
 ≥13  ≥3349  door      space2_door0+0 {key,boots,wand,crown,gold} checkpoint:space2_door0+0 hover:no
  ≥0  ≥3349  go        space2_item-1 {key,boots,wand,gems,crown,gold} checkpoint:space2_door0+0 hover:no

Posted: 11/2/2020 4:28 PM

Post subject: Route finished

Quote

Sand

He/Him

Player (125)

Joined: 6/26/2018
Posts: 154

2020-10-31 (4.25 h) Testing different ways to do the CAVE1 death. Auditing the logic graph. 2020-11-02 (4.25 h) More experimentation with the CAVE1 death. Measuring costs for the Boots route.

Sand wrote:

The only way to die from the pit in CAVE1 is by taking damage from enemies, 7 hits total. The first problem is that there's an unavoidable Shield (full HP refill) right in front of the door we need to use. Picking up a Shield at less than full HP effectively prevents Comic from taking damage over the next 6 ticks. But at full HP, the Shield becomes an extra life, and then Comic can take damage on the very next tick. I found some inputs that just barely avoid the Blind Toads, collect the Shield at full HP, and take 1 damage before entering the door. It may be possible to take more damage before entering the door, but the other three enemies are by this point already off the high platform, so it would require chasing them down (while maintaining hover) and returning to the platform. That leaves 6 hits to take in the CAVE1 pit. I see two options here. The first option is to take 3 damage, exit and re-enter the door, then take another 3 damage. The second option is to enter with enemy_respawn_counter_cycle = 20, take 2 damage as quickly as possible, hit the other 2 enemies, then wait for the first 2 enemies to respawn. The advantage of the first option is not having to wait for the enemy_respawn_counter_cycle respawns, which will be at minimum 40 ticks for the 6th enemy to appear. The advantage of the second option is that it's a race to take 2 damage, not 3; and a roundtrip through a door itself costs 26 ticks. I ran rough numbers and the costs are close, so I'll just have to try both.

In my tests, the second option—letting enemies respawn in CAVE1 and not re-entering the door—is 10 ticks faster, 127 versus 137. But still faster is spending 10 ticks to take an additional point of damage before entering the door, which requires a total of only 108 ticks. A couple of other minor optimizations that I initially overlooked can save another 4 ticks. This is how the early part of CAVE looks now. It's a lot better than my first attempt, but this section is still the trickiest to optimize and the one I'm least confident in. I'll get another chance to consider it as I execute the final route.

Speaking of which, the route is done. The magic output ‘*** FINISHED! ***’ appears at 4:14:36 in the second video linked above. Like I said in the last post, after measuring the costs for the initially proposed route, the optimizer began suggesting a route that gets the Boots from BASE before entering CAVE, on the hope that the Boots would speed up some of the later state transitions. As it turns out, the Boots do not save time. I didn't have to measure every state transition in the Boots route, only enough to convince the optimizer that it was not worth pursuing further. It required increasing a few costs that are not actually as low as their inferred lower bound. In CAVE1, I did not spend the time to optimize the death precisely, but it was enough to tighten the lower bound from ≥17 to ≥53. The latter bound represents the time it would take to die if Comic were to enter CAVE1 with 0 HP. Here is the Boots route at the point that the optimizer stopped suggesting it. It's at least 6 ticks (0.66 s) slower than the non-Boots route.

                       forest0_door0+1 {} checkpoint:forest0_door0+1 hover:yes
=240   =240  go        forest0_rb+0 {} checkpoint:forest0_door0+1 hover:no
  =1   =241  boundary  forest1_lb+0 {} checkpoint:forest1_lb+0 hover:no
=255   =496  go        forest1_rb+0 {} checkpoint:forest1_lb+0 hover:no
  =1   =497  boundary  forest2_lb+0 {} checkpoint:forest2_lb+0 hover:no
=159   =656  go        forest2_item-1 {key} checkpoint:forest2_lb+0 hover:no
 =33   =689  die       forest2_lb+0 {key} checkpoint:forest2_lb+0 hover:yes
  =1   =690  boundary  forest1_rb+0 {key} checkpoint:forest1_rb+0 hover:yes
=254   =944  go        forest1_lb+0 {key} checkpoint:forest1_rb+0 hover:no
  =1   =945  boundary  forest0_rb+0 {key} checkpoint:forest0_rb+0 hover:no
=240  =1185  go        forest0_door0+1 {key} checkpoint:forest0_rb+0 hover:no
 =13  =1198  door      castle0_door0+0 {key} checkpoint:castle0_door0+0 hover:no
 =52  =1250  die       castle0_door0+0 {key} checkpoint:castle0_door0+0 hover:yes
 =48  =1298  go        castle0_item-1 {key,crown} checkpoint:castle0_door0+0 hover:no
 =83  =1381  die       castle0_door0+0 {key,crown} checkpoint:castle0_door0+0 hover:no
 =13  =1394  door      forest0_door0+0 {key,crown} checkpoint:forest0_door0+0 hover:no
=241  =1635  go        forest0_rb+0 {key,crown} checkpoint:forest0_door0+0 hover:no
  =1  =1636  boundary  forest1_lb+0 {key,crown} checkpoint:forest1_lb+0 hover:no
=255  =1891  go        forest1_rb+0 {key,crown} checkpoint:forest1_lb+0 hover:no
  =1  =1892  boundary  forest2_lb+0 {key,crown} checkpoint:forest2_lb+0 hover:no
=238  =2130  go        forest2_door0-1 {key,crown} checkpoint:forest2_lb+0 hover:no
 =13  =2143  door      lake0_door0+0 {key,crown} checkpoint:lake0_door0+0 hover:no
=119  =2262  go        lake0_lb+0 {key,crown} checkpoint:lake0_door0+0 hover:no
  =1  =2263  boundary  lake1_rb+0 {key,crown} checkpoint:lake1_rb+0 hover:no
=254  =2517  go        lake1_lb+0 {key,crown} checkpoint:lake1_rb+0 hover:no
  =1  =2518  boundary  lake2_rb+0 {key,crown} checkpoint:lake2_rb+0 hover:no
  =1  =2519  boundary  lake1_lb+0 {key,crown} checkpoint:lake1_lb+0 hover:no
 =26  =2545  die       lake1_lb+0 {key,crown} checkpoint:lake1_lb+0 hover:yes
  =1  =2546  boundary  lake2_rb+0 {key,crown} checkpoint:lake2_rb+0 hover:yes
=178  =2724  go        lake2_door2+1 {key,crown} checkpoint:lake2_rb+0 hover:no
 =13  =2737  door      base1_door0+0 {key,crown} checkpoint:base1_door0+0 hover:no
 =28  =2765  go        base1_door2+1 {key,crown} checkpoint:base1_door0+0 hover:no
 =13  =2778  door      base2_door1+0 {key,crown} checkpoint:base2_door1+0 hover:no
 =10  =2788  go        base2_item-1 {key,boots,crown} checkpoint:base2_door1+0 hover:no
  =9  =2797  go        base2_door1+1 {key,boots,crown} checkpoint:base2_door1+0 hover:no
 =13  =2810  door      base1_door2+0 {key,boots,crown} checkpoint:base1_door2+0 hover:no
 =27  =2837  go        base1_door0+1 {key,boots,crown} checkpoint:base1_door2+0 hover:no
 =13  =2850  door      lake2_door2+0 {key,boots,crown} checkpoint:lake2_door2+0 hover:no
 =63  =2913  go        lake2_door0+1 {key,boots,crown} checkpoint:lake2_door2+0 hover:no
 =13  =2926  door      cave0_door0+0 {key,boots,crown} checkpoint:cave0_door0+0 hover:no
 =48  =2974  go        cave0_door1+1 {key,boots,crown} checkpoint:cave0_door0+0 hover:no
 =13  =2987  door      cave1_door0+0 {key,boots,crown} checkpoint:cave1_door0+0 hover:no
 ≥53  ≥3040  die       cave1_door0+0 {key,boots,crown} checkpoint:cave1_door0+0 hover:yes
 =17  ≥3057  go        cave1_rb+0 {key,boots,crown} checkpoint:cave1_door0+0 hover:no
  =1  ≥3058  boundary  cave2_lb+0 {key,boots,crown} checkpoint:cave2_lb+0 hover:no
 =63  ≥3121  go        cave2_item-1 {key,boots,wand,crown} checkpoint:cave2_lb+0 hover:no
 =34  ≥3155  die       cave2_lb+0 {key,boots,wand,crown} checkpoint:cave2_lb+0 hover:no
  ≥1  ≥3156  boundary  cave1_rb+0 {key,boots,wand,crown} checkpoint:cave1_rb+0 hover:no
 ≥22  ≥3178  go        cave1_item+1 {key,boots,wand,crown,gold} checkpoint:cave1_rb+0 hover:no
  ≥7  ≥3185  go        cave1_door0-1 {key,boots,wand,crown,gold} checkpoint:cave1_rb+0 hover:no
 ≥13  ≥3198  door      cave0_door1+0 {key,boots,wand,crown,gold} checkpoint:cave0_door1+0 hover:no
 ≥27  ≥3225  go        cave0_door0+1 {key,boots,wand,crown,gold} checkpoint:cave0_door1+0 hover:no
 ≥13  ≥3238  door      lake2_door0+0 {key,boots,wand,crown,gold} checkpoint:lake2_door0+0 hover:no
 ≥63  ≥3301  go        lake2_door2-1 {key,boots,wand,crown,gold} checkpoint:lake2_door0+0 hover:no
 ≥13  ≥3314  door      base1_door0+0 {key,boots,wand,crown,gold} checkpoint:base1_door0+0 hover:no
≥111  ≥3425  go        base1_door1-1 {key,boots,wand,crown,gold} checkpoint:base1_door0+0 hover:no
 ≥13  ≥3438  door      base0_door1+0 {key,boots,wand,crown,gold} checkpoint:base0_door1+0 hover:no
 ≥23  ≥3461  go        base0_door2-1 {key,boots,wand,crown,gold} checkpoint:base0_door1+0 hover:no
 ≥13  ≥3474  door      space2_door0+0 {key,boots,wand,crown,gold} checkpoint:space2_door0+0 hover:no
  ≥0  ≥3474  go        space2_item-1 {key,boots,wand,gems,crown,gold} checkpoint:space2_door0+0 hover:no

Here is the route the optimizer settled on. Now it remains to execute this route from the beginning. If I have not made a mistake, then the second column gives precise timing for the TAS that will result; that is, the tick counter in the HUD script should exactly match the value in the second column at the end of each state transition, and the total gameplay time (not counting booting the computer and the game's title sequence) will be 3468 / (1193182 / 65536 / 2) = 380.96 s (6:20.96), about one minute faster than my RTA run using a different route.

                       forest0_door0+1 {} checkpoint:forest0_door0+1 hover:yes
=240   =240  go        forest0_rb+0 {} checkpoint:forest0_door0+1 hover:no
  =1   =241  boundary  forest1_lb+0 {} checkpoint:forest1_lb+0 hover:no
=255   =496  go        forest1_rb+0 {} checkpoint:forest1_lb+0 hover:no
  =1   =497  boundary  forest2_lb+0 {} checkpoint:forest2_lb+0 hover:no
=159   =656  go        forest2_item-1 {key} checkpoint:forest2_lb+0 hover:no
 =33   =689  die       forest2_lb+0 {key} checkpoint:forest2_lb+0 hover:yes
  =1   =690  boundary  forest1_rb+0 {key} checkpoint:forest1_rb+0 hover:yes
=254   =944  go        forest1_lb+0 {key} checkpoint:forest1_rb+0 hover:no
  =1   =945  boundary  forest0_rb+0 {key} checkpoint:forest0_rb+0 hover:no
=240  =1185  go        forest0_door0+1 {key} checkpoint:forest0_rb+0 hover:no
 =13  =1198  door      castle0_door0+0 {key} checkpoint:castle0_door0+0 hover:no
 =52  =1250  die       castle0_door0+0 {key} checkpoint:castle0_door0+0 hover:yes
 =48  =1298  go        castle0_item-1 {key,crown} checkpoint:castle0_door0+0 hover:no
 =83  =1381  die       castle0_door0+0 {key,crown} checkpoint:castle0_door0+0 hover:no
 =13  =1394  door      forest0_door0+0 {key,crown} checkpoint:forest0_door0+0 hover:no
=241  =1635  go        forest0_rb+0 {key,crown} checkpoint:forest0_door0+0 hover:no
  =1  =1636  boundary  forest1_lb+0 {key,crown} checkpoint:forest1_lb+0 hover:no
=255  =1891  go        forest1_rb+0 {key,crown} checkpoint:forest1_lb+0 hover:no
  =1  =1892  boundary  forest2_lb+0 {key,crown} checkpoint:forest2_lb+0 hover:no
=238  =2130  go        forest2_door0-1 {key,crown} checkpoint:forest2_lb+0 hover:no
 =13  =2143  door      lake0_door0+0 {key,crown} checkpoint:lake0_door0+0 hover:no
=119  =2262  go        lake0_lb+0 {key,crown} checkpoint:lake0_door0+0 hover:no
  =1  =2263  boundary  lake1_rb+0 {key,crown} checkpoint:lake1_rb+0 hover:no
=254  =2517  go        lake1_lb+0 {key,crown} checkpoint:lake1_rb+0 hover:no
  =1  =2518  boundary  lake2_rb+0 {key,crown} checkpoint:lake2_rb+0 hover:no
  =1  =2519  boundary  lake1_lb+0 {key,crown} checkpoint:lake1_lb+0 hover:no
 =26  =2545  die       lake1_lb+0 {key,crown} checkpoint:lake1_lb+0 hover:yes
  =1  =2546  boundary  lake2_rb+0 {key,crown} checkpoint:lake2_rb+0 hover:yes
=242  =2788  go        lake2_door0+1 {key,crown} checkpoint:lake2_rb+0 hover:yes
 =13  =2801  door      cave0_door0+0 {key,crown} checkpoint:cave0_door0+0 hover:no
 =36  =2837  die       cave0_door0+0 {key,crown} checkpoint:cave0_door0+0 hover:yes
 =48  =2885  go        cave0_door1+1 {key,crown} checkpoint:cave0_door0+0 hover:no
 =13  =2898  door      cave1_door0+0 {key,crown} checkpoint:cave1_door0+0 hover:no
=104  =3002  die       cave1_door0+0 {key,crown} checkpoint:cave1_door0+0 hover:yes
  =8  =3010  go        cave1_item+1 {key,crown,gold} checkpoint:cave1_door0+0 hover:yes
 =25  =3035  go        cave1_rb+0 {key,crown,gold} checkpoint:cave1_door0+0 hover:yes
  =1  =3036  boundary  cave2_lb+0 {key,crown,gold} checkpoint:cave2_lb+0 hover:yes
 =63  =3099  go        cave2_item-1 {key,wand,crown,gold} checkpoint:cave2_lb+0 hover:no
 =34  =3133  die       cave2_lb+0 {key,wand,crown,gold} checkpoint:cave2_lb+0 hover:no
  =1  =3134  boundary  cave1_rb+0 {key,wand,crown,gold} checkpoint:cave1_rb+0 hover:no
 =14  =3148  go        cave1_door0+1 {key,wand,crown,gold} checkpoint:cave1_rb+0 hover:no
 =13  =3161  door      cave0_door1+0 {key,wand,crown,gold} checkpoint:cave0_door1+0 hover:no
 =27  =3188  go        cave0_door0+1 {key,wand,crown,gold} checkpoint:cave0_door1+0 hover:no
 =13  =3201  door      lake2_door0+0 {key,wand,crown,gold} checkpoint:lake2_door0+0 hover:no
 =63  =3264  go        lake2_door2-1 {key,wand,crown,gold} checkpoint:lake2_door0+0 hover:no
 =13  =3277  door      base1_door0+0 {key,wand,crown,gold} checkpoint:base1_door0+0 hover:no
=111  =3388  go        base1_door1-1 {key,wand,crown,gold} checkpoint:base1_door0+0 hover:no
 =13  =3401  door      base0_door1+0 {key,wand,crown,gold} checkpoint:base0_door1+0 hover:no
 =37  =3438  go        base0_door2-1 {key,wand,crown,gold} checkpoint:base0_door1+0 hover:no
 =13  =3451  door      space2_door0+0 {key,wand,crown,gold} checkpoint:space2_door0+0 hover:no
 =17  =3468  go        space2_item+1 {key,wand,gems,crown,gold} checkpoint:space2_door0+0 hover:no
*** FINISHED! ***

Posted: 11/3/2020 11:01 PM

Quote

Kabuto

Player (103)

Joined: 5/22/2007
Posts: 22

Wow, you found some really cool strategies such as the shield trick / dodging 2 enemies. I’m looking forward to seeing the full TAS!

Posted: 11/15/2020 6:50 PM
(Edited: 1/4/2022 6:08 PM)

Post subject: Finished implementing the route

Quote

Sand

He/Him

Player (125)

Joined: 6/26/2018
Posts: 154

2020-11-05 (4.5 h) TASing from the start up to CASTLE. 2020-11-11 (3.0 h) TASing between CASTLE and CAVE. 2020-11-14 (3.5 h) TASing from CAVE to the end. Video encoding. I have finished implementing the route. Here is an encode. The total time is 6:33.075, by my reckoning. Link to video Kabuto, I've started drafting a submission at https://pad.riseup.net/p/u2s2Ko2T7_xD3aBW_N8w. Feel free to edit it. I still have a few graphics I want to make for the submission. Unfortunately, I'm still having a problem I've had since at least April of this year, where I can log in to the forums but not the main site (submission system, wiki, etc.). I'll need to get that sorted out before I can make a submission.

Sand wrote:

Here is the route the optimizer settled on. Now it remains to execute this route from the beginning. If I have not made a mistake, then the second column gives precise timing for the TAS that will result; that is, the tick counter in the HUD script should exactly match the value in the second column at the end of each state transition, and the total gameplay time (not counting booting the computer and the game's title sequence) will be 3468 / (1193182 / 65536 / 2) = 380.96 s (6:20.96), about one minute faster than my RTA run using a different route.

As it turns out, there were a couple of small errors in the table of measured costs, one that lost 1 tick and one that saved 6 ticks. The total time for the route is now 3463 ticks = 380.41 s (6:20.41). The first error was a small dependency between adjacent state transitions, of the kind I talked about in Post #500452. After taking the door from cave0_door0 to lake2_door0, you need to move right. You can do the preceding cave0_door1→cave0_door0 transition in 27 ticks, but you end up facing left, not right—you have to spend 1 additional tick to face right before going through the door. Alternatively, you can go through the door facing left, then spend 1 tick to face right at the beginning of the lake2_door0→lake2_door2 transition. But you must spend the 1 tick in one transition or the other. The second error was that I found a way to end input earlier, using only 11 ticks for the final transition space2_door0→space2_item instead of 17 ticks. The key is that you can buffer a jump input coming out of a teleport. Start a teleport, calculated to end at the point where you need to jump. On the next tick, release the teleport key and press the jump key. Then no further input is needed. The jump input will take effect as soon as the teleport ends. With those corrections, this is the route used in the encode:

                       forest0_door0+1 {} checkpoint:forest0_door0+1 hover:yes
=240   =240  go        forest0_rb+0 {} checkpoint:forest0_door0+1 hover:no
  =1   =241  boundary  forest1_lb+0 {} checkpoint:forest1_lb+0 hover:no
=255   =496  go        forest1_rb+0 {} checkpoint:forest1_lb+0 hover:no
  =1   =497  boundary  forest2_lb+0 {} checkpoint:forest2_lb+0 hover:no
=159   =656  go        forest2_item-1 {key} checkpoint:forest2_lb+0 hover:no
 =33   =689  die       forest2_lb+0 {key} checkpoint:forest2_lb+0 hover:yes
  =1   =690  boundary  forest1_rb+0 {key} checkpoint:forest1_rb+0 hover:yes
=254   =944  go        forest1_lb+0 {key} checkpoint:forest1_rb+0 hover:no
  =1   =945  boundary  forest0_rb+0 {key} checkpoint:forest0_rb+0 hover:no
=240  =1185  go        forest0_door0+1 {key} checkpoint:forest0_rb+0 hover:no
 =13  =1198  door      castle0_door0+0 {key} checkpoint:castle0_door0+0 hover:no
 =52  =1250  die       castle0_door0+0 {key} checkpoint:castle0_door0+0 hover:yes
 =48  =1298  go        castle0_item-1 {key,crown} checkpoint:castle0_door0+0 hover:no
 =83  =1381  die       castle0_door0+0 {key,crown} checkpoint:castle0_door0+0 hover:no
 =13  =1394  door      forest0_door0+0 {key,crown} checkpoint:forest0_door0+0 hover:no
=241  =1635  go        forest0_rb+0 {key,crown} checkpoint:forest0_door0+0 hover:no
  =1  =1636  boundary  forest1_lb+0 {key,crown} checkpoint:forest1_lb+0 hover:no
=255  =1891  go        forest1_rb+0 {key,crown} checkpoint:forest1_lb+0 hover:no
  =1  =1892  boundary  forest2_lb+0 {key,crown} checkpoint:forest2_lb+0 hover:no
=238  =2130  go        forest2_door0-1 {key,crown} checkpoint:forest2_lb+0 hover:no
 =13  =2143  door      lake0_door0+0 {key,crown} checkpoint:lake0_door0+0 hover:no
=119  =2262  go        lake0_lb+0 {key,crown} checkpoint:lake0_door0+0 hover:no
  =1  =2263  boundary  lake1_rb+0 {key,crown} checkpoint:lake1_rb+0 hover:no
=254  =2517  go        lake1_lb+0 {key,crown} checkpoint:lake1_rb+0 hover:no
  =1  =2518  boundary  lake2_rb+0 {key,crown} checkpoint:lake2_rb+0 hover:no
  =1  =2519  boundary  lake1_lb+0 {key,crown} checkpoint:lake1_lb+0 hover:no
 =26  =2545  die       lake1_lb+0 {key,crown} checkpoint:lake1_lb+0 hover:yes
  =1  =2546  boundary  lake2_rb+0 {key,crown} checkpoint:lake2_rb+0 hover:yes
=242  =2788  go        lake2_door0+1 {key,crown} checkpoint:lake2_rb+0 hover:yes
 =13  =2801  door      cave0_door0+0 {key,crown} checkpoint:cave0_door0+0 hover:no
 =36  =2837  die       cave0_door0+0 {key,crown} checkpoint:cave0_door0+0 hover:yes
 =48  =2885  go        cave0_door1+1 {key,crown} checkpoint:cave0_door0+0 hover:no
 =13  =2898  door      cave1_door0+0 {key,crown} checkpoint:cave1_door0+0 hover:no
=104  =3002  die       cave1_door0+0 {key,crown} checkpoint:cave1_door0+0 hover:yes
  =8  =3010  go        cave1_item+1 {key,crown,gold} checkpoint:cave1_door0+0 hover:yes
 =25  =3035  go        cave1_rb+0 {key,crown,gold} checkpoint:cave1_door0+0 hover:yes
  =1  =3036  boundary  cave2_lb+0 {key,crown,gold} checkpoint:cave2_lb+0 hover:yes
 =63  =3099  go        cave2_item-1 {key,wand,crown,gold} checkpoint:cave2_lb+0 hover:no
 =34  =3133  die       cave2_lb+0 {key,wand,crown,gold} checkpoint:cave2_lb+0 hover:no
  =1  =3134  boundary  cave1_rb+0 {key,wand,crown,gold} checkpoint:cave1_rb+0 hover:no
 =14  =3148  go        cave1_door0+1 {key,wand,crown,gold} checkpoint:cave1_rb+0 hover:no
 =13  =3161  door      cave0_door1+0 {key,wand,crown,gold} checkpoint:cave0_door1+0 hover:no
 =28  =3189  go        cave0_door0+1 {key,wand,crown,gold} checkpoint:cave0_door1+0 hover:no
 =13  =3202  door      lake2_door0+0 {key,wand,crown,gold} checkpoint:lake2_door0+0 hover:no
 =63  =3265  go        lake2_door2-1 {key,wand,crown,gold} checkpoint:lake2_door0+0 hover:no
 =13  =3278  door      base1_door0+0 {key,wand,crown,gold} checkpoint:base1_door0+0 hover:no
=111  =3389  go        base1_door1-1 {key,wand,crown,gold} checkpoint:base1_door0+0 hover:no
 =13  =3402  door      base0_door1+0 {key,wand,crown,gold} checkpoint:base0_door1+0 hover:no
 =37  =3439  go        base0_door2-1 {key,wand,crown,gold} checkpoint:base0_door1+0 hover:no
 =13  =3452  door      space2_door0+0 {key,wand,crown,gold} checkpoint:space2_door0+0 hover:no
 =11  =3463  go        space2_item-1 {key,wand,gems,crown,gold} checkpoint:space2_door0+0 hover:no
*** FINISHED! ***

Posted: 11/16/2020 12:58 PM

Post subject: Re: Finished implementing the route

Quote

Radiant

Player (26)

Joined: 8/29/2011
Posts: 1206
Location: Amsterdam

Awesome work, well done! I suppose you could ask a judge if somebody else could make the submission for you; it would be straightforward to put the text in a PM and have somebody else copy/paste it into the submission framework. I'm happy to do that for you if you want, but best check a mod first.

Indie game developer

Posted: 11/16/2020 1:01 PM

Quote

Kabuto

Player (103)

Joined: 5/22/2007
Posts: 22

Well written and exhaustive submission text! I added and changed a few things, feel free to keep or change them as you like :) The run itself looks perfect to me, I don't see any room for improvement. Probably too late - another glitch that's probably only useful for some extra fun: when hovering, if you're hovering against the top of the level and hold jump for too long, the vertical velocity underflows at some point, sending Comic down to near the bottom of the screen and if you keep on holding space Comic will fall to his death. But - if you let go of space, vertical velocity will overflow again, sending Comic back up - or, if his head touched an obstacle, he'll lose vertical momentum and stay at that vertical position. (EDIT: I don't think that it'll be possible to use this for exiting the crown room again...)

Posted: 11/16/2020 10:01 PM

Post subject: Faster deathwarp in CASTLE0

Quote

Sand

He/Him

Player (125)

Joined: 6/26/2018
Posts: 154

Kabuto wrote:

(EDIT: I don't think that it'll be possible to use this for exiting the crown room again...)

This was a great idea! I knew about the vertical velocity underflow thing, but I never considered applying it here. Using the underflow to warp to the bottom of the screen is 19 ticks (over 2 seconds) faster than taking enemy damage. I'll work this into the run.

I tried releasing the jump key to land in the lower level (without dying) after the underflow, but it didn't work. Still, dying this way is faster. A side benefit is that this way does not depend on a specific value of enemy_respawn_position_cycle, which means less spawn manipulation is necessary. Thanks for the correction about the Lantern. For some reason, I had it in my mind that the early-Lantern map layout was only in Revision 2, but I checked and you're right, it's only in Revision 1. In either case, it would be possible to hover up to the Lantern.

Posted: 11/17/2020 9:41 AM

Quote

Kabuto

Player (103)

Joined: 5/22/2007
Posts: 22

Good find, I totally overlooked the possibility of using the underflow trick for death warping back to the door. IIRC you can only kind of "land" - or rather: bang your head and lose vertical velocity - if you release the jump button after falling AND there's a block right above Comic's head, i.e. in the third bottommost row of tiles.

Posted: 11/20/2020 12:00 AM
(Edited: 1/4/2022 6:19 PM)

Post subject: Encode with faster deathwarp in CASTLE0

Quote

Sand

He/Him

Player (125)

Joined: 6/26/2018
Posts: 154

2020-11-18 (8.25 h) Integrating the velocity underflow deathwarp, cleaning up some movement, starting a program to visualize routes. Here is an encode featuring the faster castle deathwarp. The time is 6:30.977, 2.097 s faster than before. I took the opportunity also to make some minor movement cleanups. Link to video Here is the latest route. The only change is that the castle0_item→castle0_door0 transition now costs 64 ticks instead of 83.

                       forest0_door0+1 {} checkpoint:forest0_door0+1 hover:yes
=240   =240  go        forest0_rb+0 {} checkpoint:forest0_door0+1 hover:no
  =1   =241  boundary  forest1_lb+0 {} checkpoint:forest1_lb+0 hover:no
=255   =496  go        forest1_rb+0 {} checkpoint:forest1_lb+0 hover:no
  =1   =497  boundary  forest2_lb+0 {} checkpoint:forest2_lb+0 hover:no
=159   =656  go        forest2_item-1 {key} checkpoint:forest2_lb+0 hover:no
 =33   =689  die       forest2_lb+0 {key} checkpoint:forest2_lb+0 hover:yes
  =1   =690  boundary  forest1_rb+0 {key} checkpoint:forest1_rb+0 hover:yes
=254   =944  go        forest1_lb+0 {key} checkpoint:forest1_rb+0 hover:no
  =1   =945  boundary  forest0_rb+0 {key} checkpoint:forest0_rb+0 hover:no
=240  =1185  go        forest0_door0+1 {key} checkpoint:forest0_rb+0 hover:no
 =13  =1198  door      castle0_door0+0 {key} checkpoint:castle0_door0+0 hover:no
 =52  =1250  die       castle0_door0+0 {key} checkpoint:castle0_door0+0 hover:yes
 =48  =1298  go        castle0_item-1 {key,crown} checkpoint:castle0_door0+0 hover:yes
 =64  =1362  die       castle0_door0+0 {key,crown} checkpoint:castle0_door0+0 hover:no
 =13  =1375  door      forest0_door0+0 {key,crown} checkpoint:forest0_door0+0 hover:no
=241  =1616  go        forest0_rb+0 {key,crown} checkpoint:forest0_door0+0 hover:no
  =1  =1617  boundary  forest1_lb+0 {key,crown} checkpoint:forest1_lb+0 hover:no
=255  =1872  go        forest1_rb+0 {key,crown} checkpoint:forest1_lb+0 hover:no
  =1  =1873  boundary  forest2_lb+0 {key,crown} checkpoint:forest2_lb+0 hover:no
=238  =2111  go        forest2_door0-1 {key,crown} checkpoint:forest2_lb+0 hover:no
 =13  =2124  door      lake0_door0+0 {key,crown} checkpoint:lake0_door0+0 hover:no
=119  =2243  go        lake0_lb+0 {key,crown} checkpoint:lake0_door0+0 hover:no
  =1  =2244  boundary  lake1_rb+0 {key,crown} checkpoint:lake1_rb+0 hover:no
=254  =2498  go        lake1_lb+0 {key,crown} checkpoint:lake1_rb+0 hover:no
  =1  =2499  boundary  lake2_rb+0 {key,crown} checkpoint:lake2_rb+0 hover:no
  =1  =2500  boundary  lake1_lb+0 {key,crown} checkpoint:lake1_lb+0 hover:no
 =26  =2526  die       lake1_lb+0 {key,crown} checkpoint:lake1_lb+0 hover:yes
  =1  =2527  boundary  lake2_rb+0 {key,crown} checkpoint:lake2_rb+0 hover:yes
=242  =2769  go        lake2_door0+1 {key,crown} checkpoint:lake2_rb+0 hover:yes
 =13  =2782  door      cave0_door0+0 {key,crown} checkpoint:cave0_door0+0 hover:no
 =36  =2818  die       cave0_door0+0 {key,crown} checkpoint:cave0_door0+0 hover:yes
 =48  =2866  go        cave0_door1+1 {key,crown} checkpoint:cave0_door0+0 hover:no
 =13  =2879  door      cave1_door0+0 {key,crown} checkpoint:cave1_door0+0 hover:no
=104  =2983  die       cave1_door0+0 {key,crown} checkpoint:cave1_door0+0 hover:yes
  =8  =2991  go        cave1_item+1 {key,crown,gold} checkpoint:cave1_door0+0 hover:yes
 =25  =3016  go        cave1_rb+0 {key,crown,gold} checkpoint:cave1_door0+0 hover:yes
  =1  =3017  boundary  cave2_lb+0 {key,crown,gold} checkpoint:cave2_lb+0 hover:yes
 =63  =3080  go        cave2_item-1 {key,wand,crown,gold} checkpoint:cave2_lb+0 hover:no
 =34  =3114  die       cave2_lb+0 {key,wand,crown,gold} checkpoint:cave2_lb+0 hover:no
  =1  =3115  boundary  cave1_rb+0 {key,wand,crown,gold} checkpoint:cave1_rb+0 hover:no
 =14  =3129  go        cave1_door0+1 {key,wand,crown,gold} checkpoint:cave1_rb+0 hover:no
 =13  =3142  door      cave0_door1+0 {key,wand,crown,gold} checkpoint:cave0_door1+0 hover:no
 =28  =3170  go        cave0_door0+1 {key,wand,crown,gold} checkpoint:cave0_door1+0 hover:no
 =13  =3183  door      lake2_door0+0 {key,wand,crown,gold} checkpoint:lake2_door0+0 hover:no
 =63  =3246  go        lake2_door2-1 {key,wand,crown,gold} checkpoint:lake2_door0+0 hover:no
 =13  =3259  door      base1_door0+0 {key,wand,crown,gold} checkpoint:base1_door0+0 hover:no
=111  =3370  go        base1_door1-1 {key,wand,crown,gold} checkpoint:base1_door0+0 hover:no
 =13  =3383  door      base0_door1+0 {key,wand,crown,gold} checkpoint:base0_door1+0 hover:no
 =37  =3420  go        base0_door2-1 {key,wand,crown,gold} checkpoint:base0_door1+0 hover:no
 =13  =3433  door      space2_door0+0 {key,wand,crown,gold} checkpoint:space2_door0+0 hover:no
 =11  =3444  go        space2_item-1 {key,wand,gems,crown,gold} checkpoint:space2_door0+0 hover:no
*** FINISHED! ***

Posted: 11/23/2020 6:14 PM

Post subject: Re: Faster deathwarp in CASTLE0

Quote

Sand

He/Him

Player (125)

Joined: 6/26/2018
Posts: 154

Sand wrote:

I knew about the vertical velocity underflow thing, but I never considered applying it here. Using the underflow to warp to the bottom of the screen is 19 ticks (over 2 seconds) faster than taking enemy damage.

Incidentally, I don't think this trick helps in any of the other places a death is required:

After collecting the Door Key in FOREST2. You could die immediately after collecting the Door Key, instead of taking 8+8 ticks to collide with an enemy and play the death animation; but you would need to die on the way to the item to initiate hover. I hacked the route optimizer to require a hover-based deathwarp from this location and confirmed that it would be no faster.
To initiate hover at the LAKE1/LAKE2 boundary. The point of dying here is that we don't have hover, therefore we cannot use hover to die faster.
To get up to the platform in CAVE0. We don't have hover at this point, and besides there's a ceiling.
To get out of the pit CAVE1. We don't have hover at this point, and besides there's a ceiling.
Deathwarp after collecting the Teleport Wand in CAVE2. There's a ceiling.

If nobody spots any further improvements, I'm planning to make a submission on Wednesday, 2020-11-25. (I solved the login problem I was having.)

Posted: 11/25/2020 10:42 AM

Quote