LabVIEWでのプログラミングのオリンピック。 勝利チームの決定

戦車に関するコンピューターゲームは、ゲーム業界で最も人気のあるゲームです。 そのようなゲームの歴史は数十年前に遡りますが、その人気は衰えることはありません。 戦車と戦車戦のテーマは、コンピューターゲームだけでなく、プログラミングにおける競争プロセスの対象でもあります。 たとえば、2012年にロシアのAIカップ-CodeTanksプログラミングコンテストが開催されました。 参加者は、人工知能タンク制御の開発に招待されました。 数年後、この競争が繰り返されました。 主催者はナショナルインスツルメンツで、毎年学生と若い科学者の間でLabVIEWプログラミングオリンピックを実施しています。 2015年のオリンピックの参加者は、LabVIEWツールを使用してタンクの自律制御のアルゴリズムを開発するよう招待されました（このプログラミング環境の概念については、リンク「LabVIEW-First Acquaintance」を参照してください）。 この記事では、LabVIEWPortalチームが受賞した戦車アルゴリズムについて説明します。

チームについて

志を同じくする人々のLabVIEWPotralチームは、伝統的にプログラマの競争に参加しています。 2011年、パフォーマンスは成功し、 チームは1位になりました 。 2015年のオリンピックでは、チームは成功を繰り返しました。 ポータルから3人のチームが編成されました。 チームメンバーはさまざまな都市やタイムゾーンに住んでいるため、一部の困難は領土の遠隔性に代表されます。 しかし、問題を探すのではなく、問題を解決する方法を探す必要があります。チームはこれにうまく対処しました。

入力データ

次のパラメーターが順番にプレーヤーに渡されます。
1.戦場のパラメーター（寸法、障害物の説明：障害物の極値の座標とその残存強度）;
2.タンクのパラメーター（寸法、船体と砲塔の回転速度、動き、砲弾の速度など）;
3.現在発射されている砲弾の説明（砲弾の現在位置の座標、速度ベクトル、砲弾を発射したプレイヤーの数）;
4.障害物の説明（障害物の極値の座標と残りの強度）;
5.戦車の現在の状態（船体の中心の座標、船体と砲塔の回転角度、残存強度、残存リロード時間）;

一定の時間内に、プレイヤーは決定を下し、戦車本体の動作（移動または回転）、戦車タワーの相対的な回転角、および射撃するかどうかを示す必要があります。 割り当てられた時間内に決定が行われない場合、プレーヤーの機能は中断され、他のプレーヤーに移動します。 勝者は、敵の戦車を何とか破壊したか、ラウンドに割り当てられた時間の後、敵よりも安全余裕がある人です。 損傷は、砲弾のみによって引き起こされます（戦車が互いに衝突した場合、または壁に衝突した場合、損傷は生じません）。 バトルモード：1対1で、バトルのマップは事前にわかりません。

戦略開発

戦闘戦術の最初の選択肢の1つは、連続射撃と、壁を迂回して敵への最短経路に沿って移動することでした。 しかし、いくつかの一般的な経路探索アルゴリズム（波動アルゴリズム、凸多角形法、A *探索アルゴリズム）のパフォーマンスを分析した結果、私たちの戦車は状況のその後の分析で動きの軌道を計算する時間がないかもしれないという結論に達しました。 この戦術は、「待機、撃ち、機動」というより単純なオプションを支持して放棄されなければなりませんでした。

待って、撃つ ：壁に関係なく、敵の中心で撃ちます。なぜなら、それらはシェルによって徐々に破壊されるからです。 それぞれの動きは、タワーが敵の中心を正確に見えるようにタワーの位置を調整します。
機動 ：戦車の船体は射線に対して垂直です。 この位置から、敵の砲弾を回避するのが最も簡単です。 この点で、危険がない限り、すべての動きは体の回転角度を調整します。 したがって、回避操作は、タンクを前後にロールすることにあります。方向の選択は、意図するヒットの場所（タンクの前部または後部）によって異なります。

ただし、予選中に、戦略の2つの重大な欠点が発見されました。

• 場合によっては、発射体からの操作が「壁への乗車」につながりました。
• 一部の壁は全体的な操作を妨げました。

これらの欠陥は、いくつかのチェックと条件を追加することで対処されました。

