ゲープロ講座セッション２：戦術型ＳＬＧの移動アルゴリズム（１）

- 戦術ＳＬＧのコンピュータルーチンはＡＩそのもの
Article Written: 99/10/29




　こんにちは、鷹月ぐみなです。講座のスタートを待ち望んでくれていた人はどれくらいいたかな？どきどき。それでは早速セッション２を始めようと思います。最初と言う事で、どのジャンルから入ろうかなといろいろ悩みました。簡単なところでＳＴＧやパズルあたりから始めようかとも思いましたけれど、結局、以前からの要望数がもっとも多かった「戦術ＳＬＧ」という難関から始めることにしました。覚悟しててね（笑）。……とはいえ、鷹月もルーチンは１度しか実装した経験がなく、あとはデコンストラクションから得られたチップスを再構成しただけなんで、どこまで実用的かの判断は皆様に委ねます。



　はじめに、戦術型ＳＬＧって具体的に何をさすのか、っていう説明からしておきますね。ゲームで言うとラングリッサーやシャン・グリ・ラ、ファーランドストーリーなどがこれにあたります。定義としては、「戦うユニットのコマをマス上を動かし、有利な状況で戦いを挑み相手を撃退するゲーム」と言った所でしょうか。これに対して戦略型ＳＬＧというものもあり、こちらは「地域地域を舞台に、相手を制圧していくタイプのＳＬＧ」と言った所です。後者はえてして戦闘に入ると戦術型ＳＬＧに入るケースが多いです。後者の例は「銀河英雄伝説」「シュヴァルツシルト」「信長の野望」「三国志」などなど。
　それで今回は、戦術型ＳＬＧの移動アルゴリズムの講義なんですが、移動ルーチンこそがシステムで最も重要なウェイトを占める場所なんで（そもそも移動は戦闘に直接繋がるので）、じっくりとやっていきたいと思います。大体５回くらいになるかな？このセッションは「戦術ＳＬＧ講座その１」とでも題して、あまり難しくない話からしていくことにしましょう。今回はプログラムソースもなしです。



　ＳＬＧの基本は「相手の動きを読み、お互いのステータスと相談しながら行動する」事だと鷹月は思ってます。実際少しでもやりこめば、相手の行動パターンなんて読めてしまうのです。だったらその考え方をそのままプログラムに……全然いかないからこそ、ＳＬＧのフリーソフトが極端に少ないんですよね(^^;)。これ、プログラムを多少知っている人でもお手上げなんです。半分以上アルゴリズムの問題ですから。
　たとえば「基本的に敵はプレイヤーキャラ｛ＰＣ｝に向かってくる」のはシューティングだろうとアクションだろうと変わらない原則なんですが、ＳＬＧでこれを単純に実行してしまうと、大変なことになります。
　上の画面のように、敵とＰＣの間に隔てるものが何も無いなら問題はありません。適当に「まずはｘ座標かｙ座標を合わせるように動いてから、もう片方の座標を合わせようとする」あたりでも、最低限ゲームとして成立するかも知れません。
（画面は鷹月が開発しているＭＡＰエディターにて制作。しかし手抜きなキャラだ……）
　実際には、両者の間には何らかの障害物なりがあることの方が普通です。これを同じアルゴリズムで実行したらどうなるか……分かりやすい例が上図です。ＰＣが動かない限りは少なくとも、敵は永遠にＰＣの元に近づけません。あなたが敵の立場だったら「おいおい、廻りこめばいいだろう〜」とかすぐに気がつくわけですが、さあこれをどういうアルゴリズムで解決するでしょうか？コンピュータは、明確な手順を示さない限りは動いてはくれません。
　たとえば、擬似３Ｄ迷路を探索する際の有名な方法「右手法」なるものがあります。これは、障害物にぶつかる度に右側の方に動きながら壁沿いに進んでいけば、最終的にどこにでも行ける、というもので、かならずしも有効とは言えませんが、迷路ゲームで迷う人はかなり重宝する考え方です。それをこの状況に使ってみましょうか。

《試行》
・ＰＣにじりじり近づくように、ｘ座標とｙ座標を交互に移動していく。
・障害物にぶつかったら、右沿いに動く。
・進行方向の周囲に障害物がなくなった時点で、再度ＰＣに近づき始める。

