経路探索の概要
最終更新：
sudoubenpi 2014年09月27日(土) 10:24:06履歴
この章では「経路探索」について解説していく。
・経路って何よ？
普段我々が使う「経路」という言葉は大体「道」「道筋」の事を表している。
ゲームやそれ以外の計算機科学での経路とは「グラフ理論」のことである。
グラフ理論において「経路」とは「頂点（ノード）」が複数個存在し各頂点を結ぶ「辺（エッジ）」があるグラフのことである。
・グラフ理論って？
頂点(節点・ノード)の集合と辺(枝・エッジ)の集合で構成されるグラフの性質について研究する学問（Wikipediaより）
「つながり方」に着目して抽象化された「点とそれをむすぶ線」の概念がグラフであり、グラフが持つ様々な性質を探求するのがグラフ理論である（Wikipediaより）
・じゃあ経路探索って？
一言で言えば「グラフ内から特定の情報を取り出す操作」である。
ここでいう「情報」とは必ずしも「ゲーム内のオブジェクトの座標」を表すものではない。
グラフ理論の項で説明があったようにグラフ理論が着目しているのは「つながり方」なので情報同士の繋がりが作成出来るような情報であれば、情報の種類は問わない。
オライリー社から出版されている「実例で学ぶゲームAIプログラミング」では、経路探索の使い方を「通り道を探す」以外にも「RTSにおいて作成したいユニットを作るためには他にどのようなユニットが必要か」という情報を取り出すためにグラフ理論を用いている。
この章では「AIが通るべき道筋を検索するため」の経路探索を解説していく。
・経路って何よ？
普段我々が使う「経路」という言葉は大体「道」「道筋」の事を表している。
ゲームやそれ以外の計算機科学での経路とは「グラフ理論」のことである。
グラフ理論において「経路」とは「頂点（ノード）」が複数個存在し各頂点を結ぶ「辺（エッジ）」があるグラフのことである。
・グラフ理論って？
頂点(節点・ノード)の集合と辺(枝・エッジ)の集合で構成されるグラフの性質について研究する学問（Wikipediaより）
「つながり方」に着目して抽象化された「点とそれをむすぶ線」の概念がグラフであり、グラフが持つ様々な性質を探求するのがグラフ理論である（Wikipediaより）
・じゃあ経路探索って？
一言で言えば「グラフ内から特定の情報を取り出す操作」である。
ここでいう「情報」とは必ずしも「ゲーム内のオブジェクトの座標」を表すものではない。
グラフ理論の項で説明があったようにグラフ理論が着目しているのは「つながり方」なので情報同士の繋がりが作成出来るような情報であれば、情報の種類は問わない。
オライリー社から出版されている「実例で学ぶゲームAIプログラミング」では、経路探索の使い方を「通り道を探す」以外にも「RTSにおいて作成したいユニットを作るためには他にどのようなユニットが必要か」という情報を取り出すためにグラフ理論を用いている。
この章では「AIが通るべき道筋を検索するため」の経路探索を解説していく。
コメントをかく