とりあえず手っ取り早く元の流れに戻すために無理矢理質問ひねり出してみるけど、
逆にまず探索する側の行動をシミュレートして、それに基づいたマップを生成するアルゴリズムってないの？
もしくは現在のマップでの行動を解析して、それを次のマップ生成へ反映させるような手法とか