Final Fantasy IV Information
Step Routes

Jason Lynch <jason@calindora.com> (Aexoden)

Introduction

This page documents the current state of my research into generating step routes for Final Fantasy IV. The instigating reason for this research was a desire to optimize the route taken in my tool-assisted speed run of the game. However, a side effect of this research is the ability to generate step routes for regular speed runs, as well.

For the uninitiated, a step route is a series of extra steps or alternate paths taken while running a game with the goal of decreasing the total amount of time the run takes. This page provides ready-to-use step routes for the original US SNES release of Final Fantasy IV (originally released as Final Fantasy II). These routes have been generated by a piece of software I have written called Spoony.

News

2016-11-26
Added routes for Octomamm%. The current routes assume you skip Mist and Kaipo, and pick up the Darkness sword. Other routes may be added if they prove to be more efficient.
2016-10-21
I have begun implementing fixes for the problem of twin seeds. Twin seeds will be distinguishable before they take extra steps, but it may still take paying attention to the exact formations.
2016-10-09
A general overhaul of the site is in progress. New routes have been generated for all categories by fcoughlin's optimizer, and a new warp has been added to the Castle of Dwarves.
2016-03-06
I have begun integrating routes generated by fcoughlin's optimizer into the site. Some of these routes are not properly credited as spoony was able to slightly optimize the step layout (to favor fewer locations with steps).
2016-01-11
The Any% Yes64 routes have been slightly changed. Specifically, the black chocobo landing has moved down three tiles in response to feedback from runners. The routes and tutorial have been updated accordingly.
2015-10-27
I have finished regenerating the routes with Spoony 0.0.7, which uses updated encounter times based on accurate back attack probability calculations provided by Myself086. Further passes of the optimizer will improve some of these routes slightly.

Tutorial

A complete tutorial is available to explain all of the various screens you may be expected to take extra steps on. Please read it completely before using any of these routes, as there are several significant differences from the previous routes you may have been using. There are also some potentially confusing areas, so being familiar with everything in advance will reduce the risk of making a mistake.

Resources

