HSPTV!掲示板

こんばんは。
とある場所から別の場所へ、障害物を回り込んで避けながら最短ルートを検索する方法を探しています。
最終的には、避ける場所を追加していって、最後に探索ルーチンを呼び出すと、指定された場所を避けて移動する経路を返してくれるようにしたいです。
調べていたところ、a*というアルゴリズムが見つかったのですが、HSPにポインタとか構造体の概念はほとんどないし(構造体は処理が複雑になってもよければいくらでも代用はできそうだが)、アルゴリズム自体も完璧には理解していないので、うまくHSPに移植できるかわかりません
もし、このアルゴリズムに詳しい方がいらっしゃいましたら、手順だけでもいいので、HSPでの実装方法のアドバイスをください。
参考URL　http://2dgames.jp/2012/05/22/a-starar/

奇遇ですね。丁度同じようなことをしようとしている最中です。
以下、自分なりに調べた結果を。誤りがあった場合はすみません。


まず、A*ですがこれは日本語の文献が非常に少ないのでより簡易なDijkstra法で先に実装したほうが良いと思います。
Dijkstra法というのはA*の元となったアルゴリズムで、これは少し変更するだけでA*に出来ます。

また、構造体やポインタの件ですがこれはメモリ消費等の観点からリスト構造等を用いることが多いだけで、
アルゴリズム自体は単純な配列を用いても実装できますので、HSPでも楽に実装できるかと思います。

但し、最短経路探索はノード数（分岐点の数）が多くなればなるほど（特にHSPでは）時間がかかります。
更に配列を用いる場合はメモリ使用量も増加します。（http://www.elc.ees.saitama-u.ac.jp/ProgrammingI/No10.pdf）
もしもノード数が多くなりすぎるのであれば、多言語で実装しDLL等を作成した方がいいかもしれません。

実装アルゴリズムはわかりませんが、過去のHSPコンテストで迷路の最短経路を探索できるプログラムがあります

迷路なら任せろ！
http://hsp.tv/contest2010/entry.php?id=66

にゃんちゃんさんは特にアルゴリズムにこだわりはないようですので、参考にしてみてはいかがでしょうか

また、避ける処理ですがこれは障害物の角（もしくはそこから少し離れた場所）をノードに
設定し、ノード間に障害物がない場合のみ接続すれば実現できるかと思います。
また、2013年のHAL研究所のプログラミングコンテストではそれに近いような問題が出題されています。
（http://www.hallab.co.jp/progcon/2013/）
ここでは問題解答のヒントなども載っていますのでもしかしたら参考になるかもしれません。
また、優勝者のソースコードや解説も載っています。
ソースコードは著作権の関係で無断転載・無断引用は出来ませんが、解説を読んで自分なりに作るのはアリだと思います。

すみません、kanahironさんの示したようなグリッドのあるマップ上での経路探索なら読み飛ばしてください。

アドバイスありがとうございます。
すみません、説明が足りませんでしたね。グリッド上での話でした。なので、特に障害物の角とかを当たり判定に入れる必要はないです。
処理時間がかかることは承知しています。しかし、今回は直線距離が何十も離れている場所を目標としないので、簡易なアルゴリズムですむと思いますし、それほど瞬間的な結果のリターンを求めてるわけでもないので、なんとかHSPでもいけるんじゃないかなぁと思っています。
提示いただいた資料を確認してみたいと思います。ほかにもなにか情報をお持ちの方がいらっしゃいましたら、引き続きお願いします。

昔途中まで作ったタワーディフェンスゲームに
経路探索の処理を組み込んであるのでソースを貼っておきますね。

http://fast-uploader.com/file/6966001852295/

ただ、昔作ったものなので内容をあまり覚えておらず説明ができないです。

経路探索の処理は、
enemy.hsp
module/GoalDisCalc.hsp
このあたりの連携でやっているはずです。

ちなみにこれで使っている経路探索は我流のものなので、
一般的な処理でない可能性が高いです。
参考程度にお考えください。

main.hsp をコンパイルしていただければ実行できます。
右のパネルの一番右下の石柱のようなものを
左クリックで設置、右クリックで削除できます。

F1キーを押すとデバッグモードのON/OFFができます。

適当にいじってみてください。

こんにちは。
とりあえず、「迷路なら任せろ」のソースがアルゴリズムそのまんまだったので、現在頑張って解読しています。
これでa*のアルゴリズムをたどっていることは分かるのですが、ループ処理が始まったあたりから動きがよく分かんなくなって、とくに親ノードを書き換えたりしている所は理解度０で、混乱中です。
もしかしたらそれ関係で別スレ立ててしまうかもしれませんが、その時にはよろしくお願いします。
HIJIKIさんの提示してくださったスクリプトも参考にさせていただいて、なんとかこの実装を理解できるようにしたいと思います（でもその前に学校の試験ｗ）