コンピュータゲームにおける、解析のためにゲームスペースを分割するボロノイ図の使用
【課題】コンピュータゲームにおいてゲーム状況を解析し、解析結果をグラフィカル形式で表示すること。
【解決手段】コンピュータゲームにおいて、各複数のゲーム要素（１０）についての状態を決定し、少なくともいくつかのゲーム要素（１０）をボロノイサイトとして利用してゲーム要素の間のボロノイ図の表現を生成し、このボロノイ図（１６）を利用してゲーム状況の解析を実行することによって、複数のゲーム要素の状態を利用して、ゲーム状況が解析される。この解析は、空間的解析および／または戦略解析であってもよく、この戦略解析に基づいて、コンピュータ制御されたエンティティの動きを決定する。ゲームスペースは、サッカー、野球、またはバスケットのプレイスペースを表現し得る。ゲーム要素の状態は、モーメント、スピード、移動の方向（１４）、速度、および／またはゲーム要素のチーム関連性を含み得る。
【解決手段】コンピュータゲームにおいて、各複数のゲーム要素（１０）についての状態を決定し、少なくともいくつかのゲーム要素（１０）をボロノイサイトとして利用してゲーム要素の間のボロノイ図の表現を生成し、このボロノイ図（１６）を利用してゲーム状況の解析を実行することによって、複数のゲーム要素の状態を利用して、ゲーム状況が解析される。この解析は、空間的解析および／または戦略解析であってもよく、この戦略解析に基づいて、コンピュータ制御されたエンティティの動きを決定する。ゲームスペースは、サッカー、野球、またはバスケットのプレイスペースを表現し得る。ゲーム要素の状態は、モーメント、スピード、移動の方向（１４）、速度、および／またはゲーム要素のチーム関連性を含み得る。
【発明の詳細な説明】
【技術分野】
【０００１】
（発明の分野）
本発明は、概して、コンピュータゲームに関し、より詳細には、コンピュータゲームにおいてゲーム状況を解析し、解析結果をグラフィカル形式で表示することに関する。
【背景技術】
【０００２】
（発明の背景）
通常の対戦型コンピュータゲームは、人間の対戦者およびコンピュータの対戦者に関係する。このような対戦型コンピュータゲームは、チェス、自動レーシング、ファンタジーゲーム、およびスポーツゲームを含む。ゲームが人間の対戦者の関心を維持するためには、人間の対戦者が毎回勝たない十分な対戦者が必要である。従って、最も単純なコンピュータゲームを除く全てにおいて、解析という要素が必要とされる。この解析は、現在のゲーム状況に基づいてなされ、コンピュータゲームによって利用されて、コンピュータの対戦者の次の動きを決定する。
【０００３】
例えば、ゲームがチェスである場合、コンピュータゲームは、ゲームの状況、すなわち、チェス盤のチェスピースの現在の位置、および人間の対戦者によって取られた動きの履歴を解析するようにプログラムされ、このゲームの状況に応じて、どのような動きを取るべきかについての決定を行う。チェスのルールは、解析および応答に制約を与え、コンピュータは、各動きごとに、１６以下のピースのうちのどれが、たった６４個の別々の位置に制約を受ける盤内の数ダースのスペースのうちの１つに移動するかを決定する必要があるのみである。従って、全ての可能な動きの決定は、非常に単純な態様である。もちろん、チェスのコンピュータの対戦者は、プログラミングすることが難しいが、それは、動きは、将来の多くの動きを予想されなければいけないからである。
【０００４】
レーシングゲームでは、コンピュータに操作されるレースカーまたはオブジェクトは、まさに、トラックに沿って迅速に移動される必要がある。ファンタジーゲームでは、可能となるアクションは、任意であり得る。現実のように実世界のアクティビティをシミュレーションするスポーツゲームおよび他の対戦型ゲームは、部分的により困難である。なぜならば、フィールドは、小さな別々のポジションの集合ではなく、ゲームは、人間の対戦者が対応する実世界の活動において期待するように振舞わなければならないからである。
【０００５】
１つの例として、サッカーのゲームは、数人のプレイヤー、および、連続的な２次元空間（可能であれば、プレイヤーがジャンプし、ボールの高さが考慮される場合は、３次元空間である）でどこにでも自由に移動するボールを含む。サッカーの戦略は、１人のプレイヤーが、対戦チームのプレイヤーからの干渉なくチームメイトにボールを蹴ることができるようにプレイヤーを配置しようとすること等、多くの考慮すべきことを含む。人間の対戦者とコンピュータの対戦者との間でプレーされるコンピュータ計算されたサッカーゲームが興味深いものであるためには、コンピュータの対戦者は、人間の対戦者にチャレンジを与えなければならず、従って、コンピュータゲームは、徹底的にゲーム状況の解析を実行しなければならず、コンピュータの対戦者チームメンバをどのように動かし、かつ操作するかを決定して、チャレンジを与えなければならない。好ましくは、コンピュータゲームで利用可能な消費電力量にいくらかの制限が与えられた場合、コンピュータの解析は、ゲームがゲーム状況を解析し、実世界で適切な応答を形成することができるように、十分に効率的である。
【発明の開示】
【課題を解決するための手段】
【０００６】
（本発明の簡単な要旨）
コンピュータゲームにおいて、本発明の１つの実施形態は、複数のゲーム要素の状態を利用してゲーム状況を解析することを提供する。これは、各複数のゲーム要素についての状態を決定し、少なくともいくつかのゲーム要素をボロノイサイトとして利用して、ゲーム要素の間のボロノイ図の表現を生成し、ボロノイ図を利用してゲーム状況の解析を実行することによる。この解析は、戦略解析の基本として利用され得る空間的解析であり、コンピュータ制御されたエンティティの動きを決定する。特定の実施形態では、ゲームスペースは、２次元のサッカー場であり、ゲーム要素は、チームに関連付けられたプレイヤーである。ゲームスペースは、３次元のゲームスペースであってもよい。ゲームスペースは、サッカー場ではなく、野球場、バスケットコート、またはほかのゲームスペースを表現してもよい。
【０００７】
ゲーム要素の状態は、モーメント、スピード、移動の方向、速度、および／またはゲーム要素のチーム関連性を含み得る。サッカー場の解析は、コンピュータ制御されたチームのプレイヤー間のレーンのパスを決定することを含む。サッカーゲーム解析では、ゴールキーパーのいない各チームのプレイヤーのボロノイ図、ゴールキーパーのいる各チームのプレイヤーの図、ならびに、ゴールキーパーがいる場合およびいない場合の２つのチームのプレイヤーの組み合わせの図のような、複数のボロノイ図が生成され得、この複数のボロノイ図を用いて解析がなされる。
【０００８】
本発明のほかの特徴および利点は、以下の詳細な説明および好ましい実施形態の観点から明らかになる。
【発明を実施するための最良の形態】
【０００９】
（発明の詳細な説明）
ここで図面を参照して、本発明の実施形態がここで説明される。図面の構成要素が参照番号とともに呼び出される場合、同様の参照番号は、同様の構成要素を表し、構成要素の同一のインスタンスを表す場合もあれば、表さない場合もある。
【００１０】
この開示全体を通して、ボノロイ図が参照される。スペース内に「ボロノイサイト」として示される点の集合が与えられると、そのスペースは、領域「ボロノイセル」の集合体に分割され得る。このとき、ボノロイサイトが関連するボロノイセルを有し、関連するボロノイセル内の各点は、任意の他のサイトよりもそのセルのサイトに対して近くなる。本明細書中において利用される際には、「ボロノイ分割」は、空間をボロノイセルに分割するプロセスを示すために利用され、ボロノイ図は、これらのボロノイセルの示す図である。
【００１１】
ボロノイ図を表現する同一の情報を表現する多くの方法が存在することを理解されたい。スペースが曲線によって結合されない場合、各セルは、セルの有限個の頂点のポジションによって記述され得る。従って、ボロノイ図の表現の生成は、このような図の表示を生成することに制限されるように構成されるべきではなく、セルの結合についての情報を生成する任意の方法をカバーし得る。
【００１２】
ボノロイ図の定義は、平面分割として定義されることがあるが、本明細書中に記載される方法および装置は、凸、凹、無限、曲線、多角形、またはこれらの特徴のいくつかの組み合わせとなり得る３（またはＮ）次元空間に分割するために利用され得るので、本明細書中では同様の定義に制限されないことが理解されるべきである。ボロノイサイトは、点であってもよいし、あるいは、多角形のオブジェクトまたは他の次元を有するオブジェクトであってもよい。
【００１３】
ボロノイ図は、数学の分野では周知であり、サイトの集合からボロノイ図を生成するために、多くの計算方法が利用されるので、定義、ならびに、ボロノイ図の生成のための従来の方法および装置は、ここで示される必要はない。従来の方法が利用され得るが、いくつかの例では、さらに高度な性能が必要とされ、この場合、本明細書中に記載されるボロノイ分割を実行する計算上のバリエーションのいくつかまたは全てが利用され得る。
【００１４】
図１は、上にボロノイ図のかさなったサッカー場の一部分を表現する透視図である。ここで、ボロノイスペースは、サッカー場（２次元）であり、ボロノイサイトは、チームの１人のプレイヤー（チームのゴールキーパーを含む）から複数のプレイヤーまでの、プレイヤーのポジションに一致する。図１は、このような図を生成し、その図をコンピュータゲームの解析に利用する装置および方法の以下の説明を理解しやすくするために提供される。図１の視点では、より暗いチームカラーの２人のプレイヤーおよびより明るい色のチームカラーの３人のプレイヤーが図示される。より暗いチームのプレイヤーの１人が、現在のボール保持者１０であり、もう一人のプレイヤーが潜在的なパスの受け側１１である。ライン１２は、相対的なフィールドポジションを示し、サッカー場を表すために本明細書中に含まれる、サッカー場のラインである。図の他のラインは、ボロノイセル間の分割を表し、ボロノイ図を示す。
【００１５】
本明細書中で説明されるように、ボロノイ図、終端または頂点を利用する１つの解析は、対戦者がパスをインターセプトすることができないボールのパス方法の解析である。例として、ボールのターゲットは、プレイヤー１１のボロノイセル１６を分割するラインセグメント１４に沿って存在し得る。ボロノイ分割のために、ラインセグメント１４上の点の全てが、あらゆる他のプレイヤーよりもプレイヤー１１により近くなることが既知であり、このような知識は、多くの座標点をテストまたはサンプリングする必要なく得られる。
【００１６】
図２は、本発明が実装されるサンプルのコンピュータゲームハードウェアシステム１００のブロック図である。システム１００は、ディスプレイ１０４、および、ゲームユーザとやりとりするために利用可能な入力／出力（Ｉ／Ｏ）デバイス１０６に接続されるコンソール１０２を含むように示される。コンソール１０２は、プロセッサ１１０、プログラムコード格納装置１１２、一時的データ格納装置１１４、およびグラフィックプロセッサ１１６を含むように示される。
【００１７】
プログラムコード格納装置１１２は、ＲＯＭ（リードオンリーメモリ）、ＲＡＭ（ランダムアクセスメモリ）、ハードディスク、他の磁気格納装置、光学格納装置、他の格納装置、あるいはこれらの組み合わせまたは変形であり得る。通常の構成では、プログラムコードの一部分がプログラム可能なＲＯＭ（ＲＯＭ、ＰＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ等）に格納され、プログラムコードの一部分がＣＤ−ＲＯＭ１２０（図示される）等の取り外し可能メディアに格納される。あるいは、プログラムコードの一部分は、カートリッジ、メモリチップ等に格納されてもよいし、必要ならばネットワークまたは他の電気的チャネルを介して取得されてもよい。
【００１８】
一時的データ格納装置１１４は、必要ならば、変数ならびに他のゲームおよびプロセッサデータを格納するために利用される。通常、一時的データ格納装置１１４はＲＡＭであり、ゲームのプレー中に生成されるデータ、例えば、各プレイヤーの状態（ポジション、方向等）およびボロノイ分割の結果のような解析のために生成されるデータを保持する。
【００１９】
図３は、ゲームがプレーされているときに一時的データ格納装置１１４に格納され得るゲーム状態のデータ構造の例を示す。ここで示されるように、ゲーム状態構造は、第１のチーム構造および第２のチーム構造に分割され、各チーム構造は、プレイヤー構造に分割される。各プレイヤー構造は、１人のプレイヤーに関連するデータにより示される。図に示される例では、チーム「Ａ」の第１のプレイヤー構造は、プレイヤーの番号（２３）、プレイヤーのポジション（ＦＢ−フルバック）、フィールド上の位置（０．４９７、０．３８６）等を表すプレイヤーデータを保持する。図示されるように、このゲーム構造はまた、ボールのポジション、ボールの速度、現在のスコア、ゲーム時間等の構造を含む。
【００２０】
図２〜３は、本発明の方法および装置を利用し得るコンピュータゲームシステムの例を示しており、本発明は、この例に制限されないことを理解されたい。従って、本発明は、図２に示されるハードウェア構成以外のハードウェア構成、および、図３に示されるデータ構造以外のデータ構造により用いられ得る。
【００２１】
図４は、プレイヤー、通常はコンピュータ制御のチームプレイヤーの次の動きを決定するプロセスを示す。通常、このプロセスは、ゲームシーケンスのより上位の動作によって開始され、図に示されるプロセスの結果は、より上位の動作によって利用され得る。例えば、より上位の動作は、ゲームおよびユーザとのインタラクションを実行するメインプログラムであってもよいし、図４に示されるプロセスは、メインプログラムが動きを作る必要があるときに呼び出されるサブルーチンである。戦略解析プロセスによって決定される「次の動き」は、チェスおよび他のゲームでは一般的であるように、分散型の動きであってもよいし、あるいは、ゲーム要素のゲームスペース位置への運動または要請等の、比較的分散型にならないように定義された動きであってもよいことを理解されたい。この解析は、分離した次の動きを決定するか、または、動きまたは戦略の次のシーケンスを決定するためだけに用いられてもよい。
【００２２】
図示される方法は、ゲーム状態の評価（ステップ１）により開始する。これは、各当該プレイヤーのいる場所、プレイヤーのモーメント、ボールのポジション、ゲーム時間等を決定することを含み得る。一旦ゲームが評価されると、フィールドはボロノイセルに分割される（ステップ２）。本明細書中で説明されるように、セルは、プレイヤーの位置に位置するそれぞれのサイトに最も近い点の集合体として規定され得る。しかし、いくつかの実施形態では、この距離関数（ｍｅｔｒｉｃ）は、常に均一で線形距離の距離関数ではなく、距離および／または他の変数の重みづけされたおよび／または非線形距離の測定基準であってもよい。
【００２３】
ゲーム状態は、通常、瞬間の状態であり、すなわち、ゲーム状態は、時間に伴い変化する。従って、結果として生じるボロノイ分割はまた、時間を介して変化し得る。もちろん、ゲーム状態は、瞬間のスナップショットでなくてもよいし、現在の瞬間の時間の状態だけでなく最近のゲームイベントの状態を考慮に入れてもよい。データを維持するボロノイ分割の再計算の頻度は、必要に応じて変更し得、ゲームプレイのレベル（より洗練された処理は、より高速の更新を必要とし得る）および処理能力（より遅いマシンは、より頻度の低い更新を必要とし得る）を考慮する。いくつかの実装例では、再計算の速度は、ゲームウィンドウ更新速度と同期する。
【００２４】
一旦フィールドが分割されると、結果として生じるボロノイ図は、可能なアクションを解析するために利用される（ステップＳ３）。アクションは、どこにプレイヤーを動かすか、どこにボールを動かすか、およびいつパスするか等を含む。この図はまた、パスする側から受け側までボールをパスする前に受け側およびパスする側をどのように動かすか、あるいは、ゴールにおいてシュートを阻止するためにどのようにゴールキーパーを動かすか等、複数のプレイヤーのアクションを決定するために利用され得る。実際のボロノイ図が、実際に生成される必要はなく、戦略エンジンまたは他の解析を実行するコンピュータエレメントは、ボロノイ頂点、および／または終端等の表示のような、ボロノイ分割の結果を表示する必要があるのみであることを理解されたい。アクションがヘッダ、クロス、コーナーキック等を含む場合、三番目の次元（高さ）が考慮に入れられ得る。
【００２５】
一旦可能なアクションがステップＳ３で決定されると、オフサイドおよびアウトオブバンウズルールのようなルールが課された制約条件を考慮する等、他のファクタが考慮され得る（ステップＳ４）。例えば、解析が、潜在的な受け側が実際にアウトオブバウンズまたはオフサイドであることを決定した場合、この解析は、その人間にパスをさせないように調節され得る。一旦他のファクタが考慮されると、戦略エンジンは、取るべきアクションを決定する（ステップＳ５）。
【００２６】
ボロノイ分割（ステップＳ２）を行うステップは、１つのボロノイ図（またはその表現）を生成するステップであり得るが、異なるサイトの集合ごとに、１つより多いボロノイ図を生成するステップであってもよい。特に、１つのボロノイ図は、サイトとしてのサッカー場のサッカープレイヤーのポジションを利用し、ステップＳ３の解析は、ステップＳ２の結果（分割）をサッカーゲームの他の幾何学的特性とを組み合わせて、コンピュータおよび人間が制御するプレイヤーの戦略オプションを計算する。他の幾何学的特性の例は、オフサイドラインの現在のポジション、ハーフライン、またはペナルティエリア（ゴールキーパーがその手を利用することができる場所、および、守備側のファールがペナルティショットになる場所を規定する際に有用である）のような客観的特性を含む。幾何学的特性はまた、「フランク（ｆｌａｎｋ）」等、ゲームスペースの領域に割り当てられた主観的な特性を含み得る。このフランクは、明らかにラインで引かれた領域（単数または複数）あるいはフランク内の点からフランク外の点へのゆるやかな遷移を有する領域のどちらかとして規定される。他の主観的特性は、「シューティング領域」を含み得る。客観的および主観的特性に加えて、解析はまた、プレイヤーの期待されるヘディングのような派生した特性を含み得る。
【００２７】
この組み合わせは、攻撃側および守備側のプレイヤーがフィールド上に自分自身をポジショニングすべき場所を決定すること、プレイヤーが攻撃側のランを行うべき時および場所を決定すること、プレイヤーがボールをドリブルすべき時および場所を決定すること、プレイヤーがボールをパスすべき時および場所を決定すること、戦略上のパターンマッチングを決定すること、守備側のマーキングロジックを決定すること、衝突の回避／検知を決定すること、および／または、戦略スクリーン上のインジケータを決定すること等、広範囲の戦略情報を計算するために有用である。プレイヤーをどこに配置するか等、戦略情報の決定のされ方の詳細は、後述される。
【００２８】
特定の実施形態では、戦略解析は、図５に示されるような、６つの異なるボロノイ図を利用する。２つのチームが「チームＡ」（四角内に書き入れられることによって）および「チームＢ」（開いた円によって示される）によってラベル付けされ、６つの図（および以下に利用される速記）は、
図５（ａ）−ゴールキーパーのいないチームＡ（ＶＤ−Ａ）
図５（ｂ）−ゴールキーパーのいるチームＡ（ＶＤ−Ａｇ）
図５（ｃ）−ゴールキーパーのいないチームＢ（ＶＤ−Ｂ）
図５（ｄ）−ゴールキーパーのいるチームＢ（ＶＤ−Ｂｇ）
図５（ｅ）−ゴールキーパーのいない両チームＶＤ−ＡＢ）
図５（ｆ）−ゴールキーパーのいる両チーム（ＶＤ−ＡＢｇ）
これらの図は、Ｆｏｒｔｕｎｅ，Ｓ．Ｊ．「Ａ Ｓｗｅｅｐｌｉｎｅ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｖｏｒｏｎｏｉ Ｄｉａｇｒａｍｓ」、Ａｌｇｏｒｉｔｈｍｉｃａ、２：１５３〜１７４（１９８７）に記載されるインクリメントするアルゴリズム等、インクリメントするアルゴリズムを用いて計算され得る。サッカーゲームの改変例では、標準的なインクリメントするアルゴリズムは、第１のパスで利用され、その後、ゲームの残り全体を通じて、インクリメントするアルゴリズムを開始するために利用された最初の推測は、前回のボロノイ図に基づく。これは、図が計算されるたびにサイトがほんの少しの量だけ動くことが期待される場合、サッカーゲームと同様の他のアプリケーションにおいて有用である。
【００２９】
さらに、図を計算する仕事は、３つ以上のフレームに分割され得、ホームチームの図は、第１のフレームで計算され、遠征チームの図は、第２のフレームで計算され、両チームの図は、改良された効率の前回の２つの計算に基づいて、第３のフレームで計算される。プレイヤーの現在のポジションは、ボロノイ分割のサイトとして利用され得るが、予測がプレイヤーの現在のポジションおよび現在のモーメント（または、スピード、速度等）に基づく場合、プレイヤーの予測された未来のポジションが代わりに利用されてもよい。ある例では、プレイヤーのポジションを利用するだけでは、プレイヤーが、そのプレイヤーの後ろよりもプレイヤーの前の点に達することがより容易であるという事実を考慮していない。プレイヤーのポジションをほんの少し前へオフセットすることによって、運動の方向に、プレイヤーのスピードと比例して、モーメントおよび回転を考慮する距離関数を利用するよりも、標準的な線形距離関数を利用して、図のより近い近時が可能になる。さらに、後者は、計算が非常に大変である。
【００３０】
（空間的戦略的解析）
ここで、ボロノイ分割の結果を利用する（ボロノイ図またはボロノイ図の表現を利用する）戦略解析の基準として利用され得る空間的解析のいくつかの例が説明される。これらの例では、フィールドはサッカー場であり、２つのチームはチームＡおよびチームＢである。実装例に応じて、どちらかのチームがコンピュータ制御されたチームであり、もう一方のチームが人間のユーザに制御されたチームである。あるいは、両チームが人間のユーザに制御されたチームであってもよいし、両チームがコンピュータ制御されたチームであってもよい。典型的なコンピュータゲームは、コンピュータ制御されたチームおよび／または人間のユーザに制御されたチームのストラテジーの決定を行うことができる戦略エンジンを含み得る。後者の場合、決定は、学習モードまたはアシストモードの一部分であってもよし、人間のユーザが補助なく全てのストラテジーの決定を行いたい対戦モードでは、オフにされてもよい。
【００３１】
プレイヤーポジショニングは、ゲーム中になされ得る１つの解析である。プレイヤーポジショニング解析は、プレイヤーを動かす、または、再ポジショニングする方法を決定するために利用可能である。例えば、様々なボロノイ図を検査して、ボールに最も近いプレイヤーならびにプレイヤー「最も近い仲間」であるチームメイトおよび／または対戦者を識別し得る。プレイヤーＯから仲間まで引かれたラインから、パスレーンを決定することができ、別のボロノイ図を用いて、どのチームメイトがこれらのパスレーンに最も近いかを計算し得る。この情報に基づいて、チームメイトは、これらのラインへ動き、パスのために自分自身をポジショニングする。プレイヤーポジショニングおよび他のストラテジーは、対戦者によって採用されたチームフォーメーション、例えば、４−４−２または３−５−２によって知らされ得る。
【００３２】
攻撃側ランは、ＶＤ−ＡＢ（または、たまにＶＤ−ＡＢｇ）を用いて計算される。この例は、図６（ａ）に示される。攻撃チーム（チームＡ）の任意のプレイヤーが、オフサイドラインよりもチームＢのネットに近いＶＤ−ＡＢ上にボロノイ頂点を有する場合、そのプレイヤーは、その頂点（図の頂点６０２）まで攻撃側のスルーランを行う。これは、プレイヤーが、フィールド上の他の誰よりも前にそのプレイヤーがスペースのピースまで達することができることを理解している場合のプレイヤーの行動をモデル化する。この点は、オフサイドライン（図のライン６０４）よりも後ろにあるので、ランは、離脱する結果となり得る。この説明から理解されるべき、最も適切なボロノイ図を用いる際には、注意がなされるべきである。例えば、ゴールキーパーがいそうなフィールドのエリアにおいてＶＤ−ＡＢが攻撃側ランに用いられる場合、ボールは、反対のゴールキーパーまでまたはその近くまでパスされてもよいし、ＶＤ−ＡＢｇが利用される場合は、ゴールキーパーのポジションが考慮される。
【００３３】
攻撃側ランの決定に加えて、攻撃ランについて上述されたプロセスは、守備側によって利用され得、それぞれの守備側のポジショニングの穴を識別し、それに応じて調節する。
【００３４】
衝突を回避するボールのドリブルは、別の戦略解析である。この解析により、ボールを有するプレイヤーにフィールド上のターゲット点までドリブルさせるためには、プレイヤーは、ターゲット点に最も近いＶＤ−ＡＢからボロノイ頂点に向かってドリブルすべきである。結果として生じる行動は、プレイヤーにその点に迅速に到着させつつ、チームメイトおよび対戦者を避けて、非常にサッカープレイヤーのように見える方法で動き、適切である場合にはフェイントおよび突然のヘディング変化を含む。
【００３５】
ボールパス決定は、ＶＤ−ＡＢｇを利用して、ボールをチームメイトまでパスする最良の場所を決定する。解析の目的は、ＶＤ−ＡＢｇにおける現在のボール保持者（「プレイヤーＢＨ」と呼ぶ）のボロノイセル内の点までボールをパスすることである。これは、図６（ｂ）によって図示され、ここで、パスする側６１２は、チームメイト６１３までのパスを考慮する。図示されるように、適切な受け側である２人のプレイヤーが存在する。ＶＤ−ＡＢのような他の図を利用することができるが、ゴールキーパーは考慮に入れられない場合、ボールは、反対のゴールキーパーがボールに最初に達し得るようにパスされ得る。これは、通常、望まれない。
【００３６】
ボールがパスされるターゲット点を決定するために、いくつかの技術が利用され得る。１つの技術では、コンピュータは、ＢＨの面するベクトルおよび受け側（単数または複数）のボロノイセルを分断して、その分断ラインにそった可能な受け取り点の範囲を得る。これらの点は、図６（ｂ）の分断ラインセグメント６１４に沿った点であり、分断ラインセグメント６１４（ａ）は、受け側６１３（ａ）がパスを受け、任意の他のプレイヤーよりも前に到達し得る点の集合であり、分断ラインセグメント６１４（ｂ）は、受け側６１３（ｂ）がパスを受け、任意の他のプレイヤーよりも前に到達し得る点の集合である。パスする側からの分断ラインセグメントの方向は、受け側の運動ベクトルの方向、あるいは、コンピュータまたはユーザによって選択される別の方向となり得る。また、解析は、依然として受け側がボールに最初に達することを保証しつつ、その受け側を最大に導く受け側のボロノイセル内の点を探し得る。分断ラインセグメントを考慮に入れると、ボールキックの提示されるパワーは、ボールが好ましいまたは最適のスピードで、好ましいまたは最適の時間に受け側のボロノイセルに到達するように、決定され得る。
【００３７】
ＶＤ−Ｂのようなボロノイ図のトポロジーは、戦略パターンマッチングのために利用され得る。どのパターンが識別されるのかに応じて、特徴とマッチする他のボロノイ図が保存され、利用され得る。サッカーゲームにおいてある状況が識別される場合、ボロノイ図のトポロジーが保存され得る。これは、エッジ角度、エッジ長、ボロノイの近隣者、およびボロノイセルエリアを含む。同一のトポロジーが後のゲームで識別される場合、その特定の状況に適切な予め定められた行動に基づいて、アクションが取られ得る。このように、同一ではないゲーム状態が、類似のゲーム状態に類推され得ることにより、比較的少ない数の予め定められた行動が記憶され、比較的多い数のゲーム状態に応じて利用され得る。
【００３８】
「守備側マーキングロジック」では、所与のプレイヤーのＶＤ−ＡＢにおけるボロノイの近隣者を利用して、そのプレイヤーがマークする潜在的な対戦者を決定する。「マーキング」は、守備中のプレイヤーがどの攻撃側プレイヤーをカバーするのかを決定するプロセスである。これは、極めて効果的である。なぜなら、マーキングアルゴリズムで考慮される必要があるプレイヤーの数を減少させることができるからである。あるいは、デローニ三角分割図が利用され得る。デローニ三角分割図は、「２重の」ボロノイ図であり、エッジを共有するセル内にあるボロノイサイトのペア間に引かれたラインセグメントを含む。デローニ三角分割図の一部分の例は、図６（ｃ）に示される。ここでは、チームメイト間のラインは、（ボロノイセルのエッジを共有する対戦者をペアにするラインのみを残して）排除されている。これらのラインは、マーキングの良好な座標を示す。デローニ三角分割図は、ある解析においてボロノイ図の適切な代替となり得ることを理解されたい。図６（ｄ）は、デローニ三角分割図が重ねられたサッカー場の表現の透視図である。
【００３９】
基本の６個以外の解析では、他のボロノイ図が利用され得る。例えば、怪我をしたプレイヤー（怪我をしているが、フィールドに残っている）が、図から排除され得ることにより、怪我をしたプレイヤーが考慮されなくなるような、解析がなされ得る。他の図では、１つのチームからのチームプレイヤーが、その反対のチームに加えられ得、わずかに異なったボロノイ図を取得する。さらに別の図では、ボール保持者が反対のチームのボロノイ図へと動く。通常の場合、ボロノイ図は、１つまたは両チームからのプレイヤーの任意の集合を有する解析のために、容易に生成され得ることを理解されたい。試合の関係者は、通常考慮されるべきではないが、試合の関係者も、適切である場合は含まれ得る。
【００４０】
１つ以上のボロノイ図がスクリーン上に与えられ得る。ＣＤ−ＡＢまたはＶＤ−ＡＢｇが与えられた場合、各チームのセルは、異なるように色が付けられ得る。これは、人間のユーザの洞察力をユーザのチームが所有するスペースに与え、戦略上の利点を与える。このバリエーションは、スクリーンのエッジのみにボロノイ図を与えることである。これは、スクリーンの外のプレイヤーが配置される場所についての考え、および、スクリーンの外にいるプレイヤーに対してなされる潜在的な成功をユーザに与える。
【００４１】
ボロノイ図の他の利用は、この開示を再考することで理解される。例えば、サッカーゲームの１つ以上のボロノイ図は、戦略エンジンが、誰がフィールド上で点を「所有」するのか、および、どのプレイヤーが他のプレイヤーに近いのかを決定する必要があるときはいつでも、利用され得る。点の所有権は、目的をパスし、かつ、マークするために有用である。なぜなら、所有権は、誰が最初にその点まで達し得るのかを示すからである。「マーキング」は、守備側のプレイヤーがどこをカバーするべきか、または、どの対戦者をカバーするのかを決定することを表す。さらに他の利用は、「与えて進む（ｇｉｖｅ ａｎｄ ｇｏ）」パス、ラン、新しいパスモデル、および「スルーパスロジック」を評価することを含む。ボロノイ図のジオメトリを利用することによって、フィールドの全ての点が一度に割り当てられ、該当する各点が別々にテストされなければならない場合よりも簡単かつ徹底的に何をすべきかの戦略評価を可能にする。
【００４２】
ボロノイ空間が野球場の場合、対応する戦略エンジンは、誰がフライボール等をキャッチすることを試みているのかを決定する必要があり得る。上述の技術はまた、コンバット解析および戦略プラニングが同様の技術により行われ得る場合、リアルタイムのストラテジーのゲームのために利用され得る。リソース（学校、消防署等）の最適配置のプラニングを行うシミュレーションゲームは、本明細書に記載される技術のいくつかを含む空間の解析を利用し得る。リアルタイムストラテジーゲームのようないくつかのゲームでは、ボロノイセルは、ゲームのちょうどプレイヤーまたはアクターによって規定され得るが、いくつかの図はまた、建物、危険区域、および他の障害物のような他のオブジェクトを含み得る。これらは、これらに向かってまたはこれらから操縦するオブジェクトとして一般化され得る。
【００４３】
ここで、いくつかのバリエーションに沿って、コンピュータゲームの解析のシステムが説明される。ボロノイ分割の利用は、効率的で一貫性のある方法で、スペースの所有権およびプレイヤーの近接性を決定する等、ゲームの戦略上の問題に対する素早いソリューションを可能にする。この情報が一旦決定され、ゲームを実装するプログラムコードを通して参照される場合、戦略コードの効率および理解可能性が改善される。さらに、これらの技術は、コンピュータ制御される対戦者のより現実的かつダイナミックな行動を可能にする。本明細書中に記載される方法は、コンピュータゲームにおける新しい特徴を可視化し、かつ、実装することに対して極めて有用である。
【００４４】
本発明は、好ましい実施形態を参照して説明された。変更および代替物が当業者には理解される。単なる例として、上述のボロノイ分割は、分割距離関数（すなわち、スペースを分割するために利用されるルール）が統一されており、距離の距離関数であることを前提としていた。しかし、本発明はまた、ボロノイ分割に適用し得る。ここで、スペースは、ちょうどボロノイサイトまでの距離以外の関数によって分割されるか、あるいは、異なるサイトに利用される距離関数が異なる。
【００４５】
例えば、２つのサイトから等距離にある点の集合によって規定される、２つのサイト間にボロノイエッジを有する代わりに、エッジは、点の集合によって規定され得る。ここで、あるサイトまでの距離は、他のサイトまでの距離よりも大きくなるように重み付けされるか、エッジ上の各点において等しくなる関数は、単なるそのサイトからの距離の線形関数ではない。このような関数は、プレイヤーが、異なる「強度」関数を割り当てられ、これらの関数がボロノイ分割を実行するために利用されるゲームの場合に、有用となり得る。このように、チームのプレイヤーは強度、敏感さ、およびスピード属性を割り当てられ、それに応じてボロノイ分割が行われる。有効であれば、これは、コンピュータ解析が、いくつかの状況では実際のサッカープレイヤーが考慮するものと同じ解析を行う一方法となり得る。いくつかの状況とは、例えば、サッカープレイヤーが、最も近い対戦者が平均的なプレイヤーである場合は、ある方向にボールをキックするが、その対戦者が平均以上のプレイヤーとして識別されるときは、最も近い対戦者からさらに離れているボールをキープする異なる角度にボールをキックする。
【００４６】
バリエーションの他の例として、多くのゲームは、２人の人間の競争者が互いについて計算することを可能にし得、この場合、コンピュータは、ゲームの任意の解析を実行する必要がなくなり得る。しかし、ゲームは、とにかく解析を実行し得、１人のプレイヤーまたは両方のプレイヤーをアシストする。さらなる別の例として、コンピュータゲームは、シミュレーションゲーム等の、スポーツに関連しないストラテジーゲームであってもよい。
【００４７】
従って、添付の特許請求の範囲によって提供される場合を除いて、本発明を制限することは意図されない。
【図面の簡単な説明】
【００４８】
【図１】図１は、本発明の複数の局面による解析に利用可能な、上のボロノイ図がかさなったサッカー場の一部分の図である。
【図２】図２は、本発明が実装され得るコンピュータゲームハードウェアシステムのブロック図である。
【図３】図３は、ゲーム状態のデータ構造の例を示す。
【図４】図４は、プレイヤーの次の動き決定するプロセスを示す。
【図５（ａ）】図５（ａ）は、ゴールキーパーのいない第１のチームのボロノイ図を示す。
【図５（ｂ）】図５（ｂ）は、ゴールキーパーのいる第１のチームのボロノイ図を示す。
【図５（ｃ）】図５（ｃ）は、ゴールキーバーのいない第２のチームのボロノイ図を示す。
【図５（ｄ）】図５（ｄ）は、ゴールキーパーのいる第２のチームのボロノイ図を示す。
【図５（ｅ）】図５（ｅ）は、ゴールキーバーのいない両チームのボロノイ図を示す。
【図５（ｆ）】図５（ｆ）は、ゴールキーパーのいる両ボロノイ図を示す。
【図６（ａ）】図６（ａ）は、オフサイドライン上で勝つためのランを決定するために利用可能なボロノイ図によって分割されるフィールドの透視図である。
【図６（ｂ）】図６（ｂ）は、パス領域を決定するために利用可能なボロノイ図によって分割されるフィールドの透視図である。
【図６（ｃ）】図６（ｃ）は、マーキング解析に利用可能な２つのチームのデローニ三角分割である。
【図６（ｄ）】図６（ｄ）は、フィールド表示の透視図からの、２つのチームのデローニ三角分割である。
【技術分野】
【０００１】
（発明の分野）
本発明は、概して、コンピュータゲームに関し、より詳細には、コンピュータゲームにおいてゲーム状況を解析し、解析結果をグラフィカル形式で表示することに関する。
【背景技術】
【０００２】
（発明の背景）
通常の対戦型コンピュータゲームは、人間の対戦者およびコンピュータの対戦者に関係する。このような対戦型コンピュータゲームは、チェス、自動レーシング、ファンタジーゲーム、およびスポーツゲームを含む。ゲームが人間の対戦者の関心を維持するためには、人間の対戦者が毎回勝たない十分な対戦者が必要である。従って、最も単純なコンピュータゲームを除く全てにおいて、解析という要素が必要とされる。この解析は、現在のゲーム状況に基づいてなされ、コンピュータゲームによって利用されて、コンピュータの対戦者の次の動きを決定する。
【０００３】
例えば、ゲームがチェスである場合、コンピュータゲームは、ゲームの状況、すなわち、チェス盤のチェスピースの現在の位置、および人間の対戦者によって取られた動きの履歴を解析するようにプログラムされ、このゲームの状況に応じて、どのような動きを取るべきかについての決定を行う。チェスのルールは、解析および応答に制約を与え、コンピュータは、各動きごとに、１６以下のピースのうちのどれが、たった６４個の別々の位置に制約を受ける盤内の数ダースのスペースのうちの１つに移動するかを決定する必要があるのみである。従って、全ての可能な動きの決定は、非常に単純な態様である。もちろん、チェスのコンピュータの対戦者は、プログラミングすることが難しいが、それは、動きは、将来の多くの動きを予想されなければいけないからである。
【０００４】
レーシングゲームでは、コンピュータに操作されるレースカーまたはオブジェクトは、まさに、トラックに沿って迅速に移動される必要がある。ファンタジーゲームでは、可能となるアクションは、任意であり得る。現実のように実世界のアクティビティをシミュレーションするスポーツゲームおよび他の対戦型ゲームは、部分的により困難である。なぜならば、フィールドは、小さな別々のポジションの集合ではなく、ゲームは、人間の対戦者が対応する実世界の活動において期待するように振舞わなければならないからである。
【０００５】
１つの例として、サッカーのゲームは、数人のプレイヤー、および、連続的な２次元空間（可能であれば、プレイヤーがジャンプし、ボールの高さが考慮される場合は、３次元空間である）でどこにでも自由に移動するボールを含む。サッカーの戦略は、１人のプレイヤーが、対戦チームのプレイヤーからの干渉なくチームメイトにボールを蹴ることができるようにプレイヤーを配置しようとすること等、多くの考慮すべきことを含む。人間の対戦者とコンピュータの対戦者との間でプレーされるコンピュータ計算されたサッカーゲームが興味深いものであるためには、コンピュータの対戦者は、人間の対戦者にチャレンジを与えなければならず、従って、コンピュータゲームは、徹底的にゲーム状況の解析を実行しなければならず、コンピュータの対戦者チームメンバをどのように動かし、かつ操作するかを決定して、チャレンジを与えなければならない。好ましくは、コンピュータゲームで利用可能な消費電力量にいくらかの制限が与えられた場合、コンピュータの解析は、ゲームがゲーム状況を解析し、実世界で適切な応答を形成することができるように、十分に効率的である。
【発明の開示】
【課題を解決するための手段】
【０００６】
（本発明の簡単な要旨）
コンピュータゲームにおいて、本発明の１つの実施形態は、複数のゲーム要素の状態を利用してゲーム状況を解析することを提供する。これは、各複数のゲーム要素についての状態を決定し、少なくともいくつかのゲーム要素をボロノイサイトとして利用して、ゲーム要素の間のボロノイ図の表現を生成し、ボロノイ図を利用してゲーム状況の解析を実行することによる。この解析は、戦略解析の基本として利用され得る空間的解析であり、コンピュータ制御されたエンティティの動きを決定する。特定の実施形態では、ゲームスペースは、２次元のサッカー場であり、ゲーム要素は、チームに関連付けられたプレイヤーである。ゲームスペースは、３次元のゲームスペースであってもよい。ゲームスペースは、サッカー場ではなく、野球場、バスケットコート、またはほかのゲームスペースを表現してもよい。
【０００７】
ゲーム要素の状態は、モーメント、スピード、移動の方向、速度、および／またはゲーム要素のチーム関連性を含み得る。サッカー場の解析は、コンピュータ制御されたチームのプレイヤー間のレーンのパスを決定することを含む。サッカーゲーム解析では、ゴールキーパーのいない各チームのプレイヤーのボロノイ図、ゴールキーパーのいる各チームのプレイヤーの図、ならびに、ゴールキーパーがいる場合およびいない場合の２つのチームのプレイヤーの組み合わせの図のような、複数のボロノイ図が生成され得、この複数のボロノイ図を用いて解析がなされる。
【０００８】
本発明のほかの特徴および利点は、以下の詳細な説明および好ましい実施形態の観点から明らかになる。
【発明を実施するための最良の形態】
【０００９】
（発明の詳細な説明）
ここで図面を参照して、本発明の実施形態がここで説明される。図面の構成要素が参照番号とともに呼び出される場合、同様の参照番号は、同様の構成要素を表し、構成要素の同一のインスタンスを表す場合もあれば、表さない場合もある。
【００１０】
この開示全体を通して、ボノロイ図が参照される。スペース内に「ボロノイサイト」として示される点の集合が与えられると、そのスペースは、領域「ボロノイセル」の集合体に分割され得る。このとき、ボノロイサイトが関連するボロノイセルを有し、関連するボロノイセル内の各点は、任意の他のサイトよりもそのセルのサイトに対して近くなる。本明細書中において利用される際には、「ボロノイ分割」は、空間をボロノイセルに分割するプロセスを示すために利用され、ボロノイ図は、これらのボロノイセルの示す図である。
【００１１】
ボロノイ図を表現する同一の情報を表現する多くの方法が存在することを理解されたい。スペースが曲線によって結合されない場合、各セルは、セルの有限個の頂点のポジションによって記述され得る。従って、ボロノイ図の表現の生成は、このような図の表示を生成することに制限されるように構成されるべきではなく、セルの結合についての情報を生成する任意の方法をカバーし得る。
【００１２】
ボノロイ図の定義は、平面分割として定義されることがあるが、本明細書中に記載される方法および装置は、凸、凹、無限、曲線、多角形、またはこれらの特徴のいくつかの組み合わせとなり得る３（またはＮ）次元空間に分割するために利用され得るので、本明細書中では同様の定義に制限されないことが理解されるべきである。ボロノイサイトは、点であってもよいし、あるいは、多角形のオブジェクトまたは他の次元を有するオブジェクトであってもよい。
【００１３】
ボロノイ図は、数学の分野では周知であり、サイトの集合からボロノイ図を生成するために、多くの計算方法が利用されるので、定義、ならびに、ボロノイ図の生成のための従来の方法および装置は、ここで示される必要はない。従来の方法が利用され得るが、いくつかの例では、さらに高度な性能が必要とされ、この場合、本明細書中に記載されるボロノイ分割を実行する計算上のバリエーションのいくつかまたは全てが利用され得る。
【００１４】
図１は、上にボロノイ図のかさなったサッカー場の一部分を表現する透視図である。ここで、ボロノイスペースは、サッカー場（２次元）であり、ボロノイサイトは、チームの１人のプレイヤー（チームのゴールキーパーを含む）から複数のプレイヤーまでの、プレイヤーのポジションに一致する。図１は、このような図を生成し、その図をコンピュータゲームの解析に利用する装置および方法の以下の説明を理解しやすくするために提供される。図１の視点では、より暗いチームカラーの２人のプレイヤーおよびより明るい色のチームカラーの３人のプレイヤーが図示される。より暗いチームのプレイヤーの１人が、現在のボール保持者１０であり、もう一人のプレイヤーが潜在的なパスの受け側１１である。ライン１２は、相対的なフィールドポジションを示し、サッカー場を表すために本明細書中に含まれる、サッカー場のラインである。図の他のラインは、ボロノイセル間の分割を表し、ボロノイ図を示す。
【００１５】
本明細書中で説明されるように、ボロノイ図、終端または頂点を利用する１つの解析は、対戦者がパスをインターセプトすることができないボールのパス方法の解析である。例として、ボールのターゲットは、プレイヤー１１のボロノイセル１６を分割するラインセグメント１４に沿って存在し得る。ボロノイ分割のために、ラインセグメント１４上の点の全てが、あらゆる他のプレイヤーよりもプレイヤー１１により近くなることが既知であり、このような知識は、多くの座標点をテストまたはサンプリングする必要なく得られる。
【００１６】
図２は、本発明が実装されるサンプルのコンピュータゲームハードウェアシステム１００のブロック図である。システム１００は、ディスプレイ１０４、および、ゲームユーザとやりとりするために利用可能な入力／出力（Ｉ／Ｏ）デバイス１０６に接続されるコンソール１０２を含むように示される。コンソール１０２は、プロセッサ１１０、プログラムコード格納装置１１２、一時的データ格納装置１１４、およびグラフィックプロセッサ１１６を含むように示される。
【００１７】
プログラムコード格納装置１１２は、ＲＯＭ（リードオンリーメモリ）、ＲＡＭ（ランダムアクセスメモリ）、ハードディスク、他の磁気格納装置、光学格納装置、他の格納装置、あるいはこれらの組み合わせまたは変形であり得る。通常の構成では、プログラムコードの一部分がプログラム可能なＲＯＭ（ＲＯＭ、ＰＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ等）に格納され、プログラムコードの一部分がＣＤ−ＲＯＭ１２０（図示される）等の取り外し可能メディアに格納される。あるいは、プログラムコードの一部分は、カートリッジ、メモリチップ等に格納されてもよいし、必要ならばネットワークまたは他の電気的チャネルを介して取得されてもよい。
【００１８】
一時的データ格納装置１１４は、必要ならば、変数ならびに他のゲームおよびプロセッサデータを格納するために利用される。通常、一時的データ格納装置１１４はＲＡＭであり、ゲームのプレー中に生成されるデータ、例えば、各プレイヤーの状態（ポジション、方向等）およびボロノイ分割の結果のような解析のために生成されるデータを保持する。
【００１９】
図３は、ゲームがプレーされているときに一時的データ格納装置１１４に格納され得るゲーム状態のデータ構造の例を示す。ここで示されるように、ゲーム状態構造は、第１のチーム構造および第２のチーム構造に分割され、各チーム構造は、プレイヤー構造に分割される。各プレイヤー構造は、１人のプレイヤーに関連するデータにより示される。図に示される例では、チーム「Ａ」の第１のプレイヤー構造は、プレイヤーの番号（２３）、プレイヤーのポジション（ＦＢ−フルバック）、フィールド上の位置（０．４９７、０．３８６）等を表すプレイヤーデータを保持する。図示されるように、このゲーム構造はまた、ボールのポジション、ボールの速度、現在のスコア、ゲーム時間等の構造を含む。
【００２０】
図２〜３は、本発明の方法および装置を利用し得るコンピュータゲームシステムの例を示しており、本発明は、この例に制限されないことを理解されたい。従って、本発明は、図２に示されるハードウェア構成以外のハードウェア構成、および、図３に示されるデータ構造以外のデータ構造により用いられ得る。
【００２１】
図４は、プレイヤー、通常はコンピュータ制御のチームプレイヤーの次の動きを決定するプロセスを示す。通常、このプロセスは、ゲームシーケンスのより上位の動作によって開始され、図に示されるプロセスの結果は、より上位の動作によって利用され得る。例えば、より上位の動作は、ゲームおよびユーザとのインタラクションを実行するメインプログラムであってもよいし、図４に示されるプロセスは、メインプログラムが動きを作る必要があるときに呼び出されるサブルーチンである。戦略解析プロセスによって決定される「次の動き」は、チェスおよび他のゲームでは一般的であるように、分散型の動きであってもよいし、あるいは、ゲーム要素のゲームスペース位置への運動または要請等の、比較的分散型にならないように定義された動きであってもよいことを理解されたい。この解析は、分離した次の動きを決定するか、または、動きまたは戦略の次のシーケンスを決定するためだけに用いられてもよい。
【００２２】
図示される方法は、ゲーム状態の評価（ステップ１）により開始する。これは、各当該プレイヤーのいる場所、プレイヤーのモーメント、ボールのポジション、ゲーム時間等を決定することを含み得る。一旦ゲームが評価されると、フィールドはボロノイセルに分割される（ステップ２）。本明細書中で説明されるように、セルは、プレイヤーの位置に位置するそれぞれのサイトに最も近い点の集合体として規定され得る。しかし、いくつかの実施形態では、この距離関数（ｍｅｔｒｉｃ）は、常に均一で線形距離の距離関数ではなく、距離および／または他の変数の重みづけされたおよび／または非線形距離の測定基準であってもよい。
【００２３】
ゲーム状態は、通常、瞬間の状態であり、すなわち、ゲーム状態は、時間に伴い変化する。従って、結果として生じるボロノイ分割はまた、時間を介して変化し得る。もちろん、ゲーム状態は、瞬間のスナップショットでなくてもよいし、現在の瞬間の時間の状態だけでなく最近のゲームイベントの状態を考慮に入れてもよい。データを維持するボロノイ分割の再計算の頻度は、必要に応じて変更し得、ゲームプレイのレベル（より洗練された処理は、より高速の更新を必要とし得る）および処理能力（より遅いマシンは、より頻度の低い更新を必要とし得る）を考慮する。いくつかの実装例では、再計算の速度は、ゲームウィンドウ更新速度と同期する。
【００２４】
一旦フィールドが分割されると、結果として生じるボロノイ図は、可能なアクションを解析するために利用される（ステップＳ３）。アクションは、どこにプレイヤーを動かすか、どこにボールを動かすか、およびいつパスするか等を含む。この図はまた、パスする側から受け側までボールをパスする前に受け側およびパスする側をどのように動かすか、あるいは、ゴールにおいてシュートを阻止するためにどのようにゴールキーパーを動かすか等、複数のプレイヤーのアクションを決定するために利用され得る。実際のボロノイ図が、実際に生成される必要はなく、戦略エンジンまたは他の解析を実行するコンピュータエレメントは、ボロノイ頂点、および／または終端等の表示のような、ボロノイ分割の結果を表示する必要があるのみであることを理解されたい。アクションがヘッダ、クロス、コーナーキック等を含む場合、三番目の次元（高さ）が考慮に入れられ得る。
【００２５】
一旦可能なアクションがステップＳ３で決定されると、オフサイドおよびアウトオブバンウズルールのようなルールが課された制約条件を考慮する等、他のファクタが考慮され得る（ステップＳ４）。例えば、解析が、潜在的な受け側が実際にアウトオブバウンズまたはオフサイドであることを決定した場合、この解析は、その人間にパスをさせないように調節され得る。一旦他のファクタが考慮されると、戦略エンジンは、取るべきアクションを決定する（ステップＳ５）。
【００２６】
ボロノイ分割（ステップＳ２）を行うステップは、１つのボロノイ図（またはその表現）を生成するステップであり得るが、異なるサイトの集合ごとに、１つより多いボロノイ図を生成するステップであってもよい。特に、１つのボロノイ図は、サイトとしてのサッカー場のサッカープレイヤーのポジションを利用し、ステップＳ３の解析は、ステップＳ２の結果（分割）をサッカーゲームの他の幾何学的特性とを組み合わせて、コンピュータおよび人間が制御するプレイヤーの戦略オプションを計算する。他の幾何学的特性の例は、オフサイドラインの現在のポジション、ハーフライン、またはペナルティエリア（ゴールキーパーがその手を利用することができる場所、および、守備側のファールがペナルティショットになる場所を規定する際に有用である）のような客観的特性を含む。幾何学的特性はまた、「フランク（ｆｌａｎｋ）」等、ゲームスペースの領域に割り当てられた主観的な特性を含み得る。このフランクは、明らかにラインで引かれた領域（単数または複数）あるいはフランク内の点からフランク外の点へのゆるやかな遷移を有する領域のどちらかとして規定される。他の主観的特性は、「シューティング領域」を含み得る。客観的および主観的特性に加えて、解析はまた、プレイヤーの期待されるヘディングのような派生した特性を含み得る。
【００２７】
この組み合わせは、攻撃側および守備側のプレイヤーがフィールド上に自分自身をポジショニングすべき場所を決定すること、プレイヤーが攻撃側のランを行うべき時および場所を決定すること、プレイヤーがボールをドリブルすべき時および場所を決定すること、プレイヤーがボールをパスすべき時および場所を決定すること、戦略上のパターンマッチングを決定すること、守備側のマーキングロジックを決定すること、衝突の回避／検知を決定すること、および／または、戦略スクリーン上のインジケータを決定すること等、広範囲の戦略情報を計算するために有用である。プレイヤーをどこに配置するか等、戦略情報の決定のされ方の詳細は、後述される。
【００２８】
特定の実施形態では、戦略解析は、図５に示されるような、６つの異なるボロノイ図を利用する。２つのチームが「チームＡ」（四角内に書き入れられることによって）および「チームＢ」（開いた円によって示される）によってラベル付けされ、６つの図（および以下に利用される速記）は、
図５（ａ）−ゴールキーパーのいないチームＡ（ＶＤ−Ａ）
図５（ｂ）−ゴールキーパーのいるチームＡ（ＶＤ−Ａｇ）
図５（ｃ）−ゴールキーパーのいないチームＢ（ＶＤ−Ｂ）
図５（ｄ）−ゴールキーパーのいるチームＢ（ＶＤ−Ｂｇ）
図５（ｅ）−ゴールキーパーのいない両チームＶＤ−ＡＢ）
図５（ｆ）−ゴールキーパーのいる両チーム（ＶＤ−ＡＢｇ）
これらの図は、Ｆｏｒｔｕｎｅ，Ｓ．Ｊ．「Ａ Ｓｗｅｅｐｌｉｎｅ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｖｏｒｏｎｏｉ Ｄｉａｇｒａｍｓ」、Ａｌｇｏｒｉｔｈｍｉｃａ、２：１５３〜１７４（１９８７）に記載されるインクリメントするアルゴリズム等、インクリメントするアルゴリズムを用いて計算され得る。サッカーゲームの改変例では、標準的なインクリメントするアルゴリズムは、第１のパスで利用され、その後、ゲームの残り全体を通じて、インクリメントするアルゴリズムを開始するために利用された最初の推測は、前回のボロノイ図に基づく。これは、図が計算されるたびにサイトがほんの少しの量だけ動くことが期待される場合、サッカーゲームと同様の他のアプリケーションにおいて有用である。
【００２９】
さらに、図を計算する仕事は、３つ以上のフレームに分割され得、ホームチームの図は、第１のフレームで計算され、遠征チームの図は、第２のフレームで計算され、両チームの図は、改良された効率の前回の２つの計算に基づいて、第３のフレームで計算される。プレイヤーの現在のポジションは、ボロノイ分割のサイトとして利用され得るが、予測がプレイヤーの現在のポジションおよび現在のモーメント（または、スピード、速度等）に基づく場合、プレイヤーの予測された未来のポジションが代わりに利用されてもよい。ある例では、プレイヤーのポジションを利用するだけでは、プレイヤーが、そのプレイヤーの後ろよりもプレイヤーの前の点に達することがより容易であるという事実を考慮していない。プレイヤーのポジションをほんの少し前へオフセットすることによって、運動の方向に、プレイヤーのスピードと比例して、モーメントおよび回転を考慮する距離関数を利用するよりも、標準的な線形距離関数を利用して、図のより近い近時が可能になる。さらに、後者は、計算が非常に大変である。
【００３０】
（空間的戦略的解析）
ここで、ボロノイ分割の結果を利用する（ボロノイ図またはボロノイ図の表現を利用する）戦略解析の基準として利用され得る空間的解析のいくつかの例が説明される。これらの例では、フィールドはサッカー場であり、２つのチームはチームＡおよびチームＢである。実装例に応じて、どちらかのチームがコンピュータ制御されたチームであり、もう一方のチームが人間のユーザに制御されたチームである。あるいは、両チームが人間のユーザに制御されたチームであってもよいし、両チームがコンピュータ制御されたチームであってもよい。典型的なコンピュータゲームは、コンピュータ制御されたチームおよび／または人間のユーザに制御されたチームのストラテジーの決定を行うことができる戦略エンジンを含み得る。後者の場合、決定は、学習モードまたはアシストモードの一部分であってもよし、人間のユーザが補助なく全てのストラテジーの決定を行いたい対戦モードでは、オフにされてもよい。
【００３１】
プレイヤーポジショニングは、ゲーム中になされ得る１つの解析である。プレイヤーポジショニング解析は、プレイヤーを動かす、または、再ポジショニングする方法を決定するために利用可能である。例えば、様々なボロノイ図を検査して、ボールに最も近いプレイヤーならびにプレイヤー「最も近い仲間」であるチームメイトおよび／または対戦者を識別し得る。プレイヤーＯから仲間まで引かれたラインから、パスレーンを決定することができ、別のボロノイ図を用いて、どのチームメイトがこれらのパスレーンに最も近いかを計算し得る。この情報に基づいて、チームメイトは、これらのラインへ動き、パスのために自分自身をポジショニングする。プレイヤーポジショニングおよび他のストラテジーは、対戦者によって採用されたチームフォーメーション、例えば、４−４−２または３−５−２によって知らされ得る。
【００３２】
攻撃側ランは、ＶＤ−ＡＢ（または、たまにＶＤ−ＡＢｇ）を用いて計算される。この例は、図６（ａ）に示される。攻撃チーム（チームＡ）の任意のプレイヤーが、オフサイドラインよりもチームＢのネットに近いＶＤ−ＡＢ上にボロノイ頂点を有する場合、そのプレイヤーは、その頂点（図の頂点６０２）まで攻撃側のスルーランを行う。これは、プレイヤーが、フィールド上の他の誰よりも前にそのプレイヤーがスペースのピースまで達することができることを理解している場合のプレイヤーの行動をモデル化する。この点は、オフサイドライン（図のライン６０４）よりも後ろにあるので、ランは、離脱する結果となり得る。この説明から理解されるべき、最も適切なボロノイ図を用いる際には、注意がなされるべきである。例えば、ゴールキーパーがいそうなフィールドのエリアにおいてＶＤ−ＡＢが攻撃側ランに用いられる場合、ボールは、反対のゴールキーパーまでまたはその近くまでパスされてもよいし、ＶＤ−ＡＢｇが利用される場合は、ゴールキーパーのポジションが考慮される。
【００３３】
攻撃側ランの決定に加えて、攻撃ランについて上述されたプロセスは、守備側によって利用され得、それぞれの守備側のポジショニングの穴を識別し、それに応じて調節する。
【００３４】
衝突を回避するボールのドリブルは、別の戦略解析である。この解析により、ボールを有するプレイヤーにフィールド上のターゲット点までドリブルさせるためには、プレイヤーは、ターゲット点に最も近いＶＤ−ＡＢからボロノイ頂点に向かってドリブルすべきである。結果として生じる行動は、プレイヤーにその点に迅速に到着させつつ、チームメイトおよび対戦者を避けて、非常にサッカープレイヤーのように見える方法で動き、適切である場合にはフェイントおよび突然のヘディング変化を含む。
【００３５】
ボールパス決定は、ＶＤ−ＡＢｇを利用して、ボールをチームメイトまでパスする最良の場所を決定する。解析の目的は、ＶＤ−ＡＢｇにおける現在のボール保持者（「プレイヤーＢＨ」と呼ぶ）のボロノイセル内の点までボールをパスすることである。これは、図６（ｂ）によって図示され、ここで、パスする側６１２は、チームメイト６１３までのパスを考慮する。図示されるように、適切な受け側である２人のプレイヤーが存在する。ＶＤ−ＡＢのような他の図を利用することができるが、ゴールキーパーは考慮に入れられない場合、ボールは、反対のゴールキーパーがボールに最初に達し得るようにパスされ得る。これは、通常、望まれない。
【００３６】
ボールがパスされるターゲット点を決定するために、いくつかの技術が利用され得る。１つの技術では、コンピュータは、ＢＨの面するベクトルおよび受け側（単数または複数）のボロノイセルを分断して、その分断ラインにそった可能な受け取り点の範囲を得る。これらの点は、図６（ｂ）の分断ラインセグメント６１４に沿った点であり、分断ラインセグメント６１４（ａ）は、受け側６１３（ａ）がパスを受け、任意の他のプレイヤーよりも前に到達し得る点の集合であり、分断ラインセグメント６１４（ｂ）は、受け側６１３（ｂ）がパスを受け、任意の他のプレイヤーよりも前に到達し得る点の集合である。パスする側からの分断ラインセグメントの方向は、受け側の運動ベクトルの方向、あるいは、コンピュータまたはユーザによって選択される別の方向となり得る。また、解析は、依然として受け側がボールに最初に達することを保証しつつ、その受け側を最大に導く受け側のボロノイセル内の点を探し得る。分断ラインセグメントを考慮に入れると、ボールキックの提示されるパワーは、ボールが好ましいまたは最適のスピードで、好ましいまたは最適の時間に受け側のボロノイセルに到達するように、決定され得る。
【００３７】
ＶＤ−Ｂのようなボロノイ図のトポロジーは、戦略パターンマッチングのために利用され得る。どのパターンが識別されるのかに応じて、特徴とマッチする他のボロノイ図が保存され、利用され得る。サッカーゲームにおいてある状況が識別される場合、ボロノイ図のトポロジーが保存され得る。これは、エッジ角度、エッジ長、ボロノイの近隣者、およびボロノイセルエリアを含む。同一のトポロジーが後のゲームで識別される場合、その特定の状況に適切な予め定められた行動に基づいて、アクションが取られ得る。このように、同一ではないゲーム状態が、類似のゲーム状態に類推され得ることにより、比較的少ない数の予め定められた行動が記憶され、比較的多い数のゲーム状態に応じて利用され得る。
【００３８】
「守備側マーキングロジック」では、所与のプレイヤーのＶＤ−ＡＢにおけるボロノイの近隣者を利用して、そのプレイヤーがマークする潜在的な対戦者を決定する。「マーキング」は、守備中のプレイヤーがどの攻撃側プレイヤーをカバーするのかを決定するプロセスである。これは、極めて効果的である。なぜなら、マーキングアルゴリズムで考慮される必要があるプレイヤーの数を減少させることができるからである。あるいは、デローニ三角分割図が利用され得る。デローニ三角分割図は、「２重の」ボロノイ図であり、エッジを共有するセル内にあるボロノイサイトのペア間に引かれたラインセグメントを含む。デローニ三角分割図の一部分の例は、図６（ｃ）に示される。ここでは、チームメイト間のラインは、（ボロノイセルのエッジを共有する対戦者をペアにするラインのみを残して）排除されている。これらのラインは、マーキングの良好な座標を示す。デローニ三角分割図は、ある解析においてボロノイ図の適切な代替となり得ることを理解されたい。図６（ｄ）は、デローニ三角分割図が重ねられたサッカー場の表現の透視図である。
【００３９】
基本の６個以外の解析では、他のボロノイ図が利用され得る。例えば、怪我をしたプレイヤー（怪我をしているが、フィールドに残っている）が、図から排除され得ることにより、怪我をしたプレイヤーが考慮されなくなるような、解析がなされ得る。他の図では、１つのチームからのチームプレイヤーが、その反対のチームに加えられ得、わずかに異なったボロノイ図を取得する。さらに別の図では、ボール保持者が反対のチームのボロノイ図へと動く。通常の場合、ボロノイ図は、１つまたは両チームからのプレイヤーの任意の集合を有する解析のために、容易に生成され得ることを理解されたい。試合の関係者は、通常考慮されるべきではないが、試合の関係者も、適切である場合は含まれ得る。
【００４０】
１つ以上のボロノイ図がスクリーン上に与えられ得る。ＣＤ−ＡＢまたはＶＤ−ＡＢｇが与えられた場合、各チームのセルは、異なるように色が付けられ得る。これは、人間のユーザの洞察力をユーザのチームが所有するスペースに与え、戦略上の利点を与える。このバリエーションは、スクリーンのエッジのみにボロノイ図を与えることである。これは、スクリーンの外のプレイヤーが配置される場所についての考え、および、スクリーンの外にいるプレイヤーに対してなされる潜在的な成功をユーザに与える。
【００４１】
ボロノイ図の他の利用は、この開示を再考することで理解される。例えば、サッカーゲームの１つ以上のボロノイ図は、戦略エンジンが、誰がフィールド上で点を「所有」するのか、および、どのプレイヤーが他のプレイヤーに近いのかを決定する必要があるときはいつでも、利用され得る。点の所有権は、目的をパスし、かつ、マークするために有用である。なぜなら、所有権は、誰が最初にその点まで達し得るのかを示すからである。「マーキング」は、守備側のプレイヤーがどこをカバーするべきか、または、どの対戦者をカバーするのかを決定することを表す。さらに他の利用は、「与えて進む（ｇｉｖｅ ａｎｄ ｇｏ）」パス、ラン、新しいパスモデル、および「スルーパスロジック」を評価することを含む。ボロノイ図のジオメトリを利用することによって、フィールドの全ての点が一度に割り当てられ、該当する各点が別々にテストされなければならない場合よりも簡単かつ徹底的に何をすべきかの戦略評価を可能にする。
【００４２】
ボロノイ空間が野球場の場合、対応する戦略エンジンは、誰がフライボール等をキャッチすることを試みているのかを決定する必要があり得る。上述の技術はまた、コンバット解析および戦略プラニングが同様の技術により行われ得る場合、リアルタイムのストラテジーのゲームのために利用され得る。リソース（学校、消防署等）の最適配置のプラニングを行うシミュレーションゲームは、本明細書に記載される技術のいくつかを含む空間の解析を利用し得る。リアルタイムストラテジーゲームのようないくつかのゲームでは、ボロノイセルは、ゲームのちょうどプレイヤーまたはアクターによって規定され得るが、いくつかの図はまた、建物、危険区域、および他の障害物のような他のオブジェクトを含み得る。これらは、これらに向かってまたはこれらから操縦するオブジェクトとして一般化され得る。
【００４３】
ここで、いくつかのバリエーションに沿って、コンピュータゲームの解析のシステムが説明される。ボロノイ分割の利用は、効率的で一貫性のある方法で、スペースの所有権およびプレイヤーの近接性を決定する等、ゲームの戦略上の問題に対する素早いソリューションを可能にする。この情報が一旦決定され、ゲームを実装するプログラムコードを通して参照される場合、戦略コードの効率および理解可能性が改善される。さらに、これらの技術は、コンピュータ制御される対戦者のより現実的かつダイナミックな行動を可能にする。本明細書中に記載される方法は、コンピュータゲームにおける新しい特徴を可視化し、かつ、実装することに対して極めて有用である。
【００４４】
本発明は、好ましい実施形態を参照して説明された。変更および代替物が当業者には理解される。単なる例として、上述のボロノイ分割は、分割距離関数（すなわち、スペースを分割するために利用されるルール）が統一されており、距離の距離関数であることを前提としていた。しかし、本発明はまた、ボロノイ分割に適用し得る。ここで、スペースは、ちょうどボロノイサイトまでの距離以外の関数によって分割されるか、あるいは、異なるサイトに利用される距離関数が異なる。
【００４５】
例えば、２つのサイトから等距離にある点の集合によって規定される、２つのサイト間にボロノイエッジを有する代わりに、エッジは、点の集合によって規定され得る。ここで、あるサイトまでの距離は、他のサイトまでの距離よりも大きくなるように重み付けされるか、エッジ上の各点において等しくなる関数は、単なるそのサイトからの距離の線形関数ではない。このような関数は、プレイヤーが、異なる「強度」関数を割り当てられ、これらの関数がボロノイ分割を実行するために利用されるゲームの場合に、有用となり得る。このように、チームのプレイヤーは強度、敏感さ、およびスピード属性を割り当てられ、それに応じてボロノイ分割が行われる。有効であれば、これは、コンピュータ解析が、いくつかの状況では実際のサッカープレイヤーが考慮するものと同じ解析を行う一方法となり得る。いくつかの状況とは、例えば、サッカープレイヤーが、最も近い対戦者が平均的なプレイヤーである場合は、ある方向にボールをキックするが、その対戦者が平均以上のプレイヤーとして識別されるときは、最も近い対戦者からさらに離れているボールをキープする異なる角度にボールをキックする。
【００４６】
バリエーションの他の例として、多くのゲームは、２人の人間の競争者が互いについて計算することを可能にし得、この場合、コンピュータは、ゲームの任意の解析を実行する必要がなくなり得る。しかし、ゲームは、とにかく解析を実行し得、１人のプレイヤーまたは両方のプレイヤーをアシストする。さらなる別の例として、コンピュータゲームは、シミュレーションゲーム等の、スポーツに関連しないストラテジーゲームであってもよい。
【００４７】
従って、添付の特許請求の範囲によって提供される場合を除いて、本発明を制限することは意図されない。
【図面の簡単な説明】
【００４８】
【図１】図１は、本発明の複数の局面による解析に利用可能な、上のボロノイ図がかさなったサッカー場の一部分の図である。
【図２】図２は、本発明が実装され得るコンピュータゲームハードウェアシステムのブロック図である。
【図３】図３は、ゲーム状態のデータ構造の例を示す。
【図４】図４は、プレイヤーの次の動き決定するプロセスを示す。
【図５（ａ）】図５（ａ）は、ゴールキーパーのいない第１のチームのボロノイ図を示す。
【図５（ｂ）】図５（ｂ）は、ゴールキーパーのいる第１のチームのボロノイ図を示す。
【図５（ｃ）】図５（ｃ）は、ゴールキーバーのいない第２のチームのボロノイ図を示す。
【図５（ｄ）】図５（ｄ）は、ゴールキーパーのいる第２のチームのボロノイ図を示す。
【図５（ｅ）】図５（ｅ）は、ゴールキーバーのいない両チームのボロノイ図を示す。
【図５（ｆ）】図５（ｆ）は、ゴールキーパーのいる両ボロノイ図を示す。
【図６（ａ）】図６（ａ）は、オフサイドライン上で勝つためのランを決定するために利用可能なボロノイ図によって分割されるフィールドの透視図である。
【図６（ｂ）】図６（ｂ）は、パス領域を決定するために利用可能なボロノイ図によって分割されるフィールドの透視図である。
【図６（ｃ）】図６（ｃ）は、マーキング解析に利用可能な２つのチームのデローニ三角分割である。
【図６（ｄ）】図６（ｄ）は、フィールド表示の透視図からの、２つのチームのデローニ三角分割である。
【特許請求の範囲】
【請求項１】
プロセッサに結合された格納装置に格納されているコンピュータゲームのゲーム状況を解析する方法であって、該ゲーム状況は、複数のゲーム要素のポジションに少なくとも依存し、
該方法は、
該プロセッサが、ゲームスペースにおいて該複数のゲーム要素のうちの１つのゲーム要素の第１のポジションを決定するステップと、
該プロセッサが、該複数のゲーム要素の少なくともいくつかをボロノイサイトとして利用して、該複数のゲーム要素の間にボロノイ図の表現を生成するステップと、
該プロセッサが、該ボロノイ図を処理することにより、該ゲームスペースにおいて該第１のポジションから第２のポジションに該１つのゲーム要素が移動することを決定するステップと
を包含する、方法。
【請求項１】
プロセッサに結合された格納装置に格納されているコンピュータゲームのゲーム状況を解析する方法であって、該ゲーム状況は、複数のゲーム要素のポジションに少なくとも依存し、
該方法は、
該プロセッサが、ゲームスペースにおいて該複数のゲーム要素のうちの１つのゲーム要素の第１のポジションを決定するステップと、
該プロセッサが、該複数のゲーム要素の少なくともいくつかをボロノイサイトとして利用して、該複数のゲーム要素の間にボロノイ図の表現を生成するステップと、
該プロセッサが、該ボロノイ図を処理することにより、該ゲームスペースにおいて該第１のポジションから第２のポジションに該１つのゲーム要素が移動することを決定するステップと
を包含する、方法。
【図１】
【図２】
【図３】
【図４】
【図５（ａ）】
【図５（ｂ）】
【図５（ｃ）】
【図５（ｄ）】
【図５（ｅ）】
【図５（ｆ）】
【図６（ａ）】
【図６（ｂ）】
【図６（ｃ）】
【図６（ｄ）】
【図２】
【図３】
【図４】
【図５（ａ）】
【図５（ｂ）】
【図５（ｃ）】
【図５（ｄ）】
【図５（ｅ）】
【図５（ｆ）】
【図６（ａ）】
【図６（ｂ）】
【図６（ｃ）】
【図６（ｄ）】
【公開番号】特開２００７−４４５５７（Ｐ２００７−４４５５７Ａ）
【公開日】平成１９年２月２２日（２００７．２．２２）
【国際特許分類】
【出願番号】特願２００６−３１４９０６（Ｐ２００６−３１４９０６）
【出願日】平成１８年１１月２１日（２００６．１１．２１）
【分割の表示】特願２００３−５３９８０３（Ｐ２００３−５３９８０３）の分割
【原出願日】平成１４年１０月２２日（２００２．１０．２２）
【出願人】（３９７０５８９３２）エレクトロニック アーツ インコーポレイテッド (9)
【Ｆターム（参考）】
【公開日】平成１９年２月２２日（２００７．２．２２）
【国際特許分類】
【出願日】平成１８年１１月２１日（２００６．１１．２１）
【分割の表示】特願２００３−５３９８０３（Ｐ２００３−５３９８０３）の分割
【原出願日】平成１４年１０月２２日（２００２．１０．２２）
【出願人】（３９７０５８９３２）エレクトロニック アーツ インコーポレイテッド (9)
【Ｆターム（参考）】
[ Back to top ]