はじめに

PNG ¹ を読み込ませたらノノグラム(お絵かきロジック/ピクロス/etc)と呼ばれるパズルが生成されるWebサービスを作りました。

GitHub Pagesを使って静的サイト（サーバーレス）として動くようになっています。

PNGを読み込んだあとTwitterでシェアすると、他の人が遊べるようにもなっています。

クエリパラメータがついたリンク1(かんたん)
クエリパラメータがついたリンク2(むずかしい)

ソースコードはこちらから。

きっかけ

ドット絵が好き+せっかくだから自分で作ったドット絵で遊びたい
→PNGファイルをアップロードしたらノノグラムが自動で作られればいいのでは！

実装

実装は、ざっくりとファイルの読み込み、ノノグラムの計算、描画で別れています。

処理のフロー

PNGを読み込み
チャンクと呼ばれるデータに分割
読み込みに必要なデータの取得
圧縮されている画像データの展開
パレット番号で分けられた画像データのマトリクスの生成
パレットの読み込み
マトリクスから数値の計算
canvasで描画

PNGの読み込み

まずはFile APIでPNGを読み込みます。

window.onload

    document.getElementById("file").addEventListener("change", function (e) {
        const file = e.target.files;
        const reader = new FileReader();
        // ファイルをDataURIで読み込み
        reader.readAsDataURL(file[0]);

        // ファイルが読み込めたら処理開始
        reader.onload = function () {
            const src = reader.result.split(',')[1];
            main(src);
        };
    }, false);

リンクから遊べることを目標にしていたので読み込みはDataURLとしました。
読み込んだものはdata:image/gif;base64,以下base64文字列〜〜となっているので、,で区切って2つ目を利用します。

main(src)

    const binary = atob(src);
    const uint8array = Uint8Array.from(binary.split(""), e => e.charCodeAt(0));

また、読み込んだものを、JavaScriptでバイナリを扱うときによく使うUint8Arrayに入れています。

チャンクと呼ばれるデータに分割

PNGというファイルフォーマットは先頭にファイルシグネチャがあり、それ以降はチャンクと呼ばれるデータのまとまりに別れています。
今回利用するノノグラムで遊ぶことができるPNGはだいたい以下の構成になっています。

チャンク名	サイズ	説明
PNGファイルシグネチャ	8byte	PNGであることの確認
IHDRチャンク	25byte	イメージヘッダ
PLTEチャンク	3×色数+12byte	パレット
tRNSチャンク	透明色数+12byte	透明色情報
IDATチャンク	可変長	データ
IENDチャンク	12byte	イメージ終端

他にもチャンクはありますので、詳しく知りたい方はこちらからどうぞ。
https://www.setsuki.com/hsp/ext/png.htm

それぞれのチャンクは最初にLengthが入っている構成です。

main(src)

    for (let i = 8; i < uint8array.length; i += splitChunk.slice(-1)[0].chunkLength + 12) {
        splitChunk.push(readChunk(uint8array.slice(i)));
    }

そこで、前のチャンクのサイズ分進んで読み込むということを繰り返すようにしました。

readChunk()

function readChunk(source) {
    const chunklength = new Uint32Array(source.slice(0, 4).reverse().buffer)[0];
    const chunktype = Array.from(source.slice(4, 8), e => String.fromCharCode(e)).join("");
    const chunkdata = source.slice(8, 8 + chunklength);
    const chunkcrc = source.slice(8 + chunklength, 12 + chunklength);
    return { chunkLength: chunklength, chunkType: chunktype, chunkData: chunkdata, chunkCRC: chunkcrc };
}

読み込み項目ははこんな感じ。

読み込みに必要なデータの取得

続いて、分けたチャンクから必要なデータを取り出します。

main(src)

    //　PNGの縦横サイズ
    const pngwidth = new Uint32Array(splitChunk.filter(x => x.chunkType === 'IHDR')[0].chunkData.slice(0, 4).reverse().buffer)[0];
    const pngheight = new Uint32Array(splitChunk.filter(x => x.chunkType === 'IHDR')[0].chunkData.slice(4, 8).reverse().buffer)[0];

    //　読み込みに必要なデータの所得
    const bitdepth = splitChunk.filter(x => x.chunkType === 'IHDR')[0].chunkData[8];
    const colortype = splitChunk.filter(x => x.chunkType === 'IHDR')[0].chunkData[9];
    let tRNSdata = 0;

pngwidthとpngheightはその名の通りPNGの幅と高さ。
bitdepthはビット深度というもので、色を表すのに何ビット使うかを表しています。
colortypeはPNGの色のタイプを表したものです。
今回の仕組み的にはパレットが必須なので、3以外はNGとしています。
tRNSdataは透過色を示したもので、今回は0番のパレットを透過色としています。

圧縮されている画像データの展開

