Submission #4992: vaxherd's NES Dragon Warrior III "item glitch" in 41:09.52

Nintendo Entertainment System
item glitch
FCEUX 2.2.2 (NewPPU)
148415
60.0988138974405
2212
Unknown
Dragon Warrior III (U) [!].nes
Submitted by vaxherd on 1/31/2016 11:27:07 AM
Submission Comments

General information

  • Emulator used: FCEUX 2.2.2 (NewPPU)
    • Note that FCEUX 2.2.2's NewPPU does not implement grayscale, which is used by Dragon Warrior III in the battle start animation. See http://pastebin.com/7YFh3v54 for a fix, which is cosmetic only and does not affect synchronization.
  • Uses death and damage to save time
  • Heavily manipulates luck
  • Corrupts memory

Overview

This run is about 7 minutes faster than the previous published run by dave_dfwm due to careful analysis of the game's code, including the behavior of the random number generator (RNG) and details of how the item glitch works. In particular, this run takes advantage of a design flaw in the RNG to cause it to output sequential values, making encounters much less frequent and more predictable (though also requiring extra walking and healing in a few places). Highlights include encounterless Najima, a double Metal Babble kill at level 1, and 2-turn Ortega and Zoma battles.

Part 1: Party setup

Before breaking the RNG, we buy a couple of Wings at the item shop, and we create a pilgrim and a wizard at Luisa's Place. We next step outside Aliahan, get into a battle with a Slime, and kill off two party members who will be used later in the item glitch. Then we go back to Luisa, swap out the dead party members for the two remaining ones, and reset to start RNG manipulation.
The names of the hero and the two characters added at Luisa's Place were selected to ensure that the pregenerated pilgrim starts with 9 MP (allowing us to cast Heal 3 times, so we need one less herb), to avoid the woman near the entrance of Aliahan getting in the way when we try to leave the town, and to force an encounter with a single Slime on the first step in the overworld.
The Slime battle has a second purpose beyond getting dead party members: setting the battle RNG seed to a useful value. DW3 has a separate RNG seed used mainly by battle routines which serves as a counter to discard some numbers from the RNG output stream; the seed is stored in backup RAM, and it only changes at the beginning of a turn in battle, and only when you don't attempt to run. Among other things, this seed is used in the healing effects for herbs and the Heal spell even outside of battle, so by setting it to a large enough value, we can skip over encounters with a single Heal spell or herb. However, we also need it set to a value that will give us a numb character in the next battle, so we end up with one spot later where we have to heal twice to get past an encounter.

Part 2: Aliahan -> Kanave

