Curious about pathfinding logic in a game like Fire Emblem

[Wist]

I tried bugging Hextator on IRC but he wasn't responding to my gentlemanly pings.

I'm currently working on a Fire Emblem related project (which essentially involves a replication of fundamental Fire Emblem mechanics in a StarCraft map run through a custom mod). I have most of the systems I need either planned out or already in place, including robust grid and coordinate systems, but one element I haven't been able to work out an elegant approach to is pathfinding (if this is the correct word to use in this context?).

Here's what I can do so far:

If a player selects a unit, I easily can show any tiles the selected unit could move to. For example, if a unit in question has a movement range of 5, I can show the following (X is the unit and # is a valid tile):

          #
        # # #
      # # # # #
    # # # # # # #
  # # # # # # # # #
# # # # # X # # # # #
  # # # # # # # # #
    # # # # # # #
      # # # # #
        # # #
          #

If there are obstacles (such as water, cliffs, or the edge of the battlefield) I can remove those from the list of valid tiles. I can do the same if a tile is occupied by another unit (B is an obstacle, U is an enemy unit):

          B
        B B B
      # # # # #
    # # # # U # #
  # # # # # # # # #
# # B B # X # # U # #
  # B B # # # # # #
    # # U # # B #
      # # # B #
        # # #
          #

This results in the following pattern of tiles (- means a tile cannot be walked on):

          -
        - - -
      # # # # #
    # # # # - # #
  # # # # # # # # #
# # - - # X # # - # #
  # - - # # # # # #
    # # - # # - #
      # # # - #
        # # #
          #

The problem is that other tiles need to be recognized as invalid because obstructions prevent the unit from reaching them in at most five steps.

Sorry it's a bit confusing. Red lines represent possible unit paths near and around obstructions. Blue dots tiles that should not be reachable because of obstacles in the unit's paths even though those tiles don't host any obstacles themselves. I need to figure out a way to figure out which the blue tiles are in game so that I don't show them as valid target locations, producing the following tile map:

          -
        - - -
      # # # # #
    # # # # - # #
  # # # # # # # # #
- - - - # X # # - - -
  - - - # # # # # #
    - - - # # - #
      # # # - -
        # # #
          #

Maybe the following will help too. How would one emulate Fire Emblem's calculating that enemy units in the way should prevent Dorcas from walking onto tile 5 (and not putting a blue square overlay there)?

Does anyone here know how Fire Emblem figures out which tiles can and cannot be reached on any given turn, or at least a logical approach one could use to figure this out? I could brute force test every possible path, but I'd rather adopt a sensible algorithm, if anybody has any ideas? Any input, even just ideas, would be very much appreciated!

[BwdYeti]

A* pathfinding

Well for move ranges you're probably using Dijkstra's algorithm, since you don't have a target location in mind, but they're 95% the same system

[Wist]

You are the best person. I think I can get this to work, thank you so much!

[Knife]

There's a Wist in the air...