今回のチャンクの中で、データが格納されているIDATはzlibで圧縮されています。
そこで、展開します。

main(src)

    const compressed = splitChunk.filter(x => x.chunkType === 'IDAT')[0].chunkData;
    const idatdata = new Zlib.Inflate(compressed).decompress();

今回は自分で展開のコードを書く必要は薄かったため、こちらを利用しています。
とても便利。
https://github.com/imaya/zlib.js/

パレット番号で分けられた画像データのマトリクスの生成

画像データからパレット番号のマトリクスを生成しています。

main(src)

    const pngmatrix = makePNGMatrix(idatdata, pngwidth, pngheight, bitdepth);

makePNGMatrix()

function makePNGMatrix(data, pngwidth, pngheight, bitdepth) {
    const pngmatrix = [];
    const depthwidth = pngwidth / (8 / bitdepth);
    for (let i = 0; i < pngheight; i++) {
        let row = Array.from(data.slice((depthwidth + 1) * i + 1, (depthwidth + 1) * (i + 1)));
        if (bitdepth < 8) {
            row = optimizeData(row, bitdepth);
        }
        pngmatrix.push(row);
    }
    return pngmatrix;
}

optimizeData()

function optimizeData(source, bitdepth) {
    const optimizeData = [];
    for (let i = 0; i < source.length; i++) {
        for (let j = 0; j < 8 / bitdepth; j++) {
            optimizeData.push((source[i] >> bitdepth * (8 / bitdepth - j - 1)) & (2 ** bitdepth - 1));
        }
    }
    return optimizeData;
}

PNGのデータをまず行ごとに分けて、その行を列の数で分割しています。
ビット深度という概念があるため若干複雑になっていますね。

パレットの読み込み

次に、パレットを読み込みます。

main(src)

// 使ってる色のパレット番号の取り出し
const pngpalettecolor = paletteColor(splitChunk.filter(x => x.chunkType === 'PLTE')[0].chunkData);

paletteColor()

function paletteColor(source) {
    const palette = [];
    for (i = 0; i < source.length / 3; i++) {
        palette.push([source[3 * i], source[3 * i + 1], source[3 * i + 2]]);
    }
    return palette;
}

こちらはPLTEチャンクのデータ部分にRGBの順に並んでいるので、そのまま3つずつ読み込めばOKです。

マトリクスから数値の計算

最後にノノグラムの肝、問題部分の数値の計算です。

main(src)

    // nonogramの数字の計算
    const numberrow = makeNumber(pngmatrix, tRNSdata);
    const numbercolumn = makeNumber(transpose(pngmatrix), tRNSdata);

縦と横、2つ計算する必要があります。
同じ関数を使い、マトリクスを転置することで計算を行いました。

makeNumber()

function makeNumber(arr, alpha) {
    const numberrowarray = [];
    let maxnumber = 0;
    for (let i = 0; i < arr.length; i++) {
        let calcnum = calcNumber(arr[i]);
        calcnum = calcnum.filter(x => (x[0] !== alpha)&&(x[0] !== -1));
        if (calcnum.length === 0) {
            calcnum.push([-1, 0]);
        }
        numberrowarray.push(calcnum);
        maxnumber = Math.max(maxnumber, calcnum.length);
    }
    return [numberrowarray, maxnumber];
}

calcNumber()

function calcNumber(arr) {
    const calculated = [[arr[0], 1]];
    for (let i = 1; i < arr.length; i++) {
        if (calculated.slice(-1)[0][0] === arr[i]) {
            calculated.slice(-1)[0][1]++;
        } else {
            calculated.push([arr[i], 1]);
        }
    }
    return calculated;
}

色と数字のペアを作り、マトリクスの値を順番に見て、隣と色が一緒ならば数を1つ増やしています。
色が違っていれば新しい色と数値のペアを作成しています。
また、このときに最初に指定した透過色は無視するようにしています。
-1も一緒に無視していますが、これは後述します。

最後のmaxnumberという値を返却していますが、これはcanvasサイズを決定するのに必要なため返却しています。

canvasで描画

最後に、計算した数字と実際に描写するマトリクス、およびパレットを描画します。
合わせて、canvasにaddEventListenerして、遊べるようにしています。
かなり無理矢理作っているのでコードは割愛しますが、計算した数字やマトリクスとの高さを合わせるためのオフセットや拡大倍率などでかなり苦労した記憶があります。²

また、パレットの描画には現在選択している色を黄色で囲むようにしています。
これを実現する方法として、すべて選択していない状態のパレットを保存しておき、
それで全体を上書きしたあと選択した色だけ新たに描画し直すという仕組みで、選択していない色を灰色に戻しています。

合わせて、パレットに斜線のマスを1つ作っています。

これは、問題を解く際にここには色が入らないということを示すための斜線マスで、パレット番号は-1としています。
これを使うため、ノノグラムの数値の計算で-1も除外しています。

