作品 ID: 1025
迷路いろいろ

公開
迷路を自動生成してみたり解いてみたりします。クラスタリング法とゆうのを試しました。棒倒し法と穴掘り法はだいたい501、502のクジラ飛行机氏のサンプルどうりですが、島や小部屋が出来ないようにちょこっと修正しています。／アドベントカレンダー用に壁伸ばし法の追加。
ソース
プログラム

＃自動生成
＃＃クラスタリング法
●(サイズの)クラスタリング法迷路作成
    変数 [道,壁]＝[0,1]。
    変数 [迷路幅,迷路高]＝サイズ。
    変数 迷路＝空配列。
    変数 壁データ＝空配列。
    変数 部屋番号＝空配列。
    # 最初に全てを壁にする。
    行を0から(迷路高-1)まで繰り返す。:
        迷路[行]＝空配列
        列を0から(迷路幅-1)まで繰り返す。:
            迷路[行][列]＝壁。

    変数 部屋数x＝迷路幅/2を整数変換。
    変数 部屋数y＝迷路高/2を整数変換。
    行を0から(部屋数y-1)まで繰り返す。:
        列を0から(部屋数x-1)まで繰り返す。:
            # 部屋を作る
            迷路[行*2+1][列*2+1]＝道。
            # 壊す壁のデータを作る
            もし、行＝部屋数y-1でなければ、:
                壁データに[行,列,行+1,列]を配列追加。# 部屋行,列とその下隣との間の壁。
            もし、列＝部屋数x-1でなければ、:
                壁データに[行,列,行,列+1]を配列追加。# 部屋行,列とその右隣との間の壁。
    # 部屋に通し番号を付ける
    部屋番号＝0から(部屋数x*部屋数y)までの配列連番作成。

    # ランダムに壁を壊していく
    壁データを配列シャッフル。
    壁データを反復。:
        変数 [Y1,X1,Y2,X2]＝対象。
        変数 部屋番1＝部屋番号[Y1＋X1*部屋数y]。
        変数 部屋番2＝部屋番号[Y2＋X2*部屋数y]。
        もし、部屋番1＝部屋番2ならば、続ける。# 部屋番号が同じなら壊さない。
        もし、X1＝X2ならば、:
            迷路[Y1*2+2][X1*2+1]＝道。# 同じ列なら下の壁を壊す。
        違えば、:
            迷路[Y1*2+1][X1*2+2]＝道。# 同じ行なら右の壁を壊す。

        # 部屋繋げる(クラスタリング)
        変数 [統合先,統合元]＝[部屋番1,部屋番2]。
        もし、部屋番1＞部屋番2ならば、:
            統合先＝部屋番2。統合元＝部屋番1。
        # 部屋番号が大きい方(統合元)を小さい方(統合先)の番号に全て変更する。
        部屋番号の要素数回:
            もし、部屋番号[回数-1]＝統合元ならば、部屋番号[回数-1]＝統合先。
    迷路で戻る。
ここまで。

＃＃棒倒し法
●(サイズの)棒倒し法迷路作成とは:
    変数 [道,壁]＝[0,1]。
    変数 [迷路幅,迷路高]＝サイズ。
    変数 迷路＝空配列。
    # 外周を壁、それ以外を道とする。
    行を0から(迷路高-1)まで繰り返す。:
        迷路[行]＝空配列。
        列を0から(迷路幅-1)まで繰り返す。:
            # 最初に全部を道にする。
            迷路[行][列]＝道。
            # それから外周を壁にする。
            もし、(列＝0)または(行＝0)または(列＝迷路幅-1)または(行＝迷路高-1)ならば、:
                迷路[行][列]＝壁。
    # 行も列も偶数なら柱を立てる（壁にする）
    行を2から(迷路高-3)まで繰り返す。:
        列を2から(迷路幅-3)まで繰り返す。:
            もし(列%2=1)または(行%2=1)ならば続ける。
            # まず柱を立てる。
            迷路[行][列]＝壁。
            # 上下左右のいずれかに向かって棒を倒す（壁にする）。
            上下左右＝[[0,-1],[0,1],[-1,0],[1,0]]。
            # ただし2段目以降は上には倒さない。
            もし、行>2ならば、上下左右の０を配列削除。
            方向＝上下左右を配列シャッフル。
            方向の要素数回:
                ｘ,ｙ＝方向[回数-1]。
                # 既に壁がある方向へは倒さない
                もし、迷路[行+ｙ][列+ｘ]＝壁でなければ、:
                    迷路[行+ｙ][列+ｘ]＝壁。
                    抜ける。
    迷路で戻る。

