JavaScriptで箱入り娘を作る（1）の続きです。今回はギブアップしたときに解を表示させる機能を追加します。
Contents
Statusクラスの定義
現在の盤面の状態を操作できるようにStatusクラスを定義します。
コンストラクタ
コンストラクタを示します。引数は操作後のarray2x2、手数、操作前のブロックがあった位置、移動方向です。
移動させたときにarray2x2の要素が変わってしまわないように引数として渡されたarray2x2のコピーをthis.Array2x2に格納しています。ここからRectangleオブジェクトの配列も生成しています。
また一度探索をした部分を何度も探索して無限ループに入りこまないようにarray2x2の要素をつなげて文字列にしたものをKeyにしています（異なるブロックでも同じ種類であれば同一局面とみなす）。
|
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 |
class Status { constructor(array2x2, numberOfSteps, beforeRow, beforeCol, moveDirect){ this.NumberOfSteps = numberOfSteps; this.BeforeRow = beforeRow; this.BeforeCol = beforeCol; this.MoveDirect = moveDirect; this.Array2x2 = []; for(let row = 0; row < ROW_COUNT; row++){ this.Array2x2.push([]); for(let col = 0; col < COL_COUNT; col++) this.Array2x2[row].push(array2x2[row][col]); } // ブロックのコピーをつくる（色や書かれている文字は必要ないので空文字を渡す） this.Rectangles = []; for(let row=0; row<ROW_COUNT; row++){ for(let col=0; col<COL_COUNT; col++){ if(this.Array2x2[row][col] == '単') this.Rectangles.push(new Rectangle(row, col, 1, 1, '', '')); if(this.Array2x2[row][col] == '上') this.Rectangles.push(new Rectangle(row, col, 1, 2, '', '')); if(this.Array2x2[row][col] == '左') this.Rectangles.push(new Rectangle(row, col, 2, 1, '', '')); if(this.Array2x2[row][col] == '娘') this.Rectangles.push(new Rectangle(row, col, 2, 2, '', '')); } } let text = ''; for (let row = 0; row < ROW_COUNT; row++){ for (let col = 0; col < COL_COUNT; col++) text += array2x2[row][col]; } this.Key = text; } } |
移動可能か？
引数で指定されたブロックを引数で指定された方向に移動可能かを調べる処理を示します。ここでは例えば左に移動させるのであればブロックの左側の座標をすべて取得し、1個以上の座標が存在し、そのすべてが’空’であれば移動可能であると判定しています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Status { CanMove(rectangle, direct){ let nexts = []; if(direct == 'up') nexts = rectangle.GetUpperNextPositions(); if(direct == 'down') nexts = rectangle.GetLowerNextPositions(); if(direct == 'left') nexts = rectangle.GetLeftNextPositions(); if(direct == 'right') nexts = rectangle.GetRightNextPositions(); const len = nexts.length; if(len > 0 && nexts.filter(_ => this.Array2x2[_.Row][_.Col] == '空').length == len) return true; else return false; } } |
移動させる
引数で指定されたブロックを引数で指定された方向に移動させる処理を示します。ここでは移動可能であればRectangle.RowとRectangle.Colの値を変更してStatus.Array2x2を更新しています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class Status { MoveRectangle(rectangle, direct){ if(!this.CanMove(rectangle, direct)) return false; if(direct == 'up') rectangle.Row--; if(direct == 'down') rectangle.Row++; if(direct == 'left') rectangle.Col--; if(direct == 'right') rectangle.Col++; this.UpdateArray2x2(); // ブロックの位置が変更されたので this.Array2x2を更新する（後述） return true; } } |
Status.Array2x2を更新する処理を示します。
|
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 |
class Status { UpdateArray2x2(){ for(let row = 0; row < ROW_COUNT; row++){ for(let col = 0; col < COL_COUNT; col++) this.Array2x2[row][col] = '空'; } for(let i= 0; i<this.Rectangles.length; i++){ const rect = this.Rectangles[i]; if(rect.HCount == 1 && rect.VCount == 1) this.Array2x2[rect.Row][rect.Col] = '単'; if(rect.HCount == 1 && rect.VCount == 2){ this.Array2x2[rect.Row][rect.Col] = '上'; this.Array2x2[rect.Row + 1][rect.Col] = '下'; } if(rect.HCount == 2 && rect.VCount == 1){ this.Array2x2[rect.Row][rect.Col] = '左'; this.Array2x2[rect.Row][rect.Col + 1] = '右'; } if(rect.HCount == 2 && rect.VCount == 2){ this.Array2x2[rect.Row][rect.Col] = '娘'; this.Array2x2[rect.Row][rect.Col + 1] = '娘1'; this.Array2x2[rect.Row + 1][rect.Col] = '娘2'; this.Array2x2[rect.Row + 1][rect.Col + 1] = '娘3'; } } } } |
移動後の結果をすべて取得する
GetMoveResults関数は移動可能なすべてのブロックを移動させて新しいStatusオブジェクトの配列を返します。
2マス移動可能な場合もあるので1マス移動させたらさらに移動できるか試してみます。移動できたら移動後の状態を配列に格納し、すぐに移動前の状態に戻します。Status.Rectanglesに格納されているオブジェクトに対して4方向の移動を試すことで移動後のすべての結果を取得することができます。
|
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 |
class Status { GetMoveResults(){ const results = []; for(let i=0; i<this.Rectangles.length; i++){ const beforeRow = this.Rectangles[i].Row; const beforeCol = this.Rectangles[i].Col; if(this.MoveRectangle(this.Rectangles[i], 'up')){ results.push(new Status(this.GetCopyArray2x2(), this.NumberOfSteps + 1, beforeRow, beforeCol, 'up')); // 結果を取得 if(this.MoveRectangle(this.Rectangles[i], 'up')){ results.push(new Status(this.GetCopyArray2x2(), this.NumberOfSteps + 1, beforeRow, beforeCol, 'up2')); // 結果を取得 this.MoveRectangle(this.Rectangles[i], 'down'); } this.MoveRectangle(this.Rectangles[i], 'down'); } if(this.MoveRectangle(this.Rectangles[i], 'down')){ results.push(new Status(this.GetCopyArray2x2(), this.NumberOfSteps + 1, beforeRow, beforeCol, 'down')); if(this.MoveRectangle(this.Rectangles[i], 'down')){ results.push(new Status(this.GetCopyArray2x2(), this.NumberOfSteps + 1, beforeRow, beforeCol, 'down2')); this.MoveRectangle(this.Rectangles[i], 'up'); } this.MoveRectangle(this.Rectangles[i], 'up'); } if(this.MoveRectangle(this.Rectangles[i], 'left')){ results.push(new Status(this.GetCopyArray2x2(), this.NumberOfSteps + 1, beforeRow, beforeCol, 'left')); if(this.MoveRectangle(this.Rectangles[i], 'left')){ results.push(new Status(this.GetCopyArray2x2(), this.NumberOfSteps + 1, beforeRow, beforeCol, 'left2')); this.MoveRectangle(this.Rectangles[i], 'right'); } this.MoveRectangle(this.Rectangles[i], 'right'); } if(this.MoveRectangle(this.Rectangles[i], 'right')){ results.push(new Status(this.GetCopyArray2x2(), this.NumberOfSteps + 1, beforeRow, beforeCol, 'right')); if(this.MoveRectangle(this.Rectangles[i], 'right')){ results.push(new Status(this.GetCopyArray2x2(), this.NumberOfSteps + 1, beforeRow, beforeCol, 'right2')); this.MoveRectangle(this.Rectangles[i], 'left'); } this.MoveRectangle(this.Rectangles[i], 'left'); } } return results; } } |
最短手順を表示する
上で定義したStatusクラスをつかって最短手順を取得して表示します。
最短手順を取得する
最短手順を取得するには現在のarray2x2をStatusクラスのコンストラクタに渡して最初のStatusオブジェクトを生成しqueue（実は配列）に格納します。そのあと幅優先探索で移動可能なブロックを移動してできるパターンをすべて取得し、これまでに探索していないものであればqueueに追加してqueueが空になるまで処理を繰り返します。
途中で娘が出口に存在するパターンが見つかったら解が存在するということなので、そのときのStatusオブジェクトを変数lastに格納します。そしてlastを最初の状態にむけて遡りながら取得されたStatusオブジェクトをretsに追加していきます。最後にretsを反転させればどのブロックをどの方向に移動するかがわかるようになります。
|
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 |
function solve(){ const queue = []; const checked = new Map(); const froms = new Map(); const start = new Status(array2x2, 0, 0, 0, ''); queue.push(start); checked.set(start.Key, 0); froms.set(start.Array2x2, null); let last = null; let min = 9999999; while (queue.length > 0){ const cur = queue.shift(); const results = cur.GetMoveResults(); for(let i=0; i<results.length; i++){ const result = results[i]; // 一度探索したパターンは無視する if (!checked.has(result.Key)) { checked.set(result.Key, result.NumberOfSteps); // 遡ることができるように前のStatusとセットにして辞書に登録する froms.set(result.Array2x2, cur); if (result.Array2x2[3][1] == '娘'){ if (min > result.NumberOfSteps){ min = result.NumberOfSteps; last = result; console.log('解が見つかった') } } queue.push(result); } else { // 一度探索したパターンでさらに手数が短いものが見つかったときの処理だが // じっさいにこのようなことは起きない const num = checked.get(result.Key); if(num > result.NumberOfSteps) console.log('この部分は実行されない') } } } if(last == null){ console.log('解なし') return null; } let rets = []; rets.push(last); while (true) { last = froms.get(last.Array2x2); if(last.Array2x2 == start.Array2x2) break; rets.push(last); } console.log(min) rets.reverse(); return rets; } |
解を表示する
ギブアップボタンをクリックしたときの処理を示します。solve関数が返したStatusオブジェクトの配列を順番にみていけばどの位置にあるブロックをどの方向に移動させればいいかがわかるのでそのとおりに移動させます。そして最後に娘を退場させます。
|
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 |
$giveup.addEventListener('click', async() => { clearInterval(intervalID); // 経過時間計測のタイマーを止める ignoreClick = true; // クリックしても反応しないようにする selectSound.currentTime = 0; selectSound.play(); $giveup.style.display = 'none'; const results = solve(); $numberOfSteps.innerHTML = '答えを表示しています'; for(let i=0; i<results.length; i++){ await new Promise(resolve => setTimeout(resolve, 500)); const result = results[i]; const rect = getRectangle(result.BeforeRow, result.BeforeCol); if(result.MoveDirect == 'up') await rect.Move('up'); if(result.MoveDirect == 'down') await rect.Move('down'); if(result.MoveDirect == 'left') await rect.Move('left'); if(result.MoveDirect == 'right') await rect.Move('right'); if(result.MoveDirect == 'up2'){ await rect.Move('up'); await rect.Move('up'); } if(result.MoveDirect == 'down2'){ await rect.Move('down'); await rect.Move('down'); } if(result.MoveDirect == 'left2'){ await rect.Move('left'); await rect.Move('left'); } if(result.MoveDirect == 'right2'){ await rect.Move('right'); await rect.Move('right'); } numberOfSteps++; $numberOfSteps.innerHTML = `${numberOfSteps} 手`; } await new Promise(resolve => setTimeout(resolve, 1000)); musumeGoOut(); await new Promise(resolve => setTimeout(resolve, 3000)); bgm.pause(); $numberOfSteps.innerHTML = '[開始]ボタンをクリックしてください'; $startButtons.style.display = 'block'; $giveup.style.display = 'none'; }); |