　なるほどこのアルゴリズムを与えれば、微妙に妖しい動きはしますが確かにＰＣの元に辿りつきます。では、たまたま右側のルートがふさがっていた場合はどうしましょう？
　その場合、行き止まりに到達して、それでも障害物は右手に続くわけですから、ぐるりと向きを逆に変えて、反対方向に戻り始める……傍から見ていると、甚だ滑稽に映ります。結論からいくと、このアルゴリズムではダメということです。

　ここで、マップをボードゲームに置換えて、あなたは敵を操作することにします。そしてが一歩ずつＰＣに近づく所を想定してみましょう。普通、先程の敵のような無様な動作はせずに、しっかりとＰＣの元にたどり着く事ができます。意識的にか、あるいは無意識的に、いくつかの事を考えているのです。それは大抵、次の通りです。

・マップを見て、行き止まりの方には動かない。
・なるべく無駄の無い、近く到達できそうなルートを頭の中で模索し決める。

　そして実は、市販ゲームのＳＬＧなどのプログラムは、ほぼこのアルゴリズム通りに実装しているのです。でも、こんな抽象的な概念をどうプログラムすればいいのでしょうか、と思うでしょう。しかしそこはそれ、コンピューターに向いた「再帰処理」という考え方を用いれば、実は結構単純に実装できるのです。正解はこうです。

《試行》
・あらかじめ、索敵距離数の限界を決めておきます。
・コンピューターは、実際に動く前に以下の長考に入ります。
・ある一方向に進んだと仮定します。その分の距離を減らしておきます。代わりにその地点からのＰＣとの直線的距離を測ります。接触可能だったらそこで全思考は終了です。そうでない限り、そこからまた、移動可能な方向に進んでみた場合を考えます（ただし戻りはしません）。これを、移動距離の限界になる地点まで続けます。
・ちなみに、一度通った場所は計算済みとして、そこで止めます。 ・残りの方向についても同じように繰り返します。
・思考の結果ＰＣと接触できる場合はそのルート、そうでない場合も最もＰＣとの距離が肉薄した場所に移動します。複数あるならば、どのルートをとっても構いません。

　「単純じゃないってば」と思われたらごめんなさい(^^;)。これはプログラムに落とすと結構単純になるんですよ〜。ちなみに今回は敢えてプログラムでは書きません。実際にエレガントな動作をさせるにはもうちょっと手を加える必要がありますが、これでも充分に機能します。
　すぐに「ああ！」と分かる人は、再帰プログラムの経験がある人か、線形計画法あたりを学んだ人じゃないでしょうか。ようするに「最適解＝最短距離」を探すアルゴリズムなのです。

　そういえば、こんな画面をＳＬＧではしばしお目にかかっているはずです。ＰＣが動く際に、移動可能な地点を瞬時に表示してくれ、プレイヤーがある場所を選択すると、そこにしっかりと「最適な移動方法で」到達してくれるのです。この「移動可能地点表示ルーチン」を実装する際にも、先程のアルゴリズムをほぼそのまま使います……というより、使わざるを得ないのです。

　今回はこれくらいにしておきます。
　本気に戦術ＳＬＧの移動ルーチンを構築しようと思ったら、単純にこれをこなすだけでは不充分です。始めの方にも書きましたが、常に攻撃の事も考えて動かなくてはいけません。攻撃して逃げる事もあります。射程のある武器を携帯している場合は近づかない位置でずるがしこく攻撃しなくてはいけません。ＨＰの低い相手のキャラが居たら優先的にそちらに近づいて倒そうとします……などなど。それらをすべて取り入れるとアルゴリズムは複雑怪奇なものになるわけですが、単体単体はプログラム未経験者でも理解できるものです。そういったケースを一つ一つ分けて紹介していけばＳＬＧだって作れちゃう、と私は思っています。



　次回は「ケース」についてあらいざらい考えていこう……と思っていましたが、とりあえず先にプレイヤーの移動ルーチン処理だけ実装を確かめて、ソースを解析しちゃおうと思います。
　ＳＬＧ移動ルーチン講座（１）、いかがだったでしょうか。為になった点、分かりにくい点、要望などありましたらお寄せ下さい。

- 鷹月ぐみな



　□ Session３：戦術ＳＬＧの移動アルゴリズム２ (1999/11/8)


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

Written by. gumina(鷹月 ぐみな)