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.

Traffic Jams

Results of trial run: Pathing/routing failure.

Details: This is where the borg got stuck:

 

The obvious problem is that our party is trying to walk North, and we've managed to pin an NPC between us and the stairway to the North. However, to really understand everything that's going on here, you're going to need to know more about how FF4 maps and mobile NPCs work.

Every map in FF4 that isn't an overworld map has a byte of layer information for each tile of the map. This layer info helps the game know which tiles you can walk on and when. To help visualize this, here's a picture of the save room in the Antlion's Den:

 

And here's an ASCII representation of the movement layers of that map:

                                 
   ###                           
  #,,,T#                         
 T,,__,_#                        
 #,,##_#                         
 #,##._.#                        
 #,.....T                        
  #.#.#.#                        
  #..S..#                        
  #.#.#.#                        
  #.....#                        
   ##.##                         
     +                           
                                 

• Pound signs (#) are layer 0 - obstacles. These are never passable under any circumstances. The capital Ts are actually layer 0 as well, but I've marked them differently because they contain treasures.
• Periods (.) and commas (,) are layers 1 and 2 respectively. Both can be walked on, but you can't step directly from layer 1 to layer 2 and vise versa. To get between them, you need to step onto layer 3, which is represented here by underscores (_). Layer 3 acts as a connecting layer - you can always step on and off of it.
• Save points (S) are layer 11, but they are essentially always accessible.
• Layers 17 and 19 represent transition squares - if you step onto one of these, you'll end up on a different map. I've chosen to mark these with plus signs (+) and greater than signs (>) respectively. Layer 17 is only accessible from layer 1. Layer 19 can be reached from anything.
• There's one other layer, layer 5, that acts as a bridge layer. You can always step on a bridge layer from layer 1 or 2, but when you leave the bridge you have to step off onto the same layer you entered on. This allows bridges that can be walked over or under, with different rules for where you can walk for each.

So that's how the movement rules work.  Except that that's only how they work for the player, which is where our movement bug comes in.

When the borg chooses a path to a destination and starts moving down it, at every step it checks for NPCs in the way. If someone's in the way, it checks to see if the NPC would get pinned in the players path if we took the next step. If so, it politely waits until the NPC moves out of the way before moving forward. Without this politeness, all too often the borg would get itself into situations like this:

Our destination is the square the NPC is standing on, they have no way to get out of the way, and the borg doesn't know how to solve the situation. The borg eventually gives up and panics.

The problem the borg ran into in this last run is that NPCs don't have the same movement rules as the player does. NPCs are restricted to either layer 1 or layer 2; they can't transition to any layer other than the one they started on, including layer 3. So when you have a map like the top floor of Summonville, whose movement layers look like this:

             ########                  
        #####........#                 
       #.......#####.##                
      T........#   #...#               
    ##..######>#   #...##              
   #...#     #.#######...#             
  #....#     #.......#...#             
  #...#       ######.###..##           
   #.#              T  #....#    
   #_#                 #....#    
   #.T####              ##.#           
   #......#####          #_#           
    #..........#     ####T.#           
    #..........#    #......#           
     ###....>..#   ##......#           
        #......####>#......#           
         ##.####....##.####            
          #_####....##_#               
          #.............#              
           ###.........#               
             #........#                
              ####T###              

...there's a few opportunities scattered about for the borg to pin an NPC in a place that it believes the NPC can escape.

Solution: The borg method that looks for a way for an NPC to escape the player's path, pathToAvoidPlayer(), now starts with all layer 3 tiles on the current map blacklisted. This gets us 99% of the truth for NPC mobility, and should help us avoid any more pinned NPCs.