ゲームプログラミング/RPG/戦闘
戦闘中のアルゴリズム

ターン制RPGでは、戦闘中、敵と味方が入り乱れて、素早さ順に行動するシステムが、一般的です。
戦闘中のアルゴリズム

このアルゴリズムが、けっこう難しいです。
戦闘中のアルゴリズム

ドラクエ1のように、敵と味方が1対1の戦いなら簡単ですが、ドラクエ2以降や『ファイナルファンタジー』シリーズのように、味方が複数人、敵も複数匹の場合、それらの行動準の決定アルゴリズムは、けっこう難しいです。
戦闘中のアルゴリズム

さて、まずアナタのすべき事として、ドラクエ1のように敵と主人公が1対1のバトルのプログラムを、あなたの自作ゲームのソースコードに書いてください。それが今後の作業の出発点です。そして、その1対1のバトルのプログラムを実際に自作ゲームに組み込んで、とりあえずプレイ可能な状態まで持っていってください。(本セクションの主題ではないので詳細を省略しますが、この時点ですでに、色々な作業があります。コマンド入力後の戦闘自動化のためのタイマー処理など、実装するために調べる点は多くあるでしょう。その他、戦闘勝利や戦闘敗北などの実装もあります。)
戦闘中のアルゴリズム

1対1の戦闘の実装が出来たら、次に、その1対1のプログラムを拡張して 多数 対 多数 のプログラムに改造していきましょう。
戦闘中のアルゴリズム

では、そのような多数対多数での素早さ順行動アルゴリズムのための考えかたを述べます。
戦闘中のアルゴリズム

あるwiki編集者は、次のようなコードで、素早さ順の並び換えが可能だと主張しています。
戦闘中のアルゴリズム

上記コードを書いた編集者が解説を加えないので、別のあるwiki編集者が解説を補います。
戦闘中のアルゴリズム

まず、上記コードにはmain関数が無いので、これだけでは動作しません。
戦闘中のアルゴリズム

また、変数 len が未定義なのでエラーです。
戦闘中のアルゴリズム

試しにLinuxの Fedora 35 のg++で上記コードを実行したら、下記のようなエラーメッセージが出ました(2022年1月24日にg++ (GCC) 11.2.1 で実行)。
戦闘中のアルゴリズム

uint8_t という型は、ヘッダ stdint.h をインクルードすることで使用可能になる仕様です。下記にあるuint8_tのコード例は、gccでなら実行できます。
戦闘中のアルゴリズム

ただし、uint8○○ などの類の型は windowsでのサポート状況に疑問があります。実際、Windows7 の Visual Studio 2019 で、gccならビルドできる下記の uintのプログラムをテストしてみたら、エラーになりビルド失敗しました(2022年1月26日に実験)。
戦闘中のアルゴリズム

コード例
戦闘中のアルゴリズム

実行結果
戦闘中のアルゴリズム

マイクロソフトの公式ドキュメントにuint8○○ などの類の型の紹介があるので、もしかしたら windows でも新しめの一部のバージョンでなら使用可能かもしれません。
戦闘中のアルゴリズム

なお、Windowsにはこれとは別に __int8 というのも存在します。
戦闘中のアルゴリズム

上記コードでは、構造体によってモンスターと味方パーティとが同一の構造体の配列に収まっていますが、実際のゲームではそのような事例は稀(まれ)でしょう。実際は、味方パーティのデータベースは戦闘以外でもアクセスすることから事前に存在しているので、その既存のデータベースをもとに、戦闘用の素早さ順の処理のための配列を作ることになるでしょう。
戦闘中のアルゴリズム

関数を使っていることもありコードは短いですが、しかし関数を使っているので、関数の「オーバーヘッド」というものにより処理速度は若干ですが低下しています。従って、そのような目的には適さないでしょう。
戦闘中のアルゴリズム

ポインタを使った処理は、おそらく高速化の目的だろうと思います。しかし関数のオーバーヘッドによる速度低下と効果が打ち消しあってしまいます。
戦闘中のアルゴリズム

以上、上記コードの解説は終わり。
戦闘中のアルゴリズム

さて、別のあるwiki編集者は、次のようなことを主張しています。
戦闘中のアルゴリズム

