Doors

Push-open doors are becoming more of a problem than I had anticipated. The borg's movement state doesn't seem to recognize that a move command into a door didn't actually move the player, so we're getting off of our movement path by one square and getting stuck in a lot of places. We already have a check for whether FF5's internal movement flag is set after a movement command, but apparently that's not enough in this case.

My inclination is to add a check for each step to verify that we're on the square we expected to end up on, and to retry the movement if not, retaining the current limit of 200 consecutive failures before panicking. I'm worried that this is going to be a problem with transitions and cutscenes, though. We'll see what happens.

We're pathed and mapped partway through the Ship Graveyard. Karboros wasn't a problem with four monks, as expected.

Edit: Ended up changing how the pre-move cooldown works in the movement state, and our door problems are gone. Pathed through the Siren fight. Sometimes she doesn't even have time to switch form before the fight is over.

Fastidiousity

Felt like getting some of the refactoring grunt work out of the way, so I created a BorgCharacter class and gave it most of the code dealing with party members from the state machine. That cleaned up a lot of code, and it'll provide a good jumping off point for implementing the job system.

Tried the new and improved cartographer out on some of the dark, unmapped corners of the Pirate Ship and the Wind Shrine, and it works great. It's nice to see it scurrying around and hunting down unexplored bits that it used to ignore. I'll have to go back and clean up some remote FF4 maps with that sometime.

We have a few more remaining issues with the cartographer, and I'd like to take care of most of them before moving on from the Tule proving grounds.

• We're not recording gold-filled treasure chests or monster-in-a-boxes properly yet. That should be a relatively quick fix.
• Cutscenes still are ignored for the purposes of navigation unless they're our destination. At the very least I'd like to be able to manually mark a cutscene as one that repeats and moves you to a different location, so we can treat them like transitions. Without this, the cartographer can get into infinite loops, like trying to explore the wall behind the exit warp in the Wind Shrine and getting warped out over and over again.
• Cutscenes are still sometimes recorded as starting on the wrong square. I might leave this one for now and build a test case for it when it becomes too annoying.
• Currently, NPC avoidance assumes that we never put ourselves into a situation where we've hopelessly pinned an NPC between ourselves and our goal. This is generally true during normal gameplay, but the cartographer may end up exploring itself into just such a situation, because it didn't have the problem destination in mind until the NPC was already pinned. My inclination is ignore this problem if we can finish the map by just restarting and rerunning the cartographer when it gets stuck. If that's not good enough, I'll teach it to try to reroute around the NPC if it has to wait more than a certain number of frames.

Due Process

I went back and made sure the changes we've made to code so far still work with the FF4 borg. Getting menu and cutscene handling to work with both games is going to be tricky. I don't want to just add lots of configuration flags that determine how each fiddly bit of code behaves, but the unfortunate truth is that every game is going to handle these sorts of things a little bit differently.

Also looked at open source emulators for other consoles that I have games for. Once I'm done with the three Final Fantasy games on the SNES, I think I'll want to switch genres and try working in a different environment.

Transitions and Cutscenes and Menus, oh my!

I looked up / ferreted out enough memory keys to get the basics of our battle code up and running. Targeting specific enemies and using skills isn't ready yet, of course, but we have enough to Defend instead of Attack when the WingRaptor covers itself.

I also confirmed some of my suspicions about how vehicles are handled by FF5, and I have a navigator command that travels to and boards a shore-docking vehicle.

I changed the cartographer code to use transitions to reach sections of the current unfinished map. This should help avoid prematurely marking maps as finished and giving up on sections we know how to reach. I'd love to try it out, but the cartographer continues to have issues, and Tule seems to be an excellent proving grounds for the myriad problems with cutscene detection, cutscene / transition, and NPC avoidance. The borg is also convinced that we start a screen transition - and don't stop it - for as long as the menu is open.

I'd like to start making some videos of the borg in action. Going to do some investigation in producing Youtube videos, so development will slow down a bit.

No Traffic Regulations Necessary