Tutorial
This guide explains most of the information needed to successfully use a step route. (It doesn't say much about any of the specialized routes, though.)
seed-step-list.txt
List of encounter steps by seed. Helps you to identify your seed (use with the maps in the tutorial).
seed-step-list-sorted.txt
List of encounter steps by seed (sorted by the first step). Probably slightly easier to use than the previous link, but functionally identical.
octomamm-seed-step-list.txt
List of encounter steps by seed for the Octomamm% route. Use the maps in the tutorial, but add 5 steps to steps before Kaipo and add 7 steps to steps after Kaipo.

General Routes

RouteSpoony VersionMaximum Steps (per area)ClassStatus
Paladin% v0.0.7 256 Optimal Complete
Any% Yes64 v0.0.7 256 Optimal Complete
Any% No64 (Edge+Drain) v0.0.7 256 Optimal Complete
Any% No64 (Edge+Excalbur) v0.0.7 256 Optimal Complete
Any% No64 (Rosa) v0.0.7 256 Optimal Complete

Specialized Routes

RouteSpoony VersionMaximum Steps (per area)ClassStatus
Pre-Mist Clip v0.0.7 256 Optimal Complete
Octomamm% (Cecil+Kain+Darkness) v0.0.7 256 Optimal Complete
Any% No64 (Rosa) [50 Elixir] v0.0.7 256 Optimal Complete
Any% No64 (Edge+Drain) [To Giant] v0.0.7 256 Optimal Complete
Any% No64 (Edge+Excalbur) [To Giant] v0.0.7 256 Optimal Complete
Giant to Zeromus v0.0.7 256 Optimal Complete
Paladin% Single Segment v0.0.7 256 Near Optimal Complete
Any% No64 Single Segment (Edge+Drain) v0.0.7 256 Partially Optimal Complete
Any% No64 Single Segment (Edge+Excalbur) v0.0.7 256 Partially Optimal Complete
Any% No64 (Edge+Drain) Marathon Safe v0.0.7 256 Optimal Complete
Any% No64 (Edge+Excalbur) Marathon Safe v0.0.7 256 Optimal Complete
Any% No64 (Edge+Excalbur) Marathon Safe Extra Bosses v0.0.7 256 Optimal Complete
SFC Any% v0.0.7 256 Optimal Complete
SFC Any% (Toru_1988) v0.0.7 256 Optimal Complete
Unprecedented Crisis v2.1 Any% No Major Skips v0.0.7 256 Near Optimal Complete
Unprecedented Crisis v3.1 Any% No Major Skips (riversmccown) v0.0.7 256 Near Optimal Complete
Unprecedented Crisis v3.1 Any% (Mist Clip%) v0.0.7 256 Near Optimal Complete
The Darkness Within v1.07b Any% v0.0.7 256 Near Optimal Complete

If you do use one of these routes and something goes wrong, please let me know and link me to a video so that I can attempt to investigate the problem. It could simply be a mistake in execution or a misinterpretation of the instructions, but it could also be a bug in the route generator, an error in my source data, an error in the code used to generate the route summaries, or simply bad wording on my part. That said, at this point I am relatively confident that the route data itself is correct, and that any errors are most likely mistakes in execution or errors in the route summaries. At this point, I am relatively confident that the routes are 100% correct.

Theory

Final Fantasy IV uses a relatively simple system for determining when encounters occur. There are 256 possible seeds (which aren't technically seeds in the typical RNG sense, but that's more or less irrelevant for our purposes). For any given seed and encounter rate, the step numbers where encounters occur is fixed. By following the path through the game, we can determine exactly when encounters will occur and what formations they will be.

There are three primary ways we use extra steps to decrease the total duration of a route:

Fewer Encounters
By taking extra steps in areas where the encounter rate is zero (or simply lower than the next area), we can directly skip encounters that we otherwise would have had to run from.

Faster Encounters
Not all enemy formations are created equal. We can take extra steps to move encounters from one area to a different area. Since enemy formations vary by room, we may be able to trade a longer encounter for a shorter one. (Average encounter times during the game range from 5.5 seconds to over 21 seconds, if you account for potential healing time.)

Guaranteed Encounters
One critical aspect of the No64 routes is that late in the game, a so-called grind fight occurs. This fight requires finding a particular enemy formation. By manipulating our steps throughout the game, we can ensure that this formation appears exactly when we need it to. This saves us from a potentially length save and reset cycle or from walking around aimlessly trying to find the needed formation.

All of this sounds wonderful, of course, but optimizing the routes is a difficult problem with an incredibly large search space. Without vast simplification, an exhaustive search of all possibilities is completely impossible. The current version of Spoony uses a stochastic optimization algorithm called ILS (iterated local search) to optimize the routes. Because of this stochastic nature, it is not guaranteed to produce truly optimal routes.

Another option is to use a dynamic programming approach to take advantage of the fact that at any given point in the run, there are only a few (on the order of one thousand) reasonable possibilities for the current state. It remains me to be seen whether this technique will be applicable to the much more complicated TAS routes, but it works wonders for the regular routes.

Until I find the time and motivation to rewrite Spoony to use this method, I am using an optimizer written by fcoughlin to generate the initial version of the routes. The optimizer appears to have some minor bugs that cause it to generate slightly suboptimal routes in some cases. Some of these may remain, but many have been optimized away by Spoony's iterative optimizer. In any case, the routes are much closer to optimal than before using his optimizer, so be sure to shower him with praise.

I'd also like to take this moment to thank Myself086 for his instrumental work in the development of FF4 step routes. His pioneering work also used a truly optimal solver, though it operated on a simplified model that didn't take individual encounter times into account and did not optimize the final descent. His routes were originally used to seed this site with good routes, and many still may remain in some form, especially in the Yes64 category.

Finally, the source code to Spoony is available at https://github.com/aexoden/spoony. I don't consider myself a particularly great C++ programmer, so I am always looking for suggestions on how to improve the code or algorithms.

A major rewrite of Spoony is planned (and is, in fact, the next project on my plate) to incorporate several features missing from the current iteration: a dynamic programming-based optimizer to generate truly optimal routes, support for arbitrary world map save/reset cycles for TAS purposes, different encounter timings for different parties, more complicated step patterns (such as the three steps taken under the stool in Cecil's room), and more.

Contact

If you have any questions, comments, suggestions or any other feedback, please send me an e-mail or message me on Twitch.