JavaScriptで四川省（二角取り）をつくる

四川省（二角取り）は麻雀牌を使ったパズルゲームです。同じ牌のペアを線でつなげた時に、線が曲がる回数が2回以内であればその牌を消すことができます。また同じ牌が隣接している場合も消せます。すべての牌を消すことができればゲームクリアです。慣れないとなかなか消えるペアを見つけることができません。

動作確認はこちらから

Contents

1 HTML部分
2 グローバル変数と定数
3 Cellクラスの定義
4 ページが読み込まれたときの処理
5 問題を解くことはできるのか？
- 5.1 取れる牌を調べる処理
6 問題を解くことはできるのか？
7 ゲーム開始の処理
8 クリック時の処理
- 8.1 手詰まりのチェック
9 「探す」コマンド
10 描画処理

HTML部分

<!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">
</head>

<body>

<div id = "field">
    <button id = "game-start">開始</button>
    <div id = "search-pair-outer">
        <button id = "search-pair">探す</button>
        できるだけこのコマンドに頼らず自分で考えましょう。
    </div>
    <div id = "volume"></div>
</div>

<script src="./app.js"></script>

</body>
</html>

<!DOCTYPE html>

<head>

<title>鳩でもわかる四川省（二角取り）</title>

</head>

<body>

できるだけこのコマンドに頼らず自分で考えましょう。

</div>

</div>

</body>

</html>

style.css

body {
    background-color: #080;
    color: #fff;
}
#game-start {
    position: absolute;
    left: 300px;
    top: 5px;
    height: 40px;
    width: 120px;
    z-index: 20;
}
#search-pair-outer {
    position: absolute;
    left: 50px;
    top: 520px;
    z-index: 20;
}
#search-pair {
    height: 40px;
    width: 120px;
}
#volume {
    position: absolute;
    left: 50px;
    top: 580px;
    z-index: 20;
}

body {

background-color: #080;

color: #fff;

}

#game-start {

position: absolute;

left: 300px;

top: 5px;

height: 40px;

width: 120px;

z-index: 20;

}

#search-pair-outer {

position: absolute;

left: 50px;

top: 520px;

z-index: 20;

}

#search-pair {

height: 40px;

width: 120px;

}

#volume {

position: absolute;

left: 50px;

top: 580px;

z-index: 20;

}

画像は素材サイトで麻雀牌の素材を探してそれを使います。そして萬子は11～19、筒子は21～29、索子は31～39、字牌は41～47の番号をつけて保存しておきます。

グローバル変数と定数

グローバル変数と定数を示します。

麻雀牌はcanvasに描画しますが、幅と高さがそれぞれCELL_WIDTH, CELL_HEIGHT のセルをつくり、そのなかに描画します。一番端のセルには牌は配置しません。二角取りできるかどうかは牌が置かれていないセルをとおって2回以内の方向転換で同じ牌とつながっているかどうかで判定します。

牌は全部で数牌が27種類、字牌が7種類で34種類あります。また同じ牌は4個あります。なので牌は最大で136個になります（春夏秋冬牌はなし）。なので(ROW_COUNT – 2 )×(const COL_COUNT – 2)は偶数であり136以下でなければなりません。以下のコードでは 8 × 17 でちょうど136になっています。

セルと牌の値は2次元配列に格納します。

app.js

const ROW_COUNT = 8 + 2;
const COL_COUNT = 17 + 2;

const CELL_WIDTH = 37;
const CELL_HEIGHT = 51;

const $field = document.getElementById('field')
const $searchPair = document.getElementById('search-pair')
const $searchPairOuter = document.getElementById('search-pair-outer')
const $gameStart = document.getElementById('game-start')

const $canvas = document.createElement('canvas');
const ctx = $canvas.getContext('2d');

const imageMap = new Map(); // 牌の番号から牌のイメージを取得できるようにするためのMap
const cells2x2 = [];
const value2x2 = [];

let selected = null; // 選択された牌
let suggested = []; // 探すコマンドで提案された牌のペア

let completedPath = []; // プレイヤーが2つの牌を選んだ時に二角取りが可能なら道筋を描画する
let suggestedPath = []; // 提案された2つの牌をつなぐ道筋

let isPlaying = false; // プレイ中？
let startTime = 0; // プレイ開始時刻
let seconds = 0; // プレイ時間の秒数
let giveuped = false; // 「探す」コマンドを使ったらギブアップとみなす

// 効果音
let volume = 0; // 音量

const gameclearSound = new Audio('./sounds/gameclear.mp3');
const gameoverSound = new Audio('./sounds/gameover.mp3');
const ngSound = new Audio('./sounds/ng.mp3');
const selectSound = new Audio('./sounds/select.mp3');
const selectSound2 = new Audio('./sounds/select2.mp3');
const deleteSound = new Audio('./sounds/delete.mp3');

const sounds = [gameclearSound, gameoverSound, ngSound, selectSound, selectSound2, deleteSound];

const ROW_COUNT = 8 + 2;

const COL_COUNT = 17 + 2;

const CELL_WIDTH = 37;

const CELL_HEIGHT = 51;

const $field = document.getElementById('field')

const $searchPair = document.getElementById('search-pair')

const $searchPairOuter = document.getElementById('search-pair-outer')

const $gameStart = document.getElementById('game-start')

const $canvas = document.createElement('canvas');

const ctx = $canvas.getContext('2d');

const imageMap = new Map(); // 牌の番号から牌のイメージを取得できるようにするためのMap

const cells2x2 = [];

const value2x2 = [];

let selected = null; // 選択された牌

let suggested = []; // 探すコマンドで提案された牌のペア

let completedPath = []; // プレイヤーが2つの牌を選んだ時に二角取りが可能なら道筋を描画する