日本のIT用語で、並び換えをすることを「ソート」と言います。特に自動的に多くのものを何らかの基準に基づいて並び換えする場合、「ソート」という言葉を使います。
戦闘中のアルゴリズム

文献『ゲームクリエイターの仕事 イマドキのゲーム制作現場を大解剖』によると、ゲーム業界でもソートという用語が使われており、この文献では「マージソート」や「クイックソート」と言う用語が紹介されています。本来、「バブルソート」とは何種類もあるfor文によるソートのうちの一種です。クイックソートなど、バブルソート以外のソートがあります。
戦闘中のアルゴリズム

このようにソートは何種類もあるので、それらをひとまとめに「バブルソート」というのは厳密ではないですが、for文などを使って走査的にグループ内の要素全部を並び換えすることを慣習的に「バブルソート」と言いあらわすこともあります。「バブルソート」と言った場合、あるグループのものを並び換えする場合、主にfor文とif文などを使って、そのグループ内の要素全部を比較する方法です。
戦闘中のアルゴリズム

上記例のコードの場合なら、戦闘に参加している敵味方のメンバー全員を、素早さを基準に大小判定して、並び変えています。
戦闘中のアルゴリズム

このため、最低限必要なのは、
戦闘中のアルゴリズム

です。
戦闘中のアルゴリズム

また、判定結果を保管するために配列が必要になります。
戦闘中のアルゴリズム

下記コードは、ゲームのではなく、高等学校の『情報』教科の教員研修用資料(※web公開されている)にあるJavaScriptでのソートのプログラム例ですが、おおむね他のどのプログラム言語でも、バブルソートの構造は、下記JavaScriptのコードのように二重のfor文でif文を囲ったものになります。
戦闘中のアルゴリズム

文部科学省の上記のコードでも、for文、if文、配列、を使っているのが分かるかと思います。
戦闘中のアルゴリズム

また、ソートをするだけなら、ポインタなどは使う必要がありません。文部科学省のコードでも、ポインタ的な機能は使っていません。もっともそもそもJavaScriptなのでC言語のポインタは存在しないのですが。
戦闘中のアルゴリズム

念のため、文部科学省の公開している他言語版の研修資料でも確認してみましたが、同様の構造です。たとえばSwift版(iOS版)なら 『高等学校情報科「情報I」教員研修用教材 swift版(第3章のみ) - 20200716-mxt_jogai01-000001169_004.pdf』(※ 2022年2月6日に確認. )。
戦闘中のアルゴリズム

他にも文科省サイトではVBA版とかドリトル版とか公開されているのですが 、しかしさすがに昨今の一般のゲームはドリトルやVBでは制作しないと思われますので、割愛します。
戦闘中のアルゴリズム

さて、ゲームの話に戻ります。 配列に保管するのは数値なので、その数値が何を意味するかは、事前に決めておかねばなりません。たとえば保管内容「0」ならパーティ1番目のキャラ、保管内容「1」ならパーティ1番目のキャラ、のようにです。
戦闘中のアルゴリズム

また、けっして「敵どうしだけ」、「味方どうしだけ」でなく、敵と味方の両方を比較する必要があります。戦闘に参加してるのは味方だけでなく敵も参加者だから、です。
戦闘中のアルゴリズム

たとえば、味方3人、敵2匹なら、配列の要素の5個を使います。あらかじめ、配列で要素数20や30など、十分に要素数の大きい配列を1つ用意しておきましょう。
戦闘中のアルゴリズム

そして、この、たとえば要素数20の配列の先端5個ぶんの要素に、素早さの値を入れるわけです。
戦闘中のアルゴリズム

たとえば
戦闘中のアルゴリズム

のようになります。今後の説明のため、とりあえずこの配列の名前を「素早さ配列」とでも名づけておきます。
戦闘中のアルゴリズム

ともかく、このように、for文などを使って、まとめて入れましょう。
戦闘中のアルゴリズム

さて、並べ替えたい対象物は、けっして「素早さ」そのものではないです。なので、上で作った配列(「素早さ配列」)そのものは、並べ替えません。
戦闘中のアルゴリズム

