Pretty much the best way to do it would be to set the terrain pathfinding in stone when the map is generated and not have it "update" based on the terrain height changes. This is what happens with Age of Mythology. Sometimes the flattened terrain would create little cliffs around some of the edges that would normally cause passability issues, but this should be ignored by the pathfinder.