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!

Ambassador, Experienced player (695)
Joined: 7/17/2004
Posts: 985
Location: The FLOATING CASTLE
Derakon wrote:
Speaking as someone who hasn't played DQ3 before, there were some interesting parts to this run
A good commentary makes RPG runs more interesting to watch. Especially since most casual viewers just watch on youtube. Translating the info from the submission text to 40 minutes of short subtitles would take some time but add a lot of entertainment value.
Player (134)
Joined: 1/18/2016
Posts: 17
TheAxeMan wrote:
Derakon wrote:
Speaking as someone who hasn't played DQ3 before, there were some interesting parts to this run
A good commentary makes RPG runs more interesting to watch. Especially since most casual viewers just watch on youtube. Translating the info from the submission text to 40 minutes of short subtitles would take some time but add a lot of entertainment value.
I could look into doing this (and I agree it would help viewers not familiar with the game), but I'm not too familiar with video processing tools; is there a particular format I should use?
Dwedit
He/Him
Joined: 3/24/2006
Posts: 692
Location: Chicago
Is there a name for DW2 that freezes the RNG at the other value?
Player (134)
Joined: 1/18/2016
Posts: 17
Dwedit wrote:
Is there a name for DW2 that freezes the RNG at the other value?
cAj/Fast (among others) should do it. Quick and dirty Perl script to list all the possibilities up to 4 characters: http://pastebin.com/LzHxhTBa
Dwedit
He/Him
Joined: 3/24/2006
Posts: 692
Location: Chicago
Anyone know where I can find the TAS that was done of the JP version of the game? I'm having a hard time finding it.
Ambassador, Experienced player (695)
Joined: 7/17/2004
Posts: 985
Location: The FLOATING CASTLE
vaxherd wrote:
is there a particular format I should use?
Since you are on FCEUX the fm2 subtitles would be best. You can just drop them in with a text editor then update your submission. There is a format spec on the emulators page but it is probably easier to look at an example fm2 with subtitles. The publishers have tools to convert the fm2 subtitles into video and youtube subtitles.
Player (134)
Joined: 1/18/2016
Posts: 17
Dwedit wrote:
Anyone know where I can find the TAS that was done of the JP version of the game? I'm having a hard time finding it.
If you mean pirohiko's Dream Ruby TAS, I think this is it: http://www.nicovideo.jp/watch/sm3134444 It uses Fighter crits and takes advantage of how the RNG counter advances every frame in DQ3 while a menu is open (as opposed to DW3, in which it doesn't so your battle RNG manipulation options are much more limited).
Player (134)
Joined: 1/18/2016
Posts: 17
TheAxeMan wrote:
Since you are on FCEUX the fm2 subtitles would be best. You can just drop them in with a text editor then update your submission. There is a format spec on the emulators page but it is probably easier to look at an example fm2 with subtitles. The publishers have tools to convert the fm2 subtitles into video and youtube subtitles.
Ah, I see, thanks. I'll get on that and update the submission ASAP.
Editor, Skilled player (1998)
Joined: 8/25/2013
Posts: 1198
Giving this a borderline meh. The leveling up section is quite boring, but the rest of it is really good.
effort on the first draft means less effort on any draft thereafter - some loser
Player (134)
Joined: 1/18/2016
Posts: 17
Okay, I've got subtitles written, but it looks like I can't update the submission anymore -- can anyone help with that? [Edit] Here's the updated movie: http://tasvideos.org/userfiles/info/28706285680998942 [Edit 2] The submission is updated. Thanks, Samsara!
Site Admin, Skilled player (1234)
Joined: 4/17/2010
Posts: 11251
Location: RU
Spike, why are you claiming 3 submissions at once? What's the point? You don't want occasional people who might occasionally have time to even touch it while you're dealing with other 2?
Warning: When making decisions, I try to collect as much data as possible before actually deciding. I try to abstract away and see the principles behind real world events and people's opinions. I try to generalize them and turn into something clear and reusable. I hate depending on unpredictable and having to make lottery guesses. Any problem can be solved by systems thinking and acting.
Dwedit
He/Him
Joined: 3/24/2006
Posts: 692
Location: Chicago
So how well would the TAS's route translate into play on a real console? I could see that the basic RNG freezing stuff would work fine, but timing the heal spells to avoid encounters seems hard to do.
Player (134)
Joined: 1/18/2016
Posts: 17
Dwedit wrote:
So how well would the TAS's route translate into play on a real console? I could see that the basic RNG freezing stuff would work fine, but timing the heal spells to avoid encounters seems hard to do.
Encounter avoidance is easy as long as you know where the RNG is, which in turn is just a matter of counting steps (and not bonking -- though bonking in dungeons is fine as long as you do it a multiple of 8 times, to get the frame counter back in sync for overworld and town RNG). This is the same reason things like Metal Slime farming near Dhama work. The catch is that to know where the RNG is after a battle, you also need to know what the battle RNG seed is, and there's no way to change that outside of actually taking a turn in battle -- so a single input mistake will throw everything off, and you can't even reset to get back to where you were before. That said, attempting to run doesn't change the battle seed, so as long as you have a way to set up the battle seed ahead of time, it might be possible to make use of seed lock in an RTA, if that's what you're asking. If you mean "could this TAS be console-verified", I'm pretty sure it could, but it would almost certainly need tuning because DW3 is only loosely interrupt-locked and it desyncs easily (especially with message boxes).
Post subject: Movie published
TASVideoAgent
They/Them
Moderator
Joined: 8/3/2004
Posts: 14776
Location: 127.0.0.1
This movie has been published. The posts before this message apply to the submission, and posts after this message apply to the published movie. ---- [3093] NES Dragon Warrior III "item glitch" by vaxherd in 41:09.52
Joined: 2/21/2008
Posts: 255
I looked at the subtitles file to see if there were any subtitles during the 8 minutes. I have trust issues...
"The guy was fatally injured and wants to be covered by God's tears (rain) before he dies. God is too busy to bother because it wastes frames." Frames 16:26
Joined: 4/2/2014
Posts: 32
Just posting to say this was a very enjoyable TAS. Liked the commentaries, clear explanations.
alt: Froggy25
Player (134)
Joined: 1/18/2016
Posts: 17
Mantidactyle wrote:
Just posting to say this was a very enjoyable TAS. Liked the commentaries, clear explanations.
Glad you liked it! The TAS was fun to make, and if the result is fun to watch, that's all I can ask for.
Dwedit
He/Him
Joined: 3/24/2006
Posts: 692
Location: Chicago
In case anyone missed it, Vaxherd also did a NON tool-assisted version of the run. Time is 45:46. https://www.twitch.tv/videos/151133045
Player (134)
Joined: 1/18/2016
Posts: 17
And at some point (in my *cough* copious free time) I need to figure out how to make myself a TASBot so I can get the TAS to run on console -- there are definite timing differences (which made turning the TAS into a realtime run quite, uh, interesting).