まえがき

実行してジャンプするプラットフォーマーゲームを作成している場合は、既にAIを追加することを考えているかもしれません。 対戦相手、プレイヤーが追いかけなければならないオブジェクトなどを制御できます...そして、単純化のために、実装プログラマーはスマートAIを拒否することが多すぎます。レベル。

この記事では、マップ上の任意の静的な場所にAIを送信できる手法を紹介します。 選択されたAIパスは、正確に選択された時間での多くのジャンプを必要とするか、このパスが静的ポイントで開始および終了する場合、シーンの一部をバイパスする必要があります（ただし、この条件は必ずしも必要ではありません）。

主なアイデアを検討し、完全な実装を作成します。 プラットフォームの移動や破壊可能な壁など、より複雑なケースについては、別の記事で検討します。

この手法はNomeraゲームで使用されています。www.dotstarmoney.comまたはTwitterを参照してください。



開始する前に、マップの単純化されたジオメトリに一致するより単純なアルゴリズムを実装できるかどうかを確認してください。 たとえば、正方形のグリッドによってレベルの競合が認識された場合（ほとんどの2Dゲームのように）。 そのような場合、より単純な手法を使用して、AIパスの信頼できる検索を実装できます。 私の方法は、主に、より「人間的な」AI動作を望む人に適しています。

準備する

作業を開始する前に、 数学的グラフとグラフトラバーサルアルゴリズムに関する知識を更新しておくと便利です。 また、表面に沿った距離の前処理と決定には、ベクトル演算の十分な理解が必要です。

この手法は、移動中のオブジェクトを含むレベルの静的な部分で主に構成されるレベルに適用され、常にオンザフライで変化するレベルには適用されません 。 線分として静的レベルの衝突データにアクセスすることが重要です。 これにより作業が簡単になりますが、この手法は簡単に拡張して、衝突に使用される幾何学的オブジェクトをサポートできます。

主なアイデア

簡単に言えば、あなたは開発者として、レベルを移動してプラットフォームにジャンプし、エンジンはプラットフォームにジャンプ/フォールした時点で使用されたユーザー入力を記録して、次の時点に到達するまで待機します。 このデータは、プレーヤーの記録された入力が保存される「エッジ」と見なされます。 AIがレベルを通るパスを作成する場合、一連のプラットフォーム（以降、これらをノードと呼びます）を頂点として処理し、それらの間のエッジをグラフとして記録します。 その後、AIが進み、さまざまなノードを移動し、エッジで記録された入力を使用してエンドポイントに到達します。 さらに多くの重要な詳細を検討する必要がありますが、最初はより一般的な概念に焦点を当てます。

使用する手法は、2つのアルゴリズムの組み合わせになります。 これは、パスグラフを作成する 、または「AIがレベルを通るパスを見つけるために使用するデータ構造を作成する」とパスグラフをバイパスする 、または「レベルに沿って敵を特定のポイントに誘導する」です。 明らかに、2番目のアルゴリズムは2番目のアルゴリズムに必要です。 パスグラフの作成は、次のように説明できます。

1. レベル衝突の静的データをロードし、それらからノードのセットを計算します。
2. レベルに記録されたすべてのエッジ（パス）をロードし、対応する開始ノードに追加します。
3. 衝突のモデルと敵の動きのパラメータを使用して、ノード間のパスを記録し、グラフに追加します。
4. レベルを終了したら、そのレベルで記録されたエッジをエクスポートします。

これは理解できないように思えるかもしれませんが、以下でアルゴリズムを詳細に分析します。 これで、ステージの一般的な概念を理解できました。

そして今、 パスグラフ走査の一般的なビュー：

1. 最終ノードの形式で終点を取得し、このノードの方向の距離を取得します。 初期（初期）ノードの同様のパラメーターを計算します。
2. ソースからエンドポイントまでの任意のグラフトラバーサルアルゴリズムを使用してパスを計算します。パスはノードとエッジのセットです。
3. ノードを介してAIをエッジまで描画します（または、実行することにより（つまり、AIが認識している任意の動きにより））、パス上の次のエッジの望ましい初期速度を達成します。
4. AIが特定の位置と速度の許容範囲でパス上の次のノードの開始点に到達すると、AIの自動制御をオフにし、エッジのフレームごとの入力データを介して制御を実行します。
5. 記録された入力データが終了すると、AIが存在するノードの自動移動に制御を戻します。
6. 終点に達するまで最後の3つのステップを繰り返します。