let suggestedPath = []; // 提案された2つの牌をつなぐ道筋

let isPlaying = false; // プレイ中？

let startTime = 0; // プレイ開始時刻

let seconds = 0; // プレイ時間の秒数

let giveuped = false; // 「探す」コマンドを使ったらギブアップとみなす

// 効果音

let volume = 0; // 音量

const gameclearSound = new Audio('./sounds/gameclear.mp3');

const gameoverSound = new Audio('./sounds/gameover.mp3');

const ngSound = new Audio('./sounds/ng.mp3');

const selectSound = new Audio('./sounds/select.mp3');

const selectSound2 = new Audio('./sounds/select2.mp3');

const deleteSound = new Audio('./sounds/delete.mp3');

const sounds = [gameclearSound, gameoverSound, ngSound, selectSound, selectSound2, deleteSound];

Cellクラスの定義

Cellクラスを定義します。また上から◯行目、左か◯列目のセルの左上部分の座標を計算する関数も定義します。

function getX(col){
    return (CELL_WIDTH + 4) * col;
}
function getY(row){
    return (CELL_HEIGHT + 4) * row;
}

class Cell {
    constructor(row, col){
        this.Row = row;
        this.Col = col;
        this.X = getX(col);
        this.Y = getY(row);
    }
}

function getX(col){

return (CELL_WIDTH + 4) * col;

}

function getY(row){

return (CELL_HEIGHT + 4) * row;

}