I'm pretty sure that the Boco used during the intro of Final Fantasy 5 isn't actually a vehicle, and neither is the boat inside the Torna Canal. This was throwing me off for quite a while trying to figure out which memory key stores the current vehicle. I'm betting Boco the vehicle isn't actually used until things open up at endgame.

Anyway, the walking/boat barriers thing is sorted out until we get the hiryuu, and then one minor code change and we'll probably be good after that. This allowed me to map and path up to the WingRaptor fight. When the cartographer got to this fight, it had understandably already been through enough fights to level up a bit, and we actually killed it before it ever covered itself with its wings. Go straight to the boss without leveling up, though, and just mashing A to get through the fight isn't enough.

Out of curiosity, I tried using the dumb timing interval I set up for the Mist Dragon from FF4, just to see what happens. The party actually stopped attacking at about the right time, but waited way too long to start attacking again, and the bird had covered itself again by the time they restarted. Well, fair enough. We'll add some conditionals to our battle strategy and call it good. We've made it to the tier 1 jobs.

I told myself I was going to completely refactor how characters are handled once I got this far, and then build out support for the job system on top of it. Now that I'm here though, I think I should stick with the development strategy I used for FF4. When I started this project, I only wrote enough code to get past the problem right in front of me. This would be a poor strategy for some software projects, but I want to continue seeing where it takes this one, for the sake of experience.

This philosophy often means using some pretty ugly code for a while. But it also means that ugly code gets prettier because it was insufficient, or because it needed to be generalized to solve a related problem. So far, the result has been progressively cleaner code that does exactly what I need it to, without any unused edifice that I built because I thought would be useful later.

So I'm just going to put some manual menu commands into my command queue and turn everybody into Monks. This will almost certainly be enough until the Liquid Flame fight. Expect a shameful battle report when I get there.

Reinterpretations

Mapped and pathed through the Seaside Cave today. The cutscene detection definitely needs some fine tuning; a lot of regular transitions are getting recorded as cutscenes, and sometimes the cartographer's off by one square on the start point of a cutscene. There's also a few cliff edges that Boco was convinced he could walk through but obviously couldn't. Huh. Will need to go back and investigate that later when I'm not riding a bird and see if that's one of the places where the map is broken.

Made it all the way out to where we're driving the pirate ship, and promptly got stuck. It turns out that open ocean squares are all zeroes on their barrier bits, which so far we've been interpreting as no passage in any direction.

So that sucks.

It'll take some more investigation, but I believe barrier bits have an entirely different meaning on the overworld map. This will mean more code that's likely to be game specific, but if my guess is right, it will also give me the information I need to handle entering/leaving the ship. It looks like barrier bits are always 1 on land, always 0 in open ocean, and switch on the coastline. We'll have to allow stepping over that barrier from land to sea if a boat is there, and from sea to land if the land square can hold an ambulating party.

Definitely not getting to tier 1 jobs this weekend. Gonna take it easy for the next week.

Mapmaking

The cartographer for FF5 is (mostly) up and running. I've mapped out the starting area of the overworld and the Tycoon meteor site. Mobile/stationary NPC detection still isn't quite right, and I still haven't written the code to track GP treasure chests yet, but I'll get to those when they become issues, which will probably be in the village of Tule for both.

I've come up with a way to track barrier information in the atlas that I think I'll be satisfied with. It's still not quite as clean looking as having only one character per square, but unexplored squares and explored no-barrier squares will just have spaces for their barrier byte, which makes the map quite readable.

Here's a cutout of the map the cartographer made of the Tycoon meteor site.

                                                                              #0#0           
          #0#0#0#0#0#0#0#0#0                                                #0_ _ #0       
        #0_7_7_7_7_7_7_7_7_7#0                                              #0_ _ #0       
  #0    #0_D. . . . . . . . _7#0                                            #0_ _ _ #0     