すでに理解し始めていますか？ 各ステップを詳しく見てみましょう。

段階的なパスの検索を実現します

パスグラフの作成

パスグラフは、レコード/エッジで接続されたプラットフォーム/ノードで構成されます。 プラットフォームとレコードを明確に定義することが重要です。

ノード/プラットフォームには次のプロパティがあります 。

• これは、レベルジオメトリを形成するラインセグメントのサブセットです。
• 通常の重力では、ノードのすべてのセグメントは、最初の頂点が2番目の頂点よりも厳密に小さいx座標を持つように方向付けられます（重力が反転すると、状況は逆転します）。
• ノードの後続の各セグメントは、最後のセグメントが終了するところから始まります。
• ノードの各セグメントは、その表面上を歩いてAIを渡すことができます。

これにより何が得られますか？ 次の重要なアイデア： ノードは、ジャンプまたは落下することなくその表面に沿って移動するAIによって完全に移動でき、AIは他のポイントからノードに沿った任意のポイントに移動できます。

レベル衝突ジオメトリの画像は次のとおりです。


そして、これはそこから抽出されたノードの画像です（明確にするために、それらは数字と異なる色でマークされています）。 私の実装では、レイヤーのロード時にノードの抽出が実行されます。 したがって、レベルが既に構築されている場合、戻って表面にマークを付ける必要はありません。 本質的に、これは「私たちが歩くことができるすべての表面」の抽出であることに気付くでしょう。


注： この画像には小さなエラーがあります。26と1は異なるノードですが、ご覧のとおり、1つでなければなりません。

レベルジオメトリの格納方法によっては、任意のラインセグメントを接続されたノードに変換するために少し余分な処理が必要になる場合があります。

もう1つの重要な点： ノードに沿って移動するのが困難な静的なジオメトリがある場合（たとえば、床に触れない壁）、この障害物によってノードを分離する必要があります。 私の例ではそうではありませんが、そのようなチェックを実行しないと、深刻な合併症につながる可能性があります。

ノードを受け取ったら、パスグラフを作成する最初の段階を完了します。 また、状況を定量化する方法を決定する必要があります。 パスを検索するときに開始点と終了点を決定する際に使用する位置は、ノード（この場合は番号）と、このノードに沿った左端点に対する水平変位です。 ノードに沿った円弧の長さではなく、水平方向の変位が発生するのはなぜですか？ AIコライダーが平らな表面に沿って上昇する勾配の方向に走る正方形または円であるとしましょう。 その表面は斜面の内側のコーナーポイントに接触できますか？ いいえ。したがって、位置は水平変位として測定されるため、水平変位は「曲線状の水平線」と見なすことができます。

2番目と3番目の段階を完了するには、エッジ/レコードとは何かを決定する必要があります。

リブには次のプロパティがあります。

• エッジには、2つの異なるノードに開始位置と終了位置があります（ただし、ジャンプを使用してプラットフォームにカットを作成する場合は、1つのノードにすることができます！）
• エッジにはフレームごとに記録されたデータのセットがあり、初期位置と初期速度のエッジでAIを指定すると、AIは最終位置によって決定される位置に向けられます。

ここでは、次の点に注意する必要があります。フレームごとに記録された入力の生成セットには、パスが作成されるAIとして、衝突とモーションの同じプロパティがあることが絶対に必要です。 ここでの大きな問題は、フレームごとに記録されたデータがどこから来るのかということです。 正しい答えは開発者からです！

ここにジャンプがあります：
ノメラゲームエンジンの開発者モードでは、記録を有効にできます。つまり、プレーヤーがノードからジャンプするか、ノードから落ちるとすぐに、ノードは、落下/ジャンプした位置に等しい開始位置で作成されます。 この瞬間から、ユーザー入力はフレームごとに記録されます。 プレイヤーが自由落下/ジャンプからノードに着地すると、記録は終了し、開始ノードと現在のノードの間のエッジとして追加されます（もちろん位置付き）。

