こんにちは。主に新規ゲームのUnity開発を行っている細野です。

2Dゲームでは、画面内の表示位置を2次元の座標系で管理しますが、
画面内の表示座標系の他に、マップチップと呼ばれる正方形スプライトを並べたタイル単位の座標系を扱うゲームも数多く存在します。

このような2D整数座標に対しても、ベクトルや三角関数・行列・複素数などで定義される演算を用いることで、複雑な処理をシンプルに表現できるケースが多く存在します。
この記事では、2D整数座標の基本的な構造から数学を取り入れた演算について、ゲーム中での具体例を挙げて説明を行います。

また、応用しやすいように、理論や数学的な意味についての解説も行います。

向きと座標クラスの定義

座標計算の際、現在の座標の上下左右のそれぞれの位置について何かの処理を行いたいことが頻繁にあります。
その際に向きと座標を列挙したテーブルを用意すると便利です。

この記事では、以下のような座標を表す構造体と方向を表す列挙型を導入します。
以下の節では、こちらの構造体を拡張していきます。

// セル上の位置を示す構造体
public struct Point
{
    public int x;
    public int y;
}
// 方向を示す列挙型
public enum Direction
{
    // x軸に正の方向
    Right,
    // y軸に正の方向
    Up,
    // x軸に負の方向
    Left,
    // y軸に負の方向
    Down
}

画面上の座標系は下図の通りになっています。

では、早速こちらの問題を元に説明を行います。

問題1

座標上に立っているキャラクターは上下左右の4方向に動くことができる。現在の場所からキャラクターが移動できる場所を深さ優先探索によって求めよ。

この問題を素直にコードに直すと以下のようになります。深さ優先探索についての説明はここでは割愛します。
ループ内では、方向を示す列挙型を列挙しつつ現在の位置からそれぞれの位置に一歩進んだ座標を計算しています。


public class Sample1
{
    void Dfs (Point pos)
    {
        if (!IsPassable(pos) || isMovable[pos]) {
          return;
        }
        isMovable[pos] = true;
        foreach (Direction direction in Enum.GetValues(typeof(Direction))) {
            var nextPos = pos + Point.Delta (direction);
            Dfs (nextPos);
        }
    }
}

今いる場所の右上左下を順に探索し、通行可能かつ未踏の位置に一歩進むことを繰り返します。４方向すべて進むことが出来ない場合一歩後退し、残りの場所を探索します。

この実装にあたって、ループ内で用いられている、向かっている方向に1マス進んだ座標を取得するメソッドDeltaを作成します。

単位円上で90度ずつ変換させていった時、Y座標は、

0, 1, 0, -1, 0, 1, 0, -1, ...

と変化するので、

i % 2 - i % 4 / 3 * 2

といった一般項を与えることもできますが、テーブルを作る方が素直に書けます。

public struct Point
{
    /* (中略) */
    // 原点から、指定した方向に1歩進んだ位置座標を取得します
    public static Point Delta (Direction dir)
    {
        return delta [(int)dir];
    }
    static readonly Point[] delta = {
        new Point (1, 0),
        new Point (0, 1),
        new Point (-1, 0),
        new Point (0, -1)
    };
    // 演算子オーバーロードによる座標の加算メソッド
    public static Point operator+ (Point left, Point right)
    {
        return new Point (left.x + right.x, left.y + right.y);
    }
}

三角関数の導入

ここで作成した、deltaのx,yの値は指定した向きに対応するコサイン、サインの値に対応しています。

	0° (Right)	90° (Up)	180° (Left)	270° (Down)
cos	1	0	-1	0
sin	0	1	0	-1

角関数を導入し、deltaテーブルを90度ごとのCos,Sinテーブルに置き換えると、先ほどの方向を座標に変換するメソッドはこのように書くこともできます。

public static readonly int[] Cos = { 1, 0, -1, 0 };
public static readonly int[] Sin = { 0, 1, 0, -1 };

// 原点から、指定した方向に1歩進んだ位置座標
public static Point Delta (Direction dir)
{
    return new Point (Cos [(int)dir], Sin [(int)dir]);
}

座標の回転

次に、パズルゲームなどでも頻出する、座標の回転について説明します。

問題2

座標のリストとして与えられた範囲を、右または左に90度回転したあとの座標を求めよ。
範囲は(0,0) を起点として回転するものとする。

回転後の座標を求めるのに、三角関数の公式を利用します。これは回転行列の計算にも現れる公式です。

$$ x’ = x * cosθ – y * sinθ \\ y’ = y * sinθ + x * cosθ $$

回転方向を示す列挙型および、回転の公式を利用します。

