経路探索システム
複数のノード（２９ＡからＧ）を備える仮想環境で目的地ノード（２９Ｇ）に対する新しい経路を生成する方法。該方法は、前記目的地ノードへの過去に生成された経路と関連付けられた１つ以上のノードを識別するノーダル情報を備え、前記新しい経路のために開始ノード（２９Ａ）を画定するために仮想環境のトポロジーを動的に再構成し、前記過去に生成された経路の少なくとも１つのノードを含むことにより、前記目的地（２９Ｇ）への新しい経路を決定するために前記記憶されたノーダル情報を処理する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、仮想世界の表現で複数のポイントに沿って経路を決定するための方法及びシステムに関する。特に、本発明は、目的地への過去の経路と関連付けられた記憶情報を使用する仮想環境内で目的地ノードへの新しい経路を生成するための方法及びシステムに関するが、それに限らない。
【背景技術】
【０００２】
新しい経路は、仮想環境の参加者が手動ナビゲーションモードから自動ナビゲーションモードにトグル(toggle)できるようにするために生成されてよい。仮想世界の参加者が、ナビゲーションシステムの自動ナビゲーションモードとナビゲーションシステムの半自動モード又は直接制御モードの間で切り替える、またはトグルできる能力は、非常に望ましい。しかしながら、ユーザが仮想環境での経路に沿ってナビゲートできるようにするシステムだけではなく、ユーザが現実世界での経路にも沿ってナビゲートできるようにするように構成されたナビゲーションシステムのナビゲーションモードの間で、ユーザがトグルできるようにすることも望ましい。
【０００３】
例えばカーナビゲーションシステム等の多くの従来技術の現実世界システムでは、出発地点と目的地点を入力するユーザによってルートが決定され、ナビゲーションシステムが、ユーザを出発地から目的地までの所定の経路に従わせるため、ユーザが従うための方向を指示することが公知である。しかしながら、ユーザが例えば迂回を実行するために所定の経路を離れることを希望する場合、ナビゲーションシステムは目的地に向かってユーザをリダイレクトし直そうと試みる。通常、ナビゲーションシステムは、ユーザが戻るための元のルートに沿った最も近い点を捜し出し、ユーザは次にその元の経路を再開する。
【０００４】
現在のテクノロジー時代には、三次元仮想現実環境（仮想世界）が定められ、作成されるシステムがますます普及してきている。このようなコンピュータシステムは、オンラインツーリストサイト、ファンタジー世界、賭博、建築上の連絡通路、不動産仲買業（売り家の仮想ツアー）、及びその他多くの、多数の商業的な用途で適用可能である。典型的には、仮想世界は、三次元（ｘ軸、ｙ軸、ｚ軸）で環境をともに緻密に計画する複数のｘ、ｙ、ｚ座標の集合により定められてもよい。仮想世界のトポロジーは、仮想世界の中のオブジェクトが三次元で編成されるように、つまり多くの（本明細書では「ノード」とも呼ばれる）ノーダルポイントの空間的な位置により定めることができる。このケースでは、トポロジーは世界の特定の座標のノードから形成できる論理的なメッシュにより決定される。メッシュは、規則正しく離間されてよい、又は規則正しく離間されなくてもよい。
【０００５】
仮想世界を通してナビゲートするユーザが通り抜けることを許されていないオブジェクト及び壁（又は仮想世界内に存在する他のアイテム）は、衝突可能（ｃｏｌｌｉｓｉｏｎａｂｌｅ）メッシュと呼ばれているものによって実現できる。したがって、衝突可能メッシュは、ユーザがナビゲートしなければならない仮想世界内で形状を定める三次元座標の追加の集合を備えてよい。
【０００６】
ナビゲーションは、コンピュータによって生成された人物、乗り物又はゲームのキャラクタ等の、その世界を通過するいかなるエンティティのための仮想世界内で必要とされる。これは、通常、外部の人間のユーザの制御下にある。従来、仮想環境の多くの商業的な実現は、ゲームエンジンから継承された自己ナビゲーション（ｓｅｌｆ−ｎａｖｉｇａｔｉｏｎ）技法に基づいて構築され、未知の仮想世界の全領域の探査が予想され、高度のユーザ能力が仮定されている。しかしながら、仮想世界の適用が他の商業的な分野にも広がるにつれ、ナビゲーションの機能性が、新しいさらに幅広いグループのユーザ全体の能力と要件に適合するために、進化することが重要である。このようなユーザは仮想世界をめぐるナビゲーションに熟達していない可能性があり、さらに多大な時間を費やして該環境になじむのに乗り気ではない可能性がある。彼らははるかに早く頭が混乱する、あるいは退屈するようになる、あるいはユーザの経験が大幅に改善されない限り重要なコンテンツを完全に見逃す可能性さえある。
【０００７】
我々の日々の生活では、人間は、通常、あちこちに移動するときにナビゲーションで自分たちを手助けするために多様な技法を利用する。我々は、頭が混乱しないようにするために、固定された基準点（ランドマーク）、移動距離の測定、及び方向の変化を使用して、自らの位置と向きに関する考えを保持する。特に多くのゲーム環境におけるケースでのように、テレポート（例えば、該世界の中の２つの異なる点の間を瞬時に移動すること）が適用される場合には、このような技法はそれらが普及していない仮想世界内の新米のユーザに使用できない可能性がある。その結果、経験不足のユーザが、自らを仮想世界にナビゲートするのを助け、彼らが精通していないこと、及び従来の自己ナビゲーションのインタフェースに対するフラストレーションという問題を克服できるようにするために、自動化された経路探索システムを提供することが有利である。その結果、例えば、ある特定のオブジェクトを見る、又は部屋を通過するために最短の経路を見つけるために、仮想世界を通る最善の経路を自動的に計算する多くのシステムが開発されてきた。
【０００８】
従来技術
Ｂａｒｂｅｒは、「コンピュータグラフィックスシーンで経路ネットワークを実現するためのシステムとしての方法」と題される米国特許出願第２００２／０１７５９１８Ａ１号で、ナビゲーションシステムを説明している。Ｂａｒｂｅｒらは、コンピュータグラフィックスシーンの中で少なくとも１つのオブジェクトの運動動作を制御するために経路ネットワークを実現するための方法を説明している。経路ネットワークは複数のノードとセグメントにより形成されている。ノード又はセグメントと関連のある多様なパラメータが、オブジェクトが経路ネットワークに沿って移動するための運動条件を確立するために定められる。Ｂａｒｂｅｒらが説明する経路ネットワークの全てのモードに共通しているのはパラメータＥｎｔｒｙＰｏｉｎｔとＥｘｉｔＰｏｉｎｔである。ＥｎｔｒｙＰｏｉｎｔは指定された経路ネットワークノード又は経路ネットワーク上の他の所定の位置である。しかしながら、Ｂａｒｂｅｒらは経路ネットワークに乗る又は降りるようにオブジェクトを導くための特定のアルゴリズムは何ら開示しておらず、Ｂａｒｂｅｒらが説明する入口点と出口点はシステムの設計者により事前に決定されている。したがって、Ｂａｒｂｅｒが説明しているような世界において、ユーザが、自動的にナビゲートされる誘導経路に従い、手動モードにトグルし、該経路からはずれ、それから自動モードにトグルして戻り、その元の経路を再開することは不可能である。
【０００９】
Ｐｏｐｐｅｎらは米国特許第６，０３８，５０９号で、ネットワーク内で起点から目的地までの経路に従うための一組の指示をユーザに与える、経路探索システムを説明している。ユーザが経路を逸れると、システムは、元の経路から外れているユーザの新しい位置から目的地までユーザを導く新しい経路を再計算する。システムは目的地までの新しい経路を決定するために要する時間量を減少するためにネットワークにリンクを追加する。該拡大されたネットワークを使用して、ユーザの新しい位置から目的地までの新しい経路が決定される。システムが新しい経路を計算するために、ユーザが位置する既存のノード、あるいはユーザが新しい起点として指定するネットワークの既存のノードのどちらかで、新しい起点が決定される、あるいはシステムは、ユーザが経路を再計算するための方法が完了するときに推定される新しい起点にいることができるように、新しい起点がユーザの現在の位置から少し離れていると判断できる。しかしながら、Ｐｏｐｐｅｎらが説明するネットワークは、ノードが固定され、事前に決定されているノーダル(nodal)システムを備える。経路探索システムは、ネットワークの特定のノードに経路を制約するネットワークの固定されたトポロジーによって制約される。
【００１０】
公知の経路探索アルゴリズムは、開始ノードから目的地ノードまでの経路が見つかるまで、考えられる経路、一度に１つのノードを拡大することにより機能する。ノードが試行される順序は、見つけられる最終的な経路の速度と品質（例えば長さ）にとって重大である。横型探索(breadth-first)技法では、アルゴリズムは最初に全てのノードの接近した近傍系を検索し、次にそれらの隣接するノードの近傍系に移動する。対照的に、縦型検索技法では、アルゴリズムは、所定の深さに達するまで毎回子ノードを使用して再帰的に経路を探索し、達するとそれはそのステップを引き返し、他の子ノードを試行する。最良優先探索は、ゴールまでの最短の残りの距離の推定値に基づいて優先的に経路を選ぶ。
【００１１】
ｈｔｔｐ：／／ｗｗｗ．ｉｄｉ．ｎｔｎｕ．ｎｏ／ｇｒｕｐｐｅｒ／ｓｕ／ｆｏｒｄｙｐｎｉｎｇｓｐｒｏｓｊｅｋｔ−２００３／ｆｏｒｄｙｐｎｉｎｇ２００３−Ｊａｎ−Ｈａｒａｌｄ−Ｆｒｅｄｒｉｋｓｅｎ．ｐｄｆに位置する、ノルウェー科学技術大学のＪａｎ−Ｈａｒａｌｄ Ｆｒｅｄｒｉｋｓｅｎによる「コンピュータゲームにおける人工知能のためのミドルウェアソリューション」（第３章−ＡＩ技術）と題される記事は、仮想世界における経路探索技法及びＡ＊アルゴリズムの使用に関する。この文書は、仮想世界を通る経路を計算するときに考慮に入れられるべきである、異なる地形のためのコストの制約の使用、及び計算性能の改善のための（詳細な部分を計算する前に幅広い全体的なルートを見つける）階層経路探索及び（仮想世界の領域をより小さな部分に分ける）ポータルの使用を検討している。この文書での経路探索が基づいている仮想世界の根本的な構造は、２つの代替バージョンを有する。第１は（中間地点と呼ばれている）複数のノードが仮想世界の中に導入され、ノード間の照準線リンクに基づいて経路が見つけられるＰＯＶ（視感度点）手法と呼ばれる。第２の手法は、複数の凸多角形が世界の表面を覆うナビゲーションメッシュを使用することであり、このケースでは、経路探索アルゴリズムは各多角形をノードであると見なし、相応して仮想世界を通る経路を計算する。
【００１２】
さらに、現在では現実世界の部分を通る移動経路のプロットを自動化するためのシステムが存在する。このようなシステムの好例が、ＡＡ組織（ｈｔｔｐ：／／ｗｗｗ．ｔｈｅＡＡ．ｃｏｍを参照されたい）のウェブサイトで提供される「ルートプランナー」ツールである。このようなシステムはユーザの特定の好み（例えば、高速道路を回避すること、最短距離、最短時間等）を考慮に入れる。しかしながら、本発明者は、決して非常に初歩的ではない何かにおいて、ルートがユーザの功利主義的ではない優先順位を考慮に入れることができるシステムを全く知らない。また、このようなシステムは必ず所定の経路（つまり、道路が存在する場所）に沿ってルートを計算することに制限されるため、生成される最終ルートの柔軟性で制限される。
【発明の開示】
【００１３】
本発明は、自動ナビゲーションモードと手動ナビゲーションモードの間でトグルするための手段を提供する、公知のナビゲーションシステムの制限を未然に防ぐ、及び／又は軽減しようとする。本発明によるナビゲーショントグルシステムは、ノーダルポイントの動的に変化するトポロジーを備えるシステムで実現され、誘導経路が動的に生成されてよい。環境内のノード及び環境のノード間の潜在的なリンクのネットワークの位置は事前に決められていないため、ユーザは自動ナビゲーションモードと手動ナビゲーションモードの間でトグルするさらに多くの自由を与えられる。
【００１４】
本発明の態様は、その従属クレームが本発明の好ましい特長を表す、添付の独立請求項によって説明されるとおりである。
【００１５】
それにも関わらず、当業者は、好ましい特長が当業者に明らかないかなる適切な方法で、本発明の態様のいずれかと適切に結合されてよいことを理解するであろう。
【００１６】
本発明によるナビゲーションシステムでは、ネットワークのナビゲーションポイントの位置は事前に決められていない。さらに、トポロジー内で生成されるナビゲーション経路は所定の構成に制限されない。したがって、ユーザが、所定の誘導経路トポロジーから離れるために自動ナビゲーションモードからトグルすると、トポロジーのノーダルポイントはユーザの位置の変化に応じて再定義されてもよい。さらに、ユーザが自動化された経路を再開することを希望し、手動ナビゲーションモードから、ユーザが誘導経路に沿って自動的にナビゲートされるナビゲーションモードにトグルして戻るときには、第１の誘導経路を離れた時点でネットワーク内に存在するナビゲーションノードが再定義されてもよい。
【００１７】
加えて、ユーザはネットワークのナビゲーションノードの内の１つで誘導経路から出るように制限されていない。代わりに、ユーザは任意の点で自由に手動ナビゲーションノードに切り替わることができる。出口ノードは、ユーザが元の誘導経路を離れる点で作成されてよい。出口ノードは、例えば特定のタイプの勢力範囲(sphere of influence)等の１つ以上の特定の特長で拡大されたノードのナビゲーションタイプであってよい。
【００１８】
例えば、本発明の一実施形態では、勢力範囲ノードは、ユーザが手動ナビゲーションモードへトグルするときに作成される出口ノードの周りに動的に生成される。ユーザがこの範囲を超えて自らをナビゲートする場合、ユーザが出発点から目的地まで生成された元の経路に再び加わるというオプションは、期限切れになってもよい。代わりにユーザが元の経路から離れてすごす時間に対する制限時間が、このオプションを期限切れとしてもよい。いずれのケースでも、再び加わるオプションは、ユーザがあまりに遠くまでさまよい（又は非常に長く離れてしまった）元の経路は現在使われていないので、自動的に使用不可能となる。例えば、ユーザが元の目的地の反対側にさまよい、その結果ユーザが完全に異なる角度から目的地に近づくことを希望するであろう場合、元の経路に再び加わる最適経路を決定するために検索が実行されるのは、計算時間／性能の効率的な使用ではないであろう。
【００１９】
ナビゲーションシステムは、初期出発点と初期目的地の間に経路を画定する仮想環境内の点の密度が固定されておらず、２つの点の間の経路を決定する点のトポロジーが経路自体がプロットされるのにつれて動的に変化できるように、多くの条件に従って変化できる、仮想環境内に設けられる。これにより仮想世界環境の中に、ユーザがそれに沿って自動的にナビゲートできる経路を設けることができる。経路のトポロジー及び／又はユーザが該経路に沿って自動的にナビゲートされる速度により、ユーザは１つ以上の関心のあるオブジェクトに遭遇することができる。
【００２０】
１つ以上のオブジェクトであって誘導経路がユーザをそれに向かって誘導しようとするものは、（例えば仮想世界内のそれらの位置に関して）動的に変化してよい。これは特に、ユーザが互いに仮想世界の中のキャラクタを介して対話できる可能性がある仮想環境で当てはまる。例えば、キャラクタの内の１つが同じ仮想環境の中で参加している別のユーザによって制御される場合、動的経路は、そのキャラクタが、ユーザがそれを制御することによって仮想世界で使用されない場合に変化してよい。
【００２１】
本発明は、例えばファンタジー世界又は歴史的な建物又は将来の建物のための設計、あるいは販売のための家等の実際の環境に基づいた世界を含む可能性があり、障害物が壁又は他の障害物を構成する可能性のある、いかなるタイプの仮想世界にも適用できる。上記で使用される意味での表現は、そのような世界を表現する記憶されたデジタルデータを指すことが多い。
【００２２】
有利なことに本発明の構成は、コンテンツプロバイダが仮想世界の中でのナビゲーションのためにいくつかの初期の点を定めることを可能とし、該コンテンツプロバイダが、取られた経路及びユーザが訪問できる関心のあるアイテムに影響を与えることができるようにする技法を採用している。したがって、システムは、最初に定められたナビゲーションポイントの限られた集合だけと比較した、該環境を通る後に生成された経路に沿ったユーザの経験を改善するように自動的に点の数を増やす。
【００２３】
仮想世界を通る経路が特定のナビゲーションポイントに制約されていない先に公知のシステムと比較すると、本発明の実施形態は実際の経路探索手順の間の処理の改善を実現する。これは、全ての新しいナビゲート可能なノードとリンクが視野方向の原則に基づいて加えられたため、当然全ての潜在的な障害物を回避するために、実施形態における経路探索の間に（経路が障害物等を回避するのを確実にする）衝突検出が必要とされないためである。
【００２４】
加えてこれらの実施形態は、指定された所定の道路等に沿ってルートを見つけることに必ず制限される、ＡＡルートファインダ（Ｒｏｕｔｅｆｉｎｄｅｒ）等の先に公知のシステムに優る利点を提供する。対照的に、実施形態では、ユーザは仮想世界の全領域の中でナビゲートできる。
【００２５】
本発明をさらによく理解するために、特定の実施形態は、添付図面を参照して一例としてここで説明される。
【発明を実施するための最良の形態】
【００２６】
本発明者らにより現在意図されている、本発明の最良の態様は、添付図面を参照して説明されるであろう。
【００２７】
本発明は、第１の過去の経路から派生するノーダル情報を含む経路を生成できるようにする。第１の経路を生成できるようにする１つのナビゲーションシステムは、ここで添付図面の図１から図１３を参照して説明される。
【００２８】
図１は、仮想世界を作成し、ユーザが仮想世界内でナビゲートできるようにするシステム１を描いている。システムは、端末３を介してコンテンツプロバイダ（仮想世界の仕様を入力する人間のユーザ）にアクセスでき、別の端末４を介して（仮想世界を見て、ナビゲートすることを所望する）ユーザにアクセスできる、サーバコンピュータ２を備える。描かれているコンピュータ構成は、コンテンツプロバイダが、ユーザがその後アクセスし対話することができる仮想世界を設計し、実現できるようにする、いかなる適切な代替策により置換されてよいことが理解されているが、この特定の実施形態では、両方の端末からサーバ２へのアクセスは例えばインターネット等の汎用ネットワーク５を通る。
【００２９】
簡略な仮想世界環境の概略が図２に示されている。これは、部屋２０を表し、その中に壁２１、扉２２、及び多様な障害物２３、２４、２５を含む。この仮想世界２０の設計を指定するとき、コンテンツプロバイダは端末３を介してサーバ２の中に該環境の形状を表す座標の形式でデータを入力する。データは、ナビゲートするユーザが通過することを許されていない障害物２３、２４及び２５を定義する、衝突可能メッシュを表現する座標を含む可能性がある。
【００３０】
フィーチャ（Ｆｅａｔｕｒｅ）ノード
コンテンツプロバイダは、ユーザが見ることを希望する場合がある部屋内で、関心のあるフィーチャを定義できる。例えば、仮想世界が歴史的な建造物を通るツアーを表現する場合、塑像、家具、絵画及び情報板等のフィーチャを挿入することが所望されてよい。これらは、例えば塑像オブジェクト２６、絵画２７及び情報板（障害物２５）等の、部屋内のオブジェクトによって表現されてよい。
【００３１】
ユーザがこれらのフィーチャにアクセスできるために、コンテンツプロバイダは、ユーザが見る又は対話することができる該フィーチャに関連付けられた、（図３に示されている）フィーチャノード２８Ａ、２８Ｂ及び２８Ｃを定義する。したがってフィーチャノードは基本的に、オブジェクト又は衝突可能なメッシュのどちらかにリンクされる仮想世界の中の点であり、本実施形態では以下のデータ組を有する。
【表１】
【００３２】
ノードＩＤ−ノードのための一意の識別子（例えば、テキスト文字列「ｍｏｎｅｔ＿ｐａｉｎｔｉｎｇ＿０１」又は数値識別子「００５６３」）
フィーチャグループＩＤ−ノードと関連付けられているフィーチャのタイプの識別子であって、例えば情報板は第２のフィーチャグループ「ｉｎｆｏｒｍａｔｉｏｎ＿ｐｏｉｎｔｓ」である可能性があるが、全ての絵画は「絵画」として識別される第１のフィーチャグループ内にあってよい。グループ分けの選択はコンテンツプロバイダと、グループが仮想世界内で識別を希望するフィーチャのタイプに大きく依存する。
【００３３】
リンクされたメッシュ／オブジェクトのオブジェクトＩＤ−これは、フィーチャノードと関連付けられているオブジェクト又は衝突可能メッシュの識別子であり、ノードＩＤ（例えば「ｍｏｎｅｔ＿ｐａｉｎｔｉｎｇ＿０１」）と同じであってよい。
【００３４】
オブジェクトピボットポイントデータのＸＹＺ−これらはフィーチャノードの位置を示す座標である（そして、フィーチャノードが関連付けられているオブジェクト／メッシュの特性から抽出することにより取得されてよい）。
【００３５】
勢力範囲設定値−これらは（３Ｄ世界のために）（例えば、図３に円３１として描かれている）フィーチャノードを取り囲む三次元の球体を形成し、仮想世界を通るナビゲーション経路の計算中に使用される。
【００３６】
ディスプレイ設定値−これらはフィーチャと関連付けられているテキスト／画像に使用される設定値の一部である。
【００３７】
ナビゲーションノード
コンテンツプロバイダは初期に、図３に示されているように仮想世界内に複数のナビゲーションノード（２９Ａ、２９Ｂ、２９Ｃ等）をさらに定義する。本来、これらのノードは、自動経路生成アルゴリズムが該環境を通るルートをプロットするために使用できる、ナビゲーションポイントの簡略な行列を提供する。各ナビゲーションノードに関連付けられているのは以下のデータ組である。
【表２】
【００３８】
ノードＩＤ−ノードの一意の識別子
ノードレベルＩＤ−これはノードのレベルを定め、ノードを様々な部分集合に効果的に分類し、仮想世界を処理効率のための異なる領域に分割するために経路探索プロセスの間に使用できるようにする識別子である。例えば、仮想世界内の２つの異なる部屋はノードの異なる領域によって表現でき、それらの間の出入り口がスイッチノードを備える。処理効率のため、初期に経路は部屋の内の一方のノードだけに基づいて計算できる（このようにしてこの段階で第２の部屋に入る経路を誤って計算するのを省き、後にのみ経路探索計算が該スイッチノードを介して第２の部屋に伸張できるようにする）。さらに、異なる部分集合が重複する領域をカバーできると考えられる（例えば、異なるレベルが同じ領域又はその領域の部分集合のさらに細かい適用範囲を提供する可能性がある一方、ノードの第１のレベルが広い面積のおよその適用範囲を提供する可能性がある）。
【００３９】
ＸＹＺ位置−これらは、ナビゲーションノードの位置を示すｘ、ｙ、ｚ座標である。
【００４０】
ＬｏＳデータ−このデータフィールドは当初、空となるが、後に現在のノードが照準線(Line of Sight)（ＬｏＳ）を有する全ノード、つまりそれがリンクすることができる全ノード（詳細については以下を参照されたい）のリストを含むために使用されてよい。
【００４１】
ＬｏＳ制約設定値−コンテンツ製作者は、角度ＬｏＳ制約（つまり、ノードが、角度範囲、その角度範囲でその視角に該当する場合にだけ、リンクするノードを検索するのを許される、詳細については以下を参照されたい）を手動で定めることを選んでよい。
【００４２】
ＦｏＶ制約設定値−コンテンツ製作者は、そのノードでユーザに表示できる画像の範囲を制約する視野（ＦｏＶ）の角度制約を定めることを選んでよい（例えば、ノード２９Ｆの場合、ＦｏＶはユーザがオブジェクトを見ることを確実にするために塑像オブジェクト２８Ａに向かう角度方向内で制約されてよい）。
【００４３】
方向制約設定値−いくつかのナビゲーションノードの場合、コンテンツ製作者は、方向制約設定値を定めることによってユーザに許されている向きを、彼らがノードに近づくにつれて制約することを選んでよい。これにより、計算された経路は強制的にある特定の方向からノードに近づく。
【００４４】
コンテンツプロバイダはこのようにして、ナビゲーションノードを使用することにより、潜在的なユーザが環境の中で関心のあるフィーチャを最良に経験できる仮想世界内の重要な位置を定めることができる。コンテンツプロバイダは、完全に自動化されている他のシステムに比較して、ユーザの関心のあるフィーチャの経験の質を高めるために、正確な位置、接近の方向（方向設定値）、及び視角（ＦｏＶ制約設定値）を定めることができる。
【００４５】
処理
以後の処理は、図１３の流れ図を参照して説明される。ノードデータがシステムに入力された（ステップ４０）後、ノードマトリックスが仮想世界のために自動的に作成される（ステップ４１）。これは、各ナビゲーションノードにとって、それがリンクできる全ての他のナビゲーションノードを識別する。ノードリンクは２つのノードのためのＬｏＳ（照準線）の基本的な規則に従って計算される。これは衝突可能なメッシュ及びノードのＬｏＳをトリミングすると見なされているあらゆる他のオブジェクトを考慮に入れる（つまりノード間の経路は障害物を通過できないため、リンクは障害物を通過することができない）。図４は、仮想世界２０内のナビゲーションノードのための、考えられる全てのＬｏＳリンク（つまり、ノード２９Ａ、２９Ｂ等をリンクする線）を描いている。例えば、ノード２９Ａはノード２９Ｂと２９Ｆの両方に直接的な照準線を有するが、２９Ｃは障害物２３を通過するであろうため、２９Ｃには直接的な照準線を有さない。図４の仮想世界２０のノードマトリックスは表形式で以下に表現される。
【表３】
【００４６】
この段階では、各ナビゲーションノードのデータセットには、可視パートナーのＸＹＺ位置を含む、これの全ての可視パートナーに関するＬｏＳデータが与えられている。いかなる他のナビゲーションノードに対する照準線も有さないあらゆるナビゲーションノードは無効と見なされ、システムから削除されてもよい。
【００４７】
コンテンツプロバイダが特定のナビゲーションノードに対するあらゆるＬｏＳ制約を指定した場合には、それがノードリンクを検索することを許される角度をトリミングするであろう。これは該ノードのための「ＬｏＳ制約設定値」を使用して制御され、それ以外の場合許された３６０°のＬｏＳをスライスする度数値を備える。このケースでは、そこで示されているリンクのいくつかが許可されないであろうために前記ノードマトリックスは異なるであろう。この機能性により、コンテンツプロバイダは、それらの周りの他のノードを無視するノードのチャネルを作成でき、ノードが所望されていないノードマトリックスで中断を生じさせることができる。このようにしてコンテンツプロバイダは仮想世界内でユーザによって取られるルートに影響を及ぼすことができるため、これはユーザ経験を改善できる。
【００４８】
処理の次の段階は、すでに定められているＬｏＳリンクに基づいて追加のノードに追加する。しかしながら、それが発生する前に、システムはどのリンクが新しいノードのためのベースとして使用されるのか／使用されないのかを決定するために、全てのリンクをチェックする（ステップ４２）。特に、システムは（２９Ｃから２９Ｄリンクを交差する２９Ｂから２９Ｅリンク等の）あらゆる交差リンクを探し、新しいノードのベースとして使用するために利用できないとして交差リンクの最も長いものを記す。この実施形態では、データフラグが、このリンクが「細分されるべきではない」ことを示すために（ノードマトリックス又は個々のノードのＬｏＳリンクデータのどちらかの中の）リンクに関連付けられている。この影響されたリンクは、図５に点線で示されている。
【００４９】
処理の次の段階は、ノードのさらに密集したマトリックスの自動作成を含む（ステップ４３）。これは、各中間点で（細分ノードとも呼ばれる）新しいナビゲーションノードを追加するために、既存のナビゲーションノードの間でＬｏＳリンクを細分することにより達成される（ステップ４４）。図６は、これらの細分されたノード（３０Ａ、３０Ｂ、３０Ｃ、．．．等）を示す。ステップ４３を通る各サイクルの間により多くの新しいノードが追加されるにつれて、ノードの密度は、最大許容ノード密度まで高まる。この密度は、例えばノードからその最も近い近傍系までの最小許容距離を指定することによって、コンテンツプロバイダによって事前にあらかじめ定められてよい。各新しいノードが追加された後、システムは、新しいノードが密度基準を満たしているかどうかをチェックする（ステップ４５）。それが許容密度基準外に含まれる場合、新しいノードが削除される（ステップ４６）。それ以外の場合、ノードは保たれる。一旦あらゆるＬｏＳリンクが細分のために調べられると（ステップ４７）、システムはあらゆる新しいノードが最後の通過の間に追加されたかどうかをチェックする（ステップ４８）。通過中に新しいノードが作成されないと、システムは終了する（ステップ４９）。
【００５０】
各通過の場合、新しいノードが追加された後、あらゆるノード（ナビゲーションノードとそれぞれの新規に作成された細分ノードの両方）のＬｏＳデータが、複数の新しい考えられるＬｏＳリンクを全て考慮に入れるために更新される（ステップ５０）。図７は、ノードの間にさらに多くの考えられるＬｏＳリンクを有する新規に作成された密度の濃いマトリックスを描いている。
【００５１】
システムはここで、新規に追加されたノードの内のどれが有効であるのかをチェックする（ステップ５１）。ノードは、それがそれ以外の場合互いに照準線を有さない任意の２つの他のノードにリンクする場合に有効と定められる。これは、図８のノード３０Ａに描かれている。この図面では、明確にするために、描かれているノードとリンクだけがノード３０Ａとノード３０Ａがリンクする７つの他のノードである。ノード３０Ａは、ノード２９Ｂと３０Ｆの間等、多くの異なる組のノードのためのブリッジとしての機能を果たす（つまり、ノード３０Ａは互いにＬｏＳを有さない２つのノードの間の接続を形成する）ことが明確に分かる。したがって、ノード３０Ａは有効であり、事実上、それが有効なノードとして定められるＬｏＳを有さない１組のノードに接続されることだけを必要とする。あらゆる無効ノードは削除される。
【００５２】
図９は、ノード３０Ｂのための同じ手順を示す。ノード３０Ｂは有効として定められている。しかしながら、この段階で、２つのノード間のブリッジを支援しない３０Ｂリンクのいずれかが削除される。これは、ノード３０Ｂと２９Ｃの間のリンクにも当てはまる。ノード２９Ｃはすでに図９に示されている全てのノードに対する照準線リンクを有する（そして、相互にノード３０Ｂは２９Ｃにリンクされた全てのノードに対する照準線も有する）ため、リンク３０Ｂ−２９Ｃは互いに照準線を有さないいかなるノードの組の間でブリッジするのに役立たず、リンク３０Ｂ−２９Ｃは削除される。
【００５３】
ノード３０Ｃはすでに図９の中に全てのノードに対して照準線を有しているため、リンク３０Ｂから３０Ｃも図９から冗長であるように見える。しかしながら、リンク３０Ｂから３０Ｃは、例えば図７から分かるように（互いに照準線を有さない）ノード３０Ｂと３０Ａを架橋するため、実際には有効であり、したがってリンク３０Ｂから３０Ｃは削除されないであろう。
【００５４】
全ての新しいノードについてこのようにして有効性チェックが実行され、他の２つ（３０Ｅと３０Ｈ）がそれぞれ図１０と図１１に示されている。
【００５５】
有効性チェックが新しいノードに対して実行された後、システムは再びあらゆる交差リンクがないかチェックする（ステップ５２）。交差リンクは以後の細分のサイクルで使用されるべきではないリンクである。リンクは、互いに交差するリンクを探し、最も長いリンクを「細分されるべきではない」とフラグを立てることによって、以前のように識別される。これは全てのリンクについて実行され、結果として生じるリンクマトリックスが（点線が、さらに多くのノードを追加するために細分のために将来使用されるべきではないそれらのリンクを描く）図１２に描かれている。
【００５６】
したがって細分の１つのサイクルが完了され、この後にもノードの数は２倍以上になり、ノード間の接続性は大幅に高まった。例えば、ノード２９Ｄは以前は２９Ｂ、２９Ｃ及び２９Ｅに対するリンクだけしか有していなかったが、現在ではさらに３０Ｂ、３０Ｃ、３０Ｅ及び３０Ｆにリンクしている。
【００５７】
細分の追加サイクル（ステップ４３）は、システムが、仮想世界の中の衝突不可能な環境を緻密に計算する適切に濃い密度のノードのマトリックスを作成するまで、繰り返されてよい。有利なことに、以後の経路探索計算の間、マトリックスノードは全てナビゲート可能な領域に制約されているため、リアルタイムで衝突データを計算する必要はない。さらに、該環境におけるノードの密度が高くなるにつれ、システムは最初に定められたノードマトリックスを用いるよりはるかに効率的な経路を生成でき、典型的には現実世界の環境をナビゲートするときにユーザが慣れている動作のタイプに従う、仮想世界を通るはるかに円滑な経路を与えることによってユーザ経験を強化する。
【００５８】
一旦経路が計算されると、さらに補間する、したがってさらに行程を円滑化するためにスプラインが生成される。本実施形態では、一旦ある特定の経路に沿ってスプライン(spline)が生成されると、該経路に沿ったデフォルトの速度が設定される。本実施形態では、これは、ほとんど関心のない領域でのかなりの高速と、関心のあるフィーチャの周りでの相対的な低速との間で、変化するように設定される。理想的には、これは最も関心のあるフィーチャノードで最小値を有し、これらの点の間で最大の速度を有するように、速度を円滑に変化することにより行われる。
【００５９】
前記の実施形態では、ノード密度基準は新しいノードと既存のノードの間の最小許容距離に関して指定されるが、これはノード密度を指定し、試験するためのいかなる他の適切な機構によっても置換できるであろう。別の考えられる方法は、アルゴリズムが終了しなければならない前に細分のサイクルの最大許容数を事前に指定することである。
【００６０】
前記の実施形態では、新しいノードが有効であるかについてのチェックは、ノードが他の２つのノードの間のブリッジとしての機能を果たすかどうかをチェックすることを含むが、それぞれの新規に追加されたノードが有効であるかどうかを定めるために使用されてよい代替の／追加の基準は、新しいノードがノードの任意の組の間でさらに短い経路を提供するのを支援するかどうかをチェックすることである。
【００６１】
経路探索
前述されたように、Ａ＊アルゴリズムは必要とされる処理時間と見つけられる経路の質の両方に関して最適の経路探索アルゴリズムである。開始ノードと目的地ノードは事前に定められ、アルゴリズムは開始から目的地までの最善のルートを見つけるために複数の異なる経路を探索する。仮想世界２０を通るツアーを希望し、扉２２で入り、適切なインタフェースを介して自分が情報板２５に接近することを所望することを示したユーザのケースを考える。
【００６２】
開始ノードはノード２９Ａとして定められ、目的地ノードは２９Ｇとして定められる。Ａ＊アルゴリズムはノードの２つのリスト、つまり、すでに探索されたノードのリスト（クローズドリスト）と、探索されたが、まだそれら自体探索されなければならないノードにリンクされたノードのリスト（オープンリスト）を維持することによって動作する。アルゴリズムはオープンリストからノードを取り、そのノードが目的地ノードである場合には、アルゴリズムは終了する。目的地ノードではない場合、選ばれたノードにリンクされている全てのノードがオープンリストに追加される。Ａ＊アルゴリズムは、それがノードの検索を誘導するために推定値を使用するため、発見的な方法として知られている。特に、オープンリストからどのノードが次に選択されなければならないのかを決定するために、全てのノードが評価関数ｆ＝コスト＋ヒューリスティック(heuristic)を有し、オープンリストから次に最新のノードとして選択されるノードがｆの最低値を有するノードである。
【００６３】
コストは、開始ノードから最新のノードまでのこれまでの経路の質の測度である（つまり、簡略なＡ＊アルゴリズムの場合、これは開始ノードと該ノードの間の経路内の全てのリンクの長さの総計となるであろう）。ヒューリスティック(heuristic)関数は最新ノードから目的地ノードへ到達するためのコストの推定値である。Ａ＊アルゴリズムの結果はコストとヒューリスティック(heuristic)関数の選択にかなり依存し、最適経路を生成できるようにするのは、本発明の実施形態のための評価関数で使用される特定の加重値及びコスト値である。
【００６４】
本実施形態のコスト関数は、あらゆるユーザの特殊な優先傾向とともにルートの多様な要因を考慮に入れる。コスト関数は、以下の形式の加重和である。
【数１】
【００６５】
ここで距離はこれまでのリンクの長さであり、ｗ１は、経路が可能な限り短いことがそれらにとってどれほど重要なのかを示す現在のユーザに帰される重みである。Ｉｎｔｅｒｅｓｔ＿ｃｏｍｐｏｎｅｎｔは、ノード（複数の場合がある）がこれまでどれほど興味深かったのかの測度を示している（しかし、我々はコスト関数を最小限にすることに注意を向けているので、ｉｎｔｅｒｅｓｔ＿ｃｏｍｐｏｎｅｎｔ値が低いほど、ノードはこれまで興味深かった）。このようにして本実施形態では、以下の形式のこれまで構築された部分的な経路に含まれる１つ以上のノードの合計が使用される。
【数２】
【００６６】
ここでｗ２は問題のノードに関連付けられているフィーチャグループに示されているパーセンテージ重み関心（ｐｅｒｃｅｎｔａｇｅ ｗｅｉｇｈｔｉｎｇ ｉｎｔｅｒｅｓｔ）であり、関心は、ノードが、該ノードに関連付けられている対応するフィーチャにどれほど強力に関連付けられているのかの測度である。したがって、本実施形態では、ナビゲーションノードが０という関心値を有するが、（通常、ユーザにとって非常に関心のある）フィーチャノードは関心値１を与えられてよく、したがって前記のように合計されるときにはさらに高いコストを示す。言及されたように、重みｗ２は、それらがそれぞれのフィーチャグループの関心のあるフィーチャにアクセスすることがユーザにとってどれほど重要であるのかの測度を示す。
【００６７】
最後に、角度は各ノードの入口リンクと出口リンクの間で角度がどれほど大きく直線から逸れるのかの合計（または平均）を表しているので、角度は、経路が今までのところどれほど小刻みに動いたのかの測度を示す。重みｗ３は、経路がほんの少ししか小刻みに動かないことがユーザにとってどれほど重要であるのかの測度を示す（つまり、高い値（例えば１００％）は、ユーザが波状の経路を回避することを好むことを示すであろうが、ｗ３のゼロ値は、経路がどれほどくねくねしていたのかをユーザが気にしていなかったことを示唆する）。
【００６８】
ヒューリスティックは現在のノードから目的地ノードに到達するためのコストの推定値であり、このために考えられる１つの選択肢は以下である。
【数３】
【００６９】
したがって、本実施形態のヒューリスティックは所望に応じて、代わりに距離、関心、及び角度の重みｗ１、ｗ２、及びｗ３の何らかの測度を含むことができるが、該ヒューリスティックは、目的地へのユークリッド距離（つまり現在のノードから目的地ノードまでの直線）に基づいている。
【００７０】
したがって、最終的な目的地ノードに達するまで、システムは評価関数を使用するノードについてＡ＊アルゴリズムを通る。重要なことには、重みｗ１、ｗ２、及びｗ３はユーザプロファイルに応じて変化できる。
【００７１】
ユーザプロファイルの定義
適切なインタフェース（図示せず）により、ユーザは自らのプロファイル（例えば、自分たちが特に何に関心があるのか、及び彼らが仮想世界をどのようにナビゲートしたいのか等）を定めることができる。ユーザプロファイル設定値は、次にＡ＊アルゴリズムに使用される前記の重みに組み込まれ、結果的に異なるユーザのために異なる経路を生じさせることになる。ユーザ関心を重みに変換することにより、そのユーザのための最適経路を生成できるように異なるルートを互いに対して比較できるようになる。特に関心のあるフィーチャ（絵画、名所旧跡等）を訪れることに興味があるユーザにとっては、システムが２つの点の間の最も速い又は最も短いルートを計算しないのが実状である可能性が高いことが分かる。むしろ、最低のコスト経路（つまりそのユーザにとって最善のルート）は、可能な限り多くの関心のあるフィーチャを訪れる経路である。
【００７２】
ユーザは、仮想世界に最初に入るときに自分たちのプロファイルを入力してよい。いくつかのオプションは以下を含む。
【表４】
【００７３】
最初の５つのオプションはオーバーライドであり、したがって重み付けされない。例えば、ユーザが「常に最短経路を選択する」をＯＮに選択した場合には、関心のあるフィーチャの重み付けｗ２は不適切になり、ゼロに設定される。
【００７４】
最後の５つのオプションは全て重みが付けられており、重み付けは分散されているが、それらは全て正規化されなければならない（例えば合計で１００％まで加算する）。ユーザにとって重要ではなく、重みが与えられないオプションは不適切と見なされ、経路探索のプロセスでは考慮に入れられない。
【００７５】
動的ナビゲーションノード
コンテンツプロバイダにより初期に定められた固定されたナビゲーションノード（２９Ａ、２９Ｂ、２９Ｃ等）に加えて、システムはまた動的ナビゲーションノード（図示せず）を含んでもよい。これらのノードは、それらがユーザにとって生成される経路の一部を形成できるが、ユーザがそれらを移動することができるため強化された機能性を提供することができるという意味では、ナビゲーションノードのように動作する。動的ナビゲーションノードはユーザによってあちこち移動できる仮想世界環境の中の対話型メッシュオブジェクトと関連付けられている。ユーザは、動的ナビゲーションノードを目的地点にすることを希望すると指定することができ、経路はその位置に対して計算される。
【００７６】
動的ナビゲーションノードが他のナビゲーションノードから大きく離れた距離に配置される場合、前述された細分プロセスは、適切なノード密度がその領域で達成されるまで新しいノードに代わるように使用されてよい。これによりノードまでの円滑な経路が計算できる。
【００７７】
動的ナビゲーションノードがあらゆる他のナビゲーションノードへの照準線なしに（つまり死角に）配置される場合、該ノードは無効と定められる−（依然として本実施形態では存在するが）ノードマトリックスから失われ、ユーザは該ノードを目的地に選択するのを妨げられる。代わりに、システムはユーザが死角に該ノードを配置するのを妨げてよく、該ノードを有効な位置に移動することだけを可能にする。
【００７８】
スイッチナビゲーションノード
固定されたナビゲーションノードと動的ナビゲーションノードに加えて、システムは、コンテンツ製作者により定められるスイッチナビゲーションノード（図示せず）も含んでよい。前述されたように、ナビゲーションノードはレベルＩＤを有し、ノードがどのレベルに属するのかを指定し、効果的に、より効率的な経路計算のために異なる部分集合にノードをグループ分けする。例えば、仮想世界が２つの異なる部屋からなる場合、一方の部屋の中のナビゲーションノードは１つのレベルに属していると定められてよく、第２の部屋のナビゲーションノードは異なるレベルに属する。一方の部屋の経路探索プロセスの間、違うレベルのノードを考慮に入れる以外は、そのレベルのノードだけが評価される。スイッチノードは、次に１つのレベルから第２のレベルにスワップする機能性を提供する（例えば、スイッチナビゲーションノードは２つの部屋間の出入り口に配置される可能性がある）。
【００７９】
各スイッチナビゲーションノードと関連付けられているのは、以下のデータセットである。
【表５】
【００８０】
ノードＩＤ−ノードのための識別子
ノードレベルＩＤ＃１−第１のレベルのための識別子
ノードレベルＩＤ＃２−第２のレベルのための識別子
ＸＹＺ位置−これらはスイッチナビゲーションノードの位置を示すｘ座標、ｙ座標、ｚ座標である。
【００８１】
ＬｏＳデータ−これは、現在のノードが照準線（ＬｏＳ）を有する（両方のレベルの）全てのノードのためのデータを示す。
【００８２】
切り替えデータ−生成された経路が、あるレベルのナビゲーションノードから他のレベルのノードに切り替わることができるとき／できないときの基準を示す。
【００８３】
イベントフィーチャノード
前述されたように、コンテンツプロバイダは、仮想世界の中の関心のあるフィーチャと関連付けられているフィーチャノード（２８Ａ、２８Ｂ、２８Ｃ等）を定めることができる。コンテンツ製作者は、彼らが仮想世界の中のユーザに反応する余分な機能性を有するイベントフィーチャノード（図示せず）も定めることができる、あるいは特定の所定の時にだけアクティブである。
【００８４】
これらのイベントフィーチャノードは、システムの機能性を、複数のユーザが環境と、及び互いと対話できるゲーム用プラットホーム及び対話型オンライン環境プラットホームに拡大する（例えば、イベントフィーチャは爆発、又は対話型チャットルーム／レースイベントの開催と閉幕をシミュレートしてよい）。コンテンツプロバイダは、イベントフィーチャがいつアクティブとなるのか／イナクティブとなるのか、あるいはそれがどのトリガに応えるのかを指定しなければならない。例のデータセットは以下のとおりである。
【表６】
【００８５】
ノードＩＤ−ノードの識別子（例えば、テキスト文字列「爆発」）
フィーチャグループＩＤ−ノードに関連付けられているフィーチャのタイプの識別子
トリガデータ−イベントフィーチャノードをアクティブにさせる条件
ピボットポイントデータのＸＹＺ−これらはイベントフィーチャノードの場所を示す座標である。
【００８６】
勢力範囲設定値−これらは（三次元世界のために）フィーチャノードを取り囲む三次元球体を定める。しかしながら、標準的なフィーチャノードに使用される設定値に加えて、これらはさらに、勢力範囲が経時的に劣化できるようにしてよい時間に依存するフィーチャを含む。
【００８７】
時間設定値−これらは、イベントフィーチャノードがいつアクティブになるのか／イナクティブになるのかを定める。
【００８８】
ディスプレイ設定値−これらは、制約時にフィーチャと関連付けられているテキスト／画像のために使用されなければならない設定値である。
【００８９】
追加の機能性
前記に説明されたように、処理段階と経路探索段階の結果、ユーザを該環境に連れて行くために使用されるであろうスプライン経路を生じさせる。したがって、スプライン経路は、それぞれ次のノードに対するリンクによって接合される複数のノードを備える。システムは、さらにユーザ経験を改善するためにスプラインを補間することによりこの経路への平滑化を適用する。
【００９０】
リアルタイムディスプレイの間、ユーザが該環境を誘導されるとき、彼らは自分の視野を制御するための追加のオプションを有する。前述されたように、コンテンツプロバイダは、ユーザが関心のあるフィーチャを見失わないことを確実にするために、特定のフィーチャノードに適用されなければならない特定の視角（ＦｏＶ制約）を指定できる。ユーザは、この自動視野プレゼンテーションを操作する、又は代わりに手動で自身の視野を制御するかのどちらかのために、トグル制御を選ぶことができる。
【００９１】
前述された実施形態では、ノードのさらに密度が濃いマトリックスを作成する処理段階が、コンテンツプロバイダが仮想世界内でコンテンツを定めた後であるが、システムがその世界の中でナビゲートすることを所望するユーザによって使用される前に、発生することが説明されている。もちろん、代わりに、システムがユーザによって使用されている間に、リアルタイムで実行されるこれらの細分されたノードを追加する処理段階の一部又は全てのどちらかが可能である。事実上、代替の構成は、仮想世界が多くの動的に移動するオブジェクトを含むときに（例えば、都市の仮想環境は移動する車、バス等を含む可能性がある）特に望ましい。この動的なケースでは、（建物等の静的なオブジェクトのための）何らかの細分だけが、ユーザがシステムにアクセスする前に事前に実行でき、残りの処理は、ユーザが経路が作成されるのを所望することを指定するたびに発生する余分なノードを追加する。処理段階はこのようにして、ユーザが経路が作成されるのを所望する瞬間に、これらの動的オブジェクトの位置を考慮に入れる。この機能性は、細分が発生する（例えば、仮想都市の中の通り）世界内のいくつかの領域、及びそれらが静止オブジェクト（例えばいくつかの建物の内部）だけしか含んでいないために、動的細分が発生しないときの世界内の他の領域を定めることによって、補足できるであろう。これは、（前述された）スイッチノードが異なる領域を区切るために使用されるときの典型的な例である。
【００９２】
さらに、経路生成手順のためにユーザによって選択される開始点と目的地点に対応する新しいノードを作成することが、リアルタイムで必要である可能性がある。ノードがこれらの場所にすでに存在していない場合には、システムはこのようなノードを自動的に作成するために使用されてよく、さらにすでに存在するノードマトリックスにそれらをリンクするために、開始ノードと目的地ノードに近い領域だけで新しく細分されたノードを追加するために処理を使用してよい。
【００９３】
複数のノードを備える仮想環境内で目的地ノードまでの新しい経路を生成する方法は、ここで説明される。該方法では、前記目的地ノードへの過去に作成された経路と関連付けられている１つ以上のノードを識別するノーダル情報が、新しい経路を決定するために処理される。処理は、単に、過去の経路に関連付けられているノードの１つ以上の勢力範囲(spheres of interest)及び／又はｉｎｔｅｒｅｓｔ＿ｃｏｍｐｏｎｅｎｔを更新し、前述された経路探索プロセスを繰り返すことを備えてもよい。代わりに、新しい経路を決定するために、前記の記憶されたノーダル情報に関してさらに複雑な処理が実行されてもよい。
【００９４】
特に、新しい経路は、過去の経路に沿って自動的にナビゲートされ、自動ナビゲーションモードから手動ナビゲーションモードに切り替わったユーザが、過去の経路の目的地まで自動ナビゲーションモードを再開できるようにしてもよい。これは、目的地ノードが移動した場合も含む、仮想環境内の１つ以上のノードが動的に変化している前記経路探索システムを使用しても実現できる。本発明の１つの実施形態では、過去の経路の妥当性検査は、これが目的地までの過去の経路に含まれていたノードの位置及び／又は特徴の変化のためにＬｏＳ又は他の制約に関して、もはや有効ではない可能性があるので実行される。過去に記憶されていたノーダル情報を再利用するための本発明のこの態様は、添付図面の図１４から図２２を参照してここでさらに詳細に説明されるであろう。
【００９５】
本発明の一実施形態は、仮想環境内で開始ノードから目的地ノードへ生成された第１の経路の一部への戻り経路を生成する方法を備える。第１の経路は、仮想環境のノーダルトポロジーが、経路が開始しなければならない点で追加のナビゲーションノードを含むように動的に再構成できる、どんな適切な経路生成プロセスによっても作成できる。
【００９６】
図１４から図１７では、ステップは、本発明の多様な実施形態に従って示される仮想環境内の、（ナビゲーションモードを切り替える又は変更することに同等となるように本文脈で定められる）ナビゲーションモードの間でトグルする方法と関連付けられて示されている。
【００９７】
本明細書において上述されている経路探索システムは、ユーザが自動的にナビゲーションされる（ステップ６２）初期原点から初期目的地までの経路を生成するために使用される（ステップ６０）。経路の原点は経路探索システムのナビゲーションノードと同一場所に配置されてよいが、経路探索システムは、ユーザが目的地まで自動的にナビゲートされることを要求する点で、開始ナビゲーションノードを自動的に作成してよい。同様に、目的地は自動経路生成のための目的地ナビゲーションノードに配置されてよいが、配置されない場合には、経路探索システムが、ユーザが所望される目的地を定めた目的地ナビゲーションノードを生成するであろう。
【００９８】
経路に沿った点では、経路はもはやアクティブにナビゲーションされなくなる。例えば、ユーザは、図１４で、初期の自動的にナビゲートされたナビゲーションモードから手動ナビゲートモードに切り替える（ステップ６４）ために、トグルをアクティブ化する。この出口点は経路のナビゲーションノードと同一場所に配置されてよい、あるいは同一場所に配置されなくてもよい。図１４から図２２に示されている実施形態では、これは経路のノード間にあるので、新しい出口ノードＦが出口点で生成される。しかしながら出口点は必ずしも経路のノードと一致する必要はない。このような状況では、出口ノードは作成されてよい、あるいは代わりに、経路上の出口ノードの前又は後のノードは、出口ノードとなるように定められてよい。図１８は、ＡからＥまでの経路に沿ってナビゲートするユーザが、経路のノードＢとＣの間の出口点でどのようにしてトグルオフ(toggle off)してよいのかを示している。
【００９９】
経路のノードに関する情報は、経路がもはやアクティブにナビゲートされなくなるときに記憶される。このようにして、経路の開始ノードと目的地ノードは、あらゆる中間ノードに関する情報と共に保存される。新しい出口ノードが定められる／作成される場合、これに関する情報も記憶される。その結果、ユーザは経路から自由自在に逸れ、自分が自動ナビゲーションモードを再開することを希望すると判断するまで、手動ナビゲーションモードを使用して探索できる（ステップ６６）。
【０１００】
図１４から図１７に示されている本発明の実施形態では、経路探索システムは、新しい経路を決定するときに、元の経路の記憶されているノーダル情報を処理する過去の経路の目的地ノードまでの新しい経路を生成しようとする。図１４、図１５、及び図１７では、誘導経路までの戻り経路が、目的地までの新しい経路を生成することにまつわる計算上の複雑さを削減するために１つ以上の基準に従って決定される。
【０１０１】
図１６では、記憶されているノーダル情報が増加したｉｎｔｅｒｅｓｔ＿ｃｏｍｐｏｎｅｎｔで更新され、新しい経路探索プロセスがこの増加したｉｎｔｅｒｅｓｔ＿ｃｏｍｐｏｎｅｎｔで実行される。これにより、新しい経路は元の経路と交差する可能性が高くなる。新しい経路が過去に生成された経路と交差する場合、目的地まで続行するために記憶されているノーダル情報を再利用できる。代わりに、図１７が示すように、新しい経路を目的地まで完全に無関係に再生成することが可能であるが、過去の経路に関連付けられているノードのｉｎｔｅｒｅｓｔ＿ｃｏｍｐｏｎｅｎｔを増加することによって、ユーザが過去に生成された経路に類似した経路を再開する可能性が高い。過去の経路に関連付けられているノーダル情報を再利用することにより、目的地までの新しい経路はさらに迅速に且つ効率的に決定でき、ユーザが自動ナビゲーションモードを再開する前に望ましくない遅延を経験するのを妨げる。これは経路が動的に生成されているときに特に有利である。
【０１０２】
本発明によると、生成された経路は経路探索システムにより許可された最適経路でなければならない。これは、元の誘導経路に戻る短くした経路であってよいが、必ずしも、ユーザが経路に沿って進行するにつれて動的に変化できる自動化された経路システムを定めるノードのネットワークのトポロジーのための可能性に起因するわけではない。
【０１０３】
ネットワークトポロジー自体が仮想環境とともに自立的に進化する可能性のために、オリジナルの経路は、ユーザが、元の経路のフィーチャが、元の経路がユーザプロファイルオプションに一致するために依然として関連性があるかどうかを判断するために、自動ナビゲーションモードにトグルして戻る（ステップ６８）ことを選択する点で再び有効になる。
【０１０４】
元の経路が依然として有効である場合には、新しい開始ノードがトグルバックポイント（ユーザが自動ナビゲーションを再開することを希望する点）で作成される（ステップ７０）。しかしながら、経路が無効である場合には、元の経路データは廃棄される（ステップ７２）。この後者のケースでは、目的地ノードだけを保持する新たな経路検索が開始される（ステップ７４）。代わりに、ユーザは元の経路に再び結合し続けることもできるが、これがもはや推奨されていないことを示すための警告が表示される（ステップ７２）。
【０１０５】
元の経路が依然として有効である場合、トグルバックポイントで生成された新しい開始ノードは次に、前述された経路探索システムを使用して戻り経路を生成するために使用されるネットワークに接続される。
【０１０６】
図１４では、戻り経路は、新しい開始ノードから、出口ノードから元の経路の目的地ノードまでの間の元の経路に沿って定められる全てのノードまで、平行ノード検索を実行することによって生成される。これらのノードは、それが最初に作成されたときの経路に沿って同じ位置にある必要はない。つまり元の経路の実際のトポロジーは進化した可能性がある。特定の新しいノードが、最初に誘導された経路に沿って現在存在する可能性がある、及び／又は最初に誘導された経路に沿ったノードのいくつかがもはや存在しないことも考えられる。したがって、高い関心フィーチャ重み又は大きな勢力範囲を有する移動オブジェクトと関連付けられているノードが移動した場合には、元の経路は相応して変化した可能性がある。本発明の一実施形態では、元の経路に沿った最も近いノードが一旦決定されると、元の経路に沿ったノードはそれ以上決定されない（ステップ７８）。これにより、最も近いノードの前の全てのノードを廃棄できるようになり、目的地までの誘導経路に沿ったままである以後のノードだけがとどまる。
【０１０７】
次に、ステップ７８で識別された最も近いノードに経路探索システムを使用して戻り経路が生成され、これは目的地まで最初に誘導された経路に沿って残る以後のノードと結合される（ステップ８０）。
【０１０８】
一旦ステップ８０で新しい誘導経路が生成されると、ナビゲーションシステムは次に目的地ノードに向かって、新しい誘導経路に沿ってユーザを自動的にナビゲートする（ステップ８２）。ユーザが目的地ノードに到達する（ステップ８４）と、自動ナビゲーションは停止し、ユーザは手動ナビゲーションを再開する（ステップ８４）。
【０１０９】
図１５、図１６及び図１７は、本発明のこれらの異なる実施形態における同等なステップについて、図１４に使用されている同じ番号付け方式を保持する。
【０１１０】
図１５では、仮想環境内のナビゲーションモード間でトグルする方法の別の実施形態が示され、図１５では図１４のステップ７８はステップ８８に置換される。
【０１１１】
図１５に示されている実施形態によると、元の経路が依然として有効である場合、新しい開始ノードは、図１４のステップ７６で説明されたのと同等な方法でノードのネットワークに接続される。しかしながら、戻り経路は元の経路の出口ノードだけに経路探索を実行することにより生成される。元の経路データに沿った残りの点が取り出され、出口ノードの前の全ての点が廃棄される。このオプションは、出口ノードがそれに関連付けられている進入角度を有する場合には使用できない可能性があり、ユーザは角度差制約を課すことによって、仮想環境とともに相対的にまっすぐな経路だけが生成されなければならないことを指定した（詳細については、付録ＩＩとして本願とともに出願された、「経路探索システム」と題される、本発明者の同時係属中の特許出願を参照されたい）。
【０１１２】
図１６では、図１４のステップ７８がステップ９０で置換される、仮想環境内のナビゲーションモードの間でトグルする方法の別の実施形態が示されている。この実施形態では、元の経路ノードに対する交差点で、付録ＩＩに説明されている勢力範囲技法を使用して新しい関心ノードが生成される。この結果、新たな経路探索を実施する（つまり、ｉｎｔｅｒｅｓｔ＿ｃｏｍｐｏｎｅｎｔが増加する）ときにさらに高い関心重みを有する、これらのノードが生じる。これらの関心ノードは、１回以上のトグルがナビゲーションモードの間で切り替えるためにユーザによってアクティブ化された後で、あるいは次の経路探索が新しい目的地で目標とされる場合に削除される。しかしながら、ｉｎｔｅｒｅｓｔ＿ｃｏｍｐｏｎｅｎｔを増加することによって、新規に生成された経路が過去に生成された経路のノードに遭遇する可能性が高い。
【０１１３】
図１７では、仮想環境内のナビゲーションモード間でトグルする方法の別の実施形態が示され、図１７では図１４のステップ７８はステップ９２で置換され、新しい戻り経路が生成される。
【０１１４】
図１７では、新たな経路探索が、元の目的地に対して実行され、該経路探索は元の経路上にある任意のノードに遭遇するとすぐに中断される。その結果、このノードは元の経路のためのリエントリノードであり、元の経路に沿って遭遇されたノードの前に存在した全てのノードが削除される（ステップ９２）。
【０１１５】
図１８は、目的地ノードが作成された目的地Ｅに対して開始ノードが作成された起点Ａからの例示的な経路を示す。生成された経路はナビゲーションノードＡ、Ｂ、Ｃ、Ｄ及びＥと交差し、Ａ〜Ｅからより直接的な経路が生成されるのを妨げるナビゲート不能オブジェクトを迂回する。
【０１１６】
図１８では、実線は、最初にＡ〜Ｅから生成され、それに沿ってユーザが自動的にナビゲートされた誘導経路を示している。破線の経路は、ユーザが手動ナビゲーションに切り替えた誘導経路に沿った点を表す。やはり図１８に示されているのは、ユーザが自動ナビゲーションモードから手動ナビゲーションモードに切り替えたときに生成された、（斜線が付いたノードアイコンで示されている）出口ノードＦである。この出口ノードは、生成された経路の一部を形成するが、元の誘導経路の一部ではなかった。
【０１１７】
やはり図１８にスマイルフェースアイコンで示されているのは、ユーザが自動ナビゲーションを再開することを決定する場所Ｇである。
【０１１８】
図１９Ａと図１９Ｂは、図１４のステップ７８の平行経路探索フィーチャが、出口ノードを含む誘導経路のノードに平行して、どのようにして複数の経路の探索を生成できるのかを示している（Ｄａｎ／Ｍａｒｔｉｎ−これは当てはまる、あるいは出口ノードは図１５のステップ８８だけに入る）。次にユーザに最も近いノードが決定され、元の誘導経路へのリエントリポイントを作成するために使用される。図１９Ａでは、最も近いノードは事実上出口ノードＦである。しかしながら、図１９Ｂでは、ノードＤは移動し、現在はノードＦにより近く配置されているため、ノードＤがリエントリポイントとして選択される。図１９Ｃは、（本明細書では再結合(rejoin）経路とも呼ばれる）戻り経路がノードＧとＤの間でどのようにして生成されるのかを示す。図１９Ｃの陰影の付いたナビゲーション点は全て削除され、経路は元の誘導経路に沿って目的地ノードＥまで続行する。一旦この経路が決定されると、自動ナビゲーションがノードＧからノードＥに沿ってノードＤを介して開始する。
【０１１９】
図２０Ａは、図１５のステップ９０の実現を示す。図２０Ａでは、経路は（例えばナビゲーションノードＨを介して）出口ノードＦに戻ると決定される。出口ノードＦは次に元の誘導経路へのリエントリの点になり、元の誘導経路に沿ってある全ての過去のノードは廃棄される（これらは図２０ＢのノードＡとＢを構成する）。
【０１２０】
図２１は、図１６のステップ９２の実現を示す。図２１に示されている実施形態では、ノードＣ、Ｄ及びＥ、及びＦがそのｉｎｔｅｒｅｓｔ＿ｃｏｍｐｏｎｅｎｔをさらに高い値に増加させる。経路探索プロセスが開始ノードＧから目的地ノードＥまでの新しい経路を決定するために実行されると、これらのノードの増加したｉｎｔｅｒｅｓｔ＿ｃｏｍｐｏｎｅｎｔが、目的地ノードＥまでナビゲーションノードＬだけではなくノードＣとＤも通過して生成された新しい経路を結果として生じる。
【０１２１】
図２２は、図１７に示されているステップ９２の実現を示す。図２２では、新しい経路が新しい開始ノードＧから目的地Ｅまでプロットされる。これはナビゲーションノードＪ及びＫ、そしてナビゲーションノードＤを取り入れる。ナビゲーションノードＤがＡ〜Ｅからの元の誘導経路に関連付けられるので、ナビゲーションノードＤで、新しい経路はＥへの元の誘導経路を再開する。これは、新しい経路を計算するのにまつわる計算の複雑さを削減する。
【０１２２】
このようにして本発明は、仮想環境において（つまり世界のいかなる仮想表現においても）戻り経路を生成する計算上の複雑さを削減する。仮想環境のトポロジーはメッシュ密度と、仮想世界を形成するノードの構成に依存する。ユーザが、どこで自動ナビゲーションモードに戻ることを希望しても、新しいノードを挿入することができなかった場合、仮想世界は、ユーザが手動でナビゲーションしなければならない場合に終わる可能性がある点の全てを予想するほど、十分に高いノーダルメッシュ密度で作成される必要があるであろう。これは、仮想世界自体の計算上の複雑さを高めることだけではなく、自動ナビゲーションのために経路を生成するときにも計算上の負担を増加するであろう。
【０１２３】
英国特許出願番号ＧＢ０４０７３８５．４号、ＧＢ０４０７３１１．０号、及びＧＢ０４０７３９．０．４号から優先権を主張する「経路探索システム」と題される、本発明者の同時係属中の国際特許出願の内容が、参照により本明細書に組み込まれる。当業者は、前記説明及び付録に関して本明細書に説明された本発明が、説明されたフィーチャに同等な機能を提供する多くのフィーチャによって実現されてよいことを理解する。当業者は、また、本発明が本明細書に開示されている実施形態に制限されないが、本明細書に説明されている本発明の一実施形態で説明されているフィーチャを組み込むことができる、又は本発明の別の実施形態への組み込みのために適応できる、あるいは同等な機能を有するいかなるフィーチャによっても置換でき、その結果本発明の適用範囲が添付された特許請求の範囲により定められるとおりであることが明らかである実施形態を特に含むために拡張することも理解するであろう。
【図面の簡単な説明】
【０１２４】
【図１】仮想世界環境における経路探索のためのシステムの概略図を示す。
【図２】仮想世界環境の図表示を示す。
【図３】図２の仮想世界環境の追加の図表示である。
【図４】図２の仮想世界環境の追加の図表示である。
【図５】図２の仮想世界環境の追加の図表示である。
【図６】図２の仮想世界環境の追加の図表示である。
【図７】図２の仮想世界環境の追加の図表示である。
【図８】図２の仮想世界環境の追加の図表示である。
【図９】図２の仮想世界環境の追加の図表示である。
【図１０】図２の仮想世界環境の追加の図表示である。
【図１１】図２の仮想世界環境の追加の図表示である。
【図１２】図２の仮想世界環境の追加の図表示である。
【図１３】仮想世界内の点を処理するための方法のフローチャートを示す。
【図１４】本発明の第１の実施形態による仮想環境内のナビゲーションモード間でトグルする方法を説明するフローチャートを示す。
【図１５】本発明の第２の実施形態による仮想環境内のナビゲーションモード間でトグルする方法を説明するフローチャートを示す。
【図１６】本発明の第３の実施形態による仮想環境内のナビゲーションモード間でトグルする方法を説明するフローチャートを示す。
【図１７】本発明の第４の実施形態による仮想環境内のナビゲーションモード間でトグルする方法を説明するフローチャートを示す。
【図１８】本発明の一実施形態に従ってユーザが自動化された経路を離れた仮想環境を概略して示す。
【図１９Ａ】図１４に示されている本発明の実施形態に従って、自動経路への戻り経路がどのようにして決定されてよいのかを概略して示す。
【図１９Ｂ】図１４に示されている本発明の実施形態に従って、自動経路への戻り経路がどのようにして決定されてよいのかを概略して示す。
【図１９Ｃ】図１４に示されている本発明の実施形態に従って、自動経路への戻り経路がどのようにして決定されてよいのかを概略して示す。
【図２０Ａ】図１５に示されている本発明の実施形態に従って、自動経路への戻り経路がどのようにして決定されてよいのかを概略して示す。
【図２０Ｂ】図１５に示されている本発明の実施形態に従って、自動経路への戻り経路がどのようにして決定されてよいのかを概略して示す。
【図２１】図１６に示されている本発明の実施形態に従って、自動経路への戻り経路がどのようにして決定されてよいのかを概略して示す。
【図２２】図１７に示されている本発明の実施形態に従って、自動経路への戻り経路がどのようにして決定されてよいのかを概略して示す。
【技術分野】
【０００１】
本発明は、仮想世界の表現で複数のポイントに沿って経路を決定するための方法及びシステムに関する。特に、本発明は、目的地への過去の経路と関連付けられた記憶情報を使用する仮想環境内で目的地ノードへの新しい経路を生成するための方法及びシステムに関するが、それに限らない。
【背景技術】
【０００２】
新しい経路は、仮想環境の参加者が手動ナビゲーションモードから自動ナビゲーションモードにトグル(toggle)できるようにするために生成されてよい。仮想世界の参加者が、ナビゲーションシステムの自動ナビゲーションモードとナビゲーションシステムの半自動モード又は直接制御モードの間で切り替える、またはトグルできる能力は、非常に望ましい。しかしながら、ユーザが仮想環境での経路に沿ってナビゲートできるようにするシステムだけではなく、ユーザが現実世界での経路にも沿ってナビゲートできるようにするように構成されたナビゲーションシステムのナビゲーションモードの間で、ユーザがトグルできるようにすることも望ましい。
【０００３】
例えばカーナビゲーションシステム等の多くの従来技術の現実世界システムでは、出発地点と目的地点を入力するユーザによってルートが決定され、ナビゲーションシステムが、ユーザを出発地から目的地までの所定の経路に従わせるため、ユーザが従うための方向を指示することが公知である。しかしながら、ユーザが例えば迂回を実行するために所定の経路を離れることを希望する場合、ナビゲーションシステムは目的地に向かってユーザをリダイレクトし直そうと試みる。通常、ナビゲーションシステムは、ユーザが戻るための元のルートに沿った最も近い点を捜し出し、ユーザは次にその元の経路を再開する。
【０００４】
現在のテクノロジー時代には、三次元仮想現実環境（仮想世界）が定められ、作成されるシステムがますます普及してきている。このようなコンピュータシステムは、オンラインツーリストサイト、ファンタジー世界、賭博、建築上の連絡通路、不動産仲買業（売り家の仮想ツアー）、及びその他多くの、多数の商業的な用途で適用可能である。典型的には、仮想世界は、三次元（ｘ軸、ｙ軸、ｚ軸）で環境をともに緻密に計画する複数のｘ、ｙ、ｚ座標の集合により定められてもよい。仮想世界のトポロジーは、仮想世界の中のオブジェクトが三次元で編成されるように、つまり多くの（本明細書では「ノード」とも呼ばれる）ノーダルポイントの空間的な位置により定めることができる。このケースでは、トポロジーは世界の特定の座標のノードから形成できる論理的なメッシュにより決定される。メッシュは、規則正しく離間されてよい、又は規則正しく離間されなくてもよい。
【０００５】
仮想世界を通してナビゲートするユーザが通り抜けることを許されていないオブジェクト及び壁（又は仮想世界内に存在する他のアイテム）は、衝突可能（ｃｏｌｌｉｓｉｏｎａｂｌｅ）メッシュと呼ばれているものによって実現できる。したがって、衝突可能メッシュは、ユーザがナビゲートしなければならない仮想世界内で形状を定める三次元座標の追加の集合を備えてよい。
【０００６】
ナビゲーションは、コンピュータによって生成された人物、乗り物又はゲームのキャラクタ等の、その世界を通過するいかなるエンティティのための仮想世界内で必要とされる。これは、通常、外部の人間のユーザの制御下にある。従来、仮想環境の多くの商業的な実現は、ゲームエンジンから継承された自己ナビゲーション（ｓｅｌｆ−ｎａｖｉｇａｔｉｏｎ）技法に基づいて構築され、未知の仮想世界の全領域の探査が予想され、高度のユーザ能力が仮定されている。しかしながら、仮想世界の適用が他の商業的な分野にも広がるにつれ、ナビゲーションの機能性が、新しいさらに幅広いグループのユーザ全体の能力と要件に適合するために、進化することが重要である。このようなユーザは仮想世界をめぐるナビゲーションに熟達していない可能性があり、さらに多大な時間を費やして該環境になじむのに乗り気ではない可能性がある。彼らははるかに早く頭が混乱する、あるいは退屈するようになる、あるいはユーザの経験が大幅に改善されない限り重要なコンテンツを完全に見逃す可能性さえある。
【０００７】
我々の日々の生活では、人間は、通常、あちこちに移動するときにナビゲーションで自分たちを手助けするために多様な技法を利用する。我々は、頭が混乱しないようにするために、固定された基準点（ランドマーク）、移動距離の測定、及び方向の変化を使用して、自らの位置と向きに関する考えを保持する。特に多くのゲーム環境におけるケースでのように、テレポート（例えば、該世界の中の２つの異なる点の間を瞬時に移動すること）が適用される場合には、このような技法はそれらが普及していない仮想世界内の新米のユーザに使用できない可能性がある。その結果、経験不足のユーザが、自らを仮想世界にナビゲートするのを助け、彼らが精通していないこと、及び従来の自己ナビゲーションのインタフェースに対するフラストレーションという問題を克服できるようにするために、自動化された経路探索システムを提供することが有利である。その結果、例えば、ある特定のオブジェクトを見る、又は部屋を通過するために最短の経路を見つけるために、仮想世界を通る最善の経路を自動的に計算する多くのシステムが開発されてきた。
【０００８】
従来技術
Ｂａｒｂｅｒは、「コンピュータグラフィックスシーンで経路ネットワークを実現するためのシステムとしての方法」と題される米国特許出願第２００２／０１７５９１８Ａ１号で、ナビゲーションシステムを説明している。Ｂａｒｂｅｒらは、コンピュータグラフィックスシーンの中で少なくとも１つのオブジェクトの運動動作を制御するために経路ネットワークを実現するための方法を説明している。経路ネットワークは複数のノードとセグメントにより形成されている。ノード又はセグメントと関連のある多様なパラメータが、オブジェクトが経路ネットワークに沿って移動するための運動条件を確立するために定められる。Ｂａｒｂｅｒらが説明する経路ネットワークの全てのモードに共通しているのはパラメータＥｎｔｒｙＰｏｉｎｔとＥｘｉｔＰｏｉｎｔである。ＥｎｔｒｙＰｏｉｎｔは指定された経路ネットワークノード又は経路ネットワーク上の他の所定の位置である。しかしながら、Ｂａｒｂｅｒらは経路ネットワークに乗る又は降りるようにオブジェクトを導くための特定のアルゴリズムは何ら開示しておらず、Ｂａｒｂｅｒらが説明する入口点と出口点はシステムの設計者により事前に決定されている。したがって、Ｂａｒｂｅｒが説明しているような世界において、ユーザが、自動的にナビゲートされる誘導経路に従い、手動モードにトグルし、該経路からはずれ、それから自動モードにトグルして戻り、その元の経路を再開することは不可能である。
【０００９】
Ｐｏｐｐｅｎらは米国特許第６，０３８，５０９号で、ネットワーク内で起点から目的地までの経路に従うための一組の指示をユーザに与える、経路探索システムを説明している。ユーザが経路を逸れると、システムは、元の経路から外れているユーザの新しい位置から目的地までユーザを導く新しい経路を再計算する。システムは目的地までの新しい経路を決定するために要する時間量を減少するためにネットワークにリンクを追加する。該拡大されたネットワークを使用して、ユーザの新しい位置から目的地までの新しい経路が決定される。システムが新しい経路を計算するために、ユーザが位置する既存のノード、あるいはユーザが新しい起点として指定するネットワークの既存のノードのどちらかで、新しい起点が決定される、あるいはシステムは、ユーザが経路を再計算するための方法が完了するときに推定される新しい起点にいることができるように、新しい起点がユーザの現在の位置から少し離れていると判断できる。しかしながら、Ｐｏｐｐｅｎらが説明するネットワークは、ノードが固定され、事前に決定されているノーダル(nodal)システムを備える。経路探索システムは、ネットワークの特定のノードに経路を制約するネットワークの固定されたトポロジーによって制約される。
【００１０】
公知の経路探索アルゴリズムは、開始ノードから目的地ノードまでの経路が見つかるまで、考えられる経路、一度に１つのノードを拡大することにより機能する。ノードが試行される順序は、見つけられる最終的な経路の速度と品質（例えば長さ）にとって重大である。横型探索(breadth-first)技法では、アルゴリズムは最初に全てのノードの接近した近傍系を検索し、次にそれらの隣接するノードの近傍系に移動する。対照的に、縦型検索技法では、アルゴリズムは、所定の深さに達するまで毎回子ノードを使用して再帰的に経路を探索し、達するとそれはそのステップを引き返し、他の子ノードを試行する。最良優先探索は、ゴールまでの最短の残りの距離の推定値に基づいて優先的に経路を選ぶ。
【００１１】
ｈｔｔｐ：／／ｗｗｗ．ｉｄｉ．ｎｔｎｕ．ｎｏ／ｇｒｕｐｐｅｒ／ｓｕ／ｆｏｒｄｙｐｎｉｎｇｓｐｒｏｓｊｅｋｔ−２００３／ｆｏｒｄｙｐｎｉｎｇ２００３−Ｊａｎ−Ｈａｒａｌｄ−Ｆｒｅｄｒｉｋｓｅｎ．ｐｄｆに位置する、ノルウェー科学技術大学のＪａｎ−Ｈａｒａｌｄ Ｆｒｅｄｒｉｋｓｅｎによる「コンピュータゲームにおける人工知能のためのミドルウェアソリューション」（第３章−ＡＩ技術）と題される記事は、仮想世界における経路探索技法及びＡ＊アルゴリズムの使用に関する。この文書は、仮想世界を通る経路を計算するときに考慮に入れられるべきである、異なる地形のためのコストの制約の使用、及び計算性能の改善のための（詳細な部分を計算する前に幅広い全体的なルートを見つける）階層経路探索及び（仮想世界の領域をより小さな部分に分ける）ポータルの使用を検討している。この文書での経路探索が基づいている仮想世界の根本的な構造は、２つの代替バージョンを有する。第１は（中間地点と呼ばれている）複数のノードが仮想世界の中に導入され、ノード間の照準線リンクに基づいて経路が見つけられるＰＯＶ（視感度点）手法と呼ばれる。第２の手法は、複数の凸多角形が世界の表面を覆うナビゲーションメッシュを使用することであり、このケースでは、経路探索アルゴリズムは各多角形をノードであると見なし、相応して仮想世界を通る経路を計算する。
【００１２】
さらに、現在では現実世界の部分を通る移動経路のプロットを自動化するためのシステムが存在する。このようなシステムの好例が、ＡＡ組織（ｈｔｔｐ：／／ｗｗｗ．ｔｈｅＡＡ．ｃｏｍを参照されたい）のウェブサイトで提供される「ルートプランナー」ツールである。このようなシステムはユーザの特定の好み（例えば、高速道路を回避すること、最短距離、最短時間等）を考慮に入れる。しかしながら、本発明者は、決して非常に初歩的ではない何かにおいて、ルートがユーザの功利主義的ではない優先順位を考慮に入れることができるシステムを全く知らない。また、このようなシステムは必ず所定の経路（つまり、道路が存在する場所）に沿ってルートを計算することに制限されるため、生成される最終ルートの柔軟性で制限される。
【発明の開示】
【００１３】
本発明は、自動ナビゲーションモードと手動ナビゲーションモードの間でトグルするための手段を提供する、公知のナビゲーションシステムの制限を未然に防ぐ、及び／又は軽減しようとする。本発明によるナビゲーショントグルシステムは、ノーダルポイントの動的に変化するトポロジーを備えるシステムで実現され、誘導経路が動的に生成されてよい。環境内のノード及び環境のノード間の潜在的なリンクのネットワークの位置は事前に決められていないため、ユーザは自動ナビゲーションモードと手動ナビゲーションモードの間でトグルするさらに多くの自由を与えられる。
【００１４】
本発明の態様は、その従属クレームが本発明の好ましい特長を表す、添付の独立請求項によって説明されるとおりである。
【００１５】
それにも関わらず、当業者は、好ましい特長が当業者に明らかないかなる適切な方法で、本発明の態様のいずれかと適切に結合されてよいことを理解するであろう。
【００１６】
本発明によるナビゲーションシステムでは、ネットワークのナビゲーションポイントの位置は事前に決められていない。さらに、トポロジー内で生成されるナビゲーション経路は所定の構成に制限されない。したがって、ユーザが、所定の誘導経路トポロジーから離れるために自動ナビゲーションモードからトグルすると、トポロジーのノーダルポイントはユーザの位置の変化に応じて再定義されてもよい。さらに、ユーザが自動化された経路を再開することを希望し、手動ナビゲーションモードから、ユーザが誘導経路に沿って自動的にナビゲートされるナビゲーションモードにトグルして戻るときには、第１の誘導経路を離れた時点でネットワーク内に存在するナビゲーションノードが再定義されてもよい。
【００１７】
加えて、ユーザはネットワークのナビゲーションノードの内の１つで誘導経路から出るように制限されていない。代わりに、ユーザは任意の点で自由に手動ナビゲーションノードに切り替わることができる。出口ノードは、ユーザが元の誘導経路を離れる点で作成されてよい。出口ノードは、例えば特定のタイプの勢力範囲(sphere of influence)等の１つ以上の特定の特長で拡大されたノードのナビゲーションタイプであってよい。
【００１８】
例えば、本発明の一実施形態では、勢力範囲ノードは、ユーザが手動ナビゲーションモードへトグルするときに作成される出口ノードの周りに動的に生成される。ユーザがこの範囲を超えて自らをナビゲートする場合、ユーザが出発点から目的地まで生成された元の経路に再び加わるというオプションは、期限切れになってもよい。代わりにユーザが元の経路から離れてすごす時間に対する制限時間が、このオプションを期限切れとしてもよい。いずれのケースでも、再び加わるオプションは、ユーザがあまりに遠くまでさまよい（又は非常に長く離れてしまった）元の経路は現在使われていないので、自動的に使用不可能となる。例えば、ユーザが元の目的地の反対側にさまよい、その結果ユーザが完全に異なる角度から目的地に近づくことを希望するであろう場合、元の経路に再び加わる最適経路を決定するために検索が実行されるのは、計算時間／性能の効率的な使用ではないであろう。
【００１９】
ナビゲーションシステムは、初期出発点と初期目的地の間に経路を画定する仮想環境内の点の密度が固定されておらず、２つの点の間の経路を決定する点のトポロジーが経路自体がプロットされるのにつれて動的に変化できるように、多くの条件に従って変化できる、仮想環境内に設けられる。これにより仮想世界環境の中に、ユーザがそれに沿って自動的にナビゲートできる経路を設けることができる。経路のトポロジー及び／又はユーザが該経路に沿って自動的にナビゲートされる速度により、ユーザは１つ以上の関心のあるオブジェクトに遭遇することができる。
【００２０】
１つ以上のオブジェクトであって誘導経路がユーザをそれに向かって誘導しようとするものは、（例えば仮想世界内のそれらの位置に関して）動的に変化してよい。これは特に、ユーザが互いに仮想世界の中のキャラクタを介して対話できる可能性がある仮想環境で当てはまる。例えば、キャラクタの内の１つが同じ仮想環境の中で参加している別のユーザによって制御される場合、動的経路は、そのキャラクタが、ユーザがそれを制御することによって仮想世界で使用されない場合に変化してよい。
【００２１】
本発明は、例えばファンタジー世界又は歴史的な建物又は将来の建物のための設計、あるいは販売のための家等の実際の環境に基づいた世界を含む可能性があり、障害物が壁又は他の障害物を構成する可能性のある、いかなるタイプの仮想世界にも適用できる。上記で使用される意味での表現は、そのような世界を表現する記憶されたデジタルデータを指すことが多い。
【００２２】
有利なことに本発明の構成は、コンテンツプロバイダが仮想世界の中でのナビゲーションのためにいくつかの初期の点を定めることを可能とし、該コンテンツプロバイダが、取られた経路及びユーザが訪問できる関心のあるアイテムに影響を与えることができるようにする技法を採用している。したがって、システムは、最初に定められたナビゲーションポイントの限られた集合だけと比較した、該環境を通る後に生成された経路に沿ったユーザの経験を改善するように自動的に点の数を増やす。
【００２３】
仮想世界を通る経路が特定のナビゲーションポイントに制約されていない先に公知のシステムと比較すると、本発明の実施形態は実際の経路探索手順の間の処理の改善を実現する。これは、全ての新しいナビゲート可能なノードとリンクが視野方向の原則に基づいて加えられたため、当然全ての潜在的な障害物を回避するために、実施形態における経路探索の間に（経路が障害物等を回避するのを確実にする）衝突検出が必要とされないためである。
【００２４】
加えてこれらの実施形態は、指定された所定の道路等に沿ってルートを見つけることに必ず制限される、ＡＡルートファインダ（Ｒｏｕｔｅｆｉｎｄｅｒ）等の先に公知のシステムに優る利点を提供する。対照的に、実施形態では、ユーザは仮想世界の全領域の中でナビゲートできる。
【００２５】
本発明をさらによく理解するために、特定の実施形態は、添付図面を参照して一例としてここで説明される。
【発明を実施するための最良の形態】
【００２６】
本発明者らにより現在意図されている、本発明の最良の態様は、添付図面を参照して説明されるであろう。
【００２７】
本発明は、第１の過去の経路から派生するノーダル情報を含む経路を生成できるようにする。第１の経路を生成できるようにする１つのナビゲーションシステムは、ここで添付図面の図１から図１３を参照して説明される。
【００２８】
図１は、仮想世界を作成し、ユーザが仮想世界内でナビゲートできるようにするシステム１を描いている。システムは、端末３を介してコンテンツプロバイダ（仮想世界の仕様を入力する人間のユーザ）にアクセスでき、別の端末４を介して（仮想世界を見て、ナビゲートすることを所望する）ユーザにアクセスできる、サーバコンピュータ２を備える。描かれているコンピュータ構成は、コンテンツプロバイダが、ユーザがその後アクセスし対話することができる仮想世界を設計し、実現できるようにする、いかなる適切な代替策により置換されてよいことが理解されているが、この特定の実施形態では、両方の端末からサーバ２へのアクセスは例えばインターネット等の汎用ネットワーク５を通る。
【００２９】
簡略な仮想世界環境の概略が図２に示されている。これは、部屋２０を表し、その中に壁２１、扉２２、及び多様な障害物２３、２４、２５を含む。この仮想世界２０の設計を指定するとき、コンテンツプロバイダは端末３を介してサーバ２の中に該環境の形状を表す座標の形式でデータを入力する。データは、ナビゲートするユーザが通過することを許されていない障害物２３、２４及び２５を定義する、衝突可能メッシュを表現する座標を含む可能性がある。
【００３０】
フィーチャ（Ｆｅａｔｕｒｅ）ノード
コンテンツプロバイダは、ユーザが見ることを希望する場合がある部屋内で、関心のあるフィーチャを定義できる。例えば、仮想世界が歴史的な建造物を通るツアーを表現する場合、塑像、家具、絵画及び情報板等のフィーチャを挿入することが所望されてよい。これらは、例えば塑像オブジェクト２６、絵画２７及び情報板（障害物２５）等の、部屋内のオブジェクトによって表現されてよい。
【００３１】
ユーザがこれらのフィーチャにアクセスできるために、コンテンツプロバイダは、ユーザが見る又は対話することができる該フィーチャに関連付けられた、（図３に示されている）フィーチャノード２８Ａ、２８Ｂ及び２８Ｃを定義する。したがってフィーチャノードは基本的に、オブジェクト又は衝突可能なメッシュのどちらかにリンクされる仮想世界の中の点であり、本実施形態では以下のデータ組を有する。
【表１】
【００３２】
ノードＩＤ−ノードのための一意の識別子（例えば、テキスト文字列「ｍｏｎｅｔ＿ｐａｉｎｔｉｎｇ＿０１」又は数値識別子「００５６３」）
フィーチャグループＩＤ−ノードと関連付けられているフィーチャのタイプの識別子であって、例えば情報板は第２のフィーチャグループ「ｉｎｆｏｒｍａｔｉｏｎ＿ｐｏｉｎｔｓ」である可能性があるが、全ての絵画は「絵画」として識別される第１のフィーチャグループ内にあってよい。グループ分けの選択はコンテンツプロバイダと、グループが仮想世界内で識別を希望するフィーチャのタイプに大きく依存する。
【００３３】
リンクされたメッシュ／オブジェクトのオブジェクトＩＤ−これは、フィーチャノードと関連付けられているオブジェクト又は衝突可能メッシュの識別子であり、ノードＩＤ（例えば「ｍｏｎｅｔ＿ｐａｉｎｔｉｎｇ＿０１」）と同じであってよい。
【００３４】
オブジェクトピボットポイントデータのＸＹＺ−これらはフィーチャノードの位置を示す座標である（そして、フィーチャノードが関連付けられているオブジェクト／メッシュの特性から抽出することにより取得されてよい）。
【００３５】
勢力範囲設定値−これらは（３Ｄ世界のために）（例えば、図３に円３１として描かれている）フィーチャノードを取り囲む三次元の球体を形成し、仮想世界を通るナビゲーション経路の計算中に使用される。
【００３６】
ディスプレイ設定値−これらはフィーチャと関連付けられているテキスト／画像に使用される設定値の一部である。
【００３７】
ナビゲーションノード
コンテンツプロバイダは初期に、図３に示されているように仮想世界内に複数のナビゲーションノード（２９Ａ、２９Ｂ、２９Ｃ等）をさらに定義する。本来、これらのノードは、自動経路生成アルゴリズムが該環境を通るルートをプロットするために使用できる、ナビゲーションポイントの簡略な行列を提供する。各ナビゲーションノードに関連付けられているのは以下のデータ組である。
【表２】
【００３８】
ノードＩＤ−ノードの一意の識別子
ノードレベルＩＤ−これはノードのレベルを定め、ノードを様々な部分集合に効果的に分類し、仮想世界を処理効率のための異なる領域に分割するために経路探索プロセスの間に使用できるようにする識別子である。例えば、仮想世界内の２つの異なる部屋はノードの異なる領域によって表現でき、それらの間の出入り口がスイッチノードを備える。処理効率のため、初期に経路は部屋の内の一方のノードだけに基づいて計算できる（このようにしてこの段階で第２の部屋に入る経路を誤って計算するのを省き、後にのみ経路探索計算が該スイッチノードを介して第２の部屋に伸張できるようにする）。さらに、異なる部分集合が重複する領域をカバーできると考えられる（例えば、異なるレベルが同じ領域又はその領域の部分集合のさらに細かい適用範囲を提供する可能性がある一方、ノードの第１のレベルが広い面積のおよその適用範囲を提供する可能性がある）。
【００３９】
ＸＹＺ位置−これらは、ナビゲーションノードの位置を示すｘ、ｙ、ｚ座標である。
【００４０】
ＬｏＳデータ−このデータフィールドは当初、空となるが、後に現在のノードが照準線(Line of Sight)（ＬｏＳ）を有する全ノード、つまりそれがリンクすることができる全ノード（詳細については以下を参照されたい）のリストを含むために使用されてよい。
【００４１】
ＬｏＳ制約設定値−コンテンツ製作者は、角度ＬｏＳ制約（つまり、ノードが、角度範囲、その角度範囲でその視角に該当する場合にだけ、リンクするノードを検索するのを許される、詳細については以下を参照されたい）を手動で定めることを選んでよい。
【００４２】
ＦｏＶ制約設定値−コンテンツ製作者は、そのノードでユーザに表示できる画像の範囲を制約する視野（ＦｏＶ）の角度制約を定めることを選んでよい（例えば、ノード２９Ｆの場合、ＦｏＶはユーザがオブジェクトを見ることを確実にするために塑像オブジェクト２８Ａに向かう角度方向内で制約されてよい）。
【００４３】
方向制約設定値−いくつかのナビゲーションノードの場合、コンテンツ製作者は、方向制約設定値を定めることによってユーザに許されている向きを、彼らがノードに近づくにつれて制約することを選んでよい。これにより、計算された経路は強制的にある特定の方向からノードに近づく。
【００４４】
コンテンツプロバイダはこのようにして、ナビゲーションノードを使用することにより、潜在的なユーザが環境の中で関心のあるフィーチャを最良に経験できる仮想世界内の重要な位置を定めることができる。コンテンツプロバイダは、完全に自動化されている他のシステムに比較して、ユーザの関心のあるフィーチャの経験の質を高めるために、正確な位置、接近の方向（方向設定値）、及び視角（ＦｏＶ制約設定値）を定めることができる。
【００４５】
処理
以後の処理は、図１３の流れ図を参照して説明される。ノードデータがシステムに入力された（ステップ４０）後、ノードマトリックスが仮想世界のために自動的に作成される（ステップ４１）。これは、各ナビゲーションノードにとって、それがリンクできる全ての他のナビゲーションノードを識別する。ノードリンクは２つのノードのためのＬｏＳ（照準線）の基本的な規則に従って計算される。これは衝突可能なメッシュ及びノードのＬｏＳをトリミングすると見なされているあらゆる他のオブジェクトを考慮に入れる（つまりノード間の経路は障害物を通過できないため、リンクは障害物を通過することができない）。図４は、仮想世界２０内のナビゲーションノードのための、考えられる全てのＬｏＳリンク（つまり、ノード２９Ａ、２９Ｂ等をリンクする線）を描いている。例えば、ノード２９Ａはノード２９Ｂと２９Ｆの両方に直接的な照準線を有するが、２９Ｃは障害物２３を通過するであろうため、２９Ｃには直接的な照準線を有さない。図４の仮想世界２０のノードマトリックスは表形式で以下に表現される。
【表３】
【００４６】
この段階では、各ナビゲーションノードのデータセットには、可視パートナーのＸＹＺ位置を含む、これの全ての可視パートナーに関するＬｏＳデータが与えられている。いかなる他のナビゲーションノードに対する照準線も有さないあらゆるナビゲーションノードは無効と見なされ、システムから削除されてもよい。
【００４７】
コンテンツプロバイダが特定のナビゲーションノードに対するあらゆるＬｏＳ制約を指定した場合には、それがノードリンクを検索することを許される角度をトリミングするであろう。これは該ノードのための「ＬｏＳ制約設定値」を使用して制御され、それ以外の場合許された３６０°のＬｏＳをスライスする度数値を備える。このケースでは、そこで示されているリンクのいくつかが許可されないであろうために前記ノードマトリックスは異なるであろう。この機能性により、コンテンツプロバイダは、それらの周りの他のノードを無視するノードのチャネルを作成でき、ノードが所望されていないノードマトリックスで中断を生じさせることができる。このようにしてコンテンツプロバイダは仮想世界内でユーザによって取られるルートに影響を及ぼすことができるため、これはユーザ経験を改善できる。
【００４８】
処理の次の段階は、すでに定められているＬｏＳリンクに基づいて追加のノードに追加する。しかしながら、それが発生する前に、システムはどのリンクが新しいノードのためのベースとして使用されるのか／使用されないのかを決定するために、全てのリンクをチェックする（ステップ４２）。特に、システムは（２９Ｃから２９Ｄリンクを交差する２９Ｂから２９Ｅリンク等の）あらゆる交差リンクを探し、新しいノードのベースとして使用するために利用できないとして交差リンクの最も長いものを記す。この実施形態では、データフラグが、このリンクが「細分されるべきではない」ことを示すために（ノードマトリックス又は個々のノードのＬｏＳリンクデータのどちらかの中の）リンクに関連付けられている。この影響されたリンクは、図５に点線で示されている。
【００４９】
処理の次の段階は、ノードのさらに密集したマトリックスの自動作成を含む（ステップ４３）。これは、各中間点で（細分ノードとも呼ばれる）新しいナビゲーションノードを追加するために、既存のナビゲーションノードの間でＬｏＳリンクを細分することにより達成される（ステップ４４）。図６は、これらの細分されたノード（３０Ａ、３０Ｂ、３０Ｃ、．．．等）を示す。ステップ４３を通る各サイクルの間により多くの新しいノードが追加されるにつれて、ノードの密度は、最大許容ノード密度まで高まる。この密度は、例えばノードからその最も近い近傍系までの最小許容距離を指定することによって、コンテンツプロバイダによって事前にあらかじめ定められてよい。各新しいノードが追加された後、システムは、新しいノードが密度基準を満たしているかどうかをチェックする（ステップ４５）。それが許容密度基準外に含まれる場合、新しいノードが削除される（ステップ４６）。それ以外の場合、ノードは保たれる。一旦あらゆるＬｏＳリンクが細分のために調べられると（ステップ４７）、システムはあらゆる新しいノードが最後の通過の間に追加されたかどうかをチェックする（ステップ４８）。通過中に新しいノードが作成されないと、システムは終了する（ステップ４９）。
【００５０】
各通過の場合、新しいノードが追加された後、あらゆるノード（ナビゲーションノードとそれぞれの新規に作成された細分ノードの両方）のＬｏＳデータが、複数の新しい考えられるＬｏＳリンクを全て考慮に入れるために更新される（ステップ５０）。図７は、ノードの間にさらに多くの考えられるＬｏＳリンクを有する新規に作成された密度の濃いマトリックスを描いている。
【００５１】
システムはここで、新規に追加されたノードの内のどれが有効であるのかをチェックする（ステップ５１）。ノードは、それがそれ以外の場合互いに照準線を有さない任意の２つの他のノードにリンクする場合に有効と定められる。これは、図８のノード３０Ａに描かれている。この図面では、明確にするために、描かれているノードとリンクだけがノード３０Ａとノード３０Ａがリンクする７つの他のノードである。ノード３０Ａは、ノード２９Ｂと３０Ｆの間等、多くの異なる組のノードのためのブリッジとしての機能を果たす（つまり、ノード３０Ａは互いにＬｏＳを有さない２つのノードの間の接続を形成する）ことが明確に分かる。したがって、ノード３０Ａは有効であり、事実上、それが有効なノードとして定められるＬｏＳを有さない１組のノードに接続されることだけを必要とする。あらゆる無効ノードは削除される。
【００５２】
図９は、ノード３０Ｂのための同じ手順を示す。ノード３０Ｂは有効として定められている。しかしながら、この段階で、２つのノード間のブリッジを支援しない３０Ｂリンクのいずれかが削除される。これは、ノード３０Ｂと２９Ｃの間のリンクにも当てはまる。ノード２９Ｃはすでに図９に示されている全てのノードに対する照準線リンクを有する（そして、相互にノード３０Ｂは２９Ｃにリンクされた全てのノードに対する照準線も有する）ため、リンク３０Ｂ−２９Ｃは互いに照準線を有さないいかなるノードの組の間でブリッジするのに役立たず、リンク３０Ｂ−２９Ｃは削除される。
【００５３】
ノード３０Ｃはすでに図９の中に全てのノードに対して照準線を有しているため、リンク３０Ｂから３０Ｃも図９から冗長であるように見える。しかしながら、リンク３０Ｂから３０Ｃは、例えば図７から分かるように（互いに照準線を有さない）ノード３０Ｂと３０Ａを架橋するため、実際には有効であり、したがってリンク３０Ｂから３０Ｃは削除されないであろう。
【００５４】
全ての新しいノードについてこのようにして有効性チェックが実行され、他の２つ（３０Ｅと３０Ｈ）がそれぞれ図１０と図１１に示されている。
【００５５】
有効性チェックが新しいノードに対して実行された後、システムは再びあらゆる交差リンクがないかチェックする（ステップ５２）。交差リンクは以後の細分のサイクルで使用されるべきではないリンクである。リンクは、互いに交差するリンクを探し、最も長いリンクを「細分されるべきではない」とフラグを立てることによって、以前のように識別される。これは全てのリンクについて実行され、結果として生じるリンクマトリックスが（点線が、さらに多くのノードを追加するために細分のために将来使用されるべきではないそれらのリンクを描く）図１２に描かれている。
【００５６】
したがって細分の１つのサイクルが完了され、この後にもノードの数は２倍以上になり、ノード間の接続性は大幅に高まった。例えば、ノード２９Ｄは以前は２９Ｂ、２９Ｃ及び２９Ｅに対するリンクだけしか有していなかったが、現在ではさらに３０Ｂ、３０Ｃ、３０Ｅ及び３０Ｆにリンクしている。
【００５７】
細分の追加サイクル（ステップ４３）は、システムが、仮想世界の中の衝突不可能な環境を緻密に計算する適切に濃い密度のノードのマトリックスを作成するまで、繰り返されてよい。有利なことに、以後の経路探索計算の間、マトリックスノードは全てナビゲート可能な領域に制約されているため、リアルタイムで衝突データを計算する必要はない。さらに、該環境におけるノードの密度が高くなるにつれ、システムは最初に定められたノードマトリックスを用いるよりはるかに効率的な経路を生成でき、典型的には現実世界の環境をナビゲートするときにユーザが慣れている動作のタイプに従う、仮想世界を通るはるかに円滑な経路を与えることによってユーザ経験を強化する。
【００５８】
一旦経路が計算されると、さらに補間する、したがってさらに行程を円滑化するためにスプラインが生成される。本実施形態では、一旦ある特定の経路に沿ってスプライン(spline)が生成されると、該経路に沿ったデフォルトの速度が設定される。本実施形態では、これは、ほとんど関心のない領域でのかなりの高速と、関心のあるフィーチャの周りでの相対的な低速との間で、変化するように設定される。理想的には、これは最も関心のあるフィーチャノードで最小値を有し、これらの点の間で最大の速度を有するように、速度を円滑に変化することにより行われる。
【００５９】
前記の実施形態では、ノード密度基準は新しいノードと既存のノードの間の最小許容距離に関して指定されるが、これはノード密度を指定し、試験するためのいかなる他の適切な機構によっても置換できるであろう。別の考えられる方法は、アルゴリズムが終了しなければならない前に細分のサイクルの最大許容数を事前に指定することである。
【００６０】
前記の実施形態では、新しいノードが有効であるかについてのチェックは、ノードが他の２つのノードの間のブリッジとしての機能を果たすかどうかをチェックすることを含むが、それぞれの新規に追加されたノードが有効であるかどうかを定めるために使用されてよい代替の／追加の基準は、新しいノードがノードの任意の組の間でさらに短い経路を提供するのを支援するかどうかをチェックすることである。
【００６１】
経路探索
前述されたように、Ａ＊アルゴリズムは必要とされる処理時間と見つけられる経路の質の両方に関して最適の経路探索アルゴリズムである。開始ノードと目的地ノードは事前に定められ、アルゴリズムは開始から目的地までの最善のルートを見つけるために複数の異なる経路を探索する。仮想世界２０を通るツアーを希望し、扉２２で入り、適切なインタフェースを介して自分が情報板２５に接近することを所望することを示したユーザのケースを考える。
【００６２】
開始ノードはノード２９Ａとして定められ、目的地ノードは２９Ｇとして定められる。Ａ＊アルゴリズムはノードの２つのリスト、つまり、すでに探索されたノードのリスト（クローズドリスト）と、探索されたが、まだそれら自体探索されなければならないノードにリンクされたノードのリスト（オープンリスト）を維持することによって動作する。アルゴリズムはオープンリストからノードを取り、そのノードが目的地ノードである場合には、アルゴリズムは終了する。目的地ノードではない場合、選ばれたノードにリンクされている全てのノードがオープンリストに追加される。Ａ＊アルゴリズムは、それがノードの検索を誘導するために推定値を使用するため、発見的な方法として知られている。特に、オープンリストからどのノードが次に選択されなければならないのかを決定するために、全てのノードが評価関数ｆ＝コスト＋ヒューリスティック(heuristic)を有し、オープンリストから次に最新のノードとして選択されるノードがｆの最低値を有するノードである。
【００６３】
コストは、開始ノードから最新のノードまでのこれまでの経路の質の測度である（つまり、簡略なＡ＊アルゴリズムの場合、これは開始ノードと該ノードの間の経路内の全てのリンクの長さの総計となるであろう）。ヒューリスティック(heuristic)関数は最新ノードから目的地ノードへ到達するためのコストの推定値である。Ａ＊アルゴリズムの結果はコストとヒューリスティック(heuristic)関数の選択にかなり依存し、最適経路を生成できるようにするのは、本発明の実施形態のための評価関数で使用される特定の加重値及びコスト値である。
【００６４】
本実施形態のコスト関数は、あらゆるユーザの特殊な優先傾向とともにルートの多様な要因を考慮に入れる。コスト関数は、以下の形式の加重和である。
【数１】
【００６５】
ここで距離はこれまでのリンクの長さであり、ｗ１は、経路が可能な限り短いことがそれらにとってどれほど重要なのかを示す現在のユーザに帰される重みである。Ｉｎｔｅｒｅｓｔ＿ｃｏｍｐｏｎｅｎｔは、ノード（複数の場合がある）がこれまでどれほど興味深かったのかの測度を示している（しかし、我々はコスト関数を最小限にすることに注意を向けているので、ｉｎｔｅｒｅｓｔ＿ｃｏｍｐｏｎｅｎｔ値が低いほど、ノードはこれまで興味深かった）。このようにして本実施形態では、以下の形式のこれまで構築された部分的な経路に含まれる１つ以上のノードの合計が使用される。
【数２】
【００６６】
ここでｗ２は問題のノードに関連付けられているフィーチャグループに示されているパーセンテージ重み関心（ｐｅｒｃｅｎｔａｇｅ ｗｅｉｇｈｔｉｎｇ ｉｎｔｅｒｅｓｔ）であり、関心は、ノードが、該ノードに関連付けられている対応するフィーチャにどれほど強力に関連付けられているのかの測度である。したがって、本実施形態では、ナビゲーションノードが０という関心値を有するが、（通常、ユーザにとって非常に関心のある）フィーチャノードは関心値１を与えられてよく、したがって前記のように合計されるときにはさらに高いコストを示す。言及されたように、重みｗ２は、それらがそれぞれのフィーチャグループの関心のあるフィーチャにアクセスすることがユーザにとってどれほど重要であるのかの測度を示す。
【００６７】
最後に、角度は各ノードの入口リンクと出口リンクの間で角度がどれほど大きく直線から逸れるのかの合計（または平均）を表しているので、角度は、経路が今までのところどれほど小刻みに動いたのかの測度を示す。重みｗ３は、経路がほんの少ししか小刻みに動かないことがユーザにとってどれほど重要であるのかの測度を示す（つまり、高い値（例えば１００％）は、ユーザが波状の経路を回避することを好むことを示すであろうが、ｗ３のゼロ値は、経路がどれほどくねくねしていたのかをユーザが気にしていなかったことを示唆する）。
【００６８】
ヒューリスティックは現在のノードから目的地ノードに到達するためのコストの推定値であり、このために考えられる１つの選択肢は以下である。
【数３】
【００６９】
したがって、本実施形態のヒューリスティックは所望に応じて、代わりに距離、関心、及び角度の重みｗ１、ｗ２、及びｗ３の何らかの測度を含むことができるが、該ヒューリスティックは、目的地へのユークリッド距離（つまり現在のノードから目的地ノードまでの直線）に基づいている。
【００７０】
したがって、最終的な目的地ノードに達するまで、システムは評価関数を使用するノードについてＡ＊アルゴリズムを通る。重要なことには、重みｗ１、ｗ２、及びｗ３はユーザプロファイルに応じて変化できる。
【００７１】
ユーザプロファイルの定義
適切なインタフェース（図示せず）により、ユーザは自らのプロファイル（例えば、自分たちが特に何に関心があるのか、及び彼らが仮想世界をどのようにナビゲートしたいのか等）を定めることができる。ユーザプロファイル設定値は、次にＡ＊アルゴリズムに使用される前記の重みに組み込まれ、結果的に異なるユーザのために異なる経路を生じさせることになる。ユーザ関心を重みに変換することにより、そのユーザのための最適経路を生成できるように異なるルートを互いに対して比較できるようになる。特に関心のあるフィーチャ（絵画、名所旧跡等）を訪れることに興味があるユーザにとっては、システムが２つの点の間の最も速い又は最も短いルートを計算しないのが実状である可能性が高いことが分かる。むしろ、最低のコスト経路（つまりそのユーザにとって最善のルート）は、可能な限り多くの関心のあるフィーチャを訪れる経路である。
【００７２】
ユーザは、仮想世界に最初に入るときに自分たちのプロファイルを入力してよい。いくつかのオプションは以下を含む。
【表４】
【００７３】
最初の５つのオプションはオーバーライドであり、したがって重み付けされない。例えば、ユーザが「常に最短経路を選択する」をＯＮに選択した場合には、関心のあるフィーチャの重み付けｗ２は不適切になり、ゼロに設定される。
【００７４】
最後の５つのオプションは全て重みが付けられており、重み付けは分散されているが、それらは全て正規化されなければならない（例えば合計で１００％まで加算する）。ユーザにとって重要ではなく、重みが与えられないオプションは不適切と見なされ、経路探索のプロセスでは考慮に入れられない。
【００７５】
動的ナビゲーションノード
コンテンツプロバイダにより初期に定められた固定されたナビゲーションノード（２９Ａ、２９Ｂ、２９Ｃ等）に加えて、システムはまた動的ナビゲーションノード（図示せず）を含んでもよい。これらのノードは、それらがユーザにとって生成される経路の一部を形成できるが、ユーザがそれらを移動することができるため強化された機能性を提供することができるという意味では、ナビゲーションノードのように動作する。動的ナビゲーションノードはユーザによってあちこち移動できる仮想世界環境の中の対話型メッシュオブジェクトと関連付けられている。ユーザは、動的ナビゲーションノードを目的地点にすることを希望すると指定することができ、経路はその位置に対して計算される。
【００７６】
動的ナビゲーションノードが他のナビゲーションノードから大きく離れた距離に配置される場合、前述された細分プロセスは、適切なノード密度がその領域で達成されるまで新しいノードに代わるように使用されてよい。これによりノードまでの円滑な経路が計算できる。
【００７７】
動的ナビゲーションノードがあらゆる他のナビゲーションノードへの照準線なしに（つまり死角に）配置される場合、該ノードは無効と定められる−（依然として本実施形態では存在するが）ノードマトリックスから失われ、ユーザは該ノードを目的地に選択するのを妨げられる。代わりに、システムはユーザが死角に該ノードを配置するのを妨げてよく、該ノードを有効な位置に移動することだけを可能にする。
【００７８】
スイッチナビゲーションノード
固定されたナビゲーションノードと動的ナビゲーションノードに加えて、システムは、コンテンツ製作者により定められるスイッチナビゲーションノード（図示せず）も含んでよい。前述されたように、ナビゲーションノードはレベルＩＤを有し、ノードがどのレベルに属するのかを指定し、効果的に、より効率的な経路計算のために異なる部分集合にノードをグループ分けする。例えば、仮想世界が２つの異なる部屋からなる場合、一方の部屋の中のナビゲーションノードは１つのレベルに属していると定められてよく、第２の部屋のナビゲーションノードは異なるレベルに属する。一方の部屋の経路探索プロセスの間、違うレベルのノードを考慮に入れる以外は、そのレベルのノードだけが評価される。スイッチノードは、次に１つのレベルから第２のレベルにスワップする機能性を提供する（例えば、スイッチナビゲーションノードは２つの部屋間の出入り口に配置される可能性がある）。
【００７９】
各スイッチナビゲーションノードと関連付けられているのは、以下のデータセットである。
【表５】
【００８０】
ノードＩＤ−ノードのための識別子
ノードレベルＩＤ＃１−第１のレベルのための識別子
ノードレベルＩＤ＃２−第２のレベルのための識別子
ＸＹＺ位置−これらはスイッチナビゲーションノードの位置を示すｘ座標、ｙ座標、ｚ座標である。
【００８１】
ＬｏＳデータ−これは、現在のノードが照準線（ＬｏＳ）を有する（両方のレベルの）全てのノードのためのデータを示す。
【００８２】
切り替えデータ−生成された経路が、あるレベルのナビゲーションノードから他のレベルのノードに切り替わることができるとき／できないときの基準を示す。
【００８３】
イベントフィーチャノード
前述されたように、コンテンツプロバイダは、仮想世界の中の関心のあるフィーチャと関連付けられているフィーチャノード（２８Ａ、２８Ｂ、２８Ｃ等）を定めることができる。コンテンツ製作者は、彼らが仮想世界の中のユーザに反応する余分な機能性を有するイベントフィーチャノード（図示せず）も定めることができる、あるいは特定の所定の時にだけアクティブである。
【００８４】
これらのイベントフィーチャノードは、システムの機能性を、複数のユーザが環境と、及び互いと対話できるゲーム用プラットホーム及び対話型オンライン環境プラットホームに拡大する（例えば、イベントフィーチャは爆発、又は対話型チャットルーム／レースイベントの開催と閉幕をシミュレートしてよい）。コンテンツプロバイダは、イベントフィーチャがいつアクティブとなるのか／イナクティブとなるのか、あるいはそれがどのトリガに応えるのかを指定しなければならない。例のデータセットは以下のとおりである。
【表６】
【００８５】
ノードＩＤ−ノードの識別子（例えば、テキスト文字列「爆発」）
フィーチャグループＩＤ−ノードに関連付けられているフィーチャのタイプの識別子
トリガデータ−イベントフィーチャノードをアクティブにさせる条件
ピボットポイントデータのＸＹＺ−これらはイベントフィーチャノードの場所を示す座標である。
【００８６】
勢力範囲設定値−これらは（三次元世界のために）フィーチャノードを取り囲む三次元球体を定める。しかしながら、標準的なフィーチャノードに使用される設定値に加えて、これらはさらに、勢力範囲が経時的に劣化できるようにしてよい時間に依存するフィーチャを含む。
【００８７】
時間設定値−これらは、イベントフィーチャノードがいつアクティブになるのか／イナクティブになるのかを定める。
【００８８】
ディスプレイ設定値−これらは、制約時にフィーチャと関連付けられているテキスト／画像のために使用されなければならない設定値である。
【００８９】
追加の機能性
前記に説明されたように、処理段階と経路探索段階の結果、ユーザを該環境に連れて行くために使用されるであろうスプライン経路を生じさせる。したがって、スプライン経路は、それぞれ次のノードに対するリンクによって接合される複数のノードを備える。システムは、さらにユーザ経験を改善するためにスプラインを補間することによりこの経路への平滑化を適用する。
【００９０】
リアルタイムディスプレイの間、ユーザが該環境を誘導されるとき、彼らは自分の視野を制御するための追加のオプションを有する。前述されたように、コンテンツプロバイダは、ユーザが関心のあるフィーチャを見失わないことを確実にするために、特定のフィーチャノードに適用されなければならない特定の視角（ＦｏＶ制約）を指定できる。ユーザは、この自動視野プレゼンテーションを操作する、又は代わりに手動で自身の視野を制御するかのどちらかのために、トグル制御を選ぶことができる。
【００９１】
前述された実施形態では、ノードのさらに密度が濃いマトリックスを作成する処理段階が、コンテンツプロバイダが仮想世界内でコンテンツを定めた後であるが、システムがその世界の中でナビゲートすることを所望するユーザによって使用される前に、発生することが説明されている。もちろん、代わりに、システムがユーザによって使用されている間に、リアルタイムで実行されるこれらの細分されたノードを追加する処理段階の一部又は全てのどちらかが可能である。事実上、代替の構成は、仮想世界が多くの動的に移動するオブジェクトを含むときに（例えば、都市の仮想環境は移動する車、バス等を含む可能性がある）特に望ましい。この動的なケースでは、（建物等の静的なオブジェクトのための）何らかの細分だけが、ユーザがシステムにアクセスする前に事前に実行でき、残りの処理は、ユーザが経路が作成されるのを所望することを指定するたびに発生する余分なノードを追加する。処理段階はこのようにして、ユーザが経路が作成されるのを所望する瞬間に、これらの動的オブジェクトの位置を考慮に入れる。この機能性は、細分が発生する（例えば、仮想都市の中の通り）世界内のいくつかの領域、及びそれらが静止オブジェクト（例えばいくつかの建物の内部）だけしか含んでいないために、動的細分が発生しないときの世界内の他の領域を定めることによって、補足できるであろう。これは、（前述された）スイッチノードが異なる領域を区切るために使用されるときの典型的な例である。
【００９２】
さらに、経路生成手順のためにユーザによって選択される開始点と目的地点に対応する新しいノードを作成することが、リアルタイムで必要である可能性がある。ノードがこれらの場所にすでに存在していない場合には、システムはこのようなノードを自動的に作成するために使用されてよく、さらにすでに存在するノードマトリックスにそれらをリンクするために、開始ノードと目的地ノードに近い領域だけで新しく細分されたノードを追加するために処理を使用してよい。
【００９３】
複数のノードを備える仮想環境内で目的地ノードまでの新しい経路を生成する方法は、ここで説明される。該方法では、前記目的地ノードへの過去に作成された経路と関連付けられている１つ以上のノードを識別するノーダル情報が、新しい経路を決定するために処理される。処理は、単に、過去の経路に関連付けられているノードの１つ以上の勢力範囲(spheres of interest)及び／又はｉｎｔｅｒｅｓｔ＿ｃｏｍｐｏｎｅｎｔを更新し、前述された経路探索プロセスを繰り返すことを備えてもよい。代わりに、新しい経路を決定するために、前記の記憶されたノーダル情報に関してさらに複雑な処理が実行されてもよい。
【００９４】
特に、新しい経路は、過去の経路に沿って自動的にナビゲートされ、自動ナビゲーションモードから手動ナビゲーションモードに切り替わったユーザが、過去の経路の目的地まで自動ナビゲーションモードを再開できるようにしてもよい。これは、目的地ノードが移動した場合も含む、仮想環境内の１つ以上のノードが動的に変化している前記経路探索システムを使用しても実現できる。本発明の１つの実施形態では、過去の経路の妥当性検査は、これが目的地までの過去の経路に含まれていたノードの位置及び／又は特徴の変化のためにＬｏＳ又は他の制約に関して、もはや有効ではない可能性があるので実行される。過去に記憶されていたノーダル情報を再利用するための本発明のこの態様は、添付図面の図１４から図２２を参照してここでさらに詳細に説明されるであろう。
【００９５】
本発明の一実施形態は、仮想環境内で開始ノードから目的地ノードへ生成された第１の経路の一部への戻り経路を生成する方法を備える。第１の経路は、仮想環境のノーダルトポロジーが、経路が開始しなければならない点で追加のナビゲーションノードを含むように動的に再構成できる、どんな適切な経路生成プロセスによっても作成できる。
【００９６】
図１４から図１７では、ステップは、本発明の多様な実施形態に従って示される仮想環境内の、（ナビゲーションモードを切り替える又は変更することに同等となるように本文脈で定められる）ナビゲーションモードの間でトグルする方法と関連付けられて示されている。
【００９７】
本明細書において上述されている経路探索システムは、ユーザが自動的にナビゲーションされる（ステップ６２）初期原点から初期目的地までの経路を生成するために使用される（ステップ６０）。経路の原点は経路探索システムのナビゲーションノードと同一場所に配置されてよいが、経路探索システムは、ユーザが目的地まで自動的にナビゲートされることを要求する点で、開始ナビゲーションノードを自動的に作成してよい。同様に、目的地は自動経路生成のための目的地ナビゲーションノードに配置されてよいが、配置されない場合には、経路探索システムが、ユーザが所望される目的地を定めた目的地ナビゲーションノードを生成するであろう。
【００９８】
経路に沿った点では、経路はもはやアクティブにナビゲーションされなくなる。例えば、ユーザは、図１４で、初期の自動的にナビゲートされたナビゲーションモードから手動ナビゲートモードに切り替える（ステップ６４）ために、トグルをアクティブ化する。この出口点は経路のナビゲーションノードと同一場所に配置されてよい、あるいは同一場所に配置されなくてもよい。図１４から図２２に示されている実施形態では、これは経路のノード間にあるので、新しい出口ノードＦが出口点で生成される。しかしながら出口点は必ずしも経路のノードと一致する必要はない。このような状況では、出口ノードは作成されてよい、あるいは代わりに、経路上の出口ノードの前又は後のノードは、出口ノードとなるように定められてよい。図１８は、ＡからＥまでの経路に沿ってナビゲートするユーザが、経路のノードＢとＣの間の出口点でどのようにしてトグルオフ(toggle off)してよいのかを示している。
【００９９】
経路のノードに関する情報は、経路がもはやアクティブにナビゲートされなくなるときに記憶される。このようにして、経路の開始ノードと目的地ノードは、あらゆる中間ノードに関する情報と共に保存される。新しい出口ノードが定められる／作成される場合、これに関する情報も記憶される。その結果、ユーザは経路から自由自在に逸れ、自分が自動ナビゲーションモードを再開することを希望すると判断するまで、手動ナビゲーションモードを使用して探索できる（ステップ６６）。
【０１００】
図１４から図１７に示されている本発明の実施形態では、経路探索システムは、新しい経路を決定するときに、元の経路の記憶されているノーダル情報を処理する過去の経路の目的地ノードまでの新しい経路を生成しようとする。図１４、図１５、及び図１７では、誘導経路までの戻り経路が、目的地までの新しい経路を生成することにまつわる計算上の複雑さを削減するために１つ以上の基準に従って決定される。
【０１０１】
図１６では、記憶されているノーダル情報が増加したｉｎｔｅｒｅｓｔ＿ｃｏｍｐｏｎｅｎｔで更新され、新しい経路探索プロセスがこの増加したｉｎｔｅｒｅｓｔ＿ｃｏｍｐｏｎｅｎｔで実行される。これにより、新しい経路は元の経路と交差する可能性が高くなる。新しい経路が過去に生成された経路と交差する場合、目的地まで続行するために記憶されているノーダル情報を再利用できる。代わりに、図１７が示すように、新しい経路を目的地まで完全に無関係に再生成することが可能であるが、過去の経路に関連付けられているノードのｉｎｔｅｒｅｓｔ＿ｃｏｍｐｏｎｅｎｔを増加することによって、ユーザが過去に生成された経路に類似した経路を再開する可能性が高い。過去の経路に関連付けられているノーダル情報を再利用することにより、目的地までの新しい経路はさらに迅速に且つ効率的に決定でき、ユーザが自動ナビゲーションモードを再開する前に望ましくない遅延を経験するのを妨げる。これは経路が動的に生成されているときに特に有利である。
【０１０２】
本発明によると、生成された経路は経路探索システムにより許可された最適経路でなければならない。これは、元の誘導経路に戻る短くした経路であってよいが、必ずしも、ユーザが経路に沿って進行するにつれて動的に変化できる自動化された経路システムを定めるノードのネットワークのトポロジーのための可能性に起因するわけではない。
【０１０３】
ネットワークトポロジー自体が仮想環境とともに自立的に進化する可能性のために、オリジナルの経路は、ユーザが、元の経路のフィーチャが、元の経路がユーザプロファイルオプションに一致するために依然として関連性があるかどうかを判断するために、自動ナビゲーションモードにトグルして戻る（ステップ６８）ことを選択する点で再び有効になる。
【０１０４】
元の経路が依然として有効である場合には、新しい開始ノードがトグルバックポイント（ユーザが自動ナビゲーションを再開することを希望する点）で作成される（ステップ７０）。しかしながら、経路が無効である場合には、元の経路データは廃棄される（ステップ７２）。この後者のケースでは、目的地ノードだけを保持する新たな経路検索が開始される（ステップ７４）。代わりに、ユーザは元の経路に再び結合し続けることもできるが、これがもはや推奨されていないことを示すための警告が表示される（ステップ７２）。
【０１０５】
元の経路が依然として有効である場合、トグルバックポイントで生成された新しい開始ノードは次に、前述された経路探索システムを使用して戻り経路を生成するために使用されるネットワークに接続される。
【０１０６】
図１４では、戻り経路は、新しい開始ノードから、出口ノードから元の経路の目的地ノードまでの間の元の経路に沿って定められる全てのノードまで、平行ノード検索を実行することによって生成される。これらのノードは、それが最初に作成されたときの経路に沿って同じ位置にある必要はない。つまり元の経路の実際のトポロジーは進化した可能性がある。特定の新しいノードが、最初に誘導された経路に沿って現在存在する可能性がある、及び／又は最初に誘導された経路に沿ったノードのいくつかがもはや存在しないことも考えられる。したがって、高い関心フィーチャ重み又は大きな勢力範囲を有する移動オブジェクトと関連付けられているノードが移動した場合には、元の経路は相応して変化した可能性がある。本発明の一実施形態では、元の経路に沿った最も近いノードが一旦決定されると、元の経路に沿ったノードはそれ以上決定されない（ステップ７８）。これにより、最も近いノードの前の全てのノードを廃棄できるようになり、目的地までの誘導経路に沿ったままである以後のノードだけがとどまる。
【０１０７】
次に、ステップ７８で識別された最も近いノードに経路探索システムを使用して戻り経路が生成され、これは目的地まで最初に誘導された経路に沿って残る以後のノードと結合される（ステップ８０）。
【０１０８】
一旦ステップ８０で新しい誘導経路が生成されると、ナビゲーションシステムは次に目的地ノードに向かって、新しい誘導経路に沿ってユーザを自動的にナビゲートする（ステップ８２）。ユーザが目的地ノードに到達する（ステップ８４）と、自動ナビゲーションは停止し、ユーザは手動ナビゲーションを再開する（ステップ８４）。
【０１０９】
図１５、図１６及び図１７は、本発明のこれらの異なる実施形態における同等なステップについて、図１４に使用されている同じ番号付け方式を保持する。
【０１１０】
図１５では、仮想環境内のナビゲーションモード間でトグルする方法の別の実施形態が示され、図１５では図１４のステップ７８はステップ８８に置換される。
【０１１１】
図１５に示されている実施形態によると、元の経路が依然として有効である場合、新しい開始ノードは、図１４のステップ７６で説明されたのと同等な方法でノードのネットワークに接続される。しかしながら、戻り経路は元の経路の出口ノードだけに経路探索を実行することにより生成される。元の経路データに沿った残りの点が取り出され、出口ノードの前の全ての点が廃棄される。このオプションは、出口ノードがそれに関連付けられている進入角度を有する場合には使用できない可能性があり、ユーザは角度差制約を課すことによって、仮想環境とともに相対的にまっすぐな経路だけが生成されなければならないことを指定した（詳細については、付録ＩＩとして本願とともに出願された、「経路探索システム」と題される、本発明者の同時係属中の特許出願を参照されたい）。
【０１１２】
図１６では、図１４のステップ７８がステップ９０で置換される、仮想環境内のナビゲーションモードの間でトグルする方法の別の実施形態が示されている。この実施形態では、元の経路ノードに対する交差点で、付録ＩＩに説明されている勢力範囲技法を使用して新しい関心ノードが生成される。この結果、新たな経路探索を実施する（つまり、ｉｎｔｅｒｅｓｔ＿ｃｏｍｐｏｎｅｎｔが増加する）ときにさらに高い関心重みを有する、これらのノードが生じる。これらの関心ノードは、１回以上のトグルがナビゲーションモードの間で切り替えるためにユーザによってアクティブ化された後で、あるいは次の経路探索が新しい目的地で目標とされる場合に削除される。しかしながら、ｉｎｔｅｒｅｓｔ＿ｃｏｍｐｏｎｅｎｔを増加することによって、新規に生成された経路が過去に生成された経路のノードに遭遇する可能性が高い。
【０１１３】
図１７では、仮想環境内のナビゲーションモード間でトグルする方法の別の実施形態が示され、図１７では図１４のステップ７８はステップ９２で置換され、新しい戻り経路が生成される。
【０１１４】
図１７では、新たな経路探索が、元の目的地に対して実行され、該経路探索は元の経路上にある任意のノードに遭遇するとすぐに中断される。その結果、このノードは元の経路のためのリエントリノードであり、元の経路に沿って遭遇されたノードの前に存在した全てのノードが削除される（ステップ９２）。
【０１１５】
図１８は、目的地ノードが作成された目的地Ｅに対して開始ノードが作成された起点Ａからの例示的な経路を示す。生成された経路はナビゲーションノードＡ、Ｂ、Ｃ、Ｄ及びＥと交差し、Ａ〜Ｅからより直接的な経路が生成されるのを妨げるナビゲート不能オブジェクトを迂回する。
【０１１６】
図１８では、実線は、最初にＡ〜Ｅから生成され、それに沿ってユーザが自動的にナビゲートされた誘導経路を示している。破線の経路は、ユーザが手動ナビゲーションに切り替えた誘導経路に沿った点を表す。やはり図１８に示されているのは、ユーザが自動ナビゲーションモードから手動ナビゲーションモードに切り替えたときに生成された、（斜線が付いたノードアイコンで示されている）出口ノードＦである。この出口ノードは、生成された経路の一部を形成するが、元の誘導経路の一部ではなかった。
【０１１７】
やはり図１８にスマイルフェースアイコンで示されているのは、ユーザが自動ナビゲーションを再開することを決定する場所Ｇである。
【０１１８】
図１９Ａと図１９Ｂは、図１４のステップ７８の平行経路探索フィーチャが、出口ノードを含む誘導経路のノードに平行して、どのようにして複数の経路の探索を生成できるのかを示している（Ｄａｎ／Ｍａｒｔｉｎ−これは当てはまる、あるいは出口ノードは図１５のステップ８８だけに入る）。次にユーザに最も近いノードが決定され、元の誘導経路へのリエントリポイントを作成するために使用される。図１９Ａでは、最も近いノードは事実上出口ノードＦである。しかしながら、図１９Ｂでは、ノードＤは移動し、現在はノードＦにより近く配置されているため、ノードＤがリエントリポイントとして選択される。図１９Ｃは、（本明細書では再結合(rejoin）経路とも呼ばれる）戻り経路がノードＧとＤの間でどのようにして生成されるのかを示す。図１９Ｃの陰影の付いたナビゲーション点は全て削除され、経路は元の誘導経路に沿って目的地ノードＥまで続行する。一旦この経路が決定されると、自動ナビゲーションがノードＧからノードＥに沿ってノードＤを介して開始する。
【０１１９】
図２０Ａは、図１５のステップ９０の実現を示す。図２０Ａでは、経路は（例えばナビゲーションノードＨを介して）出口ノードＦに戻ると決定される。出口ノードＦは次に元の誘導経路へのリエントリの点になり、元の誘導経路に沿ってある全ての過去のノードは廃棄される（これらは図２０ＢのノードＡとＢを構成する）。
【０１２０】
図２１は、図１６のステップ９２の実現を示す。図２１に示されている実施形態では、ノードＣ、Ｄ及びＥ、及びＦがそのｉｎｔｅｒｅｓｔ＿ｃｏｍｐｏｎｅｎｔをさらに高い値に増加させる。経路探索プロセスが開始ノードＧから目的地ノードＥまでの新しい経路を決定するために実行されると、これらのノードの増加したｉｎｔｅｒｅｓｔ＿ｃｏｍｐｏｎｅｎｔが、目的地ノードＥまでナビゲーションノードＬだけではなくノードＣとＤも通過して生成された新しい経路を結果として生じる。
【０１２１】
図２２は、図１７に示されているステップ９２の実現を示す。図２２では、新しい経路が新しい開始ノードＧから目的地Ｅまでプロットされる。これはナビゲーションノードＪ及びＫ、そしてナビゲーションノードＤを取り入れる。ナビゲーションノードＤがＡ〜Ｅからの元の誘導経路に関連付けられるので、ナビゲーションノードＤで、新しい経路はＥへの元の誘導経路を再開する。これは、新しい経路を計算するのにまつわる計算の複雑さを削減する。
【０１２２】
このようにして本発明は、仮想環境において（つまり世界のいかなる仮想表現においても）戻り経路を生成する計算上の複雑さを削減する。仮想環境のトポロジーはメッシュ密度と、仮想世界を形成するノードの構成に依存する。ユーザが、どこで自動ナビゲーションモードに戻ることを希望しても、新しいノードを挿入することができなかった場合、仮想世界は、ユーザが手動でナビゲーションしなければならない場合に終わる可能性がある点の全てを予想するほど、十分に高いノーダルメッシュ密度で作成される必要があるであろう。これは、仮想世界自体の計算上の複雑さを高めることだけではなく、自動ナビゲーションのために経路を生成するときにも計算上の負担を増加するであろう。
【０１２３】
英国特許出願番号ＧＢ０４０７３８５．４号、ＧＢ０４０７３１１．０号、及びＧＢ０４０７３９．０．４号から優先権を主張する「経路探索システム」と題される、本発明者の同時係属中の国際特許出願の内容が、参照により本明細書に組み込まれる。当業者は、前記説明及び付録に関して本明細書に説明された本発明が、説明されたフィーチャに同等な機能を提供する多くのフィーチャによって実現されてよいことを理解する。当業者は、また、本発明が本明細書に開示されている実施形態に制限されないが、本明細書に説明されている本発明の一実施形態で説明されているフィーチャを組み込むことができる、又は本発明の別の実施形態への組み込みのために適応できる、あるいは同等な機能を有するいかなるフィーチャによっても置換でき、その結果本発明の適用範囲が添付された特許請求の範囲により定められるとおりであることが明らかである実施形態を特に含むために拡張することも理解するであろう。
【図面の簡単な説明】
【０１２４】
【図１】仮想世界環境における経路探索のためのシステムの概略図を示す。
【図２】仮想世界環境の図表示を示す。
【図３】図２の仮想世界環境の追加の図表示である。
【図４】図２の仮想世界環境の追加の図表示である。
【図５】図２の仮想世界環境の追加の図表示である。
【図６】図２の仮想世界環境の追加の図表示である。
【図７】図２の仮想世界環境の追加の図表示である。
【図８】図２の仮想世界環境の追加の図表示である。
【図９】図２の仮想世界環境の追加の図表示である。
【図１０】図２の仮想世界環境の追加の図表示である。
【図１１】図２の仮想世界環境の追加の図表示である。
【図１２】図２の仮想世界環境の追加の図表示である。
【図１３】仮想世界内の点を処理するための方法のフローチャートを示す。
【図１４】本発明の第１の実施形態による仮想環境内のナビゲーションモード間でトグルする方法を説明するフローチャートを示す。
【図１５】本発明の第２の実施形態による仮想環境内のナビゲーションモード間でトグルする方法を説明するフローチャートを示す。
【図１６】本発明の第３の実施形態による仮想環境内のナビゲーションモード間でトグルする方法を説明するフローチャートを示す。
【図１７】本発明の第４の実施形態による仮想環境内のナビゲーションモード間でトグルする方法を説明するフローチャートを示す。
【図１８】本発明の一実施形態に従ってユーザが自動化された経路を離れた仮想環境を概略して示す。
【図１９Ａ】図１４に示されている本発明の実施形態に従って、自動経路への戻り経路がどのようにして決定されてよいのかを概略して示す。
【図１９Ｂ】図１４に示されている本発明の実施形態に従って、自動経路への戻り経路がどのようにして決定されてよいのかを概略して示す。
【図１９Ｃ】図１４に示されている本発明の実施形態に従って、自動経路への戻り経路がどのようにして決定されてよいのかを概略して示す。
【図２０Ａ】図１５に示されている本発明の実施形態に従って、自動経路への戻り経路がどのようにして決定されてよいのかを概略して示す。
【図２０Ｂ】図１５に示されている本発明の実施形態に従って、自動経路への戻り経路がどのようにして決定されてよいのかを概略して示す。
【図２１】図１６に示されている本発明の実施形態に従って、自動経路への戻り経路がどのようにして決定されてよいのかを概略して示す。
【図２２】図１７に示されている本発明の実施形態に従って、自動経路への戻り経路がどのようにして決定されてよいのかを概略して示す。
【特許請求の範囲】
【請求項１】
複数のノードを備える仮想環境において目的地ノードまでの新しい経路を生成する方法であって、
前記目的地ノードへの過去に生成された経路と関連付けられている１つ以上のノードを識別するノーダル情報を記憶することと、
前記新しい経路のために開始ノードを定めるために前記仮想環境のトポロジーを動的に再構成することと、
前記過去に生成された経路の内の少なくとも１つのノードを含むことによって、前記目的地への新しい経路を決定するために前記記憶されたノーダル情報を処理することと、
を備える、方法。
【請求項２】
前記過去の経路はもはやアクティブにナビゲートされていないときに、出口点が前記過去の経路について決定される、請求項１に記載の方法。
【請求項３】
前記出口点は前記過去の経路上にノードを備える、請求項２に記載の方法。
【請求項４】
前記仮想環境は、前記出口点が前記過去の経路上にノードを備えない場合には、前記過去の経路上にノードを含むために動的に変更される、請求項２に記載の方法。
【請求項５】
前記処理するステップでは、前記新しい経路のための前記開始ノードに最も近いノードで前記過去に生成された経路に交差する、前記過去に生成された経路への戻り経路が決定され、前記新しい経路が前記戻り経路を含む、請求項１乃至請求項４のいずれか１項に記載の方法。
【請求項６】
前記最も近いノードは、前記過去の経路上の全てのノードへの戻り経路を並列して処理することによって決定される、請求項５に記載の方法。
【請求項７】
前記新しい経路は、前記出口点と前記目的地の間の前記過去の経路の全ての以後のノードを含む、請求項２に従属する前記請求項のいずれか１項に記載の方法。
【請求項８】
前記処理するステップにおいて、前記出口点で前記過去に生成された経路に交差する前記過去に生成された経路への戻り経路が決定され、前記新しい経路が前記戻り経路を含む、請求項２に従属する前記請求項のいずれか１項に記載の方法。
【請求項９】
前記過去に生成された経路の少なくとも１つのノードを含むことによって前記目的地への前記新しい経路を決定するために前記記憶されたノーダル情報を処理する前記ステップにおいて、前記ノーダル情報は前記過去の経路の前記ノードのｉｎｔｅｒｅｓｔ＿ｃｏｍｐｏｎｅｎｔを増加するために処理される、請求項１乃至請求項８のいずれか１項に記載の方法。
【請求項１０】
前記過去に生成された経路に沿ってナビゲートするために利用されるナビゲーションモードは、前記新しい経路に沿ってナビゲートするために利用されるナビゲーションモードと同じである、請求項１乃至請求項９のいずれか１項に記載の方法。
【請求項１１】
ユーザが自動ナビゲーションモードで前記過去の経路に沿って誘導され、前記ユーザは前記新しい経路の前記開始ノードへの手動でナビゲートされた経路を生成するために手動ナビゲーションモードに切り替えることができ、前記ユーザは自動ナビゲーションモードで前記目的地への前記新しい経路に沿って誘導される、請求項１０に記載の方法。
【請求項１２】
前記参加者は、前記仮想環境のいかなる点でも自分の意思で自動ナビゲーションモードと手動ナビゲーションモードの間で切り替えることができる、請求項１１に記載の方法。
【請求項１３】
前記参加者は前記自動ナビゲーションモードから前記手動ナビゲーションモードに切り替えるとき、出口ノードが前記過去に生成された経路に沿って生成される、請求項１０に記載の方法。
【請求項１４】
仮想環境において過去に生成された経路の一部への戻り経路を生成する方法であって、ユーザが開始ノードから目的地ノードへ前記過去に生成された経路に沿って自動的にナビゲートされることができ、前記仮想環境は、前記過去に生成された経路に沿った自動ナビゲーションモードから、前記仮想環境内に前記過去に生成された経路から逸れる第２の経路を生成する手動ナビゲーションモードに、前記ユーザが自分の意思で切り替えることができる能力をサポートし、
前記仮想環境における前記過去に作成された経路の前記開始ノード、目的地ノード及びあらゆる中間ノードを識別する情報を記憶することと、
前記第２の経路が終了する点で第２の開始ノードを定めるために前記仮想環境のトポロジーを動的に再構成することと、
リエントリノードで前記過去に生成された経路に交差する前記第２の開始ノードからの戻り経路を決定するために前記記憶されたノーダル情報を処理することと、
を備える、方法。
【請求項１５】
出口ノードが、前記第２の経路が開始する前記第１の経路に沿った点で定められ、情報を記憶する前記ステップが、前記仮想環境での前記第１の経路の前記出口ノード、開始ノード、目的地ノード及びあらゆる中間ノードを識別する情報を記憶することを備える、請求項１４に記載の方法。
【請求項１６】
前記記憶された情報を使用して前記第１の経路を確証するステップを実行することをさらに備え、前記第１の経路が依然として有効である場合に、
リエントリノードで前記第１の経路に交差する前記第２の開始ノードからの戻り経路を決定するために前記記憶されたノーダル情報を処理するステップを実行する、請求項１４又は請求項１５に記載の方法。
【請求項１７】
前記戻り経路及び前記目的地への前記第１の経路の続行する部分に沿って、前記ユーザを自動的にナビゲートすることをさらに備える、請求項１４乃至請求項１６のいずれか１項に記載の方法。
【請求項１８】
前記記憶された情報を処理する前記ステップにおいて、前記第２の開始ノードから前記第１の経路の保存されたノードへの戻り経路を決定するために、平行ノード探索が前記第１の経路の全ての保存されたノードについて前記第２の開始ノードから実行される、請求項１４乃至請求項１７のいずれか１項に記載の方法。
【請求項１９】
前記第１の経路の最も近い保存されたノードが前記リエントリノードとして決定される、請求項１４乃至請求項１８のいずれか１項に記載の方法。
【請求項２０】
前記第１の経路の出口ノードは前記リエントリノードとして決定される、請求項１５に従属するいずれか１の請求項に記載の方法。
【請求項２１】
前記ユーザは前記仮想環境の参加者である、請求項１乃至請求項２０のいずれか１項に記載の方法。
【請求項２２】
複数のノードを備える仮想環境内の目的地ノードへの新しい経路の生成をサポートするように構成されたシステムであって、
前記目的地ノードへの過去に生成された経路に関連付けられた１つ以上のノードを識別するノーダル情報を記憶するための手段と、
前記新しい経路のための開始ノードを定めるために前記仮想環境のトポロジーを動的に再構成するための手段と、
前記過去に生成された経路の内の少なくとも１つのノードを含むことによって前記目的地への前記新しい経路を決定するために前記記憶されたノーダル情報を処理するための処理手段と、
を備える、システム。
【請求項２３】
仮想環境で過去に生成された経路の一部への戻り経路の生成をサポートするように構成されたシステムであって、ユーザが開始ノードから目的地ノードまで前記過去に生成された経路に沿って自動的にナビゲートされることができ、前記仮想環境は、前記過去に生成された経路に沿った自動ナビゲーションモードから、前記仮想環境で前記過去に生成された経路から逸れる第２の経路を生成する手動ナビゲーションモードに自分の意思で切り替えるユーザの能力をサポートし、
前記仮想環境内の前記過去に生成された経路の前記開始ノード、目的地ノード及びあらゆる中間ノードを識別する情報を記憶するための手段と、
前記第２の経路が終了する点で第２の開始ノードを定めるために前記仮想環境のトポロジーを動的に再構成するための手段と、
リエントリノードで前記過去に生成された経路に交差する前記第２の開始ノードからの戻り経路を含む新しい経路を決定するために前記記憶されたノーダル情報を処理するための処理手段と、
を備える、システム。
【請求項２４】
前記システムは、ユーザが前記過去に生成された経路に沿って自動的にナビゲートできるようにするための手段をさらに備える、請求項２２又は請求項２３に記載のシステム。
【請求項２５】
前記システムは、ユーザが前記過去に生成された経路に沿った自動ナビゲーションモードから、手動ナビゲーションモードに切り替え、そして前記新しい経路に沿った自動ナビゲーションへ戻ることができるようにするための手段をさらに備える、請求項２４に記載のシステム。
【請求項２６】
請求項２５に記載のコンピュータシステム用のユーザインタフェースであって、前記ユーザインタフェースは、ユーザが前記過去に生成された経路に沿った自動ナビゲーションモードから手動ナビゲーションモードへ切り替え、そして前記新しい経路に沿った自動ナビゲーションへ戻ることができるように構成されるユーザインタフェース。
【請求項２７】
命令が１台以上のプロセッサにより実行されるときに、請求項１乃至請求項２１のいずれか１項に記載の方法を前記１台以上のプロセッサに実行させるための命令を備える、コンピュータプログラム。
【請求項２８】
搬送波で具現化され、命令が１台以上のプロセッサによって実行されるときに、請求項１乃至請求項２１のいずれか１項に記載の方法を１台以上のプロセッサに実行させるための命令を表す、コンピュータデータ信号。
【請求項２９】
命令が１台以上のプロセッサによって実行されるときに、請求項２２乃至請求項２５のいずれか1項に記載のシステムとして１台以上のプロセッサを動作させるための命令を表すコンピュータ読取可能コードを搬送する記憶媒体。
【請求項３０】
命令が１台以上のプロセッサによって実行されるときに、請求項２２乃至請求項２５のいずれか１項に記載のシステムとして１台以上のプロセッサを動作させるための命令を備える、コンピュータプログラム。
【請求項３１】
搬送波で具現化され、命令が１台以上のプロセッサによって実行されるときに、請求項２２乃至請求項２５のいずれか１項に記載のシステムとして１台以上のプロセッサを動作させるための命令を表す、コンピュータデータ信号。
【請求項３２】
命令が１台以上のプロセッサによって実行されるときに、請求項１乃至請求項２１のいずれか１項に記載の方法を１台以上のプロセッサに実行させるための命令を表す、コンピュータ読取可能コードを搬送する記憶媒体。
【請求項１】
複数のノードを備える仮想環境において目的地ノードまでの新しい経路を生成する方法であって、
前記目的地ノードへの過去に生成された経路と関連付けられている１つ以上のノードを識別するノーダル情報を記憶することと、
前記新しい経路のために開始ノードを定めるために前記仮想環境のトポロジーを動的に再構成することと、
前記過去に生成された経路の内の少なくとも１つのノードを含むことによって、前記目的地への新しい経路を決定するために前記記憶されたノーダル情報を処理することと、
を備える、方法。
【請求項２】
前記過去の経路はもはやアクティブにナビゲートされていないときに、出口点が前記過去の経路について決定される、請求項１に記載の方法。
【請求項３】
前記出口点は前記過去の経路上にノードを備える、請求項２に記載の方法。
【請求項４】
前記仮想環境は、前記出口点が前記過去の経路上にノードを備えない場合には、前記過去の経路上にノードを含むために動的に変更される、請求項２に記載の方法。
【請求項５】
前記処理するステップでは、前記新しい経路のための前記開始ノードに最も近いノードで前記過去に生成された経路に交差する、前記過去に生成された経路への戻り経路が決定され、前記新しい経路が前記戻り経路を含む、請求項１乃至請求項４のいずれか１項に記載の方法。
【請求項６】
前記最も近いノードは、前記過去の経路上の全てのノードへの戻り経路を並列して処理することによって決定される、請求項５に記載の方法。
【請求項７】
前記新しい経路は、前記出口点と前記目的地の間の前記過去の経路の全ての以後のノードを含む、請求項２に従属する前記請求項のいずれか１項に記載の方法。
【請求項８】
前記処理するステップにおいて、前記出口点で前記過去に生成された経路に交差する前記過去に生成された経路への戻り経路が決定され、前記新しい経路が前記戻り経路を含む、請求項２に従属する前記請求項のいずれか１項に記載の方法。
【請求項９】
前記過去に生成された経路の少なくとも１つのノードを含むことによって前記目的地への前記新しい経路を決定するために前記記憶されたノーダル情報を処理する前記ステップにおいて、前記ノーダル情報は前記過去の経路の前記ノードのｉｎｔｅｒｅｓｔ＿ｃｏｍｐｏｎｅｎｔを増加するために処理される、請求項１乃至請求項８のいずれか１項に記載の方法。
【請求項１０】
前記過去に生成された経路に沿ってナビゲートするために利用されるナビゲーションモードは、前記新しい経路に沿ってナビゲートするために利用されるナビゲーションモードと同じである、請求項１乃至請求項９のいずれか１項に記載の方法。
【請求項１１】
ユーザが自動ナビゲーションモードで前記過去の経路に沿って誘導され、前記ユーザは前記新しい経路の前記開始ノードへの手動でナビゲートされた経路を生成するために手動ナビゲーションモードに切り替えることができ、前記ユーザは自動ナビゲーションモードで前記目的地への前記新しい経路に沿って誘導される、請求項１０に記載の方法。
【請求項１２】
前記参加者は、前記仮想環境のいかなる点でも自分の意思で自動ナビゲーションモードと手動ナビゲーションモードの間で切り替えることができる、請求項１１に記載の方法。
【請求項１３】
前記参加者は前記自動ナビゲーションモードから前記手動ナビゲーションモードに切り替えるとき、出口ノードが前記過去に生成された経路に沿って生成される、請求項１０に記載の方法。
【請求項１４】
仮想環境において過去に生成された経路の一部への戻り経路を生成する方法であって、ユーザが開始ノードから目的地ノードへ前記過去に生成された経路に沿って自動的にナビゲートされることができ、前記仮想環境は、前記過去に生成された経路に沿った自動ナビゲーションモードから、前記仮想環境内に前記過去に生成された経路から逸れる第２の経路を生成する手動ナビゲーションモードに、前記ユーザが自分の意思で切り替えることができる能力をサポートし、
前記仮想環境における前記過去に作成された経路の前記開始ノード、目的地ノード及びあらゆる中間ノードを識別する情報を記憶することと、
前記第２の経路が終了する点で第２の開始ノードを定めるために前記仮想環境のトポロジーを動的に再構成することと、
リエントリノードで前記過去に生成された経路に交差する前記第２の開始ノードからの戻り経路を決定するために前記記憶されたノーダル情報を処理することと、
を備える、方法。
【請求項１５】
出口ノードが、前記第２の経路が開始する前記第１の経路に沿った点で定められ、情報を記憶する前記ステップが、前記仮想環境での前記第１の経路の前記出口ノード、開始ノード、目的地ノード及びあらゆる中間ノードを識別する情報を記憶することを備える、請求項１４に記載の方法。
【請求項１６】
前記記憶された情報を使用して前記第１の経路を確証するステップを実行することをさらに備え、前記第１の経路が依然として有効である場合に、
リエントリノードで前記第１の経路に交差する前記第２の開始ノードからの戻り経路を決定するために前記記憶されたノーダル情報を処理するステップを実行する、請求項１４又は請求項１５に記載の方法。
【請求項１７】
前記戻り経路及び前記目的地への前記第１の経路の続行する部分に沿って、前記ユーザを自動的にナビゲートすることをさらに備える、請求項１４乃至請求項１６のいずれか１項に記載の方法。
【請求項１８】
前記記憶された情報を処理する前記ステップにおいて、前記第２の開始ノードから前記第１の経路の保存されたノードへの戻り経路を決定するために、平行ノード探索が前記第１の経路の全ての保存されたノードについて前記第２の開始ノードから実行される、請求項１４乃至請求項１７のいずれか１項に記載の方法。
【請求項１９】
前記第１の経路の最も近い保存されたノードが前記リエントリノードとして決定される、請求項１４乃至請求項１８のいずれか１項に記載の方法。
【請求項２０】
前記第１の経路の出口ノードは前記リエントリノードとして決定される、請求項１５に従属するいずれか１の請求項に記載の方法。
【請求項２１】
前記ユーザは前記仮想環境の参加者である、請求項１乃至請求項２０のいずれか１項に記載の方法。
【請求項２２】
複数のノードを備える仮想環境内の目的地ノードへの新しい経路の生成をサポートするように構成されたシステムであって、
前記目的地ノードへの過去に生成された経路に関連付けられた１つ以上のノードを識別するノーダル情報を記憶するための手段と、
前記新しい経路のための開始ノードを定めるために前記仮想環境のトポロジーを動的に再構成するための手段と、
前記過去に生成された経路の内の少なくとも１つのノードを含むことによって前記目的地への前記新しい経路を決定するために前記記憶されたノーダル情報を処理するための処理手段と、
を備える、システム。
【請求項２３】
仮想環境で過去に生成された経路の一部への戻り経路の生成をサポートするように構成されたシステムであって、ユーザが開始ノードから目的地ノードまで前記過去に生成された経路に沿って自動的にナビゲートされることができ、前記仮想環境は、前記過去に生成された経路に沿った自動ナビゲーションモードから、前記仮想環境で前記過去に生成された経路から逸れる第２の経路を生成する手動ナビゲーションモードに自分の意思で切り替えるユーザの能力をサポートし、
前記仮想環境内の前記過去に生成された経路の前記開始ノード、目的地ノード及びあらゆる中間ノードを識別する情報を記憶するための手段と、
前記第２の経路が終了する点で第２の開始ノードを定めるために前記仮想環境のトポロジーを動的に再構成するための手段と、
リエントリノードで前記過去に生成された経路に交差する前記第２の開始ノードからの戻り経路を含む新しい経路を決定するために前記記憶されたノーダル情報を処理するための処理手段と、
を備える、システム。
【請求項２４】
前記システムは、ユーザが前記過去に生成された経路に沿って自動的にナビゲートできるようにするための手段をさらに備える、請求項２２又は請求項２３に記載のシステム。
【請求項２５】
前記システムは、ユーザが前記過去に生成された経路に沿った自動ナビゲーションモードから、手動ナビゲーションモードに切り替え、そして前記新しい経路に沿った自動ナビゲーションへ戻ることができるようにするための手段をさらに備える、請求項２４に記載のシステム。
【請求項２６】
請求項２５に記載のコンピュータシステム用のユーザインタフェースであって、前記ユーザインタフェースは、ユーザが前記過去に生成された経路に沿った自動ナビゲーションモードから手動ナビゲーションモードへ切り替え、そして前記新しい経路に沿った自動ナビゲーションへ戻ることができるように構成されるユーザインタフェース。
【請求項２７】
命令が１台以上のプロセッサにより実行されるときに、請求項１乃至請求項２１のいずれか１項に記載の方法を前記１台以上のプロセッサに実行させるための命令を備える、コンピュータプログラム。
【請求項２８】
搬送波で具現化され、命令が１台以上のプロセッサによって実行されるときに、請求項１乃至請求項２１のいずれか１項に記載の方法を１台以上のプロセッサに実行させるための命令を表す、コンピュータデータ信号。
【請求項２９】
命令が１台以上のプロセッサによって実行されるときに、請求項２２乃至請求項２５のいずれか1項に記載のシステムとして１台以上のプロセッサを動作させるための命令を表すコンピュータ読取可能コードを搬送する記憶媒体。
【請求項３０】
命令が１台以上のプロセッサによって実行されるときに、請求項２２乃至請求項２５のいずれか１項に記載のシステムとして１台以上のプロセッサを動作させるための命令を備える、コンピュータプログラム。
【請求項３１】
搬送波で具現化され、命令が１台以上のプロセッサによって実行されるときに、請求項２２乃至請求項２５のいずれか１項に記載のシステムとして１台以上のプロセッサを動作させるための命令を表す、コンピュータデータ信号。
【請求項３２】
命令が１台以上のプロセッサによって実行されるときに、請求項１乃至請求項２１のいずれか１項に記載の方法を１台以上のプロセッサに実行させるための命令を表す、コンピュータ読取可能コードを搬送する記憶媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９Ａ】
【図１９Ｂ】
【図１９Ｃ】
【図２０Ａ】
【図２０Ｂ】
【図２１】
【図２２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９Ａ】
【図１９Ｂ】
【図１９Ｃ】
【図２０Ａ】
【図２０Ｂ】
【図２１】
【図２２】
【公表番号】特表２００７−５３０９６７（Ｐ２００７−５３０９６７Ａ）
【公表日】平成１９年１１月１日（２００７．１１．１）
【国際特許分類】
【出願番号】特願２００７−５０５６０８（Ｐ２００７−５０５６０８）
【出願日】平成１７年３月１４日（２００５．３．１４）
【国際出願番号】ＰＣＴ／ＧＢ２００５／０００９６９
【国際公開番号】ＷＯ２００５／０９５８９４
【国際公開日】平成１７年１０月１３日（２００５．１０．１３）
【出願人】（３９００２８５８７）ブリティッシュ・テレコミュニケーションズ・パブリック・リミテッド・カンパニー (104)
【氏名又は名称原語表記】ＢＲＩＴＩＳＨ ＴＥＬＥＣＯＭＭＵＮＩＣＡＴＩＯＮＳ ＰＵＢＬＩＣ ＬＩＭＩＴＥＤ ＣＯＭＰＡＮＹ
【Ｆターム（参考）】
【公表日】平成１９年１１月１日（２００７．１１．１）
【国際特許分類】
【出願日】平成１７年３月１４日（２００５．３．１４）
【国際出願番号】ＰＣＴ／ＧＢ２００５／０００９６９
【国際公開番号】ＷＯ２００５／０９５８９４
【国際公開日】平成１７年１０月１３日（２００５．１０．１３）
【出願人】（３９００２８５８７）ブリティッシュ・テレコミュニケーションズ・パブリック・リミテッド・カンパニー (104)
【氏名又は名称原語表記】ＢＲＩＴＩＳＨ ＴＥＬＥＣＯＭＭＵＮＩＣＡＴＩＯＮＳ ＰＵＢＬＩＣ ＬＩＭＩＴＥＤ ＣＯＭＰＡＮＹ
【Ｆターム（参考）】
[ Back to top ]