行動するキャラクター・敵の順番を並べ替えたいわけです。(大学の教科書での「バブルソート」(後述)の説明などだと、本セクションでいう「素早さ」そのもの並び変えるような場合のアルゴリズムを紹介している場合もあります。なので、教科書をそのまま暗記するような態度は、少し要求事項が変わったときに対応できません。だから暗記ではなく、小さくて簡単なアルゴリズムを、ひとつひとつ組み立てて行って、高度なアルゴリズムを構築していくように理解・把握していきましょう。)
戦闘中のアルゴリズム

なので、ともかく、「素早さ」ではなくキャラクター・敵の順番を並び変えるためには、キャラクターまたは敵のIDが入った配列が新たに必要です。なので、そのキャラクターIDまたは敵IDの入った配列の呼び名をとりあえず「行動順配列」と言いましょう。ID番号を使わずにポインタでも処理だけなら可能かもしれませんが、説明が難しくなるのに本セクションの主題とは無関係なのと、商業ゲーム制作でも少なくとも仕様書などで敵モンスターには必ずID番号が登録されているのは有名な話なので、事前にID番号が仕様であるならそれを流用したほうが効率的でしょう。このID番号と仕様書の関係のように、ゲームの他の部分との擦り合せをしながらコードを書いていく必要があります。けっして「ほらこのコードで並び換えできる」とVisual C++ でのゲーム化確認すらしなくてコマンドプロンプトのコードを書いて終わりなのではありません。
戦闘中のアルゴリズム

ともかく、この行動順配列の内容がたとえば「3, 1, 5, 4, 2」だったら、
戦闘中のアルゴリズム

というような仕組みになります。
戦闘中のアルゴリズム

要するに私たちは最終的な目標として、「行動順配列」を作れればいいのです。そして、そのための手段として、「素早さ配列」を使います。
戦闘中のアルゴリズム

そして、「行動順配列」を作るために、「素早さ配列」の各要素の数値を「ソート」技術で比較します。ソートの技術は、一般的な情報科学の本に書いてあるので、それを参照してください。
戦闘中のアルゴリズム

一般に、2つの変数の数値を入れ替えるアルゴリズムがあります。コレを使うとラクですし、そもそもソートのアルゴリズムはコレを応用します。
戦闘中のアルゴリズム

まず、X=3, Y=5 を入れ替えたい場合、
戦闘中のアルゴリズム

そして、すばやさ比較をして、「素早さ配列のソートの結果と連動して行動順配列を変更する」のがテクニックです。(※ 一般のソートの教科書では、ひとつの配列しか入れ替えないので、なかなかコレに思い至らない。)
戦闘中のアルゴリズム

イメージ的にプログラムを書くと、
戦闘中のアルゴリズム

みたいな感じの作業を、すべてのキャラ同士の組み合わせで、for文を使って網羅的に行えばよいのです。
戦闘中のアルゴリズム

以上のように、ゲームプログラミングとは、段階的にアルゴリズムを組み立てていきます。実際に上記のような段階を一つ一つずつ、ゲームの実機上(たとえばVisual C++上プログラムやDXライブラリで開発したアプリなどで)で、確認していきます。
戦闘中のアルゴリズム

一般のプログラミングはどうか知りませんが、少なくともゲーム制作において、段階的にアルゴリズムをひとつひとつゲームとして妥当な動作かどうかを確認していかないことは、仕様変更などに全く対応できず、実用的な価値のない独り善がりなコードです。そういう独り善がりな人は大学などにスッこんでてください。
戦闘中のアルゴリズム

さて、上記コード例の場合、そのときの行動順配列で2番目と5番目のキャラを素早さ比較しており、もし素早さが高ければ、そのキャラを先にもってきています。
戦闘中のアルゴリズム

ただし、配列の「2」番と「5」番なので、日常の数え方では3番と6番のことです(配列は0から数え始めるので)。さて、for文の走査は単に、w:リーグ戦方式で、単に片っ端から走査していけばいいだけです。この方法をw:バブルソートといいます。
戦闘中のアルゴリズム

実際には、戦闘に参加している自陣営パーティのキャラが、必ずしもID順に並んでいるとは限りませんので、そのために復号する処理が必要です。たとえば、ドラクエ3やウィザードリィ・シリーズでは、登録した順番と、パーティのキャラクターの隊列の前後の順番とは違います。
戦闘中のアルゴリズム