つまり、プレイヤーの記録された入力の断片が作成されます。 AIが初期位置に設定されている場合、AIはこの入力に制御を移して最終位置に到達できます。

また、衝突やプレーヤーの動きのプロパティを記録するとき、即座にAIプロパティに切り替え、そのプロパティを記録したAIのみがエッジを「ピックアップ可能」としてマークすることも重要です。

パスグラフを作成する2番目のステップは、以前に作成したすべてのエッジをロードすることであり、3番目は書き込みプロセス自体です。 記録方法は完全にあなた次第です。 画面にリブが描かれたノメラのスクリーンショットです。 線は初期位置と最終位置のみを接続し、パスを追跡しませんが、テクニックを明確に説明します。



左上隅には、エッジのゲーム内エディターのメモが表示されます。 気に入らない、またはAIが考慮に入れないエッジを削除できます。 また、入力が記録されたフレームの数も表示されます。

もちろん、エッジには、記録されたフレームや最終位置を持つ開始フレームよりも多くのプロパティが必要です。 前に言ったように、rib骨の始めの速度は重要であり、これは後で明らかになります。 また、最終位置への最短経路を見つけるのに役立つため、エッジが占めるフレーム数に便利にアクセスできると便利です。

この段階では、プラットフォームノードのパスとそれらを接続する記録されたエッジのグラフを作成する知識が既にあります。 ただし、より興味深いのは、このグラフを使用してAIがナビゲートする方法です。

パスグラフトラバーサル

パスグラフの使用を開始する前に、実装について少し説明します。 基本的にパスに沿ってAIアクションを記録しているので、プレイヤーのインターフェースに似たインターフェースでAIを制御できると便利です。 次のようなプレーヤークラスがあるとします。

class Player{ public: // ... void setInputs(int left, int right, int jump); // ... private: // ... } 

キーボードから「左、右、ジャンプ」と入力します。 まず、これらはエッジの記録中に記録する値です。 第二に、AIにはsetInputs管理インターフェースも必要なので、REALインターフェースを作成してみませんか？ 次に、コードはよりモジュール化されます。

 enum PC_ControlMode{ MANUAL, RECORDED } class PlatformController{ public: // ... void setManualInput(int left, int right, int jump); void bindRecordedInput(RecordedFrames newRecord); int getLeft(); int getRight(); int getJump(); void step(timestep as double); // ... protected: PC_ControlMode controlMode; RecordedFrames curRecord; void setInputs(int left, int right, int jump); // ... } class Player : public PlatformController{ // ... } class AI : public PlatformController{ // ... } 

現在、AIとプレーヤーの両方のクラスは、拡張され、手動コントロールと記録済みコントロールを切り替えることができるインターフェースを使用して制御されます。 このようなスキームは、プレイヤーがコントロールを失う、事前に記録されたカットシーンにも便利です。

さて、AIコントローラーにはブラックボックススタイルのメソッドが必要です。

 createPath(positionType destination); step(double timestep); 

最初の行は現在の位置と終了位置の間のパスを設定し、2番目の行は入力をsetInputs（）に渡してAIを終了位置に移動します。 アルゴリズムの段階的なプレゼンテーションでは、 createPathは最初の2つのステップを実行し、最後の3つのステップを実行します。 パスの作成を見てみましょう。

パスは、エッジから始まり、最後のノードに至る最後のエッジで終わる、異なるノードとエッジの順序付けられたシーケンスで構成されます。

最初に、現在位置が空中にあるかノードにあるかを判断できる必要があります。 ノードにいるとき、このノードへのリンクとそれに沿った水平位置が必要です（一般的な位置を思い出してください？）。

パスを構築するには、グラフトラバーサルアルゴリズムを使用します。 私の実装では、ダイクストラのアルゴリズムを使用しました。 格納されたノードごとに、そこにあるエッジを選択することで、自分が見つかった位置も格納します（将来の世代では、 edgeStartNodeCurrentPositionXと呼びます）。 したがって、特定のエッジのエッジの重みは次のように計算されます。

