今回は Slither.io (スリザリオ)のようなオンラインゲームを作ります。
これまでにオンライン対戦ゲームをいくつか作成してきましたが、当たり判定の処理がネックとなり参加できるユーザー数を一桁にするという制限をつけてきました。競技プログラミングであれこれ勉強してきたので、この知識を動員して多人数であっても動かすことができるゲームを作ってみることにしました。
Slither.io (スリザリオ)のようなオンラインゲームを作ります。なぜスリザリオなのかというと特に理由はありません。いつもお世話になっているT.Umezawa氏がスリザリオ大好き人間なのです。
ということで、Slither.io (スリザリオ)のようなオンラインゲームを作ります。プレイヤーはNPC(non player character)含めて500人、フィールドに点在する餌の数も10,000個を超えます。課題としてはやりがいがありそうです。
パケット法で計算量を減らす
ゲームとして成立させるためには、当たり判定の処理を高速化しなければならないことは容易に想像できます。問題はどのようなアルゴリズムを採用するかです。
最初は二分探索法で高速化できるのではないかと考えていました。
当たり判定に関する考察 単純な総当たりと二分探索法による高速化
この方法はX座標でソートして二分探索法で当たり判定が必要な要素とのみ当たり判定をする方法なのですが、試作品として作ったゲームではあまりスムーズには動いてくれませんでした。
原因として考えられることは以下が考えられます。
フィールドが横方向だけでなく縦方向にも長い。そのため平均するとすべてのX座標に1個以上のオブジェクトが存在するため二分探索法で範囲を限定してもまだ多すぎる。
ではどうするか？ パケット法を使います。
パケット法は列や平面をパケットという単位に分割してパケットごとにデータを管理することで効率的に計算や操作をすることができる方法です。
具体的にはフィールド全体を一辺の長さが100の正方形に分割します。この方法だと当たり判定の対象はそんなに多くはなりません。
またプレイヤーの体長が長くすると当たり判定の対象として取得したオブジェクトのなかに自分自身が大量に含まれることになり、無駄に処理に時間がかかってしまいます。これを回避するために効果的に当たり判定の対象から自分自身を取り除く処理が必要です。これは辞書を使えばよさそうです。キーをプレイヤーにすれば、パケット内のキーがひとつしか存在しない場合はそもそも当たり判定の処理は必要ないこともわかります。
通信量を減らす
もうひとつ減らさなければならないものがあります。それがデータ通信量です。オンラインゲームでは各プレイヤーの情報をユーザーの端末に送信しなければならないのですが、不必要なデータを送ってしまうと通信量がヤバいことになります。
スマホユーザーならパケ死確実です。
このゲームではプレイヤーや餌を円で表現しているのですが、これだと大量の座標を送信しなければならなくなります。しかも最初はjson形式で送っていたのでサーバーから送信されるデータが大きくなりすぎていたのです。大量のデータを送信するためサーバーには負荷がかかり、ユーザーの端末にも大量のデータが送りつけられるので処理にも時間がかかります。
json形式だと文字数が多くなるのでカンマ区切りの文字列で必要な座標だけ送ります。餌なら座標だけで充分です。プレイヤーの体であればさらに太さが必要です。プレイヤー名やその他の情報はプレイヤーの頭だけに持たせれば充分なはずです。また常にディスプレイに描画すべきオブジェクトの座標を送るのではなく、全部送るのは最初の一回だけでそれ以降は差分のみを送ることにします。これで通信量を大幅に減らすことができました。
定義するクラスについて
定義するクラスは以下のとおりです。
CirclesMap クラス
Player クラス
Game クラス
GameHub クラス
Circle クラス
餌やプレイヤーの身体を描画するためのクラスです。
CirclesMap クラス
Circleオブジェクト同士の当たり判定を高速におこなうためのクラスです。
Player クラス
プレイヤーとNPCを操作するためのクラスです。
Game クラス
ゲーム全体を進行させるためのクラスです。
GameHub クラス
サーバーサイドとクライアントサイドでデータを相互に送受信するためのクラスです。
具体的なコードは次回以降で示します。
