HSPTV!掲示板

最短経路の探索＆障害物回避のアルゴリズムについて質問です。

３次元空間内に配置された坑道のような構造内を移動させるときの最短経路の探索、
及び障害物回避にはどのようなアルゴリズムやテクニックをつかったらいいかわかりません。
（Ｄｅｓｃｅｎｔっていうゲームをご存知ならばわかっていただけるかと・・・）

もうすこし具体的にすると
・複雑な３Ｄモデルのなかを移動するのでどのように通れるところ、
通れないところを判定するかがわからない。
・「３次元空間」における最短経路の探索方法がよくわからない。

ということです。

いまのところは空間をさいの目状にわけたうえで、坑道となるオブジェクトを配置し、
通れないところを手動で設定し、障害物回避＆経路探索をする。
くらいしか思いついていないのですがほかにいい方法もしくは参考になる資料をご存知であれば
教えていただきたいです。

おねがいします。

最短距離を求めるアルゴリズムは、２Ｄも３Ｄも変わらないと思います。
詳しくはないけれど、必要な情報はチェックポイント（基本的に分岐路）同士の距離だけのはず。

http://www.deqnotes.net/acmicpc/dijkstra/

障害物については、どのような規模で、どのような振る舞いをするのかわからないのでなんとも言えません。

回答ありがとうございます＾＾

>>最短距離を求めるアルゴリズムは、２Ｄも３Ｄも変わらないと思います。
提示していただいた資料をみるとそのようですね。

障害物の回避について説明が不足していたようで申し訳ありません；
私が意図していたのは経路探索で得られた結果をもとにして移動すると壁伝いに移動する
ようなかんじになってしまい。不自然な動きになってしまうと思い、壁や障害物から適度に
距離をとり、なおかつ最短距離で移動できるようにする。
ということなのですが、よく考えてみるとチェックポイントを立てる条件に手を加えてやれば
できそうですね。

説明下手で申し訳ありませんでした；

とりあえず解決にしておきます。