経路探索装置、経路探索方法及びプログラム
【課題】任意のマップに対して経路探索結果を短時間に得ること。
【解決手段】経路探索の対象となるマップを示すマップ情報を取得するステップ(S101)と、前記マップ情報が示すマップ上に複数の代表点を設定するステップ(S102〜S104)と、前記代表点間の経路及びその距離を演算するステップ(S105)を含み、代表点間の経路及び距離を演算するステップ(S105)では、並列処理可能であってそれぞれ前記代表点のうち一部が関連づけられる複数のプロセッサのそれぞれにより、該プロセッサに関連づけられる前記代表点から他の前記代表点への経路のうち少なくとも1つ及びその距離を並列に演算する。
【解決手段】経路探索の対象となるマップを示すマップ情報を取得するステップ(S101)と、前記マップ情報が示すマップ上に複数の代表点を設定するステップ(S102〜S104)と、前記代表点間の経路及びその距離を演算するステップ(S105)を含み、代表点間の経路及び距離を演算するステップ(S105)では、並列処理可能であってそれぞれ前記代表点のうち一部が関連づけられる複数のプロセッサのそれぞれにより、該プロセッサに関連づけられる前記代表点から他の前記代表点への経路のうち少なくとも1つ及びその距離を並列に演算する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は経路探索装置、経路探索方法及びプログラムに関する。
【背景技術】
【0002】
経路探索アルゴリズムは、列車路線探索やカーナビゲーションなど、多くの応用製品で用いられている基本的なコンピュータソフトウェアアルゴリズムの1つである。経路探索アルゴリズムは一般に計算量が膨大になることから、探索処理の一部を事前に実行するとともに、その結果を記憶手段に記憶しておく場合がある(下記特許文献1参照)。こうすれば、記憶手段に記憶された情報を用いて、経路探索結果を短時間に得ることができるようになる。
【特許文献1】特開平10−9884号公報
【発明の開示】
【発明が解決しようとする課題】
【0003】
しかしながら、ゲームに用いられる仮想空間のマップなど、内容が動的に変化するマップに対しては、上記のように探索処理の一部を事前に実行しておくのは困難であり、上記従来技術は、実在の道路地図や列車路線図など、内容が固定されたマップへの適用に限られるという問題があった。
【0004】
本発明は上記課題に鑑みてなされたものであって、その目的は、任意のマップに対して経路探索結果を短時間に得ることができる経路探索装置、経路探索方法及びプログラムを提供することにある。
【課題を解決するための手段】
【0005】
上記課題を解決するために、本発明に係る経路探索装置は、経路探索の対象となるマップを示すマップ情報を取得するマップ情報取得手段と、前記マップ情報が示すマップ上に複数の代表点を設定する代表点設定手段と、前記代表点間の経路及びその距離を演算する事前経路演算手段と、前記事前経路演算手段により演算される前記代表点間の経路及びその距離を記憶する記憶手段と、前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する経路探索手段と、を含み、前記事前経路演算手段は、並列処理可能であってそれぞれ前記代表点のうち一部が関連づけられる複数のプロセッサを含み、前記各プロセッサは、該プロセッサに関連づけられる前記代表点から他の前記代表点への経路のうち少なくとも1つ及びその距離を並列に演算する、ことを特徴とする。
【0006】
また、本発明に係る経路探索方法は、経路探索の対象となるマップを示すマップ情報を取得するマップ情報取得ステップと、前記マップ情報が示すマップ上に複数の代表点を設定する代表点設定ステップと、前記代表点間の経路及びその距離を演算する事前経路演算ステップと、前記事前経路演算手段により演算される前記代表点間の経路及びその距離を記憶手段に格納する格納ステップと、前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する経路探索ステップと、を含み、前記事前経路演算ステップは、並列処理可能であってそれぞれ前記代表点のうち一部が関連づけられる複数のプロセッサのそれぞれにより、該プロセッサに関連づけられる前記代表点から他の前記代表点への経路のうち少なくとも1つ及びその距離を並列に演算する、ことを特徴とする。
【0007】
また、本発明に係るプログラムは、経路探索の対象となるマップを示すマップ情報を取得するマップ情報取得手段、前記マップ情報が示すマップ上に複数の代表点を設定する代表点設定手段、前記代表点間の経路及びその距離を演算する事前経路演算手段、前記事前経路演算手段により演算される前記代表点間の経路及びその距離を記憶する記憶手段、及び前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する経路探索手段として、並列処理可能な複数のプロセッサを備えるコンピュータを機能させるためのプログラムであって、前記各プロセッサにはそれぞれ前記代表点のうち一部が割り当てられ、前記事前経路演算手段は、前記各プロセッサにより、該プロセッサに関連づけられる前記代表点から他の前記代表点への経路のうち少なくとも1つ及びその距離を並列に演算する、ことを特徴とする。なお、プログラムは、CD−ROM、DVD−ROMなど、コンピュータ読取可能な各種の情報記憶媒体に格納されてよい。
【0008】
また、前記代表点設定手段は、前記マップ情報が示すマップ上に複数の部分領域を設定するとともに、前記各部分領域に対して1以上の代表点を設定してよい。このとき、前記事前経路演算手段に含まれる前記各プロセッサは、該プロセッサに関連づけられる前記代表点から、該代表点に係る前記部分領域に隣接する前記部分領域に対して設定される前記代表点のうち少なくとも1つへ、それら隣接する前記部分領域のみを通って至る経路及びその距離を演算してよい。また、前記各部分領域は共通の矩形状をなしてよい。このとき、前記事前経路演算手段に含まれる前記各プロセッサは、該プロセッサに関連づけられる前記代表点から、該代表点に係る前記部分領域の直交するいずれかの2辺に接する前記部分領域に対して設定される前記代表点のうち少なくとも1つへ、それら前記部分領域のみを通って至る経路及びその距離を演算するようにしてよい。
【0009】
また、前記代表点設定手段は、すでに取得された前記マップ情報が示すマップとは異なるマップを示す前記マップ情報が前記マップ情報取得手段により取得される場合に、前記複数の部分領域のうちどの前記部分領域に変更があるかを判断するとともに、変更のある前記部分領域に対して1以上の前記代表点を再設定してよい。この場合、前記事前経路演算手段は、再設定される前記代表点を端点とする経路及びその距離を再演算してよい。
【0010】
また、前記経路探索手段は、前記始点の位置に応じて前記代表点のうち1つを選択するとともに、前記始点から該選択される代表点への経路を決定する第1経路決定手段と、前記終点の位置に応じて前記代表点のうち1つを選択するとともに、該選択される代表点から前記終点への経路を決定する第2経路決定手段と、前記記憶手段に記憶される経路及びその距離に基づいて、前記選択される代表点間の経路を決定する第3経路決定手段と、を含んでよい。
【0011】
また、本発明に係る経路探索装置は、経路探索の対象となるマップを示すマップ情報を取得するマップ情報取得手段と、前記マップ情報が示すマップ上に複数の部分領域を設定するとともに、前記各部分領域に対して1以上の代表点を設定する代表点設定手段と、前記各代表点から、該代表点に係る前記部分領域に隣接する前記部分領域に対して設定される前記代表点のうち少なくとも1つへ、それら隣接する前記部分領域のみを通って至る経路、及びその距離を演算する事前経路演算手段と、前記事前経路演算手段により演算される前記代表点間の経路及びその距離を記憶する記憶手段と、前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する経路探索手段と、を含み、前記代表点設定手段は、すでに取得された前記マップ情報が示すマップとは異なるマップを示す前記マップ情報が前記マップ情報取得手段により取得される場合に、前記複数の部分領域のうちどの前記部分領域に変更があるかを判断するとともに、変更のある前記部分領域に対して1以上の前記代表点を再設定し、前記事前経路演算手段は、再設定される前記代表点を端点とする経路及びその距離を再演算する、ことを特徴とする。
【0012】
また、本発明に係る経路探索方法は、経路探索の対象となるマップを示すマップ情報を取得するステップと、前記マップ情報が示すマップ上に複数の部分領域を設定するとともに、前記各部分領域に対して1以上の代表点を設定するステップと、前記各代表点から、該代表点に係る前記部分領域に隣接する前記部分領域に対して設定される前記代表点のうち少なくとも1つへ、それら隣接する前記部分領域のみを通って至る経路、及びその距離を演算するステップと、演算される前記代表点間の経路及びその距離を記憶手段に格納するステップと、前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索するステップと、すでに取得された前記マップ情報が示すマップとは異なるマップを示す前記マップ情報が新たに取得される場合に、前記複数の部分領域のうちどの前記部分領域に変更があるかを判断するとともに、変更のある前記部分領域に対して1以上の前記代表点を再設定するステップと、再設定される前記代表点を端点とする経路及びその距離を再演算するステップと、を含むことを特徴とする。
【0013】
また、本発明に係るプログラムは、経路探索の対象となるマップを示すマップ情報を取得する手段、前記マップ情報が示すマップ上に複数の部分領域を設定するとともに、前記各部分領域に対して1以上の代表点を設定する手段、前記各代表点から、該代表点に係る前記部分領域に隣接する前記部分領域に対して設定される前記代表点のうち少なくとも1つへ、それら隣接する前記部分領域のみを通って至る経路、及びその距離を演算する手段、演算される前記代表点間の経路及びその距離を記憶手段に格納する手段、前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する手段、すでに取得された前記マップ情報が示すマップとは異なるマップを示す前記マップ情報が新たに取得される場合に、前記複数の部分領域のうちどの前記部分領域に変更があるかを判断するとともに、変更のある前記部分領域に対して1以上の前記代表点を再設定する手段、及び再設定される前記代表点を端点とする経路及びその距離を再演算する手段としてコンピュータを機能させるためのプログラムである。このプログラムも、CD−ROM、DVD−ROMなど、コンピュータ読取可能な各種の情報記憶媒体に格納されてよい。
【0014】
また、前記距離は、該距離に係る経路上に設定されるコストに基づいて演算されてよい。
【発明を実施するための最良の形態】
【0015】
以下、本発明の実施形態について図面に基づき詳細に説明する。
【0016】
図1は、本実施形態に係る経路探索装置として用いられるコンピュータのハードウェア構成を示す図である。同図に示すように、コンピュータ50は、MPU(Micro Processing Unit)51と、メインメモリ60と、画像処理部64と、モニタ66と、入出力処理部68と、音声処理部70と、スピーカ72と、光ディスク読み取り部74と、光ディスク76と、ハードディスク78と、インタフェース(I/F)80と、操作デバイス82と、ネットワークインタフェース88と、を含んで構成されるコンピュータシステムである。また、図2は、MPU51の構成を示す図である。同図に示すように、MPU51は、メインプロセッサ52と、サブプロセッサ54a,54b,54c,54d,54e,54f,54g,54hと、バス56と、メモリコントローラ58と、インタフェース(I/F)62と、を含んで構成される。すなわち、MPU51は、それぞれ並列して情報処理を実行することができるメインプロセッサ52及びサブプロセッサ54a〜54hを備える、マルチコアプロセッサである。
【0017】
メインプロセッサ52は、図示しないROM(Read Only Memory)に記憶されるオペレーティングシステム、例えばDVD(Digital Versatile Disk)−ROM等の光ディスク36から読み出されるプログラム及びデータや、通信ネットワークを介して供給されるプログラム及びデータ等に基づいて、各種情報処理を行ったり、サブプロセッサ54a〜54hに対する制御を行ったりする。
【0018】
サブプロセッサ54a〜54hは、メインプロセッサ52からの指示に従って、各種情報処理を行ったり、コンピュータ50の各部を、例えばDVD−ROM等の光ディスク36から読み出されるプログラム及びデータや、通信ネットワークを介して供給されるプログラム及びデータ等に基づいて制御したりする。
【0019】
バス56は、アドレス及びデータをコンピュータ50の各部でやり取りするためのものである。メインプロセッサ52、サブプロセッサ54a〜54h、メモリコントローラ58、インタフェース62は、バス56を介して相互にデータ授受可能に接続される。
【0020】
メモリコントローラ58は、メインプロセッサ52及びサブプロセッサ54a〜54hからの指示に従って、メインメモリ60へのアクセスを行う。メインメモリ60には、光ディスク76やハードディスク78から読み出されたプログラム及びデータや、通信ネットワークを介して供給されたプログラム及びデータが必要に応じて書き込まれる。メインメモリ60はメインプロセッサ52やサブプロセッサ54a〜54hの作業用としても用いられる。
【0021】
インタフェース62には画像処理部64及び入出力処理部68が接続される。メインプロセッサ52及びサブプロセッサ54a〜54hと、画像処理部64又は入出力処理部68と、の間のデータ授受はインタフェース62を介して行われる。
【0022】
画像処理部64は、GPU(Graphical Processing Unit)とフレームバッファとを含んで構成される。GPUは、メインプロセッサ52やサブプロセッサ54a〜54hから供給される画像データに基づいてフレームバッファに各種画面を描画する。フレームバッファに形成された画面、すなわちMPU51の実行結果を示す画面は、所定のタイミングでビデオ信号に変換されてモニタ66に出力される。なお、モニタ66には例えば家庭用テレビ受像機が用いられる。
【0023】
入出力処理部68には、音声処理部70、光ディスク読み取り部74、ハードディスク78、インタフェース80、ネットワークインタフェース88が接続される。入出力処理部68は、メインプロセッサ52及びサブプロセッサ54a〜54hと、音声処理部70、光ディスク読み取り部74、ハードディスク78、インタフェース80、ネットワークインタフェース88と、の間のデータ授受を制御する。
【0024】
音声処理部70は、SPU(Sound Processing Unit)とサウンドバッファとを含んで構成される。サウンドバッファには、光ディスク76やハードディスク78から読み出されたゲーム音楽、ゲーム効果音やメッセージなどの各種音声データが記憶される。SPUは、これらの各種音声データを再生してスピーカ72から出力させる。なお、スピーカ72には例えば家庭用テレビ受像機の内蔵スピーカが用いられる。
【0025】
光ディスク読み取り部74は、メインプロセッサ52及びサブプロセッサ54a〜54hからの指示に従って、光ディスク76に記憶されたプログラムやデータを読み取る。なお、コンピュータ50は、光ディスク76以外の他のコンピュータ読取可能な情報記憶媒体に記憶されたプログラムやデータを読取可能に構成してもよい。
【0026】
光ディスク76は例えばDVD−ROM等の一般的な光ディスク(コンピュータ読取可能な情報記憶媒体)である。また、ハードディスク78は一般的なハードディスク装置である。光ディスク76やハードディスク78には各種プログラムやデータがコンピュータ読取可能に記憶される。
【0027】
インタフェース(I/F)80は、操作デバイス82等の各種周辺機器を接続するためのインタフェースである。このようなインタフェースとしては、例えばUSB(Universal Serial Bus)インタフェースが用いられる。
【0028】
操作デバイス82は汎用操作入力手段であり、ユーザが各種操作(例えばゲーム操作)を入力するために用いられる。入出力処理部68は、所定時間(例えば1/60秒)ごとに操作デバイス82から、その各部の状態を無線又は有線通信により取得し、その結果を表す操作信号をメインプロセッサ52やサブプロセッサ54a〜54hに供給する。メインプロセッサ52やサブプロセッサ54a〜54hは、ユーザによって行われた操作の内容をその操作信号に基づいて判断する。なお、コンピュータ50は複数の操作デバイス82を通信接続可能に構成されており、各操作デバイス82から入力される操作信号に基づいて、メインプロセッサ52やサブプロセッサ54a〜54hが各種処理を実行するようになっている。
【0029】
操作デバイス82は、ユーザがコンピュータ50を操作するためのデバイスであって、USB等の有線通信手段、及びBlueTooth(商標)やワイヤレスLAN等の無線通信手段を備える可搬型の小型コンピュータとして構成されており、操作デバイス52において行われたユーザの操作内容を示す操作データがコンピュータ50に有線又は無線で送信されるようになっている。
【0030】
以下、上記ハードウェア構成を有するコンピュータ50に、ゲームプログラム及び経路探索プログラムを実行させる例について説明する。ここで、ゲームプログラムは、例えば仮想空間でキャラクタが自在に移動するゲームに関するものである。また、経路探索プログラムは、ゲームプログラムにより起動され、該ゲームプログラムから、前記仮想空間のマップを示す情報(マップ情報)、前記マップにおける前記キャラクタの移動経路の出発地点(始点)及び目標地点(終点)を受け取る。そして、前記マップにおける始点及び終点間の最短移動経路を演算し、それをゲームプログラムに通知する。ゲームプログラムでは、こうして通知される経路に沿ってキャラクタを仮想空間内で移動させる処理を実行する。ゲームプログラムや経路探索プログラムは、例えば光ディスク76に格納され、該光ディスクからコンピュータ50にロードされる。そして、いずれもMPU51によって実行される。
【0031】
図3は、ゲームプログラムから経路探索プログラムに渡されるマップ情報が示すマップの一例を示している。同図に示すマップには、仮想的な山や建物が設けられていてキャラクタが進入できない移動不可領域40,41,42、仮想的な舗装道路が存在してキャラクタが容易に移動できる低コスト領域45、それ以外の高コスト領域43,44が配置されている。マップ情報は、移動不可領域40,41,42の位置、低コスト領域45の位置及びキャラクタにとっての移動のし易さ(例えば、単位距離を移動するのに必要となる時間)を示す数値(以下、「移動コスト」という。)、高コスト領域43,44の位置及び移動コストを特定可能な情報である。
【0032】
経路探索プログラムは、図4に示すように、マップ情報が与えられるとマップ情報により示されるマップ全体を複数の部分領域11〜33に分割する。例えば、マップ情報により示されるマップが矩形であれば部分領域11〜33も矩形とし、それらの縦の長さが等しく、また横の長さも等しく、且つそれらの長さが予め決められた範囲に収まるようにする。ここでは、マップを縦方向に3分割、横方向に3分割して、合計9つの部分領域11〜33をマップ上に設定する。そして、各部分領域11〜33が縦横に整列配置される。その後、各部分領域11〜33に対して1以上の代表点を設定する。具体的には、各部分領域11〜33における移動可能な連続領域を検出して、各連続領域に対して1つの代表点を設定する。図4の例では、マップ中央の部分領域22は中央に移動不可領域41が横切っており、移動可能な領域が上下に分離し、それにより移動可能な連続領域が2つ形成されている。そこで、上側の連続領域に対しては代表点R22aが設定され、下側の連続領域に対しては代表点R22bが設定されている。他の部分領域11,12,13,21,23,31,32,33はいずれも移動可能な連続領域を1つだけ有しており、それぞれ1つずつ代表点R11,R12,R13,R21,R23,R31,R32,R33が設定されている。これらの代表点は、例えば各連続領域の重心位置に基づいて決定される。すなわち、連続領域内の各位置の座標をその位置の移動コストで重み付けして重心位置を算出し、その重心位置が移動不可領域40,41,42内でなければ、そこを代表点とする。また、移動不可領域40,41,42内であれば、そのすぐ外側を代表点とする。
【0033】
経路探索プログラムは、こうしてマップ情報が示すマップに部分領域11〜33を設定し、各部分領域に含まれる移動可能な連続領域に対して1つずつ代表点を設定すると、次に近接する代表点間の最短移動経路及びその距離(コスト付距離;経路上の位置の移動コストの総和)を算出する。具体的には、各部分領域について、その内側に設定されている代表点(仮始点)を取得するとともに、その部分領域の右側(存在すれば)及び下側に隣接する部分領域内に設定されている代表点(仮終点)を取得する。そして、これら仮始点及び仮終点間の最短移動経路及びその距離を算出する。これにより、図5において太い実線で示されるように、例えばマップ中央の部分領域22の代表点R22a及びR22bについては、それらから右隣の部分領域23の代表点R23への最短移動経路及びその距離、下側に隣接する部分領域32の代表点R32への最短移動経路及びその距離が算出される。左隣の部分領域21の代表点R21、上側に隣接する部分領域12の代表点R12への最短移動経路及びその距離は、それぞれ部分領域21及び部分領域12に関する最短移動経路及びその距離として算出される。これにより結果的に、すべての隣接領域の組み合わせについて、各領域の代表点を結ぶ最短移動経路及びその距離が算出されることになる。このように、ある矩形の部分領域を注目領域とし、その注目領域の代表点と、該注目領域の直交するいずれかの2辺に接する部分領域の代表点と、の最短移動経路及びその距離を算出し、且つ、マップに設定されたすべての部分領域を順次注目領域とすることで、すべての必要な最短移動経路及びその距離が算出されることになる。
【0034】
また、各最短移動経路は、隣接する2つの部分領域のみを通り、その他の部分領域は通過しないようにして設定される。これにより、ある部分領域に変更が生じたとしても、最短移動距離は、その変更のあった部分領域に設定された代表点から、及びそこに隣接する部分領域に設定された代表点に至るものだけを再計算すれば済み、他の最短移動経路はそのまま利用し続けることができる。
【0035】
さらに、最短移動経路とは、経路上の位置の移動コストの総和が最小となる経路を意味しており、例えばダイクストラ法、A*(A-Star)アルゴリズムなど、公知の各種経路探索アルゴリズムにより、その距離とともに容易に算出することができる。また、代表点R22aから代表点R32へは、他の部分領域(23や21など)を経由しなければキャラクタは移動できず、これら代表点間の最短移動経路は存在しないものとして扱われている。すなわち、本実施形態においては、仮始点と仮終点との間の最短移動経路としては、仮始点及び仮終点が含まれる、隣接する2つの部分領域以外の領域を通過しないものが算出されるようになっている。
【0036】
経路探索プログラムは、こうして最短移動経路及びその距離を全ての近接する代表点の組み合わせについて算出すると、それらをハードディスク78或いはメインメモリ60に記憶する。
【0037】
その後、経路探索プログラムは、ゲームプログラムからマップ上の位置である始点及び終点を受け取ると、それらの間の最短移動経路を算出する。具体的には、図6に示すように始点Sの位置に応じて、例えば移動コストを考慮して該始点Sに最も近い代表点R11を選択し、また終点Gの位置に応じて、例えば移動コストを考慮して該終点Gに最も近い代表点R33を選択する。なお、始点Sが属する部分領域11の代表点R11を選択してもよいし、同様に終点Gが属する部分領域33の代表点R33を選択してもよい。そして、始点Sから該始点Sに対して選択された代表点R11への最短移動経路を、例えばダイクストラ法やA*アルゴリズムなどにより算出する。同様に、終点Gに対して選択された代表点R33から終点Gへの最短移動経路を、例えばダイクストラ法やA*アルゴリズムなどにより算出する。さらに、始点S及び終点Gに対して選択された代表点R11及びR33の間の最短移動経路も、例えばダイクストラ法やA*アルゴリズムなどにより算出する。このとき、最短移動経路は、始点Sに対して選択された代表点R11から、隣接する部分領域の代表点を順に通過しながら、終点Gに対して選択された代表点R33に至る経路として算出する。そして、順に通過する2つの代表点を結ぶ移動経路は、事前にハードディスク78或いはメインメモリ60に記憶されたものを用いる。すなわち、経路探索プログラムは、予めハードディスク78或いはメインメモリ60に記憶されている、全ての近接する代表点の組み合わせについて算出された最短移動経路及びその距離を参照しながら、代表点R11から代表点R33まで、事前に算出された最短移動経路を通って移動する経路のうち、代表点間の最短移動経路の距離の総和が最も小さくなるものを、これら代表点間の最短移動距離として選択する。ここでは、図6に示されるように、低コスト領域45内を移動する経路が選択される。そして、こうして得られる始点Sから代表点R11への最短移動経路、代表点R11から代表点R33への最短移動経路、代表点R33から終点Gへの最短移動経路を連結して、始点Sから終点Gへの最短移動経路が算出される。そして、この経路を示す情報がゲームプログラムに渡される。上述のように、ゲームプログラムでは、この情報に従ってキャラクタを移動させるなどの処理を実行する。
【0038】
また、経路探索プログラムでは、ゲームプログラムで用いられているマップに変更があり、この変更後のマップを示すマップ情報を受け取った場合に、ハードディスク78或いはメインメモリ60に既に記憶されている代表点間の最短移動経路及びその距離を更新するようにしている。例えば、図3のマップ中央に示される移動不可領域41が、図7に示すように横方向に短い移動不可領域41aに変化し、それに伴ってより広い高コスト領域43aが現れた場合、図8に示すように変更後のマップを部分領域11〜33に分割して、変更前後のマップにおいて内容変更があった部分領域がどれであるかを調べる。そして、その変更があった部分領域について、再度、移動可能な連続領域を抽出するとともに、各連続領域に代表点を設定する。図7の例では、部分領域22のみに変更があり、移動可能な連続領域が1つに減っている。この場合、部分領域22の代表点は、R22a及びR22bの2つから、R22の1つになる。
【0039】
図9に示すように、経路探索プログラムでは、新しく設定された代表点R22から、変更のあった部分領域22の上下左右に隣接する部分領域12、部分領域32、部分領域21、部分領域23の代表点R12、代表点R32、代表点R21、代表点R23のそれぞれへの最短移動経路及びその距離を算出する。このときも、各最短移動経路は、隣接する2つの部分領域のみを通り、その他の部分領域は通過しないようにして設定される。そして、変更前の部分領域22の代表点R22a及びR22bを端点とする最短移動経路及びその距離を、ハードディスク78或いはメインメモリ60から削除し、代わりに、新たに算出された代表点R22を端点とする最短移動経路及びその距離を格納する。そして、その後は更新後の最短移動経路及びその距離の情報に基づいて、任意の始点及び終点間の最短移動経路を算出する。
【0040】
ここで、経路探索装置として機能するコンピュータ50の情報処理についてさらに説明する。図10に示すように、経路探索プログラムを実行することによりコンピュータ50では経路情報算出部90、経路情報記憶部91及び経路探索部92が実現される。経路情報算出部90は、MPU51を中心として構成されており、経路探索の対象となるマップを示すマップ情報を取得し、マップ上に複数の代表点を設定する。そして、近接する代表点間の最短移動経路及びその距離を演算して、それらの情報を経路情報記憶部91に格納する。また、マップ情報に変更があった場合には、経路情報記憶部91に記憶される最短移動経路及びその距離を更新する。上述のようにMPU51は、サブプロセッサ54a〜54hを備えており、代表点間の最短移動経路を算出する際には、各サブプロセッサ54a〜54hに対して部分領域が割り当てられ、これにより該部分領域の代表点が関連づけられる。例えば、サブプロセッサ54a〜54hのそれぞれに対して、ランダムに、或いはマップの左上から順に選択される略同数の部分領域が割り当てられる。そして、各サブプロセッサ54a〜54hは、該プロセッサに割り当てられた部分領域の代表点から、右側及び下側に隣接する部分領域の代表点への最短移動経路及びその距離を、それぞれ並列に演算する。こうして、最短移動経路の演算を高速に行うようにしている。
【0041】
経路情報記憶部91は、ハードディスク78或いはメインメモリ60を中心として構成されており、経路情報算出部90により算出される代表点間の最短移動経路及びその距離を記憶する。また、経路探索部92は、MPU51を中心として構成されており、経路情報記憶部91の記憶内容を参照しながら、任意の始点及び終点間の最短移動経路を算出する。
【0042】
図11は、経路情報算出部90による準備処理を示している。この処理は、ゲームプログラムなどの外部プログラムからマップ情報を最初に受け取った場合に実行されるものであり、まずマップ情報を取得すると、この情報が示すマップを縦横に等間隔に分割して複数の矩形の部分領域を設定する(S102)。次に、それらの部分領域を各サブプロセッサ54a〜54hに割り当て、各プロセッサ54a〜54hが並列に、割り当てられた部分領域内の可動範囲(移動可能な連続領域)を抽出する(S103)。次に、各可動範囲に対して代表点を設定する(S104)。
【0043】
全ての部分領域に対して代表点が設定されると、次に各プロセッサ54a〜54hが並列に、割り当てられた部分領域の代表点から、右側及び下側に隣接する部分領域の代表点に至る最短移動経路及びその距離を算出する(S105)。全ての部分領域に対して代表点が設定されるまで待ってから、各プロセッサ54a〜54hが、割り当てられた部分領域について最短移動経路及びその距離の算出を開始することで、隣接する部分領域の代表点が算出されるまで演算処理の待機を強いられるといった無駄をなくすことができ、これにより最短移動経路及びその距離の計算を効率化できる。なお、最短移動距離及びその距離を算出する際(S105)と、可動範囲の抽出(S103)及び代表点の設定(S104)を行う際とで、プロセッサ54a〜54hと部分領域との割り当ては異なってよい。その後、各プロセッサ54a〜54hで算出される最短移動経路及びその距離を経路情報記憶部91に格納する(S106)。
【0044】
次に、図12は経路情報算出部90による、経路情報記憶部91の記憶内容を更新する処理、及び経路探索部92による、経路情報記憶部91の最新の記憶内容に基づく経路探索処理を示している。同図に示される処理は、例えばゲームプログラムなどの外部プログラムから始点及び終点が与えられた場合に実行される。この処理では、まず経路情報算出部90がマップの更新があったか否かを判断する(S201)。例えば、外部プログラムからマップの更新の有無が与えられる場合には、与えられた情報から直ちに判断できる。また、最新のマップ情報がハードディスク78に格納されている場合には、その更新時刻により更新の有無を判断できる。そして、マップ情報の更新があった場合には、最新のマップ情報を取得して(S202)、どの部分領域に変更があったかを調べる(S203)。そして、それら変更があった部分領域を各サブプロセッサ54a〜54hに割り当て、各プロセッサ54a〜54hが並列に、割り当てられた部分領域内の可動範囲を抽出する(S204)。次に、各可動範囲に対して代表点を設定する(S205)。全ての変更のあった部分領域に対して代表点が設定されると、次に各プロセッサ54a〜54hが並列に、割り当てられた部分領域の代表点から、右側及び下側に隣接する部分領域の代表点に至る最短移動経路及びその距離を算出する(S206)。その後、変更前の部分領域の代表点を端点とする最短移動経路及びその距離を経路情報記憶部91から削除するとともに、各プロセッサ54a〜54hで新たに算出された最短移動経路及びその距離を経路情報記憶部91に格納する(S207)。S201でマップが更新されていないと判断すると、S202〜S207の処理はスキップされる。
【0045】
その後、ゲームプログラムなどの外部プログラムから与えられる始点及び終点の座標を取得し(S208)、始点から最も近い代表点を選択するとともに、その選択された代表点への最短移動経路を算出する(S209)。また、終点に最も近い代表点を選択するとともに、そこから終点への最短移動経路を算出する(S210)。さらに、S209及びS210で選択される代表点間の最短移動経路を算出する(S211)。そして、S209〜S211で算出される最短移動経路を連結して、外部プログラムから与えられる始点及び終点を結ぶ最短移動経路の情報を生成し、これを元の外部プログラムに返す(S212)。
【0046】
以上説明した実施形態によると、マップ情報が示すマップに複数の代表点を設定し、サブプロセッサ54a〜54hにこれらの代表点を関連づけ、代表点間の最短移動経路及びその距離をサブプロセッサ54a〜54hにより並列処理するようにしたので、マップ情報が与えられてから短時間で代表点間の最短移動経路を演算することができる。
【図面の簡単な説明】
【0047】
【図1】本発明の一実施形態に係る経路探索装置として機能するコンピュータのハードウェア構成を示す図である。
【図2】MPUの構成を示す図である。
【図3】マップ情報が示すマップの一例を示す図である。
【図4】部分領域及び代表点の設定を示す図である。
【図5】事前の最短移動経路の算出を示す図である。
【図6】任意の始点及び終点間の最短移動経路の算出を示す図である。
【図7】変更されたマップの一例を示す図である。
【図8】変更されたマップに対する部分領域及び代表点の設定を示す図である。
【図9】変更のある部分領域に関する最短移動経路の更新を示す図である。
【図10】本発明の一実施形態に係る経路探索装置の機能ブロック図である。
【図11】事前の最短移動経路の算出を示すフロー図である。
【図12】任意の始点及び終点間の最短移動経路の算出を示すフロー図である。
【符号の説明】
【0048】
11,12,13,21,22,23,31,32,33 部分領域、40,41,41a,42 移動不可領域、43,43a,44 高コスト領域、45 低コスト領域、50 コンピュータ、51 MPU、52 メインプロセッサ、54a〜54h サブプロセッサ、56 バス、58 メモリコントローラ、60 メインメモリ、62,80 インタフェース、64 画像処理部、66 モニタ、68 入出力処理部、70 音声処理部、72 スピーカ、74 光ディスク読み取り部、76 光ディスク、78 ハードディスク、82 操作デバイス、88 ネットワークインタフェース、90 経路情報算出部、91 経路情報記憶部、92 経路探索部。
【技術分野】
【0001】
本発明は経路探索装置、経路探索方法及びプログラムに関する。
【背景技術】
【0002】
経路探索アルゴリズムは、列車路線探索やカーナビゲーションなど、多くの応用製品で用いられている基本的なコンピュータソフトウェアアルゴリズムの1つである。経路探索アルゴリズムは一般に計算量が膨大になることから、探索処理の一部を事前に実行するとともに、その結果を記憶手段に記憶しておく場合がある(下記特許文献1参照)。こうすれば、記憶手段に記憶された情報を用いて、経路探索結果を短時間に得ることができるようになる。
【特許文献1】特開平10−9884号公報
【発明の開示】
【発明が解決しようとする課題】
【0003】
しかしながら、ゲームに用いられる仮想空間のマップなど、内容が動的に変化するマップに対しては、上記のように探索処理の一部を事前に実行しておくのは困難であり、上記従来技術は、実在の道路地図や列車路線図など、内容が固定されたマップへの適用に限られるという問題があった。
【0004】
本発明は上記課題に鑑みてなされたものであって、その目的は、任意のマップに対して経路探索結果を短時間に得ることができる経路探索装置、経路探索方法及びプログラムを提供することにある。
【課題を解決するための手段】
【0005】
上記課題を解決するために、本発明に係る経路探索装置は、経路探索の対象となるマップを示すマップ情報を取得するマップ情報取得手段と、前記マップ情報が示すマップ上に複数の代表点を設定する代表点設定手段と、前記代表点間の経路及びその距離を演算する事前経路演算手段と、前記事前経路演算手段により演算される前記代表点間の経路及びその距離を記憶する記憶手段と、前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する経路探索手段と、を含み、前記事前経路演算手段は、並列処理可能であってそれぞれ前記代表点のうち一部が関連づけられる複数のプロセッサを含み、前記各プロセッサは、該プロセッサに関連づけられる前記代表点から他の前記代表点への経路のうち少なくとも1つ及びその距離を並列に演算する、ことを特徴とする。
【0006】
また、本発明に係る経路探索方法は、経路探索の対象となるマップを示すマップ情報を取得するマップ情報取得ステップと、前記マップ情報が示すマップ上に複数の代表点を設定する代表点設定ステップと、前記代表点間の経路及びその距離を演算する事前経路演算ステップと、前記事前経路演算手段により演算される前記代表点間の経路及びその距離を記憶手段に格納する格納ステップと、前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する経路探索ステップと、を含み、前記事前経路演算ステップは、並列処理可能であってそれぞれ前記代表点のうち一部が関連づけられる複数のプロセッサのそれぞれにより、該プロセッサに関連づけられる前記代表点から他の前記代表点への経路のうち少なくとも1つ及びその距離を並列に演算する、ことを特徴とする。
【0007】
また、本発明に係るプログラムは、経路探索の対象となるマップを示すマップ情報を取得するマップ情報取得手段、前記マップ情報が示すマップ上に複数の代表点を設定する代表点設定手段、前記代表点間の経路及びその距離を演算する事前経路演算手段、前記事前経路演算手段により演算される前記代表点間の経路及びその距離を記憶する記憶手段、及び前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する経路探索手段として、並列処理可能な複数のプロセッサを備えるコンピュータを機能させるためのプログラムであって、前記各プロセッサにはそれぞれ前記代表点のうち一部が割り当てられ、前記事前経路演算手段は、前記各プロセッサにより、該プロセッサに関連づけられる前記代表点から他の前記代表点への経路のうち少なくとも1つ及びその距離を並列に演算する、ことを特徴とする。なお、プログラムは、CD−ROM、DVD−ROMなど、コンピュータ読取可能な各種の情報記憶媒体に格納されてよい。
【0008】
また、前記代表点設定手段は、前記マップ情報が示すマップ上に複数の部分領域を設定するとともに、前記各部分領域に対して1以上の代表点を設定してよい。このとき、前記事前経路演算手段に含まれる前記各プロセッサは、該プロセッサに関連づけられる前記代表点から、該代表点に係る前記部分領域に隣接する前記部分領域に対して設定される前記代表点のうち少なくとも1つへ、それら隣接する前記部分領域のみを通って至る経路及びその距離を演算してよい。また、前記各部分領域は共通の矩形状をなしてよい。このとき、前記事前経路演算手段に含まれる前記各プロセッサは、該プロセッサに関連づけられる前記代表点から、該代表点に係る前記部分領域の直交するいずれかの2辺に接する前記部分領域に対して設定される前記代表点のうち少なくとも1つへ、それら前記部分領域のみを通って至る経路及びその距離を演算するようにしてよい。
【0009】
また、前記代表点設定手段は、すでに取得された前記マップ情報が示すマップとは異なるマップを示す前記マップ情報が前記マップ情報取得手段により取得される場合に、前記複数の部分領域のうちどの前記部分領域に変更があるかを判断するとともに、変更のある前記部分領域に対して1以上の前記代表点を再設定してよい。この場合、前記事前経路演算手段は、再設定される前記代表点を端点とする経路及びその距離を再演算してよい。
【0010】
また、前記経路探索手段は、前記始点の位置に応じて前記代表点のうち1つを選択するとともに、前記始点から該選択される代表点への経路を決定する第1経路決定手段と、前記終点の位置に応じて前記代表点のうち1つを選択するとともに、該選択される代表点から前記終点への経路を決定する第2経路決定手段と、前記記憶手段に記憶される経路及びその距離に基づいて、前記選択される代表点間の経路を決定する第3経路決定手段と、を含んでよい。
【0011】
また、本発明に係る経路探索装置は、経路探索の対象となるマップを示すマップ情報を取得するマップ情報取得手段と、前記マップ情報が示すマップ上に複数の部分領域を設定するとともに、前記各部分領域に対して1以上の代表点を設定する代表点設定手段と、前記各代表点から、該代表点に係る前記部分領域に隣接する前記部分領域に対して設定される前記代表点のうち少なくとも1つへ、それら隣接する前記部分領域のみを通って至る経路、及びその距離を演算する事前経路演算手段と、前記事前経路演算手段により演算される前記代表点間の経路及びその距離を記憶する記憶手段と、前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する経路探索手段と、を含み、前記代表点設定手段は、すでに取得された前記マップ情報が示すマップとは異なるマップを示す前記マップ情報が前記マップ情報取得手段により取得される場合に、前記複数の部分領域のうちどの前記部分領域に変更があるかを判断するとともに、変更のある前記部分領域に対して1以上の前記代表点を再設定し、前記事前経路演算手段は、再設定される前記代表点を端点とする経路及びその距離を再演算する、ことを特徴とする。
【0012】
また、本発明に係る経路探索方法は、経路探索の対象となるマップを示すマップ情報を取得するステップと、前記マップ情報が示すマップ上に複数の部分領域を設定するとともに、前記各部分領域に対して1以上の代表点を設定するステップと、前記各代表点から、該代表点に係る前記部分領域に隣接する前記部分領域に対して設定される前記代表点のうち少なくとも1つへ、それら隣接する前記部分領域のみを通って至る経路、及びその距離を演算するステップと、演算される前記代表点間の経路及びその距離を記憶手段に格納するステップと、前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索するステップと、すでに取得された前記マップ情報が示すマップとは異なるマップを示す前記マップ情報が新たに取得される場合に、前記複数の部分領域のうちどの前記部分領域に変更があるかを判断するとともに、変更のある前記部分領域に対して1以上の前記代表点を再設定するステップと、再設定される前記代表点を端点とする経路及びその距離を再演算するステップと、を含むことを特徴とする。
【0013】
また、本発明に係るプログラムは、経路探索の対象となるマップを示すマップ情報を取得する手段、前記マップ情報が示すマップ上に複数の部分領域を設定するとともに、前記各部分領域に対して1以上の代表点を設定する手段、前記各代表点から、該代表点に係る前記部分領域に隣接する前記部分領域に対して設定される前記代表点のうち少なくとも1つへ、それら隣接する前記部分領域のみを通って至る経路、及びその距離を演算する手段、演算される前記代表点間の経路及びその距離を記憶手段に格納する手段、前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する手段、すでに取得された前記マップ情報が示すマップとは異なるマップを示す前記マップ情報が新たに取得される場合に、前記複数の部分領域のうちどの前記部分領域に変更があるかを判断するとともに、変更のある前記部分領域に対して1以上の前記代表点を再設定する手段、及び再設定される前記代表点を端点とする経路及びその距離を再演算する手段としてコンピュータを機能させるためのプログラムである。このプログラムも、CD−ROM、DVD−ROMなど、コンピュータ読取可能な各種の情報記憶媒体に格納されてよい。
【0014】
また、前記距離は、該距離に係る経路上に設定されるコストに基づいて演算されてよい。
【発明を実施するための最良の形態】
【0015】
以下、本発明の実施形態について図面に基づき詳細に説明する。
【0016】
図1は、本実施形態に係る経路探索装置として用いられるコンピュータのハードウェア構成を示す図である。同図に示すように、コンピュータ50は、MPU(Micro Processing Unit)51と、メインメモリ60と、画像処理部64と、モニタ66と、入出力処理部68と、音声処理部70と、スピーカ72と、光ディスク読み取り部74と、光ディスク76と、ハードディスク78と、インタフェース(I/F)80と、操作デバイス82と、ネットワークインタフェース88と、を含んで構成されるコンピュータシステムである。また、図2は、MPU51の構成を示す図である。同図に示すように、MPU51は、メインプロセッサ52と、サブプロセッサ54a,54b,54c,54d,54e,54f,54g,54hと、バス56と、メモリコントローラ58と、インタフェース(I/F)62と、を含んで構成される。すなわち、MPU51は、それぞれ並列して情報処理を実行することができるメインプロセッサ52及びサブプロセッサ54a〜54hを備える、マルチコアプロセッサである。
【0017】
メインプロセッサ52は、図示しないROM(Read Only Memory)に記憶されるオペレーティングシステム、例えばDVD(Digital Versatile Disk)−ROM等の光ディスク36から読み出されるプログラム及びデータや、通信ネットワークを介して供給されるプログラム及びデータ等に基づいて、各種情報処理を行ったり、サブプロセッサ54a〜54hに対する制御を行ったりする。
【0018】
サブプロセッサ54a〜54hは、メインプロセッサ52からの指示に従って、各種情報処理を行ったり、コンピュータ50の各部を、例えばDVD−ROM等の光ディスク36から読み出されるプログラム及びデータや、通信ネットワークを介して供給されるプログラム及びデータ等に基づいて制御したりする。
【0019】
バス56は、アドレス及びデータをコンピュータ50の各部でやり取りするためのものである。メインプロセッサ52、サブプロセッサ54a〜54h、メモリコントローラ58、インタフェース62は、バス56を介して相互にデータ授受可能に接続される。
【0020】
メモリコントローラ58は、メインプロセッサ52及びサブプロセッサ54a〜54hからの指示に従って、メインメモリ60へのアクセスを行う。メインメモリ60には、光ディスク76やハードディスク78から読み出されたプログラム及びデータや、通信ネットワークを介して供給されたプログラム及びデータが必要に応じて書き込まれる。メインメモリ60はメインプロセッサ52やサブプロセッサ54a〜54hの作業用としても用いられる。
【0021】
インタフェース62には画像処理部64及び入出力処理部68が接続される。メインプロセッサ52及びサブプロセッサ54a〜54hと、画像処理部64又は入出力処理部68と、の間のデータ授受はインタフェース62を介して行われる。
【0022】
画像処理部64は、GPU(Graphical Processing Unit)とフレームバッファとを含んで構成される。GPUは、メインプロセッサ52やサブプロセッサ54a〜54hから供給される画像データに基づいてフレームバッファに各種画面を描画する。フレームバッファに形成された画面、すなわちMPU51の実行結果を示す画面は、所定のタイミングでビデオ信号に変換されてモニタ66に出力される。なお、モニタ66には例えば家庭用テレビ受像機が用いられる。
【0023】
入出力処理部68には、音声処理部70、光ディスク読み取り部74、ハードディスク78、インタフェース80、ネットワークインタフェース88が接続される。入出力処理部68は、メインプロセッサ52及びサブプロセッサ54a〜54hと、音声処理部70、光ディスク読み取り部74、ハードディスク78、インタフェース80、ネットワークインタフェース88と、の間のデータ授受を制御する。
【0024】
音声処理部70は、SPU(Sound Processing Unit)とサウンドバッファとを含んで構成される。サウンドバッファには、光ディスク76やハードディスク78から読み出されたゲーム音楽、ゲーム効果音やメッセージなどの各種音声データが記憶される。SPUは、これらの各種音声データを再生してスピーカ72から出力させる。なお、スピーカ72には例えば家庭用テレビ受像機の内蔵スピーカが用いられる。
【0025】
光ディスク読み取り部74は、メインプロセッサ52及びサブプロセッサ54a〜54hからの指示に従って、光ディスク76に記憶されたプログラムやデータを読み取る。なお、コンピュータ50は、光ディスク76以外の他のコンピュータ読取可能な情報記憶媒体に記憶されたプログラムやデータを読取可能に構成してもよい。
【0026】
光ディスク76は例えばDVD−ROM等の一般的な光ディスク(コンピュータ読取可能な情報記憶媒体)である。また、ハードディスク78は一般的なハードディスク装置である。光ディスク76やハードディスク78には各種プログラムやデータがコンピュータ読取可能に記憶される。
【0027】
インタフェース(I/F)80は、操作デバイス82等の各種周辺機器を接続するためのインタフェースである。このようなインタフェースとしては、例えばUSB(Universal Serial Bus)インタフェースが用いられる。
【0028】
操作デバイス82は汎用操作入力手段であり、ユーザが各種操作(例えばゲーム操作)を入力するために用いられる。入出力処理部68は、所定時間(例えば1/60秒)ごとに操作デバイス82から、その各部の状態を無線又は有線通信により取得し、その結果を表す操作信号をメインプロセッサ52やサブプロセッサ54a〜54hに供給する。メインプロセッサ52やサブプロセッサ54a〜54hは、ユーザによって行われた操作の内容をその操作信号に基づいて判断する。なお、コンピュータ50は複数の操作デバイス82を通信接続可能に構成されており、各操作デバイス82から入力される操作信号に基づいて、メインプロセッサ52やサブプロセッサ54a〜54hが各種処理を実行するようになっている。
【0029】
操作デバイス82は、ユーザがコンピュータ50を操作するためのデバイスであって、USB等の有線通信手段、及びBlueTooth(商標)やワイヤレスLAN等の無線通信手段を備える可搬型の小型コンピュータとして構成されており、操作デバイス52において行われたユーザの操作内容を示す操作データがコンピュータ50に有線又は無線で送信されるようになっている。
【0030】
以下、上記ハードウェア構成を有するコンピュータ50に、ゲームプログラム及び経路探索プログラムを実行させる例について説明する。ここで、ゲームプログラムは、例えば仮想空間でキャラクタが自在に移動するゲームに関するものである。また、経路探索プログラムは、ゲームプログラムにより起動され、該ゲームプログラムから、前記仮想空間のマップを示す情報(マップ情報)、前記マップにおける前記キャラクタの移動経路の出発地点(始点)及び目標地点(終点)を受け取る。そして、前記マップにおける始点及び終点間の最短移動経路を演算し、それをゲームプログラムに通知する。ゲームプログラムでは、こうして通知される経路に沿ってキャラクタを仮想空間内で移動させる処理を実行する。ゲームプログラムや経路探索プログラムは、例えば光ディスク76に格納され、該光ディスクからコンピュータ50にロードされる。そして、いずれもMPU51によって実行される。
【0031】
図3は、ゲームプログラムから経路探索プログラムに渡されるマップ情報が示すマップの一例を示している。同図に示すマップには、仮想的な山や建物が設けられていてキャラクタが進入できない移動不可領域40,41,42、仮想的な舗装道路が存在してキャラクタが容易に移動できる低コスト領域45、それ以外の高コスト領域43,44が配置されている。マップ情報は、移動不可領域40,41,42の位置、低コスト領域45の位置及びキャラクタにとっての移動のし易さ(例えば、単位距離を移動するのに必要となる時間)を示す数値(以下、「移動コスト」という。)、高コスト領域43,44の位置及び移動コストを特定可能な情報である。
【0032】
経路探索プログラムは、図4に示すように、マップ情報が与えられるとマップ情報により示されるマップ全体を複数の部分領域11〜33に分割する。例えば、マップ情報により示されるマップが矩形であれば部分領域11〜33も矩形とし、それらの縦の長さが等しく、また横の長さも等しく、且つそれらの長さが予め決められた範囲に収まるようにする。ここでは、マップを縦方向に3分割、横方向に3分割して、合計9つの部分領域11〜33をマップ上に設定する。そして、各部分領域11〜33が縦横に整列配置される。その後、各部分領域11〜33に対して1以上の代表点を設定する。具体的には、各部分領域11〜33における移動可能な連続領域を検出して、各連続領域に対して1つの代表点を設定する。図4の例では、マップ中央の部分領域22は中央に移動不可領域41が横切っており、移動可能な領域が上下に分離し、それにより移動可能な連続領域が2つ形成されている。そこで、上側の連続領域に対しては代表点R22aが設定され、下側の連続領域に対しては代表点R22bが設定されている。他の部分領域11,12,13,21,23,31,32,33はいずれも移動可能な連続領域を1つだけ有しており、それぞれ1つずつ代表点R11,R12,R13,R21,R23,R31,R32,R33が設定されている。これらの代表点は、例えば各連続領域の重心位置に基づいて決定される。すなわち、連続領域内の各位置の座標をその位置の移動コストで重み付けして重心位置を算出し、その重心位置が移動不可領域40,41,42内でなければ、そこを代表点とする。また、移動不可領域40,41,42内であれば、そのすぐ外側を代表点とする。
【0033】
経路探索プログラムは、こうしてマップ情報が示すマップに部分領域11〜33を設定し、各部分領域に含まれる移動可能な連続領域に対して1つずつ代表点を設定すると、次に近接する代表点間の最短移動経路及びその距離(コスト付距離;経路上の位置の移動コストの総和)を算出する。具体的には、各部分領域について、その内側に設定されている代表点(仮始点)を取得するとともに、その部分領域の右側(存在すれば)及び下側に隣接する部分領域内に設定されている代表点(仮終点)を取得する。そして、これら仮始点及び仮終点間の最短移動経路及びその距離を算出する。これにより、図5において太い実線で示されるように、例えばマップ中央の部分領域22の代表点R22a及びR22bについては、それらから右隣の部分領域23の代表点R23への最短移動経路及びその距離、下側に隣接する部分領域32の代表点R32への最短移動経路及びその距離が算出される。左隣の部分領域21の代表点R21、上側に隣接する部分領域12の代表点R12への最短移動経路及びその距離は、それぞれ部分領域21及び部分領域12に関する最短移動経路及びその距離として算出される。これにより結果的に、すべての隣接領域の組み合わせについて、各領域の代表点を結ぶ最短移動経路及びその距離が算出されることになる。このように、ある矩形の部分領域を注目領域とし、その注目領域の代表点と、該注目領域の直交するいずれかの2辺に接する部分領域の代表点と、の最短移動経路及びその距離を算出し、且つ、マップに設定されたすべての部分領域を順次注目領域とすることで、すべての必要な最短移動経路及びその距離が算出されることになる。
【0034】
また、各最短移動経路は、隣接する2つの部分領域のみを通り、その他の部分領域は通過しないようにして設定される。これにより、ある部分領域に変更が生じたとしても、最短移動距離は、その変更のあった部分領域に設定された代表点から、及びそこに隣接する部分領域に設定された代表点に至るものだけを再計算すれば済み、他の最短移動経路はそのまま利用し続けることができる。
【0035】
さらに、最短移動経路とは、経路上の位置の移動コストの総和が最小となる経路を意味しており、例えばダイクストラ法、A*(A-Star)アルゴリズムなど、公知の各種経路探索アルゴリズムにより、その距離とともに容易に算出することができる。また、代表点R22aから代表点R32へは、他の部分領域(23や21など)を経由しなければキャラクタは移動できず、これら代表点間の最短移動経路は存在しないものとして扱われている。すなわち、本実施形態においては、仮始点と仮終点との間の最短移動経路としては、仮始点及び仮終点が含まれる、隣接する2つの部分領域以外の領域を通過しないものが算出されるようになっている。
【0036】
経路探索プログラムは、こうして最短移動経路及びその距離を全ての近接する代表点の組み合わせについて算出すると、それらをハードディスク78或いはメインメモリ60に記憶する。
【0037】
その後、経路探索プログラムは、ゲームプログラムからマップ上の位置である始点及び終点を受け取ると、それらの間の最短移動経路を算出する。具体的には、図6に示すように始点Sの位置に応じて、例えば移動コストを考慮して該始点Sに最も近い代表点R11を選択し、また終点Gの位置に応じて、例えば移動コストを考慮して該終点Gに最も近い代表点R33を選択する。なお、始点Sが属する部分領域11の代表点R11を選択してもよいし、同様に終点Gが属する部分領域33の代表点R33を選択してもよい。そして、始点Sから該始点Sに対して選択された代表点R11への最短移動経路を、例えばダイクストラ法やA*アルゴリズムなどにより算出する。同様に、終点Gに対して選択された代表点R33から終点Gへの最短移動経路を、例えばダイクストラ法やA*アルゴリズムなどにより算出する。さらに、始点S及び終点Gに対して選択された代表点R11及びR33の間の最短移動経路も、例えばダイクストラ法やA*アルゴリズムなどにより算出する。このとき、最短移動経路は、始点Sに対して選択された代表点R11から、隣接する部分領域の代表点を順に通過しながら、終点Gに対して選択された代表点R33に至る経路として算出する。そして、順に通過する2つの代表点を結ぶ移動経路は、事前にハードディスク78或いはメインメモリ60に記憶されたものを用いる。すなわち、経路探索プログラムは、予めハードディスク78或いはメインメモリ60に記憶されている、全ての近接する代表点の組み合わせについて算出された最短移動経路及びその距離を参照しながら、代表点R11から代表点R33まで、事前に算出された最短移動経路を通って移動する経路のうち、代表点間の最短移動経路の距離の総和が最も小さくなるものを、これら代表点間の最短移動距離として選択する。ここでは、図6に示されるように、低コスト領域45内を移動する経路が選択される。そして、こうして得られる始点Sから代表点R11への最短移動経路、代表点R11から代表点R33への最短移動経路、代表点R33から終点Gへの最短移動経路を連結して、始点Sから終点Gへの最短移動経路が算出される。そして、この経路を示す情報がゲームプログラムに渡される。上述のように、ゲームプログラムでは、この情報に従ってキャラクタを移動させるなどの処理を実行する。
【0038】
また、経路探索プログラムでは、ゲームプログラムで用いられているマップに変更があり、この変更後のマップを示すマップ情報を受け取った場合に、ハードディスク78或いはメインメモリ60に既に記憶されている代表点間の最短移動経路及びその距離を更新するようにしている。例えば、図3のマップ中央に示される移動不可領域41が、図7に示すように横方向に短い移動不可領域41aに変化し、それに伴ってより広い高コスト領域43aが現れた場合、図8に示すように変更後のマップを部分領域11〜33に分割して、変更前後のマップにおいて内容変更があった部分領域がどれであるかを調べる。そして、その変更があった部分領域について、再度、移動可能な連続領域を抽出するとともに、各連続領域に代表点を設定する。図7の例では、部分領域22のみに変更があり、移動可能な連続領域が1つに減っている。この場合、部分領域22の代表点は、R22a及びR22bの2つから、R22の1つになる。
【0039】
図9に示すように、経路探索プログラムでは、新しく設定された代表点R22から、変更のあった部分領域22の上下左右に隣接する部分領域12、部分領域32、部分領域21、部分領域23の代表点R12、代表点R32、代表点R21、代表点R23のそれぞれへの最短移動経路及びその距離を算出する。このときも、各最短移動経路は、隣接する2つの部分領域のみを通り、その他の部分領域は通過しないようにして設定される。そして、変更前の部分領域22の代表点R22a及びR22bを端点とする最短移動経路及びその距離を、ハードディスク78或いはメインメモリ60から削除し、代わりに、新たに算出された代表点R22を端点とする最短移動経路及びその距離を格納する。そして、その後は更新後の最短移動経路及びその距離の情報に基づいて、任意の始点及び終点間の最短移動経路を算出する。
【0040】
ここで、経路探索装置として機能するコンピュータ50の情報処理についてさらに説明する。図10に示すように、経路探索プログラムを実行することによりコンピュータ50では経路情報算出部90、経路情報記憶部91及び経路探索部92が実現される。経路情報算出部90は、MPU51を中心として構成されており、経路探索の対象となるマップを示すマップ情報を取得し、マップ上に複数の代表点を設定する。そして、近接する代表点間の最短移動経路及びその距離を演算して、それらの情報を経路情報記憶部91に格納する。また、マップ情報に変更があった場合には、経路情報記憶部91に記憶される最短移動経路及びその距離を更新する。上述のようにMPU51は、サブプロセッサ54a〜54hを備えており、代表点間の最短移動経路を算出する際には、各サブプロセッサ54a〜54hに対して部分領域が割り当てられ、これにより該部分領域の代表点が関連づけられる。例えば、サブプロセッサ54a〜54hのそれぞれに対して、ランダムに、或いはマップの左上から順に選択される略同数の部分領域が割り当てられる。そして、各サブプロセッサ54a〜54hは、該プロセッサに割り当てられた部分領域の代表点から、右側及び下側に隣接する部分領域の代表点への最短移動経路及びその距離を、それぞれ並列に演算する。こうして、最短移動経路の演算を高速に行うようにしている。
【0041】
経路情報記憶部91は、ハードディスク78或いはメインメモリ60を中心として構成されており、経路情報算出部90により算出される代表点間の最短移動経路及びその距離を記憶する。また、経路探索部92は、MPU51を中心として構成されており、経路情報記憶部91の記憶内容を参照しながら、任意の始点及び終点間の最短移動経路を算出する。
【0042】
図11は、経路情報算出部90による準備処理を示している。この処理は、ゲームプログラムなどの外部プログラムからマップ情報を最初に受け取った場合に実行されるものであり、まずマップ情報を取得すると、この情報が示すマップを縦横に等間隔に分割して複数の矩形の部分領域を設定する(S102)。次に、それらの部分領域を各サブプロセッサ54a〜54hに割り当て、各プロセッサ54a〜54hが並列に、割り当てられた部分領域内の可動範囲(移動可能な連続領域)を抽出する(S103)。次に、各可動範囲に対して代表点を設定する(S104)。
【0043】
全ての部分領域に対して代表点が設定されると、次に各プロセッサ54a〜54hが並列に、割り当てられた部分領域の代表点から、右側及び下側に隣接する部分領域の代表点に至る最短移動経路及びその距離を算出する(S105)。全ての部分領域に対して代表点が設定されるまで待ってから、各プロセッサ54a〜54hが、割り当てられた部分領域について最短移動経路及びその距離の算出を開始することで、隣接する部分領域の代表点が算出されるまで演算処理の待機を強いられるといった無駄をなくすことができ、これにより最短移動経路及びその距離の計算を効率化できる。なお、最短移動距離及びその距離を算出する際(S105)と、可動範囲の抽出(S103)及び代表点の設定(S104)を行う際とで、プロセッサ54a〜54hと部分領域との割り当ては異なってよい。その後、各プロセッサ54a〜54hで算出される最短移動経路及びその距離を経路情報記憶部91に格納する(S106)。
【0044】
次に、図12は経路情報算出部90による、経路情報記憶部91の記憶内容を更新する処理、及び経路探索部92による、経路情報記憶部91の最新の記憶内容に基づく経路探索処理を示している。同図に示される処理は、例えばゲームプログラムなどの外部プログラムから始点及び終点が与えられた場合に実行される。この処理では、まず経路情報算出部90がマップの更新があったか否かを判断する(S201)。例えば、外部プログラムからマップの更新の有無が与えられる場合には、与えられた情報から直ちに判断できる。また、最新のマップ情報がハードディスク78に格納されている場合には、その更新時刻により更新の有無を判断できる。そして、マップ情報の更新があった場合には、最新のマップ情報を取得して(S202)、どの部分領域に変更があったかを調べる(S203)。そして、それら変更があった部分領域を各サブプロセッサ54a〜54hに割り当て、各プロセッサ54a〜54hが並列に、割り当てられた部分領域内の可動範囲を抽出する(S204)。次に、各可動範囲に対して代表点を設定する(S205)。全ての変更のあった部分領域に対して代表点が設定されると、次に各プロセッサ54a〜54hが並列に、割り当てられた部分領域の代表点から、右側及び下側に隣接する部分領域の代表点に至る最短移動経路及びその距離を算出する(S206)。その後、変更前の部分領域の代表点を端点とする最短移動経路及びその距離を経路情報記憶部91から削除するとともに、各プロセッサ54a〜54hで新たに算出された最短移動経路及びその距離を経路情報記憶部91に格納する(S207)。S201でマップが更新されていないと判断すると、S202〜S207の処理はスキップされる。
【0045】
その後、ゲームプログラムなどの外部プログラムから与えられる始点及び終点の座標を取得し(S208)、始点から最も近い代表点を選択するとともに、その選択された代表点への最短移動経路を算出する(S209)。また、終点に最も近い代表点を選択するとともに、そこから終点への最短移動経路を算出する(S210)。さらに、S209及びS210で選択される代表点間の最短移動経路を算出する(S211)。そして、S209〜S211で算出される最短移動経路を連結して、外部プログラムから与えられる始点及び終点を結ぶ最短移動経路の情報を生成し、これを元の外部プログラムに返す(S212)。
【0046】
以上説明した実施形態によると、マップ情報が示すマップに複数の代表点を設定し、サブプロセッサ54a〜54hにこれらの代表点を関連づけ、代表点間の最短移動経路及びその距離をサブプロセッサ54a〜54hにより並列処理するようにしたので、マップ情報が与えられてから短時間で代表点間の最短移動経路を演算することができる。
【図面の簡単な説明】
【0047】
【図1】本発明の一実施形態に係る経路探索装置として機能するコンピュータのハードウェア構成を示す図である。
【図2】MPUの構成を示す図である。
【図3】マップ情報が示すマップの一例を示す図である。
【図4】部分領域及び代表点の設定を示す図である。
【図5】事前の最短移動経路の算出を示す図である。
【図6】任意の始点及び終点間の最短移動経路の算出を示す図である。
【図7】変更されたマップの一例を示す図である。
【図8】変更されたマップに対する部分領域及び代表点の設定を示す図である。
【図9】変更のある部分領域に関する最短移動経路の更新を示す図である。
【図10】本発明の一実施形態に係る経路探索装置の機能ブロック図である。
【図11】事前の最短移動経路の算出を示すフロー図である。
【図12】任意の始点及び終点間の最短移動経路の算出を示すフロー図である。
【符号の説明】
【0048】
11,12,13,21,22,23,31,32,33 部分領域、40,41,41a,42 移動不可領域、43,43a,44 高コスト領域、45 低コスト領域、50 コンピュータ、51 MPU、52 メインプロセッサ、54a〜54h サブプロセッサ、56 バス、58 メモリコントローラ、60 メインメモリ、62,80 インタフェース、64 画像処理部、66 モニタ、68 入出力処理部、70 音声処理部、72 スピーカ、74 光ディスク読み取り部、76 光ディスク、78 ハードディスク、82 操作デバイス、88 ネットワークインタフェース、90 経路情報算出部、91 経路情報記憶部、92 経路探索部。
【特許請求の範囲】
【請求項1】
経路探索の対象となるマップを示すマップ情報を取得するマップ情報取得手段と、
前記マップ情報が示すマップ上に複数の代表点を設定する代表点設定手段と、
前記代表点間の経路及びその距離を演算する事前経路演算手段と、
前記事前経路演算手段により演算される前記代表点間の経路及びその距離を記憶する記憶手段と、
前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する経路探索手段と、を含み、
前記事前経路演算手段は、並列処理可能であってそれぞれ前記代表点のうち一部が関連づけられる複数のプロセッサを含み、前記各プロセッサは、該プロセッサに関連づけられる前記代表点から他の前記代表点への経路のうち少なくとも1つ及びその距離を並列に演算する、
ことを特徴とする経路探索装置。
【請求項2】
請求項1に記載の経路探索装置において、
前記代表点設定手段は、前記マップ情報が示すマップ上に複数の部分領域を設定するとともに、前記各部分領域に対して1以上の代表点を設定する、
ことを特徴とする経路探索装置。
【請求項3】
請求項2に記載の経路探索装置において、
前記事前経路演算手段に含まれる前記各プロセッサは、該プロセッサに関連づけられる前記代表点から、該代表点に係る前記部分領域に隣接する前記部分領域に対して設定される前記代表点のうち少なくとも1つへ、それら隣接する前記部分領域のみを通って至る経路及びその距離を演算する、
ことを特徴とする経路探索装置。
【請求項4】
請求項3に記載の経路探索装置において、
前記各部分領域は共通の矩形状をなし、
前記事前経路演算手段に含まれる前記各プロセッサは、該プロセッサに関連づけられる前記代表点から、該代表点に係る前記部分領域の直交するいずれかの2辺に接する前記部分領域に対して設定される前記代表点のうち少なくとも1つへ、それら前記部分領域のみを通って至る経路及びその距離を演算する、
ことを特徴とする経路探索装置。
【請求項5】
請求項2乃至4のいずれかに記載の経路探索装置において、
前記代表点設定手段は、すでに取得された前記マップ情報が示すマップとは異なるマップを示す前記マップ情報が前記マップ情報取得手段により取得される場合に、前記複数の部分領域のうちどの前記部分領域に変更があるかを判断するとともに、変更のある前記部分領域に対して1以上の前記代表点を再設定し、
前記事前経路演算手段は、再設定される前記代表点を端点とする経路及びその距離を再演算する、
ことを特徴とする経路探索装置。
【請求項6】
請求項1乃至5のいずれかに記載の経路探索装置において、
前記経路探索手段は、
前記始点の位置に応じて前記代表点のうち1つを選択するとともに、前記始点から該選択される代表点への経路を決定する第1経路決定手段と、
前記終点の位置に応じて前記代表点のうち1つを選択するとともに、該選択される代表点から前記終点への経路を決定する第2経路決定手段と、
前記記憶手段に記憶される経路及びその距離に基づいて、前記選択される代表点間の経路を決定する第3経路決定手段と、を含む、
ことを特徴とする経路探索装置。
【請求項7】
経路探索の対象となるマップを示すマップ情報を取得するマップ情報取得手段と、
前記マップ情報が示すマップ上に複数の部分領域を設定するとともに、前記各部分領域に対して1以上の代表点を設定する代表点設定手段と、
前記各代表点から、該代表点に係る前記部分領域に隣接する前記部分領域に対して設定される前記代表点のうち少なくとも1つへ、それら隣接する前記部分領域のみを通って至る経路、及びその距離を演算する事前経路演算手段と、
前記事前経路演算手段により演算される前記代表点間の経路及びその距離を記憶する記憶手段と、
前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する経路探索手段と、を含み、
前記代表点設定手段は、すでに取得された前記マップ情報が示すマップとは異なるマップを示す前記マップ情報が前記マップ情報取得手段により取得される場合に、前記複数の部分領域のうちどの前記部分領域に変更があるかを判断するとともに、変更のある前記部分領域に対して1以上の前記代表点を再設定し、
前記事前経路演算手段は、再設定される前記代表点を端点とする経路及びその距離を再演算する、
ことを特徴とする経路探索装置。
【請求項8】
請求項1乃至7のいずれかに記載の経路探索装置において、
前記距離は、該距離に係る経路上に設定されるコストに基づいて演算される、
ことを特徴とする経路探索装置。
【請求項9】
経路探索の対象となるマップを示すマップ情報を取得するマップ情報取得ステップと、
前記マップ情報が示すマップ上に複数の代表点を設定する代表点設定ステップと、
前記代表点間の経路及びその距離を演算する事前経路演算ステップと、
前記事前経路演算ステップで演算される前記代表点間の経路及びその距離を記憶手段に格納する格納ステップと、
前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する経路探索ステップと、を含み、
前記事前経路演算ステップは、並列処理可能であってそれぞれ前記代表点のうち一部が関連づけられる複数のプロセッサのそれぞれにより、該プロセッサに関連づけられる前記代表点から他の前記代表点への経路のうち少なくとも1つ及びその距離を並列に演算する、
ことを特徴とする経路探索方法。
【請求項10】
経路探索の対象となるマップを示すマップ情報を取得するマップ情報取得手段、
前記マップ情報が示すマップ上に複数の代表点を設定する代表点設定手段、
前記代表点間の経路及びその距離を演算する事前経路演算手段、
前記事前経路演算手段により演算される前記代表点間の経路及びその距離を記憶する記憶手段、及び
前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する経路探索手段
として、並列処理可能な複数のプロセッサを備えるコンピュータを機能させるためのプログラムであって、
前記各プロセッサにはそれぞれ前記代表点のうち一部が割り当てられ、前記事前経路演算手段は、前記各プロセッサにより、該プロセッサに関連づけられる前記代表点から他の前記代表点への経路のうち少なくとも1つ及びその距離を並列に演算する、
ことを特徴とするプログラム。
【請求項11】
経路探索の対象となるマップを示すマップ情報を取得するステップと、
前記マップ情報が示すマップ上に複数の部分領域を設定するとともに、前記各部分領域に対して1以上の代表点を設定するステップと、
前記各代表点から、該代表点に係る前記部分領域に隣接する前記部分領域に対して設定される前記代表点のうち少なくとも1つへ、それら隣接する前記部分領域のみを通って至る経路、及びその距離を演算するステップと、
演算される前記代表点間の経路及びその距離を記憶手段に格納するステップと、
前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索するステップと、
すでに取得された前記マップ情報が示すマップとは異なるマップを示す前記マップ情報が新たに取得される場合に、前記複数の部分領域のうちどの前記部分領域に変更があるかを判断するとともに、変更のある前記部分領域に対して1以上の前記代表点を再設定するステップと、
再設定される前記代表点を端点とする経路及びその距離を再演算するステップと、
を含むことを特徴とする経路探索方法。
【請求項12】
経路探索の対象となるマップを示すマップ情報を取得する手段、
前記マップ情報が示すマップ上に複数の部分領域を設定するとともに、前記各部分領域に対して1以上の代表点を設定する手段、
前記各代表点から、該代表点に係る前記部分領域に隣接する前記部分領域に対して設定される前記代表点のうち少なくとも1つへ、それら隣接する前記部分領域のみを通って至る経路、及びその距離を演算する手段、
演算される前記代表点間の経路及びその距離を記憶手段に格納する手段、
前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する手段、
すでに取得された前記マップ情報が示すマップとは異なるマップを示す前記マップ情報が新たに取得される場合に、前記複数の部分領域のうちどの前記部分領域に変更があるかを判断するとともに、変更のある前記部分領域に対して1以上の前記代表点を再設定する手段、及び
再設定される前記代表点を端点とする経路及びその距離を再演算する手段
としてコンピュータを機能させるためのプログラム。
【請求項1】
経路探索の対象となるマップを示すマップ情報を取得するマップ情報取得手段と、
前記マップ情報が示すマップ上に複数の代表点を設定する代表点設定手段と、
前記代表点間の経路及びその距離を演算する事前経路演算手段と、
前記事前経路演算手段により演算される前記代表点間の経路及びその距離を記憶する記憶手段と、
前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する経路探索手段と、を含み、
前記事前経路演算手段は、並列処理可能であってそれぞれ前記代表点のうち一部が関連づけられる複数のプロセッサを含み、前記各プロセッサは、該プロセッサに関連づけられる前記代表点から他の前記代表点への経路のうち少なくとも1つ及びその距離を並列に演算する、
ことを特徴とする経路探索装置。
【請求項2】
請求項1に記載の経路探索装置において、
前記代表点設定手段は、前記マップ情報が示すマップ上に複数の部分領域を設定するとともに、前記各部分領域に対して1以上の代表点を設定する、
ことを特徴とする経路探索装置。
【請求項3】
請求項2に記載の経路探索装置において、
前記事前経路演算手段に含まれる前記各プロセッサは、該プロセッサに関連づけられる前記代表点から、該代表点に係る前記部分領域に隣接する前記部分領域に対して設定される前記代表点のうち少なくとも1つへ、それら隣接する前記部分領域のみを通って至る経路及びその距離を演算する、
ことを特徴とする経路探索装置。
【請求項4】
請求項3に記載の経路探索装置において、
前記各部分領域は共通の矩形状をなし、
前記事前経路演算手段に含まれる前記各プロセッサは、該プロセッサに関連づけられる前記代表点から、該代表点に係る前記部分領域の直交するいずれかの2辺に接する前記部分領域に対して設定される前記代表点のうち少なくとも1つへ、それら前記部分領域のみを通って至る経路及びその距離を演算する、
ことを特徴とする経路探索装置。
【請求項5】
請求項2乃至4のいずれかに記載の経路探索装置において、
前記代表点設定手段は、すでに取得された前記マップ情報が示すマップとは異なるマップを示す前記マップ情報が前記マップ情報取得手段により取得される場合に、前記複数の部分領域のうちどの前記部分領域に変更があるかを判断するとともに、変更のある前記部分領域に対して1以上の前記代表点を再設定し、
前記事前経路演算手段は、再設定される前記代表点を端点とする経路及びその距離を再演算する、
ことを特徴とする経路探索装置。
【請求項6】
請求項1乃至5のいずれかに記載の経路探索装置において、
前記経路探索手段は、
前記始点の位置に応じて前記代表点のうち1つを選択するとともに、前記始点から該選択される代表点への経路を決定する第1経路決定手段と、
前記終点の位置に応じて前記代表点のうち1つを選択するとともに、該選択される代表点から前記終点への経路を決定する第2経路決定手段と、
前記記憶手段に記憶される経路及びその距離に基づいて、前記選択される代表点間の経路を決定する第3経路決定手段と、を含む、
ことを特徴とする経路探索装置。
【請求項7】
経路探索の対象となるマップを示すマップ情報を取得するマップ情報取得手段と、
前記マップ情報が示すマップ上に複数の部分領域を設定するとともに、前記各部分領域に対して1以上の代表点を設定する代表点設定手段と、
前記各代表点から、該代表点に係る前記部分領域に隣接する前記部分領域に対して設定される前記代表点のうち少なくとも1つへ、それら隣接する前記部分領域のみを通って至る経路、及びその距離を演算する事前経路演算手段と、
前記事前経路演算手段により演算される前記代表点間の経路及びその距離を記憶する記憶手段と、
前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する経路探索手段と、を含み、
前記代表点設定手段は、すでに取得された前記マップ情報が示すマップとは異なるマップを示す前記マップ情報が前記マップ情報取得手段により取得される場合に、前記複数の部分領域のうちどの前記部分領域に変更があるかを判断するとともに、変更のある前記部分領域に対して1以上の前記代表点を再設定し、
前記事前経路演算手段は、再設定される前記代表点を端点とする経路及びその距離を再演算する、
ことを特徴とする経路探索装置。
【請求項8】
請求項1乃至7のいずれかに記載の経路探索装置において、
前記距離は、該距離に係る経路上に設定されるコストに基づいて演算される、
ことを特徴とする経路探索装置。
【請求項9】
経路探索の対象となるマップを示すマップ情報を取得するマップ情報取得ステップと、
前記マップ情報が示すマップ上に複数の代表点を設定する代表点設定ステップと、
前記代表点間の経路及びその距離を演算する事前経路演算ステップと、
前記事前経路演算ステップで演算される前記代表点間の経路及びその距離を記憶手段に格納する格納ステップと、
前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する経路探索ステップと、を含み、
前記事前経路演算ステップは、並列処理可能であってそれぞれ前記代表点のうち一部が関連づけられる複数のプロセッサのそれぞれにより、該プロセッサに関連づけられる前記代表点から他の前記代表点への経路のうち少なくとも1つ及びその距離を並列に演算する、
ことを特徴とする経路探索方法。
【請求項10】
経路探索の対象となるマップを示すマップ情報を取得するマップ情報取得手段、
前記マップ情報が示すマップ上に複数の代表点を設定する代表点設定手段、
前記代表点間の経路及びその距離を演算する事前経路演算手段、
前記事前経路演算手段により演算される前記代表点間の経路及びその距離を記憶する記憶手段、及び
前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する経路探索手段
として、並列処理可能な複数のプロセッサを備えるコンピュータを機能させるためのプログラムであって、
前記各プロセッサにはそれぞれ前記代表点のうち一部が割り当てられ、前記事前経路演算手段は、前記各プロセッサにより、該プロセッサに関連づけられる前記代表点から他の前記代表点への経路のうち少なくとも1つ及びその距離を並列に演算する、
ことを特徴とするプログラム。
【請求項11】
経路探索の対象となるマップを示すマップ情報を取得するステップと、
前記マップ情報が示すマップ上に複数の部分領域を設定するとともに、前記各部分領域に対して1以上の代表点を設定するステップと、
前記各代表点から、該代表点に係る前記部分領域に隣接する前記部分領域に対して設定される前記代表点のうち少なくとも1つへ、それら隣接する前記部分領域のみを通って至る経路、及びその距離を演算するステップと、
演算される前記代表点間の経路及びその距離を記憶手段に格納するステップと、
前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索するステップと、
すでに取得された前記マップ情報が示すマップとは異なるマップを示す前記マップ情報が新たに取得される場合に、前記複数の部分領域のうちどの前記部分領域に変更があるかを判断するとともに、変更のある前記部分領域に対して1以上の前記代表点を再設定するステップと、
再設定される前記代表点を端点とする経路及びその距離を再演算するステップと、
を含むことを特徴とする経路探索方法。
【請求項12】
経路探索の対象となるマップを示すマップ情報を取得する手段、
前記マップ情報が示すマップ上に複数の部分領域を設定するとともに、前記各部分領域に対して1以上の代表点を設定する手段、
前記各代表点から、該代表点に係る前記部分領域に隣接する前記部分領域に対して設定される前記代表点のうち少なくとも1つへ、それら隣接する前記部分領域のみを通って至る経路、及びその距離を演算する手段、
演算される前記代表点間の経路及びその距離を記憶手段に格納する手段、
前記記憶手段に記憶される経路及びその距離に基づいて、所与の始点から所与の終点への経路を探索する手段、
すでに取得された前記マップ情報が示すマップとは異なるマップを示す前記マップ情報が新たに取得される場合に、前記複数の部分領域のうちどの前記部分領域に変更があるかを判断するとともに、変更のある前記部分領域に対して1以上の前記代表点を再設定する手段、及び
再設定される前記代表点を端点とする経路及びその距離を再演算する手段
としてコンピュータを機能させるためのプログラム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【公開番号】特開2009−281942(P2009−281942A)
【公開日】平成21年12月3日(2009.12.3)
【国際特許分類】
【出願番号】特願2008−135950(P2008−135950)
【出願日】平成20年5月23日(2008.5.23)
【出願人】(395015319)株式会社ソニー・コンピュータエンタテインメント (871)
【Fターム(参考)】
【公開日】平成21年12月3日(2009.12.3)
【国際特許分類】
【出願日】平成20年5月23日(2008.5.23)
【出願人】(395015319)株式会社ソニー・コンピュータエンタテインメント (871)
【Fターム(参考)】
[ Back to top ]