For this segment of the run, we create a file with a specific name, sex, and message speed to put the RNG into a "hole", in which the random part of the generator is stuck on a single value and the output is just the sum of that value and a counter which increases by 1 each time the random routine is called. Since encounter checks, like most random checks in the game, look at whether a random number is less than a threshold value, we just need to get the RNG past that threshold and we can walk around without fear of encounters, at least until the counter rolls over.
One danger of using this method is that, due to a design flaw in the logic to generate battle groups, the game can freeze when starting an encounter, so we have to ensure that we have a way (such as Heal spells or herbs, or waiting in a town or the overworld) to push the counter past the threshold again without moving.
The route starts off by adjusting party order in preparation for the Killer Bee battle later, then Winging outside Aliahan. Not only is the Wing faster than walking, it also preserves the low RNG counter value we start out with, while walking through town would increase the counter as NPCs used random numbers to change direction. The party order switch serves the additional purpose of delaying the game's movement frame counter by 16 frames (the delay before opening the menu); on the overworld, 2-3 random numbers are consumed every 64th frame, and waiting 16 frames here shifts the frame counter so that we can skip one of those cycles. (If we Winged out immediately, the RNG counter would end up 1 higher on entering the Najima tunnel, and we'd have to do an encounter skip in the tower.)
We go straight for the hidden entrance to the Najima tunnel, since it's slightly faster to walk from Aliahan a second time than to enter and exit Reeve to get the Return point. Along the way, we stop for a short time on the bridge to get past an encounter; this is about 1 second slower than using Heal to skip the encounter, but if we used Heal, the RNG counter would get pushed too far forward and we'd have to skip another encounter in the tower. (As it is, we exit the tower on the last possible step before getting an encounter on the overworld.) Waiting also allows us to save a Heal for later, meaning one less herb we have to buy in Reeve.
After getting the key, we walk from Aliahan to Reeve, and buy herbs for encounter skips and item glitching and another Wing for the Killer Bee battle near Kanave. Then we walk all the way from Reeve to Kanave; the linear RNG output means we only need to skip two encounters along the way, though for the second one, we need a double heal, a bit of waiting, and a couple of extra steps to push the RNG counter far enough forward that we don't get an encounter when we step on a hill tile.
In Kanave, we grab the Poison Needle, then leave town and wander around until we get an encounter. (*) We arrange for the encounter to contain a Killer Bee and to have it numb the soldier; then we kill off the hero and wizard to set up for the item glitch, wing back to Aliahan, and make our way to Luisa's Place, being careful not to move on frames which would cure the soldier's numbness.
(*) This is the flip side of the RNG glitch: Once past an encounter, the RNG counter has to advance by nearly 256 before it returns to the range in which an encounter can occur. Since the counter advances an average of 1.625 per step when in the overworld and it takes around 2.3 seconds = 9 steps to open the menu and heal, which only advances the counter by 11 with the battle RNG seed we need for Killer Bee manipulation, it turns out to be faster to simply walk around on the world map to advance the RNG counter. Here, we need to take 127 steps and wait twice, costing about 34 seconds. Even with this delay, though, this route is still about 25 seconds faster through the beginning of the Killer Bee battle than the previous route, largely because we almost never have to skip encounters.
An interesting discovery made while routing this battle is that enemies with the Increase spell who use "smart" AI (which, as it happens, is all enemies with Increase) only allow targets for the spell whose defense is at least 768. This appears to be a bug; the relevant code (at $BC90 in bank 4) is:
   lda $0521,y  ;Load high byte of defense
   cmp #3       ;Compare against 3 (i.e., compare defense against 768)
   bcc $BC3F    ;If less than 3, add to enemy selection bitmask
   bcs $BC42    ;Otherwise, don't add to enemy selection bitmask
I suspect this is the result of programmer confusion caused by the fairly convoluted method used to select random targets -- in particular, the selection routines require a bitmask of characters to exclude from selection, rather than the more natural method of passing a bitmask of characters to include. So by adding enemies with defense less than 768 to the bitmask, the code is actually excluding them as possible targets, and since that leaves no valid targets, the enemy that tried to use Increase will reroll its action. The upshot of all this is that the Caterpillar which appears in the Killer Bee battle will sometimes consume several random numbers before successfully choosing an action.

Part 3: Item glitch (a.k.a. Dream Ruby glitch, numbness glitch)

As with the route used by dave_dfwm's earlier TAS, party state glitching is accomplished with 1 numb character and 3 dead characters, taking advantage of a bug in the Luisa character removal logic that lets you remove a numb character even if it leaves only dead characters in the party. We remove first the (non-numb) wizard and then the (numb) soldier, then add back the two characters we created and killed off earlier. This gives us a party of 4 dead characters, which activates the glitch.
Once the glitch has been activated, we exit to the overworld and take steps at specific times to modify the current party status. We take advantage of the dead time between steps to move items around to where they can be glitched; opening the menu also allows us to time our steps to specific frames, avoiding the 16-frame granularity that applies when moving around.
Without getting too deep into technical details (see the links below for more details than you ever wanted), the glitch occurs because the game gets confused at having no live characters in the party, so it tries to check 256 bytes of memory for damage tiles (swamp or barrier), rather than just the 1-4 bytes containing the tiles the party is standing on. If any of those bytes indicates a "swamp" tile, the game tries to subtract 2 from the corresponding HP value, but since it's checking past the end of the party list, the minus-2 is instead applied to data like Return location flags or item numbers.
It's also possible to trigger the glitch on the second floor of Luisa's Place, but the advantage of using the overworld is that we can time our steps to when just one or two bytes out of the 256 indicate swamp damage, so we can modify exactly the parts of memory we want. In town, there are a lot more bytes in memory which have the "swamp" value, and many of those point to parts of memory the game reads as 0 HP, so it shows a "<name> is dead" message (wasting several seconds) for each one.
Over the course of several trips out of and back into Aliahan, we accomplish the following:
  • Change a Cypress Stick into 2 copies of a glitched " Black Raven" item which we can sell for 58500 gold.
  • Change one of the " Black Raven" items into a Sphere of Light.
  • Change a Copper Sword into a Rainbow Drop.
  • Change a Leather Armor into a Sword of Kings.
  • Change a Leather Helmet into a Shield of Heroes.
  • Change a Wayfarer's Clothes into an Armor of Radiance.
  • Change another Wayfarer's Clothes into a Water Flying Cloth.
  • Change a Medical Herb into a Final Key.
  • Change the Thief's Key into a Wizard's Ring.
  • Give one of the pilgrims the Return flag for Rimuldar.
  • Give the pilgrims 7 of their most powerful battle spells.
