今回は The Simple Game (AtCoder Beginner Contest 427)をネタにしてパズルゲームをつくります。

Contents
The Simple Gameを解いてみる
問題の趣旨は以下のとおりです。
各頂点の出次数が 1 以上である有向グラフがあり、各頂点には’A’または’B’が書かれている。
初期状態で駒は頂点 1 に置かれていて、これを先手後手交互に移動させる。最終的に駒が置かれている頂点に書かれている文字が’A’なら先手の勝ち、’B’なら後手の勝ちである。
両者が最適に行動したときのゲームの勝者は?
このようなゲームの問題では、後ろから勝敗の状態を解析するとうまくいく場合が多いです。
最終ターンの後手の手番で’B’に移動できる頂点(後手必勝点)に駒があるなら後手の勝ちです。そうではない位置(先手必勝点)に駒があるなら先手の勝ちです。最終ターンの先手の手番で先手必勝点に移動できる位置に駒がある(先手必勝点)なら先手の勝ちで、できない(後手必勝点)のであれば後手の勝ちです。
このような操作をK回繰り返したときに頂点 1 が先手必勝点か後手必勝点かで解を得ることができます。
|
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 |
class Program { static void Main() { int T = int.Parse(Console.ReadLine()); List<string> ans = new List<string>(); for (int t = 0; t < T; t++) { string[] vs = Console.ReadLine().Split(); int N = int.Parse(vs[0]); int M = int.Parse(vs[1]); int K = int.Parse(vs[2]); char[] S = Console.ReadLine().ToArray(); List<int>[] E = new List<int>[N]; List<int>[] rE = new List<int>[N]; // 逆向きの辺 for (int i = 0; i < N; i++) { E[i] = new List<int>(); rE[i] = new List<int>(); } for (int i = 0; i < M; i++) { vs = Console.ReadLine().Split(); int a = int.Parse(vs[0]); int b = int.Parse(vs[1]); a--; b--; E[a].Add(b); rE[b].Add(a); } ans.Add(Solve(N, K, S, rE)); } foreach (var str in ans) Console.WriteLine(str); string Solve(int n, int k, char[] s, List<int>[] rE) { bool[] a_wins = new bool[n]; bool[] b_wins = new bool[n]; for (int i = 0; i < n; i++) a_wins[i] = s[i] == 'A'; for (int turn = 0; turn < k; turn++) { // 後手必勝点を求める b_wins = new bool[n]; for (int i = 0; i < n; i++) { // 先手必勝点ではないところへ移動できる頂点はすべて後手必勝点である if (!a_wins[i]) { foreach (int next in rE[i]) b_wins[next] = true; } } // 先手必勝点を求める a_wins = new bool[n]; for (int i = 0; i < n; i++) { // 後手必勝点でないところへ移動できる頂点はすべて先手必勝点である if (!b_wins[i]) { foreach (int next in rE[i]) a_wins[next] = true; } } } return a_wins[0] ? "Alice" : "Bob"; } } } |
HTML部分
HTML部分を示します。
|
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 |
<!DOCTYPE html> <html lang="ja"> <head> <meta charset="UTF-8"> <title>鳩でもわかる The Simple Game</title> <meta name = "viewport" content = "width=device-width, initial-scale = 1.0"> <link rel="stylesheet" href="./style.css"> </head> <body> <div id = "container"> <div id = "field"> <div id = "field-header"> <div id = "how-to-play"> <div id = "how-to-play-inner"> 各ターン先手後手で交互に移動させ最終位置が青なら先手が勝ち、赤なら後手勝ちです。 </div> </div> <div id = "score">Score 0000</div><div id = "time"></div> <div class = "clear-both"></div> </div> <div id = "canvas-outer"></div> <div id = "turn"></div> <div id = "start-buttons"> <p><label for="player-name">プレイヤー名:</label> <input id = "player-name" maxlength="32"></p> <p><button id = 'start'>START</button></p> <p><button id = 'go-ranking' onclick="location.href = './ranking.html'">ランキング</button></p> </div> <div id = "first-second"> <button id = "first">先手(A)</button> <button id = "second">後手(B)</button> </div> <div id = "volume"></div> </div> </div> <script src = "./app.js"></script> </body> </html> |
style.css
|
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 |
body { background-color: black; color: white; } #container { width: 360px; margin-left: auto; margin-right: auto; margin-top: 10px; border: 0px solid #1DA1F2; } #field { width: 360px; height: 600px; margin-left: auto; margin-right: auto; position: relative; border: 0px #1DA1F2 solid; } #field-header { margin-bottom: 10px; font-size: large; display: block; } #how-to-play { overflow: hidden; margin-bottom: 10px; } #how-to-play-inner { overflow: hidden; font-size: medium; width: 2000px; margin-left: 0px; } #score { float: left; margin-left: 10px; } #time { float: right; margin-right: 20px; } #turn { margin-bottom: 16px; margin-left: 10px; } .clear-both { clear: both; } #start-buttons { position: absolute; left: 0px; top: 120px; width: 100%; text-align: center; display: block; } #start, #go-ranking { font-weight: bold; text-align: center; font-size: 18px; width: 280px; border: none; font-size: 16px; background-color: #1DA1F2; padding: 10px 32px; border-radius: 100vh; color: white; cursor: pointer; } #first-second { margin-top: 0px; margin-bottom: 16px; margin-left: 0px; width: 100%; text-align: center; display: none; } #first, #second { width: 120px; height: 60px; margin-right: 20px; background-color: transparent; color: white; font-weight: bold; font-size: large; border: 2px solid #fff; } .red { color: magenta; font-weight: bold; } .blue { color: aqua; font-weight: bold; } |
グローバル変数
|
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 |
const CANVAS_WIDTH = 360; const CANVAS_HEIGHT = 345; const ROW_COUNT = 5; // 縦横のマスの数 const COL_COUNT = 5; const CELL_SIZE = 50; // マスを描画するときの大きさと隣との間隔 const CELL_TO_CELL_SPACING = 20; let cells = []; // Cellオブジェクト(後述)を格納する配列 let E = []; // マスとマスをつなぐ辺 let rE = []; // 逆向きの辺 let playing = false; let score = 0; let clear_count = 0; // 連勝した回数 let remaining_turns = 0; // 残りターン数 let max_remaining_turns = 0; // 残りターン数の初期値(クリアするたびに増やす) let is_player_first = false; // プレイヤーが選択したのは先手か? let cur_index = 12; // 選択されているマスの index let ignore_click = true; // 処理中なのでクリックしても移動処理を開始しない const REMAINING_TIME_MAX = 120 * 1000; // 制限時間とその初期値 let remaining_time = REMAINING_TIME_MAX; let how_to_play_inner_left = 200; // DOM要素 const $canvas = document.createElement('canvas'); $canvas.width = CANVAS_WIDTH; $canvas.height = CANVAS_HEIGHT; document.getElementById('canvas-outer')?.appendChild($canvas); const ctx = $canvas.getContext('2d'); const $player_name = document.getElementById('player-name'); const $score = document.getElementById('score'); const $time = document.getElementById('time'); const $how_to_play = document.getElementById('how-to-play'); const $how_to_play_inner = document.getElementById('how-to-play-inner'); // 効果音 const select_sound = new Audio('./sounds/select.mp3'); const ng_sound = new Audio('./sounds/ng.mp3'); const clear_sound = new Audio('./sounds/clear.mp3'); const gameover_sound = new Audio('./sounds/gameover.mp3'); const sounds = [select_sound, ng_sound, clear_sound, gameover_sound]; |
Cellクラスの定義
マスを描画等で必要になるのでCellクラスを定義します。
|
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 |
class Cell { constructor(idx, row, col){ this.Index = idx; this.X = (CELL_SIZE + CELL_TO_CELL_SPACING) * col + CELL_TO_CELL_SPACING / 2; this.Y = (CELL_SIZE + CELL_TO_CELL_SPACING) * row + CELL_TO_CELL_SPACING / 2; this.Color = '#00f'; this.Text = 'A'; this.Nexts = []; // 移動できるマスのindex this.DrawCount = 0; // 描画処理がおこなわれた回数 } // 設定されている文字で表示色を変える SetText(text){ if(text == 'A'){ this.Text = 'A'; this.Color = '#00f'; } else { this.Text = 'B'; this.Color = '#f00'; } } Draw(){ this.DrawCount++; ctx.fillStyle = this.Color; ctx.fillRect(this.X, this.Y, CELL_SIZE, CELL_SIZE); ctx.strokeStyle = '#fff'; ctx.lineWidth = 2; ctx.strokeRect(this.X, this.Y, CELL_SIZE, CELL_SIZE); ctx.fillStyle = '#fff'; ctx.textBaseline = 'top'; ctx.font= '24px Arial'; const w = ctx?.measureText(this.Text).width; ctx.fillText(this.Text, this.X + (CELL_SIZE - w) / 2, this.Y + 14); // 選択されていないマスを暗めに描画する // 選択されているマスをぼんやりと点滅させる if(cur_index != this.Index){ ctx.fillStyle = 'rgba(0, 0, 0, 0.64)'; ctx.fillRect(this.X, this.Y, CELL_SIZE, CELL_SIZE); } else { if(this.DrawCount % 120 < 60){ ctx.fillStyle = 'rgba(255, 255, 255, 0.1)'; ctx.fillRect(this.X, this.Y, CELL_SIZE, CELL_SIZE); } ctx.strokeRect(this.X - 2, this.Y - 2, CELL_SIZE + 4, CELL_SIZE + 4); } // 移動可能なマスにむけて矢印を描画する this.Nexts.forEach(next => { if(next == this.Index + 1 || next == this.Index - 1){ // 左右の矢印 const head_x = next == this.Index + 1 ? this.X + CELL_SIZE + CELL_TO_CELL_SPACING : this.X - CELL_TO_CELL_SPACING; const tail_x = next == this.Index + 1 ? this.X + CELL_SIZE : this.X; const mid_x = next == this.Index + 1 ? this.X + CELL_SIZE + CELL_TO_CELL_SPACING / 2 : this.X - CELL_TO_CELL_SPACING / 2; const y = this.Y + CELL_SIZE / 2; ctx.beginPath(); ctx.moveTo(head_x, y); ctx.lineTo(mid_x, y - 10); ctx.lineTo(mid_x, y - 5); ctx.lineTo(tail_x, y - 5); ctx.lineTo(tail_x, y + 5); ctx.lineTo(mid_x, y + 5); ctx.lineTo(mid_x, y + 10); ctx.closePath(); ctx.fillStyle = '#ff0'; ctx.fill(); // 現在位置からの移動に関係ない矢印は暗めに描画する if(cur_index != this.Index){ ctx.fillStyle = 'rgba(0, 0, 0, 0.5)'; ctx.fill(); } } if(next == this.Index - COL_COUNT || next == this.Index + COL_COUNT){ // 上下の矢印 const head_y = next == this.Index - COL_COUNT ? this.Y - CELL_TO_CELL_SPACING : this.Y + CELL_SIZE + CELL_TO_CELL_SPACING; const tail_y = next == this.Index - COL_COUNT ? this.Y : this.Y + CELL_SIZE; const mid_y = next == this.Index - COL_COUNT ? this.Y - CELL_TO_CELL_SPACING / 2 : this.Y + CELL_SIZE + CELL_TO_CELL_SPACING / 2; const x = this.X + CELL_SIZE / 2; ctx.beginPath(); ctx.moveTo(x, head_y); ctx.lineTo(x - 10, mid_y); ctx.lineTo(x - 5, mid_y); ctx.lineTo(x - 5, tail_y); ctx.lineTo(x + 5, tail_y); ctx.lineTo(x + 5, mid_y); ctx.lineTo(x + 10, mid_y); ctx.closePath(); ctx.fillStyle = '#ff0'; ctx.fill(); if(cur_index != this.Index){ ctx.fillStyle = 'rgba(0, 0, 0, 0.5)'; ctx.fill(); } } }); } // 引数で与えられた座標はマスの内部か? IsInside(x, y){ return this.X < x && x < this.X + CELL_SIZE && this.Y < y && y < this.Y + CELL_SIZE; } // 二次元配列である場合の添字を一次元配列の添字に変換する static ToIndex(row, col){ return row * COL_COUNT + col; } // 一次元配列の添字を行番号に変換する static GetRow(idx){ return Math.floor(idx / COL_COUNT); } // 一次元配列の添字を列番号に変換する static GetCol(idx){ return idx % COL_COUNT; } } |
ページが読み込まれたときの処理
ページが読み込まれたときにおこなわれる処理を示します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
window.addEventListener('load', () => { // 定番の処理:ローカルストレージにプレイヤー名が保存されているときはこれをセットする const savedName = localStorage.getItem('hatodemowakaru-player-name'); if(savedName && $player_name != null) $player_name.value = savedName; $player_name.addEventListener('change', () => localStorage.setItem('hatodemowakaru-player-name', $player_name.value )); createCells(); // マスを生成する(後述) addEventListeners(); // 後述 createQuestion(); // 問題を生成する(後述) startUpdate(); // 更新処理を開始する(後述) initVolume('volume', sounds); // 定番の処理:ボリューム調整(後述) }); |
マスの生成
マスを生成する処理を示します。
25個のCellオブジェクトを生成して移動可能なマス同士を連結させます。このとき隅や端にあるものを除いて入次数と出次数が 2 になるようにします。
|
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 |
function createCells(){ for(let row = 0; row < ROW_COUNT; row++){ for(let col = 0; col < COL_COUNT; col++){ const idx = Cell.ToIndex(row, col); cells.push(new Cell(idx, row, col)); } } for(let i = 0; i < ROW_COUNT * COL_COUNT; i++){ E.push([]); rE.push([]); } for(let i = 0; i < ROW_COUNT * COL_COUNT; i++){ const r = Cell.GetRow(i); const c = Cell.GetCol(i); if((r % 2 == 0 && c % 2 == 0) || (r % 2 == 1 && c % 2 == 1)){ // 左右 if(c - 1 >= 0){ cells[i].Nexts.push(i - 1); E[i].push(i - 1); rE[i - 1].push(i); } if(c + 1 < COL_COUNT){ cells[i].Nexts.push(i + 1); E[i].push(i + 1); rE[i + 1].push(i); } } else { // 上下 if(r - 1 >= 0){ cells[i].Nexts.push(i - COL_COUNT); E[i].push(i - COL_COUNT); rE[i - COL_COUNT].push(i); } if(r + 1 < ROW_COUNT){ cells[i].Nexts.push(i + COL_COUNT); E[i].push(i + COL_COUNT); rE[i + COL_COUNT].push(i); } } } } |
イベントリスナの追加
イベントリスナを追加する処理を示します。呼び出される関数に関しては後述します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
function addEventListeners(){ document.getElementById('start').addEventListener('click', () => gameStart()); document.getElementById('first').addEventListener('click', () => selectFirst(true)); document.getElementById('second').addEventListener('click', async() => selectFirst(false)); document.addEventListener('keydown', (ev) => onKeyDown(ev)); $canvas.addEventListener('click', (ev) => { const rect = $canvas.getBoundingClientRect(); const x = ev.clientX - rect.x; const y = ev.clientY - rect.y; for(let i = 0; i < ROW_COUNT * COL_COUNT; i++){ if(cells[i].IsInside(x, y)){ move(i); return; } } }); $player_name.oncontextmenu = (ev) => { ev.stopPropagation(); return true; } } |
問題を生成する処理
問題を生成する処理を示します。マスのなかから約半数に’A’を、それ以外のものに’B’を選択します。indexと乱数を結びつけてソートして約半数をランダムに選んでいます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
function createQuestion(){ cur_index = 12; const arr = []; for(let i = 0; i < ROW_COUNT * COL_COUNT; i++) arr.push({idx: i, v: Math.random()}); arr.sort((a, b) => a.v - b.v); cells.forEach(_ => _.SetText('A')); arr.length = Math.floor(ROW_COUNT * COL_COUNT / 2); arr.forEach(_ => cells[_.idx].SetText('B')); } |
更新処理の開始
更新処理を開始するための処理を示します。
その前提として、ゲーム開始ボタンと先手後手選択ボタンの表示非表示を切り替える関数を示します。
|
1 2 3 4 5 6 7 8 9 10 |
function showStartButtons(is_show){ document.getElementById('start-buttons').style.display = is_show == true ? 'block' : 'none'; } function showFirstSecondButtons(is_show){ if(is_show != undefined) document.getElementById('first-second').style.display = is_show == true ? 'block' : 'none'; else // 引数なしのときは表示されているかどうかを true false で返す return document.getElementById('first-second').style.display != 'none'; } |
|
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 |
function startUpdate(){ let prev_time = 0; function update(){ requestAnimationFrame(() => update()); const cur_time = Date.now(); if(!ignore_click) // 操作可能のときは制限時間を更新のたびに減算する remaining_time -= cur_time - prev_time; prev_time = cur_time; if(remaining_time < 0) remaining_time = 0; if(remaining_time == 0) // 制限時間オーバーのときはゲームオーバー処理(後述) gameover(); const sec = Math.floor(remaining_time / 1000); const time_text = `残り時間 ${sec.toString().padStart(3, '0')}.${(remaining_time % 1000).toString().padStart(3, '0')}`; $time.innerHTML = time_text; // HowToPlayの文字列を右から左に流す how_to_play_inner_left--; if(how_to_play_inner_left < -800) how_to_play_inner_left = 400; $how_to_play_inner.style.marginLeft = `${how_to_play_inner_left}px`; // 現在のターンの状態を表示する const $turn = document.getElementById('turn'); if(playing && showFirstSecondButtons()){ let text = `全部で ${max_remaining_turns} ターンです。<br>先手または後手を選択してください。`; $turn.innerHTML = text; } else { let text = `全ターン ${max_remaining_turns} <span style = "margin-left: 30px">残り ${remaining_turns}</span>`; if(!ignore_click) text += `<br><span class = "${is_player_first ? 'blue' : 'red'}">あなたの手番</span>です`; $turn.innerHTML = text; } $score.innerHTML = `Score ${score.toLocaleString()}`; // canvasにマスを描画する ctx.fillStyle = '#000'; ctx.fillRect(0, 0, 360, 360); cells.forEach(_ => _.Draw()); } update(); } |
ボリュームを調整できるようにする
|
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 |
function initVolume(elementId, sounds){ let volume = 0.3; const savedVolume = localStorage.getItem('hatodemowakaru-volume'); if(savedVolume) volume = Number(savedVolume); const $element = document.getElementById(elementId); const $div = document.createElement('div'); const $span1 = document.createElement('span'); $span1.innerHTML = '音量'; $div.appendChild($span1); const $range = document.createElement('input'); $range.type = 'range'; $div.appendChild($range); const $span2 = document.createElement('span'); $div.appendChild($span2); $range.addEventListener('input', () => { const value = $range.value; $span2.innerText = value; volume = Number(value) / 100; setVolume(); }); $range.addEventListener('change', () => localStorage.setItem('hatodemowakaru-volume', volume.toString())); setVolume(); $span2.innerText = Math.round(volume * 100).toString(); $span2.style.marginLeft = '16px'; $range.value = Math.round(volume * 100).toString(); $range.style.width = '230px'; $range.style.verticalAlign = 'middle'; $element.appendChild($div); const $button = document.createElement('button'); $button.innerHTML = '音量テスト'; $button.style.width = '120px'; $button.style.height = '45px'; $button.style.marginTop = '12px'; $button.style.marginLeft = '32px'; $button.addEventListener('click', () => { sounds[0].currentTime = 0; sounds[0].play(); }); $element.appendChild($button); function setVolume(){ for(let i = 0; i < sounds.length; i++) sounds[i].volume = volume; } } |
ゲーム開始以降の処理は次回とします。
