元競技プログラマのゲーム開発
はじめに
angoo株式会社でプログラマとして働いている皿海と申します。
業務での担当箇所はゲームAIとグラフィックが主です。
突然ですが、あなたは競技プログラミングを知っていますか？
競技プログラミングとは、与えられた課題をプログラミングを使って速く正確に解決する競技のことです。
課題には、簡単な四則演算だけで解けるものもあれば、聞いたこともない知識を前提に発想力を求められるような難しいものもあります。
僕はこの競技プログラミングに1年間ほど熱を上げていました。
AtCoderという競技プログラミングサイトで毎週のようにコンテストに参加し、最高で上位7%ほどのレートになりました。
この記事では、競技プログラミングを軽く説明しつつ、ゲーム会社での実際の業務で競技プログラミングがどのように関わるのかを紹介したいと思います。
もっと速く！
実際の業務の話の前に、一般的な話をしたいと思います。
計算量とは
競技プログラミングでは、プログラムの計算量を考えさせる問題がよく出ます。計算量とは、単純に言うとプログラムが完了するのに必要な計算回数です。同じことをするプログラムであれば、計算量は少ないほうが良いです。
簡単な例として、整数$${0 \le x, y \le 100}$$について、$${x + y = 100}$$となる$${(x, y)}$$の組み合わせを全て出力せよ。という問題を考えてみます。
書いてあるものをそのままコードにすると
解法1.
loop x 0 to 100:
loop y 0 to 100:
if x + y = 100:
print (x, y)のようになると思いますが、少し考えると、
解法2.
loop x 0 to 100:
y = 100 - x
print (x, y)でもよいと気付くでしょう。
ループの回数を考えると、解法1では $${100 ^ 2 = 10000}$$ 回なのに対し、解法2では$${100}$$回で済みます。
計算量の指標として、解法1は$${O(N^2)}$$のアルゴリズム、解法2は$${O(N)}$$のアルゴリズム、といったような表現をします。
ゲーム開発と計算量
一方、ゲーム開発においてもプログラムの速さは非常に大切です。
ゲームでは、キャラクターの動きが滑らかに見えるように、1秒間に30回や60回ほど描画を更新することが一般的です。
つまり与えられた時間は0.033秒～0.017秒ほどしかなく、この短い時間内にすべての計算を終わらせる必要があります。
これはとても短いように感じますが、逆にどれほどの計算をしたら0.017秒かかるのでしょうか？
このような問いも、競技プログラミング経験者であれば、
制限時間1秒だと$${O(N)}$$で$${N = 10^7}$$程度は計算できるからその$${1/60}$$で$${N = 10^5}$$程度の計算はできる。
などと、すぐに概算できるでしょう。
これは、負荷の高い処理のあるゲームを作るときに役に立ちます。
例えば弾幕も敵も大量に出るシューティングゲームを作ろう！と思った時に、計算量の考え方を知っていれば、
N個の弾とM個の敵との衝突計算を単純に行うと$${O(N \times M)}$$だから、弾も敵も300個ずつ出すと計算時間を使い切ることになるな。
と考えたり、
もっと出せる数を増やしたいな。計算量を削減できるアルゴリズムを探してみると、四分木空間分割という手法があるらしいぞ。実装してみよう。
と方針を考えたりできます。
もちろん、ゲームによっては計算量を全く考えなくても問題ないでしょう。
実際、僕もまだ業務で計算量が問題となりアルゴリズムを変更することが必要になったことはありません。
しかし、いざボトルネックとなる処理が現れたときを考えると、諦めて妥協するのではなく計算量を改善する手立てを持っていた方が、心が穏やかになります。
あっ、これ競技プログラミングでやったところだ
先ほど、業務で計算量の改善が必要になったことはないと言いました。
じゃあ競技プログラミング必要ないじゃん、と思いましたか？
では、もう一つ僕がメリットに感じたことを発表します。
それはアルゴリズムとデータ構造についての理解が深まる点です。
データ構造は、配列やグラフなどのデータの置き方であり、アルゴリズムはどのようにデータを扱って問題を解くかを意味します。
計算機科学の本などを読めばこれらの知識は得られると思います。
それに対して、競技プログラミングはいわば演習問題です。
どのアルゴリズムとデータ構造を使うかを選択して自分で実装することを繰り返すうちに、自分の手になじんだ武器が増えていきます。
この武器が業務に生きた例を数点紹介したいと思います。
事例１ 最短経路探索
ゲームにおいて経路探索は頻出のアルゴリズムのため、主要なゲームエンジンには汎用的な経路探索用のシステムが用意されています。
しかし諸々の事情からそれらを使わず、自前でCPUが障害を避けながら目的地に近づくアルゴリズムを組む必要がありました。
ゲームの経路探索として最もシンプルなやり方は、CPUが到達できる空間を静的にグリッド分割して、隣り合うグリッドをエッジでつないでグラフ構造を構築することです。
この事例ではそれに加えて以下の改造を行いました。
CPUの位置を原点としたグリッド分割を行う
エッジごとに異なる重みをつける
障害物がある場所では重みに非常に大きな値を入れる
あとは通常のグラフと同様に扱えるため、A*探索を実装して最短経路を求め、その経路のはじめにどのグリッドへ進むのかを出力すると問題が解決します。
事例２ CPUの行動制御ツール
CPUの行動制御ツールとしてBehaviorTreeの亜種のようなGUIツールを作成しました。
もともと社内で使われていた思考制御ツールにできることが少なかったため、複雑な制御をするためにはプログラムを書かなければならず、プログラマの負担となっていました。
既製品のツールを買って使用しても良かったのですが、プロジェクト用に改造することは分かっていました。
であれば、自分で1から作ったほうがいじりやすいだろうと思い、自作することにしました。
……というのは半ば建前で、自分で作ってみたかったというのが大きいです。
競技プログラミングで何度もグラフ構造を作っているうちに、もっと巨大な構造を作りたくなったのです。
簡単にツールの説明をしておきます。
このツールの基本の動作はノードの実行です。
ここでいうノードの実行とは、ノードごとに決められた処理を行って、成功・失敗・実行中のいずれかを親ノードに返すことです。
多くのノードは
自分の処理を実行する。
失敗・実行中だと、それを親ノードに返す。
成功すると子ノードを実行し、子ノードの結果を親ノードに返す。
という動作をするため、連綿と処理が繋がっていきます。
すごく細かい話ですが、ゲームAIで有名なBehavior Treeと違うのは、現在実行しているノードから次に実行するノードが繋がっている点です。
これによって、次に実行するノードを見て処理を変えることが可能になります。
これが必要だったため、既製品を使いませんでした。
機会があれば詳しい解説などもしたいと思います。
その他の事例
ほかにも、連想配列のキーとして、持っているデータリストの要素を全てXORしたものを使っていたですが、これって被るんじゃないかと気付いたこともありました。
最終的にもっと冗長な構造体をキーとして使うことにしました。
グラフだけかと思われそうなので、負け惜しみで書いてみました。
まとめ
この記事を見て、競技プログラミングとゲーム開発って結構関連あるんだなと思った方も、大して関係ないじゃんと思った方も、どちらもいるかもしれません。
僕はレートが伸び悩んでいるときに他にやりたいことができて競技プログラミングから離れてしまいましたが、競技プログラミングの経験が生きたなと思うことがしばしばあります。
これを読んで競技プログラミングに興味を持たれた方は、ぜひ一度チャレンジしてみてください！
熱中できる趣味になるかもしれません。
また、これを読んでゲーム会社に興味を持たれた方は、ぜひ一緒にゲームを作りましょう！
楽しいですよ！
