ゲープロ講座セッション4:戦術型SLGの移動アルゴリズム(3)

- Coffee Break 〜移動ルーチン活用のすすめ
Article Written: 99/11/10




 みなさんこんにちは、鷹月ぐみなです。……こんな口調で話していると、教育実習で教壇に立った事を思い出してしまいます。しみじみ。
 そんな事はどうでもいいですね。前回のアルゴリズムは理解していただけたでしょうか? サンプルAPのソースコードじゃなくて、主要な移動ルーチン部のほうです。セッション3にしてようやく出てきたソースに戸惑っている人もいますよね。何らかのプログラム言語を知っている方は多分大丈夫だろうとは思うんですが……。んで、今回もソースコードじゃらじゃらだと、混乱してしまうでしょうから、ちょっとコーヒーブレイク(小休止)を入れることにしました。主題は、前回の最後にちょっと書いた最短距離アルゴリズムについてです。ソースは出しませんので、気楽に読んで行ってください(^^



 皆さん、サンプルAPの方はもう動かしていただけたでしょうか。重ねて、Macintoshユーザの方はごめんなさいです。SoftWindowsで動くはずですが、とは言ってはいけませんね(^^;)。まぁよく見られるSLG移動のエッセンス部分を体験できたのではないかと思います。サンプルAPで注目して欲しかったのは、障害物をするりとかわして、目的地までの最短距離で到達しちゃう事です。これは紛れもないAI(人工知能)です。AIの定義は様々ですが、鷹月は、「現在地点があって目的を設定すると、その目的に到達するように思考し解決してくれること」だと位置付けています。AIの形は様々有り、それを話し出すとゆうに5〜6話くらいできちゃいそうなんで、細かい意味はまたの機会にしておきますが、ともかく移動ルーチンに関してちょっとした人工知能が組みこまれたと言って良いのです。あとはこれを少しいじってあげるだけで、今度説明しようと思っている敵キャラの索敵ルーチンをはじめ、SLGを離れた方面でも応用が効くようになります。
    : [ 図1 ]
 一旦SLGやプレイヤーの操作の事は忘れて、図1を見てください。とにかくあるキャラを、どんどん右側に進めさせたいという状況があったとします。リアルタイム系のACTや、ゲームのデモなどで使う事があるでしょうか。ここで先のアルゴリズムを組みこまず、単に右に進ませるだけのルーチンを考えてみたとします。案の定、障害物にぶつかるわけですが、そこで適当な方向に曲がらせて、また右に進めると言うルーチンにします。状況がこれくらい単純だと何の問題もないように見えます。
    : [ 図2 ]
 では図2はどうでしょう。まず壁にぶつかります。どっちかに曲がりまた直進……とやってみると、袋小路に行き詰まります。はやくも単純アルゴリズムルーチンの破綻が見えてきました。この場合、「曲がっても無駄だった場合、ぐるりと後ろに戻り始める」的な処理を加えてあげる必要があります。説明の展開がセッション2と似てますが、まあ復習だと思っていてください(^^;)。右手法でも構いません。この手法は確実に進めるかも知れませんが、戻るぶんなど、効率はひどく悪くなります。決してAIではなく、コンピュータらしい馬鹿正直な行動を取ってくれるわけです。
 では、前回のサンプルAPで導入したアルゴリズムを搭載させてみましょう。目標を与えます。「右へ進め。その際、ある地点から検索し、もっともx座標が右側になる所に移動するように進め。ルートがいくつか存在する場合、y座標を先に合わせる事
 なんか複雑そうですが、よく読んで見ると非常にシンプルな事を言っています。図2で移動地点が出ていますが、もっとも右側に伸びた白い地点めざして進んでいけばいいのです。



 こう書いて、「あれ??」と咄嗟に思った人、いるかな? そうです、もっとも右側に移動できる場所はそれこそ、袋小路への道まっしぐらなのです!
    : [ 図3 ]
 このAIも実はちょっとお馬鹿さんなのです。少し進んで図3の状態になっても、やはり袋小路の方向へ進んだほうが良いと結論付けています。
    : [ 図4 ]
 ところが、とうとう袋小路に……と思った直前で、このキャラクターは、別なルートを取った方が先に進めるじゃん、という事に気が付き、慌てて下に折り返すのです(図4)。AIルーチンによって、辛くも袋小路入りは逃れたのです。
    : [ 図5 ]
 しばらく進むと、また同じように袋小路入りの危険が発生しますが、やはり同じように直前で気づき、かわして先に進みます。順路を図5に示して見ました。最短ではないとはいえ、さほどの無駄もないまま進んでいることが分かります。さすが探索AIと言ったところですが、なぜ最短のルートで進まなかったのでしょうか。答えは簡単で、探索範囲6が狭かったからなのです。この検索距離を7、8……10と増やして行くことにより、最適なルートを選んでくれるようになっています。(厳密には、y座標優先合わせは邪魔になってしまうことがあるのですが……)。頭の良さは同じだけど、視力0.01(メガネなし)と視力2.0の人にそれぞれ道案内をさせた時のような結果が出るのです。
 ただし、前にちょっとだけ書きましたが、検索範囲を広げれば広げるほど計算回数は増え、マシンの動作は遅くなります。でも、考えるぶんだけ賢い方法をとってくれるのです。コンピューターゲーム「囲碁」「将棋」のレベル設定と一緒ですね、これをAIと呼ばずしてどうしましょう。



 とはいえ。えてして、最適ルートを取ることが必ずしも良いとは限りません。人工知能の目標がチューリングのように、「人間っぽさ」をめざすものとしたら、尚のことです。上の図のキャラクターをあなたが自由に操作するとしたらどうしますか?たとえ「右側に行こうね」と言ったところで、必ずしも最短で通るとは限りません。ぶらついて見たり、うっかり袋小路にハマってみたり(笑)して進めて行くこともあるでしょう。こういう面を重視してみると、また違った設計ができるようになります。具体的にこれをプログラムで実装する事も可能です。基本ラインとしては、最適ルートを通るようになっているけれども、30%の確率で「2番目に最適なルートを敢えて選び」、10%の確率で「適当な方向に動いたり」といったように、曖昧な部分を入れてやる事です。正直見せ掛けのテクニックです。けれども、適度にこういった要素を入れてあげる事によって、色々な楽しさを出す事ができるのです。バーチャロンなんかはいい例ですね。100%完璧な解を選んでいたらプレイヤーは絶対に勝てないからです(笑)。



 コーヒーブレイクの終わりに、ちょっとユニークな活用法を紹介しましょう。鷹月は1年以上前に、「環境RPGはいかがですか?」という記事を書いたことがあります。99年の3月にHPをリニューアルした際に、うっかり戻すのを忘れていた記事たちの一つです(笑)。ハードディスク見てみるとこういった読物が30くらい存在してたり(^^;)。短いので、どんなものかはちょっと読んでみてください。
 ……読みましたね?
 あれに書かれているのは3Dだとか、結構理想が高くなっていますが、エッセンスはそこではなく、あくまで「自動的にキャラクターたちが動く」という事にあります。平面2Dだって構わないと言えば構わないのです。その際、いかにもコンピューター的に動かれては「なんだかなぁ」と思う事でしょう。そこに、今回の「曖昧性を入れた移動アルゴリズム」を導入し、一定時間毎に目的の方向を変えてみたり、「夕方になったら街に向かって帰る」などという指定をすると、それっぽいのができあがってきます。AIは先に触れたように「目的を与えると、途中の順路は勝手に考えてくれる」所がミソで、どこどこの座標に街をセットしておき、その座標さえ与えれば、「何となく」移動して帰って来れるようになるのです。AIのない機構では強引にルーラ(笑)なりで戻らせるしかないでしょう。実装は楽とは言いませんが、充分作れそうですし、また面白い作品になるかも知れません。もっとも鷹月は他の制作で手一杯なので、この「環境RPG」を実現するのはいつになることやら……。
 こういった感じに、移動アルゴリズムは色々な所に活用することができるのです。これ自身も実際は大したルーチンではないのですが、知っていると知らないとでは、だいぶ作品の幅、質ともに違ってきます。ま、そんなこんなでコーヒーブレイクは終了です。では皆さん、まだ次回でお会いしましょう。

※ 今回のアルゴリズムは厳密ではないので、あまり突っ込まないで下さいね(^^;)。たとえば袋小路の長さが3で、探索距離が6の場合、もうちょっとロジックを足してあげないと前後移動を繰り返してハマります(汗)。



 今回、あんまり内容が無い事はお気づきですね。絵で水増ししてみました(笑)。ま、でもこういう解説も分かりやすくていいかな、と思います。けっこうくどく書いたので、移動アルゴリズムの考え方はさすがにOKかな? 次回から、このルーチンは前提として進めていくつもりです。お楽しみに。ちなみにリアルタイムで購読されている人はぜひ感想などを掲示板などに書きこんで下さいね。それが講義の指針にもなりますので。というか、来ないと打ちきっちゃうよとか言ってみたり(爆)。<嚇すかい
 なお、ここでずっと使っていくカッコイイ素材は泣く大臣さんの提供によるものです。感謝。格好悪いのがあったら(もしくはファニィなやつ)、それは鷹月制作の素材でしょう(笑)。

- 鷹月 ぐみな



  Session5:戦術SLGの移動アルゴリズム4 (1999/11/16)



カレッジの入り口に戻る
鷹月ぐみな情報局2号館

Written by. gumina(鷹月 ぐみな)