class Cell {

constructor(row, col){

this.Row = row;

this.Col = col;

this.X = getX(col);

this.Y = getY(row);

}

ページが読み込まれたときの処理

ページが読み込まれたときは以下の処理がおこなわれます。

画像ファイルから牌のイメージを生成しimageMapに格納する。
各セルの位置の計算（createField関数 – 後述）
問題の生成（createProblem関数 – 後述）
ボタンクリックに反応するようにイベントリスナの追加
レンジスライダーで音量調節ができるようにする（initVolume関数 – 後述）
描画処理（draw関数 – 後述）

window.onload = () => {
    for(let i = 11; i <= 47; i++){
        if(i % 10 == 0)
            continue;
        const path = `./images/${i}.png`;
        const img = new Image();
        img.src = path;
        imageMap.set(i, img);
    }

    createField(); // 後述
    createProblem(); // 後述

    $searchPairOuter.style.display = 'none'; // ゲーム開始前は「探す」ボタンは非表示
    $gameStart?.addEventListener('click', () => gameStart()); // 後述
    $searchPair?.addEventListener('click', () => searchPair()); // 後述
    initVolume('volume', sounds); // 後述
    draw(); // 後述
}

window.onload = () => {

for(let i = 11; i <= 47; i++){

if(i % 10 == 0)

continue;

const path = `./images/${i}.png`;

const img = new Image();

img.src = path;

imageMap.set(i, img);

}

createField(); // 後述

createProblem(); // 後述

$searchPairOuter.style.display = 'none'; // ゲーム開始前は「探す」ボタンは非表示

$gameStart?.addEventListener('click', () => gameStart()); // 後述

$searchPair?.addEventListener('click', () => searchPair()); // 後述

initVolume('volume', sounds); // 後述

draw(); // 後述

}

createField関数

createField関数はセルの位置の計算と生成されたCellオブジェクトを2次元配列に格納する処理、描画用のcanvasを要素に追加する処理をおこないます。

また見えないdiv要素を生成して牌が描画される位置に配置します。これで牌がクリックされたときにクリックを検知することができるようになります。div要素と描画用のcanvasは position : absolute にします。

function createField(){
    // フィールド全体の幅と高さを計算する
    const fieldWidth = (CELL_WIDTH + 4) * COL_COUNT;
    const fieldHeight = (CELL_HEIGHT + 4) * ROW_COUNT;

    $field.style.position = 'relative';
    $field.style.width = `${fieldWidth}px`;
    $field.style.height = `${fieldHeight}px`;

    // セルの位置の計算とCellオブジェクトの生成
    cells2x2.length = ROW_COUNT;
    for(let row=0; row<ROW_COUNT; row++){
        cells2x2[row] = [];
        cells2x2[row].length = COL_COUNT;
        for(let col=0; col<COL_COUNT; col++)
            cells2x2[row][col] = new Cell(row, col);
    }

    for(let row=0; row<ROW_COUNT; row++){
        for(let col=0; col<COL_COUNT; col++){
            // 見えないdiv要素を生成して牌が描画される位置に配置する
            const $cell = document.createElement('div');
            $cell.style.position = 'absolute';
            $cell.style.width = `${CELL_WIDTH}px`;
            $cell.style.height = `${CELL_HEIGHT}px`;
            $cell.style.left = `${cells2x2[row][col].X}px`;
            $cell.style.top = `${cells2x2[row][col].Y}px`;
            $cell.style.zIndex = '10';
            $cell.addEventListener('click', (ev) => onCellClick(row, col));
            $field?.appendChild($cell);
        }
    }
    // 描画用のcanvasの追加
    $canvas.style.position = 'absolute';
    $canvas.width = fieldWidth;
    $canvas.height = fieldHeight;
    $canvas.style.left = `0px`;
    $canvas.style.top = `0px`;
    $canvas.style.zIndex = '1';
    $field?.appendChild($canvas);
}

function createField(){

// フィールド全体の幅と高さを計算する

const fieldWidth = (CELL_WIDTH + 4) * COL_COUNT;

const fieldHeight = (CELL_HEIGHT + 4) * ROW_COUNT;

$field.style.position = 'relative';

$field.style.width = `${fieldWidth}px`;

$field.style.height = `${fieldHeight}px`;

// セルの位置の計算とCellオブジェクトの生成

cells2x2.length = ROW_COUNT;

for(let row=0; row<ROW_COUNT; row++){

cells2x2[row] = [];

cells2x2[row].length = COL_COUNT;

for(let col=0; col<COL_COUNT; col++)

cells2x2[row][col] = new Cell(row, col);

}

for(let row=0; row<ROW_COUNT; row++){

for(let col=0; col<COL_COUNT; col++){

// 見えないdiv要素を生成して牌が描画される位置に配置する

const $cell = document.createElement('div');

$cell.style.position = 'absolute';

$cell.style.width = `${CELL_WIDTH}px`;

$cell.style.height = `${CELL_HEIGHT}px`;

$cell.style.left = `${cells2x2[row][col].X}px`;

$cell.style.top = `${cells2x2[row][col].Y}px`;

$cell.style.zIndex = '10';

$cell.addEventListener('click', (ev) => onCellClick(row, col));

$field?.appendChild($cell);

}

// 描画用のcanvasの追加

$canvas.style.position = 'absolute';

$canvas.width = fieldWidth;

$canvas.height = fieldHeight;

$canvas.style.left = `0px`;

$canvas.style.top = `0px`;

$canvas.style.zIndex = '1';

$field?.appendChild($canvas);

}

問題の生成

問題を生成する処理を示します。

初回実行のときだけ2次元配列value2x2を生成する処理をおこないます。そのあと問題を生成します。

問題を生成するときは牌の番号は11～47（ただし1の位が0は欠番）なので牌の番号と生成された乱数をセットにしたものを生成し作業用の配列に格納します。配列のサイズが途中で(ROW_COUNT – 2) * (COL_COUNT – 2)に達したら処理を終了します。そのあと乱数でソートします。こうすることで牌をシャッフルすることができます。

牌をシャッフルしたらその値を2次元配列value2x2に格納します。このとき端の要素には値を格納しない（0のままにする）ようにします。これで0の部分のみを通ってつながっている同じ牌を探すパズルの完成です。

ただし解けないパズルであってはいけません。なので最後にtest関数（後述）で解けるかどうかの確認をしています。解けない問題を生成してしまった場合は再度問題生成の処理をやりなおします。

function createProblem(){
    if(value2x2.length == 0){
        for(let row=0; row<ROW_COUNT; row++){
            const arr = [];
            for(let col=0; col<COL_COUNT; col++)
                arr[col] = 0;
            value2x2.push(arr);
        }
    }

    do {
        const values = [];
        let end = false;
        for(let v=11; v<=47; v++){
            if(v % 10 == 0)
                continue;
            for(let i=0; i<4; i++){
                values.push({value: v, random: Math.random()});
                if(values.length >= (ROW_COUNT - 2) * (COL_COUNT - 2)){
                    end = true;
                    break;
                }
            }
            if(end)
                break;
        }
        values.sort((a, b) => a.random - b.random);

        let idx = 0;
        for(let row=1; row<ROW_COUNT - 1; row++){
            for(let col=1; col<COL_COUNT - 1; col++){
                value2x2[row][col] = values[idx].value;
                idx++;
            }
        }
    } while(!test()); // test関数は後述
}

function createProblem(){

if(value2x2.length == 0){

for(let row=0; row<ROW_COUNT; row++){

const arr = [];

for(let col=0; col<COL_COUNT; col++)

arr[col] = 0;

value2x2.push(arr);

}

do {

const values = [];

let end = false;

for(let v=11; v<=47; v++){

if(v % 10 == 0)

continue;

for(let i=0; i<4; i++){

values.push({value: v, random: Math.random()});

if(values.length >= (ROW_COUNT - 2) * (COL_COUNT - 2)){

end = true;

break;

}

if(end)

break;

}

values.sort((a, b) => a.random - b.random);

let idx = 0;

for(let row=1; row<ROW_COUNT - 1; row++){

for(let col=1; col<COL_COUNT - 1; col++){

value2x2[row][col] = values[idx].value;

idx++;

}

} while(!test()); // test関数は後述

}

音量調整の処理

音量調整を可能にする処理を示します。これは毎度毎度のお決まりの処理です。

function initVolume(elementId, sounds){
    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 = value / 100;
        setVolume();
    });
    $range.addEventListener('change', () => localStorage.setItem('hatodemowakaru-volume', volume.toString()));

    setVolume();
    $span2.innerText = volume * 100;
    $span2.style.marginLeft = '16px';

    $range.value = volume * 100;
    $range.style.width = '250px';
    $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;
    }
}

function initVolume(elementId, sounds){

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 = value / 100;

setVolume();

});

$range.addEventListener('change', () => localStorage.setItem('hatodemowakaru-volume', volume.toString()));

setVolume();

$span2.innerText = volume * 100;

$span2.style.marginLeft = '16px';

$range.value = volume * 100;

$range.style.width = '250px';

$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;

}

問題を解くことはできるのか？

問題を解くことはできるのかを調べる処理を解説する前に取れる牌を調べる処理の解説します。

取れる牌を調べる処理

取れる牌を調べるには開始点を決め、開始点から牌が存在しないセルだけをとおって同じ種類の牌にたどり着けるかを調べればよいです。そのために幅優先探索の処理をおこないます。

ただ2つの牌を結ぶ線の曲がる回数は2回以内でなければならないというもうひとつ条件があります。これはどうすればよいでしょうか？

線の曲がる回数は「2回以内」であることから多くの解法が存在するかもしれませんが、ここは拡張ダイクストラ法で考えます。Qiitaの四川省の判定アルゴリズムと実装例記事では、「一般的な経路探索アルゴリズムを使って、出てきた経路が条件を満たしているか判定するというやり方は牛刀割鶏に過ぎる」とありますが、こちらにはこちらの考えがあるので牛刀割鶏なやり方で臨むことにします（おいおい）。

