ムーブボロノイ

序文の代わりに

グルジアの非ロシア語学校でのロシア語レッスン。

先生：

-Dati、これは理解することは不可能です。これは覚えておく必要があります。FROMYOUは別に書かれています。

KVAS-一緒に。

ここで冗談が取られます 。

はじめに

この記事は、RPG要素を備えたターンベースの戦略ゲームであるWesnothゲームに触発されました。 このゲームでは、キャラクターは六角形のポリゴンで構成されるマップ上を動き回ります。 したがって、四方を囲まれたキャラクターは、6人の敵キャラクターに攻撃されます。 このため、ゲームの戦術的な要素は非常に重要です。 疑問が生じました：ポリゴンの固定ジオメトリを持つマップから任意のジオメトリを持つマップへの移行は、ゲームプレイにどのように影響しますか？



この投稿では、ランダムなゲームカードとして「ボロノイ図」を使用する可能性について書くことにしました。 ネットワーク上でボロノイ図を構築するためのアルゴリズムの説明をいくつか見つけました。 しかし、私が偶然読んだものはすべて、表面的なものであるか、アカデミックな言語で書かれています。 一般に、アルゴリズムの即時実装に適した説明は見つかりませんでした。 アルゴリズムのすべての微妙な点を明確に理解することなく、実装を開始する必要がありました。 ネットワーク上で異なる言語のソースコードを見つけましたが、必要な言語に翻訳してタスクに適応するための知識がまだ不足していました。 そのため、「少し丸いホイールと柔らかいサドルを使用して」ホイールを再発明することにしました。

おそらく、読者の1人が、ソースコードを使用して同様のタスクの説明を見つけました。 その後、コメントのリンクを残してください-私が得たものと比較しましょう。

アルゴリズム

だから...「指の上の」シリーズは続きます。 ウィキペディアでボロノイ図についてロシア語で読むことができます[ 1 ]。 一番下の行は、プレーン上のランダムなポイント（中心）のセット（簡単にするために2Dの場合を考えます）で、この図はポリゴンのコレクションであり、ポリゴン内のすべてのポイントは他のポリゴンの「中心」よりも「中心」に近くなります。 したがって、2つのポリゴン間の境界上のすべてのポイントは両方の中心から等しい距離にあり、ポリゴンの頂点は3つ以上の中心から一度に等距離にあります。

ダイアグラムを作成する最も「簡単な」方法は、すべての中心の間に「中間垂線」を作成することです。 これらのセグメントの中央に位置する中心のペアを接続するセグメントに垂直。 次に、得られた垂線の交点を見つけて切り取る必要があります。 ただし、ほとんどの場合、計算を実行する必要があります（O（n ^ 2 * log n））。

いわゆるのアルゴリズムがあります 「掃引線」（掃引線、フォーチュンのアルゴリズム[ 2 ]）。 その計算の複雑さはO（nlogn）です。 以下に説明します。

アルゴリズムの本質

このアルゴリズムの基本は、補助オブジェクト（直線（RF）をスイープする）の使用です。 垂直でも水平でもかまいません。 大きなY値から小さなY値に移動する水平3Dを使用します。

一番下の行は、RFPの各位置で、この行より上でその上にあるポイントのみが考慮されるということです。 同時に、「中心」のそれぞれに対して放物線が作成され、その上の点は「中心」およびRFから等距離にあります。 この場合、「中心」は対応する放物線の焦点であり、RFPは同じ放物線のディレクターです 。

放物線方程式の形式は次のとおりです。

  y =（（x-xf）^ 2 + yf ^ 2-L ^ 2）/（2 *（yf-L）） 

ここで、 xf 、 yfは放物線（ボロノイ多角形の中心）の焦点の座標です。

LはRFPの位置です（処理中の現在のイベントのY座標）。

すべての放物線の下からエンベロープを構築すると、いわゆる 「海岸線」（ビーチライン）。 この区分曲線は、アルゴリズムで重要な役割を果たします。 「放物線の破片」の交差点（ブレークポイントと呼びましょう）は、ダイアグラムのポリゴンの境界上にあります。 2つのブレークポイントが1つのポイントに収束すると、「アーチ」の1つ（放物線の1つ）が「崩壊」します。 それに隣接する2つのアーチは互いに接続されています。 これは、チャートポリゴンの上部を形成します。

したがって、タスクは2つのイベントの検出と処理に要約されます。検討中のセンターのリストに新しいポイント（サイトイベント）を追加し、頂点（円イベント）を疑います[ 3 ]。 など...このようなものは、さまざまな言語でネット上で説明しました。 そして、この概念レベルでは、すべてが非常に複雑に見えるわけではありません。 しかし、検出はどの程度正確に（段階的に）実行されますか？ そして、これらのイベントをどうすればいいのでしょうか？

簡単な言葉で述べようと思います。

データ構造