#0_E#0#0#0_D. _A#0#0_9. . . . _7#0                                        ? _ _ _ _ #0   
#0_ _7_7_7. _A#0    #0_9. . . . #0                #0  ?               ?   #0_ _ _ #0 
  #0#0_9. . #0        #0. . . _A#0              #0_ #0, ? ? ? ? ? ? ? , #0_ _ _ #0
      #0. . _7#0#0    #0. . _A#0                #0_ _ . #0, , , , , #0. _ _ _ #0
      #0_9. . _7_7#0  #0. _A#0                  #0_ _ _ _ . . . . . _ _ _ _ _ #0
        #0#0_9. . _7#0#0. #0#0#0#0#0      #0    #0_ _ _ _ _ _ _ _ _ _ _ _ _ _ #0
            #0. . . #0#0. _7_7_7_7_7#0  #0_7#0#0#0_ _ _ _ _ _ _ _ _ _ _ _ _ _ #0
            #0. . . #0#0_9. . . . _E#0#0#0_D_7_7#0_ _ _ _ _ _ _ _ _ _ _ _ _ _ #0
            #0_9. _A#0  #0#0_9. . _ _7_7_7. _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ #0
          #0#0#0. #0        #0_9. . . . . . _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ #0
        #0_7_7_7. #0          #0_9. . . . . _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ #0#0#0#0
          #0. . . #0            #0#0#0#0#0#0#0#0_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _7#0
  ? #0#0#0. . . . _7#0                          #0_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _7#0
? >7_7_7_7. . . . #0                            #0_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ #0#0_9. _7#0
? + . . . . . . . . #0                          #0_ _ _ _ _ _ _ _ _ _ _ _ _ _ #0    #0_9. #0
  ? #0_9. . . . . . #0                          #0_ _ _ _ _ _ _ _ _ _ _ _ _ _ #0      #0. #0
      #0. . . . . . #0                          #0_ _ _ _ _ _ _ _ _ _ _ _ _ _ #0      #0. #0
        #0#0#0#0#0#0                              #0_ _ _ _ _ _ _ _ _ _ _ _ #0        #0. #0
                                                    #0_ _ _ _ _ _ _ _ _ _ #0          #0. #0         
                                                      #0#0#0_ _ _ _ #0#0#0            #0. #0         
                                                            #0#0#0#0                    T0         

Again, not gorgeous, but far better than I thought it would have to be. We'll see how far our current interpretation of map data gets us.

Had to refactor the cutscene state to get us past the part where we name the main character; mashing A or B isn't enough. Since this is the only place in the game where we choose a name that I'm aware of, I wasn't able to come up with a good memory key to tell when we're on the name choosing screen. So the "ChooseName" looks for the X coordinate of the finger cursor and chooses what buttons to press from that. Very specific to this game, but it works.

Should be able to get some mapping and the beginnings of a command queue done at this point. With any luck, before the end of the weekend the borg will make it to the point where we have to manage job assignment and abilities.

Feeling a Little Silly

While I was working on refactoring isLayerCompatibleWith(), I started looking at FF4 layer numbers and noticed what is now some very obvious bit flags in local map layer numbers:

• Bits 1 and 0 are our two layer bits.
• Bit 2 is the bridge flag.
• Bit 3 is the save point flag.
• Bit 4 is the transition flag.

I could probably sort out bit flags in the 2-byte overworld tiles for things like which vehicles can pass through which squares and which can land in which squares, but for the moment I have no compelling reason to do so. I'll probably give it a shot when I try to sort out vehicles in FF5.

So the downside is that I looked dumb on the internet, although nobody's watching at the moment. The upside is I know a bit more about how mobility layers work, I got to simplify some important code, and may end up not needing to make isLayerCompatibleWith() game-specific. Yet. We still need to look for barriers between squares, but we can turn the check for that on and off with some configuration.

Oh, that's right, I didn't blog about that.

I've got a bunch of functions that just compare a location in the game's memory against a given value to see whether the game is in a certain state. isInCutscene(), isMoving(), and justOpenedTreasure() are a few examples. The logic for these functions will necessarily different for each game. We could build some C++ class that reads from a config file and interprets the logic needed for each method, and that would work, but I'd really rather not build a makeshift logic interpreter for this project, and it would slow down some functions that may actually need to run quickly.

Enter boost::function and boost::bind. Between FF4 and FF5, I really only need 3 operators for these functions: ==, !=, and <, and they're all comparing a named memory byte against a specific number. So I made three functions, one for each operator, used boost::bind to build a function with the memory key name and expected value from the config file, and saved that as a boost::function. It works great.

