１．はじめに
メタルギアソリッドというゲームで久しぶりに遊んでいたのですが、プレイヤーの操作するキャラクターが監視カメラや敵の兵隊に視認されるのはどういうアルゴリズムなのだろうと、唐突に気になりました。そこで、せっかくなのでプログラミングの勉強を兼ねて、実際に自分で作ってみることにしました。
本記事では、どのように実装し、どのようにバグを潰し、そしてどのような教訓を得たのかを書きました。プログラミングを勉強し始めた方にとっては、「こんな失敗をしないように注意しましょう」という反面教師的な内容になっています。
２．問題設定
以下の仕様を想定してみます。
プレイヤー
座標平面上に、1人のプレイヤーがいる。プレイヤーはじっとしていて動かない。動くと面倒なので。
プレイヤーの身体は点とみなして良く、その点の座標を($p_x$, $p_y$)とする。
監視カメラ
座標平面上に、監視カメラが$N$台設置されている。$N$は1以上の整数である。監視カメラはじっとしていて動かない。動くと（略）
各監視カメラのレンズは点とみなして良く、その点の座標を($x_i$, $y_i$)とする。
ただし、$i$はその監視カメラが何台目のものかを表す、1以上$N$以下の整数である。
各監視カメラの視認範囲
各監視カメラがプレイヤーを視認できる距離は、$d_i$ ($d_i$ > 0)である。
各監視カメラのレンズの向きを表す角度を$e_i$、カメラの視野を表す角度を$f_i$とする。
$e_i$はカメラの向きを表す直線と$x$軸の正の向きとのなす角であり、$e_i$, $f_i$ともに0°以上360°未満である。
つまり、各監視カメラがプレイヤーを視認できる範囲は、次の図のような半径$d_i$、中心角$f_i$のおうぎ形の周および内部となる。
パラメータの入出力
パラメータの入力は、コンソールから次の形式で行う。
$p_x$ $p_y$
$N$
$x_1$ $y_1$ $d_1$ $e_1$ $f_1$
(中略)
$x_i$ $y_i$ $d_i$ $e_i$ $f_i$
(中略)
$x_N$ $y_N$ $d_N$ $e_N$ $f_N$
各行のパラメータは半角スペースで区切るものとする。
また、各監視カメラの情報を入力される度に、その監視カメラがプレイヤーを視認できたかどうか判定し、視認できたら「視認できた」、視認できなかったら「視認できなかった」と出力するものとする。
３．データ構造の実装
初めにお断りしておきますが、今回はあくまでおうぎ形の周および内部に点が含まれる条件を考えることを目的としていますので、カプセル化やオブジェクト指向などを厳密に実装することはしません。と言うか、できません。 他にも色々と至らぬ点があるでしょうが、何卒ご容赦ください。
まず、プレイヤーの位置情報を取り扱うクラスPlayerを作ります。クラスPlayerは$x$座標と$y$座標をもち、必要に応じてその値を返す機能をもちます。
なお、プレイヤーについてはわざわざクラスにする必要はないかも知れませんが、もしこれがシステム開発だと仮定したとき、プレイヤーが沢山いるような状況を想定する可能性もありますから、「プレイヤーとはかくかくしかじかの情報や機能をもった存在なんだぜ」という考え方を明示しておくことにします。また、クラスPlayerはあくまで考え方（ややこしく言うとオブジェクトの抽象的概念）であって、本当の意味で存在するプレイヤー（ややこしく言うと実体）については後で作成します。例を挙げるなら、人類という抽象的な概念があって、その実体として私やあなたが存在している、という感じでしょうか。
class Player {
private double x; // プレイヤーのx座標
private double y; // プレイヤーのy座標
public Player(double x, double y) {
this.x = x;
this.y = y;
}
public double getX() {
return this.x;
}
public double getY() {
return this.y;
}
}
せっかくなので、カプセル化についても少し説明してみます。クラスPlayerでは、double型の変数x, yに値を格納している訳ですが、プログラムを書く人（常に私とは限りません。誰かと協力したり、誰かに丸投げするかも知れません！）が無秩序に変数の値を参照・代入できる状況下では、本来の想定とは外れた処理（バグ）を記述してしまう危険があります。そこで、プログラムを書く人（達）がクラスPlayerに対して行える処理を明示するために、上記のコードでは次のように決めてあります。
- 変数xは、直接値を書き換えない！⇒型宣言の前にprivateと書く。すると、変数xに直接値を代入するような「x = 100;」とかは書けなくなる（書くとエラーになる）。
- 変数xには、実在するプレイヤーをつくるときにx座標を代入したい！⇒実在するプレイヤーをつくるときに必ず呼び出すコンストラクタ（クラスと同じ名前のメソッド。メソッドとは処理の流れをまとめたもの）の中で、変数xに引数の値を代入する。
- 変数xの値を後から参照できるようにしたい！⇒専用のメソッドgetX()をつくる。型宣言の前にpublicと書いておくと、様々な場所から呼び出せるようになる。
- 変数yについても同様。
このように、必要な情報や処理をまとめ、でたらめに書き換えることのないようにした仕組みがクラスだったりカプセル化だったりします。プログラムを書く手間は少し増えますが、その代わりにバグをつくる危険を減らせる仕組みを、Javaは用意してくれているのです。開発の規模が大きくなればなるほど、このような仕組みが大変重要になってきます。
次に、監視カメラの情報を取り扱うクラスCameraを作ります。クラスCameraはx, y座標、視認できる距離、向きと視野角を表す角度をもちます。今は最低限の構成になっていますが、今後処理を実装するにつれて、メソッドを追加していくことになります。
class Camera {
private double x; // 監視カメラのx座標
private double y; // 監視カメラのy座標
private double distance; // 監視カメラが視認できる距離
private double dirAngle; // 監視カメラの向き(direction)を表す角度
private double viewAngle; // 監視カメラの視野角
public Camera(double x, double y, double d, double e, double f) {
this.x = x;
this.y = y;
this.distance = d;
this.dirAngle = e;
this.viewAngle = f;
}
}
４．アルゴリズムの実装
入力
どこにどんな情報を格納するかは大体決まりましたので、いよいよ処理の流れを記述していきます。まず、mainメソッドからです。Javaのプログラムを実行する際は、最初に必ずmainメソッドが呼び出されます。そのため、プログラム全体の中でただ一つだけ、mainメソッドを記述しなければなりません。とりあえず、コンソール上から入力された数値を読み取る部分だけ作成してみます。
class CameraTest {
public static void main(String[] args) {
// 入力
Scanner sc = new Scanner(System.in);
// プレイヤー
double px = sc.nextDouble(); // プレイヤーのx座標
double py = sc.nextDouble(); // プレイヤーのy座標
Player player = new Player(px, py);
// 監視カメラ
int N = sc.nextInt(); // 監視カメラの台数
for (int n = 0; n < N; n ++) {
// 監視カメラごとの入力・処理
double x = sc.nextDouble(); // 監視カメラのx座標
double y = sc.nextDouble(); // 監視カメラのy座標
double d = sc.nextDouble(); // 監視カメラが視認できる距離
double e = sc.nextDouble(); // 監視カメラの向き(direction)を表す角度
double f = sc.nextDouble(); // 監視カメラの視野角
Camera camera = new Camera(x, y, d, e, f);
}
sc.close();
}
}
staticとかScannerとかnextDoubleとかnextIntとか何やねん、ていう感じですが、これらを説明し始めると本記事の趣旨から大分脱線してしまうため、説明は割愛させていただきます。とにかく、上記まで作成した時点で、仕様通りに入力された数値は問題なく読み取られます。
監視カメラはプレイヤーを視認できるか？
もちろん、数値を読み取っただけでは無意味なので、実際にカメラがプレイヤーを視認できるかどうか判定する処理を追加していきましょう。先ほど作成したCameraクラスの中で、プレイヤーの位置情報を読み取ってそのプレイヤーを視認できるかどうか判定するメソッドfindPlayerを作成してみます。このメソッドこそが、本記事のキモになる部分です。
// Cameraクラスの中に追加する
public boolean findPlayer(Player player) {
double px = player.getX();
double py = player.getY();
// 距離による判定
double d = Math.sqrt(Math.pow(this.x - px, 2) + Math.pow(this.y - py, 2));
if (d > this.distance) {
return false;
}
// 角度による判定
double a = Math.toDegrees(Math.atan2(py - this.y, px - this.x));
double aMin = this.dirAngle - this.viewAngle/2;
double aMax = this.dirAngle + this.viewAngle/2;
if (a < aMin || aMax < a) {
return false;
}
return true;
}
では、処理の流れを簡単に説明していきます。キーワードは「距離」と「角度」の2つです。
まず「距離」では、その名の通り、監視カメラとプレイヤーの距離が監視カメラの視認できる距離よりも小さいかどうかを判定します。2点($x_i$, $y_i$), ($p_x$, $p_y$)間の距離は
\sqrt{(x_i - p_x)^2 + (y_i - p_y)^2}
で求められます。これが視認距離$d_i$以下であれば視認できる可能性がありますが、$d_i$より大きければ論外と言えるでしょう。そこで、距離で判定する部分では後者の場合にとっととfalse（偽）を返してしまい、その後の無駄な処理をしなくて済むようにしています。
次に、「距離」の条件をクリアした後の「角度」の処理ですが、2点を通る直線の傾きからその直線とx軸のなす角の大きさを求める関数$\arctan$（高校数学「三角関数」「逆関数」）が利用できますので、2点($x_i$, $y_i$), ($p_x$, $p_y$)に対してこれらを組み合わせることにより、
\arctan{\frac{y_i - p_y}{x_i - p_x}}
で求めることができます。また、カメラが視認できる角度の範囲は$e_i - \frac{f_i}{2}$以上$e_i + \frac{f_i}{2}$以下で表されますので、傾きから求めた角度がこの範囲にあればtrueを、なければfalseを返すようにします。
出力
ここまでくれば、完成したも同然です。先ほど作成したメソッドfindPlayerはboolean型の値を返しますから、その値に応じて結果を出力するだけです。
それでは、完成（？）したプログラムを載せておきます。
import java.util.Scanner;
class CameraTest {
public static void main(String[] args) {
// 入力
Scanner sc = new Scanner(System.in);
// プレイヤー
double px = sc.nextDouble(); // プレイヤーのx座標
double py = sc.nextDouble(); // プレイヤーのy座標
Player player = new Player(px, py);
// 監視カメラ
int N = sc.nextInt(); // 監視カメラの台数
for (int n = 0; n < N; n ++) {
// 監視カメラごとの入力・処理
double x = sc.nextDouble(); // 監視カメラのx座標
double y = sc.nextDouble(); // 監視カメラのy座標
double d = sc.nextDouble(); // 監視カメラが視認できる距離
double e = sc.nextDouble(); // 監視カメラの向き(direction)を表す角度
double f = sc.nextDouble(); // 監視カメラの視野角
Camera camera = new Camera(x, y, d, e, f);
if (camera.findPlayer(player)) {
System.out.println("視認できた");
} else {
System.out.println("視認できなかった");
}
}
sc.close();
}
}
class Player {
private double x; // プレイヤーのx座標
private double y; // プレイヤーのy座標
public Player(double x, double y) {
this.x = x;
this.y = y;
}
public double getX() {
return this.x;
}
public double getY() {
return this.y;
}
}
class Camera {
private double x; // 監視カメラのx座標
private double y; // 監視カメラのy座標
private double distance; // 監視カメラが視認できる距離
private double dirAngle; // 監視カメラの向き(direction)を表す角度
private double viewAngle; // 監視カメラの視野角
public Camera(double x, double y, double d, double e, double f) {
this.x = x;
this.y = y;
this.distance = d;
this.dirAngle = e;
this.viewAngle = f;
}
public boolean findPlayer(Player player) {
double px = player.getX();
double py = player.getY();
// 距離による判定
double d = Math.sqrt(Math.pow(this.x - px, 2) + Math.pow(this.y - py, 2));
if (d > this.distance) {
return false;
}
// 角度による判定
double a = Math.toDegrees(Math.atan2(py - this.y, px - this.x));
double aMin = this.dirAngle - this.viewAngle/2;
double aMax = this.dirAngle + this.viewAngle/2;
if (a < aMin || aMax < a) {
return false;
}
return true;
}
}
５．実行、そして・・・
いよいよ、監視カメラの性能を確かめるときがやってきました。試しに、プレイヤーのいる座標を(10, 10)として、監視カメラを3台使ってテストしてみましょうか。まずは1台目の処理を進めるところまで入力してみます。
10 10
3
10 0 12 90 30
視認できた
※2018/12/5 訂正
上記において3行目最後の数値が60になっていたので、訂正いたしました。
入力した情報を図で表すと、下のような状況です。ばっちりプレイヤーを視認できていますね。テンションが上がって参りました。
では2台目、いってみましょう。
10 5 10 180 90
視認できなかった
2台目は視認できませんでしたが、まったく問題ありません。なぜなら、下図のような状況だからです。距離の条件はクリアできていたのですが、監視カメラの向きが悪かった訳ですね。今回も判定はばっちりです！
それでは、ラスト3台目でフィナーレといきましょうか。
10 16 8 270 120
視認できなかった
最後は、監視カメラのすぐ目の前にいる間抜けなプレイヤーをばっちり視認……できてへんやん。シューティングゲーム的に言うと、まさかの正面安置みたいな状況ですね！（投げやり）
６．そしてデバッグへ・・・
ということで楽しいデバッグ作業の始まりなのですが、今回はここで切って後編に続きたいと思います。かつての私と同じように「え、なんで駄目なん？」と思った方は、ぜひ後編を読む前に考えてみてください。
なぜ、3台目の監視カメラはプレイヤーを視認できる状況だったにも関わらず、視認できなかったのでしょうか？また、どのようにプログラムを修正すれば良いでしょうか？