テラリウム徹底攻略ガイド 障害物回避アルゴリズムの実装 泉 祐介＋デジタルアドバンテージ 2002/06/21

---

　では、ここまでに解説した障害物回避アルゴリズムを実際のコードの形にした移動ルーチンを見ていくことにしよう。

　今回は、前々回および前回の記事で紹介したKAnimalクラスを継承したKYAnimalという名前のクラスを新たに作成し、その新しいクラスに本稿で説明している障害物回避機能を組み込んでいる。

　KYAnimalクラスのソース・コードは次のリンクからダウンロードすることができる。

→KYAnimalクラス（C#版）をダウンロードする
→KYAnimalクラス（VB.NET版）をダウンロードする

　なお、後述しているように、KYAnimalクラスではKAnimalクラスのBeginMovingメソッドをオーバーライドしているのだが、KAnimalクラスのBeginMovingメソッドは仮想メソッドではないため、前回で示したKAnimalクラスのままではオーバーライドすることができない。そのため、KAnimalクラスのBeginMovingメソッドが仮想メソッドになるように修正する必要がある（C#の場合、メソッド名の前に“virtual”を付ける）。この修正を行ったKAnimalクラスのソースは次のリンクからダウンロードできる。

→修正したKAnimalクラス（C#版）をダウンロードする
→修正したKAnimalクラス（VB.NET版）をダウンロードする

■ObstacleAreaクラス

　上記のKYAnimalクラスのソース・コードには、KYAnimalクラス以外にもいくつかのクラスが含まれている。その1つがこのObstacleAreaクラスである。このクラスは障害物に関する情報を扱う。“Obstacle”は「じゃま（物）、障害（物）」という意味だ。

　このクラスのコンストラクタの書式は次のようになっている。

ObstacleArea(OraganismState os, int myCellRadius)

　引数のosに障害物となる生物、myCellRadiusに自分自身の半径をそれぞれ指定する。コンストラクタが呼び出されると、障害物のまわりの通行できない部分を計算し、障害物の占める領域と合わせた障害領域の情報を内部のフィールドに格納する。

　このクラスには上のアルゴリズムを実装するのに必要ないくつかのメソッドを持っている。詳しい内容については、決して読みやすくはないかもしれないが、ソース・コードの方を参照して欲しい。本稿でも、このクラスのメソッドの機能については必要に応じて説明していく。

FindNextPositionメソッド

　さて、KYAnimalクラスにあるこのメソッドが、障害物回避ルーチンの核心といえるメソッドである。先に説明したアルゴリズムに従って経由する点を計算し、その点の座標を返す。書式は次のとおり。

Point FindNextPosition(Point dept, Point dest, int depth);

　引数のdeptには出発地、destには目的地をそれぞれ指定する。出発地には、通常は自分が現在いる座標を指定する。deptは“deperture”、destは“destination”の略である。

　引数depthは、再帰の深さが深くなりすぎるのを防ぐための引数だ。テラリウムでは、生物が考えることのできる時間があまり長くないため、再帰呼び出しを深くしすぎるのは得策ではない。この引数には、後どのぐらいの深さだけ再帰を認めるか、という値を指定する。例えば、この引数に5を指定すれば、後5回（深さ5）だけ再帰できるという意味になる。

　これからこのメソッドの中身を説明していくが、このメソッドは少し長いので、いくつかの部分に分けて解説することにする。

■一番近くにある障害物を探索する

　まずは、直線経路上に障害物が存在するかどうか、存在するとすればどの障害物が一番近くにあるか、といったことを調べる必要がある。

　次の部分では、生物自身が認識している障害領域の1つ1つに対して、目的地との直線経路上にあるかどうかを調べる。経路上にあった場合は、出発地とその障害物との距離を計算し、出発地から一番近くにある障害領域が変数に格納されるようになっている。

// 一番近くにある障害物を探索する ObstacleArea obstacle = null; double minDist = Double.PositiveInfinity; foreach(ObstacleArea a in foundObstacleAreas) {   if(a.CrossedBy(dept, dest) || a.ContainsNoBoundary(dept)) {     double dist = Distance(dept, a.Creature.Position);     if(dist < minDist) {       obstacle = a;       minDist = dist;     }   } }

一番近くにある障害物を探索するFindNextPositionメソッド内のコード

　変数obstacleが一番近くにある障害領域を格納するための変数である。初期値としてnullを格納しているが、これは経路上の障害物が見付かっていないことを表す。また、minDistはその障害物までの距離を格納する変数である。初期値として格納しているDouble.PositiveInfinityは正の無限大を表す定数だ。

　foundObstacleAreasはすべての障害領域の情報が格納されているKYAnimalクラスのフィールドである。このフィールドの値は、後述するUpdateObstacleAreasメソッドで更新されるようになっている。

　CrossedByは障害領域が2点を結ぶ直線経路上にあるかどうかを返すメソッド、ContainsNoBoundaryは指定した点が障害領域に含まれるかどうかを返すメソッドである。ContainsNoBoundaryメソッドでは境界線上の点は領域に含まれるとは見なさない。DistanceはKYAnimalの内部で定義した次のようなメソッドで、指定した2点間の距離を返す。

static private double Distance(Point p, Point q) {   int dx = p.X - q.X;   int dy = p.Y - q.Y;   return Math.Sqrt(dx * dx + dy * dy); }

2点間の距離を返すKYAnimalクラスのDistanceメソッド