＃＃穴掘り法
●(サイズの)穴掘り法迷路作成とは:
    変数 [道,壁]＝[0,1]。
    変数 [迷路幅,迷路高]＝サイズ。
    変数 迷路＝空配列。
    # 最初に全部を壁にする。
    行を0から(迷路高-1)まで繰り返す。:
        迷路[行]＝空配列。
        列を0から(迷路幅-1)まで繰り返す。:
            迷路[行][列]＝壁。
    # 左上を起点として穴掘りをはじめる
    迷路[1][1]＝道。# 起点をまず掘る。
    [1,1]から迷路の迷路掘削処理。

●(起点から迷路の)迷路掘削処理とは:
    変数 [道,壁]＝[0,1]。
    変数 [列,行]＝起点。# 起点は[x,y]の配列。
    変数 [迷路幅,迷路高さ]＝[迷路[0]の要素数,迷路の要素数]。
    変数 上下左右＝[[0,-1],[0,1],[-1,0],[1,0]]
    変数 方向＝上下左右の配列シャッフル。
    方向を反復:
        RX,RY＝対象。
        X1＝RX+列。Y1＝RY+行。
        X2＝RX*2＋列。Y2＝RY*2+行。
        # 2マス先を調べて壁でなければ中止
        もし、(X2≦0)または(X2≧迷路幅-1)ならば続ける。# 迷路の外
        もし、(Y2≦0)または(Y2≧迷路高-1)ならば続ける。
        もし、迷路[Y2][X2]=道ならば続ける。
        # 穴を掘る
        迷路[Y1][X1]＝道。
        迷路[Y2][X2]＝道。
        # 再帰的に掘削する
        [X2,Y2]から迷路の迷路掘削処理。
    迷路で戻る。

＃＃壁伸ばし法
●(サイズの)壁伸ばし法迷路作成とは:
    変数 [道,壁]＝[0,1]。
    変数 [迷路幅,迷路高]＝サイズ。
    変数 迷路＝空配列。
    変数 壁建設開始候補地＝空配列。
    # 外周を壁、それ以外を道とする。
    行を0から(迷路高-1)まで繰り返す。:
        迷路[行]＝空配列。
        列を0から(迷路幅-1)まで繰り返す。:
            # 外周を壁にする。
            もし、(列＝0)または(行＝0)または(列＝迷路幅-1)または(行＝迷路高-1)ならば、:
                迷路[行][列]＝壁。
            # 残りを全部を道にする。
            違えば、:
                迷路[行][列]＝道。
                # 行も列もともに偶数なら壁建設開始候補地として記録する
                もし(列%2=0)かつ(行%2=0)ならば、壁建設開始候補地に[列,行]を配列追加。

    ((壁建設開始候補地の要素数)＞０)の間:
        壁建設開始候補地を配列シャッフル。
        変数 [列,行]＝壁建設開始候補地[0]。
        壁建設開始候補地から０を配列削除。
        もし、迷路[行][列]＝道ならば、[列,行]から迷路に壁建設処理。
    迷路で戻る。

●(起点から迷路に)壁建設処理とは:
    変数 [道,壁,建設中]＝[0,1,9]。
    変数 [列,行]＝起点。# 起点は[x,y]の配列。
    変数 [迷路幅,迷路高さ]＝[迷路[0]の要素数,迷路の要素数]。
    変数 上下左右＝[[0,-1],[0,1],[-1,0],[1,0]]
    変数 方向＝上下左右の配列シャッフル。
    方向を反復:
        もし、迷路[行][列]＝道でなければ、戻る。
        変数 [RX,RY]＝対象。
        変数 [X1,Y1]＝[RX+列,RY+行]。
        変数 [X2,Y2]＝[RX*2＋列,RY*2+行]。
        迷路[Y2][X2]で条件分岐:
            建設中ならば、:
                続ける。
            道ならば、:
                迷路[行][列]＝建設中。
                迷路[Y1][X1]＝建設中。
                # 再帰的に建設する
                [X2,Y2]から迷路に壁建設処理。
            壁ならば、:
                迷路[行][列]＝建設中。
                迷路[Y1][X1]＝建設中。
                行を0から(迷路高-1)まで繰り返す。:
                    列を0から(迷路幅-1)まで繰り返す。:
                        もし、迷路[行][列]＝建設中ならば、迷路[行][列]＝壁。

    行を0から(迷路高-1)まで繰り返す。:
        列を0から(迷路幅-1)まで繰り返す。:
            もし、迷路[行][列]＝建設中ならば、迷路[行][列]＝道。