• セーフモード 戦車と敵の間に複数の壁がある場合、必ずしも邪魔にならないで最も近い壁を撃ちます。 これは重要なポイントです。敵が開いた射線に入ったときに船体がどのように回転するかは不明です。
• 危険なモード 。 戦車と敵の間に2つ未満の壁がある場合、敵の中心にあるタワーを回し、連続して撃ちます。
• 回避 。 敵の砲弾が戦車に飛び込んだ場合、衝撃点、つまり「前/後」部分を計算します。 次に、移動の方向を選択し、どれだけシフトする必要があるかを評価します。 進行方向に壁との衝突がある場合、反対方向に移動します。 シェルが侵入する危険があるまで後退します。 シェルをチェックするとき、壁が考慮されます。 したがって、壁に衝突することが保証されている発射物は無視されます。

モードに関係なく、射線（戦車の中心を結ぶ線）に垂直になるように船体の角度を調整します。

プログラムコードとアクションのアルゴリズムの詳細な説明

プログラムコードの一般的なビュー：



初期データの分析の予備段階（メインサイクルが完了する前）で、破壊された壁とそのシェルはふるいにかけられます。 以下は戦略の選択です。 私たちが危険地帯にいるなら、


敵が壁の後ろに隠れた場合、タワーを最も近い壁に戻したり戻したりするのに時間がかかり、戦闘状態での余分な時間の浪費は受け入れられないため、セーフモードに戻りません。
ゾーンが安全な場合、2つのチェックを実行します。
1.戦車と敵の間の壁の数。
2.タンクと各シェルの間の壁の数。




セキュリティ上の理由から1つの壁が選択されています。「シールド」がほとんど残っていない場合は、時間を節約するために敵に向かってタワーを前に回す必要があります。 タンクと敵の間の壁の確認は以下に示されており、タンクと発射体の間の壁の確認と同じ機能を使用します（セグメントの異なる端のみ）。



「シールド」の数の検索機能については、以下で説明します。

砲弾は周期的に整理されますが、発射体の危険は船体の中心ではなく、衝撃の点でチェックされます。 理由：角を曲がったところから発射する「cな」敵。



計算を簡単にするために、タンクは船体の周囲に外接する円と見なされます。 ヒットポイントは、発射ラインとタンクの中心からこのラインまでの垂線の交点です。 さらに、原点はタンクの中央に移動します。

線Ax + By + C = 0の場合、原点からの垂線の点は次の式で計算されます。
x0 =-AC /（A ^ 2 + B ^ 2）
y0 =-BC /（A ^ 2 + B ^ 2）

なぜなら タンクの中心の座標の原点、ヒットを確認するには、セグメントの長さを計算する必要があります[（0,0）（x0、y0）]。 長さがタンクの「半径」より短い場合、発射体は危険です。

次に、距離が計算されます。この距離は、発射体からの操作中に移動する必要があります（これは後で必要になります）。

次に、衝撃のエリアが決定されます：タンクの前部/後部。 これを行うには、直線（（0,0）（x0、y0））が0x軸に対して相対的に位置する角度を計算します。 計算を単純化するために（将来、同様の角度が必要になります）


この直線とタンクの移動方向との間の角度がπ/ 2未満の場合、前部に当たります。それ以外の場合は後部に当たります。

行う必要がある最後のテストは、砲弾が戦車に飛び込むかどうかです。 戦車の最初のバージョンは飛行方向を考慮していなかったため、戦車は安全な砲弾から脱出しようとしました。

チェックは次のように実行されます：発射物はベクトルの開始と長さ（コンポーネント単位）で与えられるため、これによりベクトルの開始からタンクの中心までの距離と、ベクトルの終了からタンクの中心までの距離を計算できます。 ベクトルの端がタンクに近い場合、発射物は私たちの方向に飛びます。



次に、存在する壁シールドの数を確認します。 検証は、安全なシェルを含むすべてのシェルで実行されます。
各壁はセグメントです。 別のセグメントは、船体の中心または衝突点と敵または発射体の中心の間に構築されます。 次に、これらのセグメントが交差するかどうかがチェックされます。 検証アルゴリズムは、リンクgrafika.me/node/237の記事から取得されています。 その本質は、セグメントのさまざまな端を接続するベクトルのベクトル積の分析にあります。




すべての壁はサイクルでチェックされ、最初の危険な発射体はブレークポイントと見なされます。状況はすでに危険であるため、さらにチェックする意味はありません。 したがって、敵の前に2つ未満の壁が残っている場合、または砲弾（壁で覆われていない）が戦車に飛び込む場合、攻撃を続ける必要があります。そうでない場合、将来の操縦のために最も近い壁の破壊が続きます。

壁攻撃（セーフモード）

最初に、身体の回転角度が調整されます。 次に、x軸との直接的な「敵の戦車」の角度は、ベクトルとそのOx軸との角度を見つけるための上記の関数を使用して決定されます。



ハウジングの回転角度の決定は次のとおりです。



ここでは「左右」は重要ではないため、2つの角度のうち、小さい方が絶対値で選択されます。



撮影の場合のように、システム（プログラムアービター）が目的のアクションを示すことは注目に値します：すぐに全体の角度を変えて、ショットをします 次に、システムは必要な許容部分を実行します：許容回転、ショット（銃がリロードされた場合）。

並行して、タンクの中心からすべての壁までの距離が計算され、最小値が選択されます。



壁を選択すると、その中心が決定され、どこで発射されます。 いくつかの最小値がある可能性があることに注意する必要がありますが、システムは最初の最小値を順番に出力します。 1つの壁（緑の方向）が破壊された後、次に近いものが選択されます。 理論的には青いかもしれませんが（距離が等しいと仮定して）、遠くの壁（赤い線）が次の順番になる可能性があり、いくつかのショットが他の壁に行く間、塔はそれに長い時間回転します。 必要に応じて、大砲に最も近いものが最も近い壁から選択されるように、選択肢を絞り込むことができます。


壁までの距離は、ポイント（タンクの中心）からセグメントまでの距離です。 場合によっては、最も近いポイントが、指定されたセグメントと垂線、場合によってはセグメントの端の交点になることがあります。
ベクトルのスカラー積を使用します。その符号は、ベクトルの同一方向に関する情報を提供します（アルゴリズム全体はコードコメントに記述されています）。




次に、Ox軸と接続セグメントの間の角度が決定され（他のセグメントのみ）、タレットの回転角度が計算されます。


次に、ターンが近いかどうかを確認します：時計回りまたは反時計回り。

敵戦車攻撃アルゴリズム

船体と砲塔の回転角度は、上記の方法で計算されます。 次に、最初の危険な発射体が特定され、発射体の衝撃点を考慮して、「より良い」方向に操縦が実行されます。 ただし、後退の障害がないことを確認する必要があります。 危険なシェルがなければ、船体を回転させます。

障害物の有無のリトリートの確認

発射体の危険性をチェックするときに、移動する必要がある距離を計算しました。 タンクの現在の位置を黒で、最終位置を灰色で示します。 このようにして、長方形が得られ、その側面はタンク船体の側面であり、前面は船体の前面の現在の望ましい位置です（青枠）。 この長方形が壁を定義するセグメントのいずれかと交差するかどうかを判断する必要があります。



交差を決定するために、Cohen-Sutherlandアルゴリズムが使用されます。その説明は、次のリンクにあります： en.wikipedia.org/Cohen_ Algorithm_ — Sutherland）。 タスクを簡素化するには、次の手順を実行します。

• 前方への動きがx軸に沿うように座標軸を回転させる
• タンクの前面への原点の移動。

したがって、チェックする長方形は次のようになります。

• 水平セグメントy = +-s / 2（タンクの幅の半分）;
• 垂直：x = 0、x = godist（カバーする必要がある距離）。

次に、チェック時にすべてのセグメント壁を回転およびシフトする必要があります。 各壁は個別にチェックされます。



ここで、長方形に対する点の「右」、「左」、「上」、「下」の位置は、xおよびyコンポーネントを長方形の境界と別々に比較することによって決定されます。



交差点が見つかった場合、チェックは完了し、この方向に移動することは不可能です。正確に選択された速度の兆候については、「フルスロットル」を示します。

おわりに

提案されたプログラムコードは、開発、テスト、デバッグのプロセスに時間がかかったため、最適であると主張していません。 また、アルゴリズムの一部はヘッドから取得され、一部はインターネットから取得されたものであり、チームは使用されたアルゴリズムの原作者を決して侵害しないことに注意する必要があります。 戦闘の過程で、戦車はアルゴリズムに従っていない場合があり、壁に「スタック」しました。 それにもかかわらず、LabVIEWPortalチームのインテリジェントなタンク制御システムが最高であることが証明され、オリンピックで1位になりました。 リンクでトーナメントの主な戦いのビデオを含むプレイリストを見ることができます： www.youtube.com/playlist?list=PLKDkvzW_BvvH36vPdeiGKRvmhcZrjMseD

ご関心をお寄せいただきありがとうございます。フィードバックをお待ちしております。