　さて、説明を読んで気づいた読者も多いだろうが、このコードでは直線経路上にある障害領域のほかに、出発地を含んでいる障害領域も考慮している。そもそも、障害物のまわりに設定する通行できない部分を、自分の半径と同じだけの大きさをとるようにすれば、自分の座標（位置）がほかの障害領域の中に含まれることはない。しかし、実際には通行できない部分を自分の半径よりも少しだけ大きめにとっているため、自分の座標がほかの障害領域の中に含まれてしまう場合も存在するのである。

　自分が障害領域の中にいるときに、障害物回避アルゴリズムをそのまま適用してしまうと、障害物に衝突してしまってうまく移動できない場合がある。そのため、障害領域の中にいるような場合は、いったんその障害領域の角に移動するようにし、元のアルゴリズムが適用できるようにする。

　なお、わざわざ通行できない部分を大きめにとっているのには理由がある。テラリウムでは、生物はグリッド単位で領域を占有することは冒頭にも述べたが、移動もグリッド単位で行われる。従って、単純な直線を引いた時点では障害領域と交わることがなくても、実際にグリッド単位で移動させてみると障害物に衝突する、ということが生じる可能性があるのである。そこで今回は通行できない部分を少し大きめにとることで、この問題を回避することにした。

■経由点の候補を2つ挙げる

　先のコードによって、一番近くにある障害領域がどれであるかを得ることができる。次に行うのは、その障害領域をよけるために経由する点の候補を2つだけ挙げる作業だ。

// 障害物がなければ目的地に直行 if(obstacle == null || depth <= 0) {   return dest; } // 経由点の候補を2つに絞る IList cornerList; if(obstacle.ContainsNoBoundary(dept)) {   cornerList = obstacle.GetBypassCorners(dept);   foundObstacleAreas.Remove(obstacle); } else {   cornerList = obstacle.GetBypassCorners(dest); }

経由点の候補を2つ挙げるためのFindNextPositionメソッド内のコード

　直線経路上に障害領域が見付からなかった場合は、目的地そのものを経由する点として返す。これは、目的地に直線経路で移動することを意味している。一方、障害領域が見付かったときは、経由する点の候補を2つだけ挙げることになる。

　すでに述べたとおり、出発地がいずれかの障害領域の内部にあるときは、いったんその障害領域の角に移動する。一方、出発地が障害領域の外にあるときは、アルゴリズムの所で述べたとおり、目的地と障害領域との関係によって2つの候補を選ぶ。

　GetBypassCornersメソッドはこの両方の場合に適用できるメソッドだ。出発地が障害領域の内部にあるときは、出発地（障害領域の内部にある点）と障害物との位置関係によって候補を決めるので、出発地を引数に指定している。一方、出発地が障害領域の外にあるときは、目的地（通常は障害領域の外部にある点）と障害領域との関係によって候補を決めるので、目的地を引数に指定している。いずれの場合もYRectangle.Corner型の値のリスト（cornerList）が返される。YRectangle.Corner型は領域の角を中心から見た相対的な位置で表すために定義した列挙体で、TopLeft（左上）、TopRight（右上）、BottomLeft（左下）、BottomRight（右下）のいずれかの値をとる。

■経由点を決める

　残る作業は、ほかの障害領域に含まれている経由点の候補があればその候補の位置を移動し、2つのうち近い方を経由点に決めることだけである。

// そのうちで近い方の点を経由点とする Point p = GetBypassPosition(   obstacle, (YRectangle.Corner)cornerList[0], 10); Point q = GetBypassPosition(   obstacle, (YRectangle.Corner)cornerList[1], 10); if(Distance(dept, p) < Distance(dept, q)) {   return FindNextPosition(dept, p, depth - 1); } else {   return FindNextPosition(dept, q, depth - 1); }

経由点を決めるためのFindNextPositionメソッド内のコード

　GetBypassPositionはKYAnimalクラスのメソッドで、YRectangle.Corner型の値（領域の中心から見た相対的な位置）として得られた経由点を、実際の座標に変換するメソッドである。また、経由点がほかの障害領域に含まれている場合には、経由点の移動も同時に行うようにしている。

　後は、出発地と得られた点との距離をそれぞれ計算して、より近い方の点に向かって移動するだけだ。アルゴリズムの所で述べたとおり、得られた経由点も直線経路で移動できる点であるとは限らないので、このFindNextPositionメソッドを再帰的に呼び出している。

　ところで、GetBypassPositionメソッドの内容は次のようになっている。

protected Point GetBypassPosition (ObstacleArea obstacle, YRectangle.Corner corner, int depth) {   Point cPoint = obstacle.GetCornerPosition(corner);   if(depth <= 0) return cPoint;   foreach(ObstacleArea a in foundObstacleAreas) {     if(a != obstacle && a.Contains(cPoint)) {       return(GetBypassPosition(a, corner, depth - 1));     }   }   return cPoint; }

実際に経由する点を返すKYAnimalクラスのGetBypassPositionメソッド

　GetCornerPositionは、YRectangle.Cornerで表された角を、実際の座標に変換するメソッドである。その座標がほかの障害領域に含まれていないかどうかを調べ、含まれていれば経由する点の候補をその領域の対応する角に変更する。このとき、変更した先の角もまた別の障害領域に含まれている可能性もあるので、ここでも再帰呼び出しを行っている。ほかの障害領域に含まれていなければ、最初に得た実際の座標を返す。

INDEX
	[連載]テラリウム徹底攻略ガイド
	第6回 より高度な障害物回避
	障害物の扱い方
	障害物回避のためのアルゴリズム
	障害物回避アルゴリズムの実装
	KAnimalクラスにあるメソッドのオーバーライド

　

「連載　 テラリウム徹底攻略ガイド」

＠ITメールマガジン　新着情報やスタッフのコラムがメールで届きます（無料）