経路探索装置、経路探索方法及びプログラム
【課題】任意のマップに対して経路探索結果を短時間に得ること。
【解決手段】経路探索の対象となるマップを示すマップ情報を取得するステップ（Ｓ１０１）と、前記マップ情報が示すマップ上に複数の代表点を設定するステップ（Ｓ１０２〜Ｓ１０４）と、前記代表点間の経路及びその距離を演算するステップ（Ｓ１０５）を含み、代表点間の経路及び距離を演算するステップ（Ｓ１０５）では、並列処理可能であってそれぞれ前記代表点のうち一部が関連づけられる複数のプロセッサのそれぞれにより、該プロセッサに関連づけられる前記代表点から他の前記代表点への経路のうち少なくとも１つ及びその距離を並列に演算する。
【解決手段】経路探索の対象となるマップを示すマップ情報を取得するステップ（Ｓ１０１）と、前記マップ情報が示すマップ上に複数の代表点を設定するステップ（Ｓ１０２〜Ｓ１０４）と、前記代表点間の経路及びその距離を演算するステップ（Ｓ１０５）を含み、代表点間の経路及び距離を演算するステップ（Ｓ１０５）では、並列処理可能であってそれぞれ前記代表点のうち一部が関連づけられる複数のプロセッサのそれぞれにより、該プロセッサに関連づけられる前記代表点から他の前記代表点への経路のうち少なくとも１つ及びその距離を並列に演算する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は経路探索装置、経路探索方法及びプログラムに関する。
【背景技術】
【０００２】
経路探索アルゴリズムは、列車路線探索やカーナビゲーションなど、多くの応用製品で用いられている基本的なコンピュータソフトウェアアルゴリズムの１つである。経路探索アルゴリズムは一般に計算量が膨大になることから、探索処理の一部を事前に実行するとともに、その結果を記憶手段に記憶しておく場合がある（下記特許文献１参照）。こうすれば、記憶手段に記憶された情報を用いて、経路探索結果を短時間に得ることができるようになる。
【特許文献１】特開平１０−９８８４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、ゲームに用いられる仮想空間のマップなど、内容が動的に変化するマップに対しては、上記のように探索処理の一部を事前に実行しておくのは困難であり、上記従来技術は、実在の道路地図や列車路線図など、内容が固定されたマップへの適用に限られるという問題があった。
【０００４】
本発明は上記課題に鑑みてなされたものであって、その目的は、任意のマップに対して経路探索結果を短時間に得ることができる経路探索装置、経路探索方法及びプログラムを提供することにある。
【課題を解決するための手段】
【０００５】
上記課題を解決するために、本発明に係る経路探索装置は、経路探索の対象となるマップを示すマップ情報を取得するマップ情報取得手段と、前記マップ情報が示すマップ上に複数の代表点を設定する代表点設定手段と、前記代表点間の経路及びその距離を演算する事前経路演算手段と、前記事前経路演算手段により演算される前記代表点間の経路及びその距離を記憶する記憶手段と、前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する経路探索手段と、を含み、前記事前経路演算手段は、並列処理可能であってそれぞれ前記代表点のうち一部が関連づけられる複数のプロセッサを含み、前記各プロセッサは、該プロセッサに関連づけられる前記代表点から他の前記代表点への経路のうち少なくとも１つ及びその距離を並列に演算する、ことを特徴とする。
【０００６】
また、本発明に係る経路探索方法は、経路探索の対象となるマップを示すマップ情報を取得するマップ情報取得ステップと、前記マップ情報が示すマップ上に複数の代表点を設定する代表点設定ステップと、前記代表点間の経路及びその距離を演算する事前経路演算ステップと、前記事前経路演算手段により演算される前記代表点間の経路及びその距離を記憶手段に格納する格納ステップと、前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する経路探索ステップと、を含み、前記事前経路演算ステップは、並列処理可能であってそれぞれ前記代表点のうち一部が関連づけられる複数のプロセッサのそれぞれにより、該プロセッサに関連づけられる前記代表点から他の前記代表点への経路のうち少なくとも１つ及びその距離を並列に演算する、ことを特徴とする。
【０００７】
また、本発明に係るプログラムは、経路探索の対象となるマップを示すマップ情報を取得するマップ情報取得手段、前記マップ情報が示すマップ上に複数の代表点を設定する代表点設定手段、前記代表点間の経路及びその距離を演算する事前経路演算手段、前記事前経路演算手段により演算される前記代表点間の経路及びその距離を記憶する記憶手段、及び前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する経路探索手段として、並列処理可能な複数のプロセッサを備えるコンピュータを機能させるためのプログラムであって、前記各プロセッサにはそれぞれ前記代表点のうち一部が割り当てられ、前記事前経路演算手段は、前記各プロセッサにより、該プロセッサに関連づけられる前記代表点から他の前記代表点への経路のうち少なくとも１つ及びその距離を並列に演算する、ことを特徴とする。なお、プログラムは、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭなど、コンピュータ読取可能な各種の情報記憶媒体に格納されてよい。
【０００８】
また、前記代表点設定手段は、前記マップ情報が示すマップ上に複数の部分領域を設定するとともに、前記各部分領域に対して１以上の代表点を設定してよい。このとき、前記事前経路演算手段に含まれる前記各プロセッサは、該プロセッサに関連づけられる前記代表点から、該代表点に係る前記部分領域に隣接する前記部分領域に対して設定される前記代表点のうち少なくとも１つへ、それら隣接する前記部分領域のみを通って至る経路及びその距離を演算してよい。また、前記各部分領域は共通の矩形状をなしてよい。このとき、前記事前経路演算手段に含まれる前記各プロセッサは、該プロセッサに関連づけられる前記代表点から、該代表点に係る前記部分領域の直交するいずれかの２辺に接する前記部分領域に対して設定される前記代表点のうち少なくとも１つへ、それら前記部分領域のみを通って至る経路及びその距離を演算するようにしてよい。
【０００９】
また、前記代表点設定手段は、すでに取得された前記マップ情報が示すマップとは異なるマップを示す前記マップ情報が前記マップ情報取得手段により取得される場合に、前記複数の部分領域のうちどの前記部分領域に変更があるかを判断するとともに、変更のある前記部分領域に対して１以上の前記代表点を再設定してよい。この場合、前記事前経路演算手段は、再設定される前記代表点を端点とする経路及びその距離を再演算してよい。
【００１０】
また、前記経路探索手段は、前記始点の位置に応じて前記代表点のうち１つを選択するとともに、前記始点から該選択される代表点への経路を決定する第１経路決定手段と、前記終点の位置に応じて前記代表点のうち１つを選択するとともに、該選択される代表点から前記終点への経路を決定する第２経路決定手段と、前記記憶手段に記憶される経路及びその距離に基づいて、前記選択される代表点間の経路を決定する第３経路決定手段と、を含んでよい。
【００１１】
また、本発明に係る経路探索装置は、経路探索の対象となるマップを示すマップ情報を取得するマップ情報取得手段と、前記マップ情報が示すマップ上に複数の部分領域を設定するとともに、前記各部分領域に対して１以上の代表点を設定する代表点設定手段と、前記各代表点から、該代表点に係る前記部分領域に隣接する前記部分領域に対して設定される前記代表点のうち少なくとも１つへ、それら隣接する前記部分領域のみを通って至る経路、及びその距離を演算する事前経路演算手段と、前記事前経路演算手段により演算される前記代表点間の経路及びその距離を記憶する記憶手段と、前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する経路探索手段と、を含み、前記代表点設定手段は、すでに取得された前記マップ情報が示すマップとは異なるマップを示す前記マップ情報が前記マップ情報取得手段により取得される場合に、前記複数の部分領域のうちどの前記部分領域に変更があるかを判断するとともに、変更のある前記部分領域に対して１以上の前記代表点を再設定し、前記事前経路演算手段は、再設定される前記代表点を端点とする経路及びその距離を再演算する、ことを特徴とする。
【００１２】
また、本発明に係る経路探索方法は、経路探索の対象となるマップを示すマップ情報を取得するステップと、前記マップ情報が示すマップ上に複数の部分領域を設定するとともに、前記各部分領域に対して１以上の代表点を設定するステップと、前記各代表点から、該代表点に係る前記部分領域に隣接する前記部分領域に対して設定される前記代表点のうち少なくとも１つへ、それら隣接する前記部分領域のみを通って至る経路、及びその距離を演算するステップと、演算される前記代表点間の経路及びその距離を記憶手段に格納するステップと、前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索するステップと、すでに取得された前記マップ情報が示すマップとは異なるマップを示す前記マップ情報が新たに取得される場合に、前記複数の部分領域のうちどの前記部分領域に変更があるかを判断するとともに、変更のある前記部分領域に対して１以上の前記代表点を再設定するステップと、再設定される前記代表点を端点とする経路及びその距離を再演算するステップと、を含むことを特徴とする。
【００１３】
また、本発明に係るプログラムは、経路探索の対象となるマップを示すマップ情報を取得する手段、前記マップ情報が示すマップ上に複数の部分領域を設定するとともに、前記各部分領域に対して１以上の代表点を設定する手段、前記各代表点から、該代表点に係る前記部分領域に隣接する前記部分領域に対して設定される前記代表点のうち少なくとも１つへ、それら隣接する前記部分領域のみを通って至る経路、及びその距離を演算する手段、演算される前記代表点間の経路及びその距離を記憶手段に格納する手段、前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する手段、すでに取得された前記マップ情報が示すマップとは異なるマップを示す前記マップ情報が新たに取得される場合に、前記複数の部分領域のうちどの前記部分領域に変更があるかを判断するとともに、変更のある前記部分領域に対して１以上の前記代表点を再設定する手段、及び再設定される前記代表点を端点とする経路及びその距離を再演算する手段としてコンピュータを機能させるためのプログラムである。このプログラムも、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭなど、コンピュータ読取可能な各種の情報記憶媒体に格納されてよい。
【００１４】
また、前記距離は、該距離に係る経路上に設定されるコストに基づいて演算されてよい。
【発明を実施するための最良の形態】
【００１５】
以下、本発明の実施形態について図面に基づき詳細に説明する。
【００１６】
図１は、本実施形態に係る経路探索装置として用いられるコンピュータのハードウェア構成を示す図である。同図に示すように、コンピュータ５０は、ＭＰＵ（Micro Processing Unit）５１と、メインメモリ６０と、画像処理部６４と、モニタ６６と、入出力処理部６８と、音声処理部７０と、スピーカ７２と、光ディスク読み取り部７４と、光ディスク７６と、ハードディスク７８と、インタフェース（Ｉ／Ｆ）８０と、操作デバイス８２と、ネットワークインタフェース８８と、を含んで構成されるコンピュータシステムである。また、図２は、ＭＰＵ５１の構成を示す図である。同図に示すように、ＭＰＵ５１は、メインプロセッサ５２と、サブプロセッサ５４ａ，５４ｂ，５４ｃ，５４ｄ，５４ｅ，５４ｆ，５４ｇ，５４ｈと、バス５６と、メモリコントローラ５８と、インタフェース（Ｉ／Ｆ）６２と、を含んで構成される。すなわち、ＭＰＵ５１は、それぞれ並列して情報処理を実行することができるメインプロセッサ５２及びサブプロセッサ５４ａ〜５４ｈを備える、マルチコアプロセッサである。
【００１７】
メインプロセッサ５２は、図示しないＲＯＭ（Read Only Memory）に記憶されるオペレーティングシステム、例えばＤＶＤ（Digital Versatile Disk）−ＲＯＭ等の光ディスク３６から読み出されるプログラム及びデータや、通信ネットワークを介して供給されるプログラム及びデータ等に基づいて、各種情報処理を行ったり、サブプロセッサ５４ａ〜５４ｈに対する制御を行ったりする。
【００１８】
サブプロセッサ５４ａ〜５４ｈは、メインプロセッサ５２からの指示に従って、各種情報処理を行ったり、コンピュータ５０の各部を、例えばＤＶＤ−ＲＯＭ等の光ディスク３６から読み出されるプログラム及びデータや、通信ネットワークを介して供給されるプログラム及びデータ等に基づいて制御したりする。
【００１９】
バス５６は、アドレス及びデータをコンピュータ５０の各部でやり取りするためのものである。メインプロセッサ５２、サブプロセッサ５４ａ〜５４ｈ、メモリコントローラ５８、インタフェース６２は、バス５６を介して相互にデータ授受可能に接続される。
【００２０】
メモリコントローラ５８は、メインプロセッサ５２及びサブプロセッサ５４ａ〜５４ｈからの指示に従って、メインメモリ６０へのアクセスを行う。メインメモリ６０には、光ディスク７６やハードディスク７８から読み出されたプログラム及びデータや、通信ネットワークを介して供給されたプログラム及びデータが必要に応じて書き込まれる。メインメモリ６０はメインプロセッサ５２やサブプロセッサ５４ａ〜５４ｈの作業用としても用いられる。
【００２１】
インタフェース６２には画像処理部６４及び入出力処理部６８が接続される。メインプロセッサ５２及びサブプロセッサ５４ａ〜５４ｈと、画像処理部６４又は入出力処理部６８と、の間のデータ授受はインタフェース６２を介して行われる。
【００２２】
画像処理部６４は、ＧＰＵ（Graphical Processing Unit）とフレームバッファとを含んで構成される。ＧＰＵは、メインプロセッサ５２やサブプロセッサ５４ａ〜５４ｈから供給される画像データに基づいてフレームバッファに各種画面を描画する。フレームバッファに形成された画面、すなわちＭＰＵ５１の実行結果を示す画面は、所定のタイミングでビデオ信号に変換されてモニタ６６に出力される。なお、モニタ６６には例えば家庭用テレビ受像機が用いられる。
【００２３】
入出力処理部６８には、音声処理部７０、光ディスク読み取り部７４、ハードディスク７８、インタフェース８０、ネットワークインタフェース８８が接続される。入出力処理部６８は、メインプロセッサ５２及びサブプロセッサ５４ａ〜５４ｈと、音声処理部７０、光ディスク読み取り部７４、ハードディスク７８、インタフェース８０、ネットワークインタフェース８８と、の間のデータ授受を制御する。
【００２４】
音声処理部７０は、ＳＰＵ（Sound Processing Unit）とサウンドバッファとを含んで構成される。サウンドバッファには、光ディスク７６やハードディスク７８から読み出されたゲーム音楽、ゲーム効果音やメッセージなどの各種音声データが記憶される。ＳＰＵは、これらの各種音声データを再生してスピーカ７２から出力させる。なお、スピーカ７２には例えば家庭用テレビ受像機の内蔵スピーカが用いられる。
【００２５】
光ディスク読み取り部７４は、メインプロセッサ５２及びサブプロセッサ５４ａ〜５４ｈからの指示に従って、光ディスク７６に記憶されたプログラムやデータを読み取る。なお、コンピュータ５０は、光ディスク７６以外の他のコンピュータ読取可能な情報記憶媒体に記憶されたプログラムやデータを読取可能に構成してもよい。
【００２６】
光ディスク７６は例えばＤＶＤ−ＲＯＭ等の一般的な光ディスク（コンピュータ読取可能な情報記憶媒体）である。また、ハードディスク７８は一般的なハードディスク装置である。光ディスク７６やハードディスク７８には各種プログラムやデータがコンピュータ読取可能に記憶される。
【００２７】
インタフェース（Ｉ／Ｆ）８０は、操作デバイス８２等の各種周辺機器を接続するためのインタフェースである。このようなインタフェースとしては、例えばＵＳＢ（Universal Serial Bus）インタフェースが用いられる。
【００２８】
操作デバイス８２は汎用操作入力手段であり、ユーザが各種操作（例えばゲーム操作）を入力するために用いられる。入出力処理部６８は、所定時間（例えば１／６０秒）ごとに操作デバイス８２から、その各部の状態を無線又は有線通信により取得し、その結果を表す操作信号をメインプロセッサ５２やサブプロセッサ５４ａ〜５４ｈに供給する。メインプロセッサ５２やサブプロセッサ５４ａ〜５４ｈは、ユーザによって行われた操作の内容をその操作信号に基づいて判断する。なお、コンピュータ５０は複数の操作デバイス８２を通信接続可能に構成されており、各操作デバイス８２から入力される操作信号に基づいて、メインプロセッサ５２やサブプロセッサ５４ａ〜５４ｈが各種処理を実行するようになっている。
【００２９】
操作デバイス８２は、ユーザがコンピュータ５０を操作するためのデバイスであって、ＵＳＢ等の有線通信手段、及びＢｌｕｅＴｏｏｔｈ（商標）やワイヤレスＬＡＮ等の無線通信手段を備える可搬型の小型コンピュータとして構成されており、操作デバイス５２において行われたユーザの操作内容を示す操作データがコンピュータ５０に有線又は無線で送信されるようになっている。
【００３０】
以下、上記ハードウェア構成を有するコンピュータ５０に、ゲームプログラム及び経路探索プログラムを実行させる例について説明する。ここで、ゲームプログラムは、例えば仮想空間でキャラクタが自在に移動するゲームに関するものである。また、経路探索プログラムは、ゲームプログラムにより起動され、該ゲームプログラムから、前記仮想空間のマップを示す情報（マップ情報）、前記マップにおける前記キャラクタの移動経路の出発地点（始点）及び目標地点（終点）を受け取る。そして、前記マップにおける始点及び終点間の最短移動経路を演算し、それをゲームプログラムに通知する。ゲームプログラムでは、こうして通知される経路に沿ってキャラクタを仮想空間内で移動させる処理を実行する。ゲームプログラムや経路探索プログラムは、例えば光ディスク７６に格納され、該光ディスクからコンピュータ５０にロードされる。そして、いずれもＭＰＵ５１によって実行される。
【００３１】
図３は、ゲームプログラムから経路探索プログラムに渡されるマップ情報が示すマップの一例を示している。同図に示すマップには、仮想的な山や建物が設けられていてキャラクタが進入できない移動不可領域４０，４１，４２、仮想的な舗装道路が存在してキャラクタが容易に移動できる低コスト領域４５、それ以外の高コスト領域４３，４４が配置されている。マップ情報は、移動不可領域４０，４１，４２の位置、低コスト領域４５の位置及びキャラクタにとっての移動のし易さ（例えば、単位距離を移動するのに必要となる時間）を示す数値（以下、「移動コスト」という。）、高コスト領域４３，４４の位置及び移動コストを特定可能な情報である。
【００３２】
経路探索プログラムは、図４に示すように、マップ情報が与えられるとマップ情報により示されるマップ全体を複数の部分領域１１〜３３に分割する。例えば、マップ情報により示されるマップが矩形であれば部分領域１１〜３３も矩形とし、それらの縦の長さが等しく、また横の長さも等しく、且つそれらの長さが予め決められた範囲に収まるようにする。ここでは、マップを縦方向に３分割、横方向に３分割して、合計９つの部分領域１１〜３３をマップ上に設定する。そして、各部分領域１１〜３３が縦横に整列配置される。その後、各部分領域１１〜３３に対して１以上の代表点を設定する。具体的には、各部分領域１１〜３３における移動可能な連続領域を検出して、各連続領域に対して１つの代表点を設定する。図４の例では、マップ中央の部分領域２２は中央に移動不可領域４１が横切っており、移動可能な領域が上下に分離し、それにより移動可能な連続領域が２つ形成されている。そこで、上側の連続領域に対しては代表点Ｒ２２ａが設定され、下側の連続領域に対しては代表点Ｒ２２ｂが設定されている。他の部分領域１１，１２，１３，２１，２３，３１，３２，３３はいずれも移動可能な連続領域を１つだけ有しており、それぞれ１つずつ代表点Ｒ１１，Ｒ１２，Ｒ１３，Ｒ２１，Ｒ２３，Ｒ３１，Ｒ３２，Ｒ３３が設定されている。これらの代表点は、例えば各連続領域の重心位置に基づいて決定される。すなわち、連続領域内の各位置の座標をその位置の移動コストで重み付けして重心位置を算出し、その重心位置が移動不可領域４０，４１，４２内でなければ、そこを代表点とする。また、移動不可領域４０，４１，４２内であれば、そのすぐ外側を代表点とする。
【００３３】
経路探索プログラムは、こうしてマップ情報が示すマップに部分領域１１〜３３を設定し、各部分領域に含まれる移動可能な連続領域に対して１つずつ代表点を設定すると、次に近接する代表点間の最短移動経路及びその距離（コスト付距離；経路上の位置の移動コストの総和）を算出する。具体的には、各部分領域について、その内側に設定されている代表点（仮始点）を取得するとともに、その部分領域の右側（存在すれば）及び下側に隣接する部分領域内に設定されている代表点（仮終点）を取得する。そして、これら仮始点及び仮終点間の最短移動経路及びその距離を算出する。これにより、図５において太い実線で示されるように、例えばマップ中央の部分領域２２の代表点Ｒ２２ａ及びＲ２２ｂについては、それらから右隣の部分領域２３の代表点Ｒ２３への最短移動経路及びその距離、下側に隣接する部分領域３２の代表点Ｒ３２への最短移動経路及びその距離が算出される。左隣の部分領域２１の代表点Ｒ２１、上側に隣接する部分領域１２の代表点Ｒ１２への最短移動経路及びその距離は、それぞれ部分領域２１及び部分領域１２に関する最短移動経路及びその距離として算出される。これにより結果的に、すべての隣接領域の組み合わせについて、各領域の代表点を結ぶ最短移動経路及びその距離が算出されることになる。このように、ある矩形の部分領域を注目領域とし、その注目領域の代表点と、該注目領域の直交するいずれかの２辺に接する部分領域の代表点と、の最短移動経路及びその距離を算出し、且つ、マップに設定されたすべての部分領域を順次注目領域とすることで、すべての必要な最短移動経路及びその距離が算出されることになる。
【００３４】
また、各最短移動経路は、隣接する２つの部分領域のみを通り、その他の部分領域は通過しないようにして設定される。これにより、ある部分領域に変更が生じたとしても、最短移動距離は、その変更のあった部分領域に設定された代表点から、及びそこに隣接する部分領域に設定された代表点に至るものだけを再計算すれば済み、他の最短移動経路はそのまま利用し続けることができる。
【００３５】
さらに、最短移動経路とは、経路上の位置の移動コストの総和が最小となる経路を意味しており、例えばダイクストラ法、Ａ＊（A-Star）アルゴリズムなど、公知の各種経路探索アルゴリズムにより、その距離とともに容易に算出することができる。また、代表点Ｒ２２ａから代表点Ｒ３２へは、他の部分領域（２３や２１など）を経由しなければキャラクタは移動できず、これら代表点間の最短移動経路は存在しないものとして扱われている。すなわち、本実施形態においては、仮始点と仮終点との間の最短移動経路としては、仮始点及び仮終点が含まれる、隣接する２つの部分領域以外の領域を通過しないものが算出されるようになっている。
【００３６】
経路探索プログラムは、こうして最短移動経路及びその距離を全ての近接する代表点の組み合わせについて算出すると、それらをハードディスク７８或いはメインメモリ６０に記憶する。
【００３７】
その後、経路探索プログラムは、ゲームプログラムからマップ上の位置である始点及び終点を受け取ると、それらの間の最短移動経路を算出する。具体的には、図６に示すように始点Ｓの位置に応じて、例えば移動コストを考慮して該始点Ｓに最も近い代表点Ｒ１１を選択し、また終点Ｇの位置に応じて、例えば移動コストを考慮して該終点Ｇに最も近い代表点Ｒ３３を選択する。なお、始点Ｓが属する部分領域１１の代表点Ｒ１１を選択してもよいし、同様に終点Ｇが属する部分領域３３の代表点Ｒ３３を選択してもよい。そして、始点Ｓから該始点Ｓに対して選択された代表点Ｒ１１への最短移動経路を、例えばダイクストラ法やＡ＊アルゴリズムなどにより算出する。同様に、終点Ｇに対して選択された代表点Ｒ３３から終点Ｇへの最短移動経路を、例えばダイクストラ法やＡ＊アルゴリズムなどにより算出する。さらに、始点Ｓ及び終点Ｇに対して選択された代表点Ｒ１１及びＲ３３の間の最短移動経路も、例えばダイクストラ法やＡ＊アルゴリズムなどにより算出する。このとき、最短移動経路は、始点Ｓに対して選択された代表点Ｒ１１から、隣接する部分領域の代表点を順に通過しながら、終点Ｇに対して選択された代表点Ｒ３３に至る経路として算出する。そして、順に通過する２つの代表点を結ぶ移動経路は、事前にハードディスク７８或いはメインメモリ６０に記憶されたものを用いる。すなわち、経路探索プログラムは、予めハードディスク７８或いはメインメモリ６０に記憶されている、全ての近接する代表点の組み合わせについて算出された最短移動経路及びその距離を参照しながら、代表点Ｒ１１から代表点Ｒ３３まで、事前に算出された最短移動経路を通って移動する経路のうち、代表点間の最短移動経路の距離の総和が最も小さくなるものを、これら代表点間の最短移動距離として選択する。ここでは、図６に示されるように、低コスト領域４５内を移動する経路が選択される。そして、こうして得られる始点Ｓから代表点Ｒ１１への最短移動経路、代表点Ｒ１１から代表点Ｒ３３への最短移動経路、代表点Ｒ３３から終点Ｇへの最短移動経路を連結して、始点Ｓから終点Ｇへの最短移動経路が算出される。そして、この経路を示す情報がゲームプログラムに渡される。上述のように、ゲームプログラムでは、この情報に従ってキャラクタを移動させるなどの処理を実行する。
【００３８】
また、経路探索プログラムでは、ゲームプログラムで用いられているマップに変更があり、この変更後のマップを示すマップ情報を受け取った場合に、ハードディスク７８或いはメインメモリ６０に既に記憶されている代表点間の最短移動経路及びその距離を更新するようにしている。例えば、図３のマップ中央に示される移動不可領域４１が、図７に示すように横方向に短い移動不可領域４１ａに変化し、それに伴ってより広い高コスト領域４３ａが現れた場合、図８に示すように変更後のマップを部分領域１１〜３３に分割して、変更前後のマップにおいて内容変更があった部分領域がどれであるかを調べる。そして、その変更があった部分領域について、再度、移動可能な連続領域を抽出するとともに、各連続領域に代表点を設定する。図７の例では、部分領域２２のみに変更があり、移動可能な連続領域が１つに減っている。この場合、部分領域２２の代表点は、Ｒ２２ａ及びＲ２２ｂの２つから、Ｒ２２の１つになる。
【００３９】
図９に示すように、経路探索プログラムでは、新しく設定された代表点Ｒ２２から、変更のあった部分領域２２の上下左右に隣接する部分領域１２、部分領域３２、部分領域２１、部分領域２３の代表点Ｒ１２、代表点Ｒ３２、代表点Ｒ２１、代表点Ｒ２３のそれぞれへの最短移動経路及びその距離を算出する。このときも、各最短移動経路は、隣接する２つの部分領域のみを通り、その他の部分領域は通過しないようにして設定される。そして、変更前の部分領域２２の代表点Ｒ２２ａ及びＲ２２ｂを端点とする最短移動経路及びその距離を、ハードディスク７８或いはメインメモリ６０から削除し、代わりに、新たに算出された代表点Ｒ２２を端点とする最短移動経路及びその距離を格納する。そして、その後は更新後の最短移動経路及びその距離の情報に基づいて、任意の始点及び終点間の最短移動経路を算出する。
【００４０】
ここで、経路探索装置として機能するコンピュータ５０の情報処理についてさらに説明する。図１０に示すように、経路探索プログラムを実行することによりコンピュータ５０では経路情報算出部９０、経路情報記憶部９１及び経路探索部９２が実現される。経路情報算出部９０は、ＭＰＵ５１を中心として構成されており、経路探索の対象となるマップを示すマップ情報を取得し、マップ上に複数の代表点を設定する。そして、近接する代表点間の最短移動経路及びその距離を演算して、それらの情報を経路情報記憶部９１に格納する。また、マップ情報に変更があった場合には、経路情報記憶部９１に記憶される最短移動経路及びその距離を更新する。上述のようにＭＰＵ５１は、サブプロセッサ５４ａ〜５４ｈを備えており、代表点間の最短移動経路を算出する際には、各サブプロセッサ５４ａ〜５４ｈに対して部分領域が割り当てられ、これにより該部分領域の代表点が関連づけられる。例えば、サブプロセッサ５４ａ〜５４ｈのそれぞれに対して、ランダムに、或いはマップの左上から順に選択される略同数の部分領域が割り当てられる。そして、各サブプロセッサ５４ａ〜５４ｈは、該プロセッサに割り当てられた部分領域の代表点から、右側及び下側に隣接する部分領域の代表点への最短移動経路及びその距離を、それぞれ並列に演算する。こうして、最短移動経路の演算を高速に行うようにしている。
【００４１】
経路情報記憶部９１は、ハードディスク７８或いはメインメモリ６０を中心として構成されており、経路情報算出部９０により算出される代表点間の最短移動経路及びその距離を記憶する。また、経路探索部９２は、ＭＰＵ５１を中心として構成されており、経路情報記憶部９１の記憶内容を参照しながら、任意の始点及び終点間の最短移動経路を算出する。
【００４２】
図１１は、経路情報算出部９０による準備処理を示している。この処理は、ゲームプログラムなどの外部プログラムからマップ情報を最初に受け取った場合に実行されるものであり、まずマップ情報を取得すると、この情報が示すマップを縦横に等間隔に分割して複数の矩形の部分領域を設定する（Ｓ１０２）。次に、それらの部分領域を各サブプロセッサ５４ａ〜５４ｈに割り当て、各プロセッサ５４ａ〜５４ｈが並列に、割り当てられた部分領域内の可動範囲（移動可能な連続領域）を抽出する（Ｓ１０３）。次に、各可動範囲に対して代表点を設定する（Ｓ１０４）。
【００４３】
全ての部分領域に対して代表点が設定されると、次に各プロセッサ５４ａ〜５４ｈが並列に、割り当てられた部分領域の代表点から、右側及び下側に隣接する部分領域の代表点に至る最短移動経路及びその距離を算出する（Ｓ１０５）。全ての部分領域に対して代表点が設定されるまで待ってから、各プロセッサ５４ａ〜５４ｈが、割り当てられた部分領域について最短移動経路及びその距離の算出を開始することで、隣接する部分領域の代表点が算出されるまで演算処理の待機を強いられるといった無駄をなくすことができ、これにより最短移動経路及びその距離の計算を効率化できる。なお、最短移動距離及びその距離を算出する際（Ｓ１０５）と、可動範囲の抽出（Ｓ１０３）及び代表点の設定（Ｓ１０４）を行う際とで、プロセッサ５４ａ〜５４ｈと部分領域との割り当ては異なってよい。その後、各プロセッサ５４ａ〜５４ｈで算出される最短移動経路及びその距離を経路情報記憶部９１に格納する（Ｓ１０６）。
【００４４】
次に、図１２は経路情報算出部９０による、経路情報記憶部９１の記憶内容を更新する処理、及び経路探索部９２による、経路情報記憶部９１の最新の記憶内容に基づく経路探索処理を示している。同図に示される処理は、例えばゲームプログラムなどの外部プログラムから始点及び終点が与えられた場合に実行される。この処理では、まず経路情報算出部９０がマップの更新があったか否かを判断する（Ｓ２０１）。例えば、外部プログラムからマップの更新の有無が与えられる場合には、与えられた情報から直ちに判断できる。また、最新のマップ情報がハードディスク７８に格納されている場合には、その更新時刻により更新の有無を判断できる。そして、マップ情報の更新があった場合には、最新のマップ情報を取得して（Ｓ２０２）、どの部分領域に変更があったかを調べる（Ｓ２０３）。そして、それら変更があった部分領域を各サブプロセッサ５４ａ〜５４ｈに割り当て、各プロセッサ５４ａ〜５４ｈが並列に、割り当てられた部分領域内の可動範囲を抽出する（Ｓ２０４）。次に、各可動範囲に対して代表点を設定する（Ｓ２０５）。全ての変更のあった部分領域に対して代表点が設定されると、次に各プロセッサ５４ａ〜５４ｈが並列に、割り当てられた部分領域の代表点から、右側及び下側に隣接する部分領域の代表点に至る最短移動経路及びその距離を算出する（Ｓ２０６）。その後、変更前の部分領域の代表点を端点とする最短移動経路及びその距離を経路情報記憶部９１から削除するとともに、各プロセッサ５４ａ〜５４ｈで新たに算出された最短移動経路及びその距離を経路情報記憶部９１に格納する（Ｓ２０７）。Ｓ２０１でマップが更新されていないと判断すると、Ｓ２０２〜Ｓ２０７の処理はスキップされる。
【００４５】
その後、ゲームプログラムなどの外部プログラムから与えられる始点及び終点の座標を取得し（Ｓ２０８）、始点から最も近い代表点を選択するとともに、その選択された代表点への最短移動経路を算出する（Ｓ２０９）。また、終点に最も近い代表点を選択するとともに、そこから終点への最短移動経路を算出する（Ｓ２１０）。さらに、Ｓ２０９及びＳ２１０で選択される代表点間の最短移動経路を算出する（Ｓ２１１）。そして、Ｓ２０９〜Ｓ２１１で算出される最短移動経路を連結して、外部プログラムから与えられる始点及び終点を結ぶ最短移動経路の情報を生成し、これを元の外部プログラムに返す（Ｓ２１２）。
【００４６】
以上説明した実施形態によると、マップ情報が示すマップに複数の代表点を設定し、サブプロセッサ５４ａ〜５４ｈにこれらの代表点を関連づけ、代表点間の最短移動経路及びその距離をサブプロセッサ５４ａ〜５４ｈにより並列処理するようにしたので、マップ情報が与えられてから短時間で代表点間の最短移動経路を演算することができる。
【図面の簡単な説明】
【００４７】
【図１】本発明の一実施形態に係る経路探索装置として機能するコンピュータのハードウェア構成を示す図である。
【図２】ＭＰＵの構成を示す図である。
【図３】マップ情報が示すマップの一例を示す図である。
【図４】部分領域及び代表点の設定を示す図である。
【図５】事前の最短移動経路の算出を示す図である。
【図６】任意の始点及び終点間の最短移動経路の算出を示す図である。
【図７】変更されたマップの一例を示す図である。
【図８】変更されたマップに対する部分領域及び代表点の設定を示す図である。
【図９】変更のある部分領域に関する最短移動経路の更新を示す図である。
【図１０】本発明の一実施形態に係る経路探索装置の機能ブロック図である。
【図１１】事前の最短移動経路の算出を示すフロー図である。
【図１２】任意の始点及び終点間の最短移動経路の算出を示すフロー図である。
【符号の説明】
【００４８】
１１，１２，１３，２１，２２，２３，３１，３２，３３ 部分領域、４０，４１，４１ａ，４２ 移動不可領域、４３，４３ａ，４４ 高コスト領域、４５ 低コスト領域、５０ コンピュータ、５１ ＭＰＵ、５２ メインプロセッサ、５４ａ〜５４ｈ サブプロセッサ、５６ バス、５８ メモリコントローラ、６０ メインメモリ、６２，８０ インタフェース、６４ 画像処理部、６６ モニタ、６８ 入出力処理部、７０ 音声処理部、７２ スピーカ、７４ 光ディスク読み取り部、７６ 光ディスク、７８ ハードディスク、８２ 操作デバイス、８８ ネットワークインタフェース、９０ 経路情報算出部、９１ 経路情報記憶部、９２ 経路探索部。
【技術分野】
【０００１】
本発明は経路探索装置、経路探索方法及びプログラムに関する。
【背景技術】
【０００２】
経路探索アルゴリズムは、列車路線探索やカーナビゲーションなど、多くの応用製品で用いられている基本的なコンピュータソフトウェアアルゴリズムの１つである。経路探索アルゴリズムは一般に計算量が膨大になることから、探索処理の一部を事前に実行するとともに、その結果を記憶手段に記憶しておく場合がある（下記特許文献１参照）。こうすれば、記憶手段に記憶された情報を用いて、経路探索結果を短時間に得ることができるようになる。
【特許文献１】特開平１０−９８８４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、ゲームに用いられる仮想空間のマップなど、内容が動的に変化するマップに対しては、上記のように探索処理の一部を事前に実行しておくのは困難であり、上記従来技術は、実在の道路地図や列車路線図など、内容が固定されたマップへの適用に限られるという問題があった。
【０００４】
本発明は上記課題に鑑みてなされたものであって、その目的は、任意のマップに対して経路探索結果を短時間に得ることができる経路探索装置、経路探索方法及びプログラムを提供することにある。
【課題を解決するための手段】
【０００５】
上記課題を解決するために、本発明に係る経路探索装置は、経路探索の対象となるマップを示すマップ情報を取得するマップ情報取得手段と、前記マップ情報が示すマップ上に複数の代表点を設定する代表点設定手段と、前記代表点間の経路及びその距離を演算する事前経路演算手段と、前記事前経路演算手段により演算される前記代表点間の経路及びその距離を記憶する記憶手段と、前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する経路探索手段と、を含み、前記事前経路演算手段は、並列処理可能であってそれぞれ前記代表点のうち一部が関連づけられる複数のプロセッサを含み、前記各プロセッサは、該プロセッサに関連づけられる前記代表点から他の前記代表点への経路のうち少なくとも１つ及びその距離を並列に演算する、ことを特徴とする。
【０００６】
また、本発明に係る経路探索方法は、経路探索の対象となるマップを示すマップ情報を取得するマップ情報取得ステップと、前記マップ情報が示すマップ上に複数の代表点を設定する代表点設定ステップと、前記代表点間の経路及びその距離を演算する事前経路演算ステップと、前記事前経路演算手段により演算される前記代表点間の経路及びその距離を記憶手段に格納する格納ステップと、前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する経路探索ステップと、を含み、前記事前経路演算ステップは、並列処理可能であってそれぞれ前記代表点のうち一部が関連づけられる複数のプロセッサのそれぞれにより、該プロセッサに関連づけられる前記代表点から他の前記代表点への経路のうち少なくとも１つ及びその距離を並列に演算する、ことを特徴とする。
【０００７】
また、本発明に係るプログラムは、経路探索の対象となるマップを示すマップ情報を取得するマップ情報取得手段、前記マップ情報が示すマップ上に複数の代表点を設定する代表点設定手段、前記代表点間の経路及びその距離を演算する事前経路演算手段、前記事前経路演算手段により演算される前記代表点間の経路及びその距離を記憶する記憶手段、及び前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する経路探索手段として、並列処理可能な複数のプロセッサを備えるコンピュータを機能させるためのプログラムであって、前記各プロセッサにはそれぞれ前記代表点のうち一部が割り当てられ、前記事前経路演算手段は、前記各プロセッサにより、該プロセッサに関連づけられる前記代表点から他の前記代表点への経路のうち少なくとも１つ及びその距離を並列に演算する、ことを特徴とする。なお、プログラムは、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭなど、コンピュータ読取可能な各種の情報記憶媒体に格納されてよい。
【０００８】
また、前記代表点設定手段は、前記マップ情報が示すマップ上に複数の部分領域を設定するとともに、前記各部分領域に対して１以上の代表点を設定してよい。このとき、前記事前経路演算手段に含まれる前記各プロセッサは、該プロセッサに関連づけられる前記代表点から、該代表点に係る前記部分領域に隣接する前記部分領域に対して設定される前記代表点のうち少なくとも１つへ、それら隣接する前記部分領域のみを通って至る経路及びその距離を演算してよい。また、前記各部分領域は共通の矩形状をなしてよい。このとき、前記事前経路演算手段に含まれる前記各プロセッサは、該プロセッサに関連づけられる前記代表点から、該代表点に係る前記部分領域の直交するいずれかの２辺に接する前記部分領域に対して設定される前記代表点のうち少なくとも１つへ、それら前記部分領域のみを通って至る経路及びその距離を演算するようにしてよい。
【０００９】
また、前記代表点設定手段は、すでに取得された前記マップ情報が示すマップとは異なるマップを示す前記マップ情報が前記マップ情報取得手段により取得される場合に、前記複数の部分領域のうちどの前記部分領域に変更があるかを判断するとともに、変更のある前記部分領域に対して１以上の前記代表点を再設定してよい。この場合、前記事前経路演算手段は、再設定される前記代表点を端点とする経路及びその距離を再演算してよい。
【００１０】
また、前記経路探索手段は、前記始点の位置に応じて前記代表点のうち１つを選択するとともに、前記始点から該選択される代表点への経路を決定する第１経路決定手段と、前記終点の位置に応じて前記代表点のうち１つを選択するとともに、該選択される代表点から前記終点への経路を決定する第２経路決定手段と、前記記憶手段に記憶される経路及びその距離に基づいて、前記選択される代表点間の経路を決定する第３経路決定手段と、を含んでよい。
【００１１】
また、本発明に係る経路探索装置は、経路探索の対象となるマップを示すマップ情報を取得するマップ情報取得手段と、前記マップ情報が示すマップ上に複数の部分領域を設定するとともに、前記各部分領域に対して１以上の代表点を設定する代表点設定手段と、前記各代表点から、該代表点に係る前記部分領域に隣接する前記部分領域に対して設定される前記代表点のうち少なくとも１つへ、それら隣接する前記部分領域のみを通って至る経路、及びその距離を演算する事前経路演算手段と、前記事前経路演算手段により演算される前記代表点間の経路及びその距離を記憶する記憶手段と、前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する経路探索手段と、を含み、前記代表点設定手段は、すでに取得された前記マップ情報が示すマップとは異なるマップを示す前記マップ情報が前記マップ情報取得手段により取得される場合に、前記複数の部分領域のうちどの前記部分領域に変更があるかを判断するとともに、変更のある前記部分領域に対して１以上の前記代表点を再設定し、前記事前経路演算手段は、再設定される前記代表点を端点とする経路及びその距離を再演算する、ことを特徴とする。
【００１２】
また、本発明に係る経路探索方法は、経路探索の対象となるマップを示すマップ情報を取得するステップと、前記マップ情報が示すマップ上に複数の部分領域を設定するとともに、前記各部分領域に対して１以上の代表点を設定するステップと、前記各代表点から、該代表点に係る前記部分領域に隣接する前記部分領域に対して設定される前記代表点のうち少なくとも１つへ、それら隣接する前記部分領域のみを通って至る経路、及びその距離を演算するステップと、演算される前記代表点間の経路及びその距離を記憶手段に格納するステップと、前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索するステップと、すでに取得された前記マップ情報が示すマップとは異なるマップを示す前記マップ情報が新たに取得される場合に、前記複数の部分領域のうちどの前記部分領域に変更があるかを判断するとともに、変更のある前記部分領域に対して１以上の前記代表点を再設定するステップと、再設定される前記代表点を端点とする経路及びその距離を再演算するステップと、を含むことを特徴とする。
【００１３】
また、本発明に係るプログラムは、経路探索の対象となるマップを示すマップ情報を取得する手段、前記マップ情報が示すマップ上に複数の部分領域を設定するとともに、前記各部分領域に対して１以上の代表点を設定する手段、前記各代表点から、該代表点に係る前記部分領域に隣接する前記部分領域に対して設定される前記代表点のうち少なくとも１つへ、それら隣接する前記部分領域のみを通って至る経路、及びその距離を演算する手段、演算される前記代表点間の経路及びその距離を記憶手段に格納する手段、前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する手段、すでに取得された前記マップ情報が示すマップとは異なるマップを示す前記マップ情報が新たに取得される場合に、前記複数の部分領域のうちどの前記部分領域に変更があるかを判断するとともに、変更のある前記部分領域に対して１以上の前記代表点を再設定する手段、及び再設定される前記代表点を端点とする経路及びその距離を再演算する手段としてコンピュータを機能させるためのプログラムである。このプログラムも、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭなど、コンピュータ読取可能な各種の情報記憶媒体に格納されてよい。
【００１４】
また、前記距離は、該距離に係る経路上に設定されるコストに基づいて演算されてよい。
【発明を実施するための最良の形態】
【００１５】
以下、本発明の実施形態について図面に基づき詳細に説明する。
【００１６】
図１は、本実施形態に係る経路探索装置として用いられるコンピュータのハードウェア構成を示す図である。同図に示すように、コンピュータ５０は、ＭＰＵ（Micro Processing Unit）５１と、メインメモリ６０と、画像処理部６４と、モニタ６６と、入出力処理部６８と、音声処理部７０と、スピーカ７２と、光ディスク読み取り部７４と、光ディスク７６と、ハードディスク７８と、インタフェース（Ｉ／Ｆ）８０と、操作デバイス８２と、ネットワークインタフェース８８と、を含んで構成されるコンピュータシステムである。また、図２は、ＭＰＵ５１の構成を示す図である。同図に示すように、ＭＰＵ５１は、メインプロセッサ５２と、サブプロセッサ５４ａ，５４ｂ，５４ｃ，５４ｄ，５４ｅ，５４ｆ，５４ｇ，５４ｈと、バス５６と、メモリコントローラ５８と、インタフェース（Ｉ／Ｆ）６２と、を含んで構成される。すなわち、ＭＰＵ５１は、それぞれ並列して情報処理を実行することができるメインプロセッサ５２及びサブプロセッサ５４ａ〜５４ｈを備える、マルチコアプロセッサである。
【００１７】
メインプロセッサ５２は、図示しないＲＯＭ（Read Only Memory）に記憶されるオペレーティングシステム、例えばＤＶＤ（Digital Versatile Disk）−ＲＯＭ等の光ディスク３６から読み出されるプログラム及びデータや、通信ネットワークを介して供給されるプログラム及びデータ等に基づいて、各種情報処理を行ったり、サブプロセッサ５４ａ〜５４ｈに対する制御を行ったりする。
【００１８】
サブプロセッサ５４ａ〜５４ｈは、メインプロセッサ５２からの指示に従って、各種情報処理を行ったり、コンピュータ５０の各部を、例えばＤＶＤ−ＲＯＭ等の光ディスク３６から読み出されるプログラム及びデータや、通信ネットワークを介して供給されるプログラム及びデータ等に基づいて制御したりする。
【００１９】
バス５６は、アドレス及びデータをコンピュータ５０の各部でやり取りするためのものである。メインプロセッサ５２、サブプロセッサ５４ａ〜５４ｈ、メモリコントローラ５８、インタフェース６２は、バス５６を介して相互にデータ授受可能に接続される。
【００２０】
メモリコントローラ５８は、メインプロセッサ５２及びサブプロセッサ５４ａ〜５４ｈからの指示に従って、メインメモリ６０へのアクセスを行う。メインメモリ６０には、光ディスク７６やハードディスク７８から読み出されたプログラム及びデータや、通信ネットワークを介して供給されたプログラム及びデータが必要に応じて書き込まれる。メインメモリ６０はメインプロセッサ５２やサブプロセッサ５４ａ〜５４ｈの作業用としても用いられる。
【００２１】
インタフェース６２には画像処理部６４及び入出力処理部６８が接続される。メインプロセッサ５２及びサブプロセッサ５４ａ〜５４ｈと、画像処理部６４又は入出力処理部６８と、の間のデータ授受はインタフェース６２を介して行われる。
【００２２】
画像処理部６４は、ＧＰＵ（Graphical Processing Unit）とフレームバッファとを含んで構成される。ＧＰＵは、メインプロセッサ５２やサブプロセッサ５４ａ〜５４ｈから供給される画像データに基づいてフレームバッファに各種画面を描画する。フレームバッファに形成された画面、すなわちＭＰＵ５１の実行結果を示す画面は、所定のタイミングでビデオ信号に変換されてモニタ６６に出力される。なお、モニタ６６には例えば家庭用テレビ受像機が用いられる。
【００２３】
入出力処理部６８には、音声処理部７０、光ディスク読み取り部７４、ハードディスク７８、インタフェース８０、ネットワークインタフェース８８が接続される。入出力処理部６８は、メインプロセッサ５２及びサブプロセッサ５４ａ〜５４ｈと、音声処理部７０、光ディスク読み取り部７４、ハードディスク７８、インタフェース８０、ネットワークインタフェース８８と、の間のデータ授受を制御する。
【００２４】
音声処理部７０は、ＳＰＵ（Sound Processing Unit）とサウンドバッファとを含んで構成される。サウンドバッファには、光ディスク７６やハードディスク７８から読み出されたゲーム音楽、ゲーム効果音やメッセージなどの各種音声データが記憶される。ＳＰＵは、これらの各種音声データを再生してスピーカ７２から出力させる。なお、スピーカ７２には例えば家庭用テレビ受像機の内蔵スピーカが用いられる。
【００２５】
光ディスク読み取り部７４は、メインプロセッサ５２及びサブプロセッサ５４ａ〜５４ｈからの指示に従って、光ディスク７６に記憶されたプログラムやデータを読み取る。なお、コンピュータ５０は、光ディスク７６以外の他のコンピュータ読取可能な情報記憶媒体に記憶されたプログラムやデータを読取可能に構成してもよい。
【００２６】
光ディスク７６は例えばＤＶＤ−ＲＯＭ等の一般的な光ディスク（コンピュータ読取可能な情報記憶媒体）である。また、ハードディスク７８は一般的なハードディスク装置である。光ディスク７６やハードディスク７８には各種プログラムやデータがコンピュータ読取可能に記憶される。
【００２７】
インタフェース（Ｉ／Ｆ）８０は、操作デバイス８２等の各種周辺機器を接続するためのインタフェースである。このようなインタフェースとしては、例えばＵＳＢ（Universal Serial Bus）インタフェースが用いられる。
【００２８】
操作デバイス８２は汎用操作入力手段であり、ユーザが各種操作（例えばゲーム操作）を入力するために用いられる。入出力処理部６８は、所定時間（例えば１／６０秒）ごとに操作デバイス８２から、その各部の状態を無線又は有線通信により取得し、その結果を表す操作信号をメインプロセッサ５２やサブプロセッサ５４ａ〜５４ｈに供給する。メインプロセッサ５２やサブプロセッサ５４ａ〜５４ｈは、ユーザによって行われた操作の内容をその操作信号に基づいて判断する。なお、コンピュータ５０は複数の操作デバイス８２を通信接続可能に構成されており、各操作デバイス８２から入力される操作信号に基づいて、メインプロセッサ５２やサブプロセッサ５４ａ〜５４ｈが各種処理を実行するようになっている。
【００２９】
操作デバイス８２は、ユーザがコンピュータ５０を操作するためのデバイスであって、ＵＳＢ等の有線通信手段、及びＢｌｕｅＴｏｏｔｈ（商標）やワイヤレスＬＡＮ等の無線通信手段を備える可搬型の小型コンピュータとして構成されており、操作デバイス５２において行われたユーザの操作内容を示す操作データがコンピュータ５０に有線又は無線で送信されるようになっている。
【００３０】
以下、上記ハードウェア構成を有するコンピュータ５０に、ゲームプログラム及び経路探索プログラムを実行させる例について説明する。ここで、ゲームプログラムは、例えば仮想空間でキャラクタが自在に移動するゲームに関するものである。また、経路探索プログラムは、ゲームプログラムにより起動され、該ゲームプログラムから、前記仮想空間のマップを示す情報（マップ情報）、前記マップにおける前記キャラクタの移動経路の出発地点（始点）及び目標地点（終点）を受け取る。そして、前記マップにおける始点及び終点間の最短移動経路を演算し、それをゲームプログラムに通知する。ゲームプログラムでは、こうして通知される経路に沿ってキャラクタを仮想空間内で移動させる処理を実行する。ゲームプログラムや経路探索プログラムは、例えば光ディスク７６に格納され、該光ディスクからコンピュータ５０にロードされる。そして、いずれもＭＰＵ５１によって実行される。
【００３１】
図３は、ゲームプログラムから経路探索プログラムに渡されるマップ情報が示すマップの一例を示している。同図に示すマップには、仮想的な山や建物が設けられていてキャラクタが進入できない移動不可領域４０，４１，４２、仮想的な舗装道路が存在してキャラクタが容易に移動できる低コスト領域４５、それ以外の高コスト領域４３，４４が配置されている。マップ情報は、移動不可領域４０，４１，４２の位置、低コスト領域４５の位置及びキャラクタにとっての移動のし易さ（例えば、単位距離を移動するのに必要となる時間）を示す数値（以下、「移動コスト」という。）、高コスト領域４３，４４の位置及び移動コストを特定可能な情報である。
【００３２】
経路探索プログラムは、図４に示すように、マップ情報が与えられるとマップ情報により示されるマップ全体を複数の部分領域１１〜３３に分割する。例えば、マップ情報により示されるマップが矩形であれば部分領域１１〜３３も矩形とし、それらの縦の長さが等しく、また横の長さも等しく、且つそれらの長さが予め決められた範囲に収まるようにする。ここでは、マップを縦方向に３分割、横方向に３分割して、合計９つの部分領域１１〜３３をマップ上に設定する。そして、各部分領域１１〜３３が縦横に整列配置される。その後、各部分領域１１〜３３に対して１以上の代表点を設定する。具体的には、各部分領域１１〜３３における移動可能な連続領域を検出して、各連続領域に対して１つの代表点を設定する。図４の例では、マップ中央の部分領域２２は中央に移動不可領域４１が横切っており、移動可能な領域が上下に分離し、それにより移動可能な連続領域が２つ形成されている。そこで、上側の連続領域に対しては代表点Ｒ２２ａが設定され、下側の連続領域に対しては代表点Ｒ２２ｂが設定されている。他の部分領域１１，１２，１３，２１，２３，３１，３２，３３はいずれも移動可能な連続領域を１つだけ有しており、それぞれ１つずつ代表点Ｒ１１，Ｒ１２，Ｒ１３，Ｒ２１，Ｒ２３，Ｒ３１，Ｒ３２，Ｒ３３が設定されている。これらの代表点は、例えば各連続領域の重心位置に基づいて決定される。すなわち、連続領域内の各位置の座標をその位置の移動コストで重み付けして重心位置を算出し、その重心位置が移動不可領域４０，４１，４２内でなければ、そこを代表点とする。また、移動不可領域４０，４１，４２内であれば、そのすぐ外側を代表点とする。
【００３３】
経路探索プログラムは、こうしてマップ情報が示すマップに部分領域１１〜３３を設定し、各部分領域に含まれる移動可能な連続領域に対して１つずつ代表点を設定すると、次に近接する代表点間の最短移動経路及びその距離（コスト付距離；経路上の位置の移動コストの総和）を算出する。具体的には、各部分領域について、その内側に設定されている代表点（仮始点）を取得するとともに、その部分領域の右側（存在すれば）及び下側に隣接する部分領域内に設定されている代表点（仮終点）を取得する。そして、これら仮始点及び仮終点間の最短移動経路及びその距離を算出する。これにより、図５において太い実線で示されるように、例えばマップ中央の部分領域２２の代表点Ｒ２２ａ及びＲ２２ｂについては、それらから右隣の部分領域２３の代表点Ｒ２３への最短移動経路及びその距離、下側に隣接する部分領域３２の代表点Ｒ３２への最短移動経路及びその距離が算出される。左隣の部分領域２１の代表点Ｒ２１、上側に隣接する部分領域１２の代表点Ｒ１２への最短移動経路及びその距離は、それぞれ部分領域２１及び部分領域１２に関する最短移動経路及びその距離として算出される。これにより結果的に、すべての隣接領域の組み合わせについて、各領域の代表点を結ぶ最短移動経路及びその距離が算出されることになる。このように、ある矩形の部分領域を注目領域とし、その注目領域の代表点と、該注目領域の直交するいずれかの２辺に接する部分領域の代表点と、の最短移動経路及びその距離を算出し、且つ、マップに設定されたすべての部分領域を順次注目領域とすることで、すべての必要な最短移動経路及びその距離が算出されることになる。
【００３４】
また、各最短移動経路は、隣接する２つの部分領域のみを通り、その他の部分領域は通過しないようにして設定される。これにより、ある部分領域に変更が生じたとしても、最短移動距離は、その変更のあった部分領域に設定された代表点から、及びそこに隣接する部分領域に設定された代表点に至るものだけを再計算すれば済み、他の最短移動経路はそのまま利用し続けることができる。
【００３５】
さらに、最短移動経路とは、経路上の位置の移動コストの総和が最小となる経路を意味しており、例えばダイクストラ法、Ａ＊（A-Star）アルゴリズムなど、公知の各種経路探索アルゴリズムにより、その距離とともに容易に算出することができる。また、代表点Ｒ２２ａから代表点Ｒ３２へは、他の部分領域（２３や２１など）を経由しなければキャラクタは移動できず、これら代表点間の最短移動経路は存在しないものとして扱われている。すなわち、本実施形態においては、仮始点と仮終点との間の最短移動経路としては、仮始点及び仮終点が含まれる、隣接する２つの部分領域以外の領域を通過しないものが算出されるようになっている。
【００３６】
経路探索プログラムは、こうして最短移動経路及びその距離を全ての近接する代表点の組み合わせについて算出すると、それらをハードディスク７８或いはメインメモリ６０に記憶する。
【００３７】
その後、経路探索プログラムは、ゲームプログラムからマップ上の位置である始点及び終点を受け取ると、それらの間の最短移動経路を算出する。具体的には、図６に示すように始点Ｓの位置に応じて、例えば移動コストを考慮して該始点Ｓに最も近い代表点Ｒ１１を選択し、また終点Ｇの位置に応じて、例えば移動コストを考慮して該終点Ｇに最も近い代表点Ｒ３３を選択する。なお、始点Ｓが属する部分領域１１の代表点Ｒ１１を選択してもよいし、同様に終点Ｇが属する部分領域３３の代表点Ｒ３３を選択してもよい。そして、始点Ｓから該始点Ｓに対して選択された代表点Ｒ１１への最短移動経路を、例えばダイクストラ法やＡ＊アルゴリズムなどにより算出する。同様に、終点Ｇに対して選択された代表点Ｒ３３から終点Ｇへの最短移動経路を、例えばダイクストラ法やＡ＊アルゴリズムなどにより算出する。さらに、始点Ｓ及び終点Ｇに対して選択された代表点Ｒ１１及びＲ３３の間の最短移動経路も、例えばダイクストラ法やＡ＊アルゴリズムなどにより算出する。このとき、最短移動経路は、始点Ｓに対して選択された代表点Ｒ１１から、隣接する部分領域の代表点を順に通過しながら、終点Ｇに対して選択された代表点Ｒ３３に至る経路として算出する。そして、順に通過する２つの代表点を結ぶ移動経路は、事前にハードディスク７８或いはメインメモリ６０に記憶されたものを用いる。すなわち、経路探索プログラムは、予めハードディスク７８或いはメインメモリ６０に記憶されている、全ての近接する代表点の組み合わせについて算出された最短移動経路及びその距離を参照しながら、代表点Ｒ１１から代表点Ｒ３３まで、事前に算出された最短移動経路を通って移動する経路のうち、代表点間の最短移動経路の距離の総和が最も小さくなるものを、これら代表点間の最短移動距離として選択する。ここでは、図６に示されるように、低コスト領域４５内を移動する経路が選択される。そして、こうして得られる始点Ｓから代表点Ｒ１１への最短移動経路、代表点Ｒ１１から代表点Ｒ３３への最短移動経路、代表点Ｒ３３から終点Ｇへの最短移動経路を連結して、始点Ｓから終点Ｇへの最短移動経路が算出される。そして、この経路を示す情報がゲームプログラムに渡される。上述のように、ゲームプログラムでは、この情報に従ってキャラクタを移動させるなどの処理を実行する。
【００３８】
また、経路探索プログラムでは、ゲームプログラムで用いられているマップに変更があり、この変更後のマップを示すマップ情報を受け取った場合に、ハードディスク７８或いはメインメモリ６０に既に記憶されている代表点間の最短移動経路及びその距離を更新するようにしている。例えば、図３のマップ中央に示される移動不可領域４１が、図７に示すように横方向に短い移動不可領域４１ａに変化し、それに伴ってより広い高コスト領域４３ａが現れた場合、図８に示すように変更後のマップを部分領域１１〜３３に分割して、変更前後のマップにおいて内容変更があった部分領域がどれであるかを調べる。そして、その変更があった部分領域について、再度、移動可能な連続領域を抽出するとともに、各連続領域に代表点を設定する。図７の例では、部分領域２２のみに変更があり、移動可能な連続領域が１つに減っている。この場合、部分領域２２の代表点は、Ｒ２２ａ及びＲ２２ｂの２つから、Ｒ２２の１つになる。
【００３９】
図９に示すように、経路探索プログラムでは、新しく設定された代表点Ｒ２２から、変更のあった部分領域２２の上下左右に隣接する部分領域１２、部分領域３２、部分領域２１、部分領域２３の代表点Ｒ１２、代表点Ｒ３２、代表点Ｒ２１、代表点Ｒ２３のそれぞれへの最短移動経路及びその距離を算出する。このときも、各最短移動経路は、隣接する２つの部分領域のみを通り、その他の部分領域は通過しないようにして設定される。そして、変更前の部分領域２２の代表点Ｒ２２ａ及びＲ２２ｂを端点とする最短移動経路及びその距離を、ハードディスク７８或いはメインメモリ６０から削除し、代わりに、新たに算出された代表点Ｒ２２を端点とする最短移動経路及びその距離を格納する。そして、その後は更新後の最短移動経路及びその距離の情報に基づいて、任意の始点及び終点間の最短移動経路を算出する。
【００４０】
ここで、経路探索装置として機能するコンピュータ５０の情報処理についてさらに説明する。図１０に示すように、経路探索プログラムを実行することによりコンピュータ５０では経路情報算出部９０、経路情報記憶部９１及び経路探索部９２が実現される。経路情報算出部９０は、ＭＰＵ５１を中心として構成されており、経路探索の対象となるマップを示すマップ情報を取得し、マップ上に複数の代表点を設定する。そして、近接する代表点間の最短移動経路及びその距離を演算して、それらの情報を経路情報記憶部９１に格納する。また、マップ情報に変更があった場合には、経路情報記憶部９１に記憶される最短移動経路及びその距離を更新する。上述のようにＭＰＵ５１は、サブプロセッサ５４ａ〜５４ｈを備えており、代表点間の最短移動経路を算出する際には、各サブプロセッサ５４ａ〜５４ｈに対して部分領域が割り当てられ、これにより該部分領域の代表点が関連づけられる。例えば、サブプロセッサ５４ａ〜５４ｈのそれぞれに対して、ランダムに、或いはマップの左上から順に選択される略同数の部分領域が割り当てられる。そして、各サブプロセッサ５４ａ〜５４ｈは、該プロセッサに割り当てられた部分領域の代表点から、右側及び下側に隣接する部分領域の代表点への最短移動経路及びその距離を、それぞれ並列に演算する。こうして、最短移動経路の演算を高速に行うようにしている。
【００４１】
経路情報記憶部９１は、ハードディスク７８或いはメインメモリ６０を中心として構成されており、経路情報算出部９０により算出される代表点間の最短移動経路及びその距離を記憶する。また、経路探索部９２は、ＭＰＵ５１を中心として構成されており、経路情報記憶部９１の記憶内容を参照しながら、任意の始点及び終点間の最短移動経路を算出する。
【００４２】
図１１は、経路情報算出部９０による準備処理を示している。この処理は、ゲームプログラムなどの外部プログラムからマップ情報を最初に受け取った場合に実行されるものであり、まずマップ情報を取得すると、この情報が示すマップを縦横に等間隔に分割して複数の矩形の部分領域を設定する（Ｓ１０２）。次に、それらの部分領域を各サブプロセッサ５４ａ〜５４ｈに割り当て、各プロセッサ５４ａ〜５４ｈが並列に、割り当てられた部分領域内の可動範囲（移動可能な連続領域）を抽出する（Ｓ１０３）。次に、各可動範囲に対して代表点を設定する（Ｓ１０４）。
【００４３】
全ての部分領域に対して代表点が設定されると、次に各プロセッサ５４ａ〜５４ｈが並列に、割り当てられた部分領域の代表点から、右側及び下側に隣接する部分領域の代表点に至る最短移動経路及びその距離を算出する（Ｓ１０５）。全ての部分領域に対して代表点が設定されるまで待ってから、各プロセッサ５４ａ〜５４ｈが、割り当てられた部分領域について最短移動経路及びその距離の算出を開始することで、隣接する部分領域の代表点が算出されるまで演算処理の待機を強いられるといった無駄をなくすことができ、これにより最短移動経路及びその距離の計算を効率化できる。なお、最短移動距離及びその距離を算出する際（Ｓ１０５）と、可動範囲の抽出（Ｓ１０３）及び代表点の設定（Ｓ１０４）を行う際とで、プロセッサ５４ａ〜５４ｈと部分領域との割り当ては異なってよい。その後、各プロセッサ５４ａ〜５４ｈで算出される最短移動経路及びその距離を経路情報記憶部９１に格納する（Ｓ１０６）。
【００４４】
次に、図１２は経路情報算出部９０による、経路情報記憶部９１の記憶内容を更新する処理、及び経路探索部９２による、経路情報記憶部９１の最新の記憶内容に基づく経路探索処理を示している。同図に示される処理は、例えばゲームプログラムなどの外部プログラムから始点及び終点が与えられた場合に実行される。この処理では、まず経路情報算出部９０がマップの更新があったか否かを判断する（Ｓ２０１）。例えば、外部プログラムからマップの更新の有無が与えられる場合には、与えられた情報から直ちに判断できる。また、最新のマップ情報がハードディスク７８に格納されている場合には、その更新時刻により更新の有無を判断できる。そして、マップ情報の更新があった場合には、最新のマップ情報を取得して（Ｓ２０２）、どの部分領域に変更があったかを調べる（Ｓ２０３）。そして、それら変更があった部分領域を各サブプロセッサ５４ａ〜５４ｈに割り当て、各プロセッサ５４ａ〜５４ｈが並列に、割り当てられた部分領域内の可動範囲を抽出する（Ｓ２０４）。次に、各可動範囲に対して代表点を設定する（Ｓ２０５）。全ての変更のあった部分領域に対して代表点が設定されると、次に各プロセッサ５４ａ〜５４ｈが並列に、割り当てられた部分領域の代表点から、右側及び下側に隣接する部分領域の代表点に至る最短移動経路及びその距離を算出する（Ｓ２０６）。その後、変更前の部分領域の代表点を端点とする最短移動経路及びその距離を経路情報記憶部９１から削除するとともに、各プロセッサ５４ａ〜５４ｈで新たに算出された最短移動経路及びその距離を経路情報記憶部９１に格納する（Ｓ２０７）。Ｓ２０１でマップが更新されていないと判断すると、Ｓ２０２〜Ｓ２０７の処理はスキップされる。
【００４５】
その後、ゲームプログラムなどの外部プログラムから与えられる始点及び終点の座標を取得し（Ｓ２０８）、始点から最も近い代表点を選択するとともに、その選択された代表点への最短移動経路を算出する（Ｓ２０９）。また、終点に最も近い代表点を選択するとともに、そこから終点への最短移動経路を算出する（Ｓ２１０）。さらに、Ｓ２０９及びＳ２１０で選択される代表点間の最短移動経路を算出する（Ｓ２１１）。そして、Ｓ２０９〜Ｓ２１１で算出される最短移動経路を連結して、外部プログラムから与えられる始点及び終点を結ぶ最短移動経路の情報を生成し、これを元の外部プログラムに返す（Ｓ２１２）。
【００４６】
以上説明した実施形態によると、マップ情報が示すマップに複数の代表点を設定し、サブプロセッサ５４ａ〜５４ｈにこれらの代表点を関連づけ、代表点間の最短移動経路及びその距離をサブプロセッサ５４ａ〜５４ｈにより並列処理するようにしたので、マップ情報が与えられてから短時間で代表点間の最短移動経路を演算することができる。
【図面の簡単な説明】
【００４７】
【図１】本発明の一実施形態に係る経路探索装置として機能するコンピュータのハードウェア構成を示す図である。
【図２】ＭＰＵの構成を示す図である。
【図３】マップ情報が示すマップの一例を示す図である。
【図４】部分領域及び代表点の設定を示す図である。
【図５】事前の最短移動経路の算出を示す図である。
【図６】任意の始点及び終点間の最短移動経路の算出を示す図である。
【図７】変更されたマップの一例を示す図である。
【図８】変更されたマップに対する部分領域及び代表点の設定を示す図である。
【図９】変更のある部分領域に関する最短移動経路の更新を示す図である。
【図１０】本発明の一実施形態に係る経路探索装置の機能ブロック図である。
【図１１】事前の最短移動経路の算出を示すフロー図である。
【図１２】任意の始点及び終点間の最短移動経路の算出を示すフロー図である。
【符号の説明】
【００４８】
１１，１２，１３，２１，２２，２３，３１，３２，３３ 部分領域、４０，４１，４１ａ，４２ 移動不可領域、４３，４３ａ，４４ 高コスト領域、４５ 低コスト領域、５０ コンピュータ、５１ ＭＰＵ、５２ メインプロセッサ、５４ａ〜５４ｈ サブプロセッサ、５６ バス、５８ メモリコントローラ、６０ メインメモリ、６２，８０ インタフェース、６４ 画像処理部、６６ モニタ、６８ 入出力処理部、７０ 音声処理部、７２ スピーカ、７４ 光ディスク読み取り部、７６ 光ディスク、７８ ハードディスク、８２ 操作デバイス、８８ ネットワークインタフェース、９０ 経路情報算出部、９１ 経路情報記憶部、９２ 経路探索部。
【特許請求の範囲】
【請求項１】
経路探索の対象となるマップを示すマップ情報を取得するマップ情報取得手段と、
前記マップ情報が示すマップ上に複数の代表点を設定する代表点設定手段と、
前記代表点間の経路及びその距離を演算する事前経路演算手段と、
前記事前経路演算手段により演算される前記代表点間の経路及びその距離を記憶する記憶手段と、
前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する経路探索手段と、を含み、
前記事前経路演算手段は、並列処理可能であってそれぞれ前記代表点のうち一部が関連づけられる複数のプロセッサを含み、前記各プロセッサは、該プロセッサに関連づけられる前記代表点から他の前記代表点への経路のうち少なくとも１つ及びその距離を並列に演算する、
ことを特徴とする経路探索装置。
【請求項２】
請求項１に記載の経路探索装置において、
前記代表点設定手段は、前記マップ情報が示すマップ上に複数の部分領域を設定するとともに、前記各部分領域に対して１以上の代表点を設定する、
ことを特徴とする経路探索装置。
【請求項３】
請求項２に記載の経路探索装置において、
前記事前経路演算手段に含まれる前記各プロセッサは、該プロセッサに関連づけられる前記代表点から、該代表点に係る前記部分領域に隣接する前記部分領域に対して設定される前記代表点のうち少なくとも１つへ、それら隣接する前記部分領域のみを通って至る経路及びその距離を演算する、
ことを特徴とする経路探索装置。
【請求項４】
請求項３に記載の経路探索装置において、
前記各部分領域は共通の矩形状をなし、
前記事前経路演算手段に含まれる前記各プロセッサは、該プロセッサに関連づけられる前記代表点から、該代表点に係る前記部分領域の直交するいずれかの２辺に接する前記部分領域に対して設定される前記代表点のうち少なくとも１つへ、それら前記部分領域のみを通って至る経路及びその距離を演算する、
ことを特徴とする経路探索装置。
【請求項５】
請求項２乃至４のいずれかに記載の経路探索装置において、
前記代表点設定手段は、すでに取得された前記マップ情報が示すマップとは異なるマップを示す前記マップ情報が前記マップ情報取得手段により取得される場合に、前記複数の部分領域のうちどの前記部分領域に変更があるかを判断するとともに、変更のある前記部分領域に対して１以上の前記代表点を再設定し、
前記事前経路演算手段は、再設定される前記代表点を端点とする経路及びその距離を再演算する、
ことを特徴とする経路探索装置。
【請求項６】
請求項１乃至５のいずれかに記載の経路探索装置において、
前記経路探索手段は、
前記始点の位置に応じて前記代表点のうち１つを選択するとともに、前記始点から該選択される代表点への経路を決定する第１経路決定手段と、
前記終点の位置に応じて前記代表点のうち１つを選択するとともに、該選択される代表点から前記終点への経路を決定する第２経路決定手段と、
前記記憶手段に記憶される経路及びその距離に基づいて、前記選択される代表点間の経路を決定する第３経路決定手段と、を含む、
ことを特徴とする経路探索装置。
【請求項７】
経路探索の対象となるマップを示すマップ情報を取得するマップ情報取得手段と、
前記マップ情報が示すマップ上に複数の部分領域を設定するとともに、前記各部分領域に対して１以上の代表点を設定する代表点設定手段と、
前記各代表点から、該代表点に係る前記部分領域に隣接する前記部分領域に対して設定される前記代表点のうち少なくとも１つへ、それら隣接する前記部分領域のみを通って至る経路、及びその距離を演算する事前経路演算手段と、
前記事前経路演算手段により演算される前記代表点間の経路及びその距離を記憶する記憶手段と、
前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する経路探索手段と、を含み、
前記代表点設定手段は、すでに取得された前記マップ情報が示すマップとは異なるマップを示す前記マップ情報が前記マップ情報取得手段により取得される場合に、前記複数の部分領域のうちどの前記部分領域に変更があるかを判断するとともに、変更のある前記部分領域に対して１以上の前記代表点を再設定し、
前記事前経路演算手段は、再設定される前記代表点を端点とする経路及びその距離を再演算する、
ことを特徴とする経路探索装置。
【請求項８】
請求項１乃至７のいずれかに記載の経路探索装置において、
前記距離は、該距離に係る経路上に設定されるコストに基づいて演算される、
ことを特徴とする経路探索装置。
【請求項９】
経路探索の対象となるマップを示すマップ情報を取得するマップ情報取得ステップと、
前記マップ情報が示すマップ上に複数の代表点を設定する代表点設定ステップと、
前記代表点間の経路及びその距離を演算する事前経路演算ステップと、
前記事前経路演算ステップで演算される前記代表点間の経路及びその距離を記憶手段に格納する格納ステップと、
前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する経路探索ステップと、を含み、
前記事前経路演算ステップは、並列処理可能であってそれぞれ前記代表点のうち一部が関連づけられる複数のプロセッサのそれぞれにより、該プロセッサに関連づけられる前記代表点から他の前記代表点への経路のうち少なくとも１つ及びその距離を並列に演算する、
ことを特徴とする経路探索方法。
【請求項１０】
経路探索の対象となるマップを示すマップ情報を取得するマップ情報取得手段、
前記マップ情報が示すマップ上に複数の代表点を設定する代表点設定手段、
前記代表点間の経路及びその距離を演算する事前経路演算手段、
前記事前経路演算手段により演算される前記代表点間の経路及びその距離を記憶する記憶手段、及び
前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する経路探索手段
として、並列処理可能な複数のプロセッサを備えるコンピュータを機能させるためのプログラムであって、
前記各プロセッサにはそれぞれ前記代表点のうち一部が割り当てられ、前記事前経路演算手段は、前記各プロセッサにより、該プロセッサに関連づけられる前記代表点から他の前記代表点への経路のうち少なくとも１つ及びその距離を並列に演算する、
ことを特徴とするプログラム。
【請求項１１】
経路探索の対象となるマップを示すマップ情報を取得するステップと、
前記マップ情報が示すマップ上に複数の部分領域を設定するとともに、前記各部分領域に対して１以上の代表点を設定するステップと、
前記各代表点から、該代表点に係る前記部分領域に隣接する前記部分領域に対して設定される前記代表点のうち少なくとも１つへ、それら隣接する前記部分領域のみを通って至る経路、及びその距離を演算するステップと、
演算される前記代表点間の経路及びその距離を記憶手段に格納するステップと、
前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索するステップと、
すでに取得された前記マップ情報が示すマップとは異なるマップを示す前記マップ情報が新たに取得される場合に、前記複数の部分領域のうちどの前記部分領域に変更があるかを判断するとともに、変更のある前記部分領域に対して１以上の前記代表点を再設定するステップと、
再設定される前記代表点を端点とする経路及びその距離を再演算するステップと、
を含むことを特徴とする経路探索方法。
【請求項１２】
経路探索の対象となるマップを示すマップ情報を取得する手段、
前記マップ情報が示すマップ上に複数の部分領域を設定するとともに、前記各部分領域に対して１以上の代表点を設定する手段、
前記各代表点から、該代表点に係る前記部分領域に隣接する前記部分領域に対して設定される前記代表点のうち少なくとも１つへ、それら隣接する前記部分領域のみを通って至る経路、及びその距離を演算する手段、
演算される前記代表点間の経路及びその距離を記憶手段に格納する手段、
前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する手段、
すでに取得された前記マップ情報が示すマップとは異なるマップを示す前記マップ情報が新たに取得される場合に、前記複数の部分領域のうちどの前記部分領域に変更があるかを判断するとともに、変更のある前記部分領域に対して１以上の前記代表点を再設定する手段、及び
再設定される前記代表点を端点とする経路及びその距離を再演算する手段
としてコンピュータを機能させるためのプログラム。
【請求項１】
経路探索の対象となるマップを示すマップ情報を取得するマップ情報取得手段と、
前記マップ情報が示すマップ上に複数の代表点を設定する代表点設定手段と、
前記代表点間の経路及びその距離を演算する事前経路演算手段と、
前記事前経路演算手段により演算される前記代表点間の経路及びその距離を記憶する記憶手段と、
前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する経路探索手段と、を含み、
前記事前経路演算手段は、並列処理可能であってそれぞれ前記代表点のうち一部が関連づけられる複数のプロセッサを含み、前記各プロセッサは、該プロセッサに関連づけられる前記代表点から他の前記代表点への経路のうち少なくとも１つ及びその距離を並列に演算する、
ことを特徴とする経路探索装置。
【請求項２】
請求項１に記載の経路探索装置において、
前記代表点設定手段は、前記マップ情報が示すマップ上に複数の部分領域を設定するとともに、前記各部分領域に対して１以上の代表点を設定する、
ことを特徴とする経路探索装置。
【請求項３】
請求項２に記載の経路探索装置において、
前記事前経路演算手段に含まれる前記各プロセッサは、該プロセッサに関連づけられる前記代表点から、該代表点に係る前記部分領域に隣接する前記部分領域に対して設定される前記代表点のうち少なくとも１つへ、それら隣接する前記部分領域のみを通って至る経路及びその距離を演算する、
ことを特徴とする経路探索装置。
【請求項４】
請求項３に記載の経路探索装置において、
前記各部分領域は共通の矩形状をなし、
前記事前経路演算手段に含まれる前記各プロセッサは、該プロセッサに関連づけられる前記代表点から、該代表点に係る前記部分領域の直交するいずれかの２辺に接する前記部分領域に対して設定される前記代表点のうち少なくとも１つへ、それら前記部分領域のみを通って至る経路及びその距離を演算する、
ことを特徴とする経路探索装置。
【請求項５】
請求項２乃至４のいずれかに記載の経路探索装置において、
前記代表点設定手段は、すでに取得された前記マップ情報が示すマップとは異なるマップを示す前記マップ情報が前記マップ情報取得手段により取得される場合に、前記複数の部分領域のうちどの前記部分領域に変更があるかを判断するとともに、変更のある前記部分領域に対して１以上の前記代表点を再設定し、
前記事前経路演算手段は、再設定される前記代表点を端点とする経路及びその距離を再演算する、
ことを特徴とする経路探索装置。
【請求項６】
請求項１乃至５のいずれかに記載の経路探索装置において、
前記経路探索手段は、
前記始点の位置に応じて前記代表点のうち１つを選択するとともに、前記始点から該選択される代表点への経路を決定する第１経路決定手段と、
前記終点の位置に応じて前記代表点のうち１つを選択するとともに、該選択される代表点から前記終点への経路を決定する第２経路決定手段と、
前記記憶手段に記憶される経路及びその距離に基づいて、前記選択される代表点間の経路を決定する第３経路決定手段と、を含む、
ことを特徴とする経路探索装置。
【請求項７】
経路探索の対象となるマップを示すマップ情報を取得するマップ情報取得手段と、
前記マップ情報が示すマップ上に複数の部分領域を設定するとともに、前記各部分領域に対して１以上の代表点を設定する代表点設定手段と、
前記各代表点から、該代表点に係る前記部分領域に隣接する前記部分領域に対して設定される前記代表点のうち少なくとも１つへ、それら隣接する前記部分領域のみを通って至る経路、及びその距離を演算する事前経路演算手段と、
前記事前経路演算手段により演算される前記代表点間の経路及びその距離を記憶する記憶手段と、
前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する経路探索手段と、を含み、
前記代表点設定手段は、すでに取得された前記マップ情報が示すマップとは異なるマップを示す前記マップ情報が前記マップ情報取得手段により取得される場合に、前記複数の部分領域のうちどの前記部分領域に変更があるかを判断するとともに、変更のある前記部分領域に対して１以上の前記代表点を再設定し、
前記事前経路演算手段は、再設定される前記代表点を端点とする経路及びその距離を再演算する、
ことを特徴とする経路探索装置。
【請求項８】
請求項１乃至７のいずれかに記載の経路探索装置において、
前記距離は、該距離に係る経路上に設定されるコストに基づいて演算される、
ことを特徴とする経路探索装置。
【請求項９】
経路探索の対象となるマップを示すマップ情報を取得するマップ情報取得ステップと、
前記マップ情報が示すマップ上に複数の代表点を設定する代表点設定ステップと、
前記代表点間の経路及びその距離を演算する事前経路演算ステップと、
前記事前経路演算ステップで演算される前記代表点間の経路及びその距離を記憶手段に格納する格納ステップと、
前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する経路探索ステップと、を含み、
前記事前経路演算ステップは、並列処理可能であってそれぞれ前記代表点のうち一部が関連づけられる複数のプロセッサのそれぞれにより、該プロセッサに関連づけられる前記代表点から他の前記代表点への経路のうち少なくとも１つ及びその距離を並列に演算する、
ことを特徴とする経路探索方法。
【請求項１０】
経路探索の対象となるマップを示すマップ情報を取得するマップ情報取得手段、
前記マップ情報が示すマップ上に複数の代表点を設定する代表点設定手段、
前記代表点間の経路及びその距離を演算する事前経路演算手段、
前記事前経路演算手段により演算される前記代表点間の経路及びその距離を記憶する記憶手段、及び
前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する経路探索手段
として、並列処理可能な複数のプロセッサを備えるコンピュータを機能させるためのプログラムであって、
前記各プロセッサにはそれぞれ前記代表点のうち一部が割り当てられ、前記事前経路演算手段は、前記各プロセッサにより、該プロセッサに関連づけられる前記代表点から他の前記代表点への経路のうち少なくとも１つ及びその距離を並列に演算する、
ことを特徴とするプログラム。
【請求項１１】
経路探索の対象となるマップを示すマップ情報を取得するステップと、
前記マップ情報が示すマップ上に複数の部分領域を設定するとともに、前記各部分領域に対して１以上の代表点を設定するステップと、
前記各代表点から、該代表点に係る前記部分領域に隣接する前記部分領域に対して設定される前記代表点のうち少なくとも１つへ、それら隣接する前記部分領域のみを通って至る経路、及びその距離を演算するステップと、
演算される前記代表点間の経路及びその距離を記憶手段に格納するステップと、
前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索するステップと、
すでに取得された前記マップ情報が示すマップとは異なるマップを示す前記マップ情報が新たに取得される場合に、前記複数の部分領域のうちどの前記部分領域に変更があるかを判断するとともに、変更のある前記部分領域に対して１以上の前記代表点を再設定するステップと、
再設定される前記代表点を端点とする経路及びその距離を再演算するステップと、
を含むことを特徴とする経路探索方法。
【請求項１２】
経路探索の対象となるマップを示すマップ情報を取得する手段、
前記マップ情報が示すマップ上に複数の部分領域を設定するとともに、前記各部分領域に対して１以上の代表点を設定する手段、
前記各代表点から、該代表点に係る前記部分領域に隣接する前記部分領域に対して設定される前記代表点のうち少なくとも１つへ、それら隣接する前記部分領域のみを通って至る経路、及びその距離を演算する手段、
演算される前記代表点間の経路及びその距離を記憶手段に格納する手段、
前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する手段、
すでに取得された前記マップ情報が示すマップとは異なるマップを示す前記マップ情報が新たに取得される場合に、前記複数の部分領域のうちどの前記部分領域に変更があるかを判断するとともに、変更のある前記部分領域に対して１以上の前記代表点を再設定する手段、及び
再設定される前記代表点を端点とする経路及びその距離を再演算する手段
としてコンピュータを機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２００９−２８１９４２（Ｐ２００９−２８１９４２Ａ）
【公開日】平成２１年１２月３日（２００９．１２．３）
【国際特許分類】
【出願番号】特願２００８−１３５９５０（Ｐ２００８−１３５９５０）
【出願日】平成２０年５月２３日（２００８．５．２３）
【出願人】（３９５０１５３１９）株式会社ソニー・コンピュータエンタテインメント (871)
【Ｆターム（参考）】
【公開日】平成２１年１２月３日（２００９．１２．３）
【国際特許分類】
【出願日】平成２０年５月２３日（２００８．５．２３）
【出願人】（３９５０１５３１９）株式会社ソニー・コンピュータエンタテインメント (871)
【Ｆターム（参考）】
[ Back to top ]