•Pre-baked node network: When the map is created the world can be broken into chunks, and each chunk can have its exits and entrances mapped. When a chunk is updated, such as when a wall is built, only that chunk's network needs to be updated.
•Staged Pathfinding: Running a path over the whole map, cell for cell, would take a lot of time, instead you would pathfind over the larger chunk network, which maps all the connection between chunks, and then only run an intra-chunk path when moving from chunk to chunk. This does 2 things for you. It speeds up the pathfinding by breaking it up over many smaller pieces, and it also enables the unit to change direction part way along the path when a chunk updates. It would re-path across the large network if any of the nodes it needs to cross update.