(We can't give the wizard his most powerful spells since he doesn't start out with any field spells, so the damage check would see the spell bits as 0 HP and not underflow. But we'll get him some levels shortly so he can deal decent damage.) A couple of the glitch steps cost the hero some max MP, but that's a small price to pay for what the glitch gives us, and the hero won't need to use much magic anyway.
The Wizard's Ring deserves an extra note: While it's certainly useful to give the pilgrims enough MP to get through the final boss rush and to recover the hero's MP so we can Heal to adjust the RNG counter, it has another important purpose, namely to shift the "parity" or position of the counter relative to the battle RNG seed. Once the boss rush starts, almost every action we can take -- either in battle or on the map -- increments the RNG counter based on the battle seed, so if the distance to our target value at some point in time is not a multiple of the battle seed, we can get stuck. The Wizard's Ring, however, lets us increment the RNG counter by 1 more than the battle seed, so we can shift into a new sequence that does allow us to reach the target.
Once all that is done, we go back into town, sell the second glitched item, buy a Wing to get to Rimuldar and some Herbs as a present to Zoma, revive our characters, and save, using Luisa since that's faster than going to talk to the king. Then we reset and create a third save file which gives us a specific random seed ($2DDE) that will bring up a good Metal Babble fight. After reloading our original game with the new seed, we equip the second pilgrim and the wizard for the upcoming Metal Babbles, then warp to Rimuldar, skipping most of the game. (Apparently there was this Baramos guy we were supposed to stop from destroying the world? Oh well, it was a stupid world anyway.)

Part 4: Rimuldar -> Charlock

Our first task at Rimuldar is to get our characters some levels so they can survive the final boss rush. Fortunately, there are Metal Babbles living in the environs of Rimuldar, and with the random seed we picked above, we can nab a couple before they get away. Note that the second pilgrim still has his Club, which we kept around while glitching items; this is needed in order for a critical hit to kill the Metal Babble, since otherwise a level-1 pilgrim's attack power is too low. (Though watching a character fail to kill a metal enemy with a critical hit can be amusing in and of itself...) We attempt to run in the second round since that gives a better RNG state than entering commands and changing the battle RNG seed.
Once we finish paging through over 8 minutes(!) of level spam, we enter Rimuldar and use the inn to fill up all the new HP and MP we have. Then we make a quick trip back to Aliahan in order to save, so we can reset and re-enable the RNG glitch. The equipment shop here sells Magic Armor which the pilgrims could use to reduce magic damage in the final boss rush, but they end up having just enough HP to survive without.
After resetting, we shuffle a few last items around and equip the hero (done here rather than before resetting since NPC movements will consume a few extra RNG outputs, so we don't have to take as many extra steps in Charlock). Then we Return back to Rimuldar and walk to Charlock Castle, skipping one encounter along the way. Before entering Charlock itself, we take a short jog around the swamp to help advance the RNG counter (swamps consume an extra RNG output per step, at a cost of less than half the time a step takes).
Inside Charlock, after skipping an encounter (and using some extra Heals to adjust the RNG state), we come across three pairs of Granite Titans. The room with the Titans has a gimmick in which the door closes behind you as soon as your party enters the room, and there are 3 forced encounters with a pair of Granite Titans each after 26, 28, and 30 more steps. Luckily, the Titans are susceptible to Defeat (maybe that's why the dialogue line says "you'll have to defeat us first"?), so we arrange for one of our pilgrims to successfully Defeat both enemies in each battle before they have a chance to attack. This is one place in which the sequential RNG output comes in useful to manipulate turn order: By forcing the RNG output to roll over right after randomizing party speed values, we guarantee that the enemies will get low speed rolls, allowing our characters to act first.
We need to skip one more encounter partway through B3. Since we also need to advance the RNG counter for the Ortega battle, we go ahead and do that here as well, with a total of 8 Heal spells and 2 Wizard's Ring uses. This takes about 30 seconds, but is still faster than walking out the equivalent number of steps.
On B4 we encounter that bane of all DW3 speedrunners, the Ortega battle. Ortega has an 88% chance of using Healall if his HP drops below half of the maximum (400), and he has 27 MP (enough for 3 Healall spells), which is why this encounter can stretch on for quite a while if one is unlucky. Fortunately, King Hydra deals 154 damage per turn with two physical attacks, so by arranging for Ortega to start the battle with low HP, we only need to hit that 12% chance once to end the battle in two turns. (A side effect of the RNG seed we use is that physical attacks always do maximum damage, which helps us out here.)

Part 5: Boss rush -> ending

The final boss rush was by far the hardest part of the route to calculate, since the RNG state at the end of each battle feeds directly into the next battle, and there are no random encounters on the final boss floor so we can't consume RNG outputs by walking around. (We also can't return to the previous floor to adjust the RNG state, since that resets the boss rush and we'd have to start from the beginning again.)
We start out facing King Hydra, who took out Ortega so efficiently a couple of minutes ago. This time, though, we get the RNG to work against him. It still takes 4 turns to take him out, mainly because he regenerates 90-109 HP every turn, which is a fair fraction of our damage output. (This is the only battle in the entire run that goes to a fourth turn. The first turn can actually be skipped, but that requires 10 heals on the map before entering the battle, which takes longer than just doing the extra turn and is boring to watch besides.) The useless Blaze spell in the third turn is to set up the RNG state properly for the fourth turn; the wizard doesn't have any useful actions which would give the same effect.
Next up is Baramos Bomus, a reincarnation of the big boss we skipped earlier. I guess some other hero took care of him? Bomus tries to destroy us with Explodet, but he doesn't get very far as we destroy him in just two turns. In the first turn, the wizard uses an Herb rather than parrying in order to advance the RNG counter; similarly to the previous battle, he has no other actions that give the same effect on RNG state.
As we approach Zoma and wade through some lag, Baramos (or at least his skeleton) comes back for more. This time he has twice as much HP and attacks for around 200 damage, but a dose of Surround and he can't hit the broad side of a barn, going down for good in three turns. Careful watchers can spot exactly where the RNG counter wraps around in turn 2.
Having taken care of Zoma's servants, we finally arrive at Zoma himself. Zoma's a pretty cold fellow, as can be seen from his blizzard breath, Snowblast, and freeze beam attacks. Fortunately, we come from the future, in which Dragon Quest VIII taught us that Nook Grass is the perfect antidote to cold. So we secretly switch our Medical Herbs for Nook Grasses and feed them to Zoma, who can't take the heat and drops dead in the second turn. (The 5 Herbs we use are the theoretical minimum; even with perfect RNG giving 255 damage from each of 4 Herbs, the total of 1020 wouldn't be enough to defeat Zoma, whose initial HP is a constant 1023.)
With Zoma defeated, we get out of the crumbling castle and make our way to Tantegel to receive our well-deserved fanfare and lovely ending music. The sequential RNG output can be seen once more here, in the straight diagonal line of tiles which disappear from the map as Charlock is destroyed.

Etc.

Route notes and scratchpad: http://pastebin.com/9Aimya4e
More details on glitches, random numbers, and other internal stuff:

Samsara: Judging.
Samsara: Impressive improvement, lovely subtitles, and a great audience reception. Accepting to Moons as an improvement to the published run!
Spikestuff: Publishing.
Spikestuff: Just an update to anyone who is wondering where it is. vaxherd has actually provided a dump with the fix, minor issue, I've been downloading it for 3 days. The other part is that the subtitles have also been taking some time, not due to trying to grab the fix, just that there's a bit to do, and make legible especially for the downloadables, hopefully, this will get done soon, just hope it wouldn't take much longer. Sorry for the delay.
Spikestuff: Update. Everything is on track again!
Last Edited by on 1/1/2022 6:13 PM
Page History Latest diff List referrers