Posts for Sand

1 2 3 4 5 6 7 8
Posted: 8/11/2023 3:42 AM
Post subject: Re: Frame rate
Sand
He/Him
Experienced Forum User, Published Author, Player (146)
Joined: 6/26/2018
Posts: 198
Sand wrote:
I don't fully understand how FrameRateOverride is meant to be used, but the formula looks wrong. It looks like the intention is that Frames / FrameRateOverride should be equal to lastNonSpecialTimestamp / 1000000000, under the constraint that Frames has to be an integer. But as it is, it's impossible for FrameRateOverride to have a non-zero fractional part. It should at least be casting lastNonSpecialTimestamp to double before doing the division. Intermediate integer truncation is what's leading to the mismatched results.
I opened an issue for this. #1638 Fix calculation of frame rate in JRSR parser
Posted: 8/10/2023 9:55 PM
(Edited: 8/11/2023 3:25 AM)
Post subject: Frame rate
Sand
He/Him
Experienced Forum User, Published Author, Player (146)
Joined: 6/26/2018
Posts: 198
fsvgm777 wrote:
So I've noticed a weird discrepancy between the time reported by JPC-RR and the time given by the site. The site claims it's 14.05 seconds long, but JPC-RR claims it's 14.294 seconds long.
It should be 14.294 s. That's what you get if you add up all the relative event timestamps to the final KEYEDGE 28, 14294723718 ns. My best guess is that the 14.05 s comes from frame count and frame rate on the submission page:
Frame Count 857 Frame Rate 61
857 / 61 = 14.049. Compare that to the previous submission:
Frame Count 951 Frame Rate 60.018933417481854
I wrote the current JRSR parser, but the frame rate formulas are just copied from what was there before: 
Language: csharp
// int Frames;
// double FrameRateOverride;
// long lastNonSpecialTimestamp = 0L;
result.Frames = (int)(lastNonSpecialTimestamp / 16666667);
result.FrameRateOverride = result.Frames / (lastNonSpecialTimestamp / 1000000000L);
Substituting 14294723718 for lastNonSpecialTimestamp yields Frames = 857 and FrameRateOverride = 61.0, as on the submission page. I don't fully understand how FrameRateOverride is meant to be used, but the formula looks wrong. It looks like the intention is that Frames / FrameRateOverride should be equal to lastNonSpecialTimestamp / 1000000000, under the constraint that Frames has to be an integer. But as it is, it's impossible for FrameRateOverride to have a non-zero fractional part. It should at least be casting lastNonSpecialTimestamp to double before doing the division. Intermediate integer truncation is what's leading to the mismatched results. It must have worked differently in the past. Looking at other recent JPC-RR publications, they all have an integer Frame Rate as well: In fact, the most recent JPC-RR publication that has a non-integer Frame Rate is the previous King's Quest publication from 2021-05-08, which predates the new site.
Posted: 8/6/2023 6:14 AM
Post subject: Priority screen for beanstalk clip
Sand
He/Him
Experienced Forum User, Published Author, Player (146)
Joined: 6/26/2018
Posts: 198
Here's a look at the priority screens to see what makes the beanstalk clip work. In room 71 there's just a big gap in the control lines (green lines) that define the edges of the beanstalk.
RoomPicturePriority
72
71
70
I made the images using agi-upscale, modified with a patch from my Mixed-Up Mother Goose repository to save the picture data rather than render it, and the renderer derived from ScummVM that is also in my repository. 
git clone https://www.bamsoftware.com/git/mumg.git
git clone https://github.com/eviltrout/agi-upscale
cd agi-upscale
git apply ../mumg/agi-upscale-write-agipic.patch
mkdir -p agipic xpm png
ruby pic.rb ~/KQ1 all agipic
make -C ../mumg/scummvm-pic
for fn in agipic/*.agipic; do N="$(basename "$fn" .agipic)"; ../mumg/scummvm-pic/scummvm-pic "$fn" "xpm/$N.pic.xpm" "xpm/$N.pri.xpm"; done
for fn in xpm/*.xpm; do convert "$fn" "png/$(basename "$fn" .xpm).png"; done
Posted: 6/9/2023 12:58 AM
Post subject: Score increment tally
Sand
He/Him
Experienced Forum User, Published Author, Player (146)
Joined: 6/26/2018
Posts: 198
Sand wrote:
My impression is that [Round 23] is score-limited rather than block-limited: 3943M breaks a few more blocks early and then takes time to clean up the rest, but that extra time is mostly "free" because it has to wait for the score to catch up anyway; whereas this submission starts slower and then breaks a large burst at the end, so less of the score tally runs concurrently with gameplay.
Here's a picture of what I mean. I wrote a Lua script to record, for each frame, the number of blocks remaining (called remainingBlocks in jaffarPlus, blue in the graph), as well as the 6-element array at 0x037c..0x0381 that represents the score increment; i.e., that points that are waiting to be tallied into the player's score (orange in the graph). Even though 3943M takes longer to break all the blocks, it is overall slightly faster. By breaking blocks at a slower, but more consistent rate, it keeps the score increment more under control. The maximum score increment in Round 23 in 3943M is 13010; here in 8315S it is 33040. The way scoring works is, when you earn points, they don't go directly into your score (the 6-element array at 0x0370..0x0375). Instead the points go into the score increment, and from there they move into your score, a little each frame. Here's an excerpt of the CSV log from 3943M to show how the transfer works:
frameroundremaining_blocksp1_scorescore_increment
2006263007820000470
2007263007830000460
2008263007840000450
2009263007850000440
2010263007860000430
2011263007870000420
2012263007880000410
2013263007890000400
2014263007990000300
2015263008090000200
2016263008190000100
2017263008290000000
The score increment counts down by tens as long as the tens digit is nonzero, then it counts down by hundreds until the whole thing is zero. So, for example, an increment of 1350 takes 13 + 5 = 18 frames to tally into the player's score. A side effect of this method is that sometimes earning points can decrease the amount of time it takes to tally the score increment. For example, an increment of 250 takes 7 frames to tally, whereas an increment of 300 takes only 3 frames. I don't know the internals of jaffarPlus, but would it make sense to add something like scoreIncrement/100 + scoreIncrement/10%10; into the reward in getStateReward, to make the bot take score increment tally delay into account?
Posted: 6/4/2023 7:57 PM
Post subject: Incomplete simulation in 3943M?
Sand
He/Him
Experienced Forum User, Published Author, Player (146)
Joined: 6/26/2018
Posts: 198
Great work. I am a big fan of this kind of TAS optimization. I appreciate the comparison video.
eien86 wrote:
They built a decision tree based on the 8 possible angles a ball can take, I went full brute, allowing any x position for the paddle when a ball is in the 'hittable' layer.
It's not clear to me why these two approaches should produce different output—unless the simulation in [3943] NES Arkanoid "warpless" by Chef Stef in 11:11.18 made an unjustified assumption somewhere and was not completely representative. Do you have a feeling for what the difference might be? For example, is it true that there are exactly 8 possible angles, or did JaffarPlus find a possibility that the simulator in 3943M did not? I suppose the best explanation would come from re-running the simulator from 3943M on a round where the strategies differ, find the point at which the simulator considered (a prefix of) the particular strategy used in this submission, and then figure out why that strategy was rejected. Or, if the simulator never considered the strategy used in this submission, find out what prevented it from exploring that part of the input space. Or does it come down to different scores resulting in different RNG outputs? Round 24 is a good example. As far as I can tell, the ball launch and ball movement are identical, up until this submission collects the multiball powerup 1 or 2 frames earlier. But according to #6347: Chef_Stef's NES Arkanoid "warpless" in 11:11.18, variable delay before collecting a powerup was one of the things considered by the simulator. ("There's a 10-frame window where the powerup is collect-able. Collecting it on different frames lets us manipulate when the single ball turns into a multiball, which affects how each ball can be bounced after that.") So why did the earlier simulator not find the faster solution found here? In Round 32, this submission loses a ball, while 3943M pruned any path that lost a ball. That's one concrete difference that could affect optimization, but it doesn't come into play in every round.
eien86 wrote:
The main difficulty during making this movie was the bonus score screen. After finishing some levels, you get 'punished' with extra score -- I believe this has to do with the amount of enemies you killed, but so far haven't been able to decode it (nor did I spend much time to research it either).
It took me a while to realize that the score tally is what makes Round 23 slower. This submission clears all the blocks more than a second faster than 3943M, but the score tally makes it slightly slower overall. The old 3943M actually earns more points than this submission does (77220 versus 77020, because of 1 additional enemy kill I believe). My impression is that this round is score-limited rather than block-limited: 3943M breaks a few more blocks early and then takes time to clean up the rest, but that extra time is mostly "free" because it has to wait for the score to catch up anyway; whereas this submission starts slower and then breaks a large burst at the end, so less of the score tally runs concurrently with gameplay.
Posted: 5/11/2023 7:18 PM
Post subject: Podcast clip about Desert Bus contest
Sand
He/Him
Experienced Forum User, Published Author, Player (146)
Joined: 6/26/2018
Posts: 198
Arcorann wrote:
Sadly, according to the contest entry form (can be found in the ZIP available here), entering the contest would only have required one point.
That's really interesting, thanks for the link. From it I found https://archive.org/details/smokemirrorsmanual and then https://waxy.org/2006/02/penn_tellers_sm/ and finally https://random.waxy.org/audio/Penn_Jillette_Podcast_on_Smoke_and_Mirrors.mp3, which is a podcast clip in which Penn talks about the Desert Bus contest and mentions a score of 100 points, starting at 3:47.
We were planning on giving a very lavish prize for the person that got the highest score. You know, it was the person that got like, it you got like, a hundred, okay. So a hundred—eight hundred hours of playing this. And we were hoping that groups of people, like fraternities and stuff, would play. We had a very lavish prize. It was going to be, you got to go on Desert Bus, from Tucson to Vegas, with, you know, showgirls and a live band, just the most partying bus ever. You got to Vegas, we're going to put you up in the Rio, big thing. And then, you know, big shows, you could go in there.
There's a summary of the podcast interview by Frank Cifaldi at https://web.archive.org/web/20061225183515/http://www.gamesetwatch.com/2006/03/penn_jillette_discusses_unrele.php. But yeah, the actual challenge rules you linked to require only 1 or even 0 points, since a photo is not required for entry:
  1. No purchase necessary. To enter, complete the official entry form and mail it along with a picture of your screen showing one point to: "Penn & Teller's Desert Bus Challenge Entries," P.O. Box 634, Gibbstown, NJ, 08027. The picture is not a requirement for entry. Incomplete or incorrect entries are ineligible. No photocopies, computer generated, or mechanically reproduced entries will be accepted. Sweepstakes begins 6/23/95. All entries must be received by 5/31/96. Not responsible for lost, late, misdirected, damaged, incomplete, altered, illegible, or postage due mail. Entries become the property of the sponsor and will not be returned.
Posted: 4/30/2023 12:22 AM
Sand
He/Him
Experienced Forum User, Published Author, Player (146)
Joined: 6/26/2018
Posts: 198
vermiceli wrote:
Is it reproducible from the fm2 file?
It is. I don't still have my notes, but I think I just opened the .fm2, let it play until the freeze, then took a look at where PC was in the built-in debugger. I tried setting a few watchpoints to find out what causes the list structure to get messed up, but didn't notice anything obvious.
Posted: 4/27/2023 10:32 PM
Sand
He/Him
Experienced Forum User, Published Author, Player (146)
Joined: 6/26/2018
Posts: 198
vermiceli wrote:
After the Summoning Salt video showing the level skip bug, I decided to start with Trax's disassembly and take it further. I've made a complete disassembly of Contra with proper labels which allows for modification without breaking jumps and branching. It includes supplemental documentation, diagrams, lua scripts, and tooling to build the rom. This code is on github at https://github.com/vermiceli/nes-contra-us/
vermiceli, this is absolutely amazing! Great work. Back when I saw Post #499433 I tried doing some reverse engineering, starting from Trax's disassembly. I gave it up because I was not making much progress. I got as far as identifying, as you did, that ENEMY_VAR_3 and ENEMY_VAR_4 form a doubly linked list of the dragon tentacle arm orbs. As I recall, the freeze in Post #499433/Post #499462 was caused by one of the lists somehow developing a cycle (one of the elements pointing to itself). I had hoped it was some wild PC branch, which might offer possibilities of code execution, but it was just an infinite loop over a linked list that had failed to maintain one of its invariants, probably in @enemy_orb_loop or nearby. Anyway, this disassembly probably opens a lot of doors, to better romhacks, mods, randomizers… pretty exciting.
Posted: 4/2/2023 2:48 AM
Sand
He/Him
Experienced Forum User, Published Author, Player (146)
Joined: 6/26/2018
Posts: 198
First one to make me LOL, good job.
Posted: 4/2/2023 2:36 AM
Sand
He/Him
Experienced Forum User, Published Author, Player (146)
Joined: 6/26/2018
Posts: 198
Great concept.
Posted: 3/26/2023 3:44 PM
Post subject: Dialog options
Sand
He/Him
Experienced Forum User, Published Author, Player (146)
Joined: 6/26/2018
Posts: 198
Nice game choice, I found this interesting.
LogansGamingRoom wrote:
The RTA world record by BeetZero chooses "TELL ME MORE" every time, so I took a page out of his book and did that.
The developer's page says there is unique dialog for each option:
Each retort will lead to unique dialogue: Tell me more: André will keep talking. Trenchant Insight: Wallace will offer some insight of his own. Bon Mot: Wallace will offer a witticism.
I would like to know if choosing options other than "Tell me more" could save time. It is possible that "Tell me more" is always the fastest option, because Wallace says just one line before André resumes talking, but maybe in some cases the sum of the lengths of Wallace's speech and André's speech is shorter overall when choosing a different option. (You will have to take cursor movement into account too.) It may turn out that all the choices are independent: in that case optimization will be easy, just choose the fastest of the three options at each decision point. If there are dependencies (past choices affect future choices), then it may be harder. As a preliminary test, you could try all three choices at the final decision point, and record the time for each. Then, try different choices for the second-to-last decision point, and see if the the final decision point remains the same.
Posted: 2/15/2023 5:11 AM
Post subject: Faster entry into crooked house
Sand
He/Him
Experienced Forum User, Published Author, Player (146)
Joined: 6/26/2018
Posts: 198
As I was watching the new publication, I noticed a small mistake. It's possible to enter the crooked house at 15:02 3 cycles faster. I did some testing, and the gain ends up getting wiped out by framerules later on, so the mistake does not actually lose time. But it's close—saving even 1 additional cycle in this segment of the run could catch an earlier framerule and save up to 1 second overall. The mistake I made was entering the door near the bottom of the screen, instead of near the top. The door is activated when the player touches a signal line, represented by the color green in the priority screen. As you can see in the graphic below, the signal line is 3 pixels closer to the right edge of the screen at the top, compared to the bottom. It doesn't lose any time to get to the top of the signal line, so I should have done that in room 15, as I did when entering similar doors at the clock house (room 24) at 11:00 and Jack Horner's house (room 26) at 12:57. A zoomed-in crop of the priority screen in room 15, with semitransparent player characters overlaid, showing where they touch the signal line at its top and bottom. The earlier entry into the clock house saves 3 cycles, but then causes a desync after delivering the Pail to Jack and Jill, which has to be fixed by adding 2 cycles of waiting before ending the cutscene. Let's look at the nature of the framerule. There are several places—including during delivery cutscenes—where the game delays for a fixed amount of time. It does this by setting the special variable clock_seconds to 0, then waiting for it to exceed a certain value. Here's an example in 51.agilogic, which is the logic file for the Pail delivery cutscene: 
if (!FLAG_CUTSCENE_PLAYING_f104 && FLAG_IN_POSITION_FOR_CUTSCENE_f104) {
  set(FLAG_CUTSCENE_PLAYING_f104);
  set(advance_sequence_f43);
  reset(FLAG_IN_POSITION_FOR_CUTSCENE_f104);
  sound(4, FLAG_SOUND_FINISHED_f103);
  clock_seconds = 0;
  set(f15);

  if (video_mode != 2) {
    print.at("                                    \n\n\n", 17, 2, 37);
    display(18, 2, "Jack and Jill went up the hill,");
  } else {
    print.at("                                    \n\n\n", 19, 2, 37);
    display(20, 2, "Jack and Jill went up the hill,");
  }
}

if ((clock_seconds > 4) && FLAG_CUTSCENE_PLAYING_f104 && !f109) {
  set(f109);

  if (video_mode != 2) {
    display(19, 2, "   To fetch a pail of water;");
  } else {
    display(21, 2, "   To fetch a pail of water;");
  }
}
Notice clock_seconds = 0 and if (clock_seconds > 4). The game engine measures time using the variables clock_seconds, which is read/write accessible to logic code, and clock_subseconds, which is not accessible to logic. clock_subseconds increments 20 times a second (regardless of game speed), repeatedly counting from 0 to 19 and incrementing clock_seconds when it wraps from 19 to 0. When the logic zeroes clock_seconds to start a delay timer, it does not also zero clock_subseconds, which means the first "second" may be less than a full second. A nominal delay of 5 seconds, for example, may take anywhere between 4.05 and 5.00 seconds of real time. Why then, does the game desync only after the Pail delivery, and not with the delivery of the Horse or the Sheep, which happen after entering the crooked house and before delivering the Pail? Both of those deliveries have similar delay logic using clock_seconds. Delivery cutscenes have many things happening at once: animation of sprites, music, and timed text in a text box. The cutscene does not end until all those mostly independent sequences are finished. The animation and music sequences have their own, separate methods of timing; animation usually works by counting game cycles rather than counting seconds. The Pail delivery, unusually, has a conditional that couples the animation timing and the delay timing: 
if ((animation_counter_v48 == 5) && (clock_seconds > 9)) {
  set(advance_sequence_f43);
}
There are only three other deliveries that have such a coupling: Watering Can, Mouse, and Pie. It is actually more complicated than I have explained so far. You can fix the desync after the Pail delivery by adding not 3, but 2 cycles of delay. After that, the movie will desync again the collection of Miss Muffet (which uses a similar clock_seconds delay). You can fix that by adding 1 more cycle of delay, but at which point the 3 cycles gained are used up, and the movie syncs to the end with no gain or loss in time. Why are only 2 cycles lost because of the clock_seconds framerule, not 3? I think it is because of a different framerule, one that comes into play when the game logic slows the game speed from Fast to Normal (i.e., changes the value of cycle_delay from 1 to 2) and back again, before and after the cutscene. I observed this 2-cycle framerule a couple of times while working on the TAS; I found a way to improve an earlier section by 1 cycle, but the gain was nullified by a later delivery. If the 3-cycle improvement on entering the crooked house doesn't help because it doesn't catch an earlier framerule, how close is that earlier framerule? Very close, it turns out: saving even 1 more cycle anywhere between delivering the Pie and delivering the Pail would do it, and save up to 1 second. In the published TAS, the zeroing of clock_seconds happens when clock_subseconds is 3. With the earlier crooked house entry, the zeroing of clock_seconds happens when clock_subseconds is 0; that is, it happens 3 cycles earlier, but then you have to wait 20 cycles to the top of the next second instead of 17 cycles. If you could get there early enough so that clock_seconds were zeroed when clock_subseconds was 19, the first "second" of delay would take only 1 cycle to elapse. I say "up to" 1 second because of the other sequences that happen during the cutscene; it could be that the actual gain is less. User movie #638120343391821721 demonstrates the faster crooked house entry.
Posted: 1/16/2023 4:42 PM
Sand
He/Him
Experienced Forum User, Published Author, Player (146)
Joined: 6/26/2018
Posts: 198
I didn't mean to suggest more work for c-square. On further reflection, it may not be possible to continue satisfying the "maximum score" objective in levels 1 and 2 while also manipulating level 3. I guess it depends on how the RNG works and whether it is possible to manipulate without sacrificing score.
Posted: 1/15/2023 8:09 PM
Post subject: End screen graphical glitch
Sand
He/Him
Experienced Forum User, Published Author, Player (146)
Joined: 6/26/2018
Posts: 198
Do you know the cause of the graphical glitch on the victory screen, TO THE HOMEL■.? The RTA video has TO THE HOMELAND.. Is it a side effect of the zip?
Posted: 1/15/2023 7:12 PM
Sand
He/Him
Experienced Forum User, Published Author, Player (146)
Joined: 6/26/2018
Posts: 198
I appreciate what you're doing, good work ShesChardcore. Nice observation about scoring at 0:00 to avoid a faceoff. Do I understand correctly, that the first two periods could be treated as a playaround, as long as you don't do anything that stops the clock or causes lag frames? That is, for the purposes of ending input early, the faceoff lockdown trick is only strictly necessary in the third period?
Posted: 1/12/2023 10:51 PM
Post subject: RNG manipulation?
Sand
He/Him
Experienced Forum User, Published Author, Player (146)
Joined: 6/26/2018
Posts: 198
I voted yes. Is the order of sentences in level 3 fixed? Or is it random? If RNG manipulation is possible, then it may be possible to optimize for real time by getting sentences that are as long as possible. My reasoning is that the timer doesn't count down during the pipe transition cutscenes, each of which takes about 10 seconds. The 5:00 timer takes 8:42 of real time to count down. The last pipe transition cutscene happens when the timer reads 4:59, which means that if any of the earlier active typing segments had lasted even 1 second longer, it would have saved 10 seconds of real time with the same high score. But if the order of sentences is fixed, then it really is an autoscroller and I don't see any way to improve it.
Posted: 1/12/2023 10:12 PM
Post subject: "Platform: ..." in LTM format
Sand
He/Him
Experienced Forum User, Published Author, Player (146)
Joined: 6/26/2018
Posts: 198
LTM movies, by default, have the system set to Linux. You can override the default by adding a line to annotations.txt like: 
Platform: DOS
However, I did not find the Platform: ... syntax documented anywhere. I discovered it by downloading and inspecting a few LTM publications. The places I checked were: I suggest that Platform: ... be documented in at least one of the above pages. The submission where I noticed this is Thread #23925: #7943: Sand's DOS Mixed-Up Mother Goose in 25:51.83.
Posted: 1/12/2023 9:52 PM
Post subject: Platform: DOS
Sand
He/Him
Experienced Forum User, Published Author, Player (146)
Joined: 6/26/2018
Posts: 198
The system is showing as Linux, but it should be DOS. I noticed after submitting that there's a way to control the system from the LTM file: add a line with Platform: DOS to annotations.txt: https://github.com/TASVideos/tasvideos/blob/c981736dc4b705e273b5e323d6e617431ca0f0ec/TASVideos.Parsers/Parsers/Ltm.cs#L99 User movie #638091565403343303 is the same as the submitted movie, but with Platform: DOS added to annotations.txt.
Posted: 1/11/2023 4:51 PM
Post subject: VGA VSYNC
Sand
He/Him
Experienced Forum User, Published Author, Player (146)
Joined: 6/26/2018
Posts: 198
TheAmazingYucemu wrote:
HDMI to VGA V-sync frame advance firmware modification instruction update is now in development
If you know about VGA VSYNC, maybe you could comment on the circuit in Post #512716, which is about an Arduino device to provide USB keyboard inputs to a PC. I have tried to make the program synchronize its timing by reading the PC's VSYNC signal, but I don't have a clue when it comes to electrical matters like this. I haven't had time to update the other thread, but I had some luck syncing [1781] DOS The Amazing Spider-Man by NitroGenesis in 00:18.62 with the VSYNC modification.
Posted: 1/8/2023 8:38 PM
(Edited: 7/20/2023 6:34 PM)
Sand
He/Him
Experienced Forum User, Published Author, Player (146)
Joined: 6/26/2018
Posts: 198
slamo wrote:
I'm unable to sync this, can you please post the contents of your cfg file?
Sure, it's here: https://www.bamsoftware.com/computers/tasvideos/mumg-tandy.cfg. You will have to replace /path/to/000168_mixed-up_mother_goose/disk1.img. ~/.pcem/nvr/tandy.tandy1000sl2.bin is just 128 bytes of 0x00. 512 KB of RAM is important—it doesn't sync with 640 KB. In the "Game executable" field of libTAS I have /usr/bin/pcem, and in the "Command-line options" field I have --config /home/user/.pcem/configs/tandy.cfg --load_drive_a /path/to/000168_mixed-up_mother_goose/disk1.img (see annotations).
Posted: 1/8/2023 7:48 AM
Post subject: Submission #7943
Sand
He/Him
Experienced Forum User, Published Author, Player (146)
Joined: 6/26/2018
Posts: 198
Sand wrote:
I have finished executing the route. Below is an encode. The time is 25:51.83
Here is the submission: #7943: Sand's DOS Mixed-Up Mother Goose in 25:51.83.
Posted: 12/21/2022 2:18 AM
Post subject: Visualization of route optimization
Sand
He/Him
Experienced Forum User, Published Author, Player (146)
Joined: 6/26/2018
Posts: 198
In writing up submission notes, I wanted to have a visualization of the simulated annealing optimization process of Post #516005. It turns out there's no way to embed an archive.org video in wiki markup, so I will post it here. The optimization schedule was set to run for 20 million iterations. There's one frame of the video for every 20,000th iteration. The yellow line shows the candidate path being explored at the current iteration. The blue line shows the current best path found so far. The graph at the bottom shows the improvement in the route cost over time, and how the cooling schedule causes the candidate routes to converge. Link to video
Posted: 11/20/2022 1:04 AM
(Edited: 1/4/2023 4:04 AM)
Post subject: Finished route in 25:52.83
Sand
He/Him
Experienced Forum User, Published Author, Player (146)
Joined: 6/26/2018
Posts: 198
I have finished executing the route. Below is an encode. The time is 25:51.83. This is the version I plan to submit, if nobody spots any improvements. The LTM file is uploaded alongside the video. Link to video
Posted: 11/11/2022 4:04 AM
Post subject: Through delivery of Knife
Sand
He/Him
Experienced Forum User, Published Author, Player (146)
Joined: 6/26/2018
Posts: 198
I have completed the route up through the delivery of the Knife. That's 16/20 deliveries complete, with 20m50s elapsed so far. We're now at another point where the optimizer found more than one route with equal cost. We need to take a more fine-grained look at costs to see which one is best. A directed graph where the nodes are subsegments of the route, each containing steps (get an item or deliver the current inventory item) to be executed in order. Arrows between the nodes show where there are equal-cost routing options. (Graphviz source.) The optimizer is telling us there are two possible orders to handle the next three items:
  • Lamb, Fiddle, Wife
  • Fiddle, Wife, Lamb
Fiddle always precedes Wife; the only choice is whether to do Lamb first or Lamb last. I started to measure out within-room costs, as in Post #517062, but after some reflection, I came to the conclusion that Lamb first must be faster, because you can take advantage of fast vertical movement along the eastern town wall. There's another way to think about the item order in this segment of the route. You need to make two excursions into the eastern part of the map: one to collect and bring back the Wife, and one to collect and bring back the Fiddlers Three. You have a choice of whether to collect and delivery the Lamb en route to collecting the Wife, or en route to collecting the Fiddlers Three. The connectivity logic along the outer walls lets you skip a lot of vertical movement. For example, moving north room 19 to room 12 doesn't put you at the bottom of the screen (y-coordinate 167) as in most rooms; it puts you at y-coordinate 107, which saves 60 game cycles, or 3 s. Below is the relevant code in 12.agilogic. (Incidentally, this code is also the source of a connectivity glitch mentioned in Post #515863, where you can "jump the wall" if you are close enough to the wall when moving north.) 
  get.posn(O_EGO, v212, v213);
  if (prev_room_no == 19) {
    if (v212 > 120) {
      // Ego came from the left part of room 19;
      // put them outside the wall.
      set.priority(O_EGO, 5);
      position(O_EGO, 149, 107);
      if (F_HAVE_WALKING_ITEM) {
        position(O_WALKING_INVENTORY_ITEM, 146, 86);
        set.priority(O_WALKING_INVENTORY_ITEM, 4);
        set(f100);
      }
    } else {
      // Ego came from the left part of room 19;
      // put them inside the fence.
      position(O_EGO, 86, 166);
      if (F_HAVE_WALKING_ITEM) {
        position(O_WALKING_INVENTORY_ITEM, 100, 167);
      }
      if (current_inventory == ITEM_PUMPKIN_WIFE) {
        load.logics(62);
        set(f42);
      }
    }
  }
If you detour to collect the Lamb, then you cannot take advantage of fast vertical movement near the wall. Since the path to collect the Wife takes you away from the wall anyway, combine the Lamb delivery with the Wife excursion, and let the Fiddlers Three excursion use wall movement.
Posted: 10/22/2022 4:43 AM
Post subject: After collecting Bowl
Sand
He/Him
Experienced Forum User, Published Author, Player (146)
Joined: 6/26/2018
Posts: 198
I finished TASing up through collecting the Bowl and bringing it to room 11. I'm now at the point where the optimizer found multiple routes that it thinks have equal cost. (See the diagram in Post #516163.) We now have to decide which route is actually best, using a more precise model of movement and cost than the optimizer had. Screenshot of the Crooked Man animation. "You there! Fetch me my sixpence!" There's one easy simplification we can apply right away. Part of the route calls for collecting the Pail in room 22 and delivering it to room 1. But on the way stands the Crooked Man in room 15. He stands in a part of the room where there is no way to avoid him. When you get close, he will waste about 8 seconds asking for his Sixpence. We can avoid this delay by always delivering the Sixpence before the Pail. Therefore we can remove all the candidate routes where G26 ("get Pail") comes before G28 ("get Sixpence"). That leaves the following 12 possibilities: 
G16-D-G24-D-G25-D-G27-D-G23-G22-D-G13-D-G21-D-G19-D-G28-D-G30-D-G15-D-G26-D-G12-D-G20-D-G23-D-G29-D-G17-D-G18-D-G11-D-G14-D
G16-D-G24-D-G25-D-G27-D-G23-G22-D-G13-D-G21-D-G19-D-G28-D-G30-D-G15-D-G26-D-G12-D-G20-D-G23-D-G29-D-G18-D-G11-D-G17-D-G14-D
G16-D-G24-D-G25-D-G27-D-G23-G22-D-G23-D-G29-D-G13-D-G21-D-G19-D-G28-D-G30-D-G15-D-G26-D-G12-D-G20-D-G17-D-G18-D-G11-D-G14-D
G16-D-G24-D-G25-D-G27-D-G23-G22-D-G23-D-G29-D-G13-D-G21-D-G19-D-G28-D-G30-D-G15-D-G26-D-G12-D-G20-D-G18-D-G11-D-G17-D-G14-D
G16-D-G24-D-G25-D-G27-D-G23-G22-D-G29-D-G13-D-G21-D-G19-D-G28-D-G30-D-G15-D-G26-D-G12-D-G20-D-G23-D-G17-D-G18-D-G11-D-G14-D
G16-D-G24-D-G25-D-G27-D-G23-G22-D-G29-D-G13-D-G21-D-G19-D-G28-D-G30-D-G15-D-G26-D-G12-D-G20-D-G23-D-G18-D-G11-D-G17-D-G14-D
G16-D-G24-D-G25-D-G27-D-G23-G22-D-G29-D-G23-D-G13-D-G21-D-G19-D-G28-D-G30-D-G15-D-G26-D-G12-D-G20-D-G17-D-G18-D-G11-D-G14-D
G16-D-G24-D-G25-D-G27-D-G23-G22-D-G29-D-G23-D-G13-D-G21-D-G19-D-G28-D-G30-D-G15-D-G26-D-G12-D-G20-D-G18-D-G11-D-G17-D-G14-D
G16-D-G24-D-G25-D-G27-D-G23-G29-D-G13-D-G21-D-G19-D-G28-D-G30-D-G15-D-G26-D-G12-D-G20-D-G22-D-G23-D-G17-D-G18-D-G11-D-G14-D
G16-D-G24-D-G25-D-G27-D-G23-G29-D-G13-D-G21-D-G19-D-G28-D-G30-D-G15-D-G26-D-G12-D-G20-D-G22-D-G23-D-G18-D-G11-D-G17-D-G14-D
G16-D-G24-D-G25-D-G27-D-G23-G29-D-G22-D-G23-D-G13-D-G21-D-G19-D-G28-D-G30-D-G15-D-G26-D-G12-D-G20-D-G17-D-G18-D-G11-D-G14-D
G16-D-G24-D-G25-D-G27-D-G23-G29-D-G22-D-G23-D-G13-D-G21-D-G19-D-G28-D-G30-D-G15-D-G26-D-G12-D-G20-D-G18-D-G11-D-G17-D-G14-D
Schematically, the remaining candidates are: A directed graph where the nodes are subsegments of the route, each containing steps (get an item or deliver the current inventory item) to be executed in order. Arrows between the nodes show where there are equal-cost routing options. (Graphviz source.) Ignoring the final part of the route, where there will also be a choice to make, there are four immediate tasks before us, which we must execute in some order:
  • Collect and deliver the Pipe to Old King Cole.
  • Collect and deliver the Bowl to Old King Cole.
  • Collect and deliver the Ladder to Humpty Dumpty.
  • Complete a tour of item delivery that begins with collecting the Mouse in room 19S and ends with delivering the Knife in room 3.
Let's abbreviate these four tasks as P, B, L, T. The optimizer tells us there six reasonable orders to do them in:
  • PTBL
  • PBLT
  • PLBT
  • PLTB
  • LPBT
  • LTPB
There are five rooms we care about: 11, 3, 4, 5, 37. (The T tour goes though many more rooms, but that part of the route is always the same, so we can ignore it for the purpose of comparing routes.) For brevity, we'll label the five rooms V, W, X, Y, Z. 
  Z       37
W X Y = 3  4  5
  V       11
I broke down every movement you might have to make in executing any of the six task orders listed above and returning to the top of room V. You'll notice that almost all movements indicated on the diagrams below are purely horizontal or purely vertical. That's because diagonal movement in this game is "free": you can move one pixel horizontally and one pixel vertically every game cycle. So while most movements include both a horizontal and a vertical component, I only show whichever of the two is greater. There are only two exceptions, w2 and y2, where obstructions prevent taking advantage of diagonal movement. The diagrams below are squished horizontally compared to how they appear in the game, to undo the game's 2× scaling and make 1 pixel equal to 1 unit of distance in all directions. The diagrams also cut off the inaccessible part of the room above the horizon. I've marked the areas where you can pick up or deliver an item, and the points to which the player character automatically walks after an item delivery animation plays.
movement
fromto
EV
cost to enter room V
v1
entry with Bowlleft side of Pipe
v2
left side of Pipe/Bowltop edge
v3
top edge − 4top side of Bowl
v4
top side of Bowltop edge
v5
top edge − 4bottom edge
v6
bottom edgetop edge
v7
top edge − 4, towards rightupper right side of Pipe/Bowl
v8
upper right side of Pipe/Bowltop edge
v9
top edge, towards leftleft side of Pipe/Bowl
EW
cost to enter room W
w1
right edgedelivery radius
w2
post-delivery (35, 118)bottom edge
EX
cost to enter room X
x1
bottom edgedoor
x2
door − 5bottom edge
x3
doorright edge
EY
cost to enter room Y
y1
left edgedelivery radius
y2
post-delivery (35, 130)bottom edge
EZ
cost to enter room Z
z1
entrydelivery rectangle
z2
post-delivery (77, 100)bottom edge
z3
post-delivery (77, 100)right side of Ladder
z4
right side of Ladderbottom edge
z5
top right of Bowldelivery rectangle
z6
entryright side of Ladder
z7
post-delivery (77, 100)top right of Bowl
T
cost to execute the T tour
Now we can add up the movements in each of the six routing options: 
      (------------ P ------------) (---------------------- B ----------------------) (------------ L ------------) (---------------- T -----------------)
PBLT = v1 + v2 + Ex + x1 + Ez + z1 + z2 + Ex + x2 + Ev + v3 + v4 + Ex + x1 + Ez + z1 + z3 + z4 + Ex + x3 + Ey + y1 + y2 + Ev + v5 + T + Ev + v6 + Ew + w1 + w2

      (------------ P ------------) (--------------------- T ----------------------) (----------------- B -----------------) (------------ L ------------)
PTBL = v1 + v2 + Ex + x1 + Ez + z1 + z2 + Ex + x2 + Ev + v5 + T + Ev + v6 + Ew + w1 + w2 + Ev + v9 + v2 + Ex + x1 + Ez + z1 + z3 + z4 + Ex + x3 + Ey + y1 + y2

      (------------ P ------------) (------------ L ------------) (------------------ B ----------------) (--------------------- T ----------------------)
PLBT = v1 + v2 + Ex + x1 + Ez + z1 + z3 + z4 + Ex + x3 + Ey + y1 + y2 + Ev + v7 + v8 + Ex + x1 + Ez + z1 + z2 + Ex + x2 + Ev + v5 + T + Ev + v6 + Ew + w1 + w2

      (------------ P ------------) (------------ L ------------) (---------------- T -----------------) (----------------- B -----------------)
PLTB = v1 + v2 + Ex + x1 + Ez + z1 + z3 + z4 + Ex + x3 + Ey + y1 + y2 + Ev + v5 + T + Ev + v6 + Ew + w1 + w2 + Ev + v9 + v2 + Ex + x1 + Ez + z1 + z2 + Ex + x2

      (---------------------- L ----------------------) (----------------- P -----------------) (-- B --) (--------------------- T ----------------------)
LPBT = v6 + Ex + x1 + Ez + z6 + z4 + Ex + x3 + Ey + y1 + y2 + Ev + v7 + v8 + Ex + x1 + Ez + z1 + z7 + z5 + z2 + Ex + x2 + Ev + v5 + T + Ev + v6 + Ew + w1 + w2

      (---------------------- L ----------------------) (---------------- T -----------------) (----------------- P -----------------) (-- B --)
LTPB = v6 + Ex + x1 + Ez + z6 + z4 + Ex + x3 + Ey + y1 + y2 + Ev + v5 + T + Ev + v6 + Ew + w1 + w2 + Ev + v9 + v2 + Ex + x1 + Ez + z1 + z7 + z5 + z2 + Ex + x2
We will not need actual numbers for most of these movements components, because common terms wil cancel. Eliminating common terms, we find all room transition costs, and anything having to with rooms W, X, and Y disappear: those components have identical costs in all routes. 
PBLT − common = v1 + v2 + v3 + v4 + z1 + z3
PTBL − common = v1 + v2 + v2 + v9 + z1 + z3
PLBT − common = v1 + v2 + v7 + v8 + z1 + z3
PLTB − common = v1 + v2 + v2 + v9 + z1 + z3
LPBT − common = v6 + v7 + v8 + z5 + z6 + z7
LTPB − common = v6 + v2 + v9 + z5 + z6 + z7
Immediately we can tell PTBL = PLTB. Because (by inspection of the diagrams) v3 + v4 < v2 + v9, we have PBLT < PTBL = PLTB. Therefore neither PTBL nor PLTB is the fastest route. Also, since v3 + v4 < v7 + v8 (barely), we have PBLT < PLBT. Similarly, since v7 + v8 < v9 + v2, we have LPBT < LTPB. That leaves just two contenders for the optimum route: 
PBLT − common = v1 + v2 + v3 + v4 + z1 + z3
LPBT − common = v6 + v7 + v8 + z5 + z6 + z7

v1 = 94 − 22 = 72
v2 = 84 − 59 = 25
v3 = 80 − 65 = 15
v4 = 84 − 65 = 19
v6 = 84 −  0 = 84
v7 = 80 − 64 = 16
v8 = 84 − 64 = 20
z1 = 50 −  0 = 50
z3 = 68 − 23 = 45
z5 = 50 − 26 = 24
z6 = 68 − 35 = 33
z7 = 68 − 26 = 42

PBLT − common = 72 + 25 + 15 + 19 + 50 + 45 = 226
LPBT − common = 84 + 16 + 20 + 24 + 33 + 42 = 219
We choose between them just by adding up the movement components. The winner, by 7 game cycles, is Ladder, Pipe, Bowl, then Mouse→Knife tour. Put another way, the originally 24 presumed equal-cost routes have collapsed into just two: 
G16-D-G24-D-G25-D-G27-D-G23-G29-D-G22-D-G23-D-G13-D-G21-D-G19-D-G28-D-G30-D-G15-D-G26-D-G12-D-G20-D-G17-D-G18-D-G11-D-G14-D
G16-D-G24-D-G25-D-G27-D-G23-G29-D-G22-D-G23-D-G13-D-G21-D-G19-D-G28-D-G30-D-G15-D-G26-D-G12-D-G20-D-G18-D-G11-D-G17-D-G14-D
1 2 3 4 5 6 7 8