How free-form are the map changes? Do you mean opening and closing doors - or completely changing the terrain as in for example Minecraft? One option would be

How free-form are the map changes? Do you mean opening and closing doors - or completely changing the terrain as in for example Minecraft? One option would be to look for strategies that "look intelligent", instead of being perfectly optimal paths at every simulation frame. Run slow pathfinding for an enemy and store the path. Have them follow the path until they hit a player-created obstacle, and only then re-run pathfinding. Besides being faster, this could let the players use the enemy behaviour to their advantage by creating traps or such.