障害物回避のアルゴリズムについて

[コレジャナイ]

http://www.atmarkit.co.jp/fdotnet/terra ... 06_02.html
こちらのサイト様を参考に障害物回避のプログラムを組んでみたのですが、上下に動いたまま一向に移動しなくなる状況が発生してしまったため質問致した次第です。

言葉では説明し辛いのでこちらの画像を参照して欲しいのですが、
緑が目的地
赤が一番近い障害物
紺色の円が最初に確定した経由点
水色が他の障害物領域に経由点が入っていたために移動していった最終地点の経由点
をそれぞれ示しています。


http://iup.2ch-library.com/i/i0849009-1360310909.png
こちらは下に移動

目的地がサイト様内で示されている①のエリア内にあるため、目的地側に紺色経由点が２つ出来ています。
この経由点は他の障害物領域内にありますので、領域内を移動した最終地点が水色となり、上の水色の方が近いため、下の水色経由点は切り捨てて、上の水色経由点で再帰処理を行います。


http://iup.2ch-library.com/i/i0849010-1360310909.png
問題はこちらの上に移動

こちらでは障害物から見た目的地が②のエリアにあるため、最初の経由点は斜めに二つ出来ます。
これらを障害物領域によって移動させると水色の地点となり、近い経由点である下の水色を採用して再帰処理を施してしまいます。

これによって延々と上下移動してしまうバグが発生してしまいました。

こういった特定の状況を除くと概ね想定通りの動きをしてくれてはいるのですが、上記の不具合はどのように修正していけば宜しいものでしょうか？

[softya（ソフト屋)]

このアルゴリズムではダメでしょうか？
「A* - Wikipedia」
http://ja.wikipedia.org/wiki/A*

[コレジャナイ]

>>ソフト屋様
一つづつ理解し実装出来ればなと思いますので出来ればこちらのアルゴリズムで完成させたいです。

このアルゴリズムはメジャーでは無いのでしょうか・・・？
障害物回避のアルゴリズムで検索をするとロボットの物が多く、こちらが一番分かり易かったので採用させて頂いたのですが・・・。

[softya（ソフト屋)]

少なくとも私は、そのアルゴリズムを知りませんしゲームで使ったことはありません。たぶん、ロボット系の障害物回避のアルゴリズムだと思います。
なので、有用性やら問題の回避方法も存じませんが、直接行けない経路をポイントしてしまっているのは大丈夫でしょうか？
こういう解釈で良いのか疑問なんですが。

ゲーム系だとこういう本で勉強した方が良いかもしれませんね。
「O'Reilly Japan - ゲーム開発者のためのAI入門」
http://www.oreilly.co.jp/books/4873112168/

内容の一部はこちらで見れます。
「ゲーム開発者のためのAI入門 - Google ブックス」
http://books.google.co.jp/books/about/% ... GetY0qpd4C

[コレジャナイ]

>>ソフト屋様
絵では冗長だったので表現してませんが、障害物の周りに当たり判定の半径分領域を加えたものを障害物領域として活用しております。
再帰を行って最終的に一番近い障害物領域の角を目標とする感じなのですが・・・。
このサイト様は同じ様な問題にぶつからなかったのかなぁと不思議です。


なるほど・・・マイナーなアルゴリズムを参考にしてしまっていたのですねorz

他の動きに関してはしっかり障害物回避していただけに、捨てるには惜しいのでどなたかこのアルゴリズムに詳しい方がいらっしゃれば宜しくお願いしますOTL
その間にURLにて勉強して参ります

[softya（ソフト屋)]

マイナーかどうかは知りませんよ。私が知らないだけかもしれません。

あと最初のリンクの「障害物回避のためのアルゴリズム」の説明にある「経由点の変更」のところの隣接領域に含まれているポイントを経由点にしているようにしか見えますが、それは違うのでしょうか？

[コレジャナイ]

>>ソフト屋様
紺色が一番最初、処理を実行する前の仮経由点の決定
水色の点が、紺色が障害物領域内に含まれていたために経由点の変更を行い最終決定した点

であり、水色の点を採用し再帰してますがどちらの画像が何か間違ってますでしょうか・・・？

よく意味を汲み取れなかったためすみません。

[softya（ソフト屋)]

画像が消えちゃったみたいですね。
とりあえず、再帰していく過程をビジュアル化して表示すれば問題点が明らかになるんじゃ？と思いました。
この手の経路問題は1週間ぐらい悩んでも全然普通なので色々試してみて下さい。

[小人]

コレジャナイです。画像が消えてしまったので再掲です。
下に移動のみ再帰処理の内容を図示しました。
頭番号１から順にご覧下さい。

[softya（ソフト屋)]

考えてみますが時間を下さい。
※　ただし、解決策が有るかはわかりませんので、そちらでも解決策を探して下さい。

[softya（ソフト屋)]

このアルゴリズムをシミュレート出来るＤＸライブラリのプログラムを用意してもらえませんか？
このままだと、誰からも答えが来ないかもしれません。