つまり、たとえば、並び替え処理用で味方「1」番とされたキャラが、実際に登録IDが「13」番のキャラだったりするような場合もあるわけです。 並び替え処理用の味方2番のキャラは、たとえば登録IDが7番かもしれません。
戦闘中のアルゴリズム

なので、
戦闘中のアルゴリズム

のような、並び替え番号から登録ID番号への、復号の処理がさらに必要です。
戦闘中のアルゴリズム

その復号処理の際、並び替え配列には敵と味方が混在していますので、味方の番号だけを復号処理する必要があるので、そのための配列も追加で必要になりす。
戦闘中のアルゴリズム

そのため、復号処理中に扱っている対象が敵か味方かを記録しておくフラグ記憶用の配列が必要になります(下記コードでは PorEflag 配列。Party or Enemy のフラグ(flag)という意味)。あらかじめ、その配列もグローバル変数などとして用意しておく必要があります。
戦闘中のアルゴリズム

よって、上記の「// 行動順配列の入れ替え」などの一連のプログラムの後に、さらに、たとえば次のような敵味方の判別用フラグのための配列作成が必要になります。
戦闘中のアルゴリズム

なお、復号は、並び替え処理側の関数でなくとも、その関数(並び替え処理関数)の呼び出し側関数(「並び替え処理関数」とは別の関数)でも可能です。呼び出し側の関数の都合によって復号のコードは違うので、復号のコードの具体例の詳細については省略します。
戦闘中のアルゴリズム

この復号も、けっこう難しいプログラムになり、初心者にはハードルが高いですが、頑張りましょう。
戦闘中のアルゴリズム

一般にRPGにおいて、戦闘に参加するのはパーティとして引き連れているキャラクターですので、 つまり、ソート結果をもとに適切なパーティ加入中キャラを呼び出し、さらにそのパーティ加入中キャラのIDをもとに内部データベ-スの登録キャラのIDにアクセスするという手続きが必要になり、これまた難問です。いやまあ、配列で書けば、せいぜい
戦闘中のアルゴリズム

のような入れ子になった配列のコード1つで済むのですが、しかし実際にこれをプログラミングしようとすると、デバッグ中に入れ子になった各パラメータを追跡する手間があるので、けっこう大変です。よって「酒場」・「冒険者ギルド」方式への対応は、初心者には敷居が高いです。
戦闘中のアルゴリズム

戦闘で各ターンのコマンド入力が終わったら、今度は、自動的にそのターンの戦闘が始まらなければいけません。
戦闘中のアルゴリズム

そして、1~2秒くらいおきに、たとえば
戦闘中のアルゴリズム

みたいに秒の経過によってメッセージが自動進行する必要があります。
戦闘中のアルゴリズム

このような自動進行の処理のため、WindowsAPIならタイマーを呼び出す必要があります。タイマーは、オペレーティングシステムが管理しています。(DXライブラリでは方法が異なるが、とりあえず説明の都合で、WindowsAPIの場合を先に説明する。)
戦闘中のアルゴリズム

オペレーテイングシステムの種類によって、タイマーの呼び出し方は異なります。Windows API の場合、 SetTimer 関数でタイマーを呼び出せます。SetTimer 関数で指定した時間が経過するごとに、case WM_TIMER ラベルが呼び出され、ラベル内のプログラムを実行します。この case WM_TIMER ラベルをWindows API の、WM_PAINT などのある位置の前後に作る必要があります。
戦闘中のアルゴリズム

さて、case WM_TIMER ラベルが書けたら、今度はそこに、さきほどの素早さの処理で作成した行動順配列の順番に基づき、戦闘に参加している各キャラが行動する必要があります。
戦闘中のアルゴリズム

コードは、下記のようなイメージになります。(イメージですので、下記のままでは動きません。)
戦闘中のアルゴリズム

説明の簡単のため、for文を使わないでコードを書いています。また、味方の死亡を無視しています。
戦闘中のアルゴリズム

なのに敵の死亡だけ上記コードで考慮してあるのは、戦闘を有限ターンで終了させるためです。本当は上記コードにさらに敵の死亡判定のためのコードが加わったり、敵全滅時の自動進行のコードが加わりますが、説明の単純化のために除去してあります。
戦闘中のアルゴリズム

