HSPポータル
サイトマップ お問い合わせ


HSPTV!掲示板


未解決 解決 停止 削除要請

2011
0210
WHITE経路探索3解決


WHITE

リンク

2011/2/10(Thu) 20:26:41|NO.36994

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

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

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

ということです。

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

おねがいします。



この記事に返信する


ひらまる

リンク

2011/2/10(Thu) 20:54:29|NO.36995

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

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

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



WHITE

リンク

2011/2/10(Thu) 21:06:38|NO.36996

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

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

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

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



WHITE

リンク

2011/2/10(Thu) 22:22:29|NO.36999

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



ONION software Copyright 1997-2023(c) All rights reserved.