＃探索
変数 調査済み迷路＝空配列。
●(現地点から出口まで迷路の)迷路深さ優先探索とは:
    調査済み迷路＝迷路を配列複製。
    変数 [今ｘ,今ｙ]＝現地点。
    変数 [終ｘ,終ｙ]＝出口。
    変数 仮迷路＝迷路を配列複製。
    変数 [道,壁,調査済み]＝[0,1,9]。# 地形の定義。
    変数 上下左右＝[[0,-1],[0,1],[-1,0],[1,0]]。
    上下左右を反復:
        ｘ,ｙ＝対象。
        次ｘ,次ｙ＝[今ｘ＋ｘ,今ｙ＋ｙ]。
        もし、(次ｘ＝終ｘ)かつ(次ｙ＝終ｙ)ならば、:
            仮迷路[今ｙ][今ｘ]＝調査済。
            仮迷路[次ｙ][次ｘ]＝調査済。
            調査済み迷路＝仮迷路を配列複製。
            抜ける。
        もし、調査済み迷路[終ｙ][終ｘ]＝調査済みならば、抜ける。
        もし、仮迷路[次ｙ][次ｘ]＝壁ならば、続ける。
        もし、仮迷路[次ｙ][次ｘ]＞0ならば、続ける。
        仮迷路[今ｙ][今ｘ]＝調査済。
        [次ｘ,次ｙ]から出口まで仮迷路の迷路深さ優先探索。
    調査済み迷路で戻る。

●(入口から出口まで迷路の)迷路幅優先探索とは:
    調査済み迷路＝迷路を配列複製。
    変数 [終ｘ,終ｙ]＝出口。
    変数 [道,壁,調査中]＝[0,1,8]。# 地形の定義。
    変数 上下左右＝[[0,-1],[0,1],[-1,0],[1,0]]。
    変数 仮迷路＝迷路を配列複製。
    変数 調査中迷路＝迷路を配列複製。
    変数 迷路調査リスト＝空配列。
    迷路調査リストに入口を配列追加。
    ((迷路調査リストの配列要素数)＞０)の間:
        今ｘ,今ｙ＝迷路調査リスト[0]。
        仮迷路[今ｙ][今ｘ]＝調査中。
        迷路調査リストの0を配列削除。
        上下左右を反復:
            ｘ,ｙ＝対象。
            次ｘ,次ｙ＝[今ｘ＋ｘ,今ｙ＋ｙ]。
            もし、(次ｘ＝終ｘ)かつ(次ｙ＝終ｙ)ならば、:
                調査中迷路[次ｙ][次ｘ]＝[今ｘ,今ｙ]。
                調査中迷路の入口から出口まで最短ルート反映。
                それで戻る。
            もし、仮迷路[次ｙ][次ｘ]＝道でなければ、続ける。
            迷路調査リストに[次ｘ,次ｙ]を配列追加。
            調査中迷路[次ｙ][次ｘ]＝[今ｘ,今ｙ]

●(調査中迷路の入口から出口まで)最短ルート反映:
    始ｘ,始ｙ＝入口。
    今ｘ,今ｙ＝出口。
    永遠の間:
        前ｘ,前ｙ＝調査中迷路[今ｙ,今ｘ]。
        調査済み迷路[今ｙ,今ｘ]＝9。
        もし、(今ｘ＝始ｘ)かつ(今ｙ＝始ｙ)ならば、抜ける。
        今ｘ,今ｙ＝[前ｘ,前ｙ]。
    調査済み迷路で戻る。

＃表示
変数 迷路表示色定義＝[白色,茶色,青色,紫色,緑色,灰色,オリーブ色,水色,黄色,赤色]。
変数 迷路表示文字定義＝[空,空,"Ｓ","Ｇ",空,空,空,空,空,空]。
●(迷路を道幅で|道幅の)迷路表示とは:
    変数 [迷路幅,迷路高さ]＝[迷路[0]の要素数,迷路の要素数]。
    もし、道幅＝空ならば、道幅＝8。
    描画中キャンバスの「width」に迷路幅*道幅をDOM属性設定。
    描画中キャンバスの「height」に迷路高さ*道幅をDOM属性設定。
    行を0から(迷路高-1)まで繰り返す:
        列を0から(迷路幅-1)まで繰り返す:
            地形＝迷路[行][列]。
            空に線色設定。
            ベージュ色に塗り色設定
            数を0から9まで繰り返す:
              もし、地形＝数ならば、迷路表示色定義[数]に塗り色設定。
            ｘ＝列*道幅。ｙ＝行*道幅。
            [ｘ,ｙ,道幅,道幅]に四角描画。
            黒色に塗り色設定。道幅に描画フォント設定。
            [ｘ,ｙ+道幅-2]に迷路表示文字定義[地形]を文字描画。

