ゲームＡＩラウンドテーブル・オン・ツイッター第12回 「パス検索の本質を考える」
-
- いいね！1
三宅陽一郎MiyakeYouichiro
@miyayou
tweetchat に入るとカスタマイズボタンがありますがリフレッシュスピードとかフォントの大きさを変化できるけど、一番大切なのはUser Control ボタンをクリックして、RT 表示をオフにするかどうかです。このボタンで 公式RTを非常時に出来ます #gameai_rt12
2011-04-24 00:34:45
三宅陽一郎MiyakeYouichiro
@miyayou
本日の議題はパス検索です。まずパス検索の解説から行います。文字しか使えないのでイメージで説明します。技術者でない方は、イメージを最大限膨らませてください。 #gameai_rt12
2011-04-24 00:36:12
三宅陽一郎MiyakeYouichiro
@miyayou
まず広大なフィールドを想像しましょう。RPGの大地みたいな。そこでキャラクター、イメージしやすいように、モンスターを動かすことを想像しましょう。 #gameai_rt12
2011-04-24 00:38:05
三宅陽一郎MiyakeYouichiro
@miyayou
もし平原に何のオブジェクトがなければ、どこにでも、モンスターをまっすぐ動かすことができます。では、たくさんの岩があったり、橋があったり、トンネルがあったり、滝があったりしたら、どうでしょうか？ #gameai_rt12
2011-04-24 00:38:58
三宅陽一郎MiyakeYouichiro
@miyayou
かつて、そういった環境では、「モンスターの動ける範囲をある長方形領域に制限する」「パスを固定して、座標数列で与えてしまう」「壁にあたったらターン」など、そういった処方が取られていました。PlayStation 2の頃までは、実に大半のタイトルがそうでした #gameai_rt12
2011-04-24 00:39:23
三宅陽一郎MiyakeYouichiro
@miyayou
しかし９０年代後半からのPCゲーム、００年代前半に入って次世代ゲーム機では、次第に「パス検索技術」が導入され始め、現在では、FPS、ストラテジーゲームをはじめ、多くのゲームがこの技術をデフォルトとして導入し、ミドルウェアも数社が作成してサポートしています #gameai_rt12
2011-04-24 00:41:44
三宅陽一郎MiyakeYouichiro
@miyayou
先のたくさんの岩が置かれた平原を例に説明しましょう。この平原にたくさんのポイントを置きます。岩のあるところには起きません。次にポイント同士で近いものを繋ぎます。すると上空から見ると平原の上に一つのネットワークグラフが出現します。これをパスデータと呼びます #gameai_rt12
2011-04-24 00:43:30
下田賢佑
@kensukeShimoda
非技術者向けにパスファインディング技術の動画を。AIミドルウェアKynapseです。このページの下のリンクから観られます。 http://bit.ly/dQH7Zi #gameai_rt12
2011-04-24 00:43:53
三宅陽一郎MiyakeYouichiro
@miyayou
このパスデータの上の任意の２ポイントを指定します。頭の中でこの２点を指定してみてください。ここでパス検索アルゴリズムを使うと、この２点の最短経路を見出すことができます。これは技術的ですが、A*アルゴリズムとかダイクストラアルゴリズムとか言います。 #gameai_rt12
2011-04-24 00:44:20
三宅陽一郎MiyakeYouichiro
@miyayou
ネットワークグラフ上の経路検索という技術は実は古くからコンピューターサイエンスで知られていた技術でした。しかし、これが実際に本格的にゲームに応用され始めたのは９０年代後半からです。 #gameai_rt12
2011-04-24 00:44:31
三宅陽一郎MiyakeYouichiro
@miyayou
さて先の例では、ポイントを置きましたが、ポイントの変わりに地形表面に沿って三角形を置く（長方形）を置く場合もあります。これをメッシュと呼んで、隣接するメッシュを結んだものを、ナビゲーションメッシュと呼びます。このナビメッシュ上でも同様のパス検索を出来ます #gameai_rt12
2011-04-24 00:46:18
nico_shindannin（診断人）
@nico_shindannin
@miyayou 80年代のシミュレーションゲーム（「三国志」とか「大戦略」とか）で、パス検索は普通に使われていると思うのですが、今回の議論はFPS用のパス検索と考えてよいでしょうか？ #gameai_rt12
2011-04-24 00:47:53
三宅陽一郎MiyakeYouichiro
@miyayou
こちらに動画がありますね。参考にしてください。RT @kensukeShimoda: 非技術者向けにパスファインディング技術の動画を。AIミドルウェアKynapseです。このページの下のリンクから観られます。 http://bit.ly/dQH7Zi #gameai_rt12
2011-04-24 00:48:01
三宅陽一郎MiyakeYouichiro
@miyayou
さて、パス検索の原理はこれでおしまいです。とても単純です。しかし、この１０年で、大きくて複雑なマップ、また様々な属性を持つ地表、さらに、動くオブジェクト（破壊されたオブジェクト）に対するために、この分野の技術が積み上げられました。 #gameai_rt12
2011-04-24 00:49:59
下田賢佑
@kensukeShimoda
3Dゲームだとパスファインディングと付随する知識表現に必要なデータが膨大なので、様々な問題があります。それを解決する話がメインの議題でしょうか。>今回の議論はFPS用のパス検索と考えてよいでしょうか？ #gameai_rt12
2011-04-24 00:50:23
三宅陽一郎MiyakeYouichiro
@miyayou
今年のGDCでは特にこの話題に集中し、大学の研究室から、企業、ミドルウェア会社が、様々な技術発表を行いました。残念ながら、今回はそういった技術的な話題には踏み込みません。そちらは僕の講演資料やブログを読んでください。 #gameai_rt12
2011-04-24 00:51:20
三宅陽一郎MiyakeYouichiro
@miyayou
今日の議題は、こうったパス検索技術が、ゲームをどのように変えて行くか、という点に集中したいと思います。パス検索技術は、AI（キャラクターやモンスター）を一定の領域、狭い行動時間から解放します。もう待ち伏せしているだけの敵ではありません。 #gameai_rt12
2011-04-24 00:52:33