通常の幅優先探索やダイクストラ法では暫定的に取得された平面上の最短距離を2次元配列上に保存するのですが、ここでは二次元配列を4つ用意して三次元配列とします。そして以下のように遷移できるようにします。

dp[z1][y][x] → dp[z2][y][x ± 1]
z1 == z2 ならコスト1で移動可能、そうでないなら移動コストは10000

dp[z1][y][x] → dp[z2][y ± 1][x]
z1 == z2 ならコスト1で移動可能、そうでないなら移動コストは10000

※ 移動先である value2x2[ny][nx] が 0 または開始点の牌と同じ番号でないときは移動不可

あとは開始点と同じ種類の牌があるセルのdp[0][y][x] ～ dp[3][y][x]の値のなかで最小のものを調べ、値が30000未満であるかを調べることで、牌がない部分のみを通って、しかも2つの牌を結ぶ線の曲がる回数は2回以内になっているかどうかを知ることができます。

もし条件を満たすセルがある場合は開始点からそのセルにたどり着く道筋も取得しオブジェクトに格納して返すようにします。

以上の説明をコードにすると以下のようになります。

// search関数が取得した解を格納する
class SearchResult{
    constructor(row, col, corner, path){
        this.Row = row;
        this.Col = col;
        this.Corner = corner; // 何回曲がったか？（2以下）
        this.Path = path;
    }
}

