(57)【要約】【課題】集団キャラクタの移動をよりリアルに表現することができる集団キャラクタ移動制御方法を提供する。【解決手段】集団キャラクタの移動において，リーダーについてはあらかじめ求めた経路計画に従って移動し（ステップ４１１），リーダー以外のキャラクタについては，隊形の情報とリーダーの位置から，そのキャラクタの目標位置を求め（ステップ４０３），目標位置がキャラクタから不可視の場合には経路計画を行って目標位置を再設定し（ステップ４０９，４１０），目標到達用加速度，衝突回避用加速度を求めてキャラクタの速度と位置を更新する（ステップ４０５〜ステップ４０８）。【選択図】図１
2005342360.tif 000002
【特許請求の範囲】
【請求項１】
3次元空間上に表現された地形に対して，リーダーを有する複数のキャラクタが集団を形成してあらかじめ設定された目標位置に移動する集団キャラクタ制御方式であって，リーダーの経路を経路計画によって求めてリーダーの移動を制御し，リーダー以外のキャラクタの目標位置をリーダーの位置と方向とあらかじめ設定された隊形情報から求め，リーダー以外のキャラクタの移動を制御することを特徴とする集団キャラクタ移動制御方法。
【請求項２】
前記リーダー以外のキャラクタの移動制御において，リーダー以外のキャラクタの目標位置が該キャラクタから可視か不可視かを判定し，不可視である場合には，目標位置への経路計画を行い，可視の目標位置を設定して，リーダー以外のキャラクタの移動を制御することを特徴とする請求項１に記載の集団キャラクタ移動制御方法。
【請求項３】
前記可視か不可視の判定は，キャラクタの位置と目標位置を結ぶ線分を求め、その線分と地形データとの交差判定を行い、交差が存在する場合には，不可視であり，交差が存在しない場合には可視であると判定することを特徴とする請求項１に記載の集団キャラクタ移動制御方法。
【請求項４】
請求項１ないし請求項２に記載の集団キャラクタ移動制御方法を記録したコンピュータ読み取り可能な記録媒体。
【請求項５】
請求項１ないし請求項２に記載の集団キャラクタ移動制御方法を備えたシミュレーション装置。
【請求項６】
請求項１ないし請求項２に記載の集団キャラクタ移動制御方法を備えたゲーム装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，集団キャラクタの移動方法，記録媒体，シミュレーション装置及びゲーム装置に係り，特に3次元仮想空間上に表現されたリーダーを有する集団が，あらかじめ指定された隊形を保持しつつ，あらかじめ指定された目標点に移動する集団キャラクタ移動方法，記録媒体，シミュレーション装置及びゲーム装置に関する。
【背景技術】
【０００２】
現在，集団で移動するキャラクタの制御は，訓練シミュレーション装置やゲーム装置に不可欠の技術である。
第１の訓練シミュレーションの分野では，コンピュータを用いて戦闘のシミュレーションを行い，訓練を行っている。従来のシミュレーション対象は，陸海空いずれも，広大な戦場を対象とするものが多かった。しかし，近年，市街地戦闘の重要性が高まるとともに，市街地における戦闘のシミュレーションを実施する必要性が高まりつつある。
【０００３】
市街地戦闘の訓練においては，集団キャラクタが隊列を組んで目的地に移動する必要がある。市街地においては，屋外ではビルなどの人工物が多数存在し，屋内では壁などが多数存在する。このために，目的地への移動において，移動可能な領域が限られるため，従来の広大な戦場を対象とした移動制御方法が適用できないという問題があった。
第２のゲームに関する分野においても，隊列を組んだ集団キャラクタを用いた戦闘シミュレーションゲームが開発されている。すなわち，敵味方に分かれた集団キャラクタが戦闘を行うものである。
例えば、プレイステーション２（株式会社ソニー・コンピュータエンタテインメントの登録商標）用として、株式会社光栄が開発した決戦２（）では，敵味方に分かれた集団キャラクタが隊列を組んで移動している。
【０００４】
また、特許文献１には、３次元仮想空間上に表現されリーダーを有する複数のキャラクタが集団を形成して予め設定された目標点に移動する集団キャラクタ移動方法に関する発明が記載されている。
さらに，ゲームやシミュレーション用の群集の移動制御アルゴリズムとして，Reynolds, C． W． : Steering Behaviors For Autonomous Characters, Game Developers Conference 1999 , Pages 763-782 (1999)が，自律キャラクタのさまざまな移動制御方法を提案している。Reynoldsの方法によれば，キャラクタが目的地に向かう制御，他のキャラクタとの衝突回避，障害物との衝突回避，群集の表現が可能である。
しかしながら，上記のゲームなどの移動方法では，市街地のように障害物が多い空間に適用すると膠着状況に陥る場合があり，所望の移動が実現できないという問題があった。
【０００５】
【特許文献１】特開２００１−５６８７０号公報
【０００６】
【非特許文献１】Reynolds, C． W． : Steering Behaviors For Autonomous Characters, Game Developers Conference 1999 , Pages 763-782 (1999)．
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、従来の複数のキャラクタの移動制御は，広大な屋外のように，障害物が少ない状況での適用を前提としていた。このため，市街地のように，人工の障害物が多数存在する場合には，障害物のために，キャラクタが目的地に到達することができずに，膠着状態に陥る場合がある。また，隊形を保持した状態での移動において，リーダー以外のキャラクタの進路が障害物に遮られて，移動不可能となるという問題があった。
【０００８】
本発明は上述したような従来技術の問題点を考慮してなされたものであり，市街地のように人工の障害物を多数含むような３次元空間上で，隊形を保持した複数キャラクタの移動制御を可能とする複数キャラクタの移動制御方法および，その方法を用いたシミュレーション装置，ゲーム装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達せするために本発明は，リーダーを有する複数キャラクタの集団の移動制御において，予め設定された隊形情報と，リーダーの初期位置と方向，リーダーの目標点と方向，隊形の情報，３次元地形情報を入力とし，
a)初期位置から目標点へのリーダーの経路を求める手順，
b)手順aで求められた経路に従い，リーダーを移動制御する手順，
c)予め設定された隊形情報に従い，リーダー以外のキャラクタの目標位置を求める手順，
d)手順ｃで求められた各キャラクタの目標位置が該キャラクタから可視かどうかを求める手順，
e)手順ｄで不可視である場合には，該キャラクタから目標位置への経路を求め，求められた目標位置を該キャラクタの目標位置に再設定する手順，
f)上記の手順によって求められた目標位置に従い各キャラクタを移動制御する手順を含み，手順b〜手順ｆを繰り返すことを特徴とする。
【発明の効果】
【００１０】
本発明によれば，市街地などの障害物を多数含む３次元空間上を複数キャラクタが隊列を維持して移動するシミュレーションが可能となり，リアルな訓練シミュレーション，ゲームを提供できる。
【発明を実施するための最良の形態】
【００１１】
以下，図面を参照して，本発明をシミュレーション装置に適用した形態について説明する。本実施形態では，キャラクタの集団を兵士の集団とし，予め設定された位置に整列させ，目標点に向かって隊列を保持して移動する場合を想定する。
【００１２】
（構成）図２は，本発明の実施形態における移動制御方法を実施するコンピュータの内部構成を示すブロック回路図である。
図２において，データバス１４上には，ＣＰＵ１０，ＲＯＭ１１，ＲＡＭ１２，ハードディスク１３，媒体入力部１６，入力制御部１８，画像生成部１９，音響生成部２１が接続される。
【００１３】
本実施形態のシミュレーションプログラムは，記録媒体１５から媒体入力部１６を用いてＲＡＭ１２に格納される。あるいは，ハードディスク１３から，シミュレーションプログラムをＲＡＭ１２に格納することも可能である。入力装置１７からのユーザの入力情報は，入力制御部１８によってＣＰＵ１０に伝えられる。シミュレーション結果により，画像生成部１９は画像情報を作成し，ディスプレイ装置２０に表示する。また，シミュレーション結果によって，音響生成部２１によってスピーカー装置２２によって，対応する音響を生成する。
【００１４】
（動作）次に，本実施形態の動作についてフローチャートを参照して説明する。
図３に集団キャラクタ移動制御ルーチンのフローチャートを示す。まず，ステップ１０１で，地形データをハードディスク装置１３から読み込み，ＲＡＭ１２に転送する。地形データの詳細は，後に詳しく説明する。次に，集団初期設定処理１０２によって，リーダーを含む集団の人数，隊形，初期位置，初期方向を設定する。次に，目標位置設定処理１０３によって，集団キャラクタの目標位置を設定する。ユーザが移動コマンドを，入力装置１７を用いて発行するまで待機する（１０４）。移動コマンドが発行されると，リーダーの経路計画処理１０５によって，リーダーが目的地に到達するための経路を求める。次に，集団移動処理１０６によって，集団キャラクタ全員の移動を制御する。目標位置到達判定１０７により，集団キャラクタが目標位置に到達したかどうかを判定し，目標位置に到達しない場合には，集団移動処理１０６を繰り返す。目標位置に到達した場合には，ユーザからの入力を待ち，終了コマンドが発行された場合には，終了する（１０８）。終了コマンドが発行されない場合には，目標位置設定処理１０３に処理を移し，再度，目標位置を設定し，集団キャラクタの移動制御を繰り返す。
【００１５】
次に，地形データ読み込み処理１０１で読み込む，地形データの詳細について説明する。地形データは，以下に説明するような，（ａ）３次元地形データ，（ｂ）２次元地図データ，（ｃ）２次元自由領域データの３つから構成される。
本発明の実施形態では，集団キャラクタは３次元空間上を移動する。このため，地形データとして，図６に示す３次元地形データを用意する。３次元地形データは，通常のコンピュータグラフィックスで使用されるような多角形データの集合として定義される。
【００１６】
キャラクタは，３次元空間上を移動するが，その移動は，床などの上を移動するという制限がある。このため，キャラクタが移動可能な領域を２次元地図データとして定義するＶ図４に２次元地図データを示す。図４において，ハッチングされている部分が建物や壁などのように，キャラクタが移動できない部分を示している。
さらに，リーダーの経路計画処理１０５や，後述するキャラクタの経路計画処理４０９のために，図４に示した地図データからキャラクタが移動できる自由領域を多角形に分解した自由領域データを用意する。図５は図４に示した２次元地図データから自由領域データを作成した結果の例である。なお，リーダーの経路計画処理１０５や，後述するキャラクタの経路計画処理４０９の詳細は，後で詳しく説明する。
【００１７】
次に，集団初期設定処理１０２について，図１２のフローチャートを参照しつつ説明する。集団キャラクタの初期設定では，まず，隊員数を設定する（２０１）。隊員数は２以上の任意の整数である。次にリーダーの位置を設定する（２０２）。リーダーの位置設定は，図４に示す２次元地図データ上で，２次元座標（ｘ，ｙ）と方向（θ）によって設定する。さらに，隊形設定２０３によって集団キャラクタがとる隊形を指定する。隊形には様々なものが考えられるが，一例を図８に示す。図８で，(a)は縦隊であり，リーダー以下のキャラクタが一列縦隊に整列する。（ｂ）は２列縦隊，（ｃ）は逆Ｖ字隊形である。以下の例では，逆Ｖ字隊形をとったものとして説明する。
図９は集団初期設定処理１０２の例を示している。図９に示すように，集団キャラクタの位置と方向，集団キャラクタの隊員数（図では，７名）を設定する。なお，図９には，目標位置設定処理１０３によって設定された集団キャラクタの目標位置も図示されている。
【００１８】
次に，リーダーの経路計画処理１０５について，図１３のフローチャートを参照しつつ説明する。自由データ読み込み処理３０１によって，図５に示すようなキャラクタが移動できる自由領域をＲＡＭに読み込む。次に，キャラクタのスタート位置，ゴール位置の読み込み処理３０２によって，キャラクタのスタート位置とゴール位置をＲＡＭに読み込む。次に，Ａ＊アルゴリズムを用いた最短経路探索処理３０３によってスタート位置からゴール位置までの最短経路を求める。なお，Ａ＊アルゴリズムを用いた最短経路探索処理については，例えば，「太田，倉林，新井：知能ロボット入門，コロナ社(2001)」や，「Stout B．: ナビゲーション メッシュによる 3D 移動とパスの発見の単純化, Game Programming Gems日本語版, p. 279-294，ボーンデジタル (2000)」にその詳細が記述されている。図７に経路計画の結果を示す。
【００１９】
次に，集団移動処理１０６について，図１に示すフローチャートを参照しつつ説明する。まず，全員の処理が終了したかどうかを判断する（４０１）。処理済の場合には，集団移動処理を終了する。処理済でない場合には，４０２に進む。４０２では，処理対象のキャラクタがリーダーかどうかの判定を行う。処理対象のキャラクタがリーダーの場合には，ステップ４１１に，リーダーでない場合にはステップ４０３に進む。
【００２０】
処理対象のキャラクタがリーダーの場合には，ステップ４１１によって，リーダーの目標位置を設定する。リーダーの経路はリーダーの経路計画１０５によって求まっているため，この経路の通過点で，リーダーがまだ到達していない点でありかつ，リーダーに最も近い点を目標位置とする。
処理対象のキャラクタがリーダーでない場合には，目標位置演算４０３によって，キャラクタの目標位置を算出する。このステップでは，リーダーの位置と方向，指定された隊形によって，個々のキャラクタの目標位置を算出する。
【００２１】
次に，前記の目標位置がそのキャラクタから可視であるかどうかを判定する（４０４）。可視性の判定は，以下のように行う。まず，キャラクタの位置と目標位置を結ぶ線分を求める。次に，その線分と地形データとの交差判定を行う。交差が存在する場合には，不可視であり，交差が存在しない場合には可視である。
もし，可視であるならば，移動に障害はないためステップ４０５に進む。もし，可視でないならば，そのキャラクタはその方向に向かって進むと膠着状態に陥る危険性がある。このため，経路計画処理４０９によって，その目標位置に到達するための経路を求める。経路計画処理４０９は，リーダーの経路計画１０６と同じ処理を行う。
次に，目標位置再設定処理４０１によって，キャラクタの目標位置を再設定する。この目標位置は，経路計画によって求められた通過点で，いまだ到達していない通過点とする。
【００２２】
以上で，キャラクタがリーダーである場合，リーダーでない場合ともに，各キャラクタの目標位置が設定された。次に，ステップ４０５〜ステップ４０８によって，各キャラクタの位置を更新する。なお，これらの処理手順は，Reynolds, C． W． : Steering Behaviors For Autonomous Characters, Game Developers Conference 1999 , Pages 763-782 (1999)にその詳細が記載されている。
まず，各キャラクタについて，目標到達用加速度演算４０５によって，目標位置に到達するための，加速度Aseekを求める。Aseekの算出方法を図１０を参照しつつ説明する。Aseekはキャラクタを与えられた目標位置に導くための加速度であり，下記の数式によって求める。
【００２３】
【数１】
2005342360.tif 000003
【００２４】
ここで，Vはキャラクタの現在の速度である。また，Δtはシミュレーションの時間間隔である。また，Vdesireは目標位置Ptargetに到達するために最適な速度であり，以下の式によって求める。
【００２５】
【数２】
2005342360.tif 000004
【００２６】
ここで，Pはキャラクタの位置，Vdefaultはキャラクタの標準速度である。以上で，目標到達用加速度演算４０５によって，目標位置に到達するための，加速度Aseekが求められた。
次に，衝突回避用加速度演算４０６によって衝突を回避するための加速度Acollisionを求める。Acollisionの算出方法を図１１を参照しつつ説明する。Acollisionはキャラクタが障害物にぶつからないようにするための加速度であり，以下のようにして求める。まず，下記の数式に時間Ｔ後のキャラクタの位置Ｐpredictを予測する。
【００２７】
【数３】
2005342360.tif 000005
【００２８】
次にPpredictが障害物の内部にあるかどうかを判定するＶもし，Ppredictが障害物の内部に存在した場合には，その障害物から距離rだけ離れた位置Pcolを求める。このPcolを目標位置として，目標到達用加速度演算４０５と同様の計算によって，障害物を回避する加速度Acollisionを求める。なお，Ppredictが障害物の外部に存在する場合には，Acollisionはゼロである。
次に，加速度総和演算４０７によって，AseekとAcollisionの和を求めて，キャラクタの加速度Ａとする。
【００２９】
【数４】
2005342360.tif 000006
【００３０】
次に，速度位置更新処理４０８によって，求められた加速度Ａに従ってキャラクタの速度と位置を更新する。以上で，キャラクタの１タイムステップΔｔにおける位置と速度が更新され，結果として，集団キャラクタの移動制御が実現される。
【００３１】
以上説明したように本発明によれば，市街地のように人工の障害物が多数存在するような３次元空間上においても，集団キャラクタを，隊形を保持しながら，目的地に到達するような移動制御が可能である。キャラクタが障害物のために膠着状態に陥った場合にも，経路計画を用いることで膠着状態を回避して，隊形を保持した移動を継続できる。このため，集団キャラクタのリアルな移動表現が可能となる。
【図面の簡単な説明】
【００３２】
【図１】本発明の集団キャラクタの移動制御ルーチンを示すフローチャート。
【図２】本発明の移動制御方法を実施するコンピュータの内部構成を示すブロック回路図。
【図３】実施形態の移動制御ルーチンを示すフローチャート。
【図４】２次元の地図を示す説明図。
【図５】図４の地図から生成される自由領域を説明する説明図。
【図６】シミュレーションの３次元表示例を示す説明図。
【図７】リーダーの経路を示す説明図。
【図８】隊形の例を示す説明図。
【図９】集団キャラクタの移動の例を示す説明図。
【図１０】個々のキャラクタの移動制御方法を説明する説明図。
【図１１】衝突回避方法を示す説明図。
【図１２】集団初期設定ルーチンを示すフローチャート。
【図１３】経路計画ルーチンを示すフローチャート。
【符号の説明】
【００３３】
１０５…リーダーの経路計画，１０６…集団移動処理，４０３…目標位置演算，４０５…目標到達用加速度演算，４０６…衝突回避用加速度演算，４０９…経路計画，４１０…目標位置再設定，４１１…リーダー目標位置演算。
【図１】
2005342360.tif 000007
【図２】
2005342360.tif 000008
【図３】
2005342360.tif 000009
【図４】
2005342360.tif 000010
【図５】
2005342360.tif 000011
【図６】
2005342360.tif 000012
【図７】
2005342360.tif 000013
【図８】
2005342360.tif 000014
【図９】
2005342360.tif 000015
【図１０】
2005342360.tif 000016
【図１１】
2005342360.tif 000017
【図１２】
2005342360.tif 000018
【図１３】
2005342360.tif 000019