そのほか、クリティカルヒットやミスなどの判定も無視しています。敵のAIも無視して、たとえば、敵の(味方への)攻撃対象は、あらかじめパーティ最前列の戦士だけを攻撃するように決めてあるとします。
戦闘中のアルゴリズム

さて上記コード例で「行動者が味方側の場合」と「行動者が敵側の場合」とでif文や関数を別々に分けている理由は、
戦闘中のアルゴリズム

参照先のデータベース(または構造体)が、それぞれ異なっているからです。
戦闘中のアルゴリズム

味方キャラのデータベースを参照するか、それともモンスターのデータベースを参照するかの違いがあるからです。
戦闘中のアルゴリズム

このように、文章だけなら一見すると同じ「○○の攻撃」という動作であっても、参照データベース(あるいは参照先の構造体など)が異なっていれば、実質的に別々の命令文になります。
戦闘中のアルゴリズム

上記コードの重要ポイントは、たとえば TimerFlag という変数を用意して、指定時間の経過ごとに case を呼び出した時に、このTimerFlag フラグと同じ番号(行動順配列での通し番号)のキャラだけが動くように設計している事です。通し番号の異なる別番号のキャラのIf文ブロックはマスク(遮蔽)されており、別キャラは行動しないようになっています。
戦闘中のアルゴリズム

そして、このTimerFlagが、行動順配列の各キャラの行動ごとに、TimerFlagの値が順番どおりに1アップしていくようにしておけば、よいのです(説明が難しい。要するに、こういう感じでRPG戦闘シーンでの自動処理が実装できる。実際に Visual C++ でやればワカル)。
カウンター攻撃に対するカウンター攻撃の問題

実装はだいぶ先になるでしょうが、たとえばドラクエの「マホカンタ」や、ファイナルファンタジーの「リフレク」のように、攻撃をカウンターするスキルがある場合、
カウンター攻撃に対するカウンター攻撃の問題

どのゲームでも、一度カウンターされた攻撃を同一ターンの同一攻撃にて再度カウンターすることは、プログラミング的な事情により不可能です。
カウンター攻撃に対するカウンター攻撃の問題

背理法で考えると分かります。
カウンター攻撃に対するカウンター攻撃の問題

つまり、仮に、カウンター攻撃に対しての、さらなるカウンター攻撃が可能だと仮定しましょう。
カウンター攻撃に対するカウンター攻撃の問題

そして、敵パーティ・味方パ-ティの双方がともにカウンタースキルを発動していたとして、誰かの攻撃にカウンターに対してカウンターが必ず発動するとしましょう。
カウンター攻撃に対するカウンター攻撃の問題

説明の簡単のため、味方から敵に攻撃開始したとしましょう。
カウンター攻撃に対するカウンター攻撃の問題

すると、まずは
カウンター攻撃に対するカウンター攻撃の問題

となります。
カウンター攻撃に対するカウンター攻撃の問題

しかし、決してここで終わりではなく、背理法の仮定により、
カウンター攻撃に対するカウンター攻撃の問題

ことになります。
カウンター攻撃に対するカウンター攻撃の問題

当然、さらに背理法の仮定により、
カウンター攻撃に対するカウンター攻撃の問題

となり、攻撃がこのあと味方に向かうので、段階Bがこのあと起きます。
カウンター攻撃に対するカウンター攻撃の問題

よって、段階Bと段階Cとを永遠に繰り返すことになってしまいます。いわゆる「無限ループ」です。
カウンター攻撃に対するカウンター攻撃の問題

このため、つまり無限ループ防止のため、普通のRPGではカウンター攻撃は絶対に1回しか反射しません。
カウンター攻撃に対するカウンター攻撃の問題

もし数学に例えると、高校数学における、公比(-1)の等比数列が絶対に収束しない問題と同じです。
カウンター攻撃に対するカウンター攻撃の問題

だから、どうしても何度でも反射する仕様にて、カウンターの攻撃対象を収束させたいなら、公比の絶対値を1未満にすれば原理的には可能です。
カウンター攻撃に対するカウンター攻撃の問題

しかし、ゲームでそこまでする必要があるかどうか。