前回、JavaScriptで『スペースウォー!』（Spacewar!）を完成させたので、次に対戦型の『スペースウォー!』を作ります。ただそのときにちょっとした問題に直面したので、今回はその部分を記事にします。
これまでに作ってきた多くのゲームの当たり判定は対象物を円、または球とみなし、その中心の距離と半径の合計を比較するという方法をとってきました。しかし今回はプレーヤーが縦に長いため、この方法はとれません。JavaScriptの場合はcontext.isPointInPath(x,y)関数がありましたが、サーバーサイド（言語はC#）で当たり判定をする場合はどうすればいいのでしょうか？
Contents
GraphicsPathクラスを使った図形との当たり判定
C#にもこのような当たり判定をする方法は存在します。GraphicsPath クラスを使う方法です。
やり方は簡単で図形の頂点の座標の配列をGraphicsPath.AddLinesメソッドに渡しておき、当たり判定をしたい座標をIsVisibleメソッドに渡します。trueが返されればその座標は図形内部にあります。
以下はクリックされた座標が_pointsで構成される図形の内部にある場合はタイトルバーに”OK”、そうでない場合は”NG”と表示するWindowsFormsアプリケーションのコードです。
|
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 |
using System; using System.Drawing; using System.Drawing.Drawing2D; using System.Windows.Forms; public partial class Form1 : Form { Point[] _points = { new Point(20, 15), new Point(50, 80), new Point(100, 10), new Point(125, 75), new Point(190, 40), new Point(110, 120), new Point(185, 140), new Point(160, 190), new Point(65, 140), new Point(30, 180), new Point(20, 15), // 閉じた図形にするため最後の要素は最初の要素と同じ }; GraphicsPath _graphicsPath = new GraphicsPath(); public Form1() { InitializeComponent(); _graphicsPath.AddLines(_points); } Pen Pen = new Pen(Color.Black, 3); protected override void OnPaint(PaintEventArgs e) { e.Graphics.DrawLines(Pen, _points); base.OnPaint(e); } protected override void OnMouseClick(MouseEventArgs e) { if (_graphicsPath.IsVisible(new Point(e.X, e.Y))) Text = "OK"; else Text = "NG"; base.OnMouseClick(e); } } |
なんだ簡単じゃないか・・・とはなりません。ASP.NET Core でこれをやろうとするとサーバー上で実行しようとしたときに例外が発生します。これはSystem.Drawing.Common が Windows でしかサポートされないからです。サーバーのOSがLinuxの場合はうまくいかないのです。
GraphicsPathクラスを使わない図形との当たり判定
ではどうするか？ GraphicsPathクラスを使わずに図形との当たり判定をする方法を考えます。
図形との内外判定をする方法のひとつにCrossing Number Algorithmがあります。今回はこのアルゴリズムを使います。このアルゴリズムは以下のようなものです。
「多角形の各線分ごとに、指定した点を通るx軸に平行な線との交点があるかどうかを調べ、交点が指定した点より右にあればカウントする。カウントした点が奇数なら指定した点は多角形に含まれている」
赤い水平線には交点が3つ（奇数）あります。青い水平線には交点が2つ（偶数）あります。たしかに前者は図形の内部にあり、後者は図形の外部にあります。
ただし、この方法には注意点があります。それは水平線が頂点を通る場合です。緑の水平線の交点は2つ（偶数）ですが、内部にあります。水平線が頂点を通る場合や辺と完全に重なってしまう場合は工夫しなければなりません。
そこで以下のようなルールを設けます。
上向きの辺は、開始点を含み終点を含まない。
下向きの辺は、開始点を含まず終点を含む。
水平な辺はカウントしない。
このルールのもとで以下のようなメソッドを定義します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
bool PointInArea(Point[] vertices, Point point) { int ret = 0; for (int i = 0; i < vertices.Length - 1; i++) { if (((vertices[i].Y <= point.Y) && (vertices[i + 1].Y > point.Y)) || ((vertices[i].Y > point.Y) && (vertices[i + 1].Y <= point.Y))) { // 辺と水平線は交わるか？ // 水平線上の点がpointと同じ高さになる位置を特定し、その時のX座標とpointの座標を比較する。 double vt = 1d * (point.Y - vertices[i].Y) / (vertices[i + 1].Y - vertices[i].Y); if (point.X < (vertices[i].X + (vt * (vertices[i + 1].X - vertices[i].X)))) ret++; } } return ret % 2 == 1; } |
JavaScript編 図形との当たり判定
次にJavaScriptでもやってみます。
|
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 68 69 70 71 72 73 74 75 76 77 78 |
<!DOCTYPE html> <html lang="ja"> <head> <meta charset="UTF-8"> <title>不規則な形をした図形との内外判定</title> <meta name = "viewport" content = "width=device-width, initial-scale = 1.0"> <style> #canvas { display: block; border: 1px solid #000; } </style> </head> <body> <canvas id = "canvas"></canvas> <div id = "result">枠内をクリックしてください</div> <script> class Point{ constructor(x, y){ this.X = x; this.Y = y; } } const $canvas = document.getElementById('canvas'); const ctx = $canvas.getContext('2d'); $canvas.width = 360; $canvas.height = 360; const vertices = []; vertices.push(new Point(50, 45)); vertices.push(new Point(80, 110)); vertices.push(new Point(130, 40)); vertices.push(new Point(155, 105)); vertices.push(new Point(220, 70)); vertices.push(new Point(140, 150)); vertices.push(new Point(215, 170)); vertices.push(new Point(190, 220)); vertices.push(new Point(95, 170)); vertices.push(new Point(60, 210)); vertices.push(new Point(50, 45)); // 閉じた図形にするため最後の要素は最初の要素と同じ ctx.beginPath(); ctx.moveTo(vertices[0].X, vertices[0].Y); for(let i=1; i<vertices.length; i++) ctx.lineTo(vertices[i].X, vertices[i].Y); ctx.fillStyle = '#f00'; ctx.stroke(); $canvas.addEventListener('click', (ev)=>{ const rect = $canvas.getBoundingClientRect(); const point = new Point(ev.pageX - rect.x, ev.pageY - rect.y); if(pointInArea(vertices, point)) document.getElementById('result').innerHTML = `座標（${ev.pageX}, ${ev.pageY}）は 内部です`; else document.getElementById('result').innerHTML = `座標（${ev.pageX}, ${ev.pageY}）は 外部です`; }); function pointInArea(vertices, point){ let ret = 0; for(let i = 0; i < vertices.length - 1; i++){ if( ((vertices[i].Y <= point.Y) && (vertices[i+1].Y > point.Y)) || ((vertices[i].Y > point.Y) && (vertices[i+1].Y <= point.Y)) ){ const vt = (point.Y - vertices[i].Y) / (vertices[i+1].Y - vertices[i].Y); if(point.X < (vertices[i].X + (vt * (vertices[i+1].X - vertices[i].X)))) ret++; } } return ret % 2 == 1; } </script> </body> </html> |
冒頭の動画のコード
冒頭の動画のコードを示します（解説は長くなるので省略）。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
<!DOCTYPE html> <html lang="ja"> <head> <meta charset="UTF-8"> <title>不規則な形をした図形との当たり判定</title> <meta name = "viewport" content = "width=device-width, initial-scale = 1.0"> </head> <body> <canvas id = "canvas"></canvas> <script src= "./index.js"></script> </body> </html> |
index.js
|
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 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 |
const CANVAS_WIDTH = 360; const CANVAS_HEIGHT = 360; const SHAPES_CENTER_X = 180; const SHAPES_CENTER_Y = 180; class Point{ constructor(x, y){ this.X = x; this.Y = y; } } class Bullet{ constructor(x, y, vx, vy){ this.Point = new Point(x, y); this.VX = vx; this.VY = vy; this.IsDead = false; } Update(){ this.Point.X += this.VX; this.Point.Y += this.VY; if(this.Point.X < 0 || this.Point.Y < 0 || this.Point.X > CANVAS_WIDTH || this.Point.Y > CANVAS_HEIGHT) this.IsDead = true; } Draw(){ ctx.beginPath(); ctx.arc(this.Point.X, this.Point.Y, 4, 0, Math.PI * 2); ctx.fillStyle = '#fff'; ctx.shadowBlur = 4; ctx.shadowColor = '#0ff'; ctx.fill(); ctx.fill(); ctx.shadowBlur = 0; } } const $canvas = document.getElementById('canvas'); const ctx = $canvas.getContext('2d'); const vertices = []; let angle = 0; let bullets = []; let updateCount = 0; window.onload = () => { $canvas.width = CANVAS_WIDTH; $canvas.height = CANVAS_HEIGHT; ctx.fillStyle ='#000'; ctx.fillRect(0, 0, CANVAS_WIDTH, CANVAS_HEIGHT); // 中心で回転する物体の頂点の座標 vertices.push(new Point(0, -60)); vertices.push(new Point(- 80, 60)); vertices.push(new Point(0, 0)); vertices.push(new Point(80, 60)); vertices.push(new Point(0, -60)); update(); } function update(){ requestAnimationFrame(update); updateCount++; angle += 0.01; const points = getRotatedPositions(); ctx.fillStyle ='#000'; ctx.fillRect(0, 0, CANVAS_WIDTH, CANVAS_HEIGHT); drawShapes(points); bullets.forEach(bullet => { bullet.Update(); if(pointInArea(points, bullet.Point)) bullet.IsDead = true; }); bullets = bullets.filter(bullet => !bullet.IsDead); bullets.forEach(bullet => bullet.Draw()); // 30回更新に1回新しい弾丸をcanvasの周囲のどこかに生成する // そして中心から少しズレた座標をめがけて移動させる if(updateCount % 30 == 0){ const r = Math.random(); let x = 0; let y = 0; if(r < 0.25){ x = 0; y = Math.random() * CANVAS_HEIGHT; } else if(r < 0.5){ x = CANVAS_WIDTH; y = Math.random() * CANVAS_HEIGHT; } else if(r < 0.75){ x = Math.random() * CANVAS_WIDTH; y = 0; } else { x = Math.random() * CANVAS_WIDTH; y = CANVAS_HEIGHT; } // どこを狙うか？ const targetX = SHAPES_CENTER_X + Math.random() * 100 - 50; const targetY = SHAPES_CENTER_Y + Math.random() * 100 - 50; const angle = Math.atan2(targetY - y, targetX - x); bullets.push(new Bullet(x, y, 2 * Math.cos(angle), 2 * Math.sin(angle))); } } // vertices を原点を中心にangleだけ回転させて、 // X軸方向にSHAPES_CENTER_X、Y軸方向にSHAPES_CENTER_Y並行移動させた座標を返す function getRotatedPositions(){ const points = []; for(let i = 0; i < vertices.length; i++){ const x = Math.cos(angle) * vertices[i].X - Math.sin(angle) * vertices[i].Y + SHAPES_CENTER_X; const y = Math.sin(angle) * vertices[i].X + Math.cos(angle) * vertices[i].Y + SHAPES_CENTER_Y; points.push(new Point(x, y)); } return points; } function drawShapes(points){ ctx.beginPath(); ctx.moveTo(points[0].X, points[0].Y); for(let i=1; i<points.length; i++) ctx.lineTo(points[i].X, points[i].Y); ctx.strokeStyle ='#ff0'; ctx.stroke(); } function pointInArea(vertices, point){ let ret = 0; for(let i = 0; i < vertices.length - 1; i++){ if( ((vertices[i].Y <= point.Y) && (vertices[i+1].Y > point.Y)) || ((vertices[i].Y > point.Y) && (vertices[i+1].Y <= point.Y)) ){ const vt = (point.Y - vertices[i].Y) / (vertices[i+1].Y - vertices[i].Y); if(point.X < (vertices[i].X + (vt * (vertices[i+1].X - vertices[i].X)))) ret++; } } return ret % 2 == 1; } |