Mashing a Square Peg Into a Round Hole

Figured out a ton of memory keys for FF5. Still haven't sorted out vehicle stuff, and I haven't done anything with jobs or character stats because I know I can look those up. But we have more than enough information to start retooling code and get the cartographer running.

The biggest remaining question is how to minimize code that only applies to one game, and organize the game-specific code we're forced to keep around. I'll probably start working on that this weekend.

Understanding Basic Navigation in FF5

Final Fantasy 4's map data lent itself fairly nicely to reverse engineering. On local maps, each square has a 1-byte number representing the square's movement layer, and there are some very basic rules about which layers connect to which; I went into more detail on this in the Traffic Jams post. Overworld map data is similar, but there's a lot more values, and different vehicles have different rules for whether they can enter each square.

That's not actually the whole story; each overworld map square actually has 2 bytes of data, but I only found the 2nd byte useful for discerning whether vehicles could land in particular squares.

Final Fantasy 5 is a bit more involved, although perhaps not as much as I initially feared. I made a couple of half-hearted attempts at figuring out memory keys for navigation 2 weeks ago, and was dismayed by the results; it's definitely using a different system than FF4. Each map square uses 2 bytes of data, and so far it doesn't appear to be layer-based. The good news: after taking another shot at deciphering map data, it looks like it's 16 bits of flags, and I may have already sorted out the most important bits.

7E10FA - current_map_square_type

This memory key stores info on the square we're currently standing on. There's data right around this on neighboring squares, which is great; building an atlas just based on reading the square we're standing on is possible, but it would take more code. Here's some sample values broken down into bits. Note that I'm presenting these as big-endian, not little-endian like they are in memory.

Samples taken from Tule Village.

3969 - 0000 1111 1000 0001 - regular walkable square

3843 - 0000 1111 0000 0011 - flowers, square just outside gated area, still can walk anywhere

3978 - 0000 1111 1000 1010 - square just inside gated area, still can walk anywhere

1930 - 0000 0111 1000 1010 - gated area, fence to north

3466 - 0000 1101 1000 1010 - gated area, fence to west

1418 - 0000 0101 1000 1010 - gated area, fence to north and west

2442 - 0000 1001 1000 1010 - gated area, fence to south and west

2954 - 0000 1011 1000 1010 - gated area, fence to south

3722 - 0000 1110 1000 1010 - gated area, fence to east

