(57)【要約】【課題】ネットワークゲームサーバのキャラクタ密集時の負荷軽減を図る。【解決手段】ネットワークゲームサーバのプログラムであって、コンピュータを、端末装置から第１のキャラクタＴのチャット情報を受信する手段、チャット情報を受信したとき、仮想空間上の第１のキャラクタの位置の周囲に矩形領域１０００を設定し、各キャラクタの位置に基づいて木構造で関係付けられたキャラクタ相互の親子関係に基づいて、矩形領域の方向に、第２のキャラクタＡを根とした当該子孫キャラクタを探索していき、子孫キャラクタが矩形領域内に存在する場合は、当該子孫キャラクタを送信対象として特定する手段、送信対象に対応する端末装置にチャット情報を送信する手段、として機能させる。【選択図】        図１８
2004298373.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークを介して接続される複数の端末装置と通信することによってネットワークゲームを進行するネットワークゲームサーバであって、
前記端末装置から第１のキャラクタについての所定情報を受信する情報受信手段と、
前記所定情報を受信したとき、仮想空間上の前記第１のキャラクタの位置の周囲に所定領域を設定し、各キャラクタの位置に基づいて木構造で関係付けられたキャラクタ相互の親子関係に基づいて、前記所定領域の方向に、第２のキャラクタを親キャラクタとした当該子孫キャラクタを探索していき、前記子孫キャラクタが前記所定領域内に存在する場合は、当該子孫キャラクタを送信対象として特定する送信対象特定手段と、
前記送信対象に対応する端末装置に前記所定情報を送信する情報送信手段と、
を備えることを特徴とするネットワークゲームサーバ。
【請求項２】
前記木構造は、前記第２のキャラクタを根とすることを特徴とする請求項１に記載のネットワークゲームサーバ。
【請求項３】
前記所定領域は、前記第１のキャラクタの位置を中心とした矩形領域であることを特徴とする請求項１または請求項２に記載のネットワークゲームサーバ。
【請求項４】
前記所定情報は、チャット情報であることを特徴とする請求項１乃至請求項３に記載のネットワークゲームサーバ。
【請求項５】
前記所定情報は、仮想空間上で位置変化のあった前記第１のキャラクタの位置変化情報であり、
前記ネットワークゲームサーバは、更に前記位置変化情報を受信したとき、当該位置変化情報に基づいて前記第１のキャラクタの位置及び前記親子関係を更新する親子関係更新手段と、
を備えることを特徴とする請求項１乃至請求項３に記載のネットワークゲームサーバ。
【請求項６】
前記ネットワークゲームサーバは、更に前記所定領域内に存在する前記子孫キャラクタの数を数える人数取得手段を備え、前記送信対象特定手段は、前記人数取得手段により取得したキャラクタ数が所定数を超えた場合は前記所定領域を狭くして、再度前記送信対象を特定することを特徴とする請求項１乃至請求項５のいずれか１項に記載のネットワークゲームサーバ。
【請求項７】
ネットワークを介して接続される複数の端末装置と通信することによってネットワークゲームを進行するネットワークゲームサーバの制御方法であって、
前記端末装置から第１のキャラクタの所定情報を受信したとき、
仮想空間上の前記第１のキャラクタの位置の周囲に所定領域を設定し、各キャラクタの位置に基づいて木構造で関係付けられたキャラクタ相互の親子関係に基づいて、前記所定領域の方向に、第２のキャラクタを親キャラクタとした当該子孫キャラクタを探索していき、前記子孫キャラクタが前記所定領域内に存在する場合は、当該子孫キャラクタを送信対象として特定し、
前記送信対象に対応する端末装置に前記所定情報を送信する、
ステップを含むことを特徴とするネットワークゲームサーバの制御方法。
【請求項８】
ネットワークを介して接続される複数の端末装置と通信することによってネットワークゲームを進行するネットワークゲームサーバが実行可能なプログラムであって、コンピュータを、
前記端末装置から第１のキャラクタの所定情報を受信する手段、
前記所定情報を受信したとき、仮想空間上の前記第１のキャラクタの位置の周囲に所定領域を設定し、各キャラクタの位置に基づいて木構造で関係付けられたキャラクタ相互の親子関係に基づいて、前記所定領域の方向に、第２のキャラクタを親キャラクタとした当該子孫キャラクタを探索していき、前記子孫キャラクタが前記所定領域内に存在する場合は、当該子孫キャラクタを送信対象として特定する手段、
前記送信対象に対応する端末装置に前記所定情報を送信する手段、
として機能させるためのプログラム。
【請求項９】
ネットワークを介して前記ネットワークゲームサーバと接続された端末装置が実行可能なプログラムであって、コンピュータを、
ゲーム画像を表示する手段、
前記ネットワークゲームサーバに前記所定情報を送信する手段、
前記ネットワークゲームサーバから前記所定情報を受信する手段、
前記受信した所定情報を表示する手段、
として機能させるためのプログラム。
【請求項１０】
請求項８または請求項９に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ネットワークゲームサーバ、制御方法、プログラム及び記憶媒体に係り、特に、ネットワークゲームサーバの負荷を軽減するネットワークゲームサーバ、該制御方法、該プログラム及び該記憶媒体に関する。
【０００２】
【従来の技術】
近年、ブロードバンドの普及によりインターネット人口の拡大と通信技術の進歩が目覚しく、これに伴ってネットワークを介して複数のプレイヤが同時に参加可能なネットワークゲームの人気が高くなってきている。
【０００３】
ネットワークゲームには、多数のゲーム参加者のうち８人程度を１グループとして多数のグループに分け、各グループのゲーム参加者が操作する端末装置のうちの何れか１台をホストマシン、他をクライアントマシンとして１グループ内で１つの仮想空間を共有し、センターの専用サーバが各グループ内の端末装置間でなされるゲームコマンドの送受信を仲介し、実際のゲームプログラムの実行は端末装置側が行うロビーサーバ型と、センターのホストマシンとしての専用サーバが実際のゲームプログラムの主な実行と各端末装置が共有する仮想空間を一元管理し、各端末装置とゲームコマンド等の送受信をすることでゲームが進行する多人数参加型のＭＭＯＲＰＧ（Ｍａｓｓｉｖｅｌｙ  Ｍｕｌｔｉｐｌａｙｅｒ  Ｏｎｌｉｎｅ  Ｒｏｌｅ  Ｐｌａｙｉｎｇ  Ｇａｍｅ）型がある。
【０００４】
このＭＭＯＲＰＧ型のネットワークゲームは、ゲーム提供者が運用する高スペックサーバに接続することにより、数千人規模のプレイヤが参加可能なゲームであり、近年急激に人気を集めているが、あまりに多数のプレイヤが同時に参加するとサーバに高負荷がかかり、ゲーム進行に支障をきたすため、サーバの負荷を軽減するための技術が研究されている。
【０００５】
これに関する特許文献として、例えば、特開２００１−２３２０６８号公報には、複数のプレイヤが同一のコンピュータゲームを行う場合、ネットワーク上のデータの送受信の量を減少させることができる発明が開示されている。この発明は、単なるプレイヤキャラクタの仮想空間上の移動等、ゲーム進行上利害関係が殆どないデータは、変化の度に他のプレイヤの端末装置との送受信を行わず、アイテムの取得やキャラクタの消滅等の特別な場合にのみ変化したパラメータを送受信する技術であり、通信上の負荷を軽減することができる。
【０００６】
また、特開２００１−７３８９９号公報には、対戦の結果によって勝利者が所定のポイントを受け取り、ポイントによって自分のランクが上昇していくロビーサーバ型のゲームであって、対戦の結果によりポイントが付与されるサーバ負荷の重いロビーと、対戦の結果に関係なくポイントが付与されないサーバ負荷の軽いロビーとを設け、双方のロビー数を適応的に増減することにより、全体的にサーバの負荷を軽減する発明が開示されている。
【０００７】
そして、特開２００２−１８３７６２号公報には、プレイヤが自己のキャラクタを操作して仮想空間内を徘徊している場合、キャラクタ数が多い地点に来ても、画面表示されるキャラクタ数が所定数に制限されるようにした発明が開示されている。この発明によれば、キャラクタ数が多くなり、プレイヤの端末装置の画面内に表示されるキャラクタの密度が増しても、キャラクタが動きにくくなるという不都合が生ずることはない。このため結果的にサーバ負荷の増大を抑えることができると考えられる。
【０００８】
更に、本発明に関する他の文献として、１９８８年８月に発行された「Ｃｏｍｐｕｔｅｒ  Ｇｒａｐｈｉｃｓ」誌の第２８９頁から第２９８頁に、Ｍａｔｔｈｅｗ  Ｍｏｏｒｅ氏とＪａｎｅ  Ｗｉｌｈｅｌｍｓ氏による「Ｃｏｌｌｉｓｉｏｎ  Ｄｅｔｅｃｔｉｏｎ  ａｎｄ  Ｒｅｓｐｏｎｓｅ  ｆｏｒ  Ｃｏｍｐｕｔｅｒ  Ａｎｉｍａｔｉｏｎ」と題される、コンピュータグラフィクスによるキャラクタがアニメーションする際の他のキャラクタとの衝突判定に関する記載がある。特に、第２９１頁には、剛体を構成するポリゴン点を木構造とし、他の剛体との当たり判定を行う際に８分木（Ｏｃｔｔｒｅｅ）探索を用いる技術が開示されている。
【０００９】
【特許文献１】
特開２００１−２３２０６８号公報（段落番号「０００３」から「００１４」まで）
【特許文献２】
特開２００２−２７３０５８号公報（段落番号「０００４」から「００３１」まで）
【特許文献３】
特開２００２−１８３７６２号公報（段落番号「０００４」から「００７１」まで）
【非特許文献１】
「コンピュータ  グラフィクス（Ｃｏｍｐｕｔｅｒ  Ｇｒａｐｈｉｃｓ）」，（米国），アディソン  ウェズリー社発行（Ａｄｄｉｓｏｎ  Ｗｅｓｌｅｙ  Ｐｕｂｌｉｓｈｉｎｇ  Ｃｏ．，Ｉｎｃ．），１９８８年８月，第２２巻，第４号，ｐ２８９−ｐ２９８
【００１０】
【発明が解決しようとする課題】
しかしながら、特開２００１−２３２０６８号公報及び特開２００２−２７３０５８号公報に記載の発明は、全体的なネットワークゲームサーバの負荷を軽減できるものの、ネットワークゲームにおける仮想空間内の特定のエリアに多数のプレイヤキャラクタが密集している特別な場合に、特に、サーバ負荷を軽減させるものではない。
【００１１】
また、特開２００２−１８３７６２号公報に記載の発明では、画面表示可能なキャラクタ数を直接制限するのでネットワークゲームサーバの負荷の増大を抑制できるが、あえて多数のキャラクタがある地点に密集する様子を表現するには向いているといえず、また、定員数を超えた場合は更に別なキャラクタがそのエリアに入ってきても表示されないため、殆ど同じ位置にいる他のプレイヤのキャラクタを認識することができない場合がある。
【００１２】
そこで本発明は、ネットワークゲームサーバの負荷が最も増大するプレイヤキャラクタの密集エリアでのチャット等の情報送受信において、情報発信しようとするプレイヤキャラクタの仮想空間上の位置を中心とした所定領域内の密集度を素早く検知し、その密集度に応じて情報受信可能な領域としての所定領域を段階的に狭くしていくことで、ネットワークゲームサーバの負荷の増大を抑制することを課題とする。
【００１３】
【課題を解決するための手段】
上記課題を解決するための、本発明の第１の態様は、ネットワークを介して接続される複数の端末装置と通信することによってネットワークゲームを進行するネットワークゲームサーバであって、前記端末装置から第１のキャラクタについての所定情報を受信する情報受信手段と、前記所定情報を受信したとき、仮想空間上の前記第１のキャラクタの位置の周囲に所定領域を設定し、各キャラクタの位置に基づいて関係付けられたキャラクタ相互の親子関係に基づいて、前記所定領域の方向に、第２のキャラクタを親キャラクタとした当該子孫キャラクタを探索していき、前記子孫キャラクタが前記所定領域内に存在する場合は、当該子孫キャラクタを送信対象として特定する送信対象特定手段と、前記送信対象に対応する端末装置に前記所定情報を送信する情報送信手段と、を備えることを特徴とする。
【００１４】
第１の態様でいう親子関係とは、あるキャラクタを親とした場合の子及びその子孫（以下、まとめて子とする）の関係であり、全キャラクタの位置に基づいて木構造を構築し、親から子の方向へ辿っていける関係をいう。この場合、探索の開始点としての親キャラクタとその目標領域を特定すれば、後はその方向に存在する子を探索していくことにより、目標領域内に存在するキャラクタを高速且つ正確に特定することができる。即ち、木のその方向のノード（節点）だけを調べれば良いので全キャラクタについて一様に座標値を調べる必要がなくなり、また、目標を点でなく領域とすることで、木のノードがその領域をかすめるような場合でも過不足なく領域内のノードとしてのキャラクタを抽出することができる。これにより、領域内のキャラクタに対応する端末装置にのみ所定情報を送信することで、ネットワークゲームサーバの負荷の増大を抑えることができる。そして、このような木構造は別なタイミングで常々作成又は更新されるようにすれば、更に所定情報受信時の計算コスト減少へと繋がる。
【００１５】
ここで、探索の開始点としての親キャラクタを木構造でいう根に割り当てられた特定のキャラクタに固定しておけば、状況により親キャラクタを変更する必要がなくなる。また、目標の所定領域を、情報を発信するキャラクタ（以下、発信キャラクタ）の位置を中心とした正方形等の矩形領域とすれば、その４つの頂点のｘ，ｙ座標成分（ｚ座標、即ち高さ成分までは考慮しなくて良い）と、探索した子の位置情報のｘ，ｙ座標成分とを各々比較すれば、その所定領域に属するか否かを容易に知ることができる。ここで、例えば発信キャラクタから半径ｒ離れた範囲に属するか否かを調べる方法では、発信キャラクタと探索した子の２点間の差を求めた後に平方根の定理により距離を求め、半径ｒと比較するような複雑な計算が必要となるが、本発明ではこのような必要がなくなり、子の子、即ち孫に対しても同様に単純な大小比較を繰り返し行っていけば良いので、大幅な計算コストの軽減となる。また、探索したキャラクタが所定領域に属するか否かが分かれば良いので、発信キャラクタを中心として近いキャラクタから昇順に並べる（ソートする）必要もない。尚、本発明では画面表示されているキャラクタ数に情報を発信するという制限はしない。
【００１６】
尚、本発明では、上記非特許文献１に記載されている、剛体を構成する各ポリゴン点を８分木構造で関係させ、ツリーノードとしての各ポリゴン点の親子関係から所定領域内に属するポリゴン点を探索することで剛体の衝突判定を実行する技術を、ネットワーク仮想空間上で各プレイヤが操作するプレイヤキャラクタを含む全キャラクタの位置情報に基づいて、各キャラクタ相互の親子関係を４分木構造として構築し、情報を発信するキャラクタの近傍に存在する他のキャラクタを高速に探索するとともに、探索したキャラクタのみに情報を伝達してサーバ負荷を軽減するという技術に応用している。
【００１７】
また、本発明の第１の態様でいう所定情報がチャット情報である場合は、上述の理由でチャット時の負荷が軽減されることになる。更にその所定情報が、仮想空間上で位置変化のあったキャラクタの位置変化量である場合は、その位置変化量からそのキャラクタの最新位置を計算して現在の位置を更新するとともに、その付近又は全体の親子関係も更新する親子関係更新手段を備えれば、キャラクタの移動があったときでも矛盾なく木構造を維持することができ、更に他のプレイヤの端末装置への位置更新の通知も、情報発信源の周辺の領域内に存在するキャラクタに対応した端末装置にのみ通知するので、このときの負荷の増大を防ぐことができる。
【００１８】
更に、所定領域内に存在するキャラクタの数を数える人数取得手段を備えて、そのキャラクタ数が所定数を超えた場合はその所定領域を狭くして、再度送信対象を特定するようにすれば、更にサーバ負荷の増大を抑制することができる。
【００１９】
本発明の第２の態様は、ネットワークを介して接続される複数の端末装置と通信することによってネットワークゲームを進行するネットワークゲームサーバの制御方法であって、前記端末装置から第１のキャラクタの所定情報を受信したとき、仮想空間上の前記第１のキャラクタの位置の周囲に所定領域を設定し、各キャラクタの位置に基づいて木構造で関係付けられたキャラクタ相互の親子関係に基づいて、前記所定領域の方向に、第２のキャラクタを親キャラクタとした当該子孫キャラクタを探索していき、前記子孫キャラクタが前記所定領域内に存在する場合は、当該子孫キャラクタを送信対象として特定し、前記送信対象に対応する端末装置に前記所定情報を送信する、ステップを含むことを特徴とする。
【００２０】
本発明の第３の態様は、ネットワークを介して接続される複数の端末装置と通信することによってネットワークゲームを進行するネットワークゲームサーバが実行可能なプログラムであって、コンピュータを、前記端末装置から第１のキャラクタの所定情報を受信する手段、前記所定情報を受信したとき、仮想空間上の前記第１のキャラクタの位置の周囲に所定領域を設定し、各キャラクタの位置に基づいて木構造で関係付けられたキャラクタ相互の親子関係に基づいて、前記所定領域の方向に、第２のキャラクタを親キャラクタとした当該子孫キャラクタを探索していき、前記子孫キャラクタが前記所定領域内に存在する場合は、当該子孫キャラクタを送信対象として特定する手段、前記送信対象に対応する端末装置に前記所定情報を送信する手段、として機能させる。
【００２１】
以上はサーバ側のプログラムであるが、一方で端末装置側のプログラムも考えられる。即ち、ネットワークを介して前記ネットワークゲームサーバと接続された端末装置が実行可能なプログラムであって、コンピュータを、ゲーム画像を表示する手段、前記ネットワークゲームサーバに前記所定情報を送信する手段、前記ネットワークゲームサーバから前記所定情報を受信する手段、前記受信した所定情報を表示する手段、として機能させる。これは、前記第１の態様で構成されるネットワークゲームサーバと接続された端末装置側のプログラムである。
【００２２】
そして本発明の第４の態様は、上記第３の態様に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体である。ここでいう記録媒体とは、例えばＣＤ−ＲＯＭ，ＤＶＤ，フレキシブルディスク，ハードディスク，ＭＯ，ＲＯＭ，メモリーカード等をいう。
【００２３】
【発明の実施の形態】
以下、本発明の実施形態を図面を参照しながら説明する。尚、本実施形態では前述したＭＭＯＲＰＧ型のネットワークゲームの場合で説明する。
【００２４】
図１は、本実施形態のネットワークゲームサーバ（以下、ゲームサーバ）と端末装置との接続形態を示す概略図である。このゲームサーバは、インターネット等のネットワーク（通信回線）を介してゲームプレイヤのパーソナルコンピュータ，家庭用ゲーム装置若しくは携帯電話等の端末装置と接続され、種々のデータの送受信を行うことで、ネットワークゲームの進行処理を行う。そして、ネットワーク上の各装置は、ＴＣＰ／ＩＰ等の通信プロトコルにより接続され、各々異なるＩＰアドレスが割り振られているため、各プレイヤが送受信する端末装置を識別することができる。
【００２５】
プレイヤは端末装置に接続されたモニタ等の表示装置に表示されるネットワークゲームの画面を見ながら、端末装置に接続されたキーボード，マウス若しくはゲームコントローラパッド等の入力装置を操作することにより、例えば、自分のキャラクタ（以下、プレイヤキャラクタ）をそのネットワークゲームの仮想空間内で移動させたり、他のキャラクタとチャット等を行うことができる。ここで、チャットとは、ネットワークゲームに参加しているプレイヤ間で主にテキスト文字による簡単な会話を楽しむものであり、ネットワークゲームの楽しみの一つでもある。
【００２６】
図２は、本実施形態のゲームサーバの内部構成を示すブロック図である。ＣＰＵはゲームサーバ全体の制御を行う。バスは、ＣＰＵ，ＲＡＭ（メモリ），ハードディスク等の記憶装置等の各デバイス間で情報をやりとりする経路である。記憶装置にはプログラムやデータが記憶されており、ＣＰＵはこれらをＲＡＭにロードした後にそのプログラムを実行する。ＲＯＭにはゲームサーバが異常時に起動するプログラム等サーバの基本的なプログラム等が記録されている。ＣＰＵ，ＲＡＭ及びＲＯＭをＣＰＵブロックとし、これらの協働により本発明でいう各手段が構成される。通信部はネットワークを介して接続された外部の各端末装置とデータの送受信を行う。
【００２７】
図３は、本実施形態の端末装置の内部構成を示すブロック図である。この端末装置はゲームサーバに対していわゆるクライアントとなる。端末装置側のゲームプログラムは、プレイヤによる操作によりネットワークサーバへコマンドやメッセージ等種々のデータを送信する一方、この送信によってネットワークゲーム内で起こった変動結果の情報や、他のプレイヤにより送信されゲームサーバを介して転送される情報、或いはゲームサーバが自発的に送信する情報等、種々のデータをゲームサーバから受信する。そして端末装置は、送受信したデータに基づいてゲームを進行し画面表示する。
【００２８】
ここで、端末装置側のプログラム及び画像や音楽等の種々のデータがＣＤ−ＲＯＭやＤＶＤ等の記録媒体に記録されている場合は、プレイヤがその記録媒体を端末装置としてのゲーム装置やパーソナルコンピュータに挿入してゲームをスタートすると、自動的にそのプログラム等が端末装置内のＲＡＭにロードされた後にそのプログラムが実行され、ゲームサーバと逐次通信しながらゲームが進行していく。一方で、端末装置内にハードディスクがある場合は、いったんプレイヤが記録媒体上のプログラム等をハードディスク上にコピーし、次回からはハードディスク上のプログラムをスタートさせる構成を取ることができる。また、ネットワーク上にこれらプログラム等がアップロードされている場合は、いったんプレイヤが端末装置側のハードディスクにダウンロードした後にそのプログラムをスタートさせる構成にしても良い。
【００２９】
そして本実施形態のネットワークゲームでは、先ずプレイヤは自分が担当するプレイヤキャラクタを選択する。プレイヤキャラクタには、例えば戦国時代をテーマとしたゲームであれば、侍，忍者，陰陽師等があり、通常はこれらの中から１つを選択する。そしてその後、プレイヤは自分のキャラクタを操作して戦闘や仕事等をすることによりキャラクタのレベルや能力等のパラメータを上昇させたり、ネットワークを介して接続された他のプレイヤのキャラクタと立身出世を競ったり、或いは他のプレイヤとチャットをしてコミュニケーションを楽しむものである。尚、この世界で登場するキャラクタは、いわゆるプレイヤが操作可能なプレイヤキャラクタに限らず、ゲームサーバによる自動的な演算により動作するＮＰＣ（ノン・プレイヤー・キャラクタ）も存在し、各端末装置上の画面に表示される。
【００３０】
ネットワークゲームの仮想空間の世界では、共通するゲームマップ上のある特定のポイントに多くのプレイヤキャラクタが集中すると、ゲームサーバの負荷が増大してゲーム進行に支障をきたすため、通常は仮想空間を複数のワールドに分け、各々のワールドに異なるゲームサーバを割り当て、複数のゲームサーバの並行処理で１つの世界を共有する構成をとる。そして、この世界の状況は各プレイヤの操作により常に流動的に変動していく。
【００３１】
ネットワークゲームの仮想空間での時間は、ゲームサーバが管理し、現実社会の時間とは異なった時間速度で進行していく。また、ゲームサーバ内の記憶装置に記憶されるゲームデータには、各プレイヤに固有のゲームデータと、全プレイヤに共通のゲームデータがあり、これらは端末装置側のプレイヤの操作やゲームサーバ自身の自動的なイベント発生等により逐次変動するため、定期的に更新され保存される。
【００３２】
次に、プレイヤが操作する端末装置側の動作について図４のフローチャートを用いて説明する。プレイヤがゲームをスタートすると、先ずステップ１０２でユーザ認証を行う。プレイヤが端末装置にユーザＩＤを入力するとゲームサーバに送信され、これを受信したゲームサーバは記憶装置に記憶されている全ユーザＩＤのデータを参照し、そのプレイヤが登録された者か否かについて確認する。登録されている場合、ゲームサーバは現在までのそのプレイヤのセーブデータを送信し、端末装置はこれを受信してゲームがスタートする。初めてゲームを開始する場合は、ユーザ登録及び自己が操作するプレイヤキャラクタの選択等の種々の初期設定を行う。その他のゲーム上必要ではあるが本発明と直接関係のない具体的な処理の説明は省略する（以下、そのような説明につき同じ）。
【００３３】
ステップ１０４では、図３に示すモニタの垂直帰線周期と一致した、１／６０秒（１６．６ミリ秒）に一度の周期で行われる垂直帰線割込（Ｖｓｙｎｃ）がなされたか否かを判断する。否定判断のときは、次のステップ１２２において、入力受信部から転送された入力情報に対する入力処理やゲーム効果音を音響処理部に合成させるための音響処理等のメイン処理を実行して、ステップ１２４へ進む。一方、ステップ１０４で肯定判断のときは、ステップ１０６において、チャットの送信要求があるか否かを判断する。肯定判断の時はステップ１０８でそのチャットデータをゲームサーバに送信する。
【００３４】
プレイヤがチャットを行う場合、そのプレイヤは端末装置に接続されたキーボードやゲームコントローラ等の入力装置を用いて、自分が発言したい内容の文字列（チャットデータ）を入力する。入力された文字列は入力受信部で受信し端末装置のＲＡＭ等のバッファにいったん蓄積され、プレイヤが入力した文字列を確定した場合は、その文字列は通信処理部の送信バッファにコピーされ、通信処理部に対して送信要求を行い、所定のタイミングで自動的にその文字列がネットワークを介してゲームサーバに送信される。尚、ゲームサーバの受信後の処理は後述する。
【００３５】
次にステップ１１０で、ゲームサーバからチャットデータを受信したか否かを判断する。肯定判断の時はステップ１１２でそのチャットデータをモニタに表示する。ゲームサーバから送信されたチャットデータはいったん通信処理部の受信バッファに蓄積され、所定のタイミングで自動的にそのチャットデータが画像処理部を介して端末装置のモニタに表示される。ここで、受信するチャットデータは、チャットデータを送信したプレイヤ以外の他のプレイヤの端末装置から送信されたものだけではなく、ゲームサーバの管理上の都合等のため、いったんゲームサーバを経由して発信者自身の端末装置にも送り返されるようにしている。また、通常チャットデータの送信はチャットに参加できるように、直接会話を交わす者以外の他のプレイヤにも送信される。
【００３６】
次にステップ１１４で、プレイヤが入力装置を操作して自分のプレイヤキャラクタを移動したか否か判断する。肯定判断の場合、ステップ１１６でプレイヤキャラクタの移動量、即ち、入力装置上の十字方向ボタンセット等を操作して入力されたｘ，ｙの座標変位量を送信する。ここで、本実施形態では高さ成分としてのｚ座標値は考慮しないものとする。ゲームサーバはこれを受信すると、そのキャラクタの最新位置を計算し、そのキャラクタ付近の他のキャラクタとの親子関係を見直して所定領域に属するプレイヤキャラクタの端末装置に最新位置を通知する。尚、親子関係の見直しは、全キャラクタに対して行っても良い。また、端末装置側でも常に最新の位置情報を持ち、移動があった時に得られた移動量から最新位置を計算する処理まで行い、その後にゲームサーバにその最新位置を送信するようにしても良い。ゲームサーバの動作については後述する。
【００３７】
次にステップ１１８で、ゲームサーバから送信された位置通知を受信したか否かを判断する。肯定判断の場合、ステップ１２０でその位置通知に対応したキャラクタを最新位置で画像処理部を介して表示し、ステップ１２４に移る。
【００３８】
ステップ１２４では、ステップ１２２でゲームを終了させるための入力装置上の所定ボタンが押下された否かを判断し、否定判断のときは、ステップ１０４へ戻り、肯定判断のときは、端末装置側が実行するプログラムを終了する。尚、説明は省略するが、キャラクタが移動した時やアイテムを得た時、又はキャラクタの能力値が上がった時等ゲーム進行上で重要な変化があった時は、その情報は端末装置からゲームサーバに送信され記憶装置にセーブされるものとし、これによりプレイヤが次回ゲームをするときは前回の状態で開始することができる。
【００３９】
次に、ゲームサーバの動作について図５から図１３までのフローチャートを用いて説明する。本実施形態ではゲームサーバは常に動作しているものとし終了することはないとする。
【００４０】
先ず、図５のステップ２０２で、図２に示すモニタの垂直帰線周期と一致した、１／６０秒（１６．６ミリ秒）に一度の周期で行われる垂直帰線割込（Ｖｓｙｎｃ）がなされたか否かを判断する。否定判断のときはこれを繰り返し、肯定判断の時は次のステップ２０４で、接続中の何れかの端末装置からキャラクタの移動量を受信したか否か判断する。肯定判断の時はステップ２０６で位置・親子関係更新サブルーチンに移行し、否定判断の時は次のステップ２０８で、何れかの端末装置から送信されたチャットデータを受信したか否かを判断する。肯定判断の時はステップ２１０でチャット負荷軽減サブルーチンに移行し、否定判断の時はステップ２０２に戻って処理を繰り返す。ここで、ゲームサーバの受信は前述した端末装置の場合と同様に、通信部の受信バッファにいったん蓄えた後に処理される。また、ゲーム進行上重要ではあるが本発明と直接関係のない情報を端末装置側から受信した場合の処理や、ゲームサーバ本体が自動的に行う処理等（例えば、上述したＮＰＣの動作等）その他の説明は省略する。
【００４１】
次に、ステップ２０６の位置・親子関係更新サブルーチンについて図６から図９を用いて説明する。先ず、ゲームサーバが受信したデータにはキャラクタの移動量の他にそのキャラクタを識別するキャラクタＩＤが含まれるものとし、このキャラクタＩＤは、あるプレイヤが初めてキャラクタを選択してゲームを開始する際に設定され、そのキャラクタの種々のデータの所在を示すポインタアドレス（以下、単にポインタ）は、０から昇順に設定されたキャラクタＩＤ順に記憶装置にセーブされるものとする。そしてステップ３０２でゲームサーバはキャラクタＩＤを取得すると、これを元にそのキャラクタの座標値等のデータを取得し、ステップ３０４の移動キャラ探索サブルーチンに移行する。
【００４２】
図７の移動キャラ探索サブルーチンでは、移動しようとするキャラクタ（以下、移動キャラクタ）を根から探索し、その親キャラクタへのポインタを、後述する子ノード探索・切り離しサブルーチン内で使用する親変数にセットする処理を行う。ここでセットするとは、ＲＡＭ上の変数にポインタアドレスやデータを格納して一時記憶することをいうとする（以下、同じ）。先ず、ステップ４０２で木構造の根として割り当てられたキャラクタのデータへのポインタをＲＡＭ上のノード変数にセットする。尚、根は、木構造で唯一であるので仮想空間上の任意の点、例えば原点（ｘ，ｙ）＝（０，０）とし、キャラクタが割り当てられていない実体のないノード、即ち視覚的に確認できない任意の座標点であっても良い。また、視覚的に確認できるキャラクタであっても人物以外のキャラクタで移動しないもの（目印となる大きな木等）であっても良い。そしてステップ４０４で移動キャラクタを探索の対象キャラクタ（以下、探索キャラクタ）とする。
【００４３】
ここで、本実施形態でいう木構造並びに親子関係について説明する。先ず、図１４（ａ）に示すようにキャラクタＡを中心としたｘ，ｙ座標軸を考えると、０から３までの４つの領域に分けることができる。一般に、キャラクタＡの右上を第１象限と呼び左回りに第２象限というように増加するが、本実施形態では処理の便宜上数字を０から開始し、右上を第０象限、左回りに第１象限というように増加するものとする。また、後述するが、各キャラクタについて自己を中心とした第何象限に子のキャラクタがいるかを考えるものとする。
【００４４】
図１４（ｂ）は、キャラクタＡを根とした場合の木構造の一例である。この例では、キャラクタＡを親と考えた場合、キャラクタＢ，Ｃ，Ｄ及びＥの４つはその子となる。そして、キャラクタＢはキャラクタＡの第０象限，キャラクタＣはキャラクタＡの第１象限，キャラクタＤはキャラクタＡの第２象限，キャラクタＥはキャラクタＡの第３象限に属するものとする。尚、各キャラクタの子は各象限に１つずつで最大４つまで持てるものとする。同様にして、キャラクタＢは第０象限にキャラクタＦ，・・・というように設定されている。
【００４５】
図１４（ｃ）は図１４（ｂ）の木構造の一例を、実際のｘ，ｙ座標平面で考えた場合の各キャラクタの接続の様子を示す。
【００４６】
そして、図１４（ｄ）は図１４（ｂ）の木構造の一例を、実際のデータ構造を用いて示した場合である。例えばキャラクタＡは、体力値等のデータ（他のデータ）と、上記の４つの子へのポインタを持ち記憶されている。ここで、子へのポインタを記憶する変数を子ポインタ変数と呼び、各キャラクタデータ内に子ポインタ変数０から３を持つとする。子ポインタ変数０は第０象限，子ポインタ変数１は第１象限，・・・とする。キャラクタＡの子ポインタ変数０（図中では、Ａ子０）にはキャラクタＢへのポインタが記憶されており、キャラクタＡの子ポインタ変数１（図中では、Ａ子１）にはキャラクタＣへのポインタが記憶されている。またキャラクタＢの子ポインタ変数０（図中では、Ｂ子０）にはキャラクタＦへのポインタが記憶されている。他の場合も同様な考え方で関係付けられている。尚、キャラクタＢの子ポインタ変数１（図中では、Ｂ子１）にはヌル（０）が記憶され、これはキャラクタＢを中心とした第１象限には子がいないことを意味する。他の場合も同様であり、キャラクタＦのように全ての子ポインタ変数がヌル（０）の場合はキャラクタＦは葉であることを意味する。ここで、子ポインタとは、親キャラクタと関係付けられた異なるキャラクタを子キャラクタとし、その子キャラクタのデータが存在するアドレスを示す。また、各キャラクタデータは動的に確保されるＲＡＭ上の領域に記憶され、且つ記憶装置にセーブされる。
【００４７】
次に図７のステップ４０６で、探索キャラクタの位置がノード変数にセットされているそのノードを中心とした第何象限に属するか調べる。そしてステップ４０８で、そのノードのその象限に属する子を調べる。
【００４８】
次にステップ４１０でその子が移動キャラクタか否か判断し、否定判断の時はステップ４１２で、その子へのポインタをノード変数にセットし、ステップ４０６に戻って繰り返す。肯定判断の時はそのノードは移動キャラクタの親であるから、ステップ４１４でそのノードへのポインタを親変数にセットし、本サブルーチンを終了して図６のステップ３０６に戻る。
【００４９】
ここで、この移動キャラ探索サブルーチンでは、移動キャラクタの位置を目標として木構造の根から順に子を辿っていくが、この様子について図１５の一例を用いて説明する。ここで、キャラクタａを根としてキャラクタｄが移動キャラクタとすると、先ず、キャラクタｄはキャラクタａの右上（第０象限）にあるのでキャラクタａの子ポインタ変数０に記憶されているキャラクタｂへのポインタを取得する。また、ここでキャラクタｂ以降の子孫（ｂ，ｃ及びｄ）は、全てキャラクタａの右上に存在するものに限られるというルールを設けるとする。次にキャラクタｄはキャラクタｂの左上にあるのでキャラクタｂの子ポインタ変数１に記憶されているキャラクタｃへのポインタを取得する。先のルールはここでも適用され、キャラクタｂ以降の子孫は全てキャラクタａの右上に存在し、キャラクタｃ以降の子孫は全てキャラクタｂの左上に存在するものに限られるということになる。即ち、あるノードの子ノードが属する象限の領域を、ノードを辿る度に論理積をとって狭くしていくというルールである。このようにして子を辿っていくことで、移動キャラクタに接続される親としてのキャラクタを特定する。
【００５０】
図６のステップ３０６に戻ると、ステップ３０２で取得した移動キャラクタの座標値、即ち現在の位置情報に、受信した移動量の各ｘ，ｙ成分を加算して最新位置を算出し、位置情報を更新する（ステップ３０６）。
【００５１】
そしてステップ３０８で、子ノード数の変数を０とし、子ノードバッファをクリアする。ここで子ノードバッファはＲＡＭ上に確保された領域である。次にステップ３１０で、ノード変数に移動キャラクタへのポインタをセットし、ステップ３１２で子ノード探索・切り離しサブルーチンに移行する。
【００５２】
図８に示す子ノード探索・切り離しサブルーチンでは、移動キャラクタ及びその全ての子孫のキャラクタ数を数えて子ノード数とし、各々のキャラクタへのポインタを子ノードバッファに追加していく処理を行う。また、これら全てのキャラクタを木構造からいったん切り離す処理を行う。ここで切り離した後に後述する子ノード結合サブルーチンで再結合するが、このようにしないと、キャラクタの移動により木構造の構築で定めた前述のルールに矛盾が生ずるためである。
【００５３】
これを図１６及び１７を用いて説明する。先ず、図１６（ａ）のような例の木構造で、矢印の方向に移動する移動キャラクタであるｄに子がいない場合で考える。キャラクタｄが図１６（ｂ）に示す位置まで移動した場合は、根のキャラクタａから見てキャラクタｄは右上に存在し、次のキャラクタｂから見てキャラクタｄは左上に存在するので、図１６（ａ）での状態で根から辿った場合と同じであり、ここまでは前述のルールは維持できている。尚、キャラクタｄはキャラクタｃの子であるがキャラクタｃの第何象限の子であるかは問題ではなく、キャラクタｄがキャラクタａの右上で且つキャラクタｂの左上であることが満たされていれば問題ない。ただし、キャラクタｃの右上に子がいないことが条件となる。そして、キャラクタｄが図１６（ｃ）に示す位置まで移動すると、キャラクタｄはキャラクタｂの子のキャラクタｃが存在する左上ではなく、右上にはみ出してしまい、このままキャラクタｃとキャラクタｄを接続していては、前述のルールに矛盾してしまう。この場合は図１６（ｃ’）のように、キャラクタｄはキャラクタｃとの接続を切り離し、新たにキャラクタｂと接続しなければならない。ただし、キャラクタｂの右上に子がいないことが条件となる。
【００５４】
また、図１７（ａ）のような例の木構造で、矢印の方向に移動する移動キャラクタであるｃに子がいる場合で考える。基本的には上記図１６の場合と同じであるが、図１７（ｃ）とはならず、図１７（ｃ’）としなければならない。即ち、キャラクタｃが図１７（ｃ）で示す位置まで移動した場合は、キャラクタｃとキャラクタｄは切り離され、新たにキャラクタｂとキャラクタｄが接続されなければならないということである。ただし、キャラクタｂの左上に子がいないことが条件となる。
【００５５】
このように、あるキャラクタが移動した場合は、いったんそのキャラクタ以降のノードを木構造から切り離し、再度矛盾が起こらないようにそれらを結合する処理が必要となってくる。
【００５６】
再び図８の子ノード探索・切り離しサブルーチンの説明に戻ると、先ず、ステップ５０２でノード変数がヌルか否かを判断し、肯定判断であれば本サブルーチンを終了する。後述するが、このサブルーチンは再帰的に呼び出される関数であり、ノード変数がヌルの場合とは、そのノードの親にはもはや子はいないことを意味する。そして、ステップ５０２で否定判断の時は、次にステップ５０４で子ノードバッファにそのノードへのポインタを追加し、ステップ５０６で子ノード人数を追加し、ステップ５０８でそのノードをその親から切り離す。具体的に切り離しの処理は、親変数にセットされているポインタが指すキャラクタの、４つの子ポインタ変数のうち、そのノードへのポインタがセットされている子ポインタ変数をヌルにセットする。そして、ステップ５１０でそのノードへのポインタを新たに親変数にセットする。
【００５７】
次にそのノードの子について調べていく。ステップ５１２でカウンタ変数ｌを０とし、ステップ５１４でｌが４より小さいか否か判断する。肯定判断の時は、ステップ５１６でそのノードの第ｌ象限の子ノードのポインタ、即ち子ポインタ変数ｌにセットされているポインタをノード変数にセットし、ステップ５１８で本サブルーチンを再帰的に呼び出す。再帰的に呼び出す理由は、現在のノードに子が見つかったためであり、その子の子，・・・についても調べる必要があるからである。再帰的呼び出しは通常スタックを使用するが、戻り先のアドレスや変数等はスタックにプッシュされ、戻った後にポップされることで正常に動作するものとする。ここで、セットしたノード変数内のポインタがヌルの場合は、再帰的に呼び出された後のステップ５０２で直ぐに戻されることになる。そして、ステップ５２０でｌを１増加しステップ５１４に戻る。また、ステップ５１４で否定判断された時は本サブルーチンを終了する。尚、ここで否定判断される場合とは、結果的にそのノードが子を持たない葉である場合となる。
【００５８】
図６のステップ３１２の子ノード探索・切り離しサブルーチンを終了すると、得られた子ノード数、子ノードバッファを元に、いったん切り離したノードを再度結合し木構造を作り直す処理を行う。即ち、ステップ３１４の子ノード結合サブルーチンに移行する。
【００５９】
図９の子ノード結合サブルーチンでは、先ず、根から子を辿っていくためにステップ６０２で根のキャラクタへのポインタをノード変数にセットする。次にステップ６０４でポインタ変数ｍを０にセットする。次にステップ６０６でｍが子ノード数より小さいか否かを判断し、肯定判断の時は、次のステップ６０８で子ノードバッファからｍ番目のデータ、即ちキャラクタへのポインタを取得する。
【００６０】
そして、ステップ６１０でそのキャラクタを探索キャラクタとし、ステップ６１２で探索キャラクタの位置がノード変数が示すノードを中心とした第何象限に属するかを調べ、ステップ６１４でそのノードの４つの子のうちその象限に属する子を調べる。そしてステップ６１６で、既に子がいるかいないか、即ち、その象限に当たる子ポインタ変数がヌルでないか否かを判断する。ここで肯定判断の時は、ステップ６１８でその子へのポインタをノード変数にセットしてステップ６１２に戻り、これを繰り返す。また、否定判断の時は、ステップ６２０で探索キャラクタをそのノードのその象限の子として結合処理を行う。即ち、その象限が第０象限であれば、探索キャラクタへのポインタを、そのノードの子ポインタ変数０にセットされる。その後、ステップ６２２でｍを１増加し、ステップ６０６に戻り、これを繰り返す。また、ステップ６０６で否定判断の時は、いったん切り離したノードを木構造のルールに矛盾なく全て結合したので、本サブルーチンを終了し、図６の位置・親子関係更新サブルーチンを終了する。
【００６１】
次に、図１０のチャット負荷軽減サブルーチンについて説明する。先ず、ステップ７０２で、受信したチャットデータに含まれるアカウントＩＤやキャラクタＩＤ等の情報を元に、記憶装置に記憶されているそのプレイヤキャラクタ（以下、発信キャラクタ）の、現在の位置情報等のゲームデータを取得する。この点は上記移動の場合と殆ど同じである。
【００６２】
そして、ステップ７０４でそのプレイヤキャラクタが現在いる仮想空間上の領域が不正でないか判断し、肯定判断の場合は本サブルーチンを終了する。これはゲーム上の都合又はトラブル等で、プレイヤキャラクタが本来ゲーム内で行動できない領域に存在する場合に、ネットワークゲームの世界で矛盾がないようにするための処理である。
【００６３】
次に、ステップ７０６でチャット可能な領域（以下、チャット領域）を発信キャラクタの現在位置を中心として各辺２５ｍ（仮想空間での距離の単位でメートル）に設定する。ここでいうチャット領域とは、図１８でいえばキャラクタＴを中心とした一定の大きさの矩形領域（本実施形態では正方形の領域）１０００をいう。キャラクタの現在の位置がこの範囲に属する場合は、そのキャラクタはチャットデータの受信候補となる。
【００６４】
そして、ステップ７０８でチャット領域の各辺が５ｍ以上か否かを判断し、肯定判断の場合はステップ７１０のチャット人数取得サブルーチンに移行し、現在のチャット領域に属するキャラクタの数（以下、チャット人数）を取得する。尚、この部分の処理は後述する。
【００６５】
そして、ステップ７１２で、ステップ３１０により取得したチャット人数が１２８人以上か否か判断し、肯定判断の時はステップ７１４で各辺を５ｍだけ縮めてステップ７０８に戻り、処理を繰り返す。又、否定判断の時は後半の処理として、図１１のステップ７１６に移行する。ここで、ステップ７１２で否定判断の時はチャット人数が１２８より小さくなるが、ステップ７０８で否定判断、即ちチャット領域の各辺が５ｍの場合でもチャット人数が１２８以上となる非常に密集している場合も、次のステップ７１６に移行することになる。しかしながら、この場合でも後述するようにステップ７３４，７３６で送信の制限を設けているので問題は生じない。尚、チャット可能な人数の上限は１２８に限らないことはいうまでもない。
【００６６】
ここで、図１２のチャット人数取得サブルーチンについて先に説明する
先ず、ステップ８０２でチャットデータ送信の対象とする人数としてのチャット人数というＲＡＭ上の変数を０に初期化し、また、送信対象のキャラクタへのポインタを記憶したチャットバッファをクリアする。ここでチャットバッファはＲＡＭ上に確保された領域である。そして、ステップ８０４でノード変数に根のキャラクタのポインタをセットし、ステップ８０６のチャットループサブルーチンに移行する。
【００６７】
図１３のチャットループサブルーチンでは、先ず、ステップ９０２でノード変数がヌルか否かを判断する。尚、本サブルーチンは、図８の子ノード探索・切り離しサブルーチンの場合と同じように再帰的に呼び出される関数であり、ステップ５０２での処理と同じように、そのノード自身のポインタがヌルの場合はその親の子がいないことを意味する。
【００６８】
そして、ステップ９０４でそのノードの座標値を取得し、ステップ９０６でそのノードが先に定めた矩形領域内か否かを判断する。ここで、矩形領域内か否かの判断は、その矩形を構成する４つの角（点）の座標値とそのノードの座標値のｘ，ｙ成分を大小比較することにより判断できる。ここで、ゲームという性質上、空中に浮くということは想定していないので、横と奥行きとしてのｘ，ｙ座標成分のみ比較すればよく、高さとしてのｚ座標成分まで比較する必要はない。そして、ステップ９０６で肯定判断の場合はステップ９１２でチャット人数に追加し、ステップ９１４でチャットバッファにそのノードのポインタを追加する。そしてそのノードは矩形領域内に存在するので、そのノードの子ノード４つを全て調べる対象（即ち、調べる象限）とし、ステップ９１８に移行する。
【００６９】
また、ステップ９０６で否定判断の時は、ステップ９０８でそのノードが矩形領域のどの方向に範囲外となっているかを調べる。具体的には矩形領域の範囲外の領域は、矩形領域の上，下，左，右と、更に左上，左下，右上，右下の８つの領域に分けられる。図１８で言えば、１から８までの領域である。そして、ステップ９１０で、得られた方向と逆方向の象限に属する子を調べる対象とする。具体的には、そのノードが矩形領域の上にいた場合（図１８でいう１領域）は、第２及び第３象限のみ調べ、下にいた場合（図１８でいう５領域）は、第０及び第１象限のみ調べ、左にいた場合（図１８でいう３領域）は、第０及び第３象限のみ調べ、右にいた場合（図１８でいう７領域）は、第１及び第２象限のみ調べることにする。また、左上にいた場合（図１８でいう２領域）は第３象限のみ調べ、左下にいた場合（図１８でいう４領域）は第０象限のみ調べ、右上にいた場合（図１８でいう８領域）は第２象限のみ調べ、右下にいた場合（図１８でい６領域）は第１象限のみ調べる。尚、図１４（ａ）を参照すると分かりやすい。従って、ステップ９１０で分かる調べる象限の数は１又は２となる
【００７０】
次に、ステップ９１８でカウンタ変数ｋを０に初期化し、ステップ９２０でｋが４より小さいか否かを判断する。否定判断の時は、ステップ９２２でそのｋ象限は上記ステップ９１０又は９１６で調べた、調べる象限か否かを判断する。否定判断の時はステップ９２８でｋを１増加してステップ９２０に戻り、これを繰り返す。また、ステップ９２２で肯定判断の時は、ステップ９２４でそのノードのｋ象限に属する子ノードのポインタ、即ち子ポインタ変数ｋにセットされたポインタをノード変数にセットし、ステップ９２６で、再帰的に本サブルーチンを呼び出す。図８のステップ５１８の場合と同様に、種々の変数等はスタックにプッシュされ、呼び出し先から戻る際にプッシュされるものとする。その後、ステップ９２８に移行する。また、ステップ９２０で肯定判断の場合は、本サブルーチンを終了し、図１２のチャット人数取得サブルーチンを終了する。
【００７１】
次に、図１１のチャット負荷軽減サブルーチンの後半部分に戻る。先ず、ステップ７１６でＲＡＭ上の送信数及び送信長の変数を０に初期化する。そして、ステップ７１８で先ずは発信者の端末装置にチャットデータを送信して送り返す。その分として、ステップ７２０で送信数を１増加するとともに送信長を送信した分だけ加算する。
【００７２】
次にステップ７２２で、カウンタ変数ｊを０に初期化した後、ステップ７２４でｊが得られたチャット人数より小さいか否かを判断する。否定判断の場合は本サブルーチンを終了して図５のステップ２０２に戻る。また肯定判断の時は、ステップ７２６でチャットバッファからｊ番目のデータ、即ちキャラクタデータへのポインタを取得する。
【００７３】
次にステップ７２８で、ステップ７２６で得られたポインタが指すキャラクタデータを参照し、そのキャラクタがプレイヤキャラクタか否かを判断する。自動的にサーバが動作させるいわゆるＮＰＣ、即ちコンピュータキャラクタである可能性もあり、この場合はチャットデータを送信する必要がないので、ステップ７２８で否定判断の場合はステップ７３４まで移行する。
【００７４】
ステップ７２８で肯定判断の時は、ステップ７３０でそのキャラクタを操作するプレイヤの端末装置にチャットデータを送信する。また、ステップ７３２で送信数を１増加するとともに送信長を送信した分だけ加算する。
【００７５】
次のステップ７３４で、送信数が６４以上か否かを判断する。肯定判断の場合は本サブルーチンを終了して図５のステップ２０２に戻る。否定判断の場合は、次のステップ７３６で、送信長が最大値の８１９２以上か否かを判断する。肯定判断の場合は本サブルーチンを終了して図５のステップ２０２に戻る。否定判断の場合は、ステップ７３８でｊを１増加してステップ７２４に戻りこれを繰り返す。ここで、チャット人数の上限と送信数の上限が違うのはＮＰＣの存在によるものである。そして、送信数及び送信長に上限を設けることにより、サーバの負荷に一定の制限を設けている。
【００７６】
尚、本実施形態では、ある特定のキャラクタが発信する所定情報をチャット情報及び移動するキャラクタの移動情報としたが、送信先のキャラクタに共通の情報であれば何でも実現できるということは言うまでもない。例えば、ある共通のイベントや命令を同時に実行させるための情報等が考えられる。
【００７７】
また、本実施形態では、いわゆる所定時間を、モニタの垂直帰線割込の１６ミリ秒としたが、これに限定されるものではない。例えば、画像処理に影響しないように別にタイマ割込みを一定間隔で発生させ、例えば１０ミリ秒に一度の周期で処理するようにしても良い。
【００７８】
【発明の効果】
ネットワークゲームサーバの負荷が最も増大するプレイヤキャラクタの密集エリアでのチャット等の情報送受信において、情報発信しようとするプレイヤキャラクタの仮想空間上の位置を中心とした所定領域内の密集度を素早く検知し、その密集度に応じて情報受信可能な領域としての所定領域を段階的に狭くしていくので、ネットワークゲームサーバの負荷の増大を抑制することができる。
【図面の簡単な説明】
【図１】本実施形態のネットワークゲームサーバと端末装置との接続形態を示す概略図である。
【図２】本実施形態のネットワークゲームサーバの内部構成を示す概略ブロック図である。
【図３】本実施形態の端末装置の内部構成を示す概略ブロック図である。
【図４】本実施形態の端末装置が実行するプログラムの概略フローチャートである。
【図５】本実施形態のネットワークゲームサーバが実行するプログラムの概略フローチャートである。
【図６】本実施形態のネットワークゲームサーバが実行する位置・親子関係更新サブルーチンのフローチャートである。
【図７】位置・親子関係更新サブルーチン内の移動キャラ探索サブルーチンのフローチャートである。
【図８】位置・親子関係更新サブルーチン内の子ノード探索・切り離しサブルーチンのフローチャートである。
【図９】位置・親子関係更新サブルーチン内の子ノード結合サブルーチンのフローチャートである。
【図１０】本実施形態のネットワークゲームサーバが実行するチャット負荷軽減サブルーチンの前半のフローチャートである。
【図１１】本実施形態のネットワークゲームサーバが実行するチャット負荷軽減サブルーチンの後半のフローチャートである。
【図１２】チャット負荷軽減サブルーチン内のチャット人数取得サブルーチンのフローチャートである。
【図１３】チャット人数取得サブルーチン内のチャットループサブルーチンのフローチャートである。
【図１４】（ａ）はキャラクタＡを中心とした周囲をｘ，ｙ座標軸で４つの領域に分け、各々を本実施形態でいうところの０から３までの象限を示す説明図である。（ｂ）は、キャラクタＡを根とした場合の木構造の一例である。（ｃ）は（ｂ）の木構造の一例を、実際のｘ，ｙ座標平面で考えた場合の各キャラクタの接続を示す説明図である。そして、（ｄ）は（ｂ）の木構造の一例を、実際のデータ構造を用いて示した場合である。
【図１５】本実施形態の木構造で、子ノードが属することが可能な領域が、根から子ノードを辿っていくにつれて狭くなる様子を示す説明図である。
【図１６】本実施形態の木構造で、矢印の方向に移動するキャラクタｄに子がいない場合のキャラクタ間の切り離し・結合についての説明図である。
【図１７】本実施形態の木構造で、矢印の方向に移動するキャラクタｃに子がいる場合のキャラクタ間の切り離し・結合についての説明図である。
【図１８】本実施形態の矩形領域で、キャラクタＴを中心とする矩形領域の外側の領域を８つに分けた場合の領域１から８までを示す説明図である。
【符号の説明】
２  ネットワークゲームサーバ
４  端末装置
６  ネットワークゲームサーバのＣＰＵブロック（情報受信手段，送信対象特定手段，情報送信手段，親子関係更新手段，人数取得手段）
８  端末装置のＣＰＵブロック
１０００  矩形領域
【図１】
2004298373.tif 000003
【図２】
2004298373.tif 000004
【図３】
2004298373.tif 000005
【図４】
2004298373.tif 000006
【図５】
2004298373.tif 000007
【図６】
2004298373.tif 000008
【図７】
2004298373.tif 000009
【図８】
2004298373.tif 000010
【図９】
2004298373.tif 000011
【図１０】
2004298373.tif 000012
【図１１】
2004298373.tif 000013
【図１２】
2004298373.tif 000014
【図１３】
2004298373.tif 000015
【図１４】
2004298373.tif 000016
【図１５】
2004298373.tif 000017
【図１６】
2004298373.tif 000018
【図１７】
2004298373.tif 000019
【図１８】
2004298373.tif 000020
【手続補正書】
【提出日】平成16年5月12日(2004.5.12)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ネットワークを介して接続される複数の端末装置と通信することによってネットワークゲームを進行するネットワークゲームサーバであって、
前記ネットワークゲームの仮想空間上の各キャラクタの位置及び前記位置に基づいて木構造で関係付けられたキャラクタ相互の親子関係を記憶した記憶装置と、
前記端末装置から前記端末装置に対応した第１のキャラクタについての所定情報を通信部を介して受信する情報受信手段と、
前記情報受信手段が前記所定情報を受信したとき、前記記憶装置に記憶された前記第１のキャラクタの位置の周囲に所定領域を設定し、前記記憶装置に記憶された前記親子関係に基づいて、前記所定領域の方向に、第２のキャラクタを親キャラクタとした当該子孫キャラクタを探索していき、前記子孫キャラクタが前記所定領域内に存在する場合は、当該子孫キャラクタを送信対象として特定する送信対象特定手段と、
前記送信対象特定手段が特定した前記送信対象に対応する当該端末装置に前記所定情報を通信部を介して送信する情報送信手段と、
を備えることを特徴とするネットワークゲームサーバ。
【請求項２】
前記木構造は、前記第２のキャラクタを根とすることを特徴とする請求項１に記載のネットワークゲームサーバ。
【請求項３】
前記所定領域は、前記第１のキャラクタの位置を中心とした矩形領域であることを特徴とする請求項１または請求項２に記載のネットワークゲームサーバ。
【請求項４】
前記所定情報は、チャット情報であることを特徴とする請求項１乃至請求項３に記載のネットワークゲームサーバ。
【請求項５】
前記所定情報は、仮想空間上で位置変化のあった前記第１のキャラクタの位置変化情報であり、
前記ネットワークゲームサーバは、更に前記情報受信手段が前記位置変化情報を通信部を介して受信したとき、前記位置変化情報に基づいて前記記憶装置に記憶された前記第１のキャラクタの位置及び前記親子関係を更新する親子関係更新手段を備え、
前記送信対象特定手段は、前記親子関係更新手段による更新後の前記第１のキャラクタの位置及び前記親子関係に基づいて送信対象を特定することを特徴とする請求項１乃至請求項３に記載のネットワークゲームサーバ。
【請求項６】
前記ネットワークゲームサーバは、更に前記所定領域内に存在する前記子孫キャラクタの数を数える人数取得手段を備え、
前記送信対象特定手段は、前記人数取得手段により取得したキャラクタ数が所定数を超えた場合は前記所定領域を狭くして再度送信対象を特定することを特徴とする請求項１乃至請求項５のいずれか１項に記載のネットワークゲームサーバ。
【請求項７】
ネットワークを介して接続される複数の端末装置と通信することによってネットワークゲームを進行するネットワークゲームサーバの制御方法であって、
前記ネットワークゲームサーバは、前記ネットワークゲームの仮想空間上の各キャラクタの位置及び前記位置に基づいて木構造で関係付けられたキャラクタ相互の親子関係を記憶した記憶装置を備えており、
前記ネットワークゲームサーバが、前記端末装置から前記端末装置に対応した第１のキャラクタの所定情報を通信部を介して受信するステップと、
前記ネットワークゲームサーバが、前記所定情報を受信したとき、前記記憶装置に記憶された前記第１のキャラクタの位置の周囲に所定領域を設定し、前記記憶装置に記憶された親子関係に基づいて、前記所定領域の方向に、第２のキャラクタを親キャラクタとした当該子孫キャラクタを探索していき、前記子孫キャラクタが前記所定領域内に存在する場合は、当該子孫キャラクタを送信対象として特定するステップと、
前記ネットワークゲームサーバが、前記特定した前記送信対象に対応する当該端末装置に前記所定情報を通信部を介して送信するステップと、
を含むことを特徴とするネットワークゲームサーバの制御方法。
【請求項８】
ネットワークを介して接続される複数の端末装置と通信することによってネットワークゲームを進行するネットワークゲームサーバが実行可能なプログラムであって、
前記ネットワークゲームサーバは、前記ネットワークゲームの仮想空間上の各キャラクタの位置及び前記位置に基づいて木構造で関係付けられたキャラクタ相互の親子関係を記憶した記憶装置を備えており、
コンピュータを、
前記端末装置から前記端末装置に対応した第１のキャラクタの所定情報を通信部を介して受信する情報受信手段、
前記情報受信手段が前記所定情報を受信したとき、前記記憶装置に記憶された前記第１のキャラクタの位置の周囲に所定領域を設定し、前記記憶装置に記憶された前記親子関係に基づいて、前記所定領域の方向に、第２のキャラクタを親キャラクタとした当該子孫キャラクタを探索していき、前記子孫キャラクタが前記所定領域内に存在する場合は、当該子孫キャラクタを送信対象として特定する送信対象特定手段、
前記送信対象特定手段が特定した前記送信対象に対応する当該端末装置に前記所定情報を通信部を介して送信する情報送信手段、
として機能させるためのプログラム。
【請求項９】
コンピュータを、更に前記所定領域内に存在する前記子孫キャラクタの数を数える人数取得手段として機能させ、
前記送信対象特定手段は、前記人数取得手段により取得したキャラクタ数が所定数を超えた場合は前記所定領域を狭くして再度送信対象を特定することを特徴とする請求項８に記載のプログラム。
【請求項１０】
請求項８または請求項９に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１３
【補正方法】変更
【補正の内容】
【００１３】
【課題を解決するための手段】
上記課題を解決するための、本発明の第１の態様は、ネットワークを介して接続される複数の端末装置と通信することによってネットワークゲームを進行するネットワークゲームサーバであって、前記ネットワークゲームの仮想空間上の各キャラクタの位置及び前記位置に基づいて木構造で関係付けられたキャラクタ相互の親子関係を記憶した記憶装置と、前記端末装置から前記端末装置に対応した第１のキャラクタについての所定情報を通信部を介して受信する情報受信手段と、前記情報受信手段が前記所定情報を受信したとき、前記記憶装置に記憶された前記第１のキャラクタの位置の周囲に所定領域を設定し、前記記憶装置に記憶された前記親子関係に基づいて、前記所定領域の方向に、第２のキャラクタを親キャラクタとした当該子孫キャラクタを探索していき、前記子孫キャラクタが前記所定領域内に存在する場合は、当該子孫キャラクタを送信対象として特定する送信対象特定手段と、前記送信対象特定手段が特定した前記送信対象に対応する当該端末装置に前記所定情報を通信部を介して送信する情報送信手段と、を備えることを特徴とする。


