You could divide the map into chunks of 50x50 cells. Then you only look at cells which make up the border of a chunk when pathfinding.
Each chunk precalculates which border cells are accessible from other border cells. This could be done efficiently by giving each chunk a list of open areas. Each open area contains a list of the border cells which are in this open area. That way if you have a completely empty chunk it is only one list. The cost of a path from one border cell to another would be estimated when it is encountered.
Optimally, you would count the bottom and right border cells as being cells just outside of the chunk. That way the bottom border cells of one chunk are the top border cells of the one below.
When pathfinding you do one large pathfind using only edge cells of the chunks. Then once you have found which edge cells you will travel through, you can do per-chunk pathfinding to find the path across each chunk.
The good thing about this is that the per-chunk pathfinding only needs to be done when that chunk is reached, and yet you know that you need to do it at some point. This allows you to make a queue system to 'smooth' the number of pathfinds needed each frame.
When a large pathfind finishes, you add all the sub-pathfinds to a queue in decreasing priority, so the first chunk along the route would have the highest priority. You could give each frame an allotted time for pathfinding.
The program would then keep popping at item of the queue and running it until the allotted time had been used up, or there are no more items in the queue.
The only downside is that it may not always find the shortest path.
[b]
