>>901
追われるのがプレイヤーであればマップ上に足跡として「ヘンゼルとグレーテル」のパンをちぎって落とす事で帰り道を残すイメージをパン屑っていってます(bread clum algorithm)
足跡をフレーム数適当に間引いてもつながりが取れる当たり判定状のデータとしてRing bufferに残しておくことでRing bufferのサイズ上限にきたら消しておけば長距離の追跡が不可能になり、RingBufferの当たりにひっかかればそれを追跡する

グラフの方は実マップがどんな構造かわからないと合わせた説明がしずらいのだけど、広いフィールドの場合は適当な領域に分割してやることでグラフではなくセル単位のA*アルゴリズムが適用できる
グラフっぽいマップとしてはローグライクゲーム(シレンとか)の通路と小部屋が該当する、通路や部屋の大きさを通過コストとして扱えばそのままA*でいける
実際には広いマップも領域と接続面をグラフ化することで全部グラフ探索によるA*へ落とせる、でA*の深さを調整するのにグラフの通過コストから自動生成するツールとかを作る必要がある

とりあえずピクセル単位ってのは絶対ダメなのでどんなに広い空間でも領域として区切りを付けてA*専用マップやグラフに変換するツールから始めると良いかもしれない