前述のように、アルゴリズムの主要なオブジェクトはイベントです：サイトイベントとサークルイベント。 これらのイベントはリストに配置され、私の場合はY座標の降順でソートされています。 Y座標の値が大きいイベントは、キューの上位に配置され、より早く処理されます。 したがって、最初に必要なのは、イベントを格納するための順序付きリストです。

次に必要なのは二分木です。 このツリーには、3つのタイプのノードが配置されます。Arc-アーチ（放物線の一部）。このノードは、放物線の焦点の座標と、円イベントへのリンク（ある場合）を格納する必要があります。 BP-ブレークポイント、2つの放物線の交点。 BPOwnerはサブツリーのルートであり、その子はタイプBPのノードです。 BPおよびBPOwnerノードは、顔へのリンクを保存する必要があります。 顔を別のリストに保存する必要があります、なぜなら サークルイベントを処理すると、BPおよびBPOwnerノードが削除されます。

出版物[ 6 ]で簡単に見つけることができるArcおよびBPのノードへの対応。 BPOwnerには直接的な名前はありません-サブツリーのルートだけです。 ソフトウェア実装の利便性のためだけに名前を付けました。

ボロノイ図の典型的な二分木図を（私が想像しているように）図に示します。 1。



図 1.バイナリツリー。

この図では、潜在的に存在するサークルイベントをすぐに強調表示できます。 左を見ると、Arc1、Arc2、Arc3は3つのトリックを形成しますが、1つの直線上にある可能性は高くありません。 サークルイベントが表示される場所は他にありません。 トリプルは{Arc3 Arc3 Arc2}、{Arc3 Arc2 Arc2}および{Arc2 Arc2 Arc1}のままです。 このようなツリー構築スキームは冗長ですが、分析が容易です。

データ構造は、[ 6 ]でより詳細に調べることができます。 おそらく私の発表はその出版物で発表されたものとは異なりますが、私にとっては簡単です。

メインサイクル

1. データの初期化。
2. 行は空ではありませんが：
   
   
   1. キューから最初のイベントを切り取ります（Y座標の最大値を使用）
   2. If（イベント= =サイトイベント）
      
      ProcessSite（イベント）
   3. その他
      
      ProcessCircle（イベント）
   
   
   
3. バイナリツリーで参照されているすべての面を仕上げます。

本当に簡単です。 イベントハンドラーのすべての魔法。

ポイントイベントの処理

バイナリツリーのポイントイベントとは何ですか？ RFPが次のポイントに到達すると、新しい放物線がツリーに追加されます。 最初に、ZPアルゴリズムに従って、イベントからイベントに移動することに注意してください（デモアニメーションでは、この直線はスムーズに移動します）。次に、最初は放物線は垂直方向の光線です。 この光線と放物線の1つとの交点で、2つの「ブレークポイント」（BP）が一度に形成されます。 したがって、ツリー内のポイントの各イベントには、対応する光線の交差が発生する放物線があります。 これは、ツリー全体のルートから開始し、このイベントのX座標とBPOwnerおよびBPノードを比較する降下法によって簡単に実行できます。 アーチが出会うまで降下します。 アーチにキュー内の既存のサークルイベントへのリンクが含まれている場合、このイベントをキューから削除し、このイベントへのリンクをこのアーチとその隣の左右のアーチから削除する必要があります。 次に、アーチ（以下のArc1を参照）の代わりに、フォームのサブツリーが作成されます。

  BPOwner
      / \
     BP BP
   / \ / \
 Arc1 Arc2 Arc2 Arc1 

ツリーの構造が変更されたので、サークルイベントを検索してツリーを左から右に実行する必要があります。 これを行うには、アーチのトリプルを連続して取得し、対応する放物線の焦点の座標を確認して共直線性を確認する必要があります。 3つの焦点が1つの直線上にない場合は、それらに共通の円を作成できます。 この円の下のポイントがRFの下にある場合は、キューに円イベントを追加できます。 円の最下部はイベントが発生する場所であり、中心はボロノイ多角形の最上部が配置されるポイントです。

要約すると、ポイントイベントはノードをツリーに追加するだけで、イベントキュー内のイベントを循環させるだけです。 それらが発生しても、それ以上何も行われません。 ポイントイベントが発生すると、放物線の交点であるBPの座標も計算されません。 「メインマジック」は、サークルイベントハンドラーで行われます。

「サークルイベント」の処理

各サークルイベントには、このイベントが発生したときに削除されるアーチ（「崩壊」、上記参照）へのリンクが含まれている必要があります。 以前は、サークルイベントを検出するために、アーチのトリプルが考慮されると書かれていました。 したがって、中央のアーチへのリンク、つまり X座標値が他の2つのアーチの対応する値の間にあるものに。 中央のイベントと同じサークルイベントへのリンクも、これらの隣接するアーチに保存する必要があります。 これについては特に必要はありませんが。 「オンザフライ」で、中央のアーチにある2つの隣接するアーチ（左と右のアーチ）へのリンクを書き留める方が簡単です。 これにより、目的のアーチを持つ次のブランチを探すためにツリーを歩く必要がなくなります（ツリーはバイナリであるため、残りの2つのアーチのいずれかが次のブランチにあります）。