＃以下はテスト
もし、プラグイン名が「メイン」ならば、
  変数 初期x＝43。
  変数 初期y＝33。
  変数 マス幅＝8。
  迷路＝[初期x,初期y]のクラスタリング法迷路作成。
  迷路をマス幅で迷路表示。

  迷路種別ラベル＝「クラスタリング法」のラベル作成。
  改行作成。改行作成。
  「迷路サイズ：」のラベル作成。
  ｘエディタ＝初期xのエディタ作成。
  ｘエディタの「幅」に「32px」をDOMスタイル設定。
  ｘエディタの「行揃え」に「右」をDOMスタイル設定。
  「×」のラベル作成。
  ｙエディタ＝初期yのエディタ作成。
  ｙエディタの「幅」に「32px」をDOMスタイル設定。
  ｙエディタの「行揃え」に「右」をDOMスタイル設定。
  「(5以上の奇数)」のラベル作成。
  改行作成。
  「迷路の生成：」のラベル作成。
  棒倒しボタン＝「棒倒し法」のボタン作成。
  穴掘りボタン＝「穴掘り法」のボタン作成。
  壁伸ばしボタン＝「壁伸ばし法」のボタン作成。
  クラスタリングボタン＝「クラスタリング法」のボタン作成。
  改行作成。
  「ルート探索：」のラベル作成。
  深さ優先探索ボタン＝「深さ優先探索」のボタン作成。
  幅優先探索ボタン＝「幅優先探索」のボタン作成。
  「｜」のラベル作成。
  戻すボタン＝「ルート消去」のボタン作成。
  改行作成。
  「迷路を保存：」のラベル作成。
  コピーボタン＝「テキストコピー」のボタン作成。
  保存ボタン＝「画像保存」のボタン作成。

  棒倒しボタンをクリックした時には、:
      迷路種別ラベルに「棒倒し法」をテキスト設定。
      ｘ＝ｘエディタのテキスト取得。
      ｙ＝ｙエディタのテキスト取得。
      迷路＝[ｘ,ｙ]の棒倒し法迷路作成。
      迷路をマス幅で迷路表示。

  穴掘りボタンをクリックした時には、:
      迷路種別ラベルに「穴掘り法」をテキスト設定。
      ｘ＝ｘエディタのテキスト取得。
      ｙ＝ｙエディタのテキスト取得。
      迷路＝[ｘ,ｙ]の穴掘り法迷路作成。
      迷路をマス幅で迷路表示。

  壁伸ばしボタンをクリックした時には、:
      迷路種別ラベルに「壁伸ばし法」をテキスト設定。
      ｘ＝ｘエディタのテキスト取得。
      ｙ＝ｙエディタのテキスト取得。
      迷路＝[ｘ,ｙ]の壁伸ばし法迷路作成。
      迷路をマス幅で迷路表示。

  クラスタリングボタンをクリックした時には、:
      迷路種別ラベルに「クラスタリング法」をテキスト設定。
      ｘ＝ｘエディタのテキスト取得。
      ｙ＝ｙエディタのテキスト取得。
      迷路＝[ｘ,ｙ]のクラスタリング法迷路作成。
      迷路をマス幅で迷路表示。

  深さ優先探索ボタンをクリックした時には、:
      変数 [迷路幅,迷路高さ]＝[迷路[0]の要素数,迷路の要素数]。
      変数 [入口,出口]＝[[1,1],[迷路幅-2,迷路高-2]]。
      入口から出口まで迷路の迷路深さ優先探索。
      それをマス幅で迷路表示。

  幅優先探索ボタンをクリックした時には、:
      変数 [迷路幅,迷路高さ]＝[迷路[0]の要素数,迷路の要素数]。
      変数 [入口,出口]＝[[1,1],[迷路幅-2,迷路高-2]]。
      入口から出口まで迷路の迷路幅優先探索。
      それをマス幅で迷路表示。

  戻すボタンをクリックした時には、:
      迷路をマス幅で迷路表示。

  コピーボタンをクリックした時には、:
      CSV＝迷路を配列複製。
      CSVを表CSV変換して、クリップボード設定。
      「クリップボードにコピーしました」を言う。

  保存ボタンをクリックした時には、:
      描画ダウンロード。

スタイル＝「style」のDOM部品作成。
CSS=「.nako3_div {波カッコ}
    font-size:1em;
    line-height:1.1em;
{波カッコ閉じ}
.nako3_div > button {波カッコ}
    font-size:0.9em;
    margin:4px;
    padding:4px;
{波カッコ閉じ}」
スタイルにCSSをHTML設定。
ここまで。
作品について
作品情報

作品を編集
雪乃☆雫作
ライセンス: CC0（著作権破棄）
形式: wnako
タグ: アドベントカレンダー2022, 迷路
利用バージョン: 3.4.1
アクセス数(累計): 147
アクセス数(今月): 90
更新日時: 2022/04/17 18:54 編集: 2022/12/16 23:58
⭐⭐
作品公開情報
交流
コメントを取得中...