ディジタル・キャラクタ或はその類等の画面上でのナビゲーションに対する方法及びシステム
ディジタル・ワールド内の始点から終点までキャラクタ或はオブジェクト等のディジタル・エンティティを画面上で移動する方法であって、前記可動ディジタル・エンティティに対する障害物の位置を提供し；到達可能な空間として障害物無しに前記ディジタル・ワールドの部分を規定し、その到達可能な空間を凸セルに分割することによってディジタル・エンティティに対するナビゲーション・メッシュを作り出し、前記凸セルの間に始セル及び終セルを配置し、前記始セルが前記終セルと対応していれば、前記ディジタル・エンティティが前記始点から前記終点まで移動させられるように構成されている。もし前記始セルが前記終セルと対応していなければ、前記始点から前記終点までの前記凸セルの間における複数セルから成るシーケンスの連続したセルの間の境界上に配置された媒介点を決定し、前記ディジタル・エンティティを前記始点から前記終点への各連続した媒介点まで移動させる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はディジタル・エンターテイメント産業及びコンピュータ・シミュレーションに関する。より詳細には、本発明はディジタル・オブジェクト或はキャラクタの画面上でのナビゲーションに対する方法及びシステムに関する。
【背景技術】
【０００２】
多年来、３次元（３Ｄ）コンピュータ・グラフィックは、映画アニメーション、ディジタル効果、ゲーム、並びに、シミュレーションを含む多くの適用例を有する充分に確立された分野である。
【０００３】
添付図面内の図１は、例えば、アニメーション・パッケージ、ビデオ／コンピュータ・ゲーム、トレイナー、或は、シミュレータの形態であり得る先行技術からの包括的な３Ｄ適用例を図示する。この３Ｄ適用例はオブジェクトの基本的には高いレベル・アーキテクチャを共有し、それらオブジェクトはディジタル・エンティティとしてより一般的には言及され得るものであり、入力装置を介したコントローラによって、或は、物理学過程及び人工知能（ＡＩ）システムによって操作され、ビジュアル・レンダリング及びオーディオを含む合成器によってユーザにとって実感が沸くようにしている。
【０００４】
ワン・レベル・ディパー、３Ｄ適用例は典型的には、シミュレータ及び画像発生器の２つの構成要素に崩壊させられる。図２及び図３に図示されているように、シミュレータは人オペレータ及びＣＧＥの双方から数多くの入力を取り入れており、次いで該シミュレータはそれ従ってワールド・データベースを変更して、変化を可視化のために画像発生器に出力する。
【０００５】
典型的なシミュレータ／アニメーション・ループ構造は図４に図示されている。ワールド状態マネージャはワールド・データベースから初期データを先ず積み込む。シミュレーションの各フレーム／チックに対して、ワールド状態マネージャはコントローラを更新し、該コントローラはそれ従って行動し、オブジェクト更新をマネージャに送り戻す。次いでワールド状態マネージャは全てのオブジェクト更新をワールド・データベース（ＷＤＶ）における新ワールド状態内に分解し、それを画像発生器（ＩＧ）に渡す。このＩＧはキャラクタ・ボディ肢位置や他のオブジェクトを更新して、それらを画面に提供する。
【０００６】
最近になって、物理的過程及び人工知能（ＡＩ）技術によって駆動される手続き上のアニメーションは３Ｄアニメーション、ビジュアル効果、並びに、ゲームの分野に導入された。ＡＩアニメーションは、訓練にわたってディジタル・エンターテイナー及びシミュレータの能力を増大することを可能とする。それはゲーム・デザイナー及びシミュレータにフィルム・アクタの幅、独立性、並びに、戦法を付与する。映画制作者はゲーム・キャラクタの一時的パフォーマンスやシミュレーション・エンティティの行動現実性を得ている。
【０００７】
２０年にわたって、映画撮影所のビジュアル効果部門は、コンピュータを介して以外の他の任意の方法を作り出すことは高価過ぎ、危険過ぎるか或は不可能であるときは常に、コンピュータ・グラフィックに益々依存してきた。驚くことなく、より見事で現実的なビジュアル効果を作り出すアニメータの芸術的な才能に対する需要も増大してきた。コンピュータ・アニメーション・チームが主演男優として映画の成功に重要であることは、現行珍しくない。
【０００８】
大群衆場面、特に戦闘場面はコンピュータ・グラフィック技術にとって理想的な候補であり、その理由は、要求される非常に多くのエキストラがそれら場面を極端に高価となし、それらの暴力的特徴が非常に危険となし、そして野獣戦士が実行不可能となし、もし不可能であれば、人のエキストラで撮影することになる。もし、そうした場面の複雑性、費用、危険性が付与されれば、効果的な人工知能（ＡＩ）アニメーション解決策がそうした戦闘を現実の人の俳優で実際に上演し撮影することがより好ましいことは明かである。しかしながら、ディジタルの群衆場面を発生する実用的で商業的な方法に対する明かな必要性にもかかわらず、満足な解決策は実現するには時間がかかった。
【０００９】
アリアス システム(Alias Systems)によるマヤ(Maya)（商標）等の商業的アニメーション・パッケージはここ２０年で、実質上、全ての３Ｄの制作スタジオがそれらに依存してそれらの制作パイプラインの基礎を形成した点まで大きな進歩を遂げた。それらのパッケージは特殊な効果や個々別々のキャラクタを作成する点で優れている。しかしながら、自動／群衆アニメーションは依然として重大な問題である。
【００１０】
コンピュータ・ゲーム分野において、１９７０代にビデオ・ゲームの幕開け以来、ゲームＡＩは存在していた。しかしながら、それはポン(Pong)（商標）及びパックマン(Pac-Man)（商標）の創造以来、長い道のりであった。今日、ゲームＡＩはゲームの成功にとって益々決定的要因となり、ゲーム開発者はそれらＡＩからより多くのものを要求している。今日のＡＩは、外見上、自身で考えて、それらの環境や経験に従って行動して、知的振る舞いの印象を付与する、即ち、それらは自主的である必要がある。
【００１１】
ゲームＡＩはゲームをより夢中にさせる。典型的には、ゲームＡＩは以下の状況で使用される。
・知的非プレーヤ・キャラクタ（ＮＰＣ）を作成すること、それはそのプレーヤ制御キャラクタに対する味方或は敵であり得る；
・ワールドに現実性を付加すること。変化するゲーム・ワールドに反応する何等かの非ゲーム遊技関連ゲームＡＩを単に付加することは、現実性を増大し、ゲーム経験を向上する。例えば、ＡＩはスポーツ競技場をアニメ観客で一杯にすべく或はコウモリ群を地下牢場面に付加すべく使用され得る；
・何もなければ、対戦相手を作成すること。多くのゲームは二人或はそれ以上のプレーヤ用に設計されているが、もし対抗してプレイすべき者がいなければ、知的ＡＩ対戦相手が必要とされる；或は
・チーム・メンバーが充分でなければチーム・メンバーを作成すること。ある種のゲームはチーム・プレイを要求し、ゲームＡＩは充分なプレーヤがいなければその欠員を満たすことができる。
【００１２】
（例えば、３Ｄ都市内で相互作用出来る車両及び人々等の）リアルタイム知的３Ｄエージェントに対する別のアプリケーションは軍隊シミュレーション、訓練（ＭＳ＆Ｔ）、並びに、より詳細にはミリタリー・オペレーション（軍事行動）・アーバン・テレイン(MOUR: Military Operation Urban Terrain)である。実際上、西欧軍隊を含む最近１５年内の全ての闘争は、事実上、都市（モガディシュ、ボスニア、並びに、イラク）であった。それにもかかわらず、複雑な都市地勢におけるリアルタイムの群衆シミュレーションは数の多さの理由のために無視された：
・最近までハードウェアは単純は充分に強力ではなかった；
・陸軍は変化を承認すべく非常に緩慢に移動し、それで彼等は必要に応じてそれを強調すべく対応して緩慢である；そして
アプリケーション開発者は機械シミュレーションより非常により難しいために人のシミュレーションを回避してきた。
【００１３】
人工知能の役割は、戦闘、交戦国（青及び赤の軍隊）、並びに、増大する一般市民（緑の軍隊）における人々（地上部隊ばかりではなく、車両のドライバをも）をシミュレートする。ＭＳ＆Ｔの文脈において、それらはしばしばコンピュータ生成軍隊（ＣＧＦ）或は半自動軍隊（ＳＡＦ）と呼称される。可能性あるシミュレートされたエージェントのタイプは以下に記載される。
【００１４】
車両ドライバ及びパイロット：車両は物理学過程で非常に複雑なモデルを有し（例えば、回転に傾きそして戦車は溝に飛び込むと跳ね返るように、ヘリコプターは現実的に揺動する）、そして、武器／通信システム（例えば、視線方向無線通信は丘を通して働かない）、それらはＭＯＵＴ（例えば、ヘリコプターが超高層周りよりもむしろ超高層を真っ直ぐ通じて飛び、そして戦車は当惑して第３ワールドの曲がりくねった廃物が満ちた道にはまり込んで抜け出せない）の３Ｄ具体的峡谷に入る単純な視線方向ナビゲーション・システムを有する傾向がある。ＡＩが使用されて得て、車両における人のドライバの頭脳をシミュレートする（実際のボディがシミュレートされると共に、或は、それがシミュレートされずに）。
【００１５】
個々別々の教義上の交戦国から成る群：ＵＳ軍事施設のみに限定されると共に都市環境において適切にナビゲート出来ないので、それらの有用性がＭＳ＆Ｔ適用例に限定されているので、個々別々の教義上の交戦国から成る群の合衆国政府作成ＳＡＦ。集合体ＳＡＦが戦略レベルでそしてしばしば難解レベルで軍事行動する一方で、個々別々の交戦国シミュレータは戦略レベルでそしてしばしば３Ｄ物理的レベルで軍事行動する。
【００１６】
個々別々の不規則な交戦国：定義によって、民兵及びテロリスト等の不規則な交戦国は非教義的であり、それ故にそれらの個性や戦略を従来のＳＡＦアーキテクチャで表現することは難しい。
【００１７】
個々別々の非交戦国（混雑）から成る群：ＭＯＵＴの最も困難な制限の内の１つは、非交戦国で占有された環境下で軍隊軍事行動をどのように実行させるかである。それら大きな一般市民は作戦上の「クラッター」としてだけ行動することによって任務に影響して戦闘の成り行きに実際に影響する。
【００１８】
ゲームＡＩ及びＭＳ＆Ｔのより特有の局面の内の１つは、エージェント自体のリアルタイム知的ナビゲーションであり、例えば、群衆シミュレーションの状況下でのエージェント自体のリアルタイム知的ナビゲーションである。
【００１９】
コンピュータ・グラフィック群衆シミュレーションは、非特許文献１でのＣ．Ｗ．レイノルズ(Reynolds)によって開拓された。レイノルズは動作は知性の基本的目標であり、知的キャラクタ自体は単純な車両モデルで表現可能であると云う核となる着想を確立した。このシステムは単純な「集団」振る舞いを作り出す点で極端に有効であり、且つ、映画特殊効果等の非リアルタイム適用例におけるコウモリ及び鳥等の動物のシミュレーションにおける大いなる成功を伴って使用されてきた。
【００２０】
非特許文献２のミューゼ(Musse)及びタルマン(Thalmann)は、ヴィクラウド(ViCrowd)と呼称されるリアルタイム群衆シミュレーションに対する階層モデルを開発し、その中で、人は個々別々でばかりではなくグループ・レベルで制御される。
【００２１】
粒子系として群衆を表現し且つクレバー・プレ-コンピュータ・アルファ-チャネル・レンダリング技術を用いることによって、テチアル等(Tecchial et al.)（Ｔｅｃｃｈｉａｌ Ｆ． Ｌｏｓｃｏｓ Ｃ．，Ｃｈｒｙｓａｎｔｈｏｕ Ｙ．の非特許文献３）は、ＰＣ上の疑似リアルタイムにおける非常に単純な製粉群の多数をシミュレート及びレンダリングする点で成功している。しかしながら、群衆は刺激に反応出来なかった。
【００２２】
リース(Reece)は分解歩兵半自動軍隊（ＤＩＳＡＦ）システム（非特許文献４を参照）内で群衆をモデル化するシステムを開発した。
【００２３】
スング等(Sung et al.)は、著者が群衆の振る舞いに対する情報をワールド幾何形状に直に描き出すことを可能とすることによって、知的粒子としての群衆メンバーの概念を詳しく説明する。この著者最適化は群衆メンバーを製粉からパニック（非特許文献５を参照）までの遷移等の変更された振る舞い間の動的な変化に限定している。
【００２４】
動作は、二足歩行、車輪で動く、牽引、或は、航空のいずれであれ、あるシミュレーション内での全エンティティの基礎となっている。それ故に、ＡＩシステムは点Ｘから点Ｙまで現実的にエンティティが誘導（ナビゲート）をすることを可能としている。例えば、車両に対して、これが意味することは、通常動作において、道路上でのドライビングや、車線で停止且つ信号機で停止等の交通規則に従うこと、そして、軍事活動においては、道路上の障害物を回避し、民間見物人を越えないようにしていることである。民兵に対してこれが意味することは、通常動作において、目立たないように歩道を歩くことであるが、軍事活動においては建造物内に迅速に駆け込んで、その階段を駆け上がって、ＲＰＧを開始すべく屋上に駆け上ることである。知的ナビゲーションは２つの基本レベルに分裂させられ得る：ＸからＹまでの経路を動的に見出して、その経路に沿っての動的障害を回避することである。
【００２５】
エージェント・ナビゲーションの一例は以下の予め決定された経路（例えば、パトロール経路上のガード）である。そうした予め決定された経路は、ディジタル・キャラクタが従うように指示され得る中間地点から成る順序集合である。例えば、走路を巡る経路はトラックの曲がり角での中間地点から成る。経路追従は、その経路上に最も近い中間地点を捜し出すことからなり、直接的な視野方向によってそこまでナビゲートしてから、該経路上の次の点までナビゲートする。キャラクタは現行の中間地点（即ち、中間地点の境界球内）に到着すると次の中間地点を捜す。例えば、図５はキャラクタが特定の方法である領域をパトロールするように指示すべくどのように経路が使用され得るかを示している。
【００２６】
判明されたことは、ナビゲーション機構としての経路追従は、スタート及び目的地が知られるばかりではなく、その経路が明白に知られる際に充分に稼働することである。
【００２７】
しかしながらこれは規則と云うよりむしろ例外であり、通常はキャラクタにその目的地を知らせたく、そしてそれにそれ自体の経路を、それ自体の知識やそのワールドに基づき、障害物を巡るそれ自体の経路を見つけ出させたいからである。
【００２８】
しかしながらディジタル・ワールド内での画面上で始点から終了点までディジタル・エンティティを自動的に移動させる方法が望まれる。
【非特許文献１】Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ，２１（４）（ＳＩＧＧＲＡＰＨ ８７ Ｐｒｏｃｅｅｄｉｎｇｓ），２５−３４，１９８７での「Ｆｌｏｃｋｓ，Ｈｅｒｄｓ，ａｎｄ Ｓｃｈｏｏｌ：Ａ Ｄｉｓｔｒｉｂｕｔｅｄ Ｂｅｈａｖｉｏｕｒａｌ Ｍｏｄｅｌ」
【非特許文献２】ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ７，（Ｎｏ．２Ａｐｒ．−Ｊｕｎ．２００１），１５２−１６４における「Ｈｉｅｒａｒｃｈｉｃａｌ ｍｏｄｅｌ ｆｏｒ ｒｅａｌ ｔｉｍｅ ｓｉｍｕｌａｔｉｏｎ ｏｆ ｖｉｒｔｕａｌ ｈｕｍａｎ ｃｒｏｗｄｓ」
【非特許文献３】Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ Ｆｏｒｕｍ ２１：１， Ｅｕｒｏｇｒａｐｈｉｃｓ， ２００２における「Ｖｉｓｕａｌｉｚｉｎｇ ｃｒｏｗｄｓ ｉｎ Ｒｅａｌ-ｔｉｍｅ」
【非特許文献４】リース，Ｄ．Ａ．，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｅｌｅｖｅｎｔｈ Ｃｏｎｆｅｒｅｃｅ ｏｎ ａｎｄ Ｂｅｈａｖｉｏｒ Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ （Ｏｒｌａｎｄ，ＦＬ，Ｍａｙ ７−９，２００２），８７−９５
【非特許文献５】Ｓｕｎｇ，Ｍ．， Ｇｌｅｉｃｈｅｒ，Ｍ．， ａｎｄ Ｃｈｅｎｎｅｙ，Ｓ．のＣｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ Ｆｏｒｕｍ２３：３，Ｅｕｒｏｇｒａｐｈｉｃｓ，２００４における「Ｓｃａｌａｂｌｅ ｂｅｈａｖｉｏｒｓ ｆｏｒ Ｃｒｏｗｄ Ｓｉｍｕｌａｔｉｏｎ」
【発明の開示】
【発明が解決しようとする課題】
【００２９】
本発明の目的は、それ故に、ディジタル・ワールド内でのディジタル・エンティティに対する改善されたナビゲーション方法を提供することである。
【００３０】
本発明の他の目的は、始点から終点まで画面上のディジタル・エンティティを自動的に移動させる方法を提供することである。
【課題を解決するための手段】
【００３１】
より詳細には、本発明の第１局面に従えば、少なくとも１つのディジタル・エンティティを始点から終点まで画面上で移動するコンピュータ・システムにおける方法が提供され、該方法が、
i）ディジタル・ワールド内での少なくとも１つの可動ディジタル・エンティティに対する障害物の各位置を提供し；前記少なくとも１つの可動ディジタル・エンティティに対する到達可能な空間として障害物無しに前記ディジタル・ワールドの少なくとも複数の部分を規定する段階と、
ii）その到達可能な空間を少なくとも１つの凸セルに分割することによって少なくとも１つの可動ディジタル・エンティティに対するナビゲーション・メッシュを作り出す段階と、
iii）始点及び終点をそれぞれ含む前記少なくとも１つの凸セルの間に始セル及び終セルを配置する段階と、
iv）前記始セルが前記終セルと対応しているかを確認し；もし前記始セルが前記終セルと対応していれば、iv）ａ）前記少なくとも１つの可動ディジタル・エンティティを前記始点から前記終点まで移動させ；もし前記始セルが前記終セルと対応していなければ、iv）ｂ）i）前記始点セルから前記終点セルまでの前記少なくとも１つの凸セルの間に複数セルから成るシーケンスを決定し、そして、iv）ｂ）ii）複数セルから成る前記シーケンス内の連続したセルの間の各境界上に配置された少なくとも１つの媒介点を決定し、そして、iv）ｂ）iii）前記少なくとも１つの可動ディジタル・エンティティを前記始点から前記終点への各連続した前記少なくとも１つの媒介点まで移動させる段階と、
の諸段階を含む。
【００３２】
本発明の第２局面に従えば、ディジタル・ワールド内においてディジタル・エンティティを始点から終点まで画面上で移動するシステムが提供され、該システムが、
前記ディジタル・ワールドについての情報を記憶し且つ前記ディジタル・ワールド内での前記可動ディジタル・エンティティに対する障害物の各位置を提供するワールド・データベースと、
ナビゲーション・モジュールであり、
i）可動ディジタル・エンティティに対する到達可能な空間として障害物無しのディジタル・ワールドの少なくとも複数の一部を規定し、
ii）前記到達可能な空間を少なくとも１つの凸セルに分割することによって前記可動ディジタル・エンティティに対するナビゲーション・メッシュを作り出し、
iii）前記始点及び前記終点をそれぞれ含む少なくとも１つの凸セルの間に始セル及び終セルを配置し、
iv）前記始セルが前記終セルと対応しているかを確認し；もし前記始セルが前記終セルと対応していなければ、v）前記始セルから前記終セルまでの前記少なくとも１つの凸セルの間における複数セルから成るシーケンスを決定し、そして、vi）複数セルから成る前記シーケンス内の連続したセルの間の各境界上に配置された少なくとも１つの媒介点を決定することからナビゲーション・モジュールと、
前記ナビゲーション・モジュール及び前記ワールド・データベースに結合されたシミュレータであり、iv）で確認されたように、もし前記始セルが前記終セルと対応していれば前記始点から前記終点まで当該シミュレータと結合された画像生成器を介して画面上で前記ディジタル・エンティティを移動するか、或は、もし前記始セルが前記終セルと対応していなければ前記始点から前記終点への各連続した前記少なくとも１つ媒介点まで前記ディジタル・エンティティを移動することから成るシミュレータと、
を備える。
【００３３】
留意されるべきことは、表現「キャラクタ」は、ここでは、「エンティティ」として広義に解釈されるべきである。
【００３４】
本発明の他の目的、長所、並びに、特徴等は、添付図面を参照しての例証を前提すれば、好適実施例の以下の非制限的記載を読むことでより明かとなる。
【発明を実施するための最良の形態】
【００３５】
本発明の例示的実施例に従ったディジタル・ワールド内における始点から終点まで、ディジタル・エンティティを画面上で移動させる方法を実施するナビゲーション・モジュール１２を含むディジタル画像エンティティ（ＩＥ）の画面上でのアニメーションに対するシステム１０を、以下、図６を参照して記載される。
【００３６】
このシステム１０は、図２に図示されたもの等の従来の３Ｄ適用例と類似点を共有し且つ簡明性目的のため、システム１０と従来の３Ｄ適用例システムとの間の相違のみがここでより詳細に記載される。
【００３７】
システム１０は、シミュレータ１４、シミュレータ１４と結合されたワールド・データベース（ＷＤＢ）１６、ワールド・データベースＤＢ及びシミュレータ１４の双方と結合された複数の画像生成器（ＩＧ）１８（３つのみが示されている）、シミュレータ１４と結合されると共に本発明の例示的実施例に従ったナビゲーション・モジュール１２、シミュレータ１４とも結合された意思決定モジュール、各ＩＧ１８とそれぞれ結合された複数のアニメーション制御モジュールを備える。
【００３８】
ＩＧ１８の数は、勿論、適用例に依存して変動し得る。例えば、システム１０が３Ｄアニメーション適用例で実施されている場合、ＩＧ１８の数はレンダリング時間に影響し得る。
【００３９】
シミュレータ１４及びＩＧ１８は単一コンピュータの形態であり得る。ワールド・データベース１６は、限定されるわけではないが、ハード・ドライブ、対応するドライブ上で読み取られるＤＶＤ若しくはＣＤ-ＲＯＭディスク等の任意の適切なメモリ手段、或は、コンピュータ１４のランダム・アクセス・メモリ部に記憶させられる。
【００４０】
シミュレータ１４及びＩＧ１８は、以下により詳細に説明されることになる、動画化、シミュレート、或は、ゲーミングのための指示でプログラムされた、コンピュータ或は演算ユニットが具備された任意の演算器の形態である。
【００４１】
シミュレータ１４、ＩＧ１８、並びに、ＤＢ１６は、インターネット等のコンピュータ・ネットワーク（不図示）を介して遠隔的に結合され得る。
【００４２】
勿論、システム１０の適用例に依存して、シミュレータ１４はゲーム・エンジン或は３Ｄアニメーション・システム等の別の形態を採用し得る。
【００４３】
モジュール１２，２０，２２は、例えば、シミュレータ１４内でプログラムされたサブ-ルーチン或は専用指示の形態である。モジュール２０，２２及びの特性及び機能、そしてより詳細には、モジュール１２の特性及び機能は、本発明の例示的実施例に従った、ディジタル・ワールド内での始点から終点までディジタル・エンティティを画面上で移動させる方法１００の以下の非制限的記載を読むことでより明らかとなる。
【００４４】
図７に図示されている方法１００は以下のステップを含む：
１０２-ディジタル・ワールド内での可動ディジタル・エンティティに対する障害物の各位置を提供し、その可動ディジタル・エンティティに対する到着可能な空間としての障害物無しディジタル・ワールドの少なくとも部分を規定するステップと；
１０４-到着可能な空間を凸セルに分割することによって可動ディジタル・エンティティに対するナビゲーション・メッシュを作り出すステップと；
１０６-始点及び終点をそれぞれ含む凸セルの間に始セル及び終セルを配置するステップと；
１０８-始セルが終セルと対応するか否かを確認するステップと；
もし始セルが終セルと対応していれば：
１１０-ディジタル・エンティティを始点から終点まで移動させて、この方法を停止するステップと；
もし始セルが終セルと対応していなければ：
１１２-始セルから終セルまで凸セルの間の複数セルから成るシーケンスを決定する；
１１４-複数セルから成るそのシーケンス内の連続したセルの間の各境界上に配置された媒介点を決定するステップと；
１１６-ディジタル・エンティティを始点から終点への各連続した媒介点まで移動させるステップとである。
【００４５】
これらステップの各々は、以下に、より詳細に記載される。
【００４６】
ステップ１０２において、ディジタル・ワールド内の可動ディジタル・エンティティに対する障害物の各位置は、可動ディジタル・エンティティに対する到着可能空間としての障害物無しのディジタル・ワールドの部分を生ずるように規定される。到着可能空間はバリヤーによって閉鎖されたディジタル・ワールドの領域として規定されている。
【００４７】
留意されるべきことは、シミュレータ１４が特定の可動ディジタル・エンティティに対する障害物を考慮するものは、啓発することを可能とする以下に付与された更なる例として別のものに対する障害物ではあり得ないことである。
【００４８】
勿論、ディジタル・ワールドは、可動ディジタル・エンティティが相互作用する任意の自発性或は非自発性のエンティティを含んで、先行して規定され得る。ディジタル・ワールド及びディジタル・エンティティの概念は、以下、本発明の例示的実施例に従って記載される。
【００４９】
ディジタル・ワールド・モデルは画像オブジェクト要素を含む。これら画像オブジェクト要素は、オブジェクトや、自発性及び非自発性のキャラクタ、建造物、動物、木々等の２次元或は３次元（２Ｄ或は３Ｄ）のグラフィカル表現を含む。それはまたバリヤー、地勢、並びに、表面をも含む。以下の記載を読むことで明らかとなるように、方法１００を用いて移動されるように可動エンティティは自発性或は非自発性の何れかであり得る。自発性及び非自発性のキャラクタ及びオブジェクトの概念は、以下、より詳細に記載される。
【００５０】
当業界で共通して知られていると思われるように、オブジェクト及びキャラクタのグラフィカル表現は、コンピュータ画面上或は別のディスプレイ装置上に、表示され、動画化されるか或は否かであり得るが、ディスプレイ装置上への表示無しに仮想のワールド内において居住し相互に作用し合うことも可能である。
【００５１】
バリヤーは、壁、動いているドア、トンネル等、或は、ディジタル・ワールドにおける任意の可動エンティティに対する任意の障害物を構築すべく使用可能である三角形平面である。地勢は２Ｄ高度場であり、それにエンティティが自動的に支配され得る（例えば、兵士キャラクタが丘を越えて行進することを保持する）。表面は、自発性キャラクタが束縛されもする完全３Ｄ形状を形成すべく組み合わせられ得る三角形平面である。
【００５２】
組み合わせにおいて、これら要素はキャラクタが居住するワールドを記載すべく使用されるものである。それらはワールドＤＢ１６内に記憶される。
【００５３】
画像オブジェクト要素に加えて、ディジタル・ワールド・モデルは、自発性キャラクタ、及び、ディジタル・ワールドにおける他のオブジェクトを含んで、エンティティを管理することを可能とするソルバー（解答するもの）を含む。
【００５４】
ソルバーは３Ｄコンフィギュレーションを有し得て、エンティティに移動の完全な自由度を具備させるか、或は、２Ｄコンフィギュレーションは、計算上より効率的であり、アニメーション・システムの性能に影響すること無しに、オペレータがより多くの可動エンティティをスクリーン内に挿入させることを可能としている。
【００５５】
２Ｄソルバーは３Ｄソルバーよりも計算上より効率的であり、その理由はソルバーがエンティティの画像オブジェクト要素の垂直（ｙ）座標を考慮しないからである。２Ｄ及び３Ｄコンフィグレーションの間の選択は、可動エンティティ及び他のオブジェクトによって仮想のワールド内において許容されている移動に依存する。もしそれらが垂直平面内で移動しなければ、３Ｄ及び２Ｄのソルバーが使用可能なものに対する解決すべき要件がない。しかしながら、もし任意のエンティティが移動の完全な自由度を要求すれば、３Ｄソルバーが使用される。留意されるべきことは、２Ｄの選択が、２Ｄ或は３Ｄであり得る仮想ワールドの次元を限定しないことである。
【００５６】
非自発性キャラクタはディジタル・ワールド内のオブジェクトであり、それらがディジタル・ワールドと潜在的に相互作用し得るにもかかわらず、該ディジタル・ワールドはソルバーによって駆動されない。これらは従来の動画化キャラクタ（例えば、グループのリーダ）から、シミュレータの他の構成要素によって駆動される（例えば、飛び散る破片）オブジェクトへのプレーヤ・キャラクタまで変動し得る。
【００５７】
バリヤーは可動エンティティに対する障害物を表現すべく使用され、一方向壁と同等、即ち、ディジタル・ワールドに居住するオブジェクト或はディジタル・エンティティはそれら壁を一方方向であるが他方方向ではなく通過できる。バリヤーが作り出されると、スパイク（前方配向ベクトル）が使用されてオブジェクト或はエンティティによって検出され得る壁の一方面を指示する。それ故に、オブジェクト或はエンティティは非スパイク側からスパイク側まで通過出来るが、その逆は出来ない。留意されるべきことは、ある種の適用例において、特定の回避制約は規定可能であり且つディジタル・エンティティがディジタル・ワールド内のバリヤーを回避する試みを為すべく起動可能である。振る舞い及び制約の概念は、以下に、より詳細に記載される。
【００５８】
図８及び図９にそれぞれ図示されているように、バリヤーは線によって２Ｄソルバーで表現され且つ３Ｄソルバーで三角形で表現される。２Ｄ及び３Ｄバリヤーに対するスパイクの方向も図８及び図９に示されており（矢印２４及び２６参照）、Ｐ１乃至Ｐ３がバリヤーの複数点が描かれている順序を言及している。バリヤーは単指向性であるので、両面バリヤーは２つのバリヤーを重畳させて、それらスパイクを相互に対向させて設定することで作られている。
【００５９】
各バリヤーは以下のパラメータによって規定され得る：
【表１】
【００６０】
共通して知られているように、境界ボックスは３Ｄオブジェクトを封入して境界付ける直線的ボックスである。
【００６１】
ディジタル・ワールド・モデルのソルバーはサブ-ソルバーを含み得て、それらがシミュレーションを走らせるべく使用されるソルバーの様々なエンジンである。各サブ-ソルバーは、計算を最適化するために、オブジェクト及びシミュレーションの特定局面を管理する。
【００６２】
当業界で共通して知られているように、各動画化ディジタル・エンティティはアニメーション・クリップと関連されて、ディジタル・ワールド内での移動中のエンティティを表現することを可能としている。本発明の特定実施例に従えば、仮想センサは幾つかのエンティティに割り当てられ且つそれらによって使用されて、それらが画像オブジェクト要素或はディジタル・ワールド内の他のエンティティについてのデータ情報を集めることを可能としている。決定木をも、データ情報を処理するために使用され得て、アニメーション・サイクルの内の１つ選択及びトリガーするか或は新振る舞いを選択するようになる。
【００６３】
当業界で周知であると思われるように、ここでは「アニメーション・クリップ」としても言及されるアニメーション・サイクルは、典型的には繰り返され得るアニメーションの単位である。例えば、キャラクタを歩かせるために、アニメータは「ウォーク・サイクル」を作り出す。このウォーク・サイクルはキャラクタに１回の反復を行わせる。キャラクタをもっと歩かせるために、サイクルのより多くの反復が起用される。もしキャラクタが経時的にスピードアップ或はスローダウンすれば、サイクルはそれに応じて「スケールされ（増減され）」て、サイクル速度がキャラクタ変位と符合して、何等滑り（例えば、キャラクタが地面上を滑っているように見える）がない。
【００６４】
自発性画像エンティティは動画化エンジン（或はプラットフォーム）のノードを変換すべく密接されている。ノードは、ロケータ、キューブ、或は、動物のモデル、車両等の形態であり得る。アニメーション・クリップ及び変換ノードが当業界で周知であると思われるので、ここではそれらが以下で更に詳細に記載されない。
【００６５】
図１０はＩＥを移動させ且つソルバーによって使用される座標システムを示す。
【００６６】
可動ディジタル画像エンティティと関連され得る属性の例は以下の表２に簡潔に記載されている。
【表２】
【００６７】
勿論、他の属性もＩＥを特徴付けるべく使用され得る。
【００６８】
ＩＥ振る舞いの概念は、以下に、より詳細に記載される。
【００６９】
属性に加えて、本発明のＩＥは振る舞いによっても特徴付けられ得る。決定木と一緒に、振る舞いはＩＥの低レベル思考装置である。それらは仮想センサを用いてディジタル・ワールドから生データを受け取って、それを処理して、それに応じてＩＥの状態を変更する。
【００７０】
振る舞いは、例えば機関車振る舞いのように分類されて、ＩＥが移動することを可能としている。それら機関車振る舞いは、例えば、運動、速度、並びに、配向（即ち、ＩＥが対向する方向）のＩＥ方向の任意のもの或は全てのものに影響し得る操舵力を生成する。
【００７１】
下記の表３は振る舞い例を含む：
【表３】
【００７２】
機関車振る舞いはＩＥに作用する力として見られ得る。この力は振る舞い力であり、物理的（重力等）と類似して、力がＩＥ自体内から見えてくる相違を伴う。
【００７３】
留意されるべきことは、振る舞い力は加法的であり得る。例えば、自発性キャラクタは１つのアクティブ振る舞い以上を同時に有することができる。ソルバーは、振る舞いの優先順位及び強度に従って、構成要素振る舞い力を組み合わせことによってキャラクタの結果としての運動を計算する。結果としての振る舞い力はキャラクタに付与され、それがそれ自体の限界及び（キャラクタの旋回半径属性等によって特定される）制限を最終運動に対して強要し得る。
【００７４】
振る舞いはＩＥに対する広範な種類の作用を作り出すことを可能としている。振る舞いは４つのサブグループに分割可能であり：単純振る舞い、目標とされた振る舞い、並びに、グループ振る舞いである。
【００７５】
単純振る舞いは単一ＩＥを含むだけの振る舞いである。
【００７６】
目標とされた振る舞いはＩＥ及び目標オブジェクトに適用され、それらはディジタル・ワールド内の他の任意のオブジェクトであり得る（複数オブジェクトから成るグループを含む）。
【００７７】
グループ振る舞いはＩＥがグループとして行動し移動することを可能として、そこでは、そのグループに含まれた個々別々のＩＥが相互に略同一速度及び配向を維持している。
【００７８】
振る舞いの例は、以下に、４つの分類の各々に提供される。勿論、当業界の当業者においてＩＥに他の振る舞いを提供すると思われる。
【００７９】
（単純振る舞い）
「バリヤーの回避」
そのバリヤーの回避は、キャラクタがバリヤーとの衝突を回避させることを可能としている。
【００８０】
この振る舞いに固有のパラメータは、例えば、以下を含み得る：
【表４】
【００８１】
障害物回避振る舞いはＩＥが障害物との衝突を回避することを可能として、それは他の自発性及び非自発性の画像エンティティであり得る。そのバリヤー回避振る舞いに対するそうした詳細以外の類似パラメータもこの振る舞いを規定すべく使用され得る。
【００８２】
「での加速」
このでの加速振る舞いは、ＩＥを特定された量だけ加速することを試みる。例えば、もしその量が負値であれば、ＩＥはその特定された量だけ減速する。実際の加速／減速はＩＥの最大加速度及び最大減速度の属性で限定され得る。
【００８３】
この振る舞いに固有のパラメータは加速度であり、それはＩＥが維持しようとする速度（距離単位／フレーム２）における変化を表現する。
【００８４】
「での速度を維持」
このでの速度を維持振る舞いは、目標のＩＥの速度を特定の値に設定しようとするものである。これはキャラクタを静止に保持するか或は一定速度で移動させることを保持すべく使用され得る。もし所望速度がキャラクタの最大速度属性よりも大きければ、この振る舞いはキャラクタ速度をその最大速度と同等に維持しようとするだけである。同様に、もし所望速度がキャラクタの最小速度属性よりも小さければ、この振る舞いはキャラクタ速度をその最小速度に維持しようとする。
【００８５】
この振る舞いを規定することを可能とするパラメータは、キャラクタが維持しようとする所望速度（距離単位／フレーム）である。
【００８６】
「歩き回り」
歩き回り振る舞いはＩＥに無作為の操舵力を適用して、それがソルバー領域内において無作為風に移動することを保証する。
【００８７】
この振る舞いを規定することを可能とするパラメータは、例えば、以下の通りであり得る：
【表５】
【００８８】
「に配向」
このに配向振る舞いはＩＥが特定方向に対向しようとすることを可能としている。
【００８９】
この振る舞いを規定することを可能とするパラメータは以下の通りである：
【表６】
【００９０】
（目標とされた振る舞い）
以下の振る舞いはＩＥ（ソース）及びそのワールド内の別のオブジェクト（目標）に適用される。目標オブジェクトは、自発性或は非自発性の画像エンティティ、経路、グループ、並びに、データ等のワールド内における任意のオブジェクトであり得る。もし目標がグループであれば、振る舞いは任意時のグループの最も近いメンバーにだけ適用される。もし目標がデータであれば、そのデータはタイプＩＤであって、振る舞いの真の目標を目指していることが仮定される。ＩＤはワールド内のオブジェクトを一意に識別すべく使用される値である。このデータの概念は、以下に、より詳細に記載されている。
【００９１】
全ての目標とされている振る舞いによって共有されたパラメータは以下の通りである：
【表７】
【００９２】
「捜し求める」
この捜し求める振る舞いは、ＩＥが、別のＩＥに向かって、或は、複数のＩＥから成るグループに向かって移動することを可能としている。もしＩＥがグループを希求すれば、それは任意時にそのグループの最も近いメンバーを求める。勿論、捜し求める振る舞いはナビゲーション方法１００に従ってプログラムされ得る。
【００９３】
この振る舞いを規定することを可能とするパラメータは、例えば、以下の通りである：
【表８】
【００９４】
「から逃走」
振る舞いからの逃走はＩＥが別のＩＥから逃走すること或は複数のＩＥから成るグループから逃走することを可能としている。ＩＥがグループから逃走すると、随時、そのグループの最も近いメンバーから逃走する。振る舞いからの逃走は前記捜し求める振る舞いと同一の属性を有するが、対抗する操舵力を作り出す。振る舞いからの逃走を規定することを可能とするパラメータが前記捜し求める振る舞いのものと非常に類似しているので、それは、以下に、より詳細に記載されない。
【００９５】
「を見る」
このを見る振る舞いは、ＩＥが別のＩＥ或は複数のＩＥから成るグループと対面することを可能としている。もしこの振る舞いの目標がグループであれば、ＩＥはそのグループの内の最も近いメンバーを見ようとする。
【００９６】
「機銃掃射」
機銃掃射振る舞いは、ＩＥにその目標の周りを回るようにしており、言い換えれば、その目標へのその視線と直交する方向に移動させるようにしている。可能性パラメータは、ＩＥが旋回し他の方向で軌道を周り始めることの各フレームでそれがどの程度あり得るかを決定することが可能である。これは、例えば、蛾に炎の周りを回させるべく使用され得る。
【００９７】
例えば、その目標を見るか或はシュートすることが、ガードの前方運動だけ固有性をターン・オフして、ガードの目標に向けて設定された前記を見る振る舞いを付加することによって達成され得る。留意されるべきことは、これを為すべく、機銃掃射は方向だけに影響すべく設定され、しかるに前記を見るは配向だけに影響すべく設定される。
【００９８】
この振る舞いに特有であるパラメータは、例えば、可能性であり、それはＩＥが軌道の方向をどの程度頻繁に変えるかを決定する０及び１の間の値をとり得る。例えば、毎秒２４フレームで、０．０４の値が平均病後とに無作為方向変化をトリガーし、しかるに０．０１の値は平均４秒毎に変化をトリガーする。
【００９９】
「仲介者」
この仲介者振る舞いはＩＥが第１目標と第２目標との間に入り込むことを可能としている。例えば、この振る舞いは、ボディガード・キャラクタに複数の敵から成るグループからキャラクタを保護させることをイネーブルすべく使用され得る。
【０１００】
以下のパラメータはこの振る舞いを特定することを可能とし、それはエンティティが向かうことが望まれる第２目標にどの程度接近しているかを決定する０及び１の間の値を採り得る。
【０１０１】
「追従経路」
この追従経路振る舞いはＩＥが経路を追従することを可能としている。例えば、この振る舞いはレーシングカーが走路を巡って移動することをイネーブルすべく使用され得る。
【０１０２】
以下のパラメータはこの振る舞いを規定することを可能としている：
【表９】
【０１０３】
（グループ振る舞い）
グループ振る舞いは、個々別々のＩＥをグループ化して、それらが個性を維持しながらグループとして行動するように為すことを可能としている。例としては、魚の群れ、小鳥の群れ等々を含む。
【０１０４】
以下のパラメータはグループ振る舞いを規定すべく使用され得る：
【表１０】
【０１０５】
以下はグループ振る舞いの例の簡単な説明を含む。
【０１０６】
「整列」
この整列振る舞いは、ＩＥがグループの他のメンバーと同一の配向及び速度を維持することを可能としている。ＩＥはそのグループの１メンバーであり得るか或はあり得ない。
【０１０７】
「参加」
この参加振る舞いは、ＩＥがグループのメンバーと密に止まることを可能としている。このＩＥはそのグループの１メンバーであり得るか或はあり得ない。
【０１０８】
この振る舞いを規定すべく使用可能なパラメータの例は参加距離であり、それは目標とされた振る舞いにおける「接触半径」と類似する。近隣半径及びその参加距離外側の内部におけるグループの各メンバーは、振る舞いの操舵力を計算する際に考慮される。参加距離はキャラクタ間の外部距離である（即ち、キャラクタの境界球の外側の間における距離である）。このパラメータの値は、そのグループのメンバが維持しようとする密接性を決定する。
【０１０９】
「から分離」
このから分離振る舞いは、ＩＥがグループのメンバーから遠ざかる特定の距離を保持することを可能としている。例えば、これは魚の群れが余りにも混雑することを防止すべく使用可能である。この振る舞いが適用されるＩＥは、そのグループの１メンバーであり得るか或はあり得ない。
【０１１０】
分離距離はこの振る舞いを規定すべく使用可能なパラメータの１例である。近隣半径及び分離距離内側の内部におけるグループの各メンバーは、その振る舞いの操舵力を計算する際に考慮される。この分離距離は複数のＩＥ間の外部距離である（即ち、それらＩＥの境界球の外側の間における距離である）。このパラメータの値は、そのグループのメンバーが維持しようとする外部分離距離を決定する。
【０１１１】
「共に群がる」
この振る舞いは、複数のＩＥが相互に群がることを可能としている。それは、整列、参加、から分離の効果を組み合わせる。
【０１１２】
以下の表１１はこの振る舞いを規定すべく使用可能なパラメータを記載している。
【表１１】
【０１１３】
（振る舞いの組み合わせ）
ＩＥは、随時、相互に関連された多数のアクティブな振る舞いを有する。それ故に、重要性を所与の振る舞いに割り当てるべく手段が提供されている。
【０１１４】
これを達成するための第１手段は、振る舞いに強度及び優先順位を割り当てることによる。振る舞いの割り当てられた強度は、その振る舞いによって生成された操舵力がどの程度強力かに影響する。強度がより高ければ、生成された振る舞いの操舵力はより大きくなる。振る舞いの優先順位はその振る舞いが他の振る舞いを凌いで有する優位を規定する。より高い優先順位の振る舞いが起動されると、より低い優先順位の振る舞いが実効的に無視される。強度及び優先順位を振る舞いに割り当てることによって、より現実的な動画を作り出すために、どの振る舞いがどの状況においてより重要かアニメータがソルバーに知らせる。
【０１１５】
ソルバーが、ＩＥの新しい速度、位置、並びに、配向を計算するために、そのソルバーは全ての振る舞いの所望運動を計算し、それら運動を振る舞いの強度に基づき合計する一方、より低い優先順位のものは無視し、そして、ＩＥの属性において規定された最大速度、加速度、減速度、並びに、旋回半径を強化する。最終的には、旋回によるブレーキングは考慮され得る。事実上、キャラクタのブレーキング・ソフトネス及びブレーキ・パッディングの属性の値に基づき、キャラクタは旋回のためにスローダウンする。
【０１１６】
図７に戻って、以下、方法１００の詳細な説明が図１１に図示された１フロア建造物３０の内室の形態での単純なディジタル・ワールドや、障害物である暗線によって表現された壁３２、可動エンティティ（不図示）に対する到達可能な空間３４を規定する内部で取り囲まれた領域を参照して続行される。
【０１１７】
ステップ１０４で、ナビゲーション・メッシュ３５が可動ディジタル・エンティティ（不図示）に対して作り出される。これは到達可能な空間３４を、図１１の１フロア建造物の例のための図１２に図示された凸セル３６に分割或は変換することによって達成される。
【０１１８】
ナビゲーション・メッシュ３５は、手動的或は自動的の何れかで、例えば、衝突層或はレンダリング形状を用いて、作り出されることが出来る。衝突層は物理学的過程の衝突検出／解像度の目的のため、レンダリング形状の単純化である形状的メッシュである。この場合、ナビゲーション・メッシュは衝突層の部分集合であり、その衝突層上を可動エンティティが移動する（これは典型的にはフロアであり、壁ではない）。
【０１１９】
レンダリング形状からナビゲーション・メッシュを誘導することは、出来る限り形状を単純化することと、出来る限り継ぎ目のないメッシュにその形状を融合することとを要求する（例えば、交差している多角形の除去等々）。
【０１２０】
手動作成において、３Ｄオペレータ（典型的には３Ｄアーチスト）は入力形状を調査し、多角形を正しく融合し、非到着可能空間を取り去る。留意されるべきことは、これを高い度合いまで自動的に取り扱うアルゴリズムが存在することである。
【０１２１】
凸多角形はナビゲーション・メッシュ３５の作成においてセルとして使用されるが、その理由は、そうしたセル内の任意の点がセルの内の他の任意の点までの直線上で直に到着可能であるからである。
【０１２２】
ナビゲーション・メッシュにおけるセルＣｘ及びＣｙと連結しているエッジＥｘｙは、もしエンティティがＥｘｙを介してセルＣｘからＣｙまで通過出来れば「通過可能」と考えられる。
【０１２３】
ステップ１０６で、始点及び終点（不図示）が配置され、それら２つの点の各々を含む対応するセルが識別される。
【０１２４】
表現「始点」及び「終点」は、ここでは、限定的に解釈されるべきではない。事実上、ディジタル可動エンティティがピクセル・サイズでなければ、始点及び終点は仮想ワールド内の１つの箇所或は領域と言及される。
【０１２５】
ステップ１０８で、第１確認は、始点及び終点が双方共に同一セル内に配置されているか否かを確認することである。もしそうであれば、方法１００はステップ１１０に進み、そこでディジタル・エンティティが方法が停止する前に始点から終点まで移動させられる。先に述べたように、凸セルの使用はディジタル可動エンティティが１つのセル内を一直線状に移動すること或は移動させられることを可能としている。しかしながら、ある種の場合、例えばオブジェクト或は他の可動エンティティは該可動エンティティが衝突回避戦略を採用するように強制する可能性がある。以下により詳細に記載されるように、本発明のより特定の例示的実施例に従った方法１００は、そうした適合性ある振る舞い伴う可動ディジタル・エンティティをもたらす。
【０１２６】
方法１００に戻れば、もし始点及び主点が同一セル内に配置されていなければ、凸セル間での複数セルから成るシーケンスは、始セルから終セルまでの間でのディジタル可動エンティティに対する経路をもたらすように、それら始セルから終セルまで決定される（ステップ１１２）。
【０１２７】
ステップ１１２は、連結性グラフ３８を先ず構築することによって達成され、該グラフは各セル３６をノード４０で置き換えて、通過可能セル（ノード）の各対を線４２で連結することによって獲得される。連結性グラフ３８の例としては図１１及び図１２に図示された例に対する図１３に図示されている。勿論、そうしたグラフ３８は純粋に仮想であり、実際にグラフ的に作り出されない。
【０１２８】
次いで、結果としてのグラフ３８は始点及び終点をそれぞれ表現している２つのノード４０の間の経路を見出すべく調査される。数多くの既知の技術が使用され得て、そうしたグラフ調査問題を解決して、それら２つの対応するノードの間の経路をもたらす。その経路は、もし存在すれば、対応するセルとして復帰される。
【０１２９】
例えば、横幅第１調査（ＢＦＳ）が使用され得て、グラフ３８を調査する。この周知のＢＦＳ方法は、最低コストの経路を提供することを可能としているが、調査されるノードの数の点では非常に高価であり得る。これも使用可能である深さ第１調査（ＤＦＳ）は調査されるノードの数の点で著しくより安価であるが、最低コストで経路を提供することを可能としていない。経験側がこのＤＦＳに負荷され得て、計算的効率性を維持しつつ、経路品質を改善しようとする。
【０１３０】
留意されるべきことは、複数セルから成るそうしたシーケンスや、終点までのナビゲートすることが出来ることを防止されたエンティティを、ステップ１１２での方法で停止が全くないと云う状況であり得ることである。
【０１３１】
もし複数セルから成るそうしたシーケンスが存在すれば、媒介点（不図示）は複数セルから成るシーケンスにおける連続したセルの間の各境界上に決定される（ステップ１１４）。言い換えれば、各凸セルに対する入口／出口の点は選択される。
【０１３２】
例えば、各エッジの中心点は選択され得る。勿論、他の点は代替的に選択され得る。セル・エッジ（セル界面）上の点はセル間を移動する距離を低減してその経路を更に平滑にするように選択可能である。
【０１３３】
次いで、ディジタル・エンティティは始点からそれぞれ選択された連続した媒介点まで移動させられ、最終的には始点まで移動させられる（ステップ１１６）。
【０１３４】
図１４乃至図２１に移れば、方法１００は壁４６によって限界が定められた別の単純ワールド４４（図１４参照）を参照して図示されている。
【０１３５】
図１５に図示されているように、ナビゲーション・メッシュ４７は作り出され、ワールド４４は基準目的のためにＡからＺまでで識別される凸セル４８に分割される。
【０１３６】
始点５０及び終点５２は図１６に示されている。方法１００のステップ１０６に追従してそれらはセル「Ｚ」及び「Ｊ」にそれぞれ見出される。それらは同一セル内に配置されていないので、方法はステップ１１２で続行し点５０及び５２の間の複数セルから成るシーケンスの決定を伴って、図１６に図示されるような以下のシーケンス：「Ｚ」、「Ｙ」、「Ｏ」、「Ｘ」、「Ｗ」、「Ｖ」、「Ｕ」、「Ｔ」、「Ｈ」、並びに、「Ｊ」をもたらす。複数セルから成るシーケンスにおける連続したセルの間の各境界上に媒介点を決定した後（ステップ１１４）、方法は図１７に図示された決定経路５４に沿って移動するエンティティを伴って続行する。図１７で見られるように、経路はより現実的な足跡をもたらすべく平滑であり得る。
【０１３７】
本発明に従ったナビゲーション方法がエンティティが目標を求めようとする際に使用されるので、ナビゲーション・メッシュは実行時間に動的に変更され得る（ステップ１０４）。例えば、図１８及び図１９に図示されているように、セルはブラインド・データを介してターン・オフされて、道路閉塞或は過剰な人々或は物理学的過程従動破片による密集をシミュレートするか、或は、ターン・オンされて、ドア開口、密集終了若しくは破壊された壁の通過をシミュレートする。図１８において、前者のセル「Ｈ」はターン・オフされて第１代替経路５６を生じ、図１９において、双方の前者セル「Ｂ」及び「Ｈ」がターン・オフされて第２代替経路５８を生ずる。
【０１３８】
また方法１００は可動ディジタル・エンティティの次元、そしてより明確にはその幅等のその移動方向と相対的なその横方向次元を考慮することを可能としている。ステップ１０４でのナビゲーション・メッシュの作成は可動エンティティのそうした特性を考慮することが出来て、方法１００はエンティティが通過出来る経路を出力する。これは図２０及び図２１に図示されている。
【０１３９】
図２０は方法１００から獲得された経路６０を図示して、ディジタル・エンティティを始点６２から終点６４まで移動させている。図２１における可動ディジタル・エンティティの幅を２倍にすることによって（球６６によって図示）、前者のセル「Ｌ」はもはやナビゲーション・メッシュ６８の部分ではなく、新経路７０がこの方法１００によって提供される。（図２１の球６６を参照）
【０１４０】
方法１００は２次元ディジタル・ワールドに限定されない。図２２及び図２３に図示されるように、方法１００が使用され得て、始点及び終点の間の経路を決定し、次いで、３次元ディジタル・ワールドにおけるそれら２つの点の間において動画化キャラクタ等のディジタル可動エンティティを移動させる。図２２は、シミュレータ、ゲーム、或は、アニメーションの小都市部分上の平面図生成器の出力を図示している。図２３は、方法１００でのステップ１０４から生ずるナビゲーション・メッシュを図示している。
【０１４１】
以下、図２４乃至図２７を参照して記載されるように、方法１００はアウトドア及びインドア環境に対して適合され得る。
【０１４２】
アウトドア環境は、典型的には、建造物や、歩道、道路、並びに、川によって分離された、市場スペース、木々を伴う公園等のオープン・スペースから構成される。対応して、平面図生成器はナビゲーション・メッシュ内において複数の穴を切り抜くべく外部建造物を用いる。
【０１４３】
可動エンティティに異なる種類御到着可能な空間の間を区別させるために、ブラインド・データが用いられて、到着可能空間の異なる部分を特徴付ける。ある種の適用において、ブラインド・データはナビゲーション・メッシュのセルと関連され得て、ナビゲーション表面における相違を特定し（例えば、道路及び歩道）、そしてエンティティにそれに応じたナビゲートを為させる（例えば、道路上の車両や歩道上の人を保持）。
【０１４４】
図２４は市街道路の形態のディジタル・ワールドを図示している。図２５は、方法１００のステップ１０４から獲得されるナビゲーション・メッシュを図示している。ブラインド・データが使用されて、車道（白色セル）及び歩道（灰色セル）の間の区別をする。
【０１４５】
図２６に図示されているように、インドア環境は、典型的には多数層であり、内壁及びドアを介して複数の部屋に分割され、階段によって連結されたフロアから構成される。対応して、平面図生成器はバリヤーとしての壁を用いて各フロアに対するナビゲーション・メッシュを計算し、次いで複数のナビゲーション表面は階段と対応するセルによってリンクする。これは３Ｄナビゲーション・メッシュを生じ、そこで、セルは相互に上部になり得る。経路見出しは変更されて、キャラクタが中にあるセルよりもむしろ、ディジタル可動エンティティが乗っている表面セルを決定する。手短には、３次元ワールドが複数のレベルによって規定されると、ナビゲーション・メッシュが各レベルに対して作り出され、２つの連続したナビゲーション・メッシュが連結セルによって相互連結されている。
【０１４６】
図７そしてより明確にはステップ１１６に移れば、凸セル内において、方法１００は可動エンティティが所定媒介点から次の点まで一直線状に移動することを可能していることが思い出される。それ故に、エンティティが一直線状に進行することを防止出来る唯一のものは動的障害物であり得る。この状況に立ち向かうべく、可動エンティティにはセンサが設けられ得る。本発明の方法に従った動的衝突回避方法をより詳細に記載する前に、センサの概念や、データ情報、コマンド（命令）、決定、並びに、決定木等の他の関連概念が先ず簡単に記載される。しかしながら留意されるべきことは、本発明に従った衝突回避方法、或は、ナビゲーション方法１００の何れも、ディジタル可能エンティティに対するセンサ或は決定規則の特定実施例に限定されると解釈されるべきではない。
【０１４７】
（データ情報）
エンティティ・データ情報はその内部メモリとして考えられる。各データはエンティティの内部メモリ内に記憶された情報の要素である。例えば、データは敵が目撃された否か、誰が最も弱い協力者であるか等々の情報を保持し得る。データはＩＥに対する状態変数としても使用され得る。
【０１４８】
データはエンティティ・センサによって或はコマンドによって決定木内に書き込まれる。データの値は決定木によって使用されて、振る舞い及びアニメーション起動及び起動解除するか、或は、エンティティの状態を試験する。センサ及び決定木は以下により詳細に記載される。
【０１４９】
（センサ）
エンティティはセンサを用いて、ワールドについての情報を得る。センサはその検知した情報をエンティティに属するデータ内に記憶する。
【０１５０】
パラメータが使用され得て、センサの起動をトリガーする。もしセンサがオフに設定されれば、それはソルバーによって無視されて、情報を任意のデータ内に記憶しない。
【０１５１】
以下、センサの例がより詳細に記載される。勿論、当業者が理解できる範囲内であって、その適用例に応じて追加或は代替のセンサを提供するものと思われる。
【０１５２】
「視覚センサ」
視覚センサはキャラクタの目及び耳であり、該キャラクタが仮想ワールド内において他の物理的オブジェクト或は可動エンティティを検知することを可能とし、それらは、例えば、自発性或は非自発性のキャラクタ、バリヤー、並びに、中間点であり得る。
【０１５３】
以下のパラメータは、例えば、視覚センサを規定することを可能としている：
【表１２】
【０１５４】
（コマンド（命令）、決定、並びに、決定木）
決定木はセンサを用いて集められたデータ情報を処理すべく使用される。
【０１５５】
コマンドは振る舞い或はアニメーションを起動すべく、或は、ＩＥ内部メモリを変更すべく使用される。
【０１５６】
コマンドは決定によって発動される。単一決定は、条件表現と発動すべきコマンドのリストとを含む。
【０１５７】
決定木はルート決定ノードを含み、それは子供決定ノードを所持することができる。それら子供の各々は、順次、それらの自体の子供を所持し、それら各々はより多くの子供を所持する等々である。
【０１５８】
決定木が評価されるべき否かを示すパラメータはその決定木を規定する点で使用可能である。
【０１５９】
コマンドがアニメーションを起動することと対応して、遷移が現行アニメーション及び新アニメーションの間で規定されると、その遷移が先ず起動される。
【０１６０】
同様に、コマンドが振る舞いを起動することと対応すると常に、混合時間が現行アニメーション及び新アニメーションの間に提供され得る。
【０１６１】
更には、コマンドが振る舞いの起動と対応すると常に、目標はデータによって特定されたオブジェクトに変更される。
【０１６２】
（動的衝突回避）
以下に記載されることは、方法１００でのステップ１１０及び１１６の双方の部分集合が、ステップ１０２乃至１１４を通じて決定された経路に沿って移動するに伴って、エンティティが任意の動いている障害物（例えば、別のキャラクタ或は物理学過程オブジェクト）にぶつかることを回避させることができることである。
【０１６３】
単に経路見出しは、２ステップ処理として見られる、即ち、：i）その経路を決定すること、そして次いでii）それに追従することであり；障害物回避は図２８に図示される２ステップ方法２００としても見られる、即ち、：
２０２-可動ディジタル・エンティティ及び動いている障害物の間の可能性ある衝突の脅威を評価又は見積もり、そして、
２０４-もしそうした脅威があれば、可動ディジタル・エンティティはその動いている障害物を回避すべく戦略を採用することによってそれに応じた応答を為す。
【０１６４】
「衝突脅威評価」
ステップ２０２で、各エンティティ７２はそのセンサ（図２９を参照）を用いて、その近辺内にはどのような可能性ある障害物があるかを検出し、それら障害物の内のどれが衝突の最も大きな脅威を提示しているか決定する。図３０に図示されているように、センサは被写界深度によって特徴付けられるエンティティ７２を巡る視野７４として構成されて、そのエンティティがどの程度遠くまで見ることができるかを規定している。各可動エンティティの視界は該エンティティを取り囲むパイ（或はその適用例に応じた球）として規定され得る。
【０１６５】
もし障害物が全くなければ、エンティティ自体の周りのエンティティ視界７４は完全に自由であり、パイは完全である。しかしながら図３０に図示されているように、各障害物はこのパイの一片を除去する。その除去された一片のサイズは障害物サイズ及びエンティティからの距離に依存する。
【０１６６】
パイの妨げられていない区分を、ここでは、穴７６乃至７８として言及する（図３１参照）。エンティティ７２は最良穴を捜し求めて持続する。
【０１６７】
最良穴は幾つかの方法で決定され得る。典型的な方法は以下の如くである：
・穴７６乃至７８はエンティティ７２の所望方向からの増大する半径距離の順に区分けされる。
・エンティティが通過するに充分に大きな第１穴が選択される。
・もし穴がなければ、エージェントが完全に阻止され移動を停止する。
【０１６８】
選択された穴に依存して可動エンティティは旋回或は逆転の何れかによってその穴に入り込むことができる。
【０１６９】
シミュレータの適用例やエンティティの特性に依存して、障害物は異なる回避重要性を有するものとして特徴付けられる。例えばハンビィー(Hummvee)は、その最高優先順位として他の車両、第２優先順位としての歩行者、非常に低い優先順としての犬等の小動物を、回避することを考え；一般歩行者はその最高優先順位としての車両、及び、第２優先順位としての他の歩行者を考える。勿論、暴動等の極端な状況はこれら優先順位を動的に変え得る。よって、異なる障害物グループは異なる回避制約を有する。最も基本的な制約は障害物に脅威であると割り当てることである。従って、各障害物グループに対して、関連された認識半径がある。キャラクタがそのワールドを通じて移動すると共に、その周りを掃引し、そのセンサはその認識半径以内であるその掃引で検出された障害物毎に、潜在的な衝突脅威としてフラグが立てられる。
【０１７０】
各知覚脅威に対して、衝突脅威状態の異なる種類が割りあてられ、以下を含む：
・静止状態：障害物が移動しないが、可動エンティティの進路内にある。
・到着：障害物が可動エンティティに向かって来る。
・出発：障害物が可動エンティティから遠ざかるように進行するが、該エンティティはそれに追突する。
・側方強打：障害物は可動エンティティと側方から衝突すると予想される。
【０１７１】
「回避戦略」
各衝突脅威に対して、２種類の回避戦略がある（ステップ２０４）：
・迂回：障害物を周回することで衝突を回避しようとする。
・待機：障害物がその衝突経路をでるまでスローダウン（そして、潜在的には停止）することで衝突を回避しようとする。
【０１７２】
留意されるべきことは、両方の上記下回避戦略は経験則であり、どちらの場合も全ての状況内で作業すべく保証されている。
【０１７３】
図３２Ａ乃至図３２Ｃ、図３３Ａ乃至図３３Ｃ、図３４Ａ乃至図３４Ｃ、並びに、図３５Ａ乃至図３５Ｃは、衝突脅威の３つの例（図３２Ａ、図３３Ａ、図３４Ａ、並びに、図３５Ａ）を図示し、各々が双方の対応する回避戦略を伴う。図３２Ａ乃至図３５Ｃは、迂回が静止状態の障害物を周回するため、そして、到着障害物の進路から外にでるためにどの程度有用であるかを示している。しかしながらそれは、出発障害物に対して多数の押しのけを生じ得る。それにもかかわらず、迂回は交通渋滞を最小化して、最終的には逃げ道を見出すと云う長所を有する。
【０１７４】
待機は、常に、出発障害物及び到着障害物に対して充分に働きかける（もしそれらが迂回しようとするならば）。しかしながら見出されたことは、待機到着障害物及び静止状態障害物は交通渋滞を引き起こし得る。殆どの場合、交通状態を回避する最も効果的な方法は飛行に対する戦略を変えるべく決定論理を使用することである。
【０１７５】
（グループに基づく動作変更器（編隊））
充分観測された事実は、鳥、魚、人を含む群れに基づく動物はグループとなって異なって移動することである。この移動振る舞いは群がりと一般には呼称される。人によって、グループに基づく移動は、曲がりくねった市街道路を走り抜くソマリア民兵の自由なグループから、現代のデルタフォース・オペレータの調整されたカバー及び掃引ルーチンへのパレードで兵隊を行進させる固定した編隊まで非常に変化に富んでいる。各場合において、グループの集合的良心はそのグループ内の各誘導個人の行動に影響する。
【０１７６】
コンピュータ・グラフィック人工知能によって最も迅速に識別されるグループ移動変更器は群がりであり、超粒子としてボイドと呼称された鳥の群れをモデル化したレイノルズ［レイノルズ、１９８７年］によって有名と為された。レイノルズは群がりへの３つの基本要素を識別した：
・整列：グループ・メンバー自身を同一速度で同一方向に整列することによってそれらの運動を調和するグループ・メンバーの傾向；
・分離：グループ・メンバー間の特定量の空間を維持すべく該グループ・メンバーの傾向；そして、
・参加：相互に対する特定の近接性を維持すべくグループ・メンバーの傾向。
【０１７７】
次に友人のグループが道路を歩いていることを考えると、グループの内のより遅いメンバーが他のメンバーに追いつくべく速度を上げると、最も速いメンバー（彼等が丁重であることを仮定）は速度を僅かに落として落伍者が追いつくことを可能としている。そのグループの教養経歴に依存して、多少の空間がそれら友人の間に要求されるか或は誂えられる（都市住人から地方住人）。
【０１７８】
図３６Ａ乃至図３６Ｆは、先導キャラクタに追従する５つのキャラクタから成るグループに対する異なる群がり戦略の効果を示している。
【０１７９】
そうしたグループに基づく変更器が使用され得て、方法１００が使用されて始点及び終点の間におけるディジタル・ワールド内においてエンティティから成るグループを同時に移動させる際、より自然な効果をもたらす。
【０１８０】
ディジタル・ワールド内において、始点から終点まで画面上のディジタル・エンティティを移動する方法及びシステムが、３Ｄ適用例の特定例示実施例に含まれるとして記載されているが、画像要素の画面上での自発性変位を要求する任意の３Ｄ適用例に含ませることができる。例えば、本発明に従ったナビゲーション方法が使用され得て、先に記載されたような振る舞いで特徴付けられないディジタル・エンティティを移動させる。
【０１８１】
本発明に従ったナビゲーション方法が使用され得て、任意の数のエンティティを誘導し、そしてディジタル・ワールドの任意のタイプ或は構成に限定されない。本方法及びシステムが使用され得て、仮想ワールド内における可動オブジェクト或はエンティティの変位をそれらオブジェクト或はエンティティの更なる移動無しに計画する。
【０１８２】
本発明がその好適実施例によって以上に説明されたが、添付の特許請求の範囲で規定されたように、本発明の精神及び本質から逸脱することなしに変更され得る。
【図面の簡単な説明】
【０１８３】
【図１】図１は、「先行技術」として明示された、包括的な３次元（３Ｄ）適用例の第１レベルを図示するブロック線図である。
【図２】図２は、「先行技術」として明示された、図１の包括的な３次元（３Ｄ）適用例における第２レベルを図示するブロック線図である。
【図３】図３は、「先行技術」として明示された、図２のブロック線図の拡張図である。
【図４】図４は、「先行技術」として明示された、図１の包括的な３次元（３Ｄ）適用例から図１の包括的な３Ｄ適用例の画像生成器部までのデータの流れを図示するフローチャートである。
【図５】図５は、「先行技術」として明示された、ディジタル・ワールド内においてディジタル・エンティティをナビゲートすべく中間地点の使用を図示する線図である。
【図６】図６は、本発明の例示実施例に従った、ディジタル・ワールドにおいて始点から終点までディジタル・エンティティを画面上で移動させるシステムを実施するナビゲーション・モジュールを含むディジタル・エンティティの画面上でのアニメーションを図示するブロック線図である。
【図７】図７は、本発明の例示実施例に従った、ディジタル・ワールドにおいて始点から終点までディジタル・エンティティを画面上で移動させる方法を図示するフローチャートである。
【図８】図８は、図７の方法と一緒に用いられる２次元バリヤーを図示する概略図である。
【図９】図９は、図７の方法と一緒に用いられる３次元バリヤーを図示する概略図である。
【図１０】図１０は、図７の方法と一緒に用いられる対等システムを図示する概略図である。
【図１１】図１１は、図７の方法に従った、特定のディジタル・エンティティに対する到達可能な空間の第１例に従った、１フロア建造物の形態での２次元ワールドの概略上面図である。
【図１２】図１２は、図７の方法を通じて作り出されたナビゲーション・メッシュを図示する図１１の１フロア建造物の概略上面図である。
【図１３】図１３は、図１２のナビゲーション・メッシュから獲得された接続性グラフの概略図である。
【図１４】図１４は、図７の方法に従った、特定の可動ディジタル・エンティティに対する到着可能な空間の第２例に従った２次元ワールドの概略上面図である。
【図１５】図１５は、図７の方法を通じて作り出されたナビゲーション・メッシュを図示する図１１のワールドの概略上面図である。
【図１６】図１６は、図７の方法の各種ステップを図示する、図１５と類似の概略上面図である。
【図１７】図１７は、図７の方法から生ずる経路を図示している、図１５と類似の概略上面図である。
【図１８】図１８は、第１通路の遮断から生ずる図１７に図示された経路に対する第１代替経路を図示している、図１７と類似の概略上面図である。
【図１９】図１９は、第２通路の遮断から生ずる図１７及び図１８に図示された経路に対する第２代替経路を図示している、図１８と類似の概略上面図である。
【図２０】図２０は、新しい始点から終点までで生ずる図１７に図示された経路に対する第３代替経路を図示している、図１７と類似の概略上面図である。
【図２１】図２１は、可動ディジタル・エンティティの幅の２倍から生ずる図２０に図示された経路に対する代替経路を図示している、図２０と類似の概略上面図である。
【図２２】図２２は、シミュレータの小都市部に対する間取図生成器の斜視図である。
【図２３】図２３は、図７の方法を用いている図２２の間取図生成器から作り出されたナビゲーション・メッシュを図示する斜視図である。
【図２４】図２４は、市街道路の形態でのディジタル・ワールドの斜視図である。
【図２５】図２５は、結果として生ずるセルを特徴付けるブラインド・データの使用を含む、図７の方法に従ったナビゲーション・メッシュ・ステップを図示している、図２４の市街道路の斜視図である。
【図２６】図２６は、建造物の形態でのディジタル・ワールドの切り取られた斜視図である。
【図２７】図２７は、図７の方法を用いている図２６の建造物から生ずるナビゲーション・メッシュの斜視図である。
【図２８】図２８は、本発明の特定の例示的実施例に従った、ディジタル・ワールドにおえる始点から終点まで画面上を移動するディジタル・エンティティに対する衝突回避方法のフローチャートである。
【図２９】図２９は、本発明に従った、キャラクタ・センサを図示している、キャラクタの形態の３Ｄ適用例におけるエンティティの斜視図である。
【図３０】図３０は、本発明に従ったエンティティの視覚センサを図示しているディジタル・ワールド内のエンティティの上面図であって、該センサによって提供される視野をより明確に図示している上面図である。
【図３１】図３１は、図７の方法の特定の実施例に従った、障害物を回避する副経路の選択を図示している図３０と類似のディジタル・ワールド内のエンティティの斜視図である。
【図３２】図３２Ａ乃至図３２Ｃは、静止状態障害物（図３２Ａ）の場合、図７の方法の特定実施例に従った、可動ディジタル・エンティティによって使用され得る回避戦略（図３２Ｂ及び図３２Ｃ）を図示する概略図である。
【図３３】図３３Ａ乃至図３３Ｃは、到着障害物（図３３Ａ）の場合、図７の方法の特定実施例に従った、可動ディジタル・エンティティによって使用され得る回避戦略（図３３Ｂ及び図３３Ｃ）を図示する概略図である。
【図３４】図３４Ａ乃至図３４Ｃは、出発障害物（図３４Ａ）の場合、図７の方法の特定実施例に従った、可動ディジタル・エンティティによって使用され得る回避戦略（図３４Ｂ及び図３４Ｃ）を図示する概略図である。
【図３５】図３５Ａ乃至図３５Ｃは、側方強打障害物（図３５Ａ）の場合、図７の方法の特定実施例に従った、可動ディジタル・エンティティによって使用され得る回避戦略（図３５Ｂ及び図３５Ｃ）を図示する概略図である。
【図３６】図３６Ａ乃至図３６Ｅは、図７の方法を用いている５つの可動ディジタル・エンティティを同時に移動させる経路を図示し且つグループに基づく移動変更器を適用している概略図である。
【図３６Ａ】図３６Ａは、図７の方法を用いている５つの可動ディジタル・エンティティを同時に移動させる経路を図示し且つグループに基づく移動変更器を適用している概略図である。
【図３６Ｂ】図３６Ｂは、図７の方法を用いている５つの可動ディジタル・エンティティを同時に移動させる経路を図示し且つグループに基づく移動変更器を適用している概略図である。
【図３６Ｃ】図３６Ｃは、図７の方法を用いている５つの可動ディジタル・エンティティを同時に移動させる経路を図示し且つグループに基づく移動変更器を適用している概略図である。
【図３６Ｄ】図３６Ｄは、図７の方法を用いている５つの可動ディジタル・エンティティを同時に移動させる経路を図示し且つグループに基づく移動変更器を適用している概略図である。
【図３６Ｅ】図３６Ｅは、図７の方法を用いている５つの可動ディジタル・エンティティを同時に移動させる経路を図示し且つグループに基づく移動変更器を適用している概略図である。
【符号の説明】
【０１８４】
１０ コンピュータ・システム
１２ ナビゲーション・モジュール
１４ シミュレータ
１６ ワールド・データベース（ＷＤＢ）
１８ 画像生成器
２０，２２ モジュール
１００ 方法
【技術分野】
【０００１】
本発明はディジタル・エンターテイメント産業及びコンピュータ・シミュレーションに関する。より詳細には、本発明はディジタル・オブジェクト或はキャラクタの画面上でのナビゲーションに対する方法及びシステムに関する。
【背景技術】
【０００２】
多年来、３次元（３Ｄ）コンピュータ・グラフィックは、映画アニメーション、ディジタル効果、ゲーム、並びに、シミュレーションを含む多くの適用例を有する充分に確立された分野である。
【０００３】
添付図面内の図１は、例えば、アニメーション・パッケージ、ビデオ／コンピュータ・ゲーム、トレイナー、或は、シミュレータの形態であり得る先行技術からの包括的な３Ｄ適用例を図示する。この３Ｄ適用例はオブジェクトの基本的には高いレベル・アーキテクチャを共有し、それらオブジェクトはディジタル・エンティティとしてより一般的には言及され得るものであり、入力装置を介したコントローラによって、或は、物理学過程及び人工知能（ＡＩ）システムによって操作され、ビジュアル・レンダリング及びオーディオを含む合成器によってユーザにとって実感が沸くようにしている。
【０００４】
ワン・レベル・ディパー、３Ｄ適用例は典型的には、シミュレータ及び画像発生器の２つの構成要素に崩壊させられる。図２及び図３に図示されているように、シミュレータは人オペレータ及びＣＧＥの双方から数多くの入力を取り入れており、次いで該シミュレータはそれ従ってワールド・データベースを変更して、変化を可視化のために画像発生器に出力する。
【０００５】
典型的なシミュレータ／アニメーション・ループ構造は図４に図示されている。ワールド状態マネージャはワールド・データベースから初期データを先ず積み込む。シミュレーションの各フレーム／チックに対して、ワールド状態マネージャはコントローラを更新し、該コントローラはそれ従って行動し、オブジェクト更新をマネージャに送り戻す。次いでワールド状態マネージャは全てのオブジェクト更新をワールド・データベース（ＷＤＶ）における新ワールド状態内に分解し、それを画像発生器（ＩＧ）に渡す。このＩＧはキャラクタ・ボディ肢位置や他のオブジェクトを更新して、それらを画面に提供する。
【０００６】
最近になって、物理的過程及び人工知能（ＡＩ）技術によって駆動される手続き上のアニメーションは３Ｄアニメーション、ビジュアル効果、並びに、ゲームの分野に導入された。ＡＩアニメーションは、訓練にわたってディジタル・エンターテイナー及びシミュレータの能力を増大することを可能とする。それはゲーム・デザイナー及びシミュレータにフィルム・アクタの幅、独立性、並びに、戦法を付与する。映画制作者はゲーム・キャラクタの一時的パフォーマンスやシミュレーション・エンティティの行動現実性を得ている。
【０００７】
２０年にわたって、映画撮影所のビジュアル効果部門は、コンピュータを介して以外の他の任意の方法を作り出すことは高価過ぎ、危険過ぎるか或は不可能であるときは常に、コンピュータ・グラフィックに益々依存してきた。驚くことなく、より見事で現実的なビジュアル効果を作り出すアニメータの芸術的な才能に対する需要も増大してきた。コンピュータ・アニメーション・チームが主演男優として映画の成功に重要であることは、現行珍しくない。
【０００８】
大群衆場面、特に戦闘場面はコンピュータ・グラフィック技術にとって理想的な候補であり、その理由は、要求される非常に多くのエキストラがそれら場面を極端に高価となし、それらの暴力的特徴が非常に危険となし、そして野獣戦士が実行不可能となし、もし不可能であれば、人のエキストラで撮影することになる。もし、そうした場面の複雑性、費用、危険性が付与されれば、効果的な人工知能（ＡＩ）アニメーション解決策がそうした戦闘を現実の人の俳優で実際に上演し撮影することがより好ましいことは明かである。しかしながら、ディジタルの群衆場面を発生する実用的で商業的な方法に対する明かな必要性にもかかわらず、満足な解決策は実現するには時間がかかった。
【０００９】
アリアス システム(Alias Systems)によるマヤ(Maya)（商標）等の商業的アニメーション・パッケージはここ２０年で、実質上、全ての３Ｄの制作スタジオがそれらに依存してそれらの制作パイプラインの基礎を形成した点まで大きな進歩を遂げた。それらのパッケージは特殊な効果や個々別々のキャラクタを作成する点で優れている。しかしながら、自動／群衆アニメーションは依然として重大な問題である。
【００１０】
コンピュータ・ゲーム分野において、１９７０代にビデオ・ゲームの幕開け以来、ゲームＡＩは存在していた。しかしながら、それはポン(Pong)（商標）及びパックマン(Pac-Man)（商標）の創造以来、長い道のりであった。今日、ゲームＡＩはゲームの成功にとって益々決定的要因となり、ゲーム開発者はそれらＡＩからより多くのものを要求している。今日のＡＩは、外見上、自身で考えて、それらの環境や経験に従って行動して、知的振る舞いの印象を付与する、即ち、それらは自主的である必要がある。
【００１１】
ゲームＡＩはゲームをより夢中にさせる。典型的には、ゲームＡＩは以下の状況で使用される。
・知的非プレーヤ・キャラクタ（ＮＰＣ）を作成すること、それはそのプレーヤ制御キャラクタに対する味方或は敵であり得る；
・ワールドに現実性を付加すること。変化するゲーム・ワールドに反応する何等かの非ゲーム遊技関連ゲームＡＩを単に付加することは、現実性を増大し、ゲーム経験を向上する。例えば、ＡＩはスポーツ競技場をアニメ観客で一杯にすべく或はコウモリ群を地下牢場面に付加すべく使用され得る；
・何もなければ、対戦相手を作成すること。多くのゲームは二人或はそれ以上のプレーヤ用に設計されているが、もし対抗してプレイすべき者がいなければ、知的ＡＩ対戦相手が必要とされる；或は
・チーム・メンバーが充分でなければチーム・メンバーを作成すること。ある種のゲームはチーム・プレイを要求し、ゲームＡＩは充分なプレーヤがいなければその欠員を満たすことができる。
【００１２】
（例えば、３Ｄ都市内で相互作用出来る車両及び人々等の）リアルタイム知的３Ｄエージェントに対する別のアプリケーションは軍隊シミュレーション、訓練（ＭＳ＆Ｔ）、並びに、より詳細にはミリタリー・オペレーション（軍事行動）・アーバン・テレイン(MOUR: Military Operation Urban Terrain)である。実際上、西欧軍隊を含む最近１５年内の全ての闘争は、事実上、都市（モガディシュ、ボスニア、並びに、イラク）であった。それにもかかわらず、複雑な都市地勢におけるリアルタイムの群衆シミュレーションは数の多さの理由のために無視された：
・最近までハードウェアは単純は充分に強力ではなかった；
・陸軍は変化を承認すべく非常に緩慢に移動し、それで彼等は必要に応じてそれを強調すべく対応して緩慢である；そして
アプリケーション開発者は機械シミュレーションより非常により難しいために人のシミュレーションを回避してきた。
【００１３】
人工知能の役割は、戦闘、交戦国（青及び赤の軍隊）、並びに、増大する一般市民（緑の軍隊）における人々（地上部隊ばかりではなく、車両のドライバをも）をシミュレートする。ＭＳ＆Ｔの文脈において、それらはしばしばコンピュータ生成軍隊（ＣＧＦ）或は半自動軍隊（ＳＡＦ）と呼称される。可能性あるシミュレートされたエージェントのタイプは以下に記載される。
【００１４】
車両ドライバ及びパイロット：車両は物理学過程で非常に複雑なモデルを有し（例えば、回転に傾きそして戦車は溝に飛び込むと跳ね返るように、ヘリコプターは現実的に揺動する）、そして、武器／通信システム（例えば、視線方向無線通信は丘を通して働かない）、それらはＭＯＵＴ（例えば、ヘリコプターが超高層周りよりもむしろ超高層を真っ直ぐ通じて飛び、そして戦車は当惑して第３ワールドの曲がりくねった廃物が満ちた道にはまり込んで抜け出せない）の３Ｄ具体的峡谷に入る単純な視線方向ナビゲーション・システムを有する傾向がある。ＡＩが使用されて得て、車両における人のドライバの頭脳をシミュレートする（実際のボディがシミュレートされると共に、或は、それがシミュレートされずに）。
【００１５】
個々別々の教義上の交戦国から成る群：ＵＳ軍事施設のみに限定されると共に都市環境において適切にナビゲート出来ないので、それらの有用性がＭＳ＆Ｔ適用例に限定されているので、個々別々の教義上の交戦国から成る群の合衆国政府作成ＳＡＦ。集合体ＳＡＦが戦略レベルでそしてしばしば難解レベルで軍事行動する一方で、個々別々の交戦国シミュレータは戦略レベルでそしてしばしば３Ｄ物理的レベルで軍事行動する。
【００１６】
個々別々の不規則な交戦国：定義によって、民兵及びテロリスト等の不規則な交戦国は非教義的であり、それ故にそれらの個性や戦略を従来のＳＡＦアーキテクチャで表現することは難しい。
【００１７】
個々別々の非交戦国（混雑）から成る群：ＭＯＵＴの最も困難な制限の内の１つは、非交戦国で占有された環境下で軍隊軍事行動をどのように実行させるかである。それら大きな一般市民は作戦上の「クラッター」としてだけ行動することによって任務に影響して戦闘の成り行きに実際に影響する。
【００１８】
ゲームＡＩ及びＭＳ＆Ｔのより特有の局面の内の１つは、エージェント自体のリアルタイム知的ナビゲーションであり、例えば、群衆シミュレーションの状況下でのエージェント自体のリアルタイム知的ナビゲーションである。
【００１９】
コンピュータ・グラフィック群衆シミュレーションは、非特許文献１でのＣ．Ｗ．レイノルズ(Reynolds)によって開拓された。レイノルズは動作は知性の基本的目標であり、知的キャラクタ自体は単純な車両モデルで表現可能であると云う核となる着想を確立した。このシステムは単純な「集団」振る舞いを作り出す点で極端に有効であり、且つ、映画特殊効果等の非リアルタイム適用例におけるコウモリ及び鳥等の動物のシミュレーションにおける大いなる成功を伴って使用されてきた。
【００２０】
非特許文献２のミューゼ(Musse)及びタルマン(Thalmann)は、ヴィクラウド(ViCrowd)と呼称されるリアルタイム群衆シミュレーションに対する階層モデルを開発し、その中で、人は個々別々でばかりではなくグループ・レベルで制御される。
【００２１】
粒子系として群衆を表現し且つクレバー・プレ-コンピュータ・アルファ-チャネル・レンダリング技術を用いることによって、テチアル等(Tecchial et al.)（Ｔｅｃｃｈｉａｌ Ｆ． Ｌｏｓｃｏｓ Ｃ．，Ｃｈｒｙｓａｎｔｈｏｕ Ｙ．の非特許文献３）は、ＰＣ上の疑似リアルタイムにおける非常に単純な製粉群の多数をシミュレート及びレンダリングする点で成功している。しかしながら、群衆は刺激に反応出来なかった。
【００２２】
リース(Reece)は分解歩兵半自動軍隊（ＤＩＳＡＦ）システム（非特許文献４を参照）内で群衆をモデル化するシステムを開発した。
【００２３】
スング等(Sung et al.)は、著者が群衆の振る舞いに対する情報をワールド幾何形状に直に描き出すことを可能とすることによって、知的粒子としての群衆メンバーの概念を詳しく説明する。この著者最適化は群衆メンバーを製粉からパニック（非特許文献５を参照）までの遷移等の変更された振る舞い間の動的な変化に限定している。
【００２４】
動作は、二足歩行、車輪で動く、牽引、或は、航空のいずれであれ、あるシミュレーション内での全エンティティの基礎となっている。それ故に、ＡＩシステムは点Ｘから点Ｙまで現実的にエンティティが誘導（ナビゲート）をすることを可能としている。例えば、車両に対して、これが意味することは、通常動作において、道路上でのドライビングや、車線で停止且つ信号機で停止等の交通規則に従うこと、そして、軍事活動においては、道路上の障害物を回避し、民間見物人を越えないようにしていることである。民兵に対してこれが意味することは、通常動作において、目立たないように歩道を歩くことであるが、軍事活動においては建造物内に迅速に駆け込んで、その階段を駆け上がって、ＲＰＧを開始すべく屋上に駆け上ることである。知的ナビゲーションは２つの基本レベルに分裂させられ得る：ＸからＹまでの経路を動的に見出して、その経路に沿っての動的障害を回避することである。
【００２５】
エージェント・ナビゲーションの一例は以下の予め決定された経路（例えば、パトロール経路上のガード）である。そうした予め決定された経路は、ディジタル・キャラクタが従うように指示され得る中間地点から成る順序集合である。例えば、走路を巡る経路はトラックの曲がり角での中間地点から成る。経路追従は、その経路上に最も近い中間地点を捜し出すことからなり、直接的な視野方向によってそこまでナビゲートしてから、該経路上の次の点までナビゲートする。キャラクタは現行の中間地点（即ち、中間地点の境界球内）に到着すると次の中間地点を捜す。例えば、図５はキャラクタが特定の方法である領域をパトロールするように指示すべくどのように経路が使用され得るかを示している。
【００２６】
判明されたことは、ナビゲーション機構としての経路追従は、スタート及び目的地が知られるばかりではなく、その経路が明白に知られる際に充分に稼働することである。
【００２７】
しかしながらこれは規則と云うよりむしろ例外であり、通常はキャラクタにその目的地を知らせたく、そしてそれにそれ自体の経路を、それ自体の知識やそのワールドに基づき、障害物を巡るそれ自体の経路を見つけ出させたいからである。
【００２８】
しかしながらディジタル・ワールド内での画面上で始点から終了点までディジタル・エンティティを自動的に移動させる方法が望まれる。
【非特許文献１】Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ，２１（４）（ＳＩＧＧＲＡＰＨ ８７ Ｐｒｏｃｅｅｄｉｎｇｓ），２５−３４，１９８７での「Ｆｌｏｃｋｓ，Ｈｅｒｄｓ，ａｎｄ Ｓｃｈｏｏｌ：Ａ Ｄｉｓｔｒｉｂｕｔｅｄ Ｂｅｈａｖｉｏｕｒａｌ Ｍｏｄｅｌ」
【非特許文献２】ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ７，（Ｎｏ．２Ａｐｒ．−Ｊｕｎ．２００１），１５２−１６４における「Ｈｉｅｒａｒｃｈｉｃａｌ ｍｏｄｅｌ ｆｏｒ ｒｅａｌ ｔｉｍｅ ｓｉｍｕｌａｔｉｏｎ ｏｆ ｖｉｒｔｕａｌ ｈｕｍａｎ ｃｒｏｗｄｓ」
【非特許文献３】Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ Ｆｏｒｕｍ ２１：１， Ｅｕｒｏｇｒａｐｈｉｃｓ， ２００２における「Ｖｉｓｕａｌｉｚｉｎｇ ｃｒｏｗｄｓ ｉｎ Ｒｅａｌ-ｔｉｍｅ」
【非特許文献４】リース，Ｄ．Ａ．，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｅｌｅｖｅｎｔｈ Ｃｏｎｆｅｒｅｃｅ ｏｎ ａｎｄ Ｂｅｈａｖｉｏｒ Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ （Ｏｒｌａｎｄ，ＦＬ，Ｍａｙ ７−９，２００２），８７−９５
【非特許文献５】Ｓｕｎｇ，Ｍ．， Ｇｌｅｉｃｈｅｒ，Ｍ．， ａｎｄ Ｃｈｅｎｎｅｙ，Ｓ．のＣｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ Ｆｏｒｕｍ２３：３，Ｅｕｒｏｇｒａｐｈｉｃｓ，２００４における「Ｓｃａｌａｂｌｅ ｂｅｈａｖｉｏｒｓ ｆｏｒ Ｃｒｏｗｄ Ｓｉｍｕｌａｔｉｏｎ」
【発明の開示】
【発明が解決しようとする課題】
【００２９】
本発明の目的は、それ故に、ディジタル・ワールド内でのディジタル・エンティティに対する改善されたナビゲーション方法を提供することである。
【００３０】
本発明の他の目的は、始点から終点まで画面上のディジタル・エンティティを自動的に移動させる方法を提供することである。
【課題を解決するための手段】
【００３１】
より詳細には、本発明の第１局面に従えば、少なくとも１つのディジタル・エンティティを始点から終点まで画面上で移動するコンピュータ・システムにおける方法が提供され、該方法が、
i）ディジタル・ワールド内での少なくとも１つの可動ディジタル・エンティティに対する障害物の各位置を提供し；前記少なくとも１つの可動ディジタル・エンティティに対する到達可能な空間として障害物無しに前記ディジタル・ワールドの少なくとも複数の部分を規定する段階と、
ii）その到達可能な空間を少なくとも１つの凸セルに分割することによって少なくとも１つの可動ディジタル・エンティティに対するナビゲーション・メッシュを作り出す段階と、
iii）始点及び終点をそれぞれ含む前記少なくとも１つの凸セルの間に始セル及び終セルを配置する段階と、
iv）前記始セルが前記終セルと対応しているかを確認し；もし前記始セルが前記終セルと対応していれば、iv）ａ）前記少なくとも１つの可動ディジタル・エンティティを前記始点から前記終点まで移動させ；もし前記始セルが前記終セルと対応していなければ、iv）ｂ）i）前記始点セルから前記終点セルまでの前記少なくとも１つの凸セルの間に複数セルから成るシーケンスを決定し、そして、iv）ｂ）ii）複数セルから成る前記シーケンス内の連続したセルの間の各境界上に配置された少なくとも１つの媒介点を決定し、そして、iv）ｂ）iii）前記少なくとも１つの可動ディジタル・エンティティを前記始点から前記終点への各連続した前記少なくとも１つの媒介点まで移動させる段階と、
の諸段階を含む。
【００３２】
本発明の第２局面に従えば、ディジタル・ワールド内においてディジタル・エンティティを始点から終点まで画面上で移動するシステムが提供され、該システムが、
前記ディジタル・ワールドについての情報を記憶し且つ前記ディジタル・ワールド内での前記可動ディジタル・エンティティに対する障害物の各位置を提供するワールド・データベースと、
ナビゲーション・モジュールであり、
i）可動ディジタル・エンティティに対する到達可能な空間として障害物無しのディジタル・ワールドの少なくとも複数の一部を規定し、
ii）前記到達可能な空間を少なくとも１つの凸セルに分割することによって前記可動ディジタル・エンティティに対するナビゲーション・メッシュを作り出し、
iii）前記始点及び前記終点をそれぞれ含む少なくとも１つの凸セルの間に始セル及び終セルを配置し、
iv）前記始セルが前記終セルと対応しているかを確認し；もし前記始セルが前記終セルと対応していなければ、v）前記始セルから前記終セルまでの前記少なくとも１つの凸セルの間における複数セルから成るシーケンスを決定し、そして、vi）複数セルから成る前記シーケンス内の連続したセルの間の各境界上に配置された少なくとも１つの媒介点を決定することからナビゲーション・モジュールと、
前記ナビゲーション・モジュール及び前記ワールド・データベースに結合されたシミュレータであり、iv）で確認されたように、もし前記始セルが前記終セルと対応していれば前記始点から前記終点まで当該シミュレータと結合された画像生成器を介して画面上で前記ディジタル・エンティティを移動するか、或は、もし前記始セルが前記終セルと対応していなければ前記始点から前記終点への各連続した前記少なくとも１つ媒介点まで前記ディジタル・エンティティを移動することから成るシミュレータと、
を備える。
【００３３】
留意されるべきことは、表現「キャラクタ」は、ここでは、「エンティティ」として広義に解釈されるべきである。
【００３４】
本発明の他の目的、長所、並びに、特徴等は、添付図面を参照しての例証を前提すれば、好適実施例の以下の非制限的記載を読むことでより明かとなる。
【発明を実施するための最良の形態】
【００３５】
本発明の例示的実施例に従ったディジタル・ワールド内における始点から終点まで、ディジタル・エンティティを画面上で移動させる方法を実施するナビゲーション・モジュール１２を含むディジタル画像エンティティ（ＩＥ）の画面上でのアニメーションに対するシステム１０を、以下、図６を参照して記載される。
【００３６】
このシステム１０は、図２に図示されたもの等の従来の３Ｄ適用例と類似点を共有し且つ簡明性目的のため、システム１０と従来の３Ｄ適用例システムとの間の相違のみがここでより詳細に記載される。
【００３７】
システム１０は、シミュレータ１４、シミュレータ１４と結合されたワールド・データベース（ＷＤＢ）１６、ワールド・データベースＤＢ及びシミュレータ１４の双方と結合された複数の画像生成器（ＩＧ）１８（３つのみが示されている）、シミュレータ１４と結合されると共に本発明の例示的実施例に従ったナビゲーション・モジュール１２、シミュレータ１４とも結合された意思決定モジュール、各ＩＧ１８とそれぞれ結合された複数のアニメーション制御モジュールを備える。
【００３８】
ＩＧ１８の数は、勿論、適用例に依存して変動し得る。例えば、システム１０が３Ｄアニメーション適用例で実施されている場合、ＩＧ１８の数はレンダリング時間に影響し得る。
【００３９】
シミュレータ１４及びＩＧ１８は単一コンピュータの形態であり得る。ワールド・データベース１６は、限定されるわけではないが、ハード・ドライブ、対応するドライブ上で読み取られるＤＶＤ若しくはＣＤ-ＲＯＭディスク等の任意の適切なメモリ手段、或は、コンピュータ１４のランダム・アクセス・メモリ部に記憶させられる。
【００４０】
シミュレータ１４及びＩＧ１８は、以下により詳細に説明されることになる、動画化、シミュレート、或は、ゲーミングのための指示でプログラムされた、コンピュータ或は演算ユニットが具備された任意の演算器の形態である。
【００４１】
シミュレータ１４、ＩＧ１８、並びに、ＤＢ１６は、インターネット等のコンピュータ・ネットワーク（不図示）を介して遠隔的に結合され得る。
【００４２】
勿論、システム１０の適用例に依存して、シミュレータ１４はゲーム・エンジン或は３Ｄアニメーション・システム等の別の形態を採用し得る。
【００４３】
モジュール１２，２０，２２は、例えば、シミュレータ１４内でプログラムされたサブ-ルーチン或は専用指示の形態である。モジュール２０，２２及びの特性及び機能、そしてより詳細には、モジュール１２の特性及び機能は、本発明の例示的実施例に従った、ディジタル・ワールド内での始点から終点までディジタル・エンティティを画面上で移動させる方法１００の以下の非制限的記載を読むことでより明らかとなる。
【００４４】
図７に図示されている方法１００は以下のステップを含む：
１０２-ディジタル・ワールド内での可動ディジタル・エンティティに対する障害物の各位置を提供し、その可動ディジタル・エンティティに対する到着可能な空間としての障害物無しディジタル・ワールドの少なくとも部分を規定するステップと；
１０４-到着可能な空間を凸セルに分割することによって可動ディジタル・エンティティに対するナビゲーション・メッシュを作り出すステップと；
１０６-始点及び終点をそれぞれ含む凸セルの間に始セル及び終セルを配置するステップと；
１０８-始セルが終セルと対応するか否かを確認するステップと；
もし始セルが終セルと対応していれば：
１１０-ディジタル・エンティティを始点から終点まで移動させて、この方法を停止するステップと；
もし始セルが終セルと対応していなければ：
１１２-始セルから終セルまで凸セルの間の複数セルから成るシーケンスを決定する；
１１４-複数セルから成るそのシーケンス内の連続したセルの間の各境界上に配置された媒介点を決定するステップと；
１１６-ディジタル・エンティティを始点から終点への各連続した媒介点まで移動させるステップとである。
【００４５】
これらステップの各々は、以下に、より詳細に記載される。
【００４６】
ステップ１０２において、ディジタル・ワールド内の可動ディジタル・エンティティに対する障害物の各位置は、可動ディジタル・エンティティに対する到着可能空間としての障害物無しのディジタル・ワールドの部分を生ずるように規定される。到着可能空間はバリヤーによって閉鎖されたディジタル・ワールドの領域として規定されている。
【００４７】
留意されるべきことは、シミュレータ１４が特定の可動ディジタル・エンティティに対する障害物を考慮するものは、啓発することを可能とする以下に付与された更なる例として別のものに対する障害物ではあり得ないことである。
【００４８】
勿論、ディジタル・ワールドは、可動ディジタル・エンティティが相互作用する任意の自発性或は非自発性のエンティティを含んで、先行して規定され得る。ディジタル・ワールド及びディジタル・エンティティの概念は、以下、本発明の例示的実施例に従って記載される。
【００４９】
ディジタル・ワールド・モデルは画像オブジェクト要素を含む。これら画像オブジェクト要素は、オブジェクトや、自発性及び非自発性のキャラクタ、建造物、動物、木々等の２次元或は３次元（２Ｄ或は３Ｄ）のグラフィカル表現を含む。それはまたバリヤー、地勢、並びに、表面をも含む。以下の記載を読むことで明らかとなるように、方法１００を用いて移動されるように可動エンティティは自発性或は非自発性の何れかであり得る。自発性及び非自発性のキャラクタ及びオブジェクトの概念は、以下、より詳細に記載される。
【００５０】
当業界で共通して知られていると思われるように、オブジェクト及びキャラクタのグラフィカル表現は、コンピュータ画面上或は別のディスプレイ装置上に、表示され、動画化されるか或は否かであり得るが、ディスプレイ装置上への表示無しに仮想のワールド内において居住し相互に作用し合うことも可能である。
【００５１】
バリヤーは、壁、動いているドア、トンネル等、或は、ディジタル・ワールドにおける任意の可動エンティティに対する任意の障害物を構築すべく使用可能である三角形平面である。地勢は２Ｄ高度場であり、それにエンティティが自動的に支配され得る（例えば、兵士キャラクタが丘を越えて行進することを保持する）。表面は、自発性キャラクタが束縛されもする完全３Ｄ形状を形成すべく組み合わせられ得る三角形平面である。
【００５２】
組み合わせにおいて、これら要素はキャラクタが居住するワールドを記載すべく使用されるものである。それらはワールドＤＢ１６内に記憶される。
【００５３】
画像オブジェクト要素に加えて、ディジタル・ワールド・モデルは、自発性キャラクタ、及び、ディジタル・ワールドにおける他のオブジェクトを含んで、エンティティを管理することを可能とするソルバー（解答するもの）を含む。
【００５４】
ソルバーは３Ｄコンフィギュレーションを有し得て、エンティティに移動の完全な自由度を具備させるか、或は、２Ｄコンフィギュレーションは、計算上より効率的であり、アニメーション・システムの性能に影響すること無しに、オペレータがより多くの可動エンティティをスクリーン内に挿入させることを可能としている。
【００５５】
２Ｄソルバーは３Ｄソルバーよりも計算上より効率的であり、その理由はソルバーがエンティティの画像オブジェクト要素の垂直（ｙ）座標を考慮しないからである。２Ｄ及び３Ｄコンフィグレーションの間の選択は、可動エンティティ及び他のオブジェクトによって仮想のワールド内において許容されている移動に依存する。もしそれらが垂直平面内で移動しなければ、３Ｄ及び２Ｄのソルバーが使用可能なものに対する解決すべき要件がない。しかしながら、もし任意のエンティティが移動の完全な自由度を要求すれば、３Ｄソルバーが使用される。留意されるべきことは、２Ｄの選択が、２Ｄ或は３Ｄであり得る仮想ワールドの次元を限定しないことである。
【００５６】
非自発性キャラクタはディジタル・ワールド内のオブジェクトであり、それらがディジタル・ワールドと潜在的に相互作用し得るにもかかわらず、該ディジタル・ワールドはソルバーによって駆動されない。これらは従来の動画化キャラクタ（例えば、グループのリーダ）から、シミュレータの他の構成要素によって駆動される（例えば、飛び散る破片）オブジェクトへのプレーヤ・キャラクタまで変動し得る。
【００５７】
バリヤーは可動エンティティに対する障害物を表現すべく使用され、一方向壁と同等、即ち、ディジタル・ワールドに居住するオブジェクト或はディジタル・エンティティはそれら壁を一方方向であるが他方方向ではなく通過できる。バリヤーが作り出されると、スパイク（前方配向ベクトル）が使用されてオブジェクト或はエンティティによって検出され得る壁の一方面を指示する。それ故に、オブジェクト或はエンティティは非スパイク側からスパイク側まで通過出来るが、その逆は出来ない。留意されるべきことは、ある種の適用例において、特定の回避制約は規定可能であり且つディジタル・エンティティがディジタル・ワールド内のバリヤーを回避する試みを為すべく起動可能である。振る舞い及び制約の概念は、以下に、より詳細に記載される。
【００５８】
図８及び図９にそれぞれ図示されているように、バリヤーは線によって２Ｄソルバーで表現され且つ３Ｄソルバーで三角形で表現される。２Ｄ及び３Ｄバリヤーに対するスパイクの方向も図８及び図９に示されており（矢印２４及び２６参照）、Ｐ１乃至Ｐ３がバリヤーの複数点が描かれている順序を言及している。バリヤーは単指向性であるので、両面バリヤーは２つのバリヤーを重畳させて、それらスパイクを相互に対向させて設定することで作られている。
【００５９】
各バリヤーは以下のパラメータによって規定され得る：
【表１】
【００６０】
共通して知られているように、境界ボックスは３Ｄオブジェクトを封入して境界付ける直線的ボックスである。
【００６１】
ディジタル・ワールド・モデルのソルバーはサブ-ソルバーを含み得て、それらがシミュレーションを走らせるべく使用されるソルバーの様々なエンジンである。各サブ-ソルバーは、計算を最適化するために、オブジェクト及びシミュレーションの特定局面を管理する。
【００６２】
当業界で共通して知られているように、各動画化ディジタル・エンティティはアニメーション・クリップと関連されて、ディジタル・ワールド内での移動中のエンティティを表現することを可能としている。本発明の特定実施例に従えば、仮想センサは幾つかのエンティティに割り当てられ且つそれらによって使用されて、それらが画像オブジェクト要素或はディジタル・ワールド内の他のエンティティについてのデータ情報を集めることを可能としている。決定木をも、データ情報を処理するために使用され得て、アニメーション・サイクルの内の１つ選択及びトリガーするか或は新振る舞いを選択するようになる。
【００６３】
当業界で周知であると思われるように、ここでは「アニメーション・クリップ」としても言及されるアニメーション・サイクルは、典型的には繰り返され得るアニメーションの単位である。例えば、キャラクタを歩かせるために、アニメータは「ウォーク・サイクル」を作り出す。このウォーク・サイクルはキャラクタに１回の反復を行わせる。キャラクタをもっと歩かせるために、サイクルのより多くの反復が起用される。もしキャラクタが経時的にスピードアップ或はスローダウンすれば、サイクルはそれに応じて「スケールされ（増減され）」て、サイクル速度がキャラクタ変位と符合して、何等滑り（例えば、キャラクタが地面上を滑っているように見える）がない。
【００６４】
自発性画像エンティティは動画化エンジン（或はプラットフォーム）のノードを変換すべく密接されている。ノードは、ロケータ、キューブ、或は、動物のモデル、車両等の形態であり得る。アニメーション・クリップ及び変換ノードが当業界で周知であると思われるので、ここではそれらが以下で更に詳細に記載されない。
【００６５】
図１０はＩＥを移動させ且つソルバーによって使用される座標システムを示す。
【００６６】
可動ディジタル画像エンティティと関連され得る属性の例は以下の表２に簡潔に記載されている。
【表２】
【００６７】
勿論、他の属性もＩＥを特徴付けるべく使用され得る。
【００６８】
ＩＥ振る舞いの概念は、以下に、より詳細に記載される。
【００６９】
属性に加えて、本発明のＩＥは振る舞いによっても特徴付けられ得る。決定木と一緒に、振る舞いはＩＥの低レベル思考装置である。それらは仮想センサを用いてディジタル・ワールドから生データを受け取って、それを処理して、それに応じてＩＥの状態を変更する。
【００７０】
振る舞いは、例えば機関車振る舞いのように分類されて、ＩＥが移動することを可能としている。それら機関車振る舞いは、例えば、運動、速度、並びに、配向（即ち、ＩＥが対向する方向）のＩＥ方向の任意のもの或は全てのものに影響し得る操舵力を生成する。
【００７１】
下記の表３は振る舞い例を含む：
【表３】
【００７２】
機関車振る舞いはＩＥに作用する力として見られ得る。この力は振る舞い力であり、物理的（重力等）と類似して、力がＩＥ自体内から見えてくる相違を伴う。
【００７３】
留意されるべきことは、振る舞い力は加法的であり得る。例えば、自発性キャラクタは１つのアクティブ振る舞い以上を同時に有することができる。ソルバーは、振る舞いの優先順位及び強度に従って、構成要素振る舞い力を組み合わせことによってキャラクタの結果としての運動を計算する。結果としての振る舞い力はキャラクタに付与され、それがそれ自体の限界及び（キャラクタの旋回半径属性等によって特定される）制限を最終運動に対して強要し得る。
【００７４】
振る舞いはＩＥに対する広範な種類の作用を作り出すことを可能としている。振る舞いは４つのサブグループに分割可能であり：単純振る舞い、目標とされた振る舞い、並びに、グループ振る舞いである。
【００７５】
単純振る舞いは単一ＩＥを含むだけの振る舞いである。
【００７６】
目標とされた振る舞いはＩＥ及び目標オブジェクトに適用され、それらはディジタル・ワールド内の他の任意のオブジェクトであり得る（複数オブジェクトから成るグループを含む）。
【００７７】
グループ振る舞いはＩＥがグループとして行動し移動することを可能として、そこでは、そのグループに含まれた個々別々のＩＥが相互に略同一速度及び配向を維持している。
【００７８】
振る舞いの例は、以下に、４つの分類の各々に提供される。勿論、当業界の当業者においてＩＥに他の振る舞いを提供すると思われる。
【００７９】
（単純振る舞い）
「バリヤーの回避」
そのバリヤーの回避は、キャラクタがバリヤーとの衝突を回避させることを可能としている。
【００８０】
この振る舞いに固有のパラメータは、例えば、以下を含み得る：
【表４】
【００８１】
障害物回避振る舞いはＩＥが障害物との衝突を回避することを可能として、それは他の自発性及び非自発性の画像エンティティであり得る。そのバリヤー回避振る舞いに対するそうした詳細以外の類似パラメータもこの振る舞いを規定すべく使用され得る。
【００８２】
「での加速」
このでの加速振る舞いは、ＩＥを特定された量だけ加速することを試みる。例えば、もしその量が負値であれば、ＩＥはその特定された量だけ減速する。実際の加速／減速はＩＥの最大加速度及び最大減速度の属性で限定され得る。
【００８３】
この振る舞いに固有のパラメータは加速度であり、それはＩＥが維持しようとする速度（距離単位／フレーム２）における変化を表現する。
【００８４】
「での速度を維持」
このでの速度を維持振る舞いは、目標のＩＥの速度を特定の値に設定しようとするものである。これはキャラクタを静止に保持するか或は一定速度で移動させることを保持すべく使用され得る。もし所望速度がキャラクタの最大速度属性よりも大きければ、この振る舞いはキャラクタ速度をその最大速度と同等に維持しようとするだけである。同様に、もし所望速度がキャラクタの最小速度属性よりも小さければ、この振る舞いはキャラクタ速度をその最小速度に維持しようとする。
【００８５】
この振る舞いを規定することを可能とするパラメータは、キャラクタが維持しようとする所望速度（距離単位／フレーム）である。
【００８６】
「歩き回り」
歩き回り振る舞いはＩＥに無作為の操舵力を適用して、それがソルバー領域内において無作為風に移動することを保証する。
【００８７】
この振る舞いを規定することを可能とするパラメータは、例えば、以下の通りであり得る：
【表５】
【００８８】
「に配向」
このに配向振る舞いはＩＥが特定方向に対向しようとすることを可能としている。
【００８９】
この振る舞いを規定することを可能とするパラメータは以下の通りである：
【表６】
【００９０】
（目標とされた振る舞い）
以下の振る舞いはＩＥ（ソース）及びそのワールド内の別のオブジェクト（目標）に適用される。目標オブジェクトは、自発性或は非自発性の画像エンティティ、経路、グループ、並びに、データ等のワールド内における任意のオブジェクトであり得る。もし目標がグループであれば、振る舞いは任意時のグループの最も近いメンバーにだけ適用される。もし目標がデータであれば、そのデータはタイプＩＤであって、振る舞いの真の目標を目指していることが仮定される。ＩＤはワールド内のオブジェクトを一意に識別すべく使用される値である。このデータの概念は、以下に、より詳細に記載されている。
【００９１】
全ての目標とされている振る舞いによって共有されたパラメータは以下の通りである：
【表７】
【００９２】
「捜し求める」
この捜し求める振る舞いは、ＩＥが、別のＩＥに向かって、或は、複数のＩＥから成るグループに向かって移動することを可能としている。もしＩＥがグループを希求すれば、それは任意時にそのグループの最も近いメンバーを求める。勿論、捜し求める振る舞いはナビゲーション方法１００に従ってプログラムされ得る。
【００９３】
この振る舞いを規定することを可能とするパラメータは、例えば、以下の通りである：
【表８】
【００９４】
「から逃走」
振る舞いからの逃走はＩＥが別のＩＥから逃走すること或は複数のＩＥから成るグループから逃走することを可能としている。ＩＥがグループから逃走すると、随時、そのグループの最も近いメンバーから逃走する。振る舞いからの逃走は前記捜し求める振る舞いと同一の属性を有するが、対抗する操舵力を作り出す。振る舞いからの逃走を規定することを可能とするパラメータが前記捜し求める振る舞いのものと非常に類似しているので、それは、以下に、より詳細に記載されない。
【００９５】
「を見る」
このを見る振る舞いは、ＩＥが別のＩＥ或は複数のＩＥから成るグループと対面することを可能としている。もしこの振る舞いの目標がグループであれば、ＩＥはそのグループの内の最も近いメンバーを見ようとする。
【００９６】
「機銃掃射」
機銃掃射振る舞いは、ＩＥにその目標の周りを回るようにしており、言い換えれば、その目標へのその視線と直交する方向に移動させるようにしている。可能性パラメータは、ＩＥが旋回し他の方向で軌道を周り始めることの各フレームでそれがどの程度あり得るかを決定することが可能である。これは、例えば、蛾に炎の周りを回させるべく使用され得る。
【００９７】
例えば、その目標を見るか或はシュートすることが、ガードの前方運動だけ固有性をターン・オフして、ガードの目標に向けて設定された前記を見る振る舞いを付加することによって達成され得る。留意されるべきことは、これを為すべく、機銃掃射は方向だけに影響すべく設定され、しかるに前記を見るは配向だけに影響すべく設定される。
【００９８】
この振る舞いに特有であるパラメータは、例えば、可能性であり、それはＩＥが軌道の方向をどの程度頻繁に変えるかを決定する０及び１の間の値をとり得る。例えば、毎秒２４フレームで、０．０４の値が平均病後とに無作為方向変化をトリガーし、しかるに０．０１の値は平均４秒毎に変化をトリガーする。
【００９９】
「仲介者」
この仲介者振る舞いはＩＥが第１目標と第２目標との間に入り込むことを可能としている。例えば、この振る舞いは、ボディガード・キャラクタに複数の敵から成るグループからキャラクタを保護させることをイネーブルすべく使用され得る。
【０１００】
以下のパラメータはこの振る舞いを特定することを可能とし、それはエンティティが向かうことが望まれる第２目標にどの程度接近しているかを決定する０及び１の間の値を採り得る。
【０１０１】
「追従経路」
この追従経路振る舞いはＩＥが経路を追従することを可能としている。例えば、この振る舞いはレーシングカーが走路を巡って移動することをイネーブルすべく使用され得る。
【０１０２】
以下のパラメータはこの振る舞いを規定することを可能としている：
【表９】
【０１０３】
（グループ振る舞い）
グループ振る舞いは、個々別々のＩＥをグループ化して、それらが個性を維持しながらグループとして行動するように為すことを可能としている。例としては、魚の群れ、小鳥の群れ等々を含む。
【０１０４】
以下のパラメータはグループ振る舞いを規定すべく使用され得る：
【表１０】
【０１０５】
以下はグループ振る舞いの例の簡単な説明を含む。
【０１０６】
「整列」
この整列振る舞いは、ＩＥがグループの他のメンバーと同一の配向及び速度を維持することを可能としている。ＩＥはそのグループの１メンバーであり得るか或はあり得ない。
【０１０７】
「参加」
この参加振る舞いは、ＩＥがグループのメンバーと密に止まることを可能としている。このＩＥはそのグループの１メンバーであり得るか或はあり得ない。
【０１０８】
この振る舞いを規定すべく使用可能なパラメータの例は参加距離であり、それは目標とされた振る舞いにおける「接触半径」と類似する。近隣半径及びその参加距離外側の内部におけるグループの各メンバーは、振る舞いの操舵力を計算する際に考慮される。参加距離はキャラクタ間の外部距離である（即ち、キャラクタの境界球の外側の間における距離である）。このパラメータの値は、そのグループのメンバが維持しようとする密接性を決定する。
【０１０９】
「から分離」
このから分離振る舞いは、ＩＥがグループのメンバーから遠ざかる特定の距離を保持することを可能としている。例えば、これは魚の群れが余りにも混雑することを防止すべく使用可能である。この振る舞いが適用されるＩＥは、そのグループの１メンバーであり得るか或はあり得ない。
【０１１０】
分離距離はこの振る舞いを規定すべく使用可能なパラメータの１例である。近隣半径及び分離距離内側の内部におけるグループの各メンバーは、その振る舞いの操舵力を計算する際に考慮される。この分離距離は複数のＩＥ間の外部距離である（即ち、それらＩＥの境界球の外側の間における距離である）。このパラメータの値は、そのグループのメンバーが維持しようとする外部分離距離を決定する。
【０１１１】
「共に群がる」
この振る舞いは、複数のＩＥが相互に群がることを可能としている。それは、整列、参加、から分離の効果を組み合わせる。
【０１１２】
以下の表１１はこの振る舞いを規定すべく使用可能なパラメータを記載している。
【表１１】
【０１１３】
（振る舞いの組み合わせ）
ＩＥは、随時、相互に関連された多数のアクティブな振る舞いを有する。それ故に、重要性を所与の振る舞いに割り当てるべく手段が提供されている。
【０１１４】
これを達成するための第１手段は、振る舞いに強度及び優先順位を割り当てることによる。振る舞いの割り当てられた強度は、その振る舞いによって生成された操舵力がどの程度強力かに影響する。強度がより高ければ、生成された振る舞いの操舵力はより大きくなる。振る舞いの優先順位はその振る舞いが他の振る舞いを凌いで有する優位を規定する。より高い優先順位の振る舞いが起動されると、より低い優先順位の振る舞いが実効的に無視される。強度及び優先順位を振る舞いに割り当てることによって、より現実的な動画を作り出すために、どの振る舞いがどの状況においてより重要かアニメータがソルバーに知らせる。
【０１１５】
ソルバーが、ＩＥの新しい速度、位置、並びに、配向を計算するために、そのソルバーは全ての振る舞いの所望運動を計算し、それら運動を振る舞いの強度に基づき合計する一方、より低い優先順位のものは無視し、そして、ＩＥの属性において規定された最大速度、加速度、減速度、並びに、旋回半径を強化する。最終的には、旋回によるブレーキングは考慮され得る。事実上、キャラクタのブレーキング・ソフトネス及びブレーキ・パッディングの属性の値に基づき、キャラクタは旋回のためにスローダウンする。
【０１１６】
図７に戻って、以下、方法１００の詳細な説明が図１１に図示された１フロア建造物３０の内室の形態での単純なディジタル・ワールドや、障害物である暗線によって表現された壁３２、可動エンティティ（不図示）に対する到達可能な空間３４を規定する内部で取り囲まれた領域を参照して続行される。
【０１１７】
ステップ１０４で、ナビゲーション・メッシュ３５が可動ディジタル・エンティティ（不図示）に対して作り出される。これは到達可能な空間３４を、図１１の１フロア建造物の例のための図１２に図示された凸セル３６に分割或は変換することによって達成される。
【０１１８】
ナビゲーション・メッシュ３５は、手動的或は自動的の何れかで、例えば、衝突層或はレンダリング形状を用いて、作り出されることが出来る。衝突層は物理学的過程の衝突検出／解像度の目的のため、レンダリング形状の単純化である形状的メッシュである。この場合、ナビゲーション・メッシュは衝突層の部分集合であり、その衝突層上を可動エンティティが移動する（これは典型的にはフロアであり、壁ではない）。
【０１１９】
レンダリング形状からナビゲーション・メッシュを誘導することは、出来る限り形状を単純化することと、出来る限り継ぎ目のないメッシュにその形状を融合することとを要求する（例えば、交差している多角形の除去等々）。
【０１２０】
手動作成において、３Ｄオペレータ（典型的には３Ｄアーチスト）は入力形状を調査し、多角形を正しく融合し、非到着可能空間を取り去る。留意されるべきことは、これを高い度合いまで自動的に取り扱うアルゴリズムが存在することである。
【０１２１】
凸多角形はナビゲーション・メッシュ３５の作成においてセルとして使用されるが、その理由は、そうしたセル内の任意の点がセルの内の他の任意の点までの直線上で直に到着可能であるからである。
【０１２２】
ナビゲーション・メッシュにおけるセルＣｘ及びＣｙと連結しているエッジＥｘｙは、もしエンティティがＥｘｙを介してセルＣｘからＣｙまで通過出来れば「通過可能」と考えられる。
【０１２３】
ステップ１０６で、始点及び終点（不図示）が配置され、それら２つの点の各々を含む対応するセルが識別される。
【０１２４】
表現「始点」及び「終点」は、ここでは、限定的に解釈されるべきではない。事実上、ディジタル可動エンティティがピクセル・サイズでなければ、始点及び終点は仮想ワールド内の１つの箇所或は領域と言及される。
【０１２５】
ステップ１０８で、第１確認は、始点及び終点が双方共に同一セル内に配置されているか否かを確認することである。もしそうであれば、方法１００はステップ１１０に進み、そこでディジタル・エンティティが方法が停止する前に始点から終点まで移動させられる。先に述べたように、凸セルの使用はディジタル可動エンティティが１つのセル内を一直線状に移動すること或は移動させられることを可能としている。しかしながら、ある種の場合、例えばオブジェクト或は他の可動エンティティは該可動エンティティが衝突回避戦略を採用するように強制する可能性がある。以下により詳細に記載されるように、本発明のより特定の例示的実施例に従った方法１００は、そうした適合性ある振る舞い伴う可動ディジタル・エンティティをもたらす。
【０１２６】
方法１００に戻れば、もし始点及び主点が同一セル内に配置されていなければ、凸セル間での複数セルから成るシーケンスは、始セルから終セルまでの間でのディジタル可動エンティティに対する経路をもたらすように、それら始セルから終セルまで決定される（ステップ１１２）。
【０１２７】
ステップ１１２は、連結性グラフ３８を先ず構築することによって達成され、該グラフは各セル３６をノード４０で置き換えて、通過可能セル（ノード）の各対を線４２で連結することによって獲得される。連結性グラフ３８の例としては図１１及び図１２に図示された例に対する図１３に図示されている。勿論、そうしたグラフ３８は純粋に仮想であり、実際にグラフ的に作り出されない。
【０１２８】
次いで、結果としてのグラフ３８は始点及び終点をそれぞれ表現している２つのノード４０の間の経路を見出すべく調査される。数多くの既知の技術が使用され得て、そうしたグラフ調査問題を解決して、それら２つの対応するノードの間の経路をもたらす。その経路は、もし存在すれば、対応するセルとして復帰される。
【０１２９】
例えば、横幅第１調査（ＢＦＳ）が使用され得て、グラフ３８を調査する。この周知のＢＦＳ方法は、最低コストの経路を提供することを可能としているが、調査されるノードの数の点では非常に高価であり得る。これも使用可能である深さ第１調査（ＤＦＳ）は調査されるノードの数の点で著しくより安価であるが、最低コストで経路を提供することを可能としていない。経験側がこのＤＦＳに負荷され得て、計算的効率性を維持しつつ、経路品質を改善しようとする。
【０１３０】
留意されるべきことは、複数セルから成るそうしたシーケンスや、終点までのナビゲートすることが出来ることを防止されたエンティティを、ステップ１１２での方法で停止が全くないと云う状況であり得ることである。
【０１３１】
もし複数セルから成るそうしたシーケンスが存在すれば、媒介点（不図示）は複数セルから成るシーケンスにおける連続したセルの間の各境界上に決定される（ステップ１１４）。言い換えれば、各凸セルに対する入口／出口の点は選択される。
【０１３２】
例えば、各エッジの中心点は選択され得る。勿論、他の点は代替的に選択され得る。セル・エッジ（セル界面）上の点はセル間を移動する距離を低減してその経路を更に平滑にするように選択可能である。
【０１３３】
次いで、ディジタル・エンティティは始点からそれぞれ選択された連続した媒介点まで移動させられ、最終的には始点まで移動させられる（ステップ１１６）。
【０１３４】
図１４乃至図２１に移れば、方法１００は壁４６によって限界が定められた別の単純ワールド４４（図１４参照）を参照して図示されている。
【０１３５】
図１５に図示されているように、ナビゲーション・メッシュ４７は作り出され、ワールド４４は基準目的のためにＡからＺまでで識別される凸セル４８に分割される。
【０１３６】
始点５０及び終点５２は図１６に示されている。方法１００のステップ１０６に追従してそれらはセル「Ｚ」及び「Ｊ」にそれぞれ見出される。それらは同一セル内に配置されていないので、方法はステップ１１２で続行し点５０及び５２の間の複数セルから成るシーケンスの決定を伴って、図１６に図示されるような以下のシーケンス：「Ｚ」、「Ｙ」、「Ｏ」、「Ｘ」、「Ｗ」、「Ｖ」、「Ｕ」、「Ｔ」、「Ｈ」、並びに、「Ｊ」をもたらす。複数セルから成るシーケンスにおける連続したセルの間の各境界上に媒介点を決定した後（ステップ１１４）、方法は図１７に図示された決定経路５４に沿って移動するエンティティを伴って続行する。図１７で見られるように、経路はより現実的な足跡をもたらすべく平滑であり得る。
【０１３７】
本発明に従ったナビゲーション方法がエンティティが目標を求めようとする際に使用されるので、ナビゲーション・メッシュは実行時間に動的に変更され得る（ステップ１０４）。例えば、図１８及び図１９に図示されているように、セルはブラインド・データを介してターン・オフされて、道路閉塞或は過剰な人々或は物理学的過程従動破片による密集をシミュレートするか、或は、ターン・オンされて、ドア開口、密集終了若しくは破壊された壁の通過をシミュレートする。図１８において、前者のセル「Ｈ」はターン・オフされて第１代替経路５６を生じ、図１９において、双方の前者セル「Ｂ」及び「Ｈ」がターン・オフされて第２代替経路５８を生ずる。
【０１３８】
また方法１００は可動ディジタル・エンティティの次元、そしてより明確にはその幅等のその移動方向と相対的なその横方向次元を考慮することを可能としている。ステップ１０４でのナビゲーション・メッシュの作成は可動エンティティのそうした特性を考慮することが出来て、方法１００はエンティティが通過出来る経路を出力する。これは図２０及び図２１に図示されている。
【０１３９】
図２０は方法１００から獲得された経路６０を図示して、ディジタル・エンティティを始点６２から終点６４まで移動させている。図２１における可動ディジタル・エンティティの幅を２倍にすることによって（球６６によって図示）、前者のセル「Ｌ」はもはやナビゲーション・メッシュ６８の部分ではなく、新経路７０がこの方法１００によって提供される。（図２１の球６６を参照）
【０１４０】
方法１００は２次元ディジタル・ワールドに限定されない。図２２及び図２３に図示されるように、方法１００が使用され得て、始点及び終点の間の経路を決定し、次いで、３次元ディジタル・ワールドにおけるそれら２つの点の間において動画化キャラクタ等のディジタル可動エンティティを移動させる。図２２は、シミュレータ、ゲーム、或は、アニメーションの小都市部分上の平面図生成器の出力を図示している。図２３は、方法１００でのステップ１０４から生ずるナビゲーション・メッシュを図示している。
【０１４１】
以下、図２４乃至図２７を参照して記載されるように、方法１００はアウトドア及びインドア環境に対して適合され得る。
【０１４２】
アウトドア環境は、典型的には、建造物や、歩道、道路、並びに、川によって分離された、市場スペース、木々を伴う公園等のオープン・スペースから構成される。対応して、平面図生成器はナビゲーション・メッシュ内において複数の穴を切り抜くべく外部建造物を用いる。
【０１４３】
可動エンティティに異なる種類御到着可能な空間の間を区別させるために、ブラインド・データが用いられて、到着可能空間の異なる部分を特徴付ける。ある種の適用において、ブラインド・データはナビゲーション・メッシュのセルと関連され得て、ナビゲーション表面における相違を特定し（例えば、道路及び歩道）、そしてエンティティにそれに応じたナビゲートを為させる（例えば、道路上の車両や歩道上の人を保持）。
【０１４４】
図２４は市街道路の形態のディジタル・ワールドを図示している。図２５は、方法１００のステップ１０４から獲得されるナビゲーション・メッシュを図示している。ブラインド・データが使用されて、車道（白色セル）及び歩道（灰色セル）の間の区別をする。
【０１４５】
図２６に図示されているように、インドア環境は、典型的には多数層であり、内壁及びドアを介して複数の部屋に分割され、階段によって連結されたフロアから構成される。対応して、平面図生成器はバリヤーとしての壁を用いて各フロアに対するナビゲーション・メッシュを計算し、次いで複数のナビゲーション表面は階段と対応するセルによってリンクする。これは３Ｄナビゲーション・メッシュを生じ、そこで、セルは相互に上部になり得る。経路見出しは変更されて、キャラクタが中にあるセルよりもむしろ、ディジタル可動エンティティが乗っている表面セルを決定する。手短には、３次元ワールドが複数のレベルによって規定されると、ナビゲーション・メッシュが各レベルに対して作り出され、２つの連続したナビゲーション・メッシュが連結セルによって相互連結されている。
【０１４６】
図７そしてより明確にはステップ１１６に移れば、凸セル内において、方法１００は可動エンティティが所定媒介点から次の点まで一直線状に移動することを可能していることが思い出される。それ故に、エンティティが一直線状に進行することを防止出来る唯一のものは動的障害物であり得る。この状況に立ち向かうべく、可動エンティティにはセンサが設けられ得る。本発明の方法に従った動的衝突回避方法をより詳細に記載する前に、センサの概念や、データ情報、コマンド（命令）、決定、並びに、決定木等の他の関連概念が先ず簡単に記載される。しかしながら留意されるべきことは、本発明に従った衝突回避方法、或は、ナビゲーション方法１００の何れも、ディジタル可能エンティティに対するセンサ或は決定規則の特定実施例に限定されると解釈されるべきではない。
【０１４７】
（データ情報）
エンティティ・データ情報はその内部メモリとして考えられる。各データはエンティティの内部メモリ内に記憶された情報の要素である。例えば、データは敵が目撃された否か、誰が最も弱い協力者であるか等々の情報を保持し得る。データはＩＥに対する状態変数としても使用され得る。
【０１４８】
データはエンティティ・センサによって或はコマンドによって決定木内に書き込まれる。データの値は決定木によって使用されて、振る舞い及びアニメーション起動及び起動解除するか、或は、エンティティの状態を試験する。センサ及び決定木は以下により詳細に記載される。
【０１４９】
（センサ）
エンティティはセンサを用いて、ワールドについての情報を得る。センサはその検知した情報をエンティティに属するデータ内に記憶する。
【０１５０】
パラメータが使用され得て、センサの起動をトリガーする。もしセンサがオフに設定されれば、それはソルバーによって無視されて、情報を任意のデータ内に記憶しない。
【０１５１】
以下、センサの例がより詳細に記載される。勿論、当業者が理解できる範囲内であって、その適用例に応じて追加或は代替のセンサを提供するものと思われる。
【０１５２】
「視覚センサ」
視覚センサはキャラクタの目及び耳であり、該キャラクタが仮想ワールド内において他の物理的オブジェクト或は可動エンティティを検知することを可能とし、それらは、例えば、自発性或は非自発性のキャラクタ、バリヤー、並びに、中間点であり得る。
【０１５３】
以下のパラメータは、例えば、視覚センサを規定することを可能としている：
【表１２】
【０１５４】
（コマンド（命令）、決定、並びに、決定木）
決定木はセンサを用いて集められたデータ情報を処理すべく使用される。
【０１５５】
コマンドは振る舞い或はアニメーションを起動すべく、或は、ＩＥ内部メモリを変更すべく使用される。
【０１５６】
コマンドは決定によって発動される。単一決定は、条件表現と発動すべきコマンドのリストとを含む。
【０１５７】
決定木はルート決定ノードを含み、それは子供決定ノードを所持することができる。それら子供の各々は、順次、それらの自体の子供を所持し、それら各々はより多くの子供を所持する等々である。
【０１５８】
決定木が評価されるべき否かを示すパラメータはその決定木を規定する点で使用可能である。
【０１５９】
コマンドがアニメーションを起動することと対応して、遷移が現行アニメーション及び新アニメーションの間で規定されると、その遷移が先ず起動される。
【０１６０】
同様に、コマンドが振る舞いを起動することと対応すると常に、混合時間が現行アニメーション及び新アニメーションの間に提供され得る。
【０１６１】
更には、コマンドが振る舞いの起動と対応すると常に、目標はデータによって特定されたオブジェクトに変更される。
【０１６２】
（動的衝突回避）
以下に記載されることは、方法１００でのステップ１１０及び１１６の双方の部分集合が、ステップ１０２乃至１１４を通じて決定された経路に沿って移動するに伴って、エンティティが任意の動いている障害物（例えば、別のキャラクタ或は物理学過程オブジェクト）にぶつかることを回避させることができることである。
【０１６３】
単に経路見出しは、２ステップ処理として見られる、即ち、：i）その経路を決定すること、そして次いでii）それに追従することであり；障害物回避は図２８に図示される２ステップ方法２００としても見られる、即ち、：
２０２-可動ディジタル・エンティティ及び動いている障害物の間の可能性ある衝突の脅威を評価又は見積もり、そして、
２０４-もしそうした脅威があれば、可動ディジタル・エンティティはその動いている障害物を回避すべく戦略を採用することによってそれに応じた応答を為す。
【０１６４】
「衝突脅威評価」
ステップ２０２で、各エンティティ７２はそのセンサ（図２９を参照）を用いて、その近辺内にはどのような可能性ある障害物があるかを検出し、それら障害物の内のどれが衝突の最も大きな脅威を提示しているか決定する。図３０に図示されているように、センサは被写界深度によって特徴付けられるエンティティ７２を巡る視野７４として構成されて、そのエンティティがどの程度遠くまで見ることができるかを規定している。各可動エンティティの視界は該エンティティを取り囲むパイ（或はその適用例に応じた球）として規定され得る。
【０１６５】
もし障害物が全くなければ、エンティティ自体の周りのエンティティ視界７４は完全に自由であり、パイは完全である。しかしながら図３０に図示されているように、各障害物はこのパイの一片を除去する。その除去された一片のサイズは障害物サイズ及びエンティティからの距離に依存する。
【０１６６】
パイの妨げられていない区分を、ここでは、穴７６乃至７８として言及する（図３１参照）。エンティティ７２は最良穴を捜し求めて持続する。
【０１６７】
最良穴は幾つかの方法で決定され得る。典型的な方法は以下の如くである：
・穴７６乃至７８はエンティティ７２の所望方向からの増大する半径距離の順に区分けされる。
・エンティティが通過するに充分に大きな第１穴が選択される。
・もし穴がなければ、エージェントが完全に阻止され移動を停止する。
【０１６８】
選択された穴に依存して可動エンティティは旋回或は逆転の何れかによってその穴に入り込むことができる。
【０１６９】
シミュレータの適用例やエンティティの特性に依存して、障害物は異なる回避重要性を有するものとして特徴付けられる。例えばハンビィー(Hummvee)は、その最高優先順位として他の車両、第２優先順位としての歩行者、非常に低い優先順としての犬等の小動物を、回避することを考え；一般歩行者はその最高優先順位としての車両、及び、第２優先順位としての他の歩行者を考える。勿論、暴動等の極端な状況はこれら優先順位を動的に変え得る。よって、異なる障害物グループは異なる回避制約を有する。最も基本的な制約は障害物に脅威であると割り当てることである。従って、各障害物グループに対して、関連された認識半径がある。キャラクタがそのワールドを通じて移動すると共に、その周りを掃引し、そのセンサはその認識半径以内であるその掃引で検出された障害物毎に、潜在的な衝突脅威としてフラグが立てられる。
【０１７０】
各知覚脅威に対して、衝突脅威状態の異なる種類が割りあてられ、以下を含む：
・静止状態：障害物が移動しないが、可動エンティティの進路内にある。
・到着：障害物が可動エンティティに向かって来る。
・出発：障害物が可動エンティティから遠ざかるように進行するが、該エンティティはそれに追突する。
・側方強打：障害物は可動エンティティと側方から衝突すると予想される。
【０１７１】
「回避戦略」
各衝突脅威に対して、２種類の回避戦略がある（ステップ２０４）：
・迂回：障害物を周回することで衝突を回避しようとする。
・待機：障害物がその衝突経路をでるまでスローダウン（そして、潜在的には停止）することで衝突を回避しようとする。
【０１７２】
留意されるべきことは、両方の上記下回避戦略は経験則であり、どちらの場合も全ての状況内で作業すべく保証されている。
【０１７３】
図３２Ａ乃至図３２Ｃ、図３３Ａ乃至図３３Ｃ、図３４Ａ乃至図３４Ｃ、並びに、図３５Ａ乃至図３５Ｃは、衝突脅威の３つの例（図３２Ａ、図３３Ａ、図３４Ａ、並びに、図３５Ａ）を図示し、各々が双方の対応する回避戦略を伴う。図３２Ａ乃至図３５Ｃは、迂回が静止状態の障害物を周回するため、そして、到着障害物の進路から外にでるためにどの程度有用であるかを示している。しかしながらそれは、出発障害物に対して多数の押しのけを生じ得る。それにもかかわらず、迂回は交通渋滞を最小化して、最終的には逃げ道を見出すと云う長所を有する。
【０１７４】
待機は、常に、出発障害物及び到着障害物に対して充分に働きかける（もしそれらが迂回しようとするならば）。しかしながら見出されたことは、待機到着障害物及び静止状態障害物は交通渋滞を引き起こし得る。殆どの場合、交通状態を回避する最も効果的な方法は飛行に対する戦略を変えるべく決定論理を使用することである。
【０１７５】
（グループに基づく動作変更器（編隊））
充分観測された事実は、鳥、魚、人を含む群れに基づく動物はグループとなって異なって移動することである。この移動振る舞いは群がりと一般には呼称される。人によって、グループに基づく移動は、曲がりくねった市街道路を走り抜くソマリア民兵の自由なグループから、現代のデルタフォース・オペレータの調整されたカバー及び掃引ルーチンへのパレードで兵隊を行進させる固定した編隊まで非常に変化に富んでいる。各場合において、グループの集合的良心はそのグループ内の各誘導個人の行動に影響する。
【０１７６】
コンピュータ・グラフィック人工知能によって最も迅速に識別されるグループ移動変更器は群がりであり、超粒子としてボイドと呼称された鳥の群れをモデル化したレイノルズ［レイノルズ、１９８７年］によって有名と為された。レイノルズは群がりへの３つの基本要素を識別した：
・整列：グループ・メンバー自身を同一速度で同一方向に整列することによってそれらの運動を調和するグループ・メンバーの傾向；
・分離：グループ・メンバー間の特定量の空間を維持すべく該グループ・メンバーの傾向；そして、
・参加：相互に対する特定の近接性を維持すべくグループ・メンバーの傾向。
【０１７７】
次に友人のグループが道路を歩いていることを考えると、グループの内のより遅いメンバーが他のメンバーに追いつくべく速度を上げると、最も速いメンバー（彼等が丁重であることを仮定）は速度を僅かに落として落伍者が追いつくことを可能としている。そのグループの教養経歴に依存して、多少の空間がそれら友人の間に要求されるか或は誂えられる（都市住人から地方住人）。
【０１７８】
図３６Ａ乃至図３６Ｆは、先導キャラクタに追従する５つのキャラクタから成るグループに対する異なる群がり戦略の効果を示している。
【０１７９】
そうしたグループに基づく変更器が使用され得て、方法１００が使用されて始点及び終点の間におけるディジタル・ワールド内においてエンティティから成るグループを同時に移動させる際、より自然な効果をもたらす。
【０１８０】
ディジタル・ワールド内において、始点から終点まで画面上のディジタル・エンティティを移動する方法及びシステムが、３Ｄ適用例の特定例示実施例に含まれるとして記載されているが、画像要素の画面上での自発性変位を要求する任意の３Ｄ適用例に含ませることができる。例えば、本発明に従ったナビゲーション方法が使用され得て、先に記載されたような振る舞いで特徴付けられないディジタル・エンティティを移動させる。
【０１８１】
本発明に従ったナビゲーション方法が使用され得て、任意の数のエンティティを誘導し、そしてディジタル・ワールドの任意のタイプ或は構成に限定されない。本方法及びシステムが使用され得て、仮想ワールド内における可動オブジェクト或はエンティティの変位をそれらオブジェクト或はエンティティの更なる移動無しに計画する。
【０１８２】
本発明がその好適実施例によって以上に説明されたが、添付の特許請求の範囲で規定されたように、本発明の精神及び本質から逸脱することなしに変更され得る。
【図面の簡単な説明】
【０１８３】
【図１】図１は、「先行技術」として明示された、包括的な３次元（３Ｄ）適用例の第１レベルを図示するブロック線図である。
【図２】図２は、「先行技術」として明示された、図１の包括的な３次元（３Ｄ）適用例における第２レベルを図示するブロック線図である。
【図３】図３は、「先行技術」として明示された、図２のブロック線図の拡張図である。
【図４】図４は、「先行技術」として明示された、図１の包括的な３次元（３Ｄ）適用例から図１の包括的な３Ｄ適用例の画像生成器部までのデータの流れを図示するフローチャートである。
【図５】図５は、「先行技術」として明示された、ディジタル・ワールド内においてディジタル・エンティティをナビゲートすべく中間地点の使用を図示する線図である。
【図６】図６は、本発明の例示実施例に従った、ディジタル・ワールドにおいて始点から終点までディジタル・エンティティを画面上で移動させるシステムを実施するナビゲーション・モジュールを含むディジタル・エンティティの画面上でのアニメーションを図示するブロック線図である。
【図７】図７は、本発明の例示実施例に従った、ディジタル・ワールドにおいて始点から終点までディジタル・エンティティを画面上で移動させる方法を図示するフローチャートである。
【図８】図８は、図７の方法と一緒に用いられる２次元バリヤーを図示する概略図である。
【図９】図９は、図７の方法と一緒に用いられる３次元バリヤーを図示する概略図である。
【図１０】図１０は、図７の方法と一緒に用いられる対等システムを図示する概略図である。
【図１１】図１１は、図７の方法に従った、特定のディジタル・エンティティに対する到達可能な空間の第１例に従った、１フロア建造物の形態での２次元ワールドの概略上面図である。
【図１２】図１２は、図７の方法を通じて作り出されたナビゲーション・メッシュを図示する図１１の１フロア建造物の概略上面図である。
【図１３】図１３は、図１２のナビゲーション・メッシュから獲得された接続性グラフの概略図である。
【図１４】図１４は、図７の方法に従った、特定の可動ディジタル・エンティティに対する到着可能な空間の第２例に従った２次元ワールドの概略上面図である。
【図１５】図１５は、図７の方法を通じて作り出されたナビゲーション・メッシュを図示する図１１のワールドの概略上面図である。
【図１６】図１６は、図７の方法の各種ステップを図示する、図１５と類似の概略上面図である。
【図１７】図１７は、図７の方法から生ずる経路を図示している、図１５と類似の概略上面図である。
【図１８】図１８は、第１通路の遮断から生ずる図１７に図示された経路に対する第１代替経路を図示している、図１７と類似の概略上面図である。
【図１９】図１９は、第２通路の遮断から生ずる図１７及び図１８に図示された経路に対する第２代替経路を図示している、図１８と類似の概略上面図である。
【図２０】図２０は、新しい始点から終点までで生ずる図１７に図示された経路に対する第３代替経路を図示している、図１７と類似の概略上面図である。
【図２１】図２１は、可動ディジタル・エンティティの幅の２倍から生ずる図２０に図示された経路に対する代替経路を図示している、図２０と類似の概略上面図である。
【図２２】図２２は、シミュレータの小都市部に対する間取図生成器の斜視図である。
【図２３】図２３は、図７の方法を用いている図２２の間取図生成器から作り出されたナビゲーション・メッシュを図示する斜視図である。
【図２４】図２４は、市街道路の形態でのディジタル・ワールドの斜視図である。
【図２５】図２５は、結果として生ずるセルを特徴付けるブラインド・データの使用を含む、図７の方法に従ったナビゲーション・メッシュ・ステップを図示している、図２４の市街道路の斜視図である。
【図２６】図２６は、建造物の形態でのディジタル・ワールドの切り取られた斜視図である。
【図２７】図２７は、図７の方法を用いている図２６の建造物から生ずるナビゲーション・メッシュの斜視図である。
【図２８】図２８は、本発明の特定の例示的実施例に従った、ディジタル・ワールドにおえる始点から終点まで画面上を移動するディジタル・エンティティに対する衝突回避方法のフローチャートである。
【図２９】図２９は、本発明に従った、キャラクタ・センサを図示している、キャラクタの形態の３Ｄ適用例におけるエンティティの斜視図である。
【図３０】図３０は、本発明に従ったエンティティの視覚センサを図示しているディジタル・ワールド内のエンティティの上面図であって、該センサによって提供される視野をより明確に図示している上面図である。
【図３１】図３１は、図７の方法の特定の実施例に従った、障害物を回避する副経路の選択を図示している図３０と類似のディジタル・ワールド内のエンティティの斜視図である。
【図３２】図３２Ａ乃至図３２Ｃは、静止状態障害物（図３２Ａ）の場合、図７の方法の特定実施例に従った、可動ディジタル・エンティティによって使用され得る回避戦略（図３２Ｂ及び図３２Ｃ）を図示する概略図である。
【図３３】図３３Ａ乃至図３３Ｃは、到着障害物（図３３Ａ）の場合、図７の方法の特定実施例に従った、可動ディジタル・エンティティによって使用され得る回避戦略（図３３Ｂ及び図３３Ｃ）を図示する概略図である。
【図３４】図３４Ａ乃至図３４Ｃは、出発障害物（図３４Ａ）の場合、図７の方法の特定実施例に従った、可動ディジタル・エンティティによって使用され得る回避戦略（図３４Ｂ及び図３４Ｃ）を図示する概略図である。
【図３５】図３５Ａ乃至図３５Ｃは、側方強打障害物（図３５Ａ）の場合、図７の方法の特定実施例に従った、可動ディジタル・エンティティによって使用され得る回避戦略（図３５Ｂ及び図３５Ｃ）を図示する概略図である。
【図３６】図３６Ａ乃至図３６Ｅは、図７の方法を用いている５つの可動ディジタル・エンティティを同時に移動させる経路を図示し且つグループに基づく移動変更器を適用している概略図である。
【図３６Ａ】図３６Ａは、図７の方法を用いている５つの可動ディジタル・エンティティを同時に移動させる経路を図示し且つグループに基づく移動変更器を適用している概略図である。
【図３６Ｂ】図３６Ｂは、図７の方法を用いている５つの可動ディジタル・エンティティを同時に移動させる経路を図示し且つグループに基づく移動変更器を適用している概略図である。
【図３６Ｃ】図３６Ｃは、図７の方法を用いている５つの可動ディジタル・エンティティを同時に移動させる経路を図示し且つグループに基づく移動変更器を適用している概略図である。
【図３６Ｄ】図３６Ｄは、図７の方法を用いている５つの可動ディジタル・エンティティを同時に移動させる経路を図示し且つグループに基づく移動変更器を適用している概略図である。
【図３６Ｅ】図３６Ｅは、図７の方法を用いている５つの可動ディジタル・エンティティを同時に移動させる経路を図示し且つグループに基づく移動変更器を適用している概略図である。
【符号の説明】
【０１８４】
１０ コンピュータ・システム
１２ ナビゲーション・モジュール
１４ シミュレータ
１６ ワールド・データベース（ＷＤＢ）
１８ 画像生成器
２０，２２ モジュール
１００ 方法
【特許請求の範囲】
【請求項１】
画面上の少なくとも１つのディジタル・エンティティをディジタル・ワールド内における始点から終点まで移動するためのコンピュータ・システムにおける方法であって、
i）ディジタル・ワールド内での少なくとも１つの可動ディジタル・エンティティに対する障害物の各位置を提供し；その少なくとも１つの可動ディジタル・エンティティに対する到達可能な空間として障害物無しに前記ディジタル・ワールドの少なくとも複数の部分を規定する段階と、
ii）その到達可能な空間を少なくとも１つの凸セルに分割することによって少なくとも１つの可動ディジタル・エンティティに対するナビゲーション・メッシュを作り出す段階と、
iii）始点及び終点をそれぞれ含む前記少なくとも１つの凸セルの間に始セル及び終セルを配置する段階と、
iv）前記始セルが前記終セルと対応しているかを確認し；もしその始セルがその終セルと対応していれば、iv）ａ）前記少なくとも１つの可動ディジタル・エンティティを前記始点から前記終点まで移動させ；もし前記始セルが前記終セルと対応していなければ、iv）ｂ）i）前記始点セルから前記終点セルまでの前記少なくとも１つの凸セルの間に複数セルから成るシーケンスを決定し、そして、iv）ｂ）ii）複数セルから成る前記シーケンス内の連続したセルの間の各境界上に配置された少なくとも１つの媒介点を決定し、そして、iv）ｂ）iii）前記少なくとも１つの可動ディジタル・エンティティを前記始点から前記終点への各連続した前記少なくとも１つの媒介点まで移動させる段階と、
の諸段階を含む方法。
【請求項２】
前記障害物が動的な障害物であり、ディジタル・ワールド内に変化を生みだし、前記ナビゲーション・メッシュが動的に作り出されて、前記ii）において、前記動的な対象物によって引き起こされる前記ディジタル・ワールド内における前記変化に対してうまく処理する、請求項１に記載の方法。
【請求項３】
前記iv）ｂ）i）が前記始セルから終セルまで前記少なくとも１つの凸セルの間に複数セルから成るシーケンスを決定することが、連結性グラフを構築することと、前記始セルから前記終セルまでの間の経路に対する前記連結性グラフを調査することとを含む、請求項１に記載の方法。
【請求項４】
横幅第１調査（ＢＦＳ）或は深さ第１調査（ＤＦＳ）が前記連結性グラフを調査することで使用される、請求項２に記載の方法。
【請求項５】
前記iv）ｂ）ii）において、複数セルから成る前記シーケンス内の連続したセルの間の各境界上に配置された少なくとも１つの媒介点が中心点を含む、請求項１に記載の方法。
【請求項６】
複数セルから成る前記シーケンスにおける連続下セルの間における各境界上に配置された少なくとも１つの仲介点が、運動の品質を改善するように選択される、請求項１に記載の方法。
【請求項７】
複数セルから成る前記シーケンスが前記連続したセルの内の少なくとも１つの範囲内において移動される距離を低減するように選択される、請求項６に記載の方法。
【請求項８】
前記ディジタル・ワールドが前記凸セルの内の前記少なくとも１つ以内に少なくとも１つの移動障害物を更に含み、iv）ａ）前記少なくとも１つの可動ディジタル・エンティティを前記始点から前記終点まで移動させ、そして、iv）ｂ）iii）前記少なくとも１つの可動ディジタル・エンティティを前記始点から前記終点への各連続した前記少なくとも１つの媒介点まで移動させることが、ａ）前記少なくとも１つの移動障害物と前記少なくとも１つのディジタル可動エンティティとの間に衝突脅威が存在するかを評価し、そして、ｂ）前記少なくとも１つのディジタル可動エンティティが、衝突脅威が存在した際に、前記少なくとも１つの移動障害物を回避すべく戦略を採用することを更に含む、請求項１に記載の方法。
【請求項９】
a）前記少なくとも１つの移動障害物と前記少なくとも１つのディジタル可動エンティティとの間に衝突脅威が存在するかを評価することが、前記少なくとも１つの移動障害物を検出すべくセンサを用いることを含む、請求項８に記載の方法。
【請求項１０】
前記センサを用いることが、被写界深度によって特徴付けられる前記少なくとも１つの可動ディジタル・エンティティの間の視野をもたらす、請求項９に記載の方法。
【請求項１１】
前記少なくとも１つの移動障害物を検出すべくセンサを用いることが、前記視野内に穴をもたらし、その穴が前記少なくとも１つの移動障害物を特徴付ける、請求項１０に記載の方法。
【請求項１２】
前記穴が少なくとも１つの特性を有し、前記少なくとも１つのディジタル可動エンティティが、前記穴の前記少なくとも１つの特性に従って前記少なくとも１つの移動障害物を回避すべくその戦略に優先順位をつける、請求項１１に記載の方法。
【請求項１３】
前記穴の前記少なくとも１つの特性が径方向距離及び幅を含む、請求項１２に記載の方法。
【請求項１４】
前記少なくとも１つの障害物を回避する前記戦略が迂回或は待機である、請求項１３に記載の方法。
【請求項１５】
前記始点及び終点の間に経路をもたらし、前記方法がより現実的な経路をもたらすべく前記経路を平滑化することを更に含む、請求項１に記載の方法。
【請求項１６】
前記少なくとも１つの可動ディジタル・エンティティが、前記経路に追従すべく群がり戦略を全てが採用している複数の可動ディジタル・エンティティを含む、請求項１５に記載の方法。
【請求項１７】
前記群がり戦略が、追従、整列、分離、並びに、参加の内の少なくとも１つを含む、請求項１６に記載の方法。
【請求項１８】
前記少なくとも１つの可動ディジタル・エンティティが複数の可動ディジタル・エンティティを含む、請求項１に記載の方法。
【請求項１９】
前記凸セルの内の少なくとも１つがブラインド・データによって特徴付けられて、ナビゲーション・セル間の区別を可能としている、請求項１に記載の方法。
【請求項２０】
前記ディジタル・ワールドが状態変化エンティティを更に含み、該状態変化エンティティが前記ブラインド・データに対して影響を及ぼす、請求項１９に記載の方法。
【請求項２１】
前記ナビゲーション・メッシュが手動的或は自動的に作り出される、請求項１に記載の方法。
【請求項２２】
前記ディジタル・ワールドがレンダリング或は物理的形状によって規定され、前記ナビゲーション・メッシュが前記レンダリング或は物理的形状を用いて作り出される、請求項１に記載の方法。
【請求項２３】
前記ディジタル・ワールドが２次元ワールドである、請求項１に記載の方法。
【請求項２４】
前記ディジタル・ワールドが３次元ワールドである、請求項１に記載の方法。
【請求項２５】
前記３次元ワールドが複数のレベルによって規定され、前記ii）において、レベル・ナビゲーション・メッシュが前記複数のレベルの各々に対して作り出され、連続したレベル・ナビゲーション・メッシュが連結セルによって相互に連結されている、請求項２４に記載の方法。
【請求項２６】
前記少なくとも１つの可動ディジタル・エンティティが自発性或は非自発性である、請求項１に記載の方法。
【請求項２７】
ディジタル・ワールド内においてディジタル・エンティティを始点から終点まで画面上で移動するシステムが、
前記ディジタル・ワールドについての情報を記憶し且つ前記ディジタル・ワールド内での前記可動ディジタル・エンティティに対する障害物の各位置を提供するワールド・データベースと、
ナビゲーション・モジュールであり、
i）前記可動ディジタル・エンティティに対する到達可能な空間として障害物無しの前記ディジタル・ワールドの少なくとも複数の一部を規定し、
ii）前記到達可能な空間を少なくとも１つの凸セルに分割することによって前記可動ディジタル・エンティティに対するナビゲーション・メッシュを作り出し、
iii）前記始点及び前記終点をそれぞれ含む少なくとも１つの凸セルの間に始セル及び終セルを配置し、
iv）前記始セルが前記終セルと対応しているかを確認し；もし前記始セルが前記終セルと対応していなければ、v）前記始セルから前記終セルまでの前記少なくとも１つの凸セルの間における複数セルから成るシーケンスを決定し、そして、vi）複数セルから成る前記シーケンス内の連続したセルの間の各境界上に配置された少なくとも１つの媒介点を決定することからナビゲーション・モジュールと、
前記ナビゲーション・モジュール及び前記ワールド・データベースに結合されたシミュレータであり、iv）で確認されたように、もし前記始セルが前記終セルと対応していれば前記始点から前記終点まで当該シミュレータと結合された画像生成器を介して画面上で前記ディジタル・エンティティを移動するか、或は、もし前記始セルが前記終セルと対応していなければ前記始点から前記終点への各連続した前記少なくとも１つ媒介点まで前記ディジタル・エンティティを移動することから成るシミュレータと、
を備えるシステム。
【請求項２８】
前記ワールド・データベースが前記凸セルの内の前記少なくとも１つ以内における少なくとも１つの移動障害物についての情報を更に記憶するものであり、前記ナビゲーション・モジュールが、ａ）前記少なくとも１つの移動障害物と前記少なくとも１つのディジタル可動エンティティとの間に衝突脅威があるかを更に評価し、そして、ｂ）前記少なくとも１つのディジタル可動エンティティが、衝突脅威が存在する際に前記少なくとも１つの移動障害物を回避する戦略を採用する、請求項２７に記載のシステム。
【請求項２９】
前記ナビゲーション・モジュールが前記シミュレータの部分である、請求項２７に記載のシステム。
【請求項３０】
前記少なくとも１つのディジタル可動エンティティに作用数前記ディジタル・ワールドに追従する前記ナビゲーション・ユニットの動的な調整のためのシミュレータと結合された意思決定モジュールを更に含む、請求項２７に記載のシステム。
【請求項１】
画面上の少なくとも１つのディジタル・エンティティをディジタル・ワールド内における始点から終点まで移動するためのコンピュータ・システムにおける方法であって、
i）ディジタル・ワールド内での少なくとも１つの可動ディジタル・エンティティに対する障害物の各位置を提供し；その少なくとも１つの可動ディジタル・エンティティに対する到達可能な空間として障害物無しに前記ディジタル・ワールドの少なくとも複数の部分を規定する段階と、
ii）その到達可能な空間を少なくとも１つの凸セルに分割することによって少なくとも１つの可動ディジタル・エンティティに対するナビゲーション・メッシュを作り出す段階と、
iii）始点及び終点をそれぞれ含む前記少なくとも１つの凸セルの間に始セル及び終セルを配置する段階と、
iv）前記始セルが前記終セルと対応しているかを確認し；もしその始セルがその終セルと対応していれば、iv）ａ）前記少なくとも１つの可動ディジタル・エンティティを前記始点から前記終点まで移動させ；もし前記始セルが前記終セルと対応していなければ、iv）ｂ）i）前記始点セルから前記終点セルまでの前記少なくとも１つの凸セルの間に複数セルから成るシーケンスを決定し、そして、iv）ｂ）ii）複数セルから成る前記シーケンス内の連続したセルの間の各境界上に配置された少なくとも１つの媒介点を決定し、そして、iv）ｂ）iii）前記少なくとも１つの可動ディジタル・エンティティを前記始点から前記終点への各連続した前記少なくとも１つの媒介点まで移動させる段階と、
の諸段階を含む方法。
【請求項２】
前記障害物が動的な障害物であり、ディジタル・ワールド内に変化を生みだし、前記ナビゲーション・メッシュが動的に作り出されて、前記ii）において、前記動的な対象物によって引き起こされる前記ディジタル・ワールド内における前記変化に対してうまく処理する、請求項１に記載の方法。
【請求項３】
前記iv）ｂ）i）が前記始セルから終セルまで前記少なくとも１つの凸セルの間に複数セルから成るシーケンスを決定することが、連結性グラフを構築することと、前記始セルから前記終セルまでの間の経路に対する前記連結性グラフを調査することとを含む、請求項１に記載の方法。
【請求項４】
横幅第１調査（ＢＦＳ）或は深さ第１調査（ＤＦＳ）が前記連結性グラフを調査することで使用される、請求項２に記載の方法。
【請求項５】
前記iv）ｂ）ii）において、複数セルから成る前記シーケンス内の連続したセルの間の各境界上に配置された少なくとも１つの媒介点が中心点を含む、請求項１に記載の方法。
【請求項６】
複数セルから成る前記シーケンスにおける連続下セルの間における各境界上に配置された少なくとも１つの仲介点が、運動の品質を改善するように選択される、請求項１に記載の方法。
【請求項７】
複数セルから成る前記シーケンスが前記連続したセルの内の少なくとも１つの範囲内において移動される距離を低減するように選択される、請求項６に記載の方法。
【請求項８】
前記ディジタル・ワールドが前記凸セルの内の前記少なくとも１つ以内に少なくとも１つの移動障害物を更に含み、iv）ａ）前記少なくとも１つの可動ディジタル・エンティティを前記始点から前記終点まで移動させ、そして、iv）ｂ）iii）前記少なくとも１つの可動ディジタル・エンティティを前記始点から前記終点への各連続した前記少なくとも１つの媒介点まで移動させることが、ａ）前記少なくとも１つの移動障害物と前記少なくとも１つのディジタル可動エンティティとの間に衝突脅威が存在するかを評価し、そして、ｂ）前記少なくとも１つのディジタル可動エンティティが、衝突脅威が存在した際に、前記少なくとも１つの移動障害物を回避すべく戦略を採用することを更に含む、請求項１に記載の方法。
【請求項９】
a）前記少なくとも１つの移動障害物と前記少なくとも１つのディジタル可動エンティティとの間に衝突脅威が存在するかを評価することが、前記少なくとも１つの移動障害物を検出すべくセンサを用いることを含む、請求項８に記載の方法。
【請求項１０】
前記センサを用いることが、被写界深度によって特徴付けられる前記少なくとも１つの可動ディジタル・エンティティの間の視野をもたらす、請求項９に記載の方法。
【請求項１１】
前記少なくとも１つの移動障害物を検出すべくセンサを用いることが、前記視野内に穴をもたらし、その穴が前記少なくとも１つの移動障害物を特徴付ける、請求項１０に記載の方法。
【請求項１２】
前記穴が少なくとも１つの特性を有し、前記少なくとも１つのディジタル可動エンティティが、前記穴の前記少なくとも１つの特性に従って前記少なくとも１つの移動障害物を回避すべくその戦略に優先順位をつける、請求項１１に記載の方法。
【請求項１３】
前記穴の前記少なくとも１つの特性が径方向距離及び幅を含む、請求項１２に記載の方法。
【請求項１４】
前記少なくとも１つの障害物を回避する前記戦略が迂回或は待機である、請求項１３に記載の方法。
【請求項１５】
前記始点及び終点の間に経路をもたらし、前記方法がより現実的な経路をもたらすべく前記経路を平滑化することを更に含む、請求項１に記載の方法。
【請求項１６】
前記少なくとも１つの可動ディジタル・エンティティが、前記経路に追従すべく群がり戦略を全てが採用している複数の可動ディジタル・エンティティを含む、請求項１５に記載の方法。
【請求項１７】
前記群がり戦略が、追従、整列、分離、並びに、参加の内の少なくとも１つを含む、請求項１６に記載の方法。
【請求項１８】
前記少なくとも１つの可動ディジタル・エンティティが複数の可動ディジタル・エンティティを含む、請求項１に記載の方法。
【請求項１９】
前記凸セルの内の少なくとも１つがブラインド・データによって特徴付けられて、ナビゲーション・セル間の区別を可能としている、請求項１に記載の方法。
【請求項２０】
前記ディジタル・ワールドが状態変化エンティティを更に含み、該状態変化エンティティが前記ブラインド・データに対して影響を及ぼす、請求項１９に記載の方法。
【請求項２１】
前記ナビゲーション・メッシュが手動的或は自動的に作り出される、請求項１に記載の方法。
【請求項２２】
前記ディジタル・ワールドがレンダリング或は物理的形状によって規定され、前記ナビゲーション・メッシュが前記レンダリング或は物理的形状を用いて作り出される、請求項１に記載の方法。
【請求項２３】
前記ディジタル・ワールドが２次元ワールドである、請求項１に記載の方法。
【請求項２４】
前記ディジタル・ワールドが３次元ワールドである、請求項１に記載の方法。
【請求項２５】
前記３次元ワールドが複数のレベルによって規定され、前記ii）において、レベル・ナビゲーション・メッシュが前記複数のレベルの各々に対して作り出され、連続したレベル・ナビゲーション・メッシュが連結セルによって相互に連結されている、請求項２４に記載の方法。
【請求項２６】
前記少なくとも１つの可動ディジタル・エンティティが自発性或は非自発性である、請求項１に記載の方法。
【請求項２７】
ディジタル・ワールド内においてディジタル・エンティティを始点から終点まで画面上で移動するシステムが、
前記ディジタル・ワールドについての情報を記憶し且つ前記ディジタル・ワールド内での前記可動ディジタル・エンティティに対する障害物の各位置を提供するワールド・データベースと、
ナビゲーション・モジュールであり、
i）前記可動ディジタル・エンティティに対する到達可能な空間として障害物無しの前記ディジタル・ワールドの少なくとも複数の一部を規定し、
ii）前記到達可能な空間を少なくとも１つの凸セルに分割することによって前記可動ディジタル・エンティティに対するナビゲーション・メッシュを作り出し、
iii）前記始点及び前記終点をそれぞれ含む少なくとも１つの凸セルの間に始セル及び終セルを配置し、
iv）前記始セルが前記終セルと対応しているかを確認し；もし前記始セルが前記終セルと対応していなければ、v）前記始セルから前記終セルまでの前記少なくとも１つの凸セルの間における複数セルから成るシーケンスを決定し、そして、vi）複数セルから成る前記シーケンス内の連続したセルの間の各境界上に配置された少なくとも１つの媒介点を決定することからナビゲーション・モジュールと、
前記ナビゲーション・モジュール及び前記ワールド・データベースに結合されたシミュレータであり、iv）で確認されたように、もし前記始セルが前記終セルと対応していれば前記始点から前記終点まで当該シミュレータと結合された画像生成器を介して画面上で前記ディジタル・エンティティを移動するか、或は、もし前記始セルが前記終セルと対応していなければ前記始点から前記終点への各連続した前記少なくとも１つ媒介点まで前記ディジタル・エンティティを移動することから成るシミュレータと、
を備えるシステム。
【請求項２８】
前記ワールド・データベースが前記凸セルの内の前記少なくとも１つ以内における少なくとも１つの移動障害物についての情報を更に記憶するものであり、前記ナビゲーション・モジュールが、ａ）前記少なくとも１つの移動障害物と前記少なくとも１つのディジタル可動エンティティとの間に衝突脅威があるかを更に評価し、そして、ｂ）前記少なくとも１つのディジタル可動エンティティが、衝突脅威が存在する際に前記少なくとも１つの移動障害物を回避する戦略を採用する、請求項２７に記載のシステム。
【請求項２９】
前記ナビゲーション・モジュールが前記シミュレータの部分である、請求項２７に記載のシステム。
【請求項３０】
前記少なくとも１つのディジタル可動エンティティに作用数前記ディジタル・ワールドに追従する前記ナビゲーション・ユニットの動的な調整のためのシミュレータと結合された意思決定モジュールを更に含む、請求項２７に記載のシステム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図３４】
【図３５】
【図３６Ａ】
【図３６Ｂ】
【図３６Ｃ】
【図３６Ｄ】
【図３６Ｅ】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図３４】
【図３５】
【図３６Ａ】
【図３６Ｂ】
【図３６Ｃ】
【図３６Ｄ】
【図３６Ｅ】
【公表番号】特表２００７−５２９７９６（Ｐ２００７−５２９７９６Ａ）
【公表日】平成１９年１０月２５日（２００７．１０．２５）
【国際特許分類】
【出願番号】特願２００７−５０３１６９（Ｐ２００７−５０３１６９）
【出願日】平成１７年３月１８日（２００５．３．１８）
【国際出願番号】ＰＣＴ／ＣＡ２００５／０００４２６
【国際公開番号】ＷＯ２００５／０９１１９８
【国際公開日】平成１７年９月２９日（２００５．９．２９）
【出願人】（５０６３１３９３６）ビージーティ バイオグラフィック テクノロジーズ インク． (1)
【Ｆターム（参考）】
【公表日】平成１９年１０月２５日（２００７．１０．２５）
【国際特許分類】
【出願日】平成１７年３月１８日（２００５．３．１８）
【国際出願番号】ＰＣＴ／ＣＡ２００５／０００４２６
【国際公開番号】ＷＯ２００５／０９１１９８
【国際公開日】平成１７年９月２９日（２００５．９．２９）
【出願人】（５０６３１３９３６）ビージーティ バイオグラフィック テクノロジーズ インク． (1)
【Ｆターム（参考）】
[ Back to top ]