Slither.io (スリザリオ)のようなオンラインゲームを作りたい（1）の続きです。独自のクラスを定義することで当たり判定の高速化を実現します。
Contents
定数について
名前空間はSnakeGameとします。インデントが深くなるので以降は名前空間部分は省略して書きます。
定数の意味は以下のとおりです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
namespace SnakeGame { public class Constant { public const int PLAYERS_MIN_COUNT = 500; // プレイヤーとNPCの総数の最小値 public const int FOODS_INIT_COUNT = 15000; // 初期の餌の個数 public const int CIRCLES_MAX_COUNT = 20 * 10000; // 後述するCircleオブジェクトの最大生成数 public const int FIELD_RADUUS = 5000; // フィールドの半径 public const double PLAYER_SPEED = 2.0; // プレイヤーの移動速度 public const int PLAYER_MIN_LENGTH = 16; // プレイヤーの初期の長さ public const int CELL_SIZE = 100; // セル（後述）のサイズ } } |
Circleクラスの定義
餌やスネークの身体を描画するためにCircleクラスを定義します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
public class Circle { public double X = 0; // 円が描画される座標 public double Y = 0; public double Radius = 0; // 円の半径 public bool IsPositionUpdated = false; // 円が描画される座標は変更されたか？ public long ID = 0; // オブジェクトの通し番号 public int Number = 0; // 追加された順番 public Player? Player = null; // 円がスネークの身体である場合、どのスネークのものか？ public long PlayerID = 0; // スネークの識別番号（0以上、-1なら餌） public bool IsHead = false; // 円がスネークの身体である場合、これは頭か？ public Circle() { } // 初期化 public void Init() { X = 0; Y = 0; Radius = 0; IsPositionUpdated = false; ID = 0; PlayerID = 0; Number = 0; IsHead = false; Player = null; } } |
Circleオブジェクトは更新処理のたびに大量に生成されるため、使い回すことにします。
Createメソッドが実行されるとすでにストックがある場合はそれを返し、ない場合は新たに生成します。Pushメソッドは不要になったCircleオブジェクトをストックに追加します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
public class Circle { static Queue<Circle> _circles = new Queue<Circle>(); static long _nextID = 0; public static Circle Create() { Circle circle; if (_circles.Count > 0) circle = _circles.Dequeue(); else circle = new Circle(); circle.Init(); // 初期化 _nextID++; circle.ID = _nextID; // 通し番号をつける return circle; } public static void Push(Circle circle) { _circles.Enqueue(circle); } } |
CirclesMapクラスの定義
Circleオブジェクト同士の当たり判定を高速におこなうためにCirclesMapクラスを定義します。ここではフィールド全体を一辺の長さが100の正方形に分割します。
Cellクラスの定義
一辺の長さが100の正方形の領域（以下、セルと表記する）を操作するためにCellクラスを定義します。
描画用のCircleオブジェクトと異なり当たり判定で使うものは間隔がある程度空いていても機能するので描画用のものと当たり判定用のものにわけます。更新処理で次々にCircleオブジェクトが追加されたり削除されるのですが、当たり判定用のものは8回に1回だけ保存します。また当たり判定用のものは必要なオブジェクト群を高速で取得できるようにPlayerIDをキーとして保存します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
public class Cell { HashSet<Circle> _forDraw = new HashSet<Circle>(); Dictionary<long, HashSet<Circle>> _forHitCheck = new Dictionary<long, HashSet<Circle>>(); public int Row { get; } public int Col { get; } public Cell(int row, int col) { Row = row; Col = col; } public void AddCircle(Circle circle) { _forDraw.Add(circle); if (circle.PlayerID < 0 || circle.Number % 8 == 0) { if (!_forHitCheck.ContainsKey(circle.PlayerID)) _forHitCheck.Add(circle.PlayerID, new HashSet<Circle>()); _forHitCheck[circle.PlayerID].Add(circle); } } public void RemoveCircle(Circle circle) { _forDraw.Remove(circle); if (circle.PlayerID < 0 || circle.Number % 8 == 0) { if (_forHitCheck.ContainsKey(circle.PlayerID)) { _forHitCheck[circle.PlayerID].Remove(circle); if (_forHitCheck[circle.PlayerID].Count == 0) // 要素がなくなったらキーを削除 _forHitCheck.Remove(circle.PlayerID); } } } } |
GetCirclesForDrawメソッドとGetCirclesForHitCheckメソッドは描画用、当たり判定用のCircleオブジェクトのリストを取得するためのものです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
public class Cell { public void GetCirclesForDraw(List<Circle> result) { result.AddRange(_forDraw.ToList()); } public void GetCirclesForHitCheck(Circle head, List<Circle> result) { foreach (var pair in _forHitCheck) { if (pair.Key != head.PlayerID) result.AddRange(pair.Value.ToList()); } } } |
以下のメソッドはセルのなかにどのようなCircleオブジェクトが存在するかを返します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
public class Cell { // 餌がひとつも存在しない public bool IsNoFood() { return ForDraw.Count(_ => _.PlayerID == -1) == 0; } // NPCか餌だけで人間のプレイヤーは存在しない public bool IsNoPlayer() { return _forDraw.All(_ => _.Player == null || _.Player.ConnectionId == ""); } // 人間のプレイヤーは存在しないしNPCすら存在しない public bool IsNoPlayerNoNpc() { return _forDraw.All(_ => _.Player == null); } } |
CirclesMapクラスの初期化
CirclesMapクラスを以下のように定義します。最初にフィールド変数とコンストラクタを示します。
フィールドは円形なので正方形に分割されたセルのなかには完全にフィールドの内部に含まれるもの、完全にフィールドの外部に存在するもの、一部のみがフィールドの内部に含まれるものにわかれます。餌やプレイヤーの初期位置を決めるときに完全にフィールドの内部に含まれるセルを知っておきたいので、コンストラクタのなかでこれを取得しています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
public class CirclesMap { Cell[,] _cells = new Cell[1, 1]; // セルの2次元配列 int _maxX = 0; // フィールドの幅 int _maxY = 0; // フィールドの高さ int _rowCount = 0; // セルは何行存在するか？ int _colCount = 0; // セルは何列存在するか？ int _foodCount = 0; // 餌の個数 int _circleCount = 0; // 格納されているCircleオブジェクトの総数 // 座標が変更されたCircleオブジェクトのリスト List<Circle> _positionUpdatedCircles = new List<Circle>(); // フィールド内に完全に含まれるCellオブジェクトのリスト public HashSet<Cell> CellsCompleteInsideField = new HashSet<Cell>(); public CirclesMap() { _maxX = Constant.FIELD_RADUUS * 2; _maxY = Constant.FIELD_RADUUS * 2; _rowCount = _maxY / Constant.CELL_SIZE + 1; _colCount = _maxX / Constant.CELL_SIZE + 1; _cells = new Cell[_rowCount, _colCount]; for (int row = 0; row < _rowCount; row++) { for (int col = 0; col < _colCount; col++) { // 完全にフィールドの内部に含まれるセルかどうかを調べる // セルの4つの角がすべてフィールドの内部であればそれはフィールドの内部に存在する _cells[row, col] = new Cell(row, col); int left = Constant.CELL_SIZE * col; int right = Constant.CELL_SIZE * (col + 1); int top = Constant.CELL_SIZE * row; int bottom = Constant.CELL_SIZE * (row + 1); double r2 = Math.Pow(Constant.FIELD_RADUUS - 100, 2); int[] xs = { left, left, right, right }; int[] ys = { top, bottom, top, bottom }; bool ret = true; for (int i = 0; i < xs.Length; i++) { if (Math.Pow(xs[i] - Constant.FIELD_RADUUS, 2) + Math.Pow(ys[i] - Constant.FIELD_RADUUS, 2) > r2) { ret = false; break; } } if (ret) CellsCompleteInsideField.Add(_cells[row, col]); } } } } |
Circleオブジェクトの追加・削除・移動
CirclesMap内にCircleオブジェクトを追加する処理を示します。追加したいCircleオブジェクトの座標をCellSizeで割ればどのセルに追加すればよいかがわかります。追加したら_circleCountをインクリメントします。追加したCircleオブジェクトが餌の場合（PlayerIDが負数のとき）は_foodCountもインクリメントします。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
public class CirclesMap { public void AddCircle(Circle circle) { int row = (int)circle.Y / Constant.CELL_SIZE; int col = (int)circle.X / Constant.CELL_SIZE; if (0 <= row && row < _rowCount && 0 <= col && col < _colCount) { _cells[row, col].AddCircle(circle); if (circle.PlayerID < 0) _foodCount++; _circleCount++; } } // 格納されているCircleオブジェクトの総数を返す public int GetCirclesCount() { return _circleCount; } // 格納されている餌の総数を返す public int GetFoodsCount() { return _foodCount; } } |
CirclesMap内からCircleオブジェクトを削除する処理を示します。やっていることは追加とほとんど同じです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
public class CirclesMap { public void RemoveCircle(Circle circle) { int row = (int)circle.Y / Constant.CELL_SIZE; int col = (int)circle.X / Constant.CELL_SIZE; if (0 <= row && row < _rowCount && 0 <= col && col < _colCount) { _cells[row, col].RemoveCircle(circle); if (circle.PlayerID < 0) _foodCount--; _circleCount--; } } } |
格納されているCircleオブジェクトの位置を移動させる処理を示します。移動元と移動先の座標から所属するセルを変更する必要がある場合は変更します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
public class CirclesMap { public void MoveCircle(Circle circle, double afterX, double afterY) { double beforeX = circle.X; double beforeY = circle.Y; // Circleオブジェクトの座標を変更する circle.X = afterX; circle.Y = afterY; // 座標を変更しても整数部分が変更されない場合はここで終了 if ((int)beforeX == (int)afterX && (int)beforeY == (int)afterY) return; // 座標が変更されたというフラグを立てる circle.IsPositionUpdated = true; _positionUpdatedCircles.Add(circle); // 座標の変更に伴い所属するセルも変更しなければならないかをチェック int beforeRow = (int)beforeY / Constant.CELL_SIZE; int beforeCol = (int)beforeX / Constant.CELL_SIZE; int afterRow = (int)afterY / Constant.CELL_SIZE; int afterCol = (int)afterX / Constant.CELL_SIZE; if (beforeRow == afterRow && beforeCol == afterCol) return; // 所属するセルを変更する（旧セルから削除して移動先のセルに追加） if (0 <= beforeRow && beforeRow < _rowCount && 0 <= beforeCol && beforeCol < _colCount) _cells[beforeRow, beforeCol].RemoveCircle(circle); if (0 <= afterRow && afterRow < _rowCount && 0 <= afterCol && afterCol < _colCount) _cells[afterRow, afterCol].AddCircle(circle); } // 座標が変更されたCircleオブジェクトのリストを取得する public List<Circle> GetPositionUpdatedCircles() { return _positionUpdatedCircles; } } |
周辺にプレイヤーがいないセルを取得する
GetCellsNoPlayerメソッドはNPCではないプレイヤーが存在しないセルのリストを返します。またGetCellsNoPlayerNoNpcメソッドはNPC含めたプレイヤーが存在しないセルのリストを返します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
public class CirclesMap { public List<Cell> GetCellsNoPlayer() { List<Cell> ret = new List<Cell>(); int[] dx = { 1, 1, 0, -1, -1, -1, 0, 1, }; int[] dy = { 0, 1, 1, 1, 0, -1, -1, -1, }; foreach (Cell cell in CellsCompleteInsideField) { if (cell.IsNoPlayer()) { bool ok = true; for (int i = 0; i < dx.Length; i++) { int r = cell.Row + dy[i]; int c = cell.Col + dx[i]; if (0 <= r && r < _rowCount && 0 <= c && c < _colCount && !_cells[r, c].IsNoPlayer()) { ok = false; break; } } if (ok) ret.Add(cell); } } return ret; } public List<Cell> GetCellsNoPlayerNoNpc() { List<Cell> ret = new List<Cell>(); int[] dx = { 1, 1, 0, -1, -1, -1, 0, 1, }; int[] dy = { 0, 1, 1, 1, 0, -1, -1, -1, }; foreach (Cell cell in CellsCompleteInsideField) { if (cell.IsNoPlayerNoNpc()) { bool ok = true; for (int i = 0; i < dx.Length; i++) { int r = cell.Row + dy[i]; int c = cell.Col + dx[i]; if (0 <= r && r < _rowCount && 0 <= c && c < _colCount && !_cells[r, c].IsNoPlayerNoNpc()) { ok = false; break; } } if (ok) ret.Add(cell); } } return ret; } } |
フィールドに餌を追加する
ゲームが進行にともなってフィールド上の餌がなくなっていきます。そこでフィールドに餌を追加する機能を追加します。これを実行するセルは餌がひとつもなく完全にフィールドの内部に存在するものだけです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
public class CirclesMap { Random _random = new Random(); public void AddFoods() { for (int row = 0; row < _rowCount; row++) { for (int col = 0; col < _colCount; col++) { if (!_cells[row, col].IsNoFood()) // 餌が存在するセルにはなにもしない continue; // フィールドに完全に含まれないセルにもなにもしない if (!CellsCompleteInsideField.Contains(_cells[row, col])) continue; Circle circle = Circle.Create(); circle.X = col * Constant.CELL_SIZE + _random.Next(Constant.CELL_SIZE); circle.Y = row * Constant.CELL_SIZE + _random.Next(Constant.CELL_SIZE); circle.Radius = 2; circle.PlayerID = -1; AddCircle(circle); } } } } |
描画用のCircleオブジェクトを取得する
クライアントサイドに送信する描画用のCircleオブジェクトを取得する処理を示します。GetNearCellsメソッドは指定された座標を中心とする幅 width, 高さ height の領域のCellオブジェクトのリストを返します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
public class CirclesMap { public List<Cell> GetNearCells(double headX, double headY, int width, int height) { int minRow = (int)((headY - height / 2) / Constant.CELL_SIZE); int maxRow = (int)((headY + height / 2) / Constant.CELL_SIZE); int minCol = (int)((headX - width / 2) / Constant.CELL_SIZE); int maxCol = (int)((headX + width / 2) / Constant.CELL_SIZE); minRow = Math.Max(0, minRow); maxRow = Math.Min(_rowCount - 1, maxRow); minCol = Math.Max(0, minCol); maxCol = Math.Min(_colCount - 1, maxCol); List<Cell> list = new List<Cell>(); for (int r = minRow; r <= maxRow; r++) { for (int c = minCol; c <= maxCol; c++) list.Add(_cells[r, c]); } return list; } } |
GetNearCirclesメソッドは指定された座標を中心とする幅 width, 高さ height の領域のCircleオブジェクトのリストを返します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
public class CirclesMap { public List<Circle> GetNearCircles(double headX, double headY, int width, int height) { double minX = headX - width / 2; double maxX = headX + width / 2; double minY = headY - height / 2; double maxY = headY + height / 2; List<Cell> cells = GetNearCells(headX, headY, width, height); List<Circle> list = new List<Circle>(); foreach(Cell cell in cells) cell.GetCirclesForDraw(list); return list.Where(circle => circle.X >= minX && maxX > circle.X && circle.Y > minY && maxY > circle.Y).ToList(); } } |
当たり判定
引数として渡されたCircleオブジェクトが餌やそれ以外のプレイヤーに接触していないかを調べる処理を示します。
引数として渡されたCircleオブジェクトがセルの端にある場合は隣接するセルも同時に確認しなければなりません。そこで最初に当たり判定の対象になりそうなCircleオブジェクトを取得してそのあとオブジェクトの半径の和と中心の距離を比較して当たり判定をおこないます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
public class CirclesMap { public List<Circle> HitCheck(Circle head) { // 当たり判定の対象になりそうなCircleオブジェクトを取得 int width = 30; int height = 30; List<Cell> cells = GetNearCells(head.X, head.Y, width, height); List<Circle> circles = new List<Circle>(); foreach (Cell cell in cells) cell.GetCirclesForHitCheck(head, circles); double minX = head.X - width / 2; double maxX = head.X + width / 2; double minY = head.Y - height / 2; double maxY = head.Y + height / 2; circles = circles.Where(circle => circle.X >= minX && maxX > circle.X && circle.Y > minY && maxY > circle.Y).ToList(); // 対象になりそうなCircleオブジェクトが取得できたので当たり判定をする List<Circle> rets = new List<Circle>(); foreach (Circle circle in circles) { double d = Math.Sqrt(Math.Pow(circle.X - head.X, 2) + Math.Pow(circle.Y - head.Y, 2)); if (circle.PlayerID >= 0) { // 他のプレイヤー（NPC含む）の身体と接触した場合は死亡判定になるので // 餌の当たり判定は無視して接触したプレイヤーの身体の部分を返す if (d < head.Radius + circle.Radius) { rets.Clear(); rets.Add(circle); } } else { // 餌の場合は複数該当する場合はすべて取得する if (d < head.Radius + circle.Radius + 4) rets.Add(circle); } } return rets; } } |
NPCによる衝突回避
NPCの衝突回避行動に関する処理を示します。まず距離が100以内で自分に一番近い位置にある他のプレイヤーのCircleオブジェクトを取得します。該当するものがあればその方向とは反対側に回頭させます。回頭する場合は以降の24回更新は右または左にターンさせます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
public class CirclesMap { public int NpcThink(Circle head, double npcAngle) { // 距離が100以内にある他のプレイヤーのCircleオブジェクトを取得 int width = 100; int height = 100; double minX = head.X - width / 2; double maxX = head.X + width / 2; double minY = head.Y - height / 2; double maxY = head.Y + height / 2; List<Cell> cells = GetNearCells(head.X, head.Y, width, height); List<Circle> circles = new List<Circle>(); foreach (Cell cell in cells) cell.GetCirclesForHitCheck(head, circles); circles = circles.Where(circle => circle.PlayerID >= 0 && circle.X >= minX && maxX > circle.X && circle.Y > minY && maxY > circle.Y).ToList(); // 一番近くにあるものとその方向を求める double nearest = double.MaxValue; Circle? nearestCircle = null; int turnDirect = 0; foreach (Circle circle in circles) { double d2 = Math.Pow(circle.X - head.X, 2) + Math.Pow(circle.Y - head.Y, 2); double d = Math.Sqrt(d2); if (d < 100) { double rad = Math.Atan2(circle.Y - head.Y, circle.X - head.X); rad += Math.PI * 2; rad %= Math.PI * 2; rad -= npcAngle; if (rad < 0) rad += Math.PI * 2; int turnDirect0 = 0; if (0 < rad && rad < Math.PI * 0.6) turnDirect0 = -1; // 時計側に敵 else if (Math.PI * 1.4 < rad && rad < Math.PI * 2) turnDirect0 = 1; // 反時計側に敵 if (nearest > d) { nearest = d; nearestCircle = circle; turnDirect = turnDirect0; } } } // 該当するものが見つかったらそれとは反対方向に進路変更する if (nearestCircle != null) { if (turnDirect > 0) return 24; if (turnDirect < 0) return -24; } return 0; } } |