public enum Rotation
{
    // 反時計周りに0度の回転
    Front,
    // 反時計周りに90度 (π/2[rad])の回転
    Left,
    // 反時計周りに180度 (π[rad])の回転
    Back,
    // 反時計周りに270度 (3π/2[rad])の回転
    Right
}

public Point Rotate (Rotation rotate)
{
    return new Point (
        Cos [(int)rotate] * x - Sin [(int)rotate] * y,
        Sin [(int)rotate] * x + Cos [(int)rotate] * y
    );
}

これを用いたコードは以下のようになります。

public void Main ()
{
    var block = new Point[] {
        new Point (0, 0),
        new Point (1, 0),
        new Point (-1, 0),
        new Point (0, 1)
    };
    block = block
        .Select (_ => _.Rotate (Rotation.Right))
        .ToArray ();
}

複素数の利用

回転後の座標を求めるのに、複素数を用いて解くこともできます。
そのためには、座標系をx軸を実数軸、y軸を虚数軸と見た複素数として扱うことを考えます。

座標系を複素数として扱うためには、座標同士の和と積を定義する必要があります。

public struct Point
{
    // (中略)
    // xを実軸、yを虚数軸とみた複素数として扱っても和の扱いは変化しません
    public static Point operator+ (Point left, Point right)
    {
        return new Point (left.x + right.x, left.y + right.y);
    }
    // xを実軸、yを虚数軸とみた複素数の積を返します
    public static Point operator* (Point left, Point right)
    {
        return new Point (
            left.x * right.x - left.y * right.y,
            left.x * right.y + right.x * left.y
        );
    }
}

複素数の積については、

$$A * B = C$$

の時、絶対値はそれぞれの絶対値の積

$$|C| = |A| * |B|$$

偏角はそれぞれの和

$$ \arg(C) = \arg(A) + \arg(B) $$

になっています。

複素数平面上で見てみると、点$A$, $B$を通る円の半径が絶対値を示しています。

円とX軸との交点を確認すると、$A$の絶対値は1.5, $B$の絶対値は2.5, $C$の絶対値は3.75となっています。
また、X軸と直線$OC$のなす角（$C$の偏角）は$A$,$B$の偏角の和になっています。

この複素数の定義を導入すると、単位円の積の形で回転を実現できるため、回転メソッドはもっと簡潔に書くことが可能です。

public Point Rotate(Rotation rotate)
{
    return delta[(int)rotate] * this;
}

なす角の大小比較

三角関数と複素数の考え方は、直線のなす角を求めるのに利用できます。

問題3

(0,0)にいるプレイヤーキャラは現在真上にいるキャラを選択している。時計回りに隣のキャラを順に選択せよ。
ただし、角度が同じ場合、プレイヤーキャラに近い方から選択するものとする。

原点から見た(0,1)と点との角度（なす角）を求め、最も小さくなるものを取り出せば良さそうです。

上図のように$OA$,$OB$のなす角は$B$の偏角から$A$の偏角を引くと求められます。

先ほど、複素数の積を求めることで偏角の和を求めましたが、偏角の差を求めるためには、複素数部分の符号を逆転した共役複素数を利用します。

共役複素数

$ A = a + ib $
の時、Aの共役複素数$ \bar{A} $は
$ \bar{A} = a – ib $

図のように、$ \bar{A} $の偏角は$A$の偏角の符号を逆転させたものになるため、
$B$の偏角から$A$の偏角を引いた角度であるなす角は
$B$の偏角に$ \bar{A} $の偏角を加えた角度は、$ (B * \bar{A}) $の偏角で得ることが出来ます。

// xを実軸、yを虚数軸とみた複素数と共役な複素数に対応するベクトルを返します
public Point Conj ()
{
    return new Point (x, -y);
}

こうして求まった座標に対して、atan2関数を適用するとなす角が求まります。

public int Compare(Point left, Point right)
{
    // なす角ベクトル座標
    var convertedLeft = left * startingPoint.Conj();
    var convertedRight = right * startingPoint.Conj();
    // なす角(Rad)
    var leftAngle = Mathf.Atan2(left.y, left.x);
    var rightAngle = Mathf.Atan2(right.y, right.x);
    if (Mathf.Abs(leftAngle - rightAngle) < Mathf.Epsilon)
    {
        return 0;
    }
    else
    {
        return (leftAngle - rightAngle < 0) ? -1 : 1;
    }
}

この比較関数に沿って座標のリストを昇順にソートすると、開始座標から見て左回りの、降順にソートすると右回りに並んだ座標が返ります。

しかし、この方法では浮動小数点の計算が発生してしまいます。atan2を使わず整数演算のみで、なす角の大小比較をできないでしょうか。