function search(mat2x2, sr, sc){
    const sv = mat2x2[sr][sc];
    const max_cost = 10000000;
    const corner_cost = 10000;

    // 移動コストを格納する三次元配列を生成する
    const dp = [];
    for(let depth=0; depth < 4; depth++){
        const arr1 = [];
        for(let row=0; row<ROW_COUNT; row++){
            const arr2 = [];
            for(let col=0; col<COL_COUNT; col++)
                arr2[col] = max_cost;
            arr1.push(arr2);
        }
        dp.push(arr1);
    }

    // どこから来たのかを格納する三次元配列を生成する
    const froms = [];
    for(let depth=0; depth < 4; depth++){
        const arr1 = [];
        for(let row=0; row<ROW_COUNT; row++){
            const arr2 = [];
            for(let col=0; col<COL_COUNT; col++)
                arr2[col] = null;
            arr1.push(arr2);
        }
        froms.push(arr1);
    }

    const xs = [];
    const ys = [];
    const zs = [];

    // 4つの開始点に0をセット
    for(let z=0; z<4; z++){
        xs.push(sc);
        ys.push(sr);
        zs.push(z);
        dp[z][sr][sc] = 0;
    }

    const dx = [1, -1, 0, 0];
    const dy = [0, 0,  1, -1];

    while(xs.length > 0){
        const x = xs.shift();
        const y = ys.shift();
        const z = zs.shift();
        for(let nz=0; nz<4; nz++){
            const nx = x + dx[nz]; // 移動先
            const ny = y + dy[nz];
            if(nx < 0 || nx >= COL_COUNT || ny < 0 || ny >= ROW_COUNT) // 配列の範囲外
                continue;
            if(mat2x2[ny][nx] != 0 && mat2x2[ny][nx] != sv) // 移動不能
                continue;

            // 移動後のコスト（z == nzかどうかで加算されるコストを切り分ける）
            const ncost = z == nz ? dp[z][y][x] + 1 : dp[z][y][x] + corner_cost + 1;
            if(dp[nz][ny][nx] > ncost){ // コストが小さければ更新
                dp[nz][ny][nx] = ncost;
                froms[nz][ny][nx] = {x:x, y:y, z:z};
                if(mat2x2[ny][nx] == 0){ // mat2x2[ny][nx] == 0 ならここが新たな移動元となる
                    xs.push(nx);
                    ys.push(ny);
                    zs.push(nz);
                }
            }
        }
    }
    const searchResults = [];
    for(let row=0; row<ROW_COUNT; row++){
        for(let col=0; col<COL_COUNT; col++){
            if(row == sr && col == sc) // 開始点と同じなら無視
                continue;
            if(mat2x2[row][col] != sv) // 配置されている牌が開始点と種類が異なるなら無視
                continue;

            // コストの最小値とzの値を取得する
            const arr = [dp[0][row][col], dp[1][row][col], dp[2][row][col], dp[3][row][col]];
            let min = max_cost;
            let minIndex = 0;
            for(let i=0; i<4; i++){
                if(min > arr[i]){
                    min = arr[i];
                    minIndex = i;
                }
            }
            const corner = Math.floor(min / corner_cost);
            if(corner <= 2){ // 曲がる回数が2回以内で到達可能
                // 道筋も取得する
                const path = [];
                let lastX = col;
                let lastY = row;
                let lastZ = minIndex;
                path.push({row:lastY, col:lastX});
                while(true){
                    const from = froms[lastZ][lastY][lastX];
                    if(from == null)
                        break;
                    lastX = from.x;
                    lastY = from.y;
                    lastZ = from.z;
                    path.push({row:lastY, col:lastX});
                }
                searchResults.push(new SearchResult(row, col, corner, path));
            }
        }
    }
    return searchResults;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

// search関数が取得した解を格納する

class SearchResult{

constructor(row, col, corner, path){

this.Row = row;

this.Col = col;

this.Corner = corner; // 何回曲がったか？（2以下）

this.Path = path;

}

function search(mat2x2, sr, sc){

const sv = mat2x2[sr][sc];

const max_cost = 10000000;

const corner_cost = 10000;

// 移動コストを格納する三次元配列を生成する

const dp = [];

for(let depth=0; depth < 4; depth++){

const arr1 = [];

for(let row=0; row<ROW_COUNT; row++){

const arr2 = [];

for(let col=0; col<COL_COUNT; col++)

arr2[col] = max_cost;

arr1.push(arr2);

}

dp.push(arr1);

}

// どこから来たのかを格納する三次元配列を生成する

const froms = [];

for(let depth=0; depth < 4; depth++){

const arr1 = [];

for(let row=0; row<ROW_COUNT; row++){

const arr2 = [];

for(let col=0; col<COL_COUNT; col++)

arr2[col] = null;

arr1.push(arr2);

}

froms.push(arr1);

}

const xs = [];

const ys = [];

const zs = [];

// 4つの開始点に0をセット

for(let z=0; z<4; z++){

xs.push(sc);

ys.push(sr);

zs.push(z);

dp[z][sr][sc] = 0;

}

const dx = [1, -1, 0, 0];

const dy = [0, 0, 1, -1];

while(xs.length > 0){

const x = xs.shift();

const y = ys.shift();

const z = zs.shift();

for(let nz=0; nz<4; nz++){

const nx = x + dx[nz]; // 移動先

const ny = y + dy[nz];

if(nx < 0 || nx >= COL_COUNT || ny < 0 || ny >= ROW_COUNT) // 配列の範囲外

continue;

if(mat2x2[ny][nx] != 0 && mat2x2[ny][nx] != sv) // 移動不能

continue;

// 移動後のコスト（z == nzかどうかで加算されるコストを切り分ける）

const ncost = z == nz ? dp[z][y][x] + 1 : dp[z][y][x] + corner_cost + 1;

if(dp[nz][ny][nx] > ncost){ // コストが小さければ更新

dp[nz][ny][nx] = ncost;

froms[nz][ny][nx] = {x:x, y:y, z:z};

if(mat2x2[ny][nx] == 0){ // mat2x2[ny][nx] == 0 ならここが新たな移動元となる

xs.push(nx);

ys.push(ny);

zs.push(nz);

}

const searchResults = [];

for(let row=0; row<ROW_COUNT; row++){

for(let col=0; col<COL_COUNT; col++){

if(row == sr && col == sc) // 開始点と同じなら無視

continue;

if(mat2x2[row][col] != sv) // 配置されている牌が開始点と種類が異なるなら無視

continue;

// コストの最小値とzの値を取得する

const arr = [dp[0][row][col], dp[1][row][col], dp[2][row][col], dp[3][row][col]];

let min = max_cost;

let minIndex = 0;

for(let i=0; i<4; i++){

if(min > arr[i]){

min = arr[i];

minIndex = i;

}

const corner = Math.floor(min / corner_cost);

if(corner <= 2){ // 曲がる回数が2回以内で到達可能

// 道筋も取得する

const path = [];

let lastX = col;

let lastY = row;

let lastZ = minIndex;

path.push({row:lastY, col:lastX});

while(true){

const from = froms[lastZ][lastY][lastX];

if(from == null)

break;

lastX = from.x;

lastY = from.y;

lastZ = from.z;

path.push({row:lastY, col:lastX});

}

searchResults.push(new SearchResult(row, col, corner, path));

}

return searchResults;

}

問題を解くことはできるのか？

上記の乱数を用いて生成された問題を解くことはできるのかを検証する処理を示します。

実際に取ることができる牌を取り続けてすべて取りきることができるかを調べているだけです。このときvalue2x2の値を変更してはならないので値を別の2次元配列 copy2x2 にコピーしてシミュレートしています。

function test(){
    const copy2x2 = createCopy2x2();
    while(getRestCount(copy2x2) > 0){
        // 取れる牌があるなら消していく
        const ret = test0();
        if(ret == null) // まだ牌があるのに取れる牌がない場合は問題として不適
            return false;

        copy2x2[ret.row1][ret.col1] = 0;
        copy2x2[ret.row2][ret.col2] = 0;
    }
    return true;

    // 最初に見つかった取れる牌の位置のペアを返す（見つからない場合はnullを返す）
    function test0(){
        for(let row=0; row<ROW_COUNT; row++){
            for(let col=0; col<COL_COUNT; col++){
                if(copy2x2[row][col] > 0){
                    const results = search(copy2x2, row, col)
                    if(results.length > 0)
                        return {row1:row, col1:col, row2:results[0].Row, col2:results[0].Col};
                }
            }
        }
        return null;
    }
}

function test(){

const copy2x2 = createCopy2x2();

while(getRestCount(copy2x2) > 0){

// 取れる牌があるなら消していく

const ret = test0();

if(ret == null) // まだ牌があるのに取れる牌がない場合は問題として不適

return false;

copy2x2[ret.row1][ret.col1] = 0;

copy2x2[ret.row2][ret.col2] = 0;

}

return true;

// 最初に見つかった取れる牌の位置のペアを返す（見つからない場合はnullを返す）

function test0(){

for(let row=0; row<ROW_COUNT; row++){

for(let col=0; col<COL_COUNT; col++){

if(copy2x2[row][col] > 0){

const results = search(copy2x2, row, col)

if(results.length > 0)

return {row1:row, col1:col, row2:results[0].Row, col2:results[0].Col};

}

return null;

}

createCopy2x2 は 2次元配列 value2x2 のコピーをつくる関数です。getRestCount は残っている牌の数を求める関数です。

function createCopy2x2(){
    const copy2x2 = [];
    for(let row=0; row<ROW_COUNT; row++){
        copy2x2[row] = [];
        for(let col=0; col<COL_COUNT; col++)
            copy2x2[row][col] = value2x2[row][col];
    }
    return copy2x2;
}

function getRestCount(mat2x2){
    let count = 0;
    for(let row=0; row<ROW_COUNT; row++){
        for(let col=0; col<COL_COUNT; col++){
            if(mat2x2[row][col] > 0)
                count++;
        }
    }
    return count;
}

function createCopy2x2(){

const copy2x2 = [];

for(let row=0; row<ROW_COUNT; row++){

copy2x2[row] = [];

for(let col=0; col<COL_COUNT; col++)

copy2x2[row][col] = value2x2[row][col];

}

return copy2x2;

}

function getRestCount(mat2x2){

let count = 0;

for(let row=0; row<ROW_COUNT; row++){

for(let col=0; col<COL_COUNT; col++){

if(mat2x2[row][col] > 0)

count++;

}

return count;

}

ゲーム開始の処理

ゲームを開始する処理は以下のとおりです。

選択されている牌や組み合わせの情報が存在するならすべてクリアする
問題の生成
スタートボタンの非表示と「探す」ボタンの表示
効果音の再生
ゲーム開始時刻の取得と保存、プレイ秒数のリセット
isPlayingフラグのセットとgiveupedフラグのクリア

function gameStart(){
    selected = null; // 選択されている牌や組み合わせの情報が存在するならすべてクリア
    suggested = [];
    suggestedPath = [];

    createProblem();

    $gameStart.style.display = 'none';
    $searchPairOuter.style.display = 'block';

    selectSound2.currentTime = 0;
    selectSound2.play();

    startTime = Date.now();
    seconds = 0;
    isPlaying = true;
    giveuped = false;
}

function gameStart(){

selected = null; // 選択されている牌や組み合わせの情報が存在するならすべてクリア

suggested = [];

suggestedPath = [];

createProblem();

$gameStart.style.display = 'none';

$searchPairOuter.style.display = 'block';

selectSound2.currentTime = 0;

selectSound2.play();

startTime = Date.now();

seconds = 0;

isPlaying = true;

giveuped = false;

}

クリック時の処理

セルがクリックされたときの処理を示します。

プレイ開始前や牌を取り除く処理がおこなわれているときのクリックは無視します。

セルがクリックされたときにまだ1つ目の牌が選択されていないのであれば、対応するセルを選択状態にします。すでに選択されているときは新たにクリックされたセルに存在する牌とセットにして取り除くことができるかを調べます。

取り除くことができるなら取り除く処理をおこないます。できない場合は不正な選択なので警告音を鳴らします。いずれの場合も2つめの牌が選択された段階で1つめに選択されていた牌の情報はクリアされます。

取り除くことができる牌のペアが成立したらすぐに取り除かずに両者を結ぶ線を描画してしばらくしてから取り除く処理をおこないます。

function onCellClick(row, col){
    if(!isPlaying || completedPath.length > 0){ // 不正なクリック
        onIncorrectSelection(); // 後述
        return;
    }

    suggested.length = 0;
    suggestedPath = [];

    if(value2x2[row][col] == 0){ // 牌が存在しないセルをクリックした
        onIncorrectSelection();
        selected = null;
        return;
    }

    if(selected == null){ // 1つめの牌が選択された
        onSelect(); // 後述
        selected = cells2x2[row][col];
    }
    else {
        // 2つめの牌が選択されたらsearch関数が返す結果のなかにその牌が存在するか調べる
        const results = search(value2x2, selected.Row, selected.Col);
        let ok = false;
        for(let i=0; i<results.length; i++){
            if(row == results[i].Row && col == results[i].Col){
                ok = true;
                completedPath = results[i].Path; // ペアを結ぶ線を描画する
                break;
            }
        }
        if(ok){
            onSelect();
            const row0 = selected.Row;
            const col0 = selected.Col;
            setTimeout(() => { // 0.5秒後に牌を消す
                value2x2[row0][col0] = 0;
                value2x2[row][col] = 0;
                completedPath = [];
                matchingSucceeded(); // ペア成立時（後述）
            }, 500);
        }
        else {
            matchingFailed(); // ペア不成立時（後述）
        }
        selected = null; // どの牌も選択されていない状態にする
    }
}

function onCellClick(row, col){

if(!isPlaying || completedPath.length > 0){ // 不正なクリック

onIncorrectSelection(); // 後述

return;

}

suggested.length = 0;

suggestedPath = [];

if(value2x2[row][col] == 0){ // 牌が存在しないセルをクリックした

onIncorrectSelection();

selected = null;

return;

}

if(selected == null){ // 1つめの牌が選択された

onSelect(); // 後述

selected = cells2x2[row][col];

}

else {

// 2つめの牌が選択されたらsearch関数が返す結果のなかにその牌が存在するか調べる

const results = search(value2x2, selected.Row, selected.Col);

let ok = false;

for(let i=0; i<results.length; i++){

if(row == results[i].Row && col == results[i].Col){

ok = true;

completedPath = results[i].Path; // ペアを結ぶ線を描画する

break;

}

if(ok){

onSelect();

const row0 = selected.Row;

const col0 = selected.Col;

setTimeout(() => { // 0.5秒後に牌を消す

value2x2[row0][col0] = 0;

value2x2[row][col] = 0;

completedPath = [];

matchingSucceeded(); // ペア成立時（後述）

}, 500);

}

else {

matchingFailed(); // ペア不成立時（後述）

}

selected = null; // どの牌も選択されていない状態にする

}

ペア成立時はこれによってすべての牌が取り除かれてしまったかもしれません。この場合はゲームクリアの処理をおこないます。

function matchingSucceeded(){
    if(getRestCount(value2x2) == 0)
        onGameClear(); // 後述
    else if(checkStalemate()) // 後述
        onStalemate(); // 後述
    else
        onDelete(); // 後述
}

function onGameClear(){
    isPlaying = false;
    gameclearSound.currentTime = 0;
    gameclearSound.play();
    $gameStart.style.display = 'inline';
    $searchPairOuter.style.display = 'none';
}

function matchingSucceeded(){

if(getRestCount(value2x2) == 0)

onGameClear(); // 後述

else if(checkStalemate()) // 後述

onStalemate(); // 後述

else

onDelete(); // 後述

}

function onGameClear(){

isPlaying = false;

gameclearSound.currentTime = 0;

gameclearSound.play();

$gameStart.style.display = 'inline';

$searchPairOuter.style.display = 'none';

}

以下の処理は効果音を鳴らしているだけです。

// 選択された2つの牌は取ることができない組み合わせである
function matchingFailed(){
    ngSound.currentTime = 0;
    ngSound.play();
}

// 選択された2つの牌を消去した
function onDelete(){
    deleteSound.currentTime = 0;
    deleteSound.play();
}

// 牌を選択した
function onSelect(){
    selectSound.currentTime = 0;
    selectSound.play();
}

// 不正なクリックがおこなわれた
function onIncorrectSelection(){
    ngSound.currentTime = 0;
    ngSound.play();
}

// 選択された2つの牌は取ることができない組み合わせである

function matchingFailed(){

ngSound.currentTime = 0;

ngSound.play();

}

// 選択された2つの牌を消去した

function onDelete(){

deleteSound.currentTime = 0;

deleteSound.play();

}

// 牌を選択した

function onSelect(){

selectSound.currentTime = 0;

selectSound.play();

}

// 不正なクリックがおこなわれた

function onIncorrectSelection(){

ngSound.currentTime = 0;

ngSound.play();

}

手詰まりのチェック

牌を消去したときこれ以上牌を取り除くことができない、いわゆる手詰まりになっている可能性もあります。手詰まりのときはゲームオーバーの処理をおこないます。

詰まりになっているかどうかは以下の方法で確認できます。まず残されたすべての牌でsearch関数を実行します。もしすべて戻り値の配列の長さが0なら次の手は存在しない＝手詰まりと判断することができます。

function checkStalemate(){
    for(let row=0; row<ROW_COUNT; row++){
        for(let col=0; col<COL_COUNT; col++){
            if(value2x2[row][col] > 0){
                const results = search(value2x2, row, col)
                if(results.length > 0)
                    return false;
            }
        }
    }
    return true;
}

function onStalemate(){
    isPlaying = false;
    gameoverSound.currentTime = 0;
    gameoverSound.play();
    $gameStart.style.display = 'inline';
    $searchPairOuter.style.display = 'none';
}

function checkStalemate(){

for(let row=0; row<ROW_COUNT; row++){

for(let col=0; col<COL_COUNT; col++){

if(value2x2[row][col] > 0){

const results = search(value2x2, row, col)

if(results.length > 0)

return false;

}

return true;

}

function onStalemate(){

isPlaying = false;

gameoverSound.currentTime = 0;

gameoverSound.play();

$gameStart.style.display = 'inline';

$searchPairOuter.style.display = 'none';

}

「探す」コマンド

自分で取ることができる牌を見つけることができない場合は「探す」ボタンをクリックすることで候補が示されます。その処理を示します。

これは最初に発見した取れる牌の組み合わせを表示しているだけです。なので最適解とは限りません。またこの機能を使用したらギブアップしたものとして処理をします。

function searchPair(){
    if(!isPlaying || completedPath.length > 0)
        return;

    selectSound2.currentTime = 0;
    selectSound2.play();
    giveuped = true;

    selected = null; // すでに1つめの牌がユーザーによって選択されている場合はクリアする

    let row1 = -1;
    let col1 = -1;
    let row2 = -1;
    let col2 = -1;
    let path = null;
    for(let row=0; row<ROW_COUNT; row++){
        for(let col=0; col<COL_COUNT; col++){
            if(value2x2[row][col] > 0){
                const results = search(value2x2, row, col)
                if(results.length > 0){
                    row1 = row;
                    col1 = col;
                    row2 = results[0].Row;
                    col2 = results[0].Col;
                    path = results[0].Path;
                    break;
                }
            }
        }
        if(row1 != -1)
            break;
    }
    if(row1 != -1){
        // 提案された牌の組み合わせを変数に格納する
        suggested[0] = cells2x2[row1][col1];
        suggested[1] = cells2x2[row2][col2];
        suggestedPath = path;
    }
    else {
        suggested.length = 0;
        suggestedPath = [];
    }
}

function searchPair(){

if(!isPlaying || completedPath.length > 0)

return;

selectSound2.currentTime = 0;

selectSound2.play();

giveuped = true;

selected = null; // すでに1つめの牌がユーザーによって選択されている場合はクリアする

let row1 = -1;

let col1 = -1;

let row2 = -1;

let col2 = -1;

let path = null;

for(let row=0; row<ROW_COUNT; row++){

for(let col=0; col<COL_COUNT; col++){

if(value2x2[row][col] > 0){

const results = search(value2x2, row, col)

if(results.length > 0){

row1 = row;

col1 = col;

row2 = results[0].Row;

col2 = results[0].Col;

path = results[0].Path;

break;

}

if(row1 != -1)

break;

}

if(row1 != -1){

// 提案された牌の組み合わせを変数に格納する

suggested[0] = cells2x2[row1][col1];

suggested[1] = cells2x2[row2][col2];

suggestedPath = path;

}

else {

suggested.length = 0;

suggestedPath = [];

}

描画処理

描画処理を示します。

初期化の処理がおこなわれていない場合（value2x2の長さが0のとき）はなにもしません。

もし牌と牌をつなぐ道筋が存在する場合はそれを先に描画します。そのあと各セルがある位置に牌が存在する場合は対応するイメージを取得してそれを描画します。もし選択されている牌や提案されている牌がある場合はその位置に赤い枠も描画します。

またプレイ中でギブアップしていない場合は経過時間を取得（開始時刻と現在時刻の差から調べる）してこれを左上に表示します。ギブアップ時はその旨表示します。

function draw(){
    requestAnimationFrame(() => {
        draw();
    })

    if(value2x2.length == 0)
        return;

    ctx.fillStyle = '#080';
    ctx.fillRect(0, 0, $canvas.width, $canvas.height);

    drawPath(completedPath);
    drawPath(suggestedPath);

    for(let row=0; row<ROW_COUNT; row++){
        for(let col=0; col<COL_COUNT; col++){
            const x = cells2x2[row][col].X
            const y = cells2x2[row][col].Y
            const v = value2x2[row][col];
            if(!imageMap.has(v))
                continue;

            const image = imageMap.get(v);
            ctx?.drawImage(image, x, y, CELL_WIDTH, CELL_HEIGHT);
        }
    }
    if(selected != null){
        ctx.strokeStyle = '#f00';
        ctx.lineWidth = 2;
        ctx?.strokeRect(selected.X - 1, selected.Y - 1, CELL_WIDTH + 2, CELL_HEIGHT + 2);
    }
    if(suggested.length == 2){
        ctx.strokeStyle = '#f00';
        ctx.lineWidth = 2;
        for(let i = 0; i < 2; i++)
            ctx?.strokeRect(suggested[i].X - 1, suggested[i].Y - 1, CELL_WIDTH + 2, CELL_HEIGHT + 2);
    }
    if(isPlaying)
        seconds = Math.floor((Date.now() - startTime) / 1000);

    ctx.font='24px Arial';
    ctx.textBaseline='top';
    ctx.fillStyle = '#fff';
    if(!giveuped){
        const min = Math.floor(seconds / 60);
        let sec = seconds % 60 < 10 ? '0' + seconds % 60 : seconds % 60;
        const text = `経過時間 ${min} 分 ${sec} 秒`;
        ctx.fillText(text, 50, 14);
    }
    else
        ctx.fillText('GIVE UP', 50, 14);
}

function draw(){

requestAnimationFrame(() => {

draw();

})

if(value2x2.length == 0)

return;

ctx.fillStyle = '#080';

ctx.fillRect(0, 0, $canvas.width, $canvas.height);

drawPath(completedPath);

drawPath(suggestedPath);

for(let row=0; row<ROW_COUNT; row++){

for(let col=0; col<COL_COUNT; col++){

const x = cells2x2[row][col].X

const y = cells2x2[row][col].Y

const v = value2x2[row][col];

if(!imageMap.has(v))

continue;

const image = imageMap.get(v);

ctx?.drawImage(image, x, y, CELL_WIDTH, CELL_HEIGHT);

}

if(selected != null){

ctx.strokeStyle = '#f00';

ctx.lineWidth = 2;

ctx?.strokeRect(selected.X - 1, selected.Y - 1, CELL_WIDTH + 2, CELL_HEIGHT + 2);

}

if(suggested.length == 2){

ctx.strokeStyle = '#f00';

ctx.lineWidth = 2;

for(let i = 0; i < 2; i++)

ctx?.strokeRect(suggested[i].X - 1, suggested[i].Y - 1, CELL_WIDTH + 2, CELL_HEIGHT + 2);

}

if(isPlaying)

seconds = Math.floor((Date.now() - startTime) / 1000);

ctx.font='24px Arial';

ctx.textBaseline='top';

ctx.fillStyle = '#fff';

if(!giveuped){

const min = Math.floor(seconds / 60);

let sec = seconds % 60 < 10 ? '0' + seconds % 60 : seconds % 60;

const text = `経過時間 ${min} 分 ${sec} 秒`;

ctx.fillText(text, 50, 14);

}

else

ctx.fillText('GIVE UP', 50, 14);

}

これは牌と牌を結ぶ道筋を描画する処理です。

function drawPath(path){
    if(path.length > 1){
        ctx?.beginPath();
        const x0 = getX(path[0].col) + CELL_WIDTH / 2;
        const y0 = getY(path[0].row) + CELL_HEIGHT / 2;
        ctx?.moveTo(x0, y0);

        for(let i=1; i<path.length; i++){
            const x = getX(path[i].col) + CELL_WIDTH / 2;
            const y = getY(path[i].row) + CELL_HEIGHT / 2;
            ctx?.lineTo(x, y);
        }
        ctx.strokeStyle = '#f00';
        ctx.lineWidth = 4;
        ctx?.stroke();
    }
}

function drawPath(path){

if(path.length > 1){

ctx?.beginPath();

const x0 = getX(path[0].col) + CELL_WIDTH / 2;

const y0 = getY(path[0].row) + CELL_HEIGHT / 2;

ctx?.moveTo(x0, y0);

for(let i=1; i<path.length; i++){

const x = getX(path[i].col) + CELL_WIDTH / 2;

const y = getY(path[i].row) + CELL_HEIGHT / 2;

ctx?.lineTo(x, y);

}

ctx.strokeStyle = '#f00';

ctx.lineWidth = 4;

ctx?.stroke();

}

動作確認はこちらから

JavaScriptで四川省（二角取り）をつくる

HTML部分

グローバル変数と定数

Cellクラスの定義

ページが読み込まれたときの処理

createField関数

問題の生成

音量調整の処理

問題を解くことはできるのか？

取れる牌を調べる処理

問題を解くことはできるのか？

ゲーム開始の処理

クリック時の処理

手詰まりのチェック

「探す」コマンド

描画処理

鳩でも分かるC#管理人からのお願い

コメントについて

管理人のモチベーションアップのために

コメントをどうぞ