グループに属するキャラクタについて移動方向及び移動速度のうち少なくとも1つを判定する判定方法であって、前記キャラクタが存在している地域マップ内の現在のセルからトレース情報を読み取るステップと、衝突回避の要否を判定するステップと、衝突回避を要しない場合、先行する方向及び先行する速度に応じて前記キャラクタを進めるステップと、衝突回避を要する場合、合致する方向及び合致する速度のうち少なくとも1つを探索するステップと、合致する方向及び又は速度が発見された場合、衝突する時間を計算し、計算した前記衝突する時間と所定の範囲とを比較するステップと、前記衝突する時間が前記所定の範囲内にあった場合に、発見した合致する方向及び又は速度に応じて前記キャラクタを進めるステップと、合致する方向及び又は速度が発見できなかった場合又は前記衝突する時間が前記所定の範囲外であった場合、衝突回避手順を実行し、前記地域マップの現在のセルにおける前記トレース情報を更新するステップとを有する判定方法。前記地域マップのセルが、d<ΔtVprefに従う距離dを有し、Δtはシミュレーションの時間ステップであり、Vprefはキャラクタの所定の好ましい速度である、請求項1に記載の判定方法。複数のキャラクタが使用され、前記キャラクタの所定の好ましい速度が全てのキャラクタに対して同じである、請求項1又は2に記載の判定方法。前記キャラクタが存在している地域マップ内の現在のセルからトレース情報を読み取る前記ステップは、前記セルに入って来る少なくとも次のキャラクタの個々の行動に影響を及ぼすが、前記グループの全体的な行動には影響を及ぼさない、請求項1-3の何れか1項に記載の判定方法。衝突回避の要否を判定する前記ステップにおいて、キャラクタは、新たなセルに進入した場合、該キャラクタの進入角度を含む少なくとも角度範囲を示す前記トレース情報を探索する、請求項1-4の何れか1項に記載の判定方法。地域マップのセルのトレース情報が、過去に該セルに入って来た少なくとも1つのキャラクタについての進入角度、新たな速度及び衝突する時間を示す、請求項1-5の何れか1項に記載の判定方法。セルの前記トレース情報が、少なくとも4つのデータ群を示し、該データ群の各々は前記キャラクタの進入方向の範囲に関連し、該データ群の各々は前記新たな速度と該新たな速度に基づく衝突する時間とを少なくとも示す、請求項1-6の何れか1項に記載の判定方法。前記地域マップに保存されている前記トレース情報は、現在の状況に基づいて、スピード、速度及び方向の少なくとも1つを決定するためのガイドラインとして、少なくとも次のキャラクタに対して使用される中間結果を示す、請求項1-7の何れか1項に記載の判定方法。クラウドのシミュレーション方法であって、グループが向いている方向を判定するステップと、グループが向いている方向が変わった場合に、該グループに属するキャラクタ各々について速度の調整を行うステップと、前記グループについての前記速度及びローカルな前記調整を組み合わせてキャラクタ各々について新たな速度を決定するステップとを有し、キャラクタ各々についてのローカルな前記調整は、請求項1に記載の判定方法による方法を用いて行われる、シミュレーション方法。グループに属するキャラクタについて移動方向及び移動速度のうち少なくとも1つを判定する判定装置であって、地域マップのセルを保存するメモリと、前記キャラクタが存在している地域マップ内の現在のセルからトレース情報を読み取る第1のデータ読み取り手段と、前記第1のデータ読み取り手段からの前記トレース情報に基づいて衝突回避の要否を判定し、判定結果を通知する第1の衝突検出部と、前記第1の衝突検出部が、衝突回避を要しないことを通知した場合、先行する方向及び先行する速度に応じて前記キャラクタを進める第1の位置計算部と、前記第1の衝突検出部が、衝突回避を要することを通知した場合、合致する方向及び合致する速度のうち少なくとも1つを探索する第1のプロセッサと、発見した合致する方向及び又は速度に基づいて衝突する時間を計算する第2のプロセッサと、計算した前記衝突する時間と所定の範囲とを比較する比較部と、前記発見した合致する方向及び又は速度に応じて前記キャラクタを進め、合致する方向及び又は速度が発見できなかった場合又は前記衝突する時間が前記所定の範囲外であった場合に、衝突回避手順を実行し、前記現在の地域セルにおける前記トレース情報を更新する第2の位置計算部とを有する判定装置。地域マップのセルのトレース情報が、過去に該セルに入って来た少なくとも1つのキャラクタについての進入角度、新たな速度及び衝突する時間を示す、請求項10に記載の判定装置。セルの前記トレース情報が、少なくとも4つのデータ群を示し、該データ群の各々は前記キャラクタの進入方向の範囲に関連し、該データ群の各々は前記新たな速度と該新たな速度に基づく衝突する時間とを少なくとも示す、請求項10又は11に記載の判定装置。前記第1の衝突検出部は、新たなセルに入って来るキャラクタについて衝突回避の要否を判定する場合に、該キャラクタの進入角度を含む少なくとも角度範囲を示す前記トレース情報を探索する、請求項10-12の何れか1項に記載の判定装置。前記地域マップのセルが、d<ΔtVprefに従う距離dを有し、Δtはシミュレーションの時間ステップであり、Vprefはキャラクタの所定の好ましい速度である、請求項10-13の何れか1項に記載の判定装置。プロセッサを有するクラウドのシミュレーション装置であって、前記プロセッサは、グループが向いている方向を判定し、グループが向いている方向が変わった場合に、該グループに属するキャラクタ各々について速度の調整を行い、前記グループについての前記速度及びローカルな前記調整を組み合わせてキャラクタ各々について新たな速度を決定し、キャラクタ各々についてのローカルな前記調整は、請求項10-14の何れか1項に記載の判定装置を用いて行われる、シミュレーション装置。実施の形態の課題は、クラウドシミュレーションを簡易に実行できる装置及び方法等を提供することである。実施の形態による判定方法は、グループに属するキャラクタについて移動方向及び移動速度のうち少なくとも1つを判定する判定方法であって、前記キャラクタが存在している地域マップ内の現在のセルからトレース情報を読み取るステップと、衝突回避の要否を判定するステップと、衝突回避を要しない場合、先行する方向及び先行する速度に応じて前記キャラクタを進めるステップと、衝突回避を要する場合、合致する方向及び合致する速度のうち少なくとも1つを探索するステップと、合致する方向及び又は速度が発見された場合、衝突する時間を計算し、計算した前記衝突する時間と所定の範囲とを比較するステップと、前記衝突する時間が前記所定の範囲内にあった場合に、発見した合致する方向及び又は速度に応じて前記キャラクタを進めるステップと、合致する方向及び又は速度が発見できなかった場合又は前記衝突する時間が前記所定の範囲外であった場合、衝突回避手順を実行し、前記地域マップの現在のセルにおける前記トレース情報を更新するステップとを有する判定方法である。<発明の概要>本発明によれば、少なくとも計算される新たな速度に関する情報が地域マップ又はロードマップのセルに保存され、セルに入ってきた少なくとも次のキャラクタに影響を及ぼす。ロードマップは少なくとも次のキャラクタの個々の動作に影響を及ぼすが、全体的なグループの行動には影響しないことが好ましい。既存のグリッド探索とは異なり、その情報は、経路予想に使用されるような固定された地域障害物には関連していない。そうではなく、地域マップに保存される情報は、中間的な結果であるに過ぎず、少なくとも次のキャラクタについて現在の状況に基づいて決定する際のガイドラインとして使用される。一実施形態において、本発明は、グリッドセルを区別する方法、それを衝突回避に利用する方法、トレース情報を構築する方法、及び情報の有効性を判定する方法等に関連する。本発明の一実施形態による判定装置は、グループに属するキャラクタについて移動方向及び移動速度のうち少なくとも1つを判定する判定装置であって、地域マップのセルを保存するメモリと、前記キャラクタが存在している地域マップ内の現在のセルからトレース情報を読み取る第1のデータ読み取り手段と、前記第1のデータ読み取り手段からの前記トレース情報に基づいて衝突回避の要否を判定し、判定結果を通知する第1の衝突検出部と、前記第1の衝突検出部が、衝突回避を要しないことを通知した場合、先行する方向及び先行する速度に応じて前記キャラクタを進める第1の位置計算部と、前記第1の衝突検出部が、衝突回避を要することを通知した場合、合致する方向及び合致する速度のうち少なくとも1つを探索する第1のプロセッサと、発見した合致する方向及び又は速度に基づいて衝突する時間を計算する第2のプロセッサと、計算した前記衝突する時間と所定の範囲とを比較する比較部と、前記発見した合致する方向及び又は速度に応じて前記キャラクタを進め、合致する方向及び又は速度が発見できなかった場合又は前記衝突する時間が前記所定の範囲外であった場合に、衝突回避手順を実行し、前記現在の地域セルにおける前記トレース情報を更新する第2の位置計算部とを有する判定装置である。例えば、所定の地域は所定のサイズのセル群に分断される。そのサイズは様々なパラメータに応じて決定されてもよい。地域セルに入ってきたキャラクタに関し、進入方向が判定され、同じ方向から入ってきた先行するキャラクタについて方向及び又は速度の判定結果は何であったかが確認される。その判定結果に至った所定の前提条件が依然として有効であるか否かが検査される。非特許文献2に記載されているような相互速度障害は衝突回避を取り扱う新しい方法である。2つのキャラクタの状況がある場合、速度平面上でキャラクタ各々についてRVO領域があり、それは衝突を回避できるようにキャラクタが選択すべきでない速度を示す。キャラクタがRVO範囲外の任意の速度を選択する場合、他のキャラクタとの衝突を回避できることが保証される。RVO方式は、キャラクタの各々が衝突を回避するために同じ方法を採用することも想定している。言い換えれば、キャラクタは、何らかの衝突を回避する責務を共有しかつそれに応じた動作を行う。<発明の詳細な説明>本発明の実施の形態は添付図面を参照しながら説明される。図1は複数のキャラクタが存在する状況のRVOを示す。図1の場合、あるキャラクタ10は、全ての隣接するキャラクタのRVOの組み合わせ以外の速度を選択すべきである。隣接するキャラクタ11は個別の移動方向及び速度12を有する。しかしながら、非常に密集した群衆シミュレーションの場合、この速度は存在しないかもしれない。シミュレーションを進めるため、キャラクタの速度を選択する必要がある。このため、少なくともペナルティと共に速度を選択する。キャラクタiについての典型的なペナルティ関数は次のとおりである。数式において、Vi’は新たな速度であり、Viprefは好ましい速度であり、tciは推定された衝突する時間であり、wiは衝突する時間と速度分布との間のバランスをとるための重み又はウェイトである。∥∥は隔たり又は距離を示す。この方法は実際の問題に対して良好なパフォーマンス又は特性を示すが、演算負担が重すぎるので、多数のキャラクタを伴う群衆又はクラウドをシミュレーションすることは困難である。時間ステップ毎に、キャラクタ各々について、シミュレータは、何百もの許容可能な速度をサンプリングし、その速度の各々についてペナルティを計算し、ペナルティが最小である速度を見出さなければならないからである。従って、大規模な群衆シミュレーション又はクラウドシミュレーションにおいて、特にリアルタイムアプリケーションの場合に、速度選択の複雑さを軽減することが非常に重要である。以下において、新規な速度選択方法が提案されている。RVO速度選択方式と比較して、以下に説明される方法はクラウドシミュレーションの全体的な複雑さを大幅に減らす。提案する方法は、先行するキャラクタのトレース情報を利用してターゲットキャラクタの新たな速度を選択することで、クラウドシミュレーションの複雑さを減らす。先ず、キャラクタが歩行又は移動する面が、規則的なグリッドに離散化される。グリッドの分解能又は解像度は、好ましい速度及びシミュレーションの時間ステップにより決定される。進入角度、新たな速度及び衝突する時間等を含むトレース情報が、グリッドのセル各々に保存される。新たなセルに入ると、後のキャラクタは、そのキャラクタの進入角度に合致するトレース情報を探し、新たな速度に基づいて衝突する時間を計算する。現在のキャラクタについての衝突する時間がセルに保存されているものに匹敵する場合、キャラクタは、RVO方式の衝突回避演算の新たなやり直しを行うことなく新たな速度を選択し、そうでなかった場合、従来のRVO衝突回避方式が行われ、セルのトレース情報がそれに応じて改められる。図2は提案するシミュレーションの骨子のステップを示す。以下、各ステップを詳細に説明する。準備段階20において、離散化及び初期化が実行される。シミュレーションの前に、地域が規則的なセルのグリッドに離散化又は分割される。図3は直径又は対角線距離がdである地域グリッドの一部を示し、dは分解能又は解像度と言及されてもよい。グリッドの分解能は、時間ステップ各々について、キャラクタが新たなセルに向かって好ましい速度で歩行又は進行するという原理によって決定される。すなわち、次式が成り立つ。d<ΔtVprefここで、dはグリッドセルの対角線距離であり、Δtは時間ステップの長さであり、Vprefは好ましい速度である。一実施形態では、簡明化のため、全てのキャラクタは同じであることが想定されている。図4はグリッドの一部及びトレース情報を示す。グリッドセルに保存されるトレース情報は、少なくとも4つのデータ群を含み、データの各々はキャラクタの進入方向Veの範囲に関連する。データ群の各々には、新たな速度Vnew及びこの新たな速度に基づく衝突する時間が含められかつ提示される。図2に示す第2段階では、シミュレーションプロセスが実行される。衝突回避が必要である場合、第1のモジュールP1は探索ステップ22において合致するものの探索を実行する。すなわち、ステップ21において衝突回避手順が必要であると判定された場合は常に、そのキャラクタが占めるセルを探し、そのキャラクタの進入方向に合致するトレース情報が存在するか否かを判断する。そのようなトレース情報が存在しなかった場合、既存の通常使用されている演算負担が重い従来の衝突回避手順が実行される。次のステップ24において、第2のモジュールP2は衝突する時間を計算する。キャラクタがトレース情報から新たな速度を取得したとしても、依然としてキャラクタが他のキャラクタに衝突する可能性がある。TTCは衝突が始めて起こるまでにかかる時間である。如何なる衝突も生じないことが判定された場合、TTCは充分に大きい。この計算されたTTCは以下の条件を満たす必要がある。TTCcomputed>maxここで、TTCtracingはセルに保存されているトレーシング情報である。そうではなかった場合、合致するものはなく、従来の衝突回避手順が実行される。定数kはシミュレーション時間ステップの数を示し、不整合の耐性を示すように適切に選択されるべきである。kが小さいほど、より厳密な一致となる。一致の厳密性と一致の成功確率との間にはトレードオフが存在する。kが大きすぎた場合、トレーシング情報の照合は、現在のキャラクタに対して適切なガイダンス又は案内とはならず、衝突回避を非効率的にしてしまう不適切な新たな速度を導いてしまう。実際のkの値は、所与のシミュレーション時間ステップΔtの長さ、すなわちシミュレーションの時間分解能に強く依存する。第3のモジュールP3は従来の衝突回避手順を実行する。トレース情報がセルに存在しなかった場合、或いは利用可能なトレース情報が充分に合致しなかった場合、その現在のキャラクタについての新たな速度を選択するために、従来の衝突回避手順が実行される。その方法の1つは、非特許文献1のような従来のRVO衝突回避方法を使用して、速度選択問題を取り扱うことである。第4のモジュールP4は地域セルにおけるトレース情報を更新する。従来の衝突回避手順が実行される場合は常に、セルに保存された対応するトレース情報が更新されなければならない。第5のモジュールP5はキャラクタを進める。新たな速度に基づいて、例えばニュートン力学を利用することでキャラクタの新たな位置が計算される。新たな位置は、地域マップ又は別個のメモリの何れかに保存される。一実施形態において、本発明は、グループ内のキャラクタについて移動方向及び移動速度のうち少なくとも1つを判定する装置に関連している。図5はそのような装置のブロック図を示す。グループ内のキャラクタについて移動方向及び移動速度のうち少なくとも1つを判定する装置は、地域マップのセルを保存するメモリ51と、キャラクタが存在している地域マップ内の現在のセルからトレース情報を読み取る第1のデータ読み取り手段52と、第1のデータ読み取り手段からのトレース情報に基づいて衝突回避の要否を判定し、判定結果ca、ncaを通知する第1の衝突検出部53と、第1の衝突検出部が、衝突回避は不要であることを通知した場合、先行する方向及び先行する速度に応じてキャラクタを進める第1の位置計算部54と、第1の衝突検出部が、衝突回避を要することを通知した場合、合致する方向dir及び合致する速度velのうち少なくとも1つを探索する第1のプロセッサ55と、発見した合致する方向及び又は速度に基づいて衝突する時間TTCを計算する第2のプロセッサ56と、計算した衝突する時間TTCと所定の範囲とを比較する比較部57と、発見した合致する方向及び又は速度に応じてキャラクタを進め、合致する方向及び又は速度が発見できなかった場合又は衝突する時間が所定の範囲外であった場合に、衝突回避手順を実行し、現在の地域セルにおけるトレース情報を更新する第2の位置計算部58とを有する。本発明は様々な応用分野で使用可能である。概して、本方法は、従来の衝突回避手順よりも時間を短縮することで、クラウドシミュレーションの複雑さを軽減する。地域セルに保存されているトレース情報は、地域セルにかつて存在した別のキャラクタと同様な進入方向を有する現在のキャラクタに対するガイダンスとして使用され、複雑な計算を行うことなく、保存されている速度を直ちに使用できるようにする。本方法は、他のキャラクタの後に進入するグループ内のキャラクタが、先行する他のキャラクタと同様な状況に遭遇するという仮定に基づいている。特に、これは、キャラクタの2つのグループが互いに交わるような場合に正しい。すなわち、本発明による方法は、あるグループが別のグループを横切る場合や、あるグループが別のグループに遭遇する等の場合のように互いに干渉し合うグループ内の個々のキャラクタの移動方向及び移動速度を決定するために使用できる。上記の仮定が妥当である限り、本方法は、映画の戦闘シーン、交通シミュレーション、避難シミュレーション等のような任意のクラウドシミュレーションに使用できる。提案する方法は非常に大規模な群衆又はクラウドをシミュレーションする効率的な方法である。シミュレーションする群衆又はクラウドの行動を制御する入力パラメータが幾つか存在する。1つはdであり、動きの滑らかさを決定する。別の例はTTCの数式におけるkであり、不一致に対する耐性を決定する。例えば、本発明を使用するシミュレーションソフトウェアにおいて、これらのパラメータは適宜設定可能である。本発明は地域グリッドセルの中で自明な後続パターンを導出する。なぜなら、後続のキャラクタは先行するキャラクタからのトレーシング情報を使用するからである。すなわち、次々に続くキャラクタは一般的には同じ仕方で移動するが、現在の状況を考慮に入れると、現実味のある群衆の行動に類似してくる。本発明は、例えば、先ず各グループの経路及び速度を予想し、次にグループ内のキャラクタ各々について速度を調整することで、群衆をシミュレーションすることに利用可能である。その方法は、1.グループについてのグローバル予想及びローカル衝突回避。各グループは1つの要素として取り扱われる。2.グループが向かう方向が変化した場合は常に、グループ内のキャラクタ各々の速度を調整する。3.グループの速度とローカルな調整とを組み合わせてキャラクタ各々についての新たな速度を生成する。後続の他のキャラクタについては、完全な計算を再び実行する必要はない。そうではなく、計算された新たな位置についての情報が地域マップのセルに保存される。本方法は、群衆シミュレーションの複雑さを軽減し、映画やゲーム製作に使用することができ、特に整然としたグループのキャラクタの行動をシミュレーションする場合に有用である。以上、本発明の基本的な新規な特徴を、本発明の好適実施形態に適用するように説明、記述及び指摘してきたが、説明された装置の形態及び詳細において及びそれらの動作において、説明された装置及び方法に対する様々な省略、置換及び変形が、本発明の精神から逸脱することなく当業者によってなされてもよいことが、理解されるであろう。同一の結果をもたらす実質的に同様な方式で実質的に同様な機能を実行するこれらの要素の全ての組み合わせが本発明の範囲に包含されていることが、本質的に意図されている。説明された或る実施形態から別の実施形態への要素の置換も当然に意図されており想定されている。本発明は単なる例示によって説明されてきたこと、及び具体的な詳細事項の修正は本発明の範囲から逸脱することなくなされてよいことが、理解されるであろう。明細書、特許請求の範囲及び図面により開示された特徴の各々は、独立して使用されてもよいし、或いは任意の適切な組み合わせにより使用されてもよい。特許請求の範囲に参照番号がある場合、それは単なる例示に過ぎず、特許請求の範囲を限定する如何なる影響も有しない。