atan2関数は座標の偏角を求めることができる関数でしたが、座標からタンジェントは$y/x$を計算することで求まります。

そして、タンジェントの値は図のように

$$ 0 < x < \pi/2, \\ \pi/2 < x < \pi, \\ … $$
と$ π \over 2$ごとの範囲で単調増加なので、偏角が座標平面上でどの象限に位置するか、$tanθ$の値が比較できれば偏角の大小を比較できそうです。

まず、偏角を$ π \over 2$で割って切り捨てた値を求める関数を作成します。
x軸上、y軸上以外の点の場合、この関数は象限を返します。

// 原点以外の点について、座標を4分割した時の位置を返します
// すなわち、x軸との角度をt (rad) とすると
// 0      &lt;= t &lt; pi/2   のとき 0
// pi/2   &lt;= t &lt; pi     のとき 1
// pi     &lt;= t &lt; pi<em>3/2 のとき 2
// pi</em>3/2 &lt;= t &lt; 2*pi   のとき 3
// を返します。

public int Quadrant {
    get {
        if (x > 0 && y >= 0) {
            return 0;
        }
        if (y > 0) {
            return 1;
        }
        if (x < 0) {
            return 2;
        }
        return 3;
    }
}

同一象限上の場合、傾きを比較します。

$$ y_{1}, x_{2} \neq 0 $$ のとき
$$ y_{1}x_{1} – y_{2}x_{2} $$

$ x_{1}, x_{2} $ は同符号なので、両辺に$x_{1}x_{2}$を掛けても符号は変化しません。よって、比較関数は

$$ y_{1}x_{2} – x_{1}y_{2} $$

と書けます。この式は

$ x_{1}, = 0, x_{2} = 0 $ の時も前後の象限で成り立ちます。

この条件に加えて、「傾きも同一の場合、原点により近いものから選択する」という条件を加えれば良さそうです。

上記を踏まえると比較関数は以下のようになります。

class AngleComparer : IComparer<Point>
{
    public int Compare (Point left, Point right)
    {
        var <em>left = (left * startingPoint.Conj ()).Conj ();
        var _right = (right * startingPoint.Conj ()).Conj ();
        return new int [] {
            _left.Quadrant - _right.Quadrant,
            _left.y * _right.x - _left.x * _right.y,
            Math.Abs (_left.x) - Math.Abs (_right.x),
            Math.Abs (_left.y) - Math.Abs (_right.y)
        }.FirstOrDefault (</em>  _ != 0);
    }
    static readonly Point startingPoint = new Point (0, 1);
}

var _left = (left * startingPoint.Conj ()).Conj ();

のところでは、先ほど求めた、なす角に加えて、座標を時計回りに変換するため、さらに複素共役な値を求めています。

サンプルコードは下記になります。

public void Main ()
{
    var positionList = new Point [] {
        new Point (2, 3),
        new Point (-1, -1),
        new Point (3, 6),
        new Point (-6, 4),
        new Point (-4, 1),
        new Point (0, 5),
        new Point (0, -1),
        new Point (-4, -5),
        new Point (-3, -2),
        new Point (-4, 0),
        new Point (-2, 0),
        new Point (3, -2),
        new Point (6, -4),
        new Point (2, 4),
        new Point (3, 0),
        new Point (-1, -8),
        new Point (5, -1)
    };
    var comparer = new AngleComparer ();
    Array.Sort (positionList, comparer);
    foreach (var position in positionList) {
        Console.WriteLine (position);
    }
}
/*
=>
(0, 5)
(2, 4)
(3, 6)
(2, 3)
(3, 0)
(5, -1)
(3, -2)
(6, -4)
(0, -1)
(-1, -8)
(-4, -5)
(-1, -1)
(-3, -2)
(-2, 0)
(-4, 0)
(-4, 1)
(-6, 4)
*/

実行前と実行後の座標のリストの順序は下図のようになっています。

こうして、Y軸に正の方向から時計回りに列挙することができました。

終わりに

ベクトルや外積、行列というと3Dゲームで使用される知識というイメージが強いと思います。
また、三角関数も浮動小数点演算での処理というイメージがあり、整数の座標計算で利用するイメージはなかったかもしれません。

けれども、2Dのゲームで必要になってくる処理に対しても、
こういった数学の知識を活用できる事例はたくさんあります。

また、今回2Dのタイル単位の座標の操作を意図したクラス構成となっていますが、
画面内の表示計算に用いたり、3Dの座標系に使用する数学の理解にも繋がるのではないでしょうか。

この記事がお役に立てれば幸いです。

C#によるゲーム制作のための2D整数座標入門