SRPGにおける移動ルートの計算について

[なよ/acgin]

こんばんは、新しくなってからは初めての投稿になります。
随分と便利になってて感動しました。

と、早速ですが掲題の件について…

現在SRPG（イメージとしてはファイアーエムブレムのようなもの）を作成しているのですが、
移動可能範囲を再帰を用いて出したまではいいもののキャラクターが移動するアニメーションをしたいため、移動ルートも必要になりました。
基本的にはカーソルの移動した通りに移動するのですが、例えば

・途中で移動範囲外に出てしまってからまた移動範囲内に戻ってきた場合
・前カーソルが移動したマスにカーソルを戻した場合
・くねくねと曲がりながら移動したために途中で移動力が足りなくなった場合

などに移動ルートを再計算する必要が出てきました。
※参考に画像を添付します。

フィールドは左上座標を(0,0)としたマスクラス（移動コストや種類、移動範囲表示中はその場所を通る際の最大残り移動力等を保持）
の二次元配列で構成されています。

こういった場合どのように移動ルートを保持するのが良いのでしょうか。

再計算が必要ない場合に考えていたものは、キャラクターを選択し、移動範囲を表示する際にキャラクターの移動力を変数Aに格納、移動回数を変数Bに格納、
カーソルが移動する度に変数Aの値をカーソル位置のマスの移動コスト分引いて、変数Bの値をマスに保存し、変数Bをインクリメント、
移動方向はマスに保存しておいた移動回数を順番に辿っていく、というものでした。

しかしこの方法だと例の再計算が必要になった際どうすれば良いのか思いつかず…
何かアドバイスをもらえたら、と思います。

言語はC++、開発環境はVC++ 2008 EEとDXライブラリです。

以上、よろしくお願いします。

[a5ua]

＞その場所を通る際の最大残り移動力
を計算するときに、「このマスを通るときの一個手前のマス」も保持しておけば、
カーソル位置から、逆順にたどることで経路を求めることができます。
これで、カーソルの動きに関係なく、移動範囲が決まれば、あるマスに行くため経路も決まることになります。

※この種の問題は、「最短経路問題」と呼ばれています。一度調べてみるといいでしょう。

[なよ/acgin]

>a5uaさん
回答ありがとうございます。
その方法でやれば効率的且つ目的の動作が実現できそうです！

さらにこの種の問題の名前まで教えていただいて感謝です。
よく理解した上で引き続きゲーム製作を続けていこうと思います。

改めてどうもありがとうございました！

以上、当トピックの問題は解決とさせて頂きます。
考えてくださった方、見てくださった方もありがとうございます。