前ローグライクゲーム作っててAstarの経路探索をガチで極めようとしたけど挫折した

上下左右斜めの８方向に移動できるから例えば何も考えずに５マス先への最短経路を調べるには８×５回のマス目の進入可否チェックを行う
ただ障害物があって結局遠回りする可能性もあるから、最初の８マスを調べたらその８マスの周囲８マスを調べて、そこから更に８マスを・・・ってなる
一度調べたマスはスキップとか可能な限り最適化しても、５０×４０マスとかのくそでかマップに３０体くらいの敵を配置したら計算量がとんでもないことになって１ターン分の経路探索に200ミリ秒くらいかかった

その条件でもっと高速に動いてるローグライクゲームなら他にもあるしやり方が悪かったんだろうな・・・