リソースの場合分けとビット演算 - 実践ゲーム製作メモ帳2

例えば自動生成のマップチップのようなものを想像しよう。上下左右に道があって、道のパターンによって使うマップチップが変わる。上に道があればこれ、左と右に道があればこれ、右と下ならこれ……。よくあるシチュエーションだ。
マップチップじゃなくてもいい。入力のパターンに複数の組み合わせがあって、出力が多種多様に変化するもの。入力がただの Enum（列挙型）一つなら Switch 文で事足りるんだけど……というケース。

泥臭く if 文で書くことはできるけど、汚いし、実は C# とかで 128*128 のマップを全部走査したりすると、結構な時間がかかったりする。じゃあ、どうやって書くのがスマートか。*1

というわけでたまには真面目なプログラミングの TIPS でも。しかし、あんまりこういう TIPS ってないよね。多分みんなスーパープログラマーだから必要ないんだろうね。

普通に書くとこんな感じ。関数名や列挙型の意味は適当に推測してほしい。

bool top    = checkRoad( x, y - 1 );
bool left   = checkRoad( x - 1, y );
bool right  = checkRoad( x + 1, y );
bool bottom = checkRoad( x, y + 1 );

if ( top ) {
	if ( left ) {
		if ( right ) {
			if ( bottom ) {
				return Cross;		// 十字路
			} else {
				return TBottom;		// Ｔ字路
			}
		} else {
			if ( bottom ) {
				return TRight;		// Ｔ字路
			} else {
				return TopLeft;		// Ｌ字路
			}
		}
	} else {
		if ( right ) {
			if ( bottom ) {
				return TLeft;		// Ｔ字路
			} else {
				return TopRight;	// Ｌ字路
			}
		} else {
			if ( bottom ) {
				return TopBottom;	// Ｉ字路
			} else {
				return Top;		// 行き止まり
			}
		}
	}
} else {
	if ( left ) {
		if ( right ) {
			if ( bottom ) {
				return TTop;		// Ｔ字路
			} else {
				return LeftRight;	// Ｉ字路
			}
		} else {
			if ( bottom ) {
				return LeftBottom;	// Ｌ字路
			} else {
				return Left;		// 行き止まり
			}
		}
	} else {
		if ( right ) {
			if ( bottom ) {
				return RightBottom;	// Ｌ字路
			} else {
				return Right;		// 行き止まり
			}
		} else {
			if ( bottom ) {
				return Bottom;		// 行き止まり
			} else {
				return None;		// 八方ふさがり
			}
		}
	}
}

やってられん。一応三項演算子を使えば同じ処理でもう少し簡略に書くこともできるが、やたら奇妙なコードになるし、だからどうしたという感じ。

top ? left ? right ? bottom ? return Cross          // 十字路
                            : return TBottom        // Ｔ字路
                   : bottom ? return TRight         // Ｔ字路
                            : return TopLeft        // Ｌ字路
           : right ? bottom ? return TLeft          // Ｔ字路
                            : return TopRight       // Ｌ字路
                   : bottom ? return TopBottom      // Ｉ字路
                            : return Top            // 行き止まり
    : left ? right ? bottom ? return TTop           // Ｔ字路
                            : return LeftRight      // Ｉ字路
                   : bottom ? return LeftBottom     // Ｌ字路
                            : return Left           // 行き止まり
           : right ? bottom ? return RightBottom    // Ｌ字路
                            : return Right          // 行き止まり
                   : bottom ? return Bottom         // 行き止まり
                            : return None;          // 八方ふさがり

というわけで、どうするかというと、ビット演算を使う。 top と left と right と bottom が 16 通りのパターンを作るのだから、それぞれが被らないようにビットを与えてあげればいい。
例えば top が 0001、left が 0010、right が 0100、bottom が 1000 といった具合だ。

int direction = 0;
if ( checkRoad( x, y - 1 ) ) direction |= 0x01; // top: 0001
if ( checkRoad( x - 1, y ) ) direction |= 0x02; // left: 0010
if ( checkRoad( x + 1, y ) ) direction |= 0x04; // right: 0100
if ( checkRoad( x, y + 1 ) ) direction |= 0x08; // bottom: 1000

こうすると、例えば top と left を満たしている場合 0011 = 3 となる。top と right と bottom なら 1101 = 13。奇妙なことに、これらの組み合わせは一度も被ることなく、十進数にして 0〜15 の数字に変換されるというわけだ。

じゃあ、後はこんなテーブルを用意してあげればいい。

EDirec direc_table[] =
{
    None,
    Top,          // 1    top
    Left,         // 2    left
    TopLeft,      // 3    top,left
    Right,        // 4    right
    TopRight,     // 5    top,right
    LeftRight,    // 6    left,right
    TBottom,      // 7    top,left,right
    Bottom,       // 8    bottom
    TopBottom,    // 9    top,bottom
    LeftBottom,   // 10   left,bottom
    TRight,       // 11   top,left,bottom
    RightBottom,  // 12   right,bottom
    TLeft,        // 13   top,right,bottom
    TTop,         // 14   left,right,bottom
    Cross,        // 15   all
};

このテーブルはループの外、或いは関数の外に書いておくのが賢明だ*2。まとめると、こんな感じになる。

EDirec direc_table[] =
{
    None,
    Top,          // 1    top
    Left,         // 2    left
    TopLeft,      // 3    top,left
    Right,        // 4    right
    TopRight,     // 5    top,right
    LeftRight,    // 6    left,right
    TBottom,      // 7    top,left,right
    Bottom,       // 8    bottom
    TopBottom,    // 9    top,bottom
    LeftBottom,   // 10   left,bottom
    TRight,       // 11   top,left,bottom
    RightBottom,  // 12   right,bottom
    TLeft,        // 13   top,right,bottom
    TTop,         // 14   left,right,bottom
    Cross,        // 15   all
};

EDirec checkDirection( int x, int y )
{
    int direction = 0;
    if ( checkRoad( x, y - 1 ) ) direction |= 0x01; // top: 0001
    if ( checkRoad( x - 1, y ) ) direction |= 0x02; // left: 0010
    if ( checkRoad( x + 1, y ) ) direction |= 0x04; // right: 0100
    if ( checkRoad( x, y + 1 ) ) direction |= 0x08; // bottom: 1000

    return direc_table[ direction ];
}

ふつくしい……（個人の感想です）。
で、実測値として、実際にステージ生成で使っているコードを持ってきて試してみた（色々処理が入っているのでそのまま処理速度でないことはご留意）。試行回数はちょっと少な目で、32*32のチャンクを50個*3。これでも有為な差が出るんだから、C# の if 文ってほんと遅い。