コミケで、RTSのアルゴリズムについて興味があると言われたので、触りだけでも書いてみます。興味がある人が多いようなら、細かなことも書いてみようかと思います。
（注：上記で「RTS」と書いていますが、うちのゲームは「ストラテジー」ってほどじゃないケースもあるので、リアルタイムシミュレーションぐらいの意味で読んでください）
というわけで、まずは上記2つのゲームについて軽く触れます。
●「キングオブアース」
私が2～3年前に作ったiアプリ向けRTSです。生産と占領、戦争を行う、戦略級のリアルタイムシミュレーションゲームになります（iモード公式の「RPG大集合!」でプレイ可能）。
特徴は、2,000ぐらいの建物と500ぐらいのユニットが、画面外まで広がる広大なマップ内でリアルタイムに動き、自動で戦争を行うことです。
建物には、収入が入る「都市系」、兵士や戦車や戦闘機を生産する「工場系」、壁や要塞や対空砲などの防衛を行う「防御系」があります。
また、兵団を効率よく輸送する「道路」や「橋」を建設することもでき、都市設計も楽しめるゲームになっています。
戦争に使えるユニットには、歩兵や戦車、戦闘機など色々とあり、特殊能力を持ったパートナーも選べます。爆撃機の編隊を作って、敵都市を絨毯爆撃したり、忍者をパートナーに選んで、敵の市庁舎に高レベル兵士を瞬時に送り込んだり、様々な戦い方を楽しめます。
自軍、敵軍、最大合計8カ国のユニットが、画面内で自律的に動き、互いに戦闘をしながら、敵陣の建物を破壊して市庁舎を落とすことで陣地が広がっていきます。
もちろん敵のプレイヤーもAIを持っており、自分たちで考えながら都市設計を行い、周囲の国に戦争を仕掛けていきます。
●「Army & Maiden」
次に、私が今年作ったPC向けRTS「Army & Maiden」です。こちらは、戦術級のリアルタイムシミュレーションゲームです（現在、DL販売版と体験版を準備中）。
特徴としては、敵味方合計100体ぐらいのユニットが、自動で戦闘を繰り広げることです。プレイヤー側のユニットは、移動場所をドラッグすることで、そこに向かって移動して戦闘をします。敵側のユニットは、自動で自分の行動を判断して、戦闘を行います。
こちらはユーザーインターフェースを中心に考えられたゲームで、スマートフォンのタッチパネル操作を想定した作りになっています。
この2つのゲームは、同じ作者が作ったゲームなので共通点も多いです。また、条件の違いや、ゲームの内容の違いで異なっている点もあります。
以下、簡単に表にまとめてみます。以下「KOE」は「キングオブアース」で、「A&M」は「Army & Maiden」です。
・動作環境
KOE：iモード900i以上（3年前ぐらいの機種）
A&M：PC（将来的にはAndroid Phoneへ移植予定。使用メモリーは、現在の開発バージョンでは16MB以内に収まっています）
・各ユニットの表現
KOE：byte配列
A&M：Javaのクラス
・ユニット数
KOE：ユニット500＋建物2000で2500ぐらい
A&M：128ぐらい
・画面サイズ
KOE：240×240
A&M：800×600
さて、この2つのゲームは「リアルタイム」シミュレーション・ゲームです。
というわけで、「リアルタイム」シミュレーション・ゲームと、「非リアルタイム」シミュレーション・ゲームの最大の違いを書きます。
それは「待ち時間があるかないか」です。
「非リアルタイム」系のシミュレーション・ゲームは、待ち時間があるので、その間に複雑な計算を行えます。
「リアルタイム」系のシミュレーション・ゲームは、待ち時間がないので、描画に余ったCPU時間とメモリ量の中で、全ての計算を遅延なく行わなければなりません。
こういった「リアルタイム・シミュレーション・ゲーム」を作る際に、行わなければならないことは3つあります。
１．現実の模倣と間引きとモデル化
２．省メモリー省CPUのデータ形式とアルゴリズムの開発
３．計算時間の分割とユーザーへの目くらまし
１２３は、それぞれ相互に絡んでいます。以下、順に説明していきます。
１．現実の模倣と間引きとモデル化
たとえば、戦術級の戦闘を模倣した際、「索敵」「移動」「攻撃」という行動を、ユニットに行わせる必要があります。
さらに現実を詳細に模倣しようとすれば、指揮官の情報収集、兵士への指揮の伝達など、模倣すべきことは多岐にわたります。
しかし、全てを現実のままに模倣することはできません。なぜならば、CPU時間には限りがあるし、メモリにも限界があるからです。
そこで、「そのゲームで何を表現するか」を考えて、現実の「どの部分を模倣するか」、そして「何を間引きするか」を決定します。
例えば今年の夏コミで作った「Army & Maiden」では、「索敵」「移動」「攻撃」に加えて、「グループ化」（ネストも可能）などの要素を採用しています。
そして、そういった要素を、なるべく簡単に実現でき、かつ自然に見えるようにモデル化しています。
モデル化の際には、「全てを盛り込む」のではなく、「そのゲームで何を表現したいか」を考えてその世界のルールを決めます。
モデル化の例として、「索敵」について説明します。
「索敵」の最も簡単なモデルは「敵と自分の距離だけを見る」というものです。もう一段階複雑になると「射線が通っている」という要素が加わります。さらに複雑にするなら、「仲間（もしくは指揮官）の射線が通っている敵は見える」というルールを付け加えることもできます。
このように、模倣を「より強く」行えば、計算量は増えますが「より自然」になります。
でも、それがゲームで表現したいことと無関係なら、処理時間とメモリーがもったいないので、その仕様は捨てた方がよいです。
「Army & Maiden」では、索敵範囲内の最もHPが少ないユニットを探して殴りに行くという非常に単純なモデルを採用しています（実際には、あといくつかルールがあって、そう簡単ではないのですが、それは割愛します）。
なぜそういったシンプルなモデルかと言うと、あまり複雑な「索敵」モデルを作っても、プレイヤーが同時に数十体の索敵状況を把握できないからです。ユーザーの認識できない仕様は、ないのと同じです。
そして、ユーザーが予測できる範囲の仕様でないと、ユーザーの「発見の喜び」や、「自分が考えた勝った」という達成感は得られません。なので、「索敵」はシンプルにしています。
このようにして、「そのゲームで何を表現したいか」を考えながら、「現実の模倣と間引きとモデル化」を行っていきます。
２．省メモリー省CPUのデータ形式とアルゴリズムの開発
実はこれがかなり重要です。
私は携帯電話向けのゲームを中心に作ってきたので、限られたメモリーとCPUで、いかにゲームを動かすかは色々と学びました。
この部分を行うためにまず最初に知らないといけないのは、ターゲットのマシンのメモリーとCPUの特性です。
メモリもCPUもロースペックというケースもありますが、どちらかだけが厳しいという場合もあります。
たとえば、メモリだけがきつくてCPUは割と速いのなら、計算結果のバッファを持たずに、その都度計算を行うような設計にします。
逆に、CPUが遅くてメモリに余裕があるなら、計算結果をバッファに持って、計算量を減らす工夫をします。
あとは開発期間とのトレードオフです。省メモリー省CPUの設計にすると、ソースが複雑になりがちなので、開発期間は長くなります。
そういったことを考慮しながら、１で作ったモデルを、プログラムでどう表現するかを考えていきます。
ここの実装次第で、ゲームがリアルタイムで動くか処理落ちするかが決まります。また、どれだけの機能を盛り込めるかも決定します。計算時間をオーバーするような仕様は、基本的には盛り込めません。
計算速度を稼ぐためには、細かな計算の端折り方もします。forループを展開して実行速度を稼いだり、判定を簡略化したりもします。
たとえばCPU時間を稼ぎたい場合には、索敵範囲を円形にせず、ひし形や四角にします。
また、メモリを稼ぎたい場合には、ゲーム全体をbyteだけで表現できるように設計します。intの半分のメモリで済むようになります。
アルゴリズムについても同じように工夫します。
夏コミに出した「Army & Maiden」では、マップは1200×600の大きさになります。この中で目的地に行く最短ルートを計算しようとすると、かなりのメモリとCPU時間を使います。
また、敵は通過できないので、最短経路を計算するためのマップは常時変化します。その計算も入ってきます。
なので、このアルゴリズムの実装の仕方次第では、リアルタイムに動かせなくなってしまいます。
ではどうやっているのか？ アプローチは色々とあるのですが、今回は「シムシティ」のアルゴリズムを参考にしています。
「シムシティ」という有名なシミュレーションゲームは、実は内部はレイヤー構造になっています。
小マップ、中マップ、大マップのように、マス目のサイズが違うレイヤーがいくつかあり、配置ユニットは内部的には、そのユニットに対応したレイヤーに配置されます。そして、そのレイヤー内で処理が行われます。
「シムシティ」では、そうした「サイズの違うマップの結果」が、それぞれ別のマップにフィードバックされます。こうすることでレイヤー間の相互作用が生まれて、「シムシティ」では複雑系を表現しています。
「Army & Maiden」も同じように、見た目のレイヤーとは違う、移動のための複数のレイヤーを持っています。
このレイヤーは当然、ユーザーの見ている表層レイヤーよりも1マスのドット数が大きく、計算量とメモリー量を減らすのに役立っています。
具体的には、マス目の大きなレイヤー上を移動して、ゴール近くになるとマス目の小さなレイヤー上で移動を行います。
これで、メモリー量とCPU時間は劇的に減ります。
リアルタイム系のシミュレーション・ゲームでは、こういったデータ構造とアルゴリズムの工夫を随所に盛り込んでいきます。
３．計算時間の分割とユーザーへの目くらまし
これは、ユニット数の多いリアルタイム・シミュレーション・ゲームならではの手法だと思います。
各ユニットの行動を、毎フレーム、バカ正直に計算したりしません。
いくつかの方法で、時間軸上での分散処理を行います。
まず、私が行うのは、ユニット数で割った分散処理です。たとえば、スペック的に1フレーム10体の計算が限界ならば、1フレームごとに10体ずつ計算を行います。
複数CPUで並列処理を行うように、複数フレームで並列処理（この場合は分散処理の方が適切）を行うわけです。
当然、そういったことができるように、データ構造を設計しなければなりません。そういったことを考慮していないと、データに矛盾が生じます。
また、先ほどレイヤー分けして処理量とメモリ量を減らすアルゴリズムの話をしましたが、同じようなことを時間軸に対しても行います。
たとえば、大きな処理を1秒に1回行い、小さな処理を1フレームごとに行うなどです。
こういったことを行い、計算時間を分割してリアルタイム内に収まるようにします。
これと同時に必要になるのが、ユーザーに対しての目くらましです。
たとえば「Army & Maiden」では、リアルタイムに全てのユニットが動いているように見えますが、実は各ユニットは1.3秒に一度しか動いていません。移動計算のタイミングは、1.3秒に一度しかないからです。
その他の時間は、計算後のデータを使って、単純に位置をスライドさせています。
これだけだと1.3秒に一度しか動いていないように見えてしまうので、目くらましを使っています。攻撃を1秒に一度計算するようにしています。
移動と攻撃の計算タイミングをずらして、この2つの周期が、ぱっと見た目では重ならないようにしています。
これでユーザーは処理タイミングが見えなくなり、リアルタイムにずっと計算されているように見えます。
また「キングオブアース」では別のめくらましを使っています。
このゲームは、画面外のマップが広大なゲームです。そこで、画面に映る範囲では、詳細な挙動を伴った移動アルゴリズムを使い、画面外だともう少し簡単なアルゴリズムを使うことで、処理時間を稼いでいます。
ユーザーは、自分の見える範囲しか見ておらず、画面をスクロールすると、目に入ったユニットがすべて複雑な挙動をしているので、全てのユニットが同じ計算で動いているように見えます。
こういった計算時間の分割と目くらましを使い、リアルタイムで動かすためのCPU時間とメモリ量を稼いでいきます。
ざっと駆け足で書きましたが、リアルタイム・シミュレーション・ゲームのアルゴリズムについて知りたいという要望があったので簡単に書いてみました。
そんなに難しいことをしているわけではないということが、分かったと思います。
要望が多いようなら、もう少し詳しい話を書いてもよいのかなと思います。
とっても興味深い記事をありがとうございます！
返信削除私はこれからAndroidで初めてのゲーム作りをしたいと思っているド素人です。
シムシティについての解説が特に興味があります。
シムシティ的なゲームの作り方についてさんざんググった結果、貴サイト以外はほとんど見かけなかったので、ここを見つけたときは小躍りして喜びました。
できれば「Android（Java）でシンプルなシムシティ風ゲームを作るチュートリアル」みたいな記事をアップしていただけませんでしょうか？