1923 - 0000 0111 1000 0011 - standing in front of Pub sign (can't walk north)

3971 - 0000 1111 1000 0011 - standing just to right of a building.

3977 - 0000 1111 1000 1001 - partly occluded by chimney / tree / side overhang

3851 - 0000 1111 0000 1011 - mostly occluded by roof of building
0 - 0000 0000 0000 0000 - obstacle.

I was very excited when I started seeing the bit breakdowns for these. Bits 11 through 8 seem to be exactly what I need: 1 if passable to the neighboring square, 0 if barrier, in the order NSWE. The order of directions struck me as a little odd, since for both FF4 and FF5 they seem to usually do directions in the order NESW, but whatever. I'm also glad that generic obstacles are still all zeros, and that treasure chests seem to all be on obstacles. Two more things I don't have to change.

My square->isLayerCompatibleWith(other_square) method is going to have to be a bit more complicated for FF5. We can't just compare numbers; we have know how the two squares are oriented and make sure the relevant passability bit is 1 in both squares.

The other 12 bits of map data obviously mean something, but I haven't sorted out what yet, and probably won't have to for a while. Some samples from the overworld map provide some clues.

Samples taken from overworld map:
12111 - 0010 1111 0100 1111 - grass
53071 - 1100 1111 0100 1111 - forest
61263 - 1110 1111 0100 1111 - desert
27215 - 0110 1010 0100 1111 - shore, can't walk south or east
26191 - 0110 0110 0100 1111 - shore, can't walk north or east
61252 - 1110 1111 0100 0100 - mountain
25212 - 0101 0011 0000 0100 - coast, land to west
26748 - 0110 1000 0111 1100 - coast, land to north
61261 - 1110 1111 0100 1101 - meteor
58437 - 1110 0100 0100 0101 - cave entrance 

These help confirm my analysis of bits 11-8, although I'm not sure about those coast measurements; I'll need to take more data while I'm in the boat. It also looks like a square can't be walked on if its two least significant bits are 0. Might be some FF4-style layering in here after all. That and the passability flags should give me enough to get the cartographer running. I'll figure out vehicles later.

My rule of development on these projects has been to write just enough code to solve the problem right in front of us and then see how much farther the borg gets. Rinse, lather, repeat. I know that my understanding of map data will change as time goes on, but this is good enough for now, and the point in time where it's not good enough is exactly the point that the cartographer will put me in a position to learn more. That's why I'm not testing my assumptions out; we'll find out soon enough how sound they are.

Starting Out on FF5

In some ways, building the borg for FF5 is going to be a lot easier. Most of the important code for the FF4 will drop right in place, provided I find the right memory keys to look at. I've already written the code that's going to save me the most time; namely, the Cartographer and Navigator states. I'll continue to fine-tune these, but I should be able to get started with commands like "GoToCutscene:Bartz Saves Lenna from Goblins" in a week or so. Battle handling will be a bit different, but we should be able to get through a good portion of the game with careful job selection and mashing A in fights.

I think the problems will actually be strategic ones. Not that FF5 is harder; indeed, with the job system, there's far more opportunities for abusing the system. No, the problem is that in Final Fantasy 5, your choices for job development early on heavily influence your battle strategy throughout the game. Not so in Final Fantasy 4, where each character is strapped in to a specific set of skills. Coming up with ways to express job development and battle strategy in a way that doesn't make me rewrite half the command queue if we run into a boss fight we're not prepared for is going to be a challenge. On the other hand, I'd prefer not to just pick a bonehead strategy (e.g. everyone is a Monk for the whole game) for ease of maintenance. I'd like to tell the borg to use some of the cooler skill combinations, most of which require some up front investment in job growth.

Fun! We'll see what happens with the Cartographer this week. Here's my current development to-do list:

• Cartographer for FF5:
• Figure out enough memory keys for the Cartographer to get started. Mobility, transitions, basic cutscene detection, treasure, current map.
• Refactor isLayerCompatibleWith(). Come up with a good way to organize game-specific code and keep it as thin as possible.
• Refactor BorgMapSquare saving/loading itself.
• Try out the Cartographer. Run it until it gets stuck and implement what it needs next.
• Proper monster-in-a-box reward detection.
• Proper detection of GP in a treasure chest.
• Include cutscenes in navigation considerations.
• Is there a way to tell from memory whether a cutscene is repeatable, one time, or repeats on certain conditions? Or do we just have to record what kind they are manually?
• Repeatable cutscenes should be treated similarly to transitions.
• Don't mark a room as finished if some items of cartographical interest can be reached through transitions.
• Add a Navigator command that walks to a square on the current map, using transitions to get there if necessary.
• Move character stuff into a class.
• Add a Recovery interrupt.
• Add support for the job system.
• Rewrite battle handler to use the skills a character has instead of hard-coding the list.

More important stuff is generally at the top, but I work on whatever I feel like working on. This is for fun, after all.

Two battle bug fixes

While I was testing out the new Zeromus strategy, I noticed that TimesPerBattle bug happening again, and finally figured out what was happening. It has nothing to do std::map or the used_commands cache. The class I'm using to store battle command information has two constructors, and one of them doesn't initialize the boolean that determines whether the command has been chosen for execution. Fixed!

I also had a couple of issues with party members missing the item/spell they were supposed to use and choosing something else instead. I was having this issue earlier in development and cranked up the cooldown between button presses, but apparently it still happens every once in a while. Instead of increasing the cooldown even more, I chose to rewrite the code that chooses button inputs to only queue one button press at a time while choosing a spell or item to use, and then re-evaluate what to do after each press. That prevents the occasional miss, and it also lets me turn the cooldown way down. The borg's battle commands are flying by again.