【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１９
【補正方法】変更
【補正の内容】
【００１９】
本発明の第２の態様は、ネットワークを介して接続される複数の端末装置と通信することによってネットワークゲームを進行するネットワークゲームサーバの制御方法であって、前記ネットワークゲームサーバは、前記ネットワークゲームの仮想空間上の各キャラクタの位置及び前記位置に基づいて木構造で関係付けられたキャラクタ相互の親子関係を記憶した記憶装置を備えており、前記ネットワークゲームサーバが、前記端末装置から前記端末装置に対応した第１のキャラクタの所定情報を通信部を介して受信するステップと、前記ネットワークゲームサーバが、前記所定情報を受信したとき、前記記憶装置に記憶された前記第１のキャラクタの位置の周囲に所定領域を設定し、前記記憶装置に記憶された親子関係に基づいて、前記所定領域の方向に、第２のキャラクタを親キャラクタとした当該子孫キャラクタを探索していき、前記子孫キャラクタが前記所定領域内に存在する場合は、当該子孫キャラクタを送信対象として特定するステップと、前記ネットワークゲームサーバが、前記特定した前記送信対象に対応する当該端末装置に前記所定情報を通信部を介して送信するステップと、を含むことを特徴とする。


【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００２０
【補正方法】変更
【補正の内容】
【００２０】
本発明の第３の態様は、ネットワークを介して接続される複数の端末装置と通信することによってネットワークゲームを進行するネットワークゲームサーバが実行可能なプログラムであって、前記ネットワークゲームサーバは、前記ネットワークゲームの仮想空間上の各キャラクタの位置及び前記位置に基づいて木構造で関係付けられたキャラクタ相互の親子関係を記憶した記憶装置を備えており、コンピュータを、前記端末装置から前記端末装置に対応した第１のキャラクタの所定情報を通信部を介して受信する情報受信手段、前記情報受信手段が前記所定情報を受信したとき、前記記憶装置に記憶された前記第１のキャラクタの位置の周囲に所定領域を設定し、前記記憶装置に記憶された前記親子関係に基づいて、前記所定領域の方向に、第２のキャラクタを親キャラクタとした当該子孫キャラクタを探索していき、前記子孫キャラクタが前記所定領域内に存在する場合は、当該子孫キャラクタを送信対象として特定する送信対象特定手段、前記送信対象特定手段が特定した前記送信対象に対応する当該端末装置に前記所定情報を通信部を介して送信する情報送信手段、として機能させる。そして、コンピュータを、更に前記所定領域内に存在する前記子孫キャラクタの数を数える人数取得手段として機能させ、前記送信対象特定手段は、前記人数取得手段により取得したキャラクタ数が所定数を超えた場合は前記所定領域を狭くして再度送信対象を特定することを特徴とする。
【手続補正５】
【補正対象書類名】図面
【補正対象項目名】図１３
【補正方法】変更
【補正の内容】
【図１３】
2004298373.tif 000021
【手続補正６】
【補正対象書類名】図面
【補正対象項目名】図１４
【補正方法】変更
【補正の内容】
【図１４】
2004298373.tif 000022