When you are near the edge of your loaded chunks, you should be loading more (in the background), and that will reduce the lag time as you travel long distances.

One option is to instead of considering unloaded chunks to be unwalkable consider them unknown. In a first pass you consider them as unwalkable tiles, when path finding fails in that case you can do a second pass where you actually load those chunks.

You can also use a bidirectional A*. That way, if one side ends in a dead end in the first pass, you can skip the second pass.

Also, if it's a pregenerated map it should be possible to load the walk-able state separately (which will be cheaper to load and keep in memory) and even keep the entire map's walk-able state loaded as a bitmap.

ratchet freak
  • 7.2k
  • 19
  • 15