その他、細かいこと

問題をシェアして解けるようにする

base64エンコードしているものをクエリパラメータとしていれればシェアできるかも、と思い入れてみました。

main(src)

    document.getElementById('share').href = `http://twitter.com/share?url=${window.location.href+"?"+encodeURIComponent(src)}&text=このNonogramが解けるかな？&related=sytkm`;

TwitterはURLは文字数制限の対象には入らないので、上手くいきました。

問題を解くときはファイルアップロードボタンや解答表示ボタンは必要ないので、display:noneしています。

window.onload

    if (window.location.search[0] === '?') {
        document.getElementById("file").style.display = "none";
        document.getElementById("solve").style.display = "none";
        document.getElementById("downl").style.display = "none";
        document.getElementById("share").style.display = "none";
        main(decodeURIComponent(window.location.search.slice(1)));
    }

回答が合っているかのチェック

どうすれば簡単にチェックできるか検討した結果、自分で描いた画像からもう一度計算した数字を生成し、問題になっている数字と比較すれば簡単にチェックできそう、ということでその形で実装しています。

main(src)

    document.getElementById('check').addEventListener("click", function () {
        console.log(numberrow);
        console.log(numbercolumn);
        console.log(g_drawmatrix);
        if (checkNumber(numberrow, g_drawmatrix, tRNSdata) && checkNumber(numbercolumn, transpose(g_drawmatrix), tRNSdata)) {
            alert("correct!");
            document.getElementById("downl").style.display = "inline";
        } else {
            alert("incorrect...");
        }
    });

checkNumber()

function checkNumber(checkarr, targetmatrix, alpha) {
    return String(checkarr) === String(makeNumber(targetmatrix, alpha));
}

問題部分の文字色

白だけ、黒だけなどいろいろ試しても必ず読みにくい色が出てしまっていたのですが、この記事で解決しました。
ありがとうございます。

jsdocについて

GitHubのコードにはjsdocを入れてみていますが、これは今回始めてやってみました。
入れてみたら早速違っていた部分があったのでびっくりしましたね。
入出力を考えるので見通しが明るくなるのと、ミスが起こりにくくなるので今後も使っていればと思っています。

最後に

初めてJavaScriptでバイナリデータを扱ってみたのですが、通常といろいろ勝手が違うので難しいですね。
画像ファイルなのでなんとかなりましたが、これが音声ファイルとかだとしたら目も当てられなそう。
あと、canvas。なんでもできそうに見えて扱いがとても難しい。
素のcanvasではなくライブラリなどを使ったほうが良さそうだと毎回思っていますが、使う頃にはいつも忘れています。
なんとか動くものができてよかった。

元は2年前のコードなのになぜ今更修正&Qiita投稿するようになったかというと、ドット絵のコミュニティに参加したことでドット絵へのやる気が復活してきたからです。
この場を借りてお礼を。
ありがとうございます。
ドット絵に興味ある方はぜひどうぞ。

参考文献

http://www.landofcrispy.com/nonogrammer/nonogram.html?mode=play
https://www.setsuki.com/hsp/ext/png.htm
https://dawn.hateblo.jp/entry/2017/10/22/205417
https://www.shigemk2.com/entry/2014/09/15/%E6%96%87%E5%AD%97%E5%88%97%E3%82%9216%E9%80%B2%E6%95%B0%E3%81%AB%E5%A4%89%E6%8F%9B%E3%81%97%E3%81%A6%E3%81%BF%E3%82%8B
https://tech-blog.s-yoshiki.com/2018/01/10/
https://developer.mozilla.org/ja/docs/Web/Guide/HTML/Canvas_tutorial/Pixel_manipulation_with_canvas
https://hoshi-sano.hatenablog.com/entry/2013/08/18/112550
https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/DataView
https://qiita.com/megadreams14/items/dded3cf770010bb8ff08
https://developer.mozilla.org/ja/docs/Web/API/FileReader/result
http://var.blog.jp/archives/62330155.html
http://imaya.blog.jp/archives/6136997.html
https://stackoverflow.com/questions/4858187/save-restore-background-area-of-html5-canvas
https://qiita.com/nekoneko-wanwan/items/9af7fb34d0fb7f9fc870
https://katashin.info/2018/12/18/247
https://qiita.com/kznr_luk/items/790f1b154d1b6d4de398
https://rmtmhome.com/under-fixmenu-342
http://www.htmq.com/canvas/font.shtml
https://qiita.com/rico/items/0f645e84028d4fe00be6
https://qiita.com/8x9/items/218e24b7e6eea2446beb
https://ics.media/entry/6789/

パレットを利用したノンインターレースのPNG ↩
原型は2年前に作っていましたので、当時の記憶が若干おぼろげです。 ↩