JavaScriptで迷路自動生成プログラム
迷路を自動生成してcanvasに描画するプログラムを作成しました。
See the Pen
Untitled by Imai (@imai1)
on CodePen.
四角マップ状の迷路を生成
迷路の構造
まずは、このプログラムにおける（四角マップ版の）迷路の定義を説明します。
- マス目を碁盤状に並べる。
- 各マスの面が空間を表し、罫線が壁を表す。面の色で空間／壁を表すタイプではない。
- 隣接する二つのマスの共有辺に罫線がなければ、そのマスは繋がっている。
- 全てのマスから別の全てのマスに到達する経路が必ず一つ存在する。
- ゆえに、スタートとゴールはランダムに2点を選べば良い。
上記の３番目の要件が曲者ですが、あとの二つは単純です。よってまず先に、迷路のデータ構造と、それを描画する関数を説明します。
迷路のデータ構造
本プログラムでは、以下のRectangularMapクラスで四角マップ版の迷路のデータ構造を管理します。
class RectangularMap { static UP = 0; static RIGHT = 1; static DOWN = 2; static LEFT = 3; constructor(width, height) { this.width = width; this.height = height; this.initializeConnection(); this.buildConnection(); } initializeConnection() { this.connection = new Array(this.height); for (let y = 0; y < this.height; ++y) { this.connection[y] = new Array(this.width); for (let x = 0; x < this.width; ++x) { this.connection[y][x] = new Array(4).fill(false); } } } buildConnection() { // 「全てのマスから別の全てのマスに到達する経路が必ず一つ存在する。」を満たすように接続を生成する。 } }
connectionプロパティはマス目の二次元配列で、更に各マスは上下左右の四方向に壁があるかどうかを表す固定長配列です。後述の、接続を生成するbuildConnection関数のみやや複雑ですが、それ以外はシンプルではないかと思います。
迷路の描画
canvasへの描画は以下のdrawRectanuglarMapToCanvas関数にRectangularMapのインスタンスを与えます。
function drawRectangularMapToCanvas(canvasId, rectangularMap, cellWidth, cellHeight) { const canvas = document.getElementById(canvasId); const context = canvas.getContext("2d"); context.clearRect(0, 0, canvas.width, canvas.height); context.strokeStyle = "black"; for (let y = 0; y < rectangularMap.height; ++y) { for (let x = 0; x < rectangularMap.width; ++x) { if (!rectangularMap.connection[y][x][RectangularMap.UP]) { context.beginPath(); context.moveTo(cellWidth * x, cellHeight * y); context.lineTo(cellWidth * (x + 1), cellHeight * y); context.stroke(); } /* 右・下・左についても同様 */ } } }
RectangularMapのconnectionプロパティを走査して、壁があれば対応する座標に罫線を引くだけの単純な関数です。迷路の接続生成のアルゴリズムに依存していないため、簡単な処理になっています。少し改変すればcanvas以外の描画方法も簡単に実装できるのではないかと思います。
迷路の接続の自動生成
最後に「全てのマスから別の全てのマスに到達する経路が必ず一つ存在する」ような接続の自動生成を説明します。計算機科学的な概念については本項では細かく説明しませんが、各語に補足のためのリンクを貼り付けました。
生成にはグラフ理論を利用します。
まず、本稿の定義の迷路において、全ての辺に壁が無い迷路は、マス目が頂点、罫線が辺の、格子グラフです。あとは、この格子グラフから全域木という部分グラフを取り出して、全域木の辺に対応する壁にのみ穴を開ければ、それだけで迷路の完成です。
あるグラフの全域木とは、そのグラフの全ての頂点を含む木グラフのことです。木は、木の中に含まれる各二頂点間の経路を必ずただ一つだけ持つようなグラフであるため、それだけで「全てのマスから別の全てのマスに到達する経路が必ず一つ存在する」が満たされます。
迷路生成部分
この処理に対応するRectangularMap.buildConnectionを以下に示します。
buildConnection() { // 格子グラフを構築 const graph = new Array(); // 辺(片方の頂点の座標＋方向, もう片方の頂点の座標＋方向)のリスト。 for (let y = 0; y < this.height; ++y) { for (let x = 0; x < this.width; ++x) { if (x < this.width - 1) { graph.push([x, y, RectangularMap.RIGHT, x + 1, y, RectangularMap.LEFT]); } if (y < this.height - 1) { graph.push([x, y, RectangularMap.DOWN, x, y + 1, RectangularMap.UP]); } } } // 全域木を抽出 const edges = graph.map((v) => [this.indexOf(v[0], v[1]), this.indexOf(v[3], v[4])]); const spanningTree = makeSpanningTree(this.width * this.height, edges); // 全域木の辺に穴を開ける let i = 0; for (let i = 0; i < edges.length; ++i) { const connected = spanningTree[i]; if (connected) { this.connection[graph[i][1]][graph[i][0]][graph[i][2]] = true; this.connection[graph[i][4]][graph[i][3]][graph[i][5]] = true; } } }
ランダムな全域木の生成
全域木の生成には、クラスカル法を改変したアルゴリズムを使いました。
function makeSpanningTree(numVertices, edges) { const disjointSet = new DisjointSet(numVertices); const connection = new Array(edges.length); for (const index of shuffle(makeIndexList(edges.length))) { const [vertex1, vertex2] = edges[index]; const group1 = disjointSet.find(vertex1); const group2 = disjointSet.find(vertex2); if (group1 != group2) { connection[index] = true; disjointSet.union(vertex1, vertex2); } else { connection[index] = false; } } return connection; }
最小全域木を生成するためにコストの小さい順に辺を走査するのではなく、辺集合をランダムにシャッフルして走査します。それ以外はクラスカル法と同様に、着目している辺の両端の頂点が既に繋がっていたらその辺は破棄し、未接続であればその辺を全域木に加える、という処理を繰り返すだけです。この方法で、ランダムな全域木が生成できます。誰かが既に考えている気がしますが名前はないのでしょうか？
素集合データ構造
辺の両端の頂点が過去に調べた辺で接続されているかどうかは、素集合データ構造を利用します。素集合データ構造とは、要素の集合に対して、以下の二つの操作を行うデータ構造です。
- 二つの要素が同じ集合に属しているか調べる
- 二つの部分集合を合体させて大きな部分集合を作る
迷路の生成においては、要素＝グラフの頂点＝マス目の面、です。makeSpanningTreeの各イテレーションにおいて、それまでに採用した辺によって互いに行き来できるマス目の集合を一つの部分集合として管理します。
このデータ構造の実現のために本プログラムではUnion-Findアルゴリズムを実装しました。実用的には素集合データ構造とUnion-Findアルゴリズムはほぼ等価なものとして扱われている気がします。
class DisjointSet { constructor(num) { this.num = num; this.parentOf = new Array(num); this.rankOf = new Array(num); for (let i = 0; i < this.num; ++i) { this.parentOf[i] = i; this.rankOf[i] = 0; } } find(index) { const parent = this.parentOf[index]; if (parent == index) { return index; } else { const root = this.find(parent); this.parentOf[index] = root; return root; } } union(index1, index2) { const root1 = this.find(index1); const root2 = this.find(index2); const rank1 = this.rankOf[root1]; const rank2 = this.rankOf[root2]; if (rank1 > rank2) { this.parentOf[root2] = root1; } else if (rank1 < rank2) { this.parentOf[root1] = root2; } else if (root1 != root2) { this.parentOf[root2] = root1; this.rankOf[root1] += 1; } } }
細かい関数の説明は省略しましたが、以上で四角マップの迷路を生成するプログラムの完成です。
六角マップ状の迷路を生成
四角形のマス目を碁盤状に並べるという制約を取り去っても、同じ方法で様々な構造の迷路を生成できます。
- 各タイルの面が空間を表し、罫線が壁を表す。
- 隣接する二つのタイルの共有辺に罫線がなければ、そのタイルは繋がっている。
- 全てのタイルから別の全てのタイルに到達する経路が必ず一つ存在する。
- ゆえに、スタートとゴールはランダムに2点を選べば良い。
例として本稿では、冒頭のCodePenの通り、六角マップ状の迷路も実装してみました。
class HexagonalMap { static UPPER_RIGHT = 0; static RIGHT = 1; static LOWER_RIGHT = 2; static LOWER_LEFT = 3; static LEFT = 4; static UPPER_LEFT = 5; constructor(width, height) { this.width = width; this.height = height; this.initializeConnection(); this.buildConnection(); } initializeConnection() { this.connection = new Array(this.height); for (let y = 0; y < this.height; ++y) { this.connection[y] = new Array(this.width); for (let x = 0; x < this.width; ++x) { this.connection[y][x] = new Array(6).fill(false); } } } buildConnection() { // 元になるグラフを構築 const graph = new Array(); for (let y = 0; y < this.height; ++y) { for (let x = 0; x < this.width; ++x) { if (x < this.width - 1) { graph.push([x, y, HexagonalMap.RIGHT, x + 1, y, HexagonalMap.LEFT]); } if (y < this.height - 1) { if (y % 2 == 0) { graph.push([x, y, HexagonalMap.LOWER_RIGHT, x, y + 1, HexagonalMap.UPPER_LEFT]); if (x > 0) { graph.push([x, y, HexagonalMap.LOWER_LEFT, x - 1, y + 1, HexagonalMap.UPPER_RIGHT]); } } else { graph.push([x, y, HexagonalMap.LOWER_LEFT, x, y + 1, HexagonalMap.UPPER_RIGHT]); if (x < this.width - 1) { graph.push([x, y, HexagonalMap.LOWER_RIGHT, x + 1, y + 1, HexagonalMap.UPPER_LEFT]); } } } } } // あとの処理はRectangularMapと全く同じ // 全域木を抽出 // 全域木の辺に穴を開ける } }
タイルの形は六角形ですが、タイルの配列は行列状に並べることにしました。シミュレーションゲームなどでもそのような配置です。そのため、coordinateは長さ6の配列の二次元配列になります。buildConnectionでmakeSpanningTreeに与えるグラフを生成する処理以外は、RectangularMapと同じコードです。
drawHexagonalMapToCanvasも、HexagonalMapの各タイルの各辺を調べて、壁があったら対応する座標に線を引くだけです。内容をご覧になりたい場合はCodePenのコードを参照ください。
三角タイリングでも、ボロノイ図でも、makeSpanningTreeに与えるグラフをコーディングできれば、元になるグラフとして任意の平面グラフを使用可能です。
身近な不思議の科学に関するリンク集 主に人体と栄養編
身近なのによく考えたら不思議だな・面白いなと筆者が思った物事について、紹介・説明しているWebページのリンク集をまとめました。
注：リンク先のページのテキストや画像の権利はそのページの作成者（場合によってはその更に引用元）に帰属します。リンク先の情報を利用・引用する際にはご留意ください。また、実験を行う場合には安全性に十分に配慮してください。
消化の働き
食べ物を口に入れてから吸収されたり外に出たりするまでに、体の中では何が起こっているのでしょうか。テレビ番組などで断片的には散々聞いた気もしますが、いまいちちゃんと理解できていなかったので、俯瞰できる資料を集めてみました。
タンパク質って何？
タンパク質とは、20種類のアミノ酸がたくさん繋がった高分子化合物とのことです。比較的少ない個数のアミノ酸の分子はペプチドというらしいです。
タンパク質が様々な化合物の総称なら、食品によって摂れる分子が異なるのでは？と思いますが、ペプチドやアミノ酸に分解されてから吸収されるようです。また、体の中で合成できない9種類の必須アミノ酸がどれくらい含まれているかというアミノ酸スコアというものも考えられているそうです。
コラーゲンもタンパク質の一種で、大きな分子なので、経口摂取してもそのまま吸収されるわけではないらしいです。
吸収の仕組み
栄養素を吸収するとは、具体的にはどういうことなのかも調べました。
また、飲み薬もまずは小腸で吸収されるみたいです。
身近な不思議の科学に関するリンク集 主に機械・工場・計測編
身近なのによく考えたら不思議だな・面白いなと筆者が思った物事について、紹介・説明しているWebページのリンク集をまとめました。
- 大量のご飯はどうやって炊いている？
- マヨネーズやケーキに使う卵の殻ってどうしてるの？
- 雨の量ってどうやって測るの？
- 非接触の温度計の仕組みは？
- 糸や布ってどうやって作ってるの？
- 自動ドアやゲートの仕組み
- ピッチャーの球速はどうやって計っている？
- 高い建物に水を届ける仕組み
注：リンク先のページのテキストや画像の権利はそのページの作成者（場合によってはその更に引用元）に帰属します。リンク先の情報を利用・引用する際にはご留意ください。また、実験を行う場合には安全性に十分に配慮してください。
大量のご飯はどうやって炊いている？
工場で調理された弁当などのご飯はどうやって大量に炊いているんだろうと気になりました。
家庭用の炊飯器よりは圧倒的に大きいものの、複数並列に稼働させているみたいです。
雨の量ってどうやって測るの？
原理的には降ってきた雨を集めて重さを測るだけですが、効率よく計測したり排水したりする仕組みが工夫されているようです。
糸や布ってどうやって作ってるの？
非常に様々な工程や仕組みが連携するシステムが構築されているようです。ITでもどこの世界でもシステム開発ってやっぱり凄いなと思いました。
ピッチャーの球速はどうやって計っている？
canvasのサイズとBootstrap
この記事では、HTMLのcanvasタグのサイズ設定と、それを更にBootstrapと組み合わせてレスポンシブデザインにする方法を説明します。
See the Pen
Untitled by Imai (@imai1)
on CodePen.
発端：JavaScriptでちょっとローグライクゲームでも作ってみようかなと思ったのですが、マップのアスペクト比を維持しつつ様々なスクリーンサイズに対応したり、メッセージウィンドウをレスポンシブに改行したりするにはどうしたら良いのかと考えたことがきっかけです。
canvasのサイズとスタイルのサイズ
canvasタグには二種類のサイズ設定があります。canvasタグの属性width heightと、タグのstyle属性のwidth heightです。
<canvas width="300px" height="150px" style="width: 500px; height: 250px;">
- タグの
widthおよびheight属性は、描画領域の座標空間のサイズを設定するためのものです。 - 一方、
style属性のwidthおよびheightは、canvasタグがブラウザ上で描画される際のサイズを指定するためのものです。 - ただし、
style属性の設定がない場合は、タグのwidthおよびheight属性が後者にも適用されます。
具体的な例で見てみましょう。
まず、canvas内に、固定の大きさの矩形と、canvasのサイズを描画する次の関数を用意しました。
function drawSample(canvas) { const context = canvas.getContext("2d"); context.fillStyle = "white"; context.fillText(`canvas.width=${canvas.width}, canvas.height=${canvas.height}`, 20, 20); context.fillRect(20, 30, 100, 100); }
それを次のタグに適用します。
<canvas id="canvas1" class="bg-dark" width="300px" height="150px" style="width: 500px; height: 250px;"></canvas> <canvas id="canvas2" class="bg-dark" width="300px" height="150px"></canvas> <canvas id="canvas3" class="bg-dark" width="500px" height="250px"></canvas>
drawSample(document.getElementById("canvas1")); drawSample(document.getElementById("canvas2")); drawSample(document.getElementById("canvas3"));
すると、レンダリング結果は次のようになります。
| ID | 描画領域の論理サイズ | ブラウザ上の表示サイズ |
canvas1 |
300 x 150 | 500 x 250 |
canvas2 |
300 x 150 | 300 x 150 |
canvas3 |
500 x 250 | 500 x 250 |
Bootstrapにcanvasを設置
ここまでの説明を踏まえて、Bootstrapにおいて、固定のアスペクト比のcanvasをグリッド内に配置する例は以下のようになります。
<div class="row"> <div class="col-sm-8 border"> <canvas id="canvas4" class="bg-dark ratio ratio-1x1" width="600px" height="600px"></canvas> </div> <div class="col-sm-4 border"> <p>Message Window</p> </div> </div>
rowcolでグリッドを作成します。これによってcanvasの横幅は（別のスタイルで上書きしなければ）自動的に定まります。ratio ratio-1x1を設定することで、アスペクト比を設定します。比率はこの他にratio-4x3ratio-16x9ratio-21x9が用意されています。canvasタグのwidthheightで描画領域の論理サイズを設定します。
レンダリング結果は次のようになります。
ブラウザの横幅を変えたり、CodePenの縮尺を変更したりしても、canvasのアスペクト比と論理サイズは変わらないまま、ブラウザ上の表示サイズのみが変わることを確認してみてください。Message Window（ローグライクゲームを想定）は、ブラウザの幅を狭めると縦置きになります。
なお、表示サイズに対してcanvasタグのwidth heightが小さすぎると、画像の拡大処理が適用されてぼやけた表示になります。
グリッドに関する説明は本記事では省略しますが、詳しく知りたい方は以下もご覧いただけたら嬉しいです。
身近な不思議の科学に関するリンク集 主に火や熱編
身近なのによく考えたら不思議だな・面白いなと筆者が思った物事について、紹介・説明しているWebページのリンク集をまとめました。
- ものが燃える仕組み
- 電子レンジ・オーブン・トースターの仕組みや違いなど
- 冷やす家電
- ガスで温める仕組み
- 陶磁器を焼く理由
- たまごの仕組み
- 加熱と料理
- 風邪と発熱
- 温暖化に関するあれこれ
- 砂漠の気温変化
注：リンク先のページのテキストや画像の権利はそのページの作成者（場合によってはその更に引用元）に帰属します。リンク先の情報を利用・引用する際にはご留意ください。また、実験を行う場合には安全性に十分に配慮してください。
ものが燃える仕組み
そもそも火とは何なのか、よくわからなかったので調べてみました。
電子レンジ・オーブン・トースターの仕組みや違いなど
現代人にとっては火よりも身近な気がします。マイクロ波や赤外線がどうこうという話は聞きますが、それがどういう理屈で作用するかがわかってませんでした。
冷やす家電
氷のようなすでに冷えているものに熱を移す以外に、機械と電気でどうやってものを冷やすのかも不思議です。
たまごの仕組み
たまごも熱を加えると固まるものの一つです。どういう仕組みで固まるのか不思議に思いました。
風邪と発熱
風邪をひくと発熱することは当然知っていますが、それにどんな効果があるのかは何となくしか理解していませんでした。熱で病原体を殺しているだけでなく、熱が上がると免疫機能が活性化されるそうです。
温暖化に関するあれこれ
どうしてこんなに暑くなるのか、毎年夏になると不思議に思っていました。
