例えば自動生成のマップチップのようなものを想像しよう。上下左右に道があって、道のパターンによって使うマップチップが変わる。上に道があればこれ、左と右に道があればこれ、右と下ならこれ……。よくあるシチュエーションだ。
マップチップじゃなくてもいい。入力のパターンに複数の組み合わせがあって、出力が多種多様に変化するもの。入力がただの 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; // T字路 } } else { if ( bottom ) { return TRight; // T字路 } else { return TopLeft; // L字路 } } } else { if ( right ) { if ( bottom ) { return TLeft; // T字路 } else { return TopRight; // L字路 } } else { if ( bottom ) { return TopBottom; // I字路 } else { return Top; // 行き止まり } } } } else { if ( left ) { if ( right ) { if ( bottom ) { return TTop; // T字路 } else { return LeftRight; // I字路 } } else { if ( bottom ) { return LeftBottom; // L字路 } else { return Left; // 行き止まり } } } else { if ( right ) { if ( bottom ) { return RightBottom; // L字路 } else { return Right; // 行き止まり } } else { if ( bottom ) { return Bottom; // 行き止まり } else { return None; // 八方ふさがり } } } }
やってられん。一応三項演算子を使えば同じ処理でもう少し簡略に書くこともできるが、やたら奇妙なコードになるし、だからどうしたという感じ。
top ? left ? right ? bottom ? return Cross // 十字路 : return TBottom // T字路 : bottom ? return TRight // T字路 : return TopLeft // L字路 : right ? bottom ? return TLeft // T字路 : return TopRight // L字路 : bottom ? return TopBottom // I字路 : return Top // 行き止まり : left ? right ? bottom ? return TTop // T字路 : return LeftRight // I字路 : bottom ? return LeftBottom // L字路 : return Left // 行き止まり : right ? bottom ? return RightBottom // L字路 : 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 文ってほんと遅い。
- 場合分け版
- 8.63ms
- 8.84ms
- 8.28ms
- 8.85ms
- 8.61ms
- ビット演算テーブル版
- 6.88ms
- 7.40ms
- 6.38ms
- 7.13ms
- 6.95ms
まあ……これに加えてGameObjectのInstantiateすると 5 チャンクで 100ms とか行くんだけど……。
まとめ
ビット演算で掛け算割り算を置き換えたり構造体を圧縮して高速化する時代は正直終わったけど、コードをシンプルに書いたり、ネットワーク越しに情報を渡す時など、まだまだ彼らが役立つときもあったりする。いつでもスマートに書けるようになっていれば、きっとあなたの力になってくれるはずだ。
*4