tile-based pathfinding with dynamic terrain costs — A* isn't enough on its own

been banging my head against this for the past few weeks and finally have something worth sharing. if your game has terrain that changes cost at runtime — mud that slows enemies, fire that damages them but they'll still walk through it, roads that speed them up — vanilla A* with static weights breaks down fast and the fixes are not obvious.

the core issue: A* with a simple heuristic assumes your cost map is stable. the moment you start mutating costs at runtime (burning fields, flooding tiles, player-placed obstacles), you either re-run the full pathfind every frame which is brutal, or you cache paths that go stale and cause agents to clip through hazards they should be avoiding.

what actually helped me:

first, separate structural impassability (walls, chasms) from cost modifiers (terrain type, status effects). the former changes rarely, the latter changes constantly. cache the navigation mesh based on structural data, then apply cost modifiers only during the pathfind evaluation step. this means you only invalidate the full cache when geometry changes, not when someone drops a fire trap.

second, don't store absolute costs per tile — store a cost multiplier and a list of modifier sources. when a modifier is removed (fire burns out, effect expires), you recalculate that tile's effective cost from the remaining sources rather than trying to undo an accumulated value. sounds obvious but i spent three days debugging a cost-underflow bug caused by subtraction order.

rough code sketch in pseudocode:

class TileCostMap:
    base_costs: Dict[TilePos, float]       # terrain type base
    modifiers: Dict[TilePos, List[Modifier]]  # stacked sources

    def effective_cost(pos):
        base = base_costs.get(pos, 1.0)
        mult = 1.0
        for mod in modifiers.get(pos, []):
            mult *= mod.cost_multiplier
        return base * mult

    def add_modifier(pos, mod):
        modifiers[pos].append(mod)

    def remove_modifier(pos, mod):
        modifiers[pos].remove(mod)
        # effective_cost recalculated on next query, no manual undo needed

third — and this took me longest to accept — sometimes you don't want agents to find the optimal path. dumber enemies should take a plausible path, not a perfect one. running full Dijkstra on every cost change is correct but slow. for grunt-type enemies i now run A* on a coarser grid and only refine to tile resolution when they get within a certain range of the target. massive perf win, barely noticeable to the player.

happy to dig into the coarse/fine grid handoff if anyone's doing something similar. also curious whether anyone's tried flow fields for this use case — i've read the theory but haven't implemented one yet.