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:
- http://pastebin.com/PVzs5a4A (Dream Ruby glitch and dreams of ACE)
- http://pastebin.com/WKQ9A21a (RNG details)
- http://pastebin.com/FEXT7S3F (partial memory map)
- http://pastebin.com/LCzssawF (list of BRK functions)
Samsara: Judging.
Samsara: File replaced with a version that adds FCEUX subtitles.
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!