はじめに
ロールプレイングゲームに「町の人」と呼ばれるキャラクターがいます。町の中をぶらぶらと歩いて、主人公が話しかけると、何らかの情報を提供してくれる人たちです。彼らは、その情報提供という役目から、主人公が話しかけやすいように同じような場所を、ときどき立ち止まったりしながら歩いています。
実は僕、そんな彼らを見てると、「たまには好き勝手に動きたいんじゃないの？」とか、「本当はお腹が減ってて、急いで家に帰りたいんじゃないの？」とか想像しちゃうんですよね。そんなわけで今回は、町の人たちを縦横無尽に歩かせるプログラムを作ってみました。名づけて『アイちゃんの大冒険』。主人公の女の子アイちゃんとその仲間たちが、元気に町の中を駆け回るアプレットです。
対象読者
ゲームプログラムに興味がある方や、経路探索プログラムに興味がある方を対象とします。また、Java初心者の方には、楽しめる教材として役に立つことと思います。
必要な環境
アプレットの実行には、Javaを動作させることの出来るブラウザーが必要です。もし、お使いのブラウザーでアプレットが動かない場合は、Java ソフトウェアの無料ダウンロードより、最新の Java Runtime Environment を入手してください。
また、コンパイルにはJ2SE Development Kit(JDK) 1.4以上が必要です。
画面説明
簡単に画面の説明をしておきましょう。
左上にあるのが全体マップ。グレーの部分が通行可能な場所で、白い部分は建物などの進入できない場所になってます。主人公は赤い点、それ以外のキャラは黄色い点で表され、主人公の経路探索の様子が、ラインで示されます。左下には、町の現在の状況、および経路探索のパフォーマンスをチェックするための情報を表示しています。
右側にあるのが拡大マップ。真ん中の赤い服の女の子が主人公。頭の上に出るアイコンは、「！」が目的地に到着したことを、「？」が経路の再探索が行われたことを表します。
経路探索の特徴
このプログラムの特徴はキャラクターの経路探索にあります。経路探索のアルゴリズムには様々なものがあり、特に、迷路で最短距離を求めるアルゴリズムはすでに優れたものが存在しています。しかし、ロールプレイングゲームの町のマップなどは、必ずしも迷路になってるわけではなく、今回のように大勢がリアルタイムに移動する場合もあって、厳密な最短経路の探索よりも、消費メモリの少なさと処理速度が優先されます。
そこで、目的地までの障害物回避に主眼を置いて、中継点を結ぶことで、キャラクターの移動経路を決める、新たなアルゴリズムを考案してみました。アルゴリズムの大まかな流れはこうなります。
- 現在地と目的地を直線で結び、中間点を設定する
- 中間点が進入不可能な位置にある場合は、近くの場所を中継点とする
- 今度は、現在地と中継点で同じ処理を行う
以上の処理を、障害物に当たることなく、「水平線」または「垂直線」で構成されるようになるまで、再帰的に繰り返します。つまり、次の中継点に直角に曲がるだけで到達できるレベルまで、どんどん直線を分割していくわけですね。また、自分の近くを詳細に、遠くを大まかに検索することで、中継点を少なく保つ手法をとっています。
なかなか文章だけではイメージがつかみにくいでしょうから、これはもう、実際にアプレットを見てもらうのが一番だと思います。経路の分割の様子がリアルタイムで分かるようになってます。
このアルゴリズムの長所は、少ないメモリ消費量にあります。特に、マップがいくら広くなっても、それに比例して消費メモリが増えることはありません。むしろ、広大な空間のマップを得意としています。今回のマップだと、一人当たり最大で10数個の中継点をもつだけで、あらゆる場所に移動することが出来ます。
逆に短所は、迷路のような複雑な地形には向かないことと、最短距離を通らないことです。でもまあ、今回は、移動するのが「町の人」なんで、多少寄り道したとしても、ご愛嬌ってことで許してやってください。
ソースの説明
まず、大まかなクラスの説明です。
TownAppletクラスとMainPanelクラスがGUIを構成し、TownMapクラスとPeopleクラスが町と人々のデータを管理しています。経路探索アルゴリズムを実装しているのが、RouteSearchクラスとNodeクラス。この記事では、その経路探索に関連するクラスを詳しく解説することにします。
Nodeクラスの解説
Nodeクラスは、経路探索結果の座標情報を保持する単方向リンクリストです。マップ上のxy座標と、次のノードの参照を持っており、目的地の場合は次のノードの参照がnullになります。キャラクターはこのNodeをたどっていくことによって、目的地へとたどり着くことが出来ます。
public class Node { /** x座標 */ public int x; /** y座標 */ public int y; /** 次のノード */ private Node next; /** * 座標は(0, 0)で初期化されます。 */ public Node() { x = 0; y = 0; next = null; } /** * 引数で座標を初期化します。 * @param p ノードの座標 */ public Node(Point p) { x = p.x; y = p.y; next = null; } /** * 引数で座標を初期化します。 * @param x ノードのx座標 * @param y ノードのy座標 */ public Node(int x, int y) { this.x = x; this.y = y; next = null; } /** * 次のノードを返します。 * @return 次のノード */ public Node getNext() { return next; } /** * 次のノードを設定します。 * @param next 次のノード */ public void setNext(Node next) { this.next = next; } /** * ノードを次のノードとの間に挿入します。 * @param node 挿入するノード */ public void insert(Node node) { node.setNext(next); next = node; } /** * 次のノードを取り除きます。 */ public void removeNext() { next = next.getNext(); } }
RouteSearchクラスの解説
経路探索アルゴリズムを実装したクラスで、その中心的役割はsearchRouteメソッドとsearchRelayNodeメソッドに集約されます。
public void searchRoute(Node node, int level) { // 次に進むノードを取得 if (node == null) return; Node nextNode = node.getNext(); // 終端なら探索終了 if (nextNode == null) return; // 対象のノードが進入不可能な位置にあるなら探索終了 if (!isStreet(node) || !isStreet(nextNode)) return; // 一直線に進めるなら探索終了 if (isStraight(node)) return; // 進めない場合は、中継ノードを求め挿入 Node relayNode = searchRelayNode(node); if (relayNode != null) { node.insert(relayNode); // 余分なノードを除去 if (isStraight(relayNode, nextNode.getNext())){ relayNode.removeNext(); } // 再帰的に探索 if (level >= SEARCH_LEVEL) { searchRoute(relayNode, ++level); } searchRoute(node, ++level); } // 最大ノード数を集計 int count = countNode(node); nodeMax = Math.max(nodeMax, count); }
このメソッドのポイントは再帰的に呼び出されるというところです。やってることはシンプルで、次のノードとの間に障害物があれば、中継ノードを挿入しているだけです。また、再帰階層の深さに応じて、経路探索の精度を変えています。深い階層で呼び出された場合を、「自分の近くを検索している」と見なし、中継ノードとその次のノードの間も探索しています。どれくらいの深さからを自分の近くと見なすかについては、RouteSearchクラスの定数SEARCH_LEVELで設定可能になっています。経路探索アルゴリズムのパフォーマンスは、この定数である程度調整可能です。
また、アバウトに探索した遠い部分の経路に関しては、キャラクターが近づいてから、再探索するようになってます。アプレットを見ると、歩いている途中で頭の上に「？」マークが出て経路が変わることがあると思いますが、あれが再探索のタイミングです。この仕組みによって、使用するノード数を抑えることが可能になってます。
private Node searchRelayNode(Node node) { Node nextNode = node.getNext(); // 中間点を求める int x = (node.x + nextNode.x) / 2; int y = (node.y + nextNode.y) / 2; // 座標はマップソース単位に x = x - x % TownMap.SOURCE_SIZE; y = y - y % TownMap.SOURCE_SIZE; Node relayNode = new Node(x, y); // 次のノードとの位置関係で場合分けする if (node.x == nextNode.x) { // 上下に移動可能な場所を探す for (int d=0; d <= TownMap.MAP_W; d += TownMap.SOURCE_SIZE) { if (isStreet(relayNode.x + d, relayNode.y)) { relayNode.x = relayNode.x + d; break; } else if (isStreet(relayNode.x - d, relayNode.y)) { relayNode.x = relayNode.x - d; break; } } } else if (node.y == nextNode.y) { // 左右に移動可能な場所を探す for (int d=0; d <= TownMap.MAP_H; d += TownMap.SOURCE_SIZE) { if (isStreet(relayNode.x, relayNode.y + d)) { relayNode.y = relayNode.y + d; break; } else if (isStreet(relayNode.x, relayNode.y - d)) { relayNode.y = relayNode.y - d; break; } } } else { // 1回曲がって到達可能か？ if (isStraight(node.x, node.y, node.x, nextNode.y) && isStraight(node.x, nextNode.y, nextNode.x, nextNode.y)) { relayNode.x = node.x; relayNode.y = nextNode.y; } else if (isStraight(node.x, node.y, nextNode.x, node.y) && isStraight(nextNode.x, node.y, nextNode.x, nextNode.y)) { relayNode.x = nextNode.x; relayNode.y = node.y; } else { // 斜めに移動可能な場所を探す int dx = node.x < nextNode.x ? 1 : -1; int dy = node.y < nextNode.y ? 1 : -1; for (int d = 0; d <= TownMap.MAP_W; d += TownMap.SOURCE_SIZE) { if (isStreet(relayNode.x + d, relayNode.y - d * (dx * dy))) { relayNode.x += d; relayNode.y -= d * (dx * dy); break; } else if (isStreet(relayNode.x - d, relayNode.y + d * (dx * dy))) { relayNode.x -= d; relayNode.y += d * (dx * dy); break; } } } } return relayNode; }
このメソッドは、2点のノードの中継点を求めるメソッドです。このアルゴリズムでは、いかに最適な中継点を求めるかが経路の質を左右します。とはいえ、このメソッドも、そんなに難しいことはやってません。
- 直角に1回曲がって到達できる場合は、その角を中継点とする
- それが出来ない場合は、2点間の中点（アタリの場合はその近くの点）を中継点とする
の二つの法則に基づいて、中継点を探しています。両メソッドとも難しい処理は行ってませんが、アルゴリズムにとって、コアな部分がシンプルなことは、とても喜ばしい傾向といえますね。
残された課題
この経路探索プログラムですが、まだまだ改善の余地は残されています。たとえば、探索の結果ノードの数が増えたときに、遠い位置のノードからリリースしていく作りにすれば、最大ノードを減らすことができそうです。また、多少面倒にはなるのですが、Nodeをオブジェクトとせずに、Peopleクラスの中でint型の配列で管理すれば、オブジェクト生成のオーバーヘッドが省け、メモリおよび処理速度の点で改善が見込めるでしょう。
経路の最適化にいたってはほとんど手をつけてないので、様々なアプローチがありそうですね。経路探索後の無駄なノードを除去する最適化メソッドの実装や、中継点の設定時にゴールへの直接的な経路を探索する、などの方法が考えられます。興味がある方は、色々と試してみてください。
最後に、グラフィックを作成してくれた、HALとaitarohに感謝の念を捧げ、この記事を終わりにしたいと思います。
