(57)【特許請求の範囲】
【請求項１】
グループ内のキャラクタについて移動方向及び移動速度のうち少なくとも１つを判定する方法であって、
前記キャラクタが存在している地域マップ内の現在のセルから、キャラクタの進入方向及び新たな速度を少なくとも含むトレース情報を読み取るステップと、
衝突回避の要否を判定するステップと、
衝突回避を要しない場合、前記トレース情報を利用せずに、先行する方向及び先行する速度に応じて前記キャラクタを進めるステップと、
衝突回避を要する場合、前記キャラクタの進入方向に合致するトレース情報を探索するステップと、
前記合致するトレース情報が発見された場合、当該トレース情報に基づいて衝突する時間を計算し、計算した前記衝突する時間と所定の範囲とを比較するステップと、
前記衝突する時間が前記所定の範囲内にあった場合に、発見した前記合致するトレース情報に応じて前記キャラクタを進めるステップと、
前記合致するトレース情報が発見されなかった場合又は前記衝突する時間が前記所定の範囲外であった場合、前記現在のセルのトレース情報を利用せずに衝突回避手順を実行し、前記地域マップの現在のセルにおけるトレース情報を更新するステップと
を有する方法。
【請求項２】
前記地域マップのセルが、ｄ＜Δｔ＊Ｖｐｒｅｆに従う直径又は対角線距離ｄを有し、Δｔはシミュレーションの時間ステップであり、Ｖｐｒｅｆはキャラクタの所定の好ましい速度である、請求項１に記載の方法。
【請求項３】
複数のキャラクタが使用され、前記キャラクタの所定の好ましい速度が全てのキャラクタに対して同じである、請求項１又は２に記載の方法。
【請求項４】
前記セルの前記トレース情報を読み取ることは、前記セルに入って来る少なくとも次のキャラクタの個々の行動に影響を及ぼすが、前記グループの全体的な行動には影響を及ぼさない、請求項１−３の何れか１項に記載の方法。
【請求項５】
衝突回避の要否を判定する前記ステップは、キャラクタが新たなセルに進入した場合に、該キャラクタの進入角度を含む少なくとも或る角度範囲に合致する前記トレース情報を探索する、請求項１−４の何れか１項に記載の方法。
【請求項６】
地域マップのセルのトレース情報が、該セルに入って来た少なくとも１つの過去のキャラクタについての進入方向、新たな速度及び衝突する時間を含む、請求項１−５の何れか１項に記載の方法。
【請求項７】
セルの前記トレース情報が、少なくとも４つのデータ群を含み、該データ群の各々は前記キャラクタの進入方向の範囲に関連し、該データ群の各々は新たな速度と該新たな速度に基づく衝突する時間とを少なくとも含む、請求項１−６の何れか１項に記載の方法。
【請求項８】
前記地域マップに保存されている前記トレース情報は、現在の状況に基づいて、少なくとも次のキャラクタに関し、速度及び方向の少なくとも１つを決定するためのガイドラインとして使用される中間結果を含む、請求項１−７の何れか１項に記載の方法。
【請求項９】
クラウドをシミュレーションする方法であって、
グループが向いている方向を判定するステップと、
グループが向いている方向が変わった場合に、該グループ内のキャラクタ各々について速度の調整を行うステップと、
前記グループについての前記速度及びローカルな前記調整を組み合わせてキャラクタ各々について新たな速度を生成するステップと
を有し、キャラクタ各々についてのローカルな前記調整は、請求項１に記載の方法を用いて行われる、方法。
【請求項１０】
グループ内のキャラクタについて移動方向及び移動速度のうち少なくとも１つを判定する装置であって、
地域マップのセルを保存するメモリと、
前記キャラクタが存在している地域マップ内の現在のセルから、キャラクタの進入方向及び新たな速度を少なくとも含むトレース情報を読み取る第１のデータ読み取り手段と、
前記第１のデータ読み取り手段からの前記トレース情報に基づいて衝突回避の要否を判定し、判定結果を通知する第１の衝突検出部と、
前記第１の衝突検出部が、衝突回避を要しないことを通知した場合、前記トレース情報を利用せずに、先行する方向及び先行する速度に応じて前記キャラクタを進める第１の位置計算部と、
前記第１の衝突検出部が、衝突回避を要することを通知した場合、前記キャラクタの進入方向に合致するトレース情報を探索する第１のプロセッサと、
発見した前記合致するトレース情報に基づいて衝突する時間を計算する第２のプロセッサと、
計算した前記衝突する時間と所定の範囲とを比較する比較部と、
発見した前記合致するトレース情報に応じて前記キャラクタを進め、前記合致するトレース情報が発見されなかった場合又は前記衝突する時間が前記所定の範囲外であった場合、前記セルのトレース情報を利用せずに衝突回避手順を実行し、前記現在の地域セルにおけるトレース情報を更新する第２の位置計算部と
を有する装置。
【請求項１１】
地域マップのセルのトレース情報が、該セルに入って来た少なくとも１つの過去のキャラクタについての進入方向、新たな速度及び衝突する時間を含む、請求項１０に記載の装置。
【請求項１２】
セルの前記トレース情報が、少なくとも４つのデータ群を含み、該データ群の各々は前記キャラクタの進入方向の範囲に関連し、該データ群の各々は新たな速度と該新たな速度に基づく衝突する時間とを少なくとも含む、請求項１０又は１１に記載の装置。
【請求項１３】
前記第１の衝突検出部は、新たなセルに入って来るキャラクタについて衝突回避の要否を判定する場合に、該キャラクタの進入角度を含む少なくとも或る角度範囲に合致する前記トレース情報を探索する、請求項１０−１２の何れか１項に記載の装置。
【請求項１４】
前記地域マップのセルが、ｄ＜Δｔ＊Ｖｐｒｅｆに従う直径又は対角線距離ｄを有し、Δｔはシミュレーションの時間ステップであり、Ｖｐｒｅｆはキャラクタの所定の好ましい速度である、請求項１０−１３の何れか１項に記載の装置。
【請求項１５】
プロセッサを有する、クラウドをシミュレーションする装置であって、前記プロセッサは、
グループが向いている方向を判定し、
グループが向いている方向が変わった場合に、該グループ内のキャラクタ各々について速度の調整を行い、
前記グループについての前記速度及びローカルな前記調整を組み合わせてキャラクタ各々について新たな速度を生成し、
キャラクタ各々についてのローカルな前記調整は、請求項１に記載の方法を用いて行われる、装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はキャラクタ(character)を動かす方法等に関連し、特にクラウド(crowd)と呼ばれる多くのキャラクタ群を動かす方法等に関連する。
【背景技術】
【０００２】
クラウドシミュレーション又は群衆シミュレーションは、ゲーム、映画、都市計画及び緊急避難シミュレーション等において幅広く使用されている。キャラクタのグループ又はキャラクタ群(すなわち、クラウド)は、一緒にいる人々/キャラクタの集まりであり、同じ目的を有し、同様に行動する又は振る舞う。グループの行動は我々の日常生活で非常に一般的であり、幅広く研究されている。クラウドの中で強力なグループ行動が存在する場合、先ずグループ各々についてまとめて経路(path)を予想し、次にグループに属するキャラクタ各々の動作を予想することでシミュレーションできることが知られている。クラウドシミュレーションで最も重要な観点の1つは衝突回避(collision  avoiding)であり、特に仮想キャラクタ(アバタ(avatar))同士の衝突回避である。キャラクタが自然に見えるように、キャラクタの各々は個別的に行動し、特に、所与の地域又は場所(terrain)において自身の方向に移動すべきである。地域は、地域の地図やロードマップにより表現される。グループ内のキャラクタ各々は個々の位置及び状況の評価を行い、例えば「ポテンシャルフィールド」操作(“potential  field”  manoeuvre)（グループに属するキャラクタ各々が各自の位置及び環境に応じて動くこと）を行うので、問題の1つはシミュレーションが複雑なことである。「ポテンシャルフィールド」手順の場合、キャラクタ各々の位置及び環境は、次のステップを決定するスタートライン(scratch)から評価される。
【０００３】
通常、速度調整に関する複雑な演算が実行される(この点については、例えば非特許文献1に示されている)。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】“Reciprocal  velocity  obstacles  for  real-time  multi-agent  navigation”,  J.  van  den  Berg,  M.  Lin,  D.  Manocha,  IEEE  International  Conference  on  Robotics  and  Automation,  2008
【非特許文献２】“Real-time  rendering  of  densely  populated  urban  environments”,  F.  Tecchia,  Y.  Chrysanthou,  Proceedings  of  the  Eurographics  Workshop  on  Rendering  Techniques,  2000
【発明の概要】
【発明が解決しようとする課題】
【０００５】
実施の形態の課題は、クラウドシミュレーションを簡易に実行できる装置及び方法等を提供することである。
【課題を解決するための手段】
【０００６】
実施の形態による判定方法は、
グループに属するキャラクタについて移動方向及び移動速度のうち少なくとも１つを判定する判定方法であって、
前記キャラクタが存在している地域マップ内の現在のセルからトレース情報を読み取るステップと、
衝突回避の要否を判定するステップと、
衝突回避を要しない場合、先行する方向及び先行する速度に応じて前記キャラクタを進めるステップと、
衝突回避を要する場合、合致する方向及び合致する速度のうち少なくとも１つを探索するステップと、
合致する方向及び/又は速度が発見された場合、衝突する時間を計算し、計算した前記衝突する時間と所定の範囲とを比較するステップと、
前記衝突する時間が前記所定の範囲内にあった場合に、発見した合致する方向及び/又は速度に応じて前記キャラクタを進めるステップと、
合致する方向及び/又は速度が発見できなかった場合又は前記衝突する時間が前記所定の範囲外であった場合、衝突回避手順を実行し、前記地域マップの現在のセルにおける前記トレース情報を更新するステップと
を有する判定方法である。
【図面の簡単な説明】
【０００７】
【図１】複数のキャラクタが存在する相互速度障害の状況を示す図。
【図２】シミュレーション方法のステップを示す図。
【図３】地域グリッドの一部を示す図。
【図４】グリッド位置及びトレース情報を示す図。
【図５】グループに属するキャラクタについて移動方向及び移動速度のうち少なくとも1つを判定する装置のブロック図。
【発明を実施するための形態】
【０００８】
＜発明の概要＞
本発明によれば、少なくとも計算される新たな速度に関する情報が地域マップ又はロードマップのセルに保存され、セルに入ってきた少なくとも次のキャラクタに影響を及ぼす。ロードマップは少なくとも次のキャラクタの個々の動作に影響を及ぼすが、全体的なグループの行動には影響しないことが好ましい。既存のグリッド探索(grid  searching)とは異なり、その情報は、経路予想に使用されるような固定された地域障害物には関連していない。そうではなく、地域マップに保存される情報は、中間的な結果であるに過ぎず、少なくとも次のキャラクタについて現在の状況に基づいて決定する際のガイドラインとして使用される。
【０００９】
一実施形態において、本発明は、グリッドセルを区別する(size)方法、それを衝突回避に利用する方法、トレース情報(tracing  information)を構築する方法、及び情報の有効性を判定する方法等に関連する。
【００１０】
本発明の一実施形態による判定装置は、
グループに属するキャラクタについて移動方向及び移動速度のうち少なくとも１つを判定する判定装置であって、
地域マップのセルを保存するメモリと、
前記キャラクタが存在している地域マップ内の現在のセルからトレース情報を読み取る第１のデータ読み取り手段と、
前記第１のデータ読み取り手段からの前記トレース情報に基づいて衝突回避の要否を判定し、判定結果を通知する第１の衝突検出部と、
前記第１の衝突検出部が、衝突回避を要しないことを通知した場合、先行する方向及び先行する速度に応じて前記キャラクタを進める第１の位置計算部と、
前記第１の衝突検出部が、衝突回避を要することを通知した場合、合致する方向及び合致する速度のうち少なくとも１つを探索する第１のプロセッサと、
発見した合致する方向及び/又は速度に基づいて衝突する時間を計算する第２のプロセッサと、
計算した前記衝突する時間と所定の範囲とを比較する比較部と、
前記発見した合致する方向及び/又は速度に応じて前記キャラクタを進め、合致する方向及び/又は速度が発見できなかった場合又は前記衝突する時間が前記所定の範囲外であった場合に、衝突回避手順を実行し、前記現在の地域セルにおける前記トレース情報を更新する第２の位置計算部と
を有する判定装置である。
【００１１】
例えば、所定の地域は所定のサイズのセル群に分断される。そのサイズは様々なパラメータ(例えば、典型的な速度(後述))に応じて決定されてもよい。地域セルに入ってきたキャラクタに関し、進入方向が判定され(例えば、北N、東E、南S、西Wのうちの何れか、或いは北N、北東NE、東E、南東SE等のうちの何れかが判定され)、同じ方向から入ってきた先行するキャラクタについて方向及び/又は速度の判定結果は何であったかが確認される。その判定結果に至った所定の前提条件が依然として有効であるか否かが検査される。
【００１２】
非特許文献2に記載されているような相互速度障害(Reciprocal  Velocity  Obstacle：RVO)は衝突回避を取り扱う新しい方法である。2つのキャラクタの状況がある場合、速度平面上でキャラクタ各々についてRVO領域(又はRVOエリア又はRVO範囲)があり、それは衝突を回避できるようにキャラクタが選択すべきでない速度を示す。キャラクタがRVO範囲外の任意の速度を選択する場合、他のキャラクタとの衝突を回避できることが保証される。RVO方式は、キャラクタの各々が衝突を回避するために同じ方法を採用することも想定している。言い換えれば、キャラクタは、何らかの衝突を回避する責務を共有しかつそれに応じた動作を行う。
【００１３】
＜発明の詳細な説明＞
本発明の実施の形態は添付図面を参照しながら説明される。
【００１４】
図1は複数のキャラクタが存在する状況のRVOを示す。図1の場合、あるキャラクタ10は、全ての隣接するキャラクタのRVOの組み合わせ以外の速度を選択すべきである。隣接するキャラクタ11は個別の移動方向及び速度(スピード)12を有する。しかしながら、非常に密集した群衆シミュレーションの場合、この速度は存在しないかもしれない。シミュレーションを進めるため、キャラクタの速度を選択する必要がある。このため、少なくとも「ペナルティ(penalty)」と共に速度を選択する。キャラクタiについての典型的なペナルティ関数は次のとおりである。
【００１５】
【数１】
0005905481.tif 000002
数式(1)において、Vi’は新たな速度であり、Viprefは好ましい速度であり、tci(Vi’)は推定された衝突する時間であり、wiは衝突する時間と速度分布との間のバランスをとるための重み又はウェイトである。‖・・・‖は隔たり又は距離を示す。
【００１６】
この方法は実際の問題に対して良好なパフォーマンス又は特性を示すが、演算負担が重すぎるので、多数のキャラクタを伴う群衆又はクラウドをシミュレーションすることは困難である。時間ステップ毎に、キャラクタ各々について、シミュレータは、何百もの許容可能な速度をサンプリングし、その速度の各々についてペナルティを計算し、ペナルティが最小である速度を見出さなければならないからである(以後、この方法は「RVO速度選択」と言及される)。従って、大規模な群衆シミュレーション又はクラウドシミュレーションにおいて、特にリアルタイムアプリケーションの場合に、「速度選択」の複雑さを軽減することが非常に重要である。
【００１７】
以下において、新規な速度選択方法が提案されている。「RVO速度選択」方式と比較して、以下に説明される方法はクラウドシミュレーションの全体的な複雑さを大幅に減らす。
【００１８】
提案する方法は、先行するキャラクタのトレース情報を利用してターゲットキャラクタの新たな速度を選択することで、クラウドシミュレーションの複雑さを減らす。先ず、キャラクタが歩行又は移動する面(例えば、2D平面)が、規則的なグリッドに離散化される。グリッドの分解能又は解像度は、好ましい速度及びシミュレーションの時間ステップにより決定される。進入角度、新たな速度及び衝突する時間等を含むトレース情報が、グリッドのセル各々に保存される。新たなセルに入ると、後のキャラクタは、そのキャラクタの進入角度に合致するトレース情報(すなわち、実質的に同じ進入角度を示すもの)を探し、新たな速度に基づいて衝突する時間を計算する。現在のキャラクタについての衝突する時間がセルに保存されているものに匹敵する場合(少なくとも双方が等しい場合)、キャラクタは、RVO方式の衝突回避演算の新たなやり直しを行うことなく新たな速度を選択し、そうでなかった場合、従来のRVO衝突回避方式が行われ、セルのトレース情報がそれに応じて改められる。
【００１９】
図2は提案するシミュレーションの骨子のステップを示す。以下、各ステップを詳細に説明する。
【００２０】
準備段階20において、離散化及び初期化が実行される(P0)。シミュレーションの前に、地域が規則的なセルのグリッドに離散化又は分割される(これは3D的な地域表面に容易に適用可能であるが、説明の簡明化のためここでは2D平面が使用される)。図3は直径又は対角線距離がdである地域グリッドの一部を示し、dは分解能又は解像度と言及されてもよい。グリッドの分解能は、時間ステップ各々について、キャラクタが新たなセルに向かって好ましい速度で歩行又は進行するという原理によって決定される。すなわち、次式が成り立つ。
【００２１】
d＜Δt＊Vpref      (2)
ここで、dはグリッドセルの対角線距離であり(図3)、Δtは時間ステップの長さであり、Vprefは好ましい速度である。一実施形態では、簡明化のため、全てのキャラクタは同じであることが想定されている。
【００２２】
図4はグリッドの一部及びトレース情報を示す。グリッドセルに保存されるトレース情報は、少なくとも4つのデータ群を含み、データの各々はキャラクタの進入方向Veの範囲に関連する。データ群の各々には、新たな速度Vnew及びこの新たな速度に基づく衝突する時間(time-to-collide：TTC)が含められかつ提示される。
【００２３】
図2に示す第2段階では、シミュレーションプロセスが実行される。衝突回避が必要である場合、第1のモジュールP1は探索ステップ22において合致するものの探索を実行する。すなわち、ステップ21において衝突回避手順が必要であると判定された場合は常に、そのキャラクタが占めるセルを探し(22)、そのキャラクタの進入方向に合致するトレース情報が存在するか否かを判断する(23)。そのようなトレース情報が存在しなかった場合、既存の通常使用されている演算負担が重い従来の衝突回避手順が実行される(27)。
【００２４】
次のステップ24において、第2のモジュールP2は衝突する時間(TTC)を計算する。キャラクタがトレース情報から新たな速度を取得したとしても、依然としてキャラクタが他のキャラクタに衝突する可能性がある。TTCは衝突が始めて起こるまでにかかる時間である。如何なる衝突も生じないことが判定された場合、TTCは充分に大きい。この計算されたTTCは以下の条件を満たす必要がある。
【００２５】
TTCcomputed＞max  (TTCtracing−k*Δt，Δt)      (3)
ここで、TTCtracingはセルに保存されているトレーシング情報である。そうではなかった場合、合致するものはなく、従来の衝突回避手順が実行される(27)。定数kはシミュレーション時間ステップの数を示し、不整合の耐性を示すように適切に選択されるべきである。kが小さいほど、より厳密な一致となる。一致(又は照合)の厳密性と一致(又は照合)の成功確率との間にはトレードオフが存在する。kが大きすぎた場合、トレーシング情報の照合は、現在のキャラクタに対して適切なガイダンス又は案内とはならず、衝突回避を非効率的にしてしまう不適切な新たな速度を導いてしまう。実際のkの値は、所与のシミュレーション時間ステップΔtの長さ、すなわちシミュレーションの時間分解能に強く依存する。
【００２６】
第3のモジュールP3は従来の衝突回避手順を実行する(27)。トレース情報がセルに存在しなかった場合、或いは利用可能なトレース情報が充分に合致しなかった場合、その現在のキャラクタについての新たな速度を選択するために、従来の衝突回避手順が実行される。その方法の1つは、非特許文献1のような従来のRVO衝突回避方法を使用して、速度選択問題を取り扱うことである。
【００２７】
第4のモジュールP4は地域セルにおけるトレース情報を更新する(28)。従来の衝突回避手順が実行される場合は常に、セルに保存された対応するトレース情報が更新されなければならない。
【００２８】
第5のモジュールP5はキャラクタを進める(26)。新たな速度に基づいて、例えばニュートン力学(Newtonian  mechanics)を利用することでキャラクタの新たな位置が計算される(すなわち、新たな位置は、s=v*tにより計算され、sは距離であり、vは速度であり、tは時間である)。新たな位置は、地域マップ又は別個のメモリの何れかに保存される。
【００２９】
一実施形態において、本発明は、グループ内のキャラクタについて移動方向及び移動速度のうち少なくとも1つを判定する装置に関連している。図5はそのような装置のブロック図を示す。グループ内のキャラクタについて移動方向及び移動速度のうち少なくとも1つを判定する装置は、
地域マップのセルを保存するメモリ51と、
キャラクタが存在している地域マップ内の現在のセルからトレース情報を読み取る第1のデータ読み取り手段52(例えば、メモリアクセス部)と、
第1のデータ読み取り手段からのトレース情報に基づいて衝突回避の要否を判定し、判定結果ca、ncaを通知する第１の衝突検出部53と、
第1の衝突検出部が、衝突回避は不要であること(nca)を通知した場合、先行する方向及び先行する速度に応じてキャラクタを進める第1の位置計算部54と、
第1の衝突検出部が、衝突回避を要することを通知した場合、合致する方向dir及び合致する速度velのうち少なくとも1つを探索する第1のプロセッサ55と、
発見した合致する方向及び/又は速度に基づいて衝突する時間TTCを計算する第2のプロセッサ56と、
計算した衝突する時間TTCと所定の範囲とを比較する比較部57と、
発見した合致する方向及び/又は速度に応じてキャラクタを進め、合致する方向及び/又は速度が発見できなかった場合又は衝突する時間が所定の範囲外であった場合に、衝突回避手順を実行し、現在の地域セルにおけるトレース情報を更新する第2の位置計算部58と
を有する。
【００３０】
本発明は様々な応用分野で使用可能である。概して、本方法は、従来の衝突回避手順よりも時間を短縮することで、クラウドシミュレーションの複雑さを軽減する。地域セルに保存されているトレース情報は、地域セルにかつて存在した別のキャラクタと同様な進入方向を有する現在のキャラクタに対するガイダンス(又は案内又は助言)として使用され、複雑な計算を行うことなく、保存されている速度を直ちに使用できるようにする。
【００３１】
本方法は、他のキャラクタの後に進入するグループ内のキャラクタが、先行する他のキャラクタと同様な状況に遭遇するという仮定に基づいている。特に、これは、キャラクタの2つのグループが互いに交わるような場合に正しい。すなわち、本発明による方法は、あるグループが別のグループを横切る場合や、あるグループが別のグループに遭遇する等の場合のように互いに干渉し合うグループ内の個々のキャラクタの移動方向及び移動速度を決定するために使用できる。上記の仮定が妥当である限り、本方法は、映画の戦闘シーン、交通シミュレーション、避難シミュレーション等のような任意のクラウドシミュレーションに使用できる。
【００３２】
提案する方法は(何千ものキャラクタ又はそれ以上の)非常に大規模な群衆又はクラウドをシミュレーションする効率的な方法である。シミュレーションする群衆又はクラウドの行動を制御する入力パラメータが幾つか存在する。1つはd(すなわち、グリッドの解像度のインジケータ)であり、動きの滑らかさを決定する。別の例はTTCの数式におけるkであり、不一致に対する耐性を決定する。例えば、本発明を使用するシミュレーションソフトウェアにおいて、これらのパラメータは適宜設定可能である。本発明は地域グリッドセルの中で自明な「後続(following)」パターンを導出する。なぜなら、後続のキャラクタは先行するキャラクタからのトレーシング情報を使用するからである。すなわち、次々に続くキャラクタは一般的には同じ仕方で移動するが、(例えば、移動する障害物のような)現在の状況を考慮に入れると、現実味のある群衆の行動に類似してくる。
【００３３】
本発明は、例えば、先ず各グループの経路及び速度を予想し、次にグループ内のキャラクタ各々について速度を調整することで、群衆をシミュレーションすることに利用可能である。その方法は、
1．グループについてのグローバル予想及びローカル衝突回避。各グループは1つの要素(entity)として取り扱われる(すなわち、グループが向かう方向がグループ各々について決定される)。
【００３４】
2．グループが向かう方向が変化した場合は常に、グループ内のキャラクタ各々の速度を調整する。
【００３５】
3．グループの速度とローカルな調整とを組み合わせてキャラクタ各々についての新たな速度を生成する。後続の他のキャラクタについては、完全な計算を再び実行する必要はない。そうではなく、計算された新たな位置についての情報が地域マップのセルに保存される。本方法は、群衆シミュレーションの複雑さを軽減し、映画やゲーム製作に使用することができ、特に(例えば、軍隊のような)整然としたグループのキャラクタの行動をシミュレーションする場合に有用である。
【００３６】
以上、本発明の基本的な新規な特徴を、本発明の好適実施形態に適用するように説明、記述及び指摘してきたが、説明された装置の形態及び詳細において及びそれらの動作において、説明された装置及び方法に対する様々な省略、置換及び変形が、本発明の精神から逸脱することなく当業者によってなされてもよいことが、理解されるであろう。同一の結果をもたらす実質的に同様な方式で実質的に同様な機能を実行するこれらの要素の全ての組み合わせが本発明の範囲に包含されていることが、本質的に意図されている。説明された或る実施形態から別の実施形態への要素の置換も当然に意図されており想定されている。
【００３７】
本発明は単なる例示によって説明されてきたこと、及び具体的な詳細事項の修正は本発明の範囲から逸脱することなくなされてよいことが、理解されるであろう。
【００３８】
明細書、(場合によっては)特許請求の範囲及び図面により開示された特徴の各々は、独立して使用されてもよいし、或いは任意の適切な組み合わせにより使用されてもよい。
【００３９】
特許請求の範囲に参照番号がある場合、それは単なる例示に過ぎず、特許請求の範囲を限定する如何なる影響も有しない。
上記の実施形態に関連する手段を以下に例示的に列挙する。
（付記１）
グループに属するキャラクタについて移動方向及び移動速度のうち少なくとも１つを判定する判定方法であって、
前記キャラクタが存在している地域マップ内の現在のセルからトレース情報を読み取るステップと、
衝突回避の要否を判定するステップと、
衝突回避を要しない場合、先行する方向及び先行する速度に応じて前記キャラクタを進めるステップと、
衝突回避を要する場合、合致する方向及び合致する速度のうち少なくとも１つを探索するステップと、
合致する方向及び/又は速度が発見された場合、衝突する時間を計算し、計算した前記衝突する時間と所定の範囲とを比較するステップと、
前記衝突する時間が前記所定の範囲内にあった場合に、発見した合致する方向及び/又は速度に応じて前記キャラクタを進めるステップと、
合致する方向及び/又は速度が発見できなかった場合又は前記衝突する時間が前記所定の範囲外であった場合、衝突回避手順を実行し、前記地域マップの現在のセルにおける前記トレース情報を更新するステップと
を有する判定方法。
（付記２）
前記地域マップのセルが、d＜Δt*Vprefに従う距離dを有し、Δtはシミュレーションの時間ステップであり、Vprefはキャラクタの所定の好ましい速度である、付記１に記載の判定方法。
（付記３）
複数のキャラクタが使用され、前記キャラクタの所定の好ましい速度が全てのキャラクタに対して同じである、付記１又は２に記載の判定方法。
（付記４）
前記キャラクタが存在している地域マップ内の現在のセルからトレース情報を読み取る前記ステップは、前記セルに入って来る少なくとも次のキャラクタの個々の行動に影響を及ぼすが、前記グループの全体的な行動には影響を及ぼさない、付記１−３の何れか１項に記載の判定方法。
（付記５）
衝突回避の要否を判定する前記ステップにおいて、キャラクタは、新たなセルに進入した場合、該キャラクタの進入角度を含む少なくとも角度範囲を示す前記トレース情報を探索する、付記１−４の何れか１項に記載の判定方法。
（付記６）
地域マップのセルのトレース情報が、過去に該セルに入って来た少なくとも１つのキャラクタについての進入角度、新たな速度及び衝突する時間を示す、付記１−５の何れか１項に記載の判定方法。
（付記７）
セルの前記トレース情報が、少なくとも４つのデータ群を示し、該データ群の各々は前記キャラクタの進入方向の範囲に関連し、該データ群の各々は前記新たな速度と該新たな速度に基づく衝突する時間とを少なくとも示す、付記１−６の何れか１項に記載の判定方法。
（付記８）
前記地域マップに保存されている前記トレース情報は、現在の状況に基づいて、スピード、速度及び方向の少なくとも１つを決定するためのガイドラインとして、少なくとも次のキャラクタに対して使用される中間結果を示す、付記１−７の何れか１項に記載の判定方法。
（付記９）
クラウドのシミュレーション方法であって、
グループが向いている方向を判定するステップと、
グループが向いている方向が変わった場合に、該グループに属するキャラクタ各々について速度の調整を行うステップと、
前記グループについての前記速度及びローカルな前記調整を組み合わせてキャラクタ各々について新たな速度を決定するステップと
を有し、キャラクタ各々についてのローカルな前記調整は、付記１に記載の判定方法による方法を用いて行われる、シミュレーション方法。
（付記１０）
グループに属するキャラクタについて移動方向及び移動速度のうち少なくとも１つを判定する判定装置であって、
地域マップのセルを保存するメモリと、
前記キャラクタが存在している地域マップ内の現在のセルからトレース情報を読み取る第１のデータ読み取り手段と、
前記第１のデータ読み取り手段からの前記トレース情報に基づいて衝突回避の要否を判定し、判定結果を通知する第１の衝突検出部と、
前記第１の衝突検出部が、衝突回避を要しないことを通知した場合、先行する方向及び先行する速度に応じて前記キャラクタを進める第１の位置計算部と、
前記第１の衝突検出部が、衝突回避を要することを通知した場合、合致する方向及び合致する速度のうち少なくとも１つを探索する第１のプロセッサと、
発見した合致する方向及び/又は速度に基づいて衝突する時間を計算する第２のプロセッサと、
計算した前記衝突する時間と所定の範囲とを比較する比較部と、
前記発見した合致する方向及び/又は速度に応じて前記キャラクタを進め、合致する方向及び/又は速度が発見できなかった場合又は前記衝突する時間が前記所定の範囲外であった場合に、衝突回避手順を実行し、前記現在の地域セルにおける前記トレース情報を更新する第２の位置計算部と
を有する判定装置。
（付記１１）
地域マップのセルのトレース情報が、過去に該セルに入って来た少なくとも１つのキャラクタについての進入角度、新たな速度及び衝突する時間を示す、付記１０に記載の判定装置。
（付記１２）
セルの前記トレース情報が、少なくとも４つのデータ群を示し、該データ群の各々は前記キャラクタの進入方向の範囲に関連し、該データ群の各々は前記新たな速度と該新たな速度に基づく衝突する時間とを少なくとも示す、付記１０又は１１に記載の判定装置。
（付記１３）
前記第１の衝突検出部は、新たなセルに入って来るキャラクタについて衝突回避の要否を判定する場合に、該キャラクタの進入角度を含む少なくとも角度範囲を示す前記トレース情報を探索する、付記１０−１２の何れか１項に記載の判定装置。
（付記１４）
前記地域マップのセルが、d＜Δt*Vprefに従う距離dを有し、Δtはシミュレーションの時間ステップであり、Vprefはキャラクタの所定の好ましい速度である、付記１０−１３の何れか１項に記載の判定装置。
（付記１５）
プロセッサを有するクラウドのシミュレーション装置であって、前記プロセッサは、
グループが向いている方向を判定し、
グループが向いている方向が変わった場合に、該グループに属するキャラクタ各々について速度の調整を行い、
前記グループについての前記速度及びローカルな前記調整を組み合わせてキャラクタ各々について新たな速度を決定し、
キャラクタ各々についてのローカルな前記調整は、付記１０−１４の何れか１項に記載の判定装置を用いて行われる、シミュレーション装置。
【図１】
0005905481.tif 000003
【図２】
0005905481.tif 000004
【図３】
0005905481.tif 000005
【図４】
0005905481.tif 000006
【図５】
0005905481.tif 000007