HSPTV!掲示板

初めて当掲示板を利用させていただきます。

現在HSPを用いてヘクスマップ形式のシミュレーションゲームを製作しています。

障害物が存在しない場合の最短経路検索→移動は何とかなるのですが、
障害物が存在する場合の最短経路の検索→移動の方法が分かりません。

現在地から目的地への最短経路を探索
↓
目的地へ1マスずつ移動

といった感じのプログラムを書きたい場合どうすればよいでしょうか？

http://uploda.cc/img/img5231b5ad4fdd5.bmp

参考までに、上記添付画像において移動したいユニットが「Ｆ」で、
移動先が(X,Y)=(3,5)の場合について考えております。

よろしくお願いします。

サンプルもあるのでここが参考になりそうです。
http://d.hatena.ne.jp/yonkoushi/20100406/1270556773

local変数を使った再帰呼び出しで周囲六方向？の全てのマスを探索していって、
すでに探索した場所にはマークを付けて以降の探索から除外して
一番速くFに辿りついたものを返すとか？
今思いついたので最適化されているかぜんぜん分かりませんが…。

素早いご回答ありがとうございます。

>catsさん
サンプル拝見させていただきました。
コードを理解するのにしばらく時間がかかりそうですが、
ヘクスマップへ応用ができそうであれば使ってみます。

>ht.さん
マスのずれも考慮するとかなり混乱してしまいまして、
その方法も考えたのですが経路の記憶、評価を含め、
どのようなコードにすれば良いのか分からず今に至る次第です。

経路探索
http://hspdev-wiki.net/?%B7%D0%CF%A9%B7%E8%C4%EA

これをヘックスに対応させれば何とかなると思います。

マップで目的地から障害物以外に隣接する順に番号を振り、今いる位置からその番号の小さいほうへ移動して行けば
最短で移動できると思います。

>トホホッティーさん
リンク先拝見させていただきました。
考えてる挙動的には、関連項目の「COM経路探索」が一番近かったです。
http://hspdev-wiki.net/?%B7%D0%CF%A9%B7%E8%C4%EA

>マップで目的地から障害物以外に隣接する順に番号を振り、
>今いる位置からその番号の小さいほうへ移動して行けば
>最短で移動できると思います。
多分この考え方自体はht.さんのおっしゃってるものと同じ（？）みたいですね。
ですが説明して頂いた事を紙で書いてみましたところ大変分かりやすかったです。


イメージ的には、


　１．目的地周囲6マスの状態取得
　　周囲の1マス目を調べる。
　　　→障害物であれば : そのマスの数値は1000などにしておく→2マス目を調べる。
　　　→障害物じゃなければ : そのマスの数値を１に指定
　　　　　　　　　　　　　　→そのマス周囲の状態を取得
　　　　　　　　　　　　　　→そのマスの周囲6マスを調べる、etc

　２．ユニットの周囲6マスの数値を取得
　　　→最も数値の小さい場所へ移動する。
　　上記繰り返し


こんな感じでしょうか。

後日試させて頂きます。
ありがとうございます。

解決しましたのでご報告に。
http://uploda.cc/img/img523322c0d52d7.bmp

目標地点の値を0にして、障害物地点を特定値(暫定的に9999)、
その他の地点を適当な大きな値（総マス数より上）に設定しました。


その後、

マップ全体を検索
↓
cnt数に合致する値のマスがあれば、障害物を除いて、その周りの値をcnt+1に。
この時既に値が決定されていれば小さいほうの値で決定する。

上記のループで無理やりですが番号を振ることが出来ました。

4次元配列を用いて、全マスの、特定のマスに対応する値をマップ生成時に計算してしまえば、
ユニット移動時の無駄な計算も不要となり後の処理も軽くなると言うことにも気付き感動しております。

素早く的確なご助言に感謝します。
とても助かりました！
ありがとうございます！