 edgeFrameLength =      walkToEdgeDist = abs(edgeStartX - edgeStartNodeCurrentPositionX) edgeWeight = edgeFrameLength * TIMESTEP + walkToEdgeDist / (HORIZONTAL_WALKING_SPEED) if(edgeDestinationNode == destinationPositionNode){ edgeWeight += abs(edgeEndX - destinationPositionX) / (HORIZONTAL_WALKING_SPEED) } 

ご覧のとおり、最終エッジの重みは秒単位で表され、書き込みに費やした時間とエッジの先頭まで歩いて費やした時間の合計です。 この計算は不正確であり、敵の動きにランニングが使用されている場合は異なります。 また、最終ノードにいるかどうかを確認し、そうであれば、リブの最終位置からパスの最終位置までの歩行時間がウェイトに追加されます。

エッジの重みを計算できる場合、ダイクストラアルゴリズムを適用できます！ （または、「最終位置までのユークリッド距離」などのヒューリスティックを使用する場合、他のグラフトラバーサルアルゴリズムA *はここで適切です）。

この時点で、方法があるはずです！ アルゴリズムの4つの段階をほぼ完了し、完了しました。 基本的に、エッジがノード内にあるか、記録によって制御されるかに応じて、2つの手順を切り替えます。

結び目がある場合は 、現在の位置からrib骨の方向に進みます。これは次に必要です。 先に述べたように、記録されたエッジの初期速度も知る必要があります。 多くの場合、AIは歩行の開始時または終了時にわずかな加速または制動を行うために必要です。 これらの遷移速度の1つは、ターゲットエッジの開始点になります。 したがって、rib骨の開始点に移動するとき、走行/歩行の開始に備えるために、少し減速したり、速度を上げたりする必要がある場合があります。

移動するrib骨の初期位置に達すると、おそらく、私たちの位置はto骨の初期位置に正確に対応しません。 私の実装では、位置がピクセルを超えることはめったにありませんでした。 重要なことは、一定の許容範囲でrib骨の初期位置に到達し、到達するとすぐにAIの位置/速度をrib骨の初期位置/速度に変更することです。

これで、rib骨の制御を移す準備ができました。

エッジにいる場合、各フレームはエッジの記録によって送信された制御を単に受け取り、読み取られる記録されたフレームの数を増やします。 そしてそれだけです！ 遅かれ早かれ、記録は終了し、フレームの前で正確だった場合、AIは次のノードにあり、制御がノードに転送されます。

追加

ゲームでこの手法を構成するには、いくつかの変更を加えることができます。

パスを記録および消去するためのゲーム内インターフェイスを追加することを強くお勧めします。これは、レベルに沿って移動するためのパスを簡単に作成するのに役立ちます。ノメラでは、レベルパスの作成には約10分かかります。

ノードの自動抽出を提供することも便利です。 技術的には自分で実行できますが、自動抽出を追加すると、ワークフローが非常に簡単になります。

ノードのパラメーターをすばやく取得するために、Nomeraはすべてのノードをハッシュテーブルに、すべてのエッジを各ノードのリストに保存します。 表示を簡単にするために、エッジも共通リストに保存され、画面上でラインの開始/終了ポイントを表示できます。

まだ気付いていない場合、階段やロープなど、衝突のあるオブジェクトではない静的なインタラクティブ要素は、この手法によって自動的に処理されます。 たとえば、階段を上るには「上」を押す必要があります。「上」を押すとAIが上記のようなインターフェイスを使用すると、入力データを登録して登ります。

まとめると

衝突ジオメトリに関係なく機能するプラットフォームレベルでAIを実行する方法を学びました。 これにより、AIはプラットフォーマーのすべての制御可能性を活用できます。 まず、レベルのパスグラフを生成してから、グラフのパスを作成し、最後にそのパスに沿ってAIを実行しました。

しかし、それは機能しますか？ どのように機能しますか？ ここにgifがあります：


これらの人は「ハグモード」にあります。 どこへ行っても彼らは私に近づこうとしています。

ご質問やご提案がありましたら、chris @ dotstarmoney.comまでご連絡ください。 読んでくれてありがとう！