経路探索
spinの3DMark05についての記事でDynamic A* Lite(D* Lite)が使われてるという話が。船の航跡の経路探索に使われてるそうで。ただしベンチマーク中では経路は前計算されてて、D*Lite自体はCPUの負荷テストだけに使われてるとのこと。というかわざわざ使う意味…
http://www.renderware.com/ai.asp のpathfindingってpdf。RenderWare A.Iの資料だけど、ミドルウェアとして、どの辺を問題にしてるのかが、わかりやすくまとめられてて結構おもしろい。そういえば1週間位前に、Electronic Arts、キヤノンから「RenderWare」…
書き残してた部分を。本題のARA*について。 f( )=g( ) +ε*h( )。係数εの値によって探索速度と経路精度の調整ができる。得られる経路の精度は最悪でも本来の最短路のε倍に抑えられる。ARA*はこの性質を利用して、最初に大きい係数εで素早く初期経路を見つけて…
ε-admissible Searchについて。 A*の探索には式、f()=g()+h()が用いられる。gはノードまで実際にかかったコスト。hはヒューリスティックで目的地までの見積もりコスト。通常、幾何学的な距離みたいな単純な式が用いられる。hの見積もりが実際のコストよりも…
http://www-2.cs.cmu.edu/~maxim/publications.html ARA*(AnyTime Repairing A*)2003年の論文だけど見落としてた。検索かけるときはpathfindingよりも"shortest path"の方が分野によっては通りがいいみたいだ。 流れとしてはLPA*と多少関係してるのかな…著者…
http://www.jogd.com/Charles River MediaからJournal of Game Developmentってのが出てたらしい。で、そのVolume 1にHPA* (Hierarchical Path-Finding A*)ってのが。正直そのままHierarchical A*でいいんじゃないのかと。Abstractしか公開されてないので詳…
ダイクストラ法とA*の大きな違い。ダイクストラ法では基本的にOPENリストに入ったノードは近いうちに展開される。それに対してA*ではh()が入ってるので無意味にfが悪化するようなノード、ゴールと反対方向に向かうようなノードはめったに展開されることはな…
A*でOPENリストに入る評価コストの計算式 f( )=g( )+h( )gはその地点までにかかった実際のコスト、hはヒューリスティックでゴールまでの見積もりコスト。 ダイクストラ法の場合h( )が0、探索が進むにつれてOPENリストに入っているfはほぼ単調に増加。よってO…
DeleteMinで取ってきたノードに隣接するノードはk個。これらをさらに展開してOPENリストに入れるわけだから、理論上Member,InsertはDeleteMinのk倍の回数呼ばれることになる。ただ実際にInsertが呼ばれる頻度はｋ倍まではいかないだろうけど。 線形リスト、…
1日経ったら、何書こうと思ってたのか忘れた…前も同じことあったような・・・だめだな。http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html の各データ構毎の比較がわかりやすくていい感じ。A*の動作を簡単に説明すると OPENリス…
本当はこっちが今日書こうと思ってたこと。メモだけ。今週はちょっと忙しいので明日書けるかは不明。 ダイクストラ法のデータ保持構造について書いたけど、ゲームに使うことを考えるとそれほど問題を一般化する必要はないわけで。とりあえず経路探索が必要そ…
ダイクストラ法(Dijkstra)について。一日に１人２人はこの検索用語に引っかかってくるんだけど、何故こんなに？ で、ダイクストラ法の計算量オーダーについて書いてなかったので補足。 探索するグラフの頂点数n、辺数m、かつ>>>>mとする。最後の条件が必要な…
後で書く予定。OPENリスト、データ保持構造の実装方法の比較。
http://www.jaist.ac.jp/~itota/LRTA/ LRTA*のデモ。同じ問題を解くことを繰り返すごとに得られる経路に収束していくのがわかる。広間に入るとなかなか抜けれなかったりしてるけど。何か面白い使い道でもあるんでしょうか…これ。 http://www.jaist.ac.jp/~it…
２日、間があいて何書こうと思ってたんだか忘れた…まだ何かあったと思うんだけどなぁ。続きの続き。前回に挙げられた手法、環境に動的に対応するってのは、あくまでも変化した時点での最短経路探索であって過去、未来の情報は一切考慮していない。 これによ…
さらに続き。A*についてが長くなりすぎた。 今まで書いてきたのは静的な探索(off-line Search)について。この用途ではほぼA*が最適ってことで間違いない。 次に動的な環境での探索について。静的な探索では経路を探索中に探索空間が変化しないことを仮定して…
続き。 ２点間の最短経路を求めるアルゴリズムについて。A*が最も有名。ダイクストラ法に加えてヒューリスティック(目的地までの予想距離)を用いた探索を行う。A*の簡単な解説。実際動いてるの見たほうがわかりやすいと思う。http://www.generation5.org/con…
経路探索を一般化するとグラフ上の問題として表現される。グラフ理論の一分野？読んでて面白くないのであんまり調べてないけど。 昨日の続き。今のまで調べてたことの分類と整理。 単一始点最短路問題(single-source shortest-paths problem) ある特定の1ノ…
http://pc2.2ch.net/test/read.cgi/gamedev/1079745509/SRPGとかでよくある移動可能範囲を調べる問題について。ここ見ながら、どっかでみたことあるなと思って探したらhttp://www-cs-students.stanford.edu/~amitp/Articles/RangeSighting.htmlにそのまんま…
少し前から、GDAlgorithmsを読んでる。投稿数が多いので読まずにいると、どんどん溜まってく…過去ログも少しずつ読もうとしてるんだけど、やたら手間がかかって面倒。最近で、経路探索の所だけ読んでみた。RTS Dynamic obstacles path-finding 2004-02 11〜1…
RTA*。Real-Time Search for Learning Autonomous Agents ISBN:0792399447読んでたんだけど、なんか探してたのと方向性が違うっぽい。探索してすぐ移動ってのを繰り返すんだけど、その１サイクルをMAPのサイズとかに関係なく定数時間で処理しようってのに無…
経路探索と衝突判定は密接に絡んでくるけど、当面タイルベースの探索、キャラクタのサイズもタイル程度の大きさを想定してるんであんま気にしなくてよさそう。 キャラクタが（タイルorポリゴンメッシュ）より大きい場合は経路を調べる時に衝突判定もしてやら…
以前から調べてる内容について補足。ゲームに使うにはA*で十分なのは確か。後は環境の変化にどういう風に対応して再探索を行うかっていうのと、RTSみたいなゲームの場合、探索空間をどうやって狭めるかっていうのが問題。 この辺をゲームの性質にあわせて工…
Googleでゲーム方面から探した結果。 http://www.ensemblestudios.com/age/journalmenu.html Age of Empiresシリーズの開発元のページ。使ってるアルゴリズムなんかを詳しく解説してる。左下のほうのTerrain analysis。AoE2では大体60〜70%の時間を経路探索…
AI Game Programming Wisdomと一緒にGLSL本買うつもりだったんだけど、そういうわけで少し待っても出そうになかったらこっちだけ注文することに。とりあえず１の方だけ。 目次＆abstract http://www.aiwisdom.com/byresource_aiwisdom.html ここ２、３日経路…
経路探索アルゴリズムにはいろいろな種類があるわけだけどゲームに用いる上で、これが最適ってアルゴリズムってのは存在しない。そのゲームについての完全な知識を持った人工知能でもできれば話は別だろうけど。探索アルゴリズムにはそれぞれ特徴があるわけ…
調べ物続き。 RTA*(Real-Time A*) 変種がたくさんあってまだ把握しきれてない。とりあえず、移動しながら経路を探すのをReal-Time探索に分類するらしい。A*みたいにスタート地点からの最短経路が確定してから移動を開始するのはOff-Line探索に分類される。 M…
関係ありそうな論文を次々辿ってく。今更ながらもう少し英語ちゃんと勉強しとくんだったと実感。 試用中のBabylon4.0だけどPDFのファイルによって文字の識別ができないことがある。使えないとやっぱり不便。文章翻訳ソフトって使えるのかな…そこそこの精度が…
前、書いてたのをもう少し突っ込んで調べてみた。 ・LPA*(Lifelong Planning A*) 別名Incremental A*。 Incremental Searchってのは以前の探索結果を利用して再計算の量を減らす手法の名前らしい。この手法をA*に適用したものがLPA*。以前通れた場所が通れな…
以下 http://theory.stanford.edu/~amitp/GameProgramming/のImplementation notes を参考に書いた。 A*の実装について。A*は「OPEN」と「CLOSED」この二つのノード集合の操作によって探索を進めるわけだけど、このノード集合をどんな形で内部に保持するかが…
