うーん。これまたわかりにくいタイトルですね。要はこんな感じのパズルを作りたかったのです。
このパズルの目的は以下となります。
最初に釘をひとつだけ取り除く。
隣に色違いの釘が存在し、隣の隣に釘が存在しない場合、その釘を移動させることができる。
釘を移動させたら飛び越された釘を取り除く。
このような動作を繰り返して最下段の中央の釘のみを残して他の釘を取り除くことができたらクリアとする。
動画では単に飛び越えた釘を消すだけですが、これだと手順を覚えてしまうと誰でも簡単にできてしまうので、異なる色の釘でないと飛び越えて消すことができないというルールを追加しています。
Contents
解ける問題を生成することはできるのか？
このパズル。適当に釘を配置しておけば必ず解は存在するのでしょうか？ 残念ながら解が存在しない問題も生成されてしまいます。
ただ解が存在する場合はかなりの確率で存在するので適当に問題を生成して解が存在しない場合は作り直すという方針で問題ないことがわかりました。なのでここは乱数で問題を生成することにします。
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 43 44 45 46 47 48 49 50 |
<!DOCTYPE html> <html lang="ja"> <head> <meta charset="UTF-8"> <title>釘を飛び越して消していくパズル</title> <meta name = "viewport" content = "width=device-width, initial-scale = 1.0"> <link rel="stylesheet" href="./style.css"> <link rel="shortcut icon" type="image/x-icon" href="https://lets-csharp.com/wp-content/themes/cool_black/favicon.ico"> </head> <body> <div id = "container"> <div id = "field"> <div id = "how-to-play"> <span id = "how-to-play-inner"> 遊び方：最初にひとつだけ釘を取り除きます。 そのあと釘を <span class = "red">隣の隣で釘がない場所</span> に移動させます。 そのとき <span class = "red">色違いの釘を飛び越える</span> ように移動させなければなりません。 飛び越えられた釘は取り除かれます。 <span class = "red">最下段中央の釘 (それ以外は失敗)</span> だけ残してそれ以外の釘を取り除くことができたらクリアです。 </span> </div> <div id = "field-header"> <div id = "time"></div> </div> <div id = "canvas-outer"></div> <div id = "navi"></div> <div id = "ctrl-buttons"> <button id = "go-back">ひとつ戻す</button> <button id = "give-up">ギブアップ</button> </div> <div id = "volume"></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> </div> <script src = "./index.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 97 |
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: 560px; margin-left: auto; margin-right: auto; position: relative; border: 0px wheat solid; } #field-header { margin-top: 4px; margin-bottom: 8px; font-size: larger; } #how-to-play { overflow: hidden; } #how-to-play-inner { margin-left: 400px; width: 1200px; white-space: nowrap; } #canvas-outer { width: 360px; border: 0px red solid; } #start-buttons { position: absolute; left: 0px; top: 140px; 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; } #ctrl-buttons { margin-top: 8px; margin-bottom: 16px; text-align: center; } #go-back, #give-up { width: 120px; height: 40px; margin-left: 10px; margin-right: 10px; vertical-align: middle; } .red { color: magenta; font-weight: bold; } .aqua { color: aqua; font-weight: bold; } .ml { margin-left: 20px; } #giveup { display: inline; } |
グローバル変数と定数
グローバル変数と定数を以下のように定義します。
index.js
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
const CANVAS_WIDTH = 360; const CANVAS_HEIGHT = 320; const CELL_RADIUS = 34; // マスの半径 const TOP_CX = 180; // 一番上にあるマスの中心のXY座標 const TOP_CY = 40; const $canvas = document.createElement('canvas'); // canvasを生成してコンテキストを取得 $canvas.width = CANVAS_WIDTH; $canvas.height = CANVAS_HEIGHT; document.getElementById('canvas-outer').appendChild($canvas); const ctx = $canvas.getContext('2d'); |
Cellクラスの定義
釘が配置されるマスは円形です。マスの描画と隣接関係を管理できるようにするためにCellクラスを定義します。
マスの位置とインデックスは以下のようにします。row * (row + 1) / 2 + col とやれば 0 ～ 15の連続する整数でindexを割り振ることができます。
|
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 |
class Cell { constructor(r, c){ const cx = TOP_CX + CELL_RADIUS * (2 * c - r); const cy = TOP_CY + r * CELL_RADIUS * 1.75; this.CX = cx; this.CY = cy; this.Index = this.GetIndex(r, c); // 隣のマスと隣の隣のマスのindexを格納する。これで移動可能なマスを管理できる this.MovablePairs = []; // 隣と隣の隣のindexを取得して格納する const diffs = [[1,0], [-1, 0], [0, 1], [0, -1], [1,1], [-1, -1]]; diffs.forEach(diff => { const nr1 = r + diff[0]; const nc1 = c + diff[1]; const nr2 = r + diff[0] * 2; const nc2 = c + diff[1] * 2; if(nr2 >= 0 && nr2 < 5 && nc2 >= 0 && nc2 <= nr2) this.MovablePairs.push([this.GetIndex(nr1, nc1), this.GetIndex(nr2, nc2)]); }); } GetIndex(r, c){ return r * (r + 1) / 2 + c; } // 引数は移動元のマスとして選択されている状態にあるかどうか？ Draw(isSelected){ if(!isSelected){ ctx.strokeStyle = '#fff'; ctx.lineWidth = 2; } else { ctx.strokeStyle = '#ff0'; ctx.lineWidth = 6; } ctx.beginPath(); ctx.arc(this.CX, this.CY, CELL_RADIUS, 0, Math.PI * 2); ctx.stroke(); ctx.lineWidth = 1; } } |
Nailクラスの定義
釘の描画とその座標を管理するためにNailクラスを定義します。
|
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 |
class Nail { constructor(color){ this.CX = 0; // 中心座標 this.CY = 0; this.Color = color; // 色 this.Exist = true; // その釘は存在するかどうか？ this.Image = new Image(); if(color == '1') this.Image.src = './images/red.png'; if(color == '2') this.Image.src = './images/green.png'; if(color == '3') this.Image.src = './images/blue.png'; } Draw(){ if(!this.Exist) return; const x = this.CX - CELL_RADIUS; const y = this.CY - CELL_RADIUS; ctx.drawImage(this.Image, x, y, CELL_RADIUS * 2, CELL_RADIUS * 2); } } |
QueueStackクラスの定義
幅優先探索で必要となるQueueの役割をするQueueStackクラスを定義します。これは 8パズルでゲームをつくる で示したものとまったく同じです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
class QueueStack { constructor(){ this.stackPush = []; this.stackPop = []; } Enqueue(value) { this.stackPush.push(value); } Count = () => this.stackPop.length + this.stackPush.length; Dequeue() { if (this.stackPop.length === 0) { while (this.stackPush.length > 0) this.stackPop.push(this.stackPush.pop()); } return this.stackPop.pop(); } } |
問題を生成する
問題を生成するQuestionGeneratorクラスを定義します。
コンストラクタの引数としてCellオブジェクトの配列を渡します。
|
1 2 3 4 5 |
class QuestionGenerator { constructor(cells){ this.Cells = cells; } } |
何色の釘がどのマスに存在するかを文字列で表すことにします。’0’ならそこには釘は存在せず、’1′,’2′,’3’であればその色の釘が存在するものとして扱います。
マスは15個あるので文字列も15文字です。初期状態では’1′,’2′,’3’の3種類の文字がそれぞれ5個ずつ存在します。初手ではこのなかからひとつを取り除くのでこのなかから1つを’0’に置き換えます。この置き換えられた文字列が引数として渡されます。
このパズルの目的は最下段の中央の釘を残してそれ以外の釘を消してしまうことです。これは言い換えると文字列を”000000000000100″か”000000000000200″か”000000000000300″のいずれかに変えてしまうことを意味します。Solve関数は幅優先探索でこれを実現することが可能であるかどうかを調べています。また一度探索した文字列を何度も探索しないようにMapで管理しています。
|
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 |
class QuestionGenerator { Solve(start){ let cur_nails = start; // 最終的に end_nails1, end_nails2, end_nails3 のいずれかになればよい const end_nails1 = "000000000000100"; const end_nails2 = "000000000000200"; const end_nails3 = "000000000000300"; const q = new QueueStack(); q.Enqueue(cur_nails); const set = new Set(); set.add(cur_nails); const map = new Map(); map.set(cur_nails, {text: '', from: -1, to: -1, deleted: cur_nails.indexOf('0')}); while (q.Count() > 0){ cur_nails = q.Dequeue(); // 釘が存在しない場所を調べる const missing = []; for (let i = 0; i < 15; i++){ if (cur_nails[i] == '0') missing.push(i); } // 釘が存在しない場所に移動できる釘を移動させてみる missing.forEach(idx => { const pairs = this.Cells[idx].MovablePairs; for(let i = 0; i < pairs.length; i++){ const pair = pairs[i]; if(cur_nails[pair[0]] == '0' || cur_nails[pair[1]] == '0') continue; if(cur_nails[pair[0]] == cur_nails[pair[1]]) continue; let arr = cur_nails.split(''); const ch = arr[pair[1]]; arr[pair[0]] = '0'; arr[pair[1]] = '0'; arr[idx] = ch; const next_nails = arr.join(''); if (!set.has(next_nails)){ q.Enqueue(next_nails); set.add(next_nails); map.set(next_nails, {text: cur_nails, from: pair[1], to: idx, deleted: pair[0]}); } } }); } // クリア可能であればその手順を取得する let last = ''; const arr = []; if (set.has(end_nails1)) last = end_nails1; else if (set.has(end_nails2)) last = end_nails2; else if (set.has(end_nails3)) last = end_nails3; else return null; while(true){ arr.push(map.get(last)); last = map.get(last).text; if(last == '') break; } arr.reverse(); // クリア可能かどうか？ 可能であればその手順も戻り値として返す const rets = []; arr.forEach(_ => rets.push({from: _.from, to: _.to, deleted: _.deleted})); return rets; } } |
GetAnswer関数は与えられた問題から釘をひとつ取り除いたパターン（全部で15種類）を生成して前述のSolve関数に渡します。そして解が存在するならその解を戻り値として返します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class QuestionGenerator { GetAnswer(question){ for(let i = 0; i < question.length; i++){ const chars = question.split(''); chars[i] = '0'; const start = chars.join(''); const ans = this.Solve(start); if(ans != null) return ans; } return null; } } |
Generate関数は乱数を生成してランダムに初期の釘の位置を決めて問題を生成します。そしてこれをGetAnswer関数に渡して本当に解が存在するかを調べます。解が存在するならこれを出題するために問題と解をセットにしたオブジェクトを戻り値として返します。解が存在しないなら解が存在する問題が生成させるまで処理を繰り返します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class QuestionGenerator { Generate(){ while(true){ // 3色の釘を5本ずつ生成してランダムにシャッフルする const arr = []; for(let a = 1; a <= 3; a++){ for(let b = 0; b < 5; b++) arr.push({char: a.toString(), rand: Math.random()}); } arr.sort((a, b) => a.rand - b.rand); // ランダムにシャッフルされた釘から文字列を生成して本当に解が存在するか調べる let q = ''; arr.forEach(_ => q += _.char); const ans = this.GetAnswer(q); if(ans != null) return {q: q, ans: ans}; else console.log('解なし'); } } } |
MoveHistoryクラスの定義
途中で操作前の状態に戻せるようにMoveHistoryクラスを定義します。
どの釘をどこからどこに移動させたのか、それにともなってどの位置にあった釘が消えたのかをコンストラクタの引数として渡します。
|
1 2 3 4 5 6 7 8 |
class MoveHistory { constructor(nail, oldCellIndex, deletedNail, deletedOldCellIndex){ this.Nail = nail; this.OldCellIndex = oldCellIndex; this.DeletedNail = deletedNail; this.DeletedOldCellIndex = deletedOldCellIndex; } } |
続きは次回とします。
