(57)【特許請求の範囲】
【請求項１】
コンピュータを、
仮想のゲーム空間内において、ゲームプレイヤが操作しないノンプレイヤキャラクタの移動開始位置と該ノンプレイヤキャラクタの移動の目標位置とするゲームプレイヤが操作するプレイヤキャラクタの位置とから、探索領域においてノンプレイヤキャラクタが経由可能な経由候補位置の配置を決定する決定手段、
前記決定手段によって配置を決定した経由候補位置に基づき、前記移動開始位置から前記目標位置までの経路を選択する経路選択手段、および
前記経路選択手段によって選択された経路にしたがって、前記ノンプレイヤキャラクタを前記目標位置に移動させるキャラクタ制御手段、として機能させるためのゲームプログラムであって、
前記決定手段は、記憶部から前記仮想ゲーム空間に対応した複数の経由候補位置の情報である探索経路情報を読み出し、この探索経路情報に基づいて、前記探索領域における前記プレイヤキャラクタの周辺領域である所定範囲に配される経由候補位置の間隔よりも、前記所定範囲外に配される経由候補位置の間隔の方が大きくなるように、前記探索領域の経由候補位置の配置を決定し、
前記経由候補位置は、相対的に細かい目を有する第１経由候補位置マップ情報と相対的に粗い目を有する第２経由候補位置マップ情報とに基づいて設定され、
前記ノンプレイヤキャラクタには、
前記所定範囲において前記第１経由候補位置マップ情報を用い、前記所定範囲外において前記第２経由候補位置マップ情報を用いて、前記探索領域の経由候補位置の配置が決定されるノンプレイヤキャラクタと、
前記第１経由候補位置マップ情報のみを用いて、前記探索領域の経由候補位置の配置が決定されるノンプレイヤキャラクタと、
が含まれる、ゲームプログラム。
【請求項２】
請求項１に記載のゲームプログラムを記憶したプログラム記憶部、及び、該プログラム記憶部に記憶されたゲームプログラムを実行するコンピュータ、を備えることを特徴とするゲームシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ノンプレイヤキャラクの移動開始位置から目標位置までの経路探索を行うゲームプログラム、及びゲームシステムに関する。
【背景技術】
【０００２】
従来のゲームでは、プレイヤが操作するプレイヤキャラクタ（これ以降、ＰＣと称する）が存在する仮想空間において、このＰＣが行動できる範囲を、障害物または透明な壁などで制限していた。また、遠景は舞台の書き割りのように描かれた絵により表現し、ＰＣはその遠景に描かれた空間には移動することができなかった。このため、プレイヤは、ゲーム体験上、閉塞感を抱くことがあった。
【０００３】
しかしながら近年では、ゲーム装置の有するハードウェアの性能向上やプログラム技術の進歩に伴い、より広く設計された仮想空間の世界を、ＰＣがシームレスに移動可能なゲームも提供されるようになってきている。このように設計された仮想空間は一般に「オープンワールド」と称される。
【０００４】
オープンワールドを採用したゲームでは、プレイヤからの移動操作に応じて、仮想空間を形成する地形データなどを随時読み込んで表示している。また、ＰＣが移動可能な仮想空間は、従来のオープンワールドではないゲームにて１回のロードデータにより表現し得る仮想空間よりも格段に広くなっている。そして、この広い仮想空間を、マップの切り替えやデータロードに伴う画面の静止や暗転を行うことなくシームレスに表現している。このため、オープンワールドに設計された仮想空間全体のデータ量は、従来のオープンワールドではないゲームにてロードされる仮想空間のデータ量よりも、格段に大きくなる。そこで、オープンワールドの仮想空間については、ＰＣの移動に伴ってその周辺領域に関してのみ地形データをロードし、この周辺領域に関してのみ、仮想カメラによって撮影された仮想空間の二次元画像を表示させるなどして、データの処理量を低減する工夫をしている。
【０００５】
ところで、オープンワールドのゲームでは、ＰＣの周辺領域以外であっても、すなわち仮想カメラによる撮影範囲外であってＰＣが直接関与していない仮想空間においても、プレイヤが操作しないノンプレイヤキャラクタ（これ以降、ＮＰＣと称する）を自立して行動させることができる。例えば、ＰＣの周辺領域以外の仮想空間に存在するＮＰＣがＰＣを目指して移動するようにゲームを設計することができる。
【０００６】
このようにＮＰＣがＰＣを目指して移動する場合、これらＮＰＣ及びＰＣが含まれる探索領域を設定し、目標位置（ＰＣの位置）までの経路探索を行い、この探索結果にしたがってＮＰＣは移動することとなる。このように経路探索を行って移動開始位置から目標位置までＮＰＣを移動させる技術としては、例えば、特許文献１および特許文献２などが挙げられる。
【０００７】
すなわち、特許文献１では、ＮＰＣの移動をより自然に見せるためにメッシュデータなどの経由地点（経由候補位置）に関する情報を用いて、所定のアルゴリズムにより経路を探索し、決定することができるプログラムが開示されている。また、特許文献２には、予め記憶されているルートの中から、現在位置および目的位置に応じて最短ルートを選択することができるゲーム装置が開示されている。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２０１０−６８８７２号公報
【特許文献２】特許第３５２００６９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
通常、ゲームの仮想空間において経路探索を行う場合、移動開始位置から目標位置までの距離が遠くなればなるほど探索に係る処理負荷が増大する。特に、上述したオープンワールドのゲームでは、ＮＰＣが移動可能な仮想空間が広く、移動開始位置から目標位置までの距離が大きくなり得るため、探索に係るコンピュータの処理負荷の増大は顕著となり、ゲームを製作するにあたり大きな問題となる。これは、上述した特許文献１，２に記載の発明においても同様であり、仮想空間において移動開始位置から目標位置までの距離が大きくなるにつれ、経路の探索に係る処理負荷が増大するという問題が生じる。また、プレイヤがゲーム画面上で見てＮＰＣの動きに不自然さを感じないようにするためには、ＮＰＣが経由可能な経由候補位置に関して細かく設定する必要があるが、設定される経由候補位置の増大は経路探索に係る処理負荷をますます増大させてしまう。
【００１０】
本発明は、上記の問題点に鑑みてなされたものであり、その目的は、ノンプレイヤキャラクタの移動を自然に見せつつ、ゲームの仮想空間において移動開始位置から目標位置までの距離が大きくなっても、その間の経路探索に係る処理負荷の増大を抑制することができる、ゲームプログラム、及びコンピュータ装置を提供することである。
【課題を解決するための手段】
【００１１】
本発明に係るゲームプログラムは、上記した課題を解決するために、コンピュータを、仮想のゲーム空間内において、ゲームプレイヤが操作しないノンプレイヤキャラクタの移動開始位置と該ノンプレイヤキャラクタの移動の目標位置とから、探索領域においてノンプレイヤキャラクタが経由可能な経由候補位置の配置を決定する決定手段、前記決定手段によって配置を決定した経由候補位置に基づき、前記移動開始位置から前記目標位置までの経路を選択する経路選択手段、および前記経路選択手段によって選択された経路にしたがって、前記ノンプレイヤキャラクタを前記目標位置に移動させるキャラクタ制御手段、として機能させるためのゲームプログラムであって、前記決定手段は、記憶部から前記仮想ゲーム空間に対応した複数の経由候補位置の情報である探索経路情報を読み出し、この探索経路情報に基づいて、前記探索領域の所定範囲に配される経由候補位置の間隔よりも、前記所定範囲外に配される経由候補位置の間隔の方が大きくなるように、前記探索領域の経由候補位置の配置を決定する。
【００１２】
上述のように本発明に係るゲームプログラムでは、コンピュータを前記決定手段、前記経路選択手段、前記キャラクタ制御手段として機能させることができるため、ノンプレイヤキャラクタを現在位置から目標位置まで適切な経路で移動させることができる。
【００１３】
さらにまた、前記探索経路情報に基づき決定手段により決定される経由候補位置の配置では、所定範囲外の方が所定範囲内よりも各経由候補位置の間隔が大きくなる。このため、所定範囲外では、ノンプレイヤキャラクタを移動させる経路を選択する際（経路探索時）に考慮すべき経由候補位置の数（すなわち考慮すべき情報）が、所定範囲内よりも少なくなる。従って、同じスケールでの経路探索に係る処理量を低減することができる。逆に所定範囲内では、各経由公報位置の間隔を小さく、すなわち密にすることができ、ノンプレイヤキャラクタの移動経路をより細かく規定することができる。このため、例えば、自然な描画を要求される範囲を所定範囲と一致させれば、プレイヤは、ノンプレイキャラクタの動きに不自然さを感じることがない。
【００１４】
ここで、移動開始位置から目標位置までの距離にかかわらず上記所定範囲をほぼ一定面積とすると、前記距離が大きくなればなるほど、探索領域においてこの所定範囲外の領域が占める割合が大きくなる。そして、この所定範囲外では経路探索時の演算処理量が所定範囲内よりも小さい。したがって、ノンプレイヤキャラクタの移動を自然に見せつつ、ゲームの仮想空間において移動開始位置から目標位置までの距離が大きくなっても、その間の経路探索に係る処理負荷の増大を抑制することができるという効果を奏する。
【００１５】
さらには、上記所定範囲をノンプレイヤキャラクタの移動が画面において不自然に見えない範囲で、できるだけ小さく設定すればするほど探索処理に必要なデータ量を低減させることができるため、メモリに記憶させるデータ量を低減させることができる。
【００１６】
また、前記所定範囲は、少なくとも仮想的なカメラにより写し出されたゲーム空間の範囲の一部を含んでいる。
【００１７】
このため、仮想的なカメラにより写し出されるゲーム空間において、ノンプレイヤキャラクタの移動を所定範囲外よりも設置間隔が小さい経由候補位置により規定することができる。したがって、仮想的なカメラにより写し出された画像において、ノンプレイヤキャラクタが移動する経路をより細かく規定し、より自然な移動態様を表現できる。
【００１８】
さらにまた、前記仮想的なカメラにより写し出されたゲーム空間の画像を描画する描画手段をさらに備え、前記ゲーム空間は、少なくとも前記描画手段により精細な画像が形成される第１範囲と、前記描画手段により該第１範囲の画像よりも相対的に粗い画像が形成される第２範囲とに分けられており、前記所定範囲は、前記ゲーム空間の前記第１範囲と一致してもよい。
【００１９】
また、本発明に係るゲームプログラムは、前記探索経路情報は、第１探索経路情報と、該第１探索経路情報よりも経由候補位置の間隔が大きい第２探索経路情報とを含でおり、前記決定手段は、前記所定範囲については前記第１探索経路情報を用いて経由候補位置の配置を決定し、前記所定範囲外については前記第２探索経路情報を用いて経由候補位置の配置を決定してもよい。
【００２０】
また、本発明に係るゲームシステムは、上記したゲームプログラムを記憶したプログラム記憶部、及び、該プログラム記憶部に記憶されたゲームプログラムを実行するコンピュータ、を備えることを特徴とする。
【００２１】
したがって、本発明に係るゲームシステムは、ゲームの仮想空間において移動開始位置から目標位置までの距離が大きくなっても、その間の経路探索に係る処理負荷の増大を抑制することができるという効果を奏する。
【発明の効果】
【００２２】
本発明は以上に説明したように構成され、ノンプレイヤキャラクタの移動を自然に見せつつ、ゲームの仮想空間において移動開始位置から目標位置までの距離が大きくなっても、その間の経路探索に係る処理負荷の増大を抑制することができるゲームプログラム及びゲームシステムを提供することができるという効果を奏する。
【図面の簡単な説明】
【００２３】
【図１】本発明の実施の形態に係るゲーム装置の要部構成の一例を示すブロック図である。
【図２】図１に示すゲーム装置の機能的な構成の一例を示すブロック図である。
【図３】本実施の形態に係るゲーム空間を周辺描画領域と外周描画領域とに区分けした一例を示す図である。
【図４】本実施の形態に係るゲーム空間の探索領域を所定領域と外周領域とに区分けした一例を示す図である。
【図５】図４に示すゲーム空間の探索領域において経由候補点を設定する一例を示す図である。
【図６】図１に示すゲーム装置における経路探索処理の一例を示すフローチャートである。
【図７】図４に示すゲーム空間の探索領域において経由候補点を設定する一例を示す図である。
【図８】図４に示すゲーム空間の探索領域において経由候補点を設定する一例を示す図である。
【発明を実施するための形態】
【００２４】
以下、本発明の実施の形態に係るゲームプログラム及びコンピュータ装置について、図面を参照しつつ説明する。
【００２５】
本実施の形態に係るゲーム装置（ゲームシステム）１は、ディスク型記録媒体３０からゲームプログラム３０ａ及びゲームデータ３０ｂを読み出し、プレイヤにより入力された操作を処理して、その結果として出力を行うことでゲームを実行するものである。
【００２６】
本実施形態では、ゲーム装置１により実行されるゲームとしてプレイヤキャラクタがプレイヤからの操作指示に応じて、舞台となるゲーム空間６０の世界を自由に動き回り、アイテムを探索したり、ミッションを攻略したりできる、オープンワールドのゲームを例に挙げて説明するものとする。
【００２７】
（ゲーム装置）
まず、本実施の形態に係るゲーム装置１について説明する。図１は、本発明の実施の形態に係るゲーム装置（コンピュータ装置）１の要部構成の一例を示すブロック図である。図１に示すように、ゲーム装置１は、その動作を制御するＣＰＵ２を備え、このＣＰＵ２にはバス３を介してディスクドライブ４、メモリカードスロット５、ＨＤＤ６、ＲＯＭ７、及びＲＡＭ８が接続されている。
【００２８】
ディスクドライブ４には、ＤＶＤ−ＲＯＭ等のディスク型記録媒体３０が装填される。そしてこのディスク型記録媒体３０には、ゲームプログラム３０ａ、及びゲームデータ３０ｂが記憶される。このゲームデータ３０ｂには、ゲームに登場するキャラクタ等を含むゲーム空間６０を形成するのに必要な画像データ３２と、地形データ３３が含まれる。なお、地形データ３３はゲーム空間６０内を表示するための地形に係る情報（例えば、ゲーム空間中におけるどの領域が舗装道路、砂地、沼地、水辺等であるかを示す情報、障害物等のオブジェクトの配置を示す情報、ゲーム空間中に設定されている座標情報など）と、詳細は後述するが経路探索処理における探索領域６９の設定に係る情報とを含む。
【００２９】
メモリカードスロット５には、カード型記録媒体３１が装填されるようになっており、ゲーム本編の途中経過等のプレイ状況を示すセーブデータを、ＣＰＵ２からの指示に応じて記録することができる。
【００３０】
ＨＤＤ６は、ゲーム装置１が内蔵する大容量記録媒体であって、ディスク型記録媒体３０から読み込んだゲームプログラム３０ａ及びゲームデータ３０ｂ、ゲームの進行経過を記録したセーブデータ等を記録しておくことができる。
【００３１】
ＲＯＭ７は、マスクＲＯＭ又はＰＲＯＭなどの半導体メモリであり、ゲーム装置１を起動する起動プログラムや、ディスク型記録媒体３０が装填されたときの動作を制御するプログラムなどを記録する。
【００３２】
ＲＡＭ８は、ＤＲＡＭ又はＳＲＡＭなどから成り、ＣＰＵ２が実行するべきゲームプログラム３０ａ、及びその実行の際に必要になるゲームデータ３０ｂなどを、ゲームのプレイ状況に応じてディスク型記録媒体３０又はＨＤＤ６から読み込んで一時的に記録する。例えば、本ゲームのディスク型記録媒体３０がディスクドライブ４に装填されると、ＣＰＵ２は、ゲームプログラム３０ａ及びゲームデータ３０ｂをＲＡＭ８に読み込み、本ゲームのタイトルが表記されたタイトル画面またはメニュー画面などの表示を行うように制御する。そして、このメニュー画面などの表示に基づきプレイヤがコントローラ１８を操作してゲームの開始を指示すると、ＣＰＵ２が該指示に応じてゲームプログラム３０ａ、ゲームデータ３０ｂを実行しゲームが開始する。
【００３３】
さらにまた、ＣＰＵ２にはバス３を介してグラフィック処理部１１、オーディオ合成部１４、無線通信制御部１７、及びネットワークインタフェース１９が接続されている。
【００３４】
グラフィック処理部１１は、ＣＰＵ２の指示に従って各場面に応じたゲーム空間６０や該ゲーム空間６０でのキャラクタ等の動作などを含むゲーム画像を描画する。グラフィック処理部１１にはビデオ変換部１２を介して外部のモニタ１３が接続されており、グラフィック処理部１１は、描画したゲーム画像の画像データ（ゲーム画像データ）をビデオ変換部１２に出力する。
【００３５】
ビデオ変換部１２は、グラフィック処理部１１からゲーム画像データを受け取ると、このゲーム画像データをモニタ１３に表示可能な動画形式に変換する。
【００３６】
オーディオ合成部１４は、ＣＰＵ２の指示に従ってデジタルのゲーム音声を再生及び合成する。また、オーディオ合成部１４にはオーディオ変換部１５を介してスピーカ１６が接続されている。従って、オーディオ合成部１４にて再生及び合成されたゲーム音声は、オーディオ変換部１５にてアナログ形式にデコードされ、更にスピーカ１６から外部へ出力される。
【００３７】
無線通信制御部１７は、例えば、２．４ＧＨｚ帯の無線通信モジュールを有しており、該無線通信モジュールによりゲーム装置１とそれに付属するコントローラ１８との間で無線による接続を確立する。そして、接続を確立すると、無線通信制御部１７は、ゲーム装置１とコントローラ１８との間でデータの送受信を行う。プレイヤは、コントローラ１８に設けられたボタン等の操作子（図示せず）を操作することにより、ゲーム装置１へ信号を入力する。そして、この入力された信号によりモニタ１３に表示されるプレイヤキャラクタの動作を制御する。
【００３８】
ネットワークインタフェース１９は、インターネットやＬＡＮなどの通信ネットワーク２０に対してゲーム装置１を接続し、他のゲーム装置１との間でクライアント・サーバ方式又はピア・ツー・ピア方式による通信を行う。そして、ゲーム装置１を、通信ネットワーク２０を介して他のゲーム装置１と接続し、互いにデータを送受信することにより、同一のゲーム空間６０内で同期して各プレイヤキャラクタを動作させることができ、複数人が共同してゲームを進行させるマルチプレイが可能になる。
【００３９】
（ゲーム装置の機能的な構成）
次に、ゲーム装置１に係る機能的な構成について図２を参照して説明する。図２は、図１に示すゲーム装置１の機能的な構成の一例を示すブロック図である。なお、図２では、以下で行う説明上必要な、ＲＡＭ８に読み込んだゲームプログラム３０ａを実行することでＣＰＵ２により実現できる機能と、該機能に直接かかわるハードウェア要素（グラフィック処理部１１、無線通信制御部１７）についてのみ記載しており、他の構成要素は省略している。
【００４０】
図２に示すように、ゲーム装置１は、機能的な構成として、仮想ゲーム空間生成部４１、キャラクタ動作制御部（キャラクタ制御手段）４２、ゲーム進行制御部４３、経路探索部（経路選択手段）４４、および探索領域設定部（決定手段）４５を備える。なお、このような各機能は、上述したように、ＣＰＵ２がディスク型記録媒体３０からゲームプログラム３０ａをＲＡＭ８に読み出し、実行することで実現できる。
【００４１】
仮想ゲーム空間生成部４１は、グラフィック処理部１１を制御して、プレイヤキャラクタが行動するゲーム空間６０を描画するためのゲーム画像データを、適宜、ゲームデータ３０ｂの画像データ３２および地形データ３３を用いて生成する。なお、仮想ゲーム空間生成部４１によるゲーム空間５０の描画処理に関する詳細は後述する。
【００４２】
キャラクタ動作制御部４２は、プレイヤによるコントローラ１８からの入力信号に応じて、又はゲームの進行状況に応じて、ゲーム空間６０におけるキャラクタ等の動作に関する制御情報を生成する。例えば、本実施形態のゲームでは、敵ノンプレイヤキャラクタ（敵ＮＰＣ）５１がＰＣ５０に向かって移動するように設定されている（図４参照）。そこで、キャラクタ動作制御部４２は、ＰＣ５０のゲーム空間６０における位置に応じて、敵ＮＰＣ５１がＰＣ５０に向かって移動するための制御情報を生成する。なお、敵ＮＰＣ５１がＰＣ５０に向かって移動する際の移動経路の決定は、後述する経路探索部４４および探索領域設定部４５による経路探索処理結果に基づき行う。
【００４３】
キャラクタ動作制御部４２は制御情報を生成すると、この制御情報をグラフィック処理部１１に出力する。グラフィック処理部１１は、キャラクタ動作制御部４２から受け取った制御情報と、仮想ゲーム空間生成部４１からの指示とに応じてゲーム画像データに基づく描画を行う。なお、キャラクタ動作制御部４２は、無線通信制御部１７を介して、コントローラ１８からの入力信号を受け取り、また、後述するゲーム進行制御部４３からゲームの進行状況に関する情報を受け取る。
【００４４】
ゲーム進行制御部４３は、ゲームデータ３０ｂの地形データ３３およびゲームプログラム３０aを参照してＰＣ５０等のキャラクタのゲーム空間６０における位置を記録する。さらにまた、ゲーム進行制御部４３は、ＰＣ５０の行動およびゲーム空間６０における位置等に応じて、新たなキャラクタの出現タイミング、およびその種類を決定し、イベント、またはミッション等の発生タイミング、およびその種類を決定する。さらにまた、ゲーム進行制御部４３は、ゲームの進行状況を管理し、プレイヤからのゲーム中断指示を、無線通信制御部１７を通じて受信すると、現時点までのゲームの経過情報をセーブデータとしてＨＤＤ６またはカード型記録媒体３１に記憶する。
【００４５】
経路探索部４４は、キャラクタ動作制御部４２からの指示に応じて、ゲーム空間６０内にある敵ＮＰＣ５１をＰＣ５０に向かって移動させるための移動経路を探索する。経路探索部４４は、ゲーム進行制御部４３から、ＰＣ５０のゲーム空間６０における現在位置を示す情報と、移動させる敵ＮＰＣ５１のゲーム空間６０における現在位置を示す情報を受け取る。そして、この受け取ったそれぞれの現在位置を示す情報と、後述する探索領域設定部４５から受信した探索領域情報とに基づき敵ＮＰＣ５１のＰＣ５０までの移動経路を求める。そして、経路探索部４４は、求めた移動経路を探索処理結果としてキャラクタ動作制御部４２に出力する。
【００４６】
探索領域設定部４５は、経路探索部４４からの指示に応じて、ゲーム空間６０の探索領域６９中に経由候補位置を示すノードを配した探索領域情報を生成する。なお、この探索領域情報の生成に関する詳細な説明は後述する。
【００４７】
（描画処理）
次に、図３を参照して、ゲーム装置１が備える仮想ゲーム空間生成部４１によるゲーム画面の描画処理に関する概要を説明する。図３は、本実施の形態に係るゲーム空間６０を周辺描画領域６１と外周描画領域６２とに区分けした一例を示す図である。
【００４８】
本実施の形態に係るゲームでは、図３に示すように、ゲーム空間６０全体をＰＣ５０の現在位置を含む周辺描画領域（第１範囲）６１と、該周辺描画領域６１の外周に位置する領域である外周描画領域（第２範囲）６２とに分けている。
【００４９】
本実施の形態において、この周辺描画領域６１は、ＰＣ５０の周囲の３次元空間や該３次元空間中に配されるオブジェクト等を精細に描画する領域である。一方、外周描画領域６２は、周辺描画領域６１外に配されるオブジェクト等やそのオブジェクト等が存在する３次元空間を粗く描画する領域である。
【００５０】
そして、実際のゲーム実行画面では、ＰＣ５０の視線方向に見た周辺描画領域６１に含まれるオブジェクト、および該オブジェクトが存在する３次元空間を、精細に描画した２次元画像として表示する。一方、ＰＣ５０の視線方向に見た外周描画領域６２は、周辺描画領域６１よりも粗く描画された２次元画像として表示する。
【００５１】
すなわち、外周描画領域６２にあるオブジェクト等はＰＣ５０（または、仮想カメラ）から見て周辺描画領域６１にあるオブジェクト等よりも遠くにあるため、小さく描画される。このため、外周描画領域６２にあるオブジェクト等を精細に描いた場合と粗く描いた場合とを比較しても、モニタ１３を通じてプレイヤが視認できる情報量に大差がない。そこで、外周描画領域６２にあるオブジェクト等については周辺描画領域６１よりも粗く描画して描画に係るデータ量を削減するように設計されている。
【００５２】
より具体的には、仮想ゲーム空間生成部４１は、以下のようにして外周描画領域６２におけるオブジェクト等の描画を行う。例えば、描画対象を３Ｄゲームに登場するキャラクタとした場合、該キャラクタは実在の人間のようにその内部に骨を仕込み、アクション時はこの骨を動かし、外皮頂点を変形させるように描画している。外周描画領域６２にいるキャラクタについてはこの骨数を削減し、キャラクタの動きに対応する描画情報を低減させる。もしくは、つま先など体の一部であって遠方からは視認することが困難な部位などは描画しないように設定されていてもよい。
【００５３】
なお、本実施の形態に係るゲーム装置１では、仮想ゲーム空間生成部４１がゲーム空間６０を描画するために必要な画像データ３２および地形データ３３などを随時読み込み、上述した周辺描画領域６１と外周描画領域６２とにおいて異なる精細さで描画されたゲーム画像を表示する。
【００５４】
ここで、この周辺描画領域６１と外周描画領域６２との境界は、ゲーム空間６０におけるＰＣ５０の現在位置からの一定範囲となるように決められていてもよい。あるいは、ＰＣ５０が位置する地形、ＰＣ５０が存在するゲーム空間６０を映し出す仮想カメラの立脚点または注視点等に応じてその境界が決められるように設定されていてもよい。
【００５５】
例えば、地上と水中では当然、視界は異なるものとなるため、ＰＣ５０がいる位置が水中の場合は、この周辺描画領域６１の範囲を地上よりも小さくする。また、例えば、仮想カメラの立脚点が崖などの標高の高い位置にあり、地上にいる場合よりも遠方まで見渡すことができる場合は、周辺描画領域６１の範囲を地上よりも大きくする。また、例えば、仮想カメラの注視点位置（焦点位置）に重要でかつ強調したい情報がある場合は、注視点がある近傍の描画を精細とするように、周辺描画領域６１の一部を広げてもよい。
【００５６】
周辺描画領域６１と外周描画領域６２との境界を、ＰＣ５０が位置する地形、仮想カメラの立脚点または注視点等に応じて決めるように設定されている方が、ＰＣ５０を取り巻く環境に応じて適切な精細度（または、解像度）で描画することができるため好適である。
【００５７】
なお、上述した周辺描画領域６１の範囲および外周描画領域６２の範囲の決定は仮想ゲーム空間生成部４１が行う。また、ゲームデータ３０ｂには、予め、精細な描画用のゲーム画像データと粗い描画用のゲーム画像データが用意されている。そして、仮想ゲーム空間生成部４１は、決定した周辺描画領域６１の範囲、外周描画領域６２の範囲に応じて、精細な描画用のゲーム画像データを利用するのか、あるいは粗い描画用のゲーム画像データを利用するのかを、グラフィック処理部１１に指示する。
【００５８】
上述のようにゲームデータ３０ｂに精細な描画用の画像データ３２と粗い描画用の画像データ３２とが用意され、描画する範囲に応じてこれらを使い分ける構成であったがこれに限定されるものではない。例えば、ゲームデータ３０ｂには精細な描画用の画像データ３２のみが記録されており、この画像データ３２から粗い描画用の画像データ３２を仮想ゲーム空間生成部４１が生成する構成であってもよい。
【００５９】
また、本実施の形態に係るゲームでは、ゲーム空間６０を周辺描画領域６１と外周描画領域６２との２つの領域に分ける構成であるが、分ける領域はこの２つの限定されるものではない。例えば、描画する精細さを複数段階に分け、それぞれの段階に応じた領域を設ける構成であってもよい。
【００６０】
また、本実施形態では、外周描画領域６２内に１つの周辺描画領域６１が存在する例を示しているがこれに限定されない。例えば、周辺描画領域６１は、外周描画領域６２内に複数あってもよい。
【００６１】
（経路探索処理）
次に、敵ＮＰＣ５１がＰＣ５０に向かって移動する場合における、敵ＮＰＣ５１の移動に係る経路探索処理について説明する。本実施の形態に係るゲームでは、ゲームの進行状態に応じて、キャラクタ動作制御部４２がゲーム空間６０に存在する敵ＮＰＣ５１それぞれについてのＰＣ５０までの移動を制御する。キャラクタ動作制御部４２は、敵ＮＰＣ５１の移動を制御するにあたり、探索領域６９におけるＰＣ５０までの移動経路を経路探索部４４に求めるように指示する。この指示に応じて経路探索部４４が、探索領域６９における敵ＮＰＣ５１それぞれのＰＣ５０までの移動経路を求める。
【００６２】
（探索領域）
まず、ここで図５および図４を参照して本実施形態に係る探索領域６９について説明する。図４は、本実施の形態に係るゲーム空間６０の探索領域６９を所定領域６３と外周領域６４とに区分けした一例を示す図である。また、図５は、図４に示すゲーム空間６０の探索領域６９において経由候補点６５を設定する一例を示す図である。図５に示す例では、説明の便宜上、移動経路上の経由候補点６５を黒丸により強調して表示している。
【００６３】
探索領域６９は、図４に示すように、ＰＣ５０の現在地を基準に、ＰＣ５０の周辺領域である所定領域（所定範囲）６３と、該所定領域６３外の領域である外周領域（所定範囲外）６４とに区分けされる。本実施形態に係るゲームでは、所定領域６３を上述した周辺描画領域６１に一致させ、探索領域６９をゲーム空間６０の範囲に一致させている。但し、これに限定されるものではなく、必ずしもこれら両者が一致する必要はない。すなわち、探索領域６９は、少なくとも敵ＮＰＣ５１が移動可能なゲーム空間６０の範囲に対応していればよく、探索領域６９が必ずしもゲーム空間６０と一致する必要はない。例えば、敵ＮＰＣ５１がゲーム空間６０における陸地の範囲でしか行動ができない場合、探索領域６９は、ゲーム空間６０における陸地の範囲に限定されてもよい。
【００６４】
また、探索領域６９では、図５に示すように、敵ＮＰＣ５１が移動する地面または床面などの面に、複数の三角形の格子で構成されるメッシュが設定されている。ただし、探索領域６９では図５に示すように障害物領域６６a、６６ｂは避けてメッシュが設定される。また、例えば、三角形の格子の各辺の中央位置を、移動経路を設定する上での敵ＮＰＣ５１の経由候補点（ノード）６５とする。
【００６５】
探索領域６９では所定領域６３よりも外周領域６４の方が、経由候補位置の配置を規定する各格子（メッシュの目）の大きさが大きくなるように設定される。つまり、ゲームデータ３０ｂの地形データ３３には、経路探索処理における探索領域６９の設定に係る情報が含まれている。この探索領域６９の設定に係る情報は、具体的には各メッシュの目の大きさがより小さい精細なメッシュについての情報（第１経由候補位置マップ情報）と、各メッシュの目の大きさがより大きい粗いメッシュについての情報（第２経由候補位置マップ情報）とを含んでいる。そこで、ゲーム装置１では、探索領域設定部４５が、第１経由候補位置マップ情報を利用して、所定領域６３に精細なメッシュの設定を行い、第２経由候補位置マップ情報を利用して、外周領域６４に粗いメッシュの設定を行う。本実施形態では、第１経由候補位置マップ情報の範囲は、所定領域６３であるのに対して第２経由候補位置マップ情報の範囲は、所定領域６３および外周領域６４を含む探索領域６９全体となる。
【００６６】
なお、本実施形態では、後述するように、第２経由候補位置マップ情報利用して所定領域６３および外周領域６４に粗いメッシュの設定を行っているが、実際は所定領域６３内では粗いメッシュで求めた移動経路にしたがって敵ＮＰＣ５１の移動は行われない。したがって、第２経由候補位置マップ情報を利用して、外周領域６４に粗いメッシュの設定を行うことと実質的に同一となる。
【００６７】
このように、所定領域６３と外周領域６４とでは各格子の大きさが異なるメッシュが設定される。このため、同一距離を敵ＮＰＣ５１が進むとしても、外周領域６４を進む場合の方が所定領域６３を進む場合よりも、考慮すべき経由候補点６５の数を大きく削減できる。
【００６８】
（経路探索処理の処理フロー）
次に、図６を参照して敵ＮＰＣ５１がＰＣ５０へ向かう際の移動経路を決定する経路探索処理の処理フローについて説明する。この経路探索処理は、本実施形態では経路探索部４４および探索領域設定部４５によって実行される。図６は、図１に示すゲーム装置１における経路探索処理の一例を示すフローチャートである。なお、説明の便宜上、移動する敵ＮＰＣ５１は１体であるものとするが、実際のゲームでは移動する敵ＮＰＣ５１はこの１体に限定されるものではなく複数体であってもよい。図６に示す経路探索処理は、例えば毎フレーム実行される。例えば、６０ｆｐｓのフレームレートで描画の更新が行なわれる場合では１／６０秒ごとに経路探索処理を実行することとなる。
【００６９】
まず、探索領域設定部４５は、経路探索部４４からの指示に応じて、探索領域６９において求める移動経路の始点６７と終点６８とを設定する（ステップＳ１１）。より具体的には、探索領域設定部４５は、経路探索部４４を介してゲーム進行制御部４３からＰＣ５０および敵ＮＰＣ５１の現在位置に関する情報を受け取る。そして、この受け取った情報に基づき、移動させる敵ＮＰＣ５１の現在位置を始点（移動開始位置）６７とし、ＰＣ５０の位置を終点（目標位置）６８として設定する。
【００７０】
このように移動経路の始点６７と終点６８とを設定すると、探索領域設定部４５は、探索領域６９において、ＰＣ５０の周辺領域である所定領域６３と、この所定領域６３外の領域である外周領域６４とのそれぞれの範囲について決定する。そして、探索領域設定部４５は、所定領域６３の範囲に精細なメッシュを、第１経由候補位置マップ情報に基づき設定する。一方、所定領域６３および外周領域６４の範囲に粗いメッシュを、第２経由候補位置マップ情報に基づいて設定する（ステップＳ１２）。
【００７１】
探索領域設定部４５は、所定領域６３と外周領域６４との両者の領域の範囲を決定すると、ゲームデータ３０ｂにおける地形データ３３を参照して、探索領域６９のうち、障害物領域６６ａ、６６ｂの設定を行う（ステップＳ１３）。この障害物領域６６ａ、６６ｂとは、障害物オブジェクトが配される領域であり敵ＮＰＣ５１が侵入することができない（移動不可の）領域である。図５に示す例では、この障害物領域６６ａ、６６ｂは塗りつぶされた領域として示される。
【００７２】
そして、探索領域設定部４５は、このように探索領域６９に障害物領域６６ａ、６６ｂ、および敵ＮＰＣ５１の移動における始点６７および終点６８を設定するとともに、所定領域６３と外周領域６４とに区分けした探索領域６９の情報（探索領域情報）を経路探索部４４に送信する。
【００７３】
経路探索部４４は、探索領域設定部４５から受信した探索領域情報に基づき、敵ＮＰＣ５１の移動経路を求める。すなわち、図５に示す例では、２つの移動不可領域（障害物領域６６ａ、６６ｂ）を避けて、近接する経由候補点６５を伝いながら始点６７から終点６８までを最短距離で結ぶ移動経路を求める。本実施形態では、経路探索部４４は、Ａ＊（エースター）アルゴリズムを利用して移動経路の算出を行う。
【００７４】
具体的には、経路探索部４４は、始点６７から終点６８まで、まず粗いメッシュに配置された経由候補点６５に基づき、Ａ＊アルゴリズムを利用して移動経路を選択する（ステップＳ１４）。次に、経路探索部４４は、選択した移動経路において、ＮＰＣ５１が現在、到達している位置に対応する経由候補点６５、すなわち現在到達ノードと、次に移動する位置に対応する経由候補点６５、すなわち次ノードとが共に所定領域６３内にあるか否か判定する（ステップＳ１５）。ここで、両ノードが所定領域６３内にある場合（ステップＳ１５において「ＹＥＳ」）、経路探索部４４は、終点６８までの移動経路を、精細なメッシュに配置された経由候補点６５に基づき、Ａ＊アルゴリズムを利用して移動経路を再度、設定し、その設定した移動経路に決定する（ステップＳ１６）。一方、ステップＳ１５において「ＮＯ」の場合、すなわち、少なくとも現在到達ノードと次ノードとのいずれか一方が所定領域６３内に存在しない場合、ステップＳ１４で粗いメッシュを用いて選択した移動経路に決定する（ステップＳ１７）。
【００７５】
例えば、外周領域６４にある始点６７から所定領域６３内にある終点６８まで移動する場合、経路探索部４４は、敵ＮＰＣ５１が外周領域６４に存在する間は大きい格子が配された粗いメッシュの経由候補点６５を使って大雑把な移動経路を求めておく。そして、敵ＮＰＣ５１が所定領域６３内まで移動すると、小さい格子が配された精細なメッシュの経由候補点６５を使って細かい移動経路を、再度求める。
【００７６】
逆に、例えば、敵ＮＰＣ５１がＰＣ５０の近傍を始点とし、外周領域６４の任意の点を終点として移動する場合、つまり、敵ＮＰＣ５１がＰＣ５０から離れていく動きをする場合は以下のように敵ＮＰＣ５１の移動経路を求める。すなわち、経路探索部４４は、まず、現在位置から外周領域６４の任意の点まで、まず大きい格子が配された粗いメッシュの経由候補点６５を使って大雑把な移動経路を求めておく。そして、敵ＮＰＣ５１が所定領域６３内に存在する間は移動経路を小さい格子が配された精細なメッシュの経由候補点６５を使って求める。そして、敵ＮＰＣ５１の移動経路における次の経由候補点（次ノード）６５が外周領域６４に存在する位置まで該敵ＮＰＣ５１が移動すると、事前に粗いメッシュの経由候補点６５を使って求めた移動経路を選択して、該移動経路にしたがって移動する。なお、ここでは、外周領域６４から所定領域６３に敵ＮＰＣ５１が移動する場合、あるいは、逆に所定領域６３から外周領域６４に移動する場合について説明した。しかしながら、移動経路の途中において、所定領域６３を通過するように敵ＮＰＣ５１が移動するような場合であっても、敵ＮＰＣ５１の現在到達ノードを示す経由候補点６５と次ノードを示す経由候補点６５との位置関係から、所定領域６３内では精細なメッシュの経由候補点６５を使って移動経路を求めることができる。
【００７７】
また、図５に示すように移動経路では所定領域６３よりも外周領域６４の方が経由候補点６５の間隔が大きく、ゲーム空間６０において同一距離で考慮すべき経由候補点６５の数が所定領域６３よりも少ない。このため、外周領域６４では所定領域６３よりも細かい移動経路の指定はできないため敵ＮＰＣ５１の動きは所定領域６３内での動きよりも大雑把なものとなる。しかしながら、外周領域６４の範囲は、外周描画領域６２の範囲であり敵ＮＰＣ５１の動きが大雑把であってもゲーム画面を視認しているプレイヤ自身は不自然に感じることがないため、描画において問題とならない。
【００７８】
一方、周辺描画領域６１に対応する所定領域６３では経由候補点６５は、外周領域６４よりも間隔が小さく、敵ＮＰＣ５１の細かい動きを指定することができる。したがって、周辺描画領域６１の範囲では敵ＮＰＣ５１は自然な動き（移動態様）でＰＣ５０に接近してくるシーンを描画することができる。
【００７９】
また、外周領域６４では、所定領域６３よりも同一距離の移動で考慮すべき経由候補点６５の数を低減することができる。このため、所定領域６３内の経由候補点６５の間隔で全探索領域６９を設定した場合よりも経路探索部４４による経路探索に係る演算処理量を低減させることができる。
【００８０】
なお、探索領域６９では、敵ＮＰＣ５１が移動する面を複数の三角形形状の格子で構成し、三角形の各辺の中央位置を、移動経路を設定する上での敵ＮＰＣ５１の経由候補点（ノード）６５とする構成であった。しかしながら、経由候補点６５の位置は、例えば、三角形の中心点などを経由候補点６５としてもよい。また、この経由候補点６５は、敵ＮＰＣ５１が始点６７から終点６８に到達するために移動する必要のある一連の三角形の格子を表すパスであり、敵ＮＰＣ５１は実際には三角形の格子内であればどこに位置してもよい。すなわち、経路探索部４４は、同一の格子内ではどの位置からでも他の位置に移動するための情報は予め保持している。例えば、経路探索部４４は、経由候補点６５から所定の範囲以内に敵ＮＰＣ５１が到達したとき、この経由候補点６５に到達したとみなす。そして、この経由候補点６５に到達したとみなされると、敵ＮＰＣ５１は移動経路における次の経由候補点６５に向かって移動する。さらには、移動する空間が敵ＮＰＣ５１から見てどのように見えるかについての情報を保持していてもよい。このような情報を保持することで格子間の移動をより自然に振舞うようにすることができる。
【００８１】
なお、本実施形態では、探索領域６９には上述したように、敵ＮＰＣ５１が移動する面には複数の三角形の格子が設定される構成であった。そして、三角形の格子の各辺の中央位置を、移動経路を設定する上での敵ＮＰＣ５１の経由候補点（ノード）６５としていた。しかしながら設定される格子の形状はこの三角形に限定されるものではなく、例えば、図７に示すように正方形とし、正方形の格子の各辺の中央位置または正方形における任意の位置を、移動経路を設定する上での敵ＮＰＣ５１の経由候補点（ノード）６５としてもよい。この場合、所定領域６３内で設定する正方形の格子と、所定領域６３および外周領域６４（探索領域６９全体）で設定する正方形の格子とでは後者の方が、格子の面積が大きくなる。このように、より小さな正方形の格子が配されたメッシュと、より大きな正方形の格子が配されたメッシュとをそれぞれ設定する。そして、各格子の任意の位置に設定した経由候補点６５に基づき、上述したようにＡ＊アルゴリズムを利用して移動経路を求めるように構成されていてもよい。
【００８２】
また、図８に示すように、第１経由候補位置マップ情報および第２経由候補位置マップ情報として、格子で構成されるメッシュを設定するのではなく探索領域６９に直接、経由候補点６５を配する構成であってもよい。この場合、所定領域６３のみに配される経由候補点６５と、該所定領域６３および外周領域６４、すなわち探索領域６９全体に配される経由候補点６５とでは、後者の方が経由候補点６５間の間隔が大きくなるように各経由候補点（ノード）６５が配されたマップが設定される。そして、これら設定された経由候補点６５に基づき、例えば、ウエイポイントナビゲーションを用いて移動経路を選択する構成であってもよい。なお、図８では、所定領域６３内のみに配される経由候補点６５、あるいは探索領域６９全体に配される経由候補点６５それぞれにおいて、各経由候補点６５間の間隔が等間隔となっているがこれに限定されるものではない。
【００８３】
例えば、探索領域６９に壁等が配されており全方位を見渡すことができない環境に設定されている場合、どの経由候補点６５も１以上のノードからみた視野に入るように配置される。このため、各経由候補点６５間の間隔が必ずしも等間隔となるとは限らない。ただし、外周領域６４における経由候補点６５間の間隔の方が所定領域６３における経由候補点６５間の間隔よりも大きくなるという関係は維持される。図７および図８は、図４に示すゲーム空間６０の探索領域６９において経由候補点６５を設定する一例を示す図である。
【００８４】
さらにまた、上記ではゲームプログラム３０ａには、第１経由候補位置マップ情報と第２経由候補位置マップ情報とを含むものとして説明した。しかしながら、初めからゲームプログラム３０ａに、これら２種類のマップ情報が記録される構成に限定されない。例えば、ゲームプログラム３０ａには、第１経由候補位置マップ情報だけが含まれており、ゲーム装置１にてこの第１経由候補位置マップ情報から第２経由候補位置マップ情報を生成する構成であってもよい。例えば、第１経由候補位置マップ情報が三角形または四角形等の複数の格子を配したメッシュ情報である場合、格子を組み合わせてより大きな格子とし、該格子を配したメッシュ情報を第２経由候補位置マップ情報として生成することができる。例えば、第１経由候補位置マップ情報が複数の経由候補点６５を配したマップ情報である場合、このマップ情報から経由候補点６５を適当に間引いたマップ情報を第２経由候補位置マップ情報として生成することができる。
【００８５】
あるいは、ゲームプログラム３０ａには、２種類の第２経由候補位置マップ情報を含んでおり、ゲーム装置１においてこの２種類の第２経由候補位置マップ情報を組み合わせて第１経由候補位置マップ情報を生成する構成としてもよい。このような構成の場合、生成した第１経由候補位置マップ情報と、２種類の第２経由候補位置マップ情報のうちの一方の情報とを用いて、本実施の形態に係る経路探索処理を実行することができる。
【００８６】
また、本実施形態では精細なメッシュを設定する範囲を、所定領域６３とし、粗いメッシュを設定する範囲を、所定領域６３および外周領域６４としているが、これに限定されるものではない。例えば、所定領域６３には精細なメッシュが設定され、外周領域６４には粗いメッシュが設定され、これら設定された２種類のメッシュを利用して経路探索を行なってもよい。
【００８７】
なお、本実施形態のゲームでは、敵ＮＰＣ５１がＰＣ５０に接近する例を挙げて、敵ＮＰＣ５１のＰＣ５０までの経路探索処理について説明した。ＰＣ５０に向かって移動するキャラクタは敵ＮＰＣ５１に限定されるものではなく、例えば、ＰＣの仲間となりうるキャラクタなどのＮＰＣであってもよい。
【００８８】
また、上記では敵ＮＰＣ５１を１体として経路探索処理について説明したが、当然、敵ＮＰＣ５１は複数体であってもよい。また、敵ＮＰＣ５１が複数体ある場合において、全ての敵ＮＰＣ５１について上述したような経路探索処理を行なってもよいし、このうちのいくつかの敵ＮＰＣ５１だけ上述したような経路探索処理を行なってもよい。例えば、複数の敵ＮＰＣ５１それぞれについて、その能力等に応じてレベルが設定されているとき、レベルの低い敵ＮＰＣ５１については、第１経由候補位置マップ情報と第２経由候補位置マップ情報とを用いた上述した経路探索処理により移動経路を決定する。一方、レベルの高い敵ＮＰＣ５１については、第１経由候補位置マップ情報のみを用いた経路探索処理により移動経路を求めるように構成してもよい。また、敵ＮＰＣ５１の移動目標は、ＰＣ５０に限定されるものではなくＰＣ５０の近傍、もしくは所定領域６３の任意の位置であってもよい。
【００８９】
あるいは、敵ＮＰＣ５１は、外周領域６４の任意の位置に移動しており、その移動経路の途中が所定領域６３に含まれる場合であってもよい。このように移動経路の途中が所定領域６３に含まれる場合では、経路探索部４４は、敵ＮＰＣ５１の現在位置から目標位置まで、まず大きい格子が配されたメッシュの経由候補点６５により移動経路の算出を行う。そして、敵ＮＰＣ５１が所定領域６３に入ると、経路探索部４４は、小さい格子が配されたメッシュの経由候補点６５により再度、算出する。つまり、敵ＮＰＣ５１が、ＰＣ５０の現在位置に応じて移動する例を挙げて経路探索処理について説明したが、敵ＮＰＣ５１はＰＣ５０の動きとは無関係にゲーム空間６０内を移動するものであってもよい。また、敵ＮＰＣ５１の動作態様によっては、敵ＮＰＣ５１がずっと所定領域６３内に存在する場合もあるし、逆に外周領域６４に存在する場合もある。
【００９０】
例えばＰＣ５０が、味方のＮＰＣを護衛する役割であり、敵ＮＰＣ５１が、ＰＣ５０が護衛するＮＰＣを目指して接近してくるとする。この場合、ＰＣ５０と護衛対象のＮＰＣとの位置関係によっては、敵ＮＰＣ５１の位置が所定領域６３と外周領域６４との間を刻々と変化する場合もありうる。このように、敵ＮＰＣ５１の位置が所定領域６３と外周領域６４との間を刻々と変化する場合であっても、本実施形態では、敵ＮＰＣ５１の移動経路を粗いメッシュを用いて決定するのか、精細なメッシュを用いて決定するのかリアルタイムに適宜対応することができる。
【００９１】
また、本実施形態に係るゲームとして、オープンワールドのゲームを想定して敵ＮＰＣ５１のＰＣ５０までの経路探索処理について説明した。しかしながら、ゲーム空間６０をマップの切り替えやデータロードに伴って画面の静止や暗転を行い表現するようなゲームであっても、本実施形態に係る経路探索処理を利用することができる。ただし、扱うデータ量が大きく、経路探索を行う範囲が広くなるオープンワールドのゲームの方が、本実施形態に係る「経路探索処理」によるメリットをより多く享受できる。
【００９２】
なお、本実施形態に係る経路探索処理では、敵ＮＰＣ５１は、２次元平面（例えば地面）を移動してＰＣ５０に接近する例を挙げて説明したが、敵ＮＰＣ５１の移動は、３次元空間（例えば、空中または水中）であってもよい。この移動する場所に応じて、障害物領域６６ａ、６６ｂの設定は変化する。また、敵ＮＰＣの移動速度に応じて所定領域６３、外周領域６４に設定するメッシュの目（格子）の大きさを変更する構成であってもよい。なお、敵ＮＰＣ５１が３次元空間を移動する場合、第１経由候補位置マップ情報および第２経由候補位置マップ情報それぞれについて３次元空間に対応したメッシュが作成される。
【００９３】
また、上記した「経路探索処理」では、探索領域設定部４５は、探索領域６９を所定領域６３と外周領域６４の２つの領域に分離する構成であったが、分離される領域はこの２つに限定されるものではない。さらに外周領域６４を細かく分離し、所定領域６３からの距離が遠くなればなるほどメッシュの目（格子）の大きさが大きくなるように設定してもよい。
【００９４】
また、本実施形態に係る経路探索処理では、図６に示すように、ステップＳ１３において、障害物領域の設定を行なっていた。しかしながら、障害物オブジェクトが配される領域（図６の例では、障害物領域６６ａ、６６ｂ）に関する情報が第１経由候補位置マップ情報および第２経由候補位置マップ情報それぞれに予め含まれていてもよい。このように、障害物オブジェクトが配される領域を第１経由候補位置マップ情報および第２経由候補位置マップ情報それぞれが含む場合、ステップＳ１３の処理を省略することができる。なお、障害物オブジェクトが配される領域に関する情報が第１経由候補位置マップ情報および第２経由候補位置マップ情報それぞれに予め含まれている例としては以下のような場合が挙げられる。すなわち、例えば、図８に示すように、第１経由候補位置マップ情報および第２経由候補位置マップ情報として、探索領域６９に直接、経由候補点６５を配する場合である。この場合、この経由候補点６５は、敵ＮＰＣ５１の移動可能な領域を考慮して配される。つまり、この場合、経由候補点６５を配する際に、すでに敵ＮＰＣ５１が移動不可な障害物オブジェクトが配される領域についても考慮していることとなる。このため、この場合第１経由候補位置マップ情報および第２経由候補位置マップ情報には、すでに障害物オブジェクトが配される領域情報が含まれていることとなる。
【００９５】
また、本実施形態では、図２に機能ブロックとして示す各部（仮想ゲーム空間生成部４１、キャラクタ動作制御部４２、ゲーム進行制御部４３、経路探索部４４、および探索領域設定部４５）を、ＣＰＵ２がディスク型記録媒体３０からゲームプログラム３０ａをＲＡＭ８に読み出し、実行することで実現していた。
【００９６】
しかしながら、ゲームプログラム３０aの提供先はこのディスク型記録媒体３０に限定されるものではない。例えば、ゲームプログラム３０aは、カード型記録媒体３１に記録され、このカード型記録媒体３１からゲーム装置１に提供される構成であってもよい。
【００９７】
あるいは、ゲームデータ３０ｂをサーバ装置２１が保持しており、サーバ装置２１から通信ネットワーク２０を通じてこのゲームデータ３０ｂをゲーム装置１に提供する構成であってもよい。あるいは、ゲームプログラム３０ａは、ＨＤＤ６等に予め記憶されていてもよい。
【００９８】
また、本実施形態では、図２に機能ブロックとして示す各要素は、上述のようにＣＰＵ２によりソフトウェアにより実現されるものとして説明した。しかしながら、これら各要素を予めゲーム装置１が備える場合は、ハードウェアロジックによって構成してもよい。
【００９９】
また、本実施例では据え置き型のゲーム装置について説明したが、携帯ゲーム装置、携帯電話機や、パーソナルコンピュータなどのコンピュータについても、本発明を好適に適用することができる。
【０１００】
上記説明から、当業者にとっては、本発明の多くの改良や他の実施形態が明らかである。従って、上記説明は、例示としてのみ解釈されるべきであり、本発明を実行する最良の態様を当業者に教示する目的で提供されたものである。本発明の精神を逸脱することなく、その構造及び／又は機能の詳細を実質的に変更できる。
【産業上の利用可能性】
【０１０１】
本発明は、ゲーム空間において移動開始位置から目標位置までの距離が大きくなるにつれ増大する探索に係る処理負荷を抑制することができるゲームプログラム及びコンピュータ装置を提供することができる。
【符号の説明】
【０１０２】
１    ゲーム装置
２    ＣＰＵ
４      ディスクドライブ
６    ＨＤＤ
７    ＲＯＭ
８    ＲＡＭ
１１  グラフィック処理部
１２    ビデオ変換部
１３    モニタ
１７  無線通信制御部
１８    コントローラ
１９    ネットワークインタフェース
２０    通信ネットワーク
２１    サーバ装置
３０  ディスク型記録媒体
３０ａ  ゲームプログラム
３０ｂ  ゲームデータ
３１    カード型記録媒体
３２    画像データ
３３    地形データ
４１  仮想ゲーム空間生成部
４２  キャラクタ動作制御部
４３  ゲーム進行制御部
４４  経路探索部
４５  探索領域設定部
５０  プレイヤキャラクタ（ＰＣ）
５１  敵ノンプレイヤキャラクタ（敵ＮＰＣ）
６０  ゲーム空間
６１  周辺描画領域
６２  外周描画領域
６３  所定領域
６４  外周領域
６６ａ  障害物領域
６６ｂ  障害物領域
６７    始点
６８    終点
６９  探索領域
【図１】
0005627526.tif 000002
【図２】
0005627526.tif 000003
【図６】
0005627526.tif 000004
【図７】
0005627526.tif 000005
【図８】
0005627526.tif 000006
【図３】
0005627526.tif 000007
【図４】
0005627526.tif 000008
【図５】
0005627526.tif 000009