調べたらダイクストラ法というのが出てくると思うけどそれが最適なアルゴリズム
ただしそれを使ってもかなり重い処理なんで1フレーム中に計算できるのは12歩くらいが限度
20歩とかやるとフリーズする
ファイヤーエムブレムifではステージギミックで20歩くらい動けるところがあったけどどうやってるのか謎