サークルイベントの処理は、削除されたアーチを直接制限するブレークポイントの座標を更新することで構成されます。 次に、アーチとそれに関連付けられた2つのブレークポイントが削除されます。 その後、ツリーを再構築する必要があります。 その結果、新しいBPノードが追加され、結果のサブツリーが1レベル上に移動します...

テキストでは、このような手順はかなり難しいと感じられます。 いずれにせよ、私にとっては、グラフと二分木の理論に真剣な知識を持たない人として、これは重要な作業でした。したがって、図にも説明します。 2。



図 2サークルイベントの処理

結果

ここで、ダイアグラムの特徴的なビュー、つまり 任意の多角形のジオメトリを持つゲームカードのビュー。



図3ゲームカード

「中心」のこの地図（私は覚えています-これは、エリア全体にランダムに分布する最初のポイントのセットです）文字があります。 これらのポリゴンのエッジを通して、敵のキャラクターはキャラクターを攻撃できます。 上の写真では、「グリーンマン」とは...いや、アルコール依存症ではありません。 緑のシルエットが配置されている埋め立て地は、敵の移動ごとに可能な攻撃の数の観点から安全な場所です（最大4）。 しかし、赤い文字は不運でした。 非友好的な集団による最大8回の攻撃がそれに対して行われます。

戦術

マップ上の各ポリゴンに「通過コスト」を割り当てることができます。 それ以外の場合は、「交差コスト」をポリゴンの境界に割り当てるか、両方の組み合わせを使用します（境界交差コスト+通過コストの半分）。 また、ポリゴンのエリア（またはマップグリッドのカバーポイントの数）に応じて、さまざまなボーナス（アーティファクトの発生頻度、イベントの発生など）、保護ポイント、要塞を構築するためのリソースなどを割り当てることができます。 これはすでに素晴らしい戦術的な機会を提供します。 さらに、滞在できる適切なトレーニング場を選択する必要があります。 冒頭に書いたように、大きな訓練場はより多くの境界を持つことができます。つまり、敵の1回の動きでより多くの攻撃を行うことができます。 ただし、大きなトレーニンググラウンドは大きなボーナスを意味します（境界線の数ではなく、エリアに応じたボーナスの対象となります）。 これは、最小数の境界で最大面積のポリゴンが特に価値があることを意味します。 これはMaxiMinタスクであり、自動化が簡単です。 AIで受け取ったボーナスの使用を自動化することはより困難です。

A *（1つの投稿の「TODO」）を使用してパスを検索できます。 パスを敷設するためのシステムに入ることができます-最初に、キャラクターを手動で保持し、パスを記録してから、作成した「ウェイポイント」を自動化に使用できます。 しかし、それはおそらく不便すぎるでしょう。 ゲームプレイはマイナスの影響を与える可能性があります。

今、要塞について。 各訓練場には、要塞を作成するための特定のリソースセットが必要です。要塞のタイプと構造の構築速度は、これらに依存します。 まさに「文明」が得られます。 キャラクターはアクションポイントを使用して、選択した位置で強化します。 彼らは2つのグループに分けることができます-防御と攻撃。 同時に、保護ODは、敵の攻撃（シールドを上げる、矢をかわす、攻撃をブロックするなど）の間に要塞と防御活動を構築するために費やされ、攻撃者は攻撃中と防御（反撃、軍縮）の両方に費やすことができます。 ZPG「MyBrute」に言及することができます。アバターは、防御するときに、敵からの打撃を受けることなく、イニシアチブを奪い、それに応じて攻撃することができます。

各キャラクターは要塞のセットを持つことができ、その構造は訓練されます。 各タイプの要塞は、異なる程度の保護および/またはボーナスを与えます。 要塞からのボーナスに加えて、埋め立て地自体はランダムなボーナスを与えることができます。 特定の場所に長時間滞在すると、キャラクターは、特定のポリゴンの貴重な何かを見つけたり、隠されたプロパティを「発見」する確率を高めます。

このような推論を続けることができます。 演習の余地は十分にありますが、記事のトピックから逸​​脱します。

結論

ゲームカードのジオメトリを変更すると、必然的にゲームの戦術に重大な変更（より良いと思います）が発生します。 追加の戦術レベル、戦闘の転換点で正しい方向にスケールを正しく上回る能力があります。 さらに、このアプローチにより、ゲームカードが動的になり、トポロジが（ローカルまたはグローバルに）変更されます。 ここでは、STALKERゲームの可変ロケーションの考えを思い起こせずにはいられませんでした（私の意見では）。 2Dでは、これを実装するのはそれほど難しくありません。 しかし、ボロノイ図も3D用に構築されていることを忘れないでください。

ご清聴ありがとうございました！ あなたのコメント...

参照資料

1. ボロノイ図
2. ボロノイ図とビーチでの一日
3. Fortuneのアルゴリズムによる平面ボロノイ図
4. 多角形マップの生成
5. ボロノイ図
6. フォーチュンスイープアルゴリズム