Step Routes

A new version of this site is currently under development. It is taking me much longer to develop that I initially hoped. Until then, you can play around with the beta versions of the step routes at https://www.aexoden.com/tmp/ff4-beta.

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.

- 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.

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.

- 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.

Route | Spoony Version | Maximum Steps (per area) | Class | Status |
---|---|---|---|---|

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 |

Route | Spoony Version | Maximum Steps (per area) | Class | Status |
---|---|---|---|---|

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.

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:

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.

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