10
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

Day 24

Elixir Advent Calendar 2025

@dezamisystem(東亜 プリン)

Elixir言語で迷路生成・解決編

Posted at

はじめに

（正常な迷路アルゴリズムは）初投稿です。

古来より伝わる「迷路生成アルゴリズム」をElixir言語で実装しようチャレンジの続きです。

ちゃんと動く版が完成したので公開します。

迷路の定義

以下の条件を厳守するものとします。

  • 外の通路につながらない領域(閉じた領域)が無い
  • ループになる通路が無い

開発環境

  • MacStudio2023(M2 Max)
  • macOS Tahoe(26.1)
  • Erlang/OTP 27
  • Elixir 1.19.3

迷路表示までの手順

流れは以下です。

  1. 迷路のルート決定
  2. ルートから壁の決定
  3. 壁と柱の表示

迷路情報格納変数の型

Map型として、以下キーと値の型を持ちます。

キー 値の型 役割
connects Map{key:{x,y}, value:MapSet{x,y}} 床の進行可能座標を保持
visited MapSet{x,y} 訪問済み座標を保持

ルート生成アルゴリズム

穴掘り法（Recursive Backtracker）をベースに以下の手順にしています。

  • 迷路の通路に当たる部分を床、その外周を壁とする
  • 迷路の横軸をx, 縦軸をyとし、穴掘りの開始位置を開始位置を左上(x, y)とする
  • 以下を再帰呼び出しで実行
    • 縦か横で隣接する床の任意方向に以下の条件を満たしていれば、その床に進行する
      • 壁に阻まれていない
      • まだ訪問していない
    • どの方向にも進行不可能ならば、再帰を抜ける
  • すべての再帰を抜ければ、迷路は完成している

通路確認アルゴリズム

確認方向を、上から時計回り順に配列として初期化します。

              [0]{x, y-1}
                  ↑
[3]={x-1, y} ← floor={x, y} → [1]={x+1, y}
                  ↓
              [2]={x, y+1}

関数表現は以下になります。

  # 進行可能なフロアを取得
  @spec get_enabled_floors({integer, integer}, integer, integer) :: list
  defp get_enabled_floors({x, y}, w, h) do
    [{x, y - 1}, {x + 1, y}, {x, y + 1}, {x - 1, y}]
    |> Enum.filter(fn {nx, ny} ->
      # 外周は候補から外す
      nx >= 0 and nx < w and ny >= 0 and ny < h
    end)
  end

床の隣接を繋ぐアルゴリズム

接続の情報は送り側と受け側の両方に対応する必要があります。

  # フロア同士の接続を更新する
  @spec connect_route(map, {integer, integer}, {integer, integer}) :: map
  defp connect_route(route, from_pos, to_pos) do
    new_connects =
      route.connects
      # 床の接続情報を追加する
      |> Map.update(from_pos, MapSet.new([to_pos]), fn set ->
        MapSet.put(set, to_pos)
      end)
      # 反対側の床にも情報追加
      |> Map.update(to_pos, MapSet.new([from_pos]), fn set ->
        MapSet.put(set, from_pos)
      end)
    # ルートマップ更新
    %{route | connects: new_connects}
  end

左上座標{0, 0}から始めて再帰呼び出しでルートを繋げていきます。

  @doc """
  ルート更新
  """
  @spec update_route(map, {integer, integer}, {integer, integer}, integer) :: map
  def update_route(route, {w, h}, pos, seed \\ 1) do
    # 現在地を訪問済みにする
    route = %{route | visited: MapSet.put(route.visited, pos)}
    # 進行可能なフロアを取得
    get_enabled_floors(pos, w, h)
    # 進行方向リストをシャッフル
    |> shuffle(seed)
    # 進行可能なルートの検索
    |> Enum.reduce(route, fn next_pos, acc_route ->
      if MapSet.member?(acc_route.visited, next_pos) do
        # すでに訪問済みなら何もしない
        acc_route
      else
        # 現在地と次のフロアの関係を更新する
        acc_route = connect_route(acc_route, pos, next_pos)
        # 再帰呼び出しでさらに進む
        update_route(acc_route, {w, h}, next_pos, seed + 1)
      end
    end)
  end

ルート変数の初期化

    route =
      update_route(
        %{connects: Map.new(), visited: MapSet.new()},
        {w, h},
        {0, 0},
        seed
      )

表示用文字列を取得して出力

出力時の偶数行を「横壁」、奇数行を「縦壁」が表示されるよう文字列を取得します。

# 最初の行は迷路の横幅だけ柱と壁を敷き詰める
■--■--■--■--■--■--■--■--■--■--■--■--■--■--■--■--■--■--■
# floor{x, 0}のルートから左右の隣接情報の無い方向に壁を追加
|  |        |                 |  |           |        |
# floor{x, 0}のルートから上下の隣接情報の無い方向に壁を追加、柱はすべての床の隣接に追加
■  ■--■  ■  ■  ■--■  ■--■--■  ■  ■  ■--■  ■  ■--■--■  ■
# 以下迷路の縦幅まで繰り返し

コードで表現すると以下です。

  # ルートがつながっているか？
  @spec connected?(map, {integer, integer}, {integer, integer}) :: boolean
  defp connected?(route, first, second) do
    case Map.get(route.connects, first) do
      nil -> false
      connections -> MapSet.member?(connections, second)
    end
  end

  # 迷路として表示
  defp display(route, {w, h}) do
    # 最初の固定壁
    IO.puts(String.duplicate("■--", w) <> "■")

    Enum.each(0..(h - 1), fn y ->
      # 縦壁
      row_top =
        Enum.map(0..(w - 1), fn x ->
          right_connected = connected?(route, {x, y}, {x + 1, y})
          wall = if right_connected, do: " ", else: "|"
          "  #{wall}"
        end)
        |> Enum.join()

      # 横壁
      row_bottom =
        Enum.map(0..(w - 1), fn x ->
          bottom_connected = connected?(route, {x, y}, {x, y + 1})
          wall = if bottom_connected, do: "  ", else: "--"
          "#{wall}■"
        end)
        |> Enum.join()

      IO.puts("|" <> row_top)
      IO.puts("■" <> row_bottom)
    end)
  end

SEED値指定によるパターン化

Elixirで標準の乱数生成パターンを固定化する方法を知りました。

    # 現在のプロセスの乱数生成器にシードを設定する
    # :exsss はErlang/Elixirの標準的な乱数アルゴリズム
    # シードは {integer, integer, integer} の3つ組が必要なため、同じ値をセットする
    _old_state = :rand.seed(:exsss, {seed, seed, seed})

これは乱数を用いる各標準関数にも影響するので、それを利用してシード値に対応した迷路パターンを生成することが出来ました。

  @doc """
  リストとシード値(整数)を受け取り、再現性のあるシャッフルを行う
  """
  @spec shuffle(list, integer) :: list
  def shuffle(list, seed) when is_integer(seed) do
    _old_state = :rand.seed(:exsss, {seed, seed, seed})
    # 直前にシードを固定したため、結果はシードに依存して決定する
    Enum.shuffle(list)
  end

前述のルート更新関数の内部で呼び出しています。

  @doc """
  ルート更新
  """
  @spec update_route(map, {integer, integer}, {integer, integer}, integer) :: map
  def update_route(route, {w, h}, pos, seed \\ 1) do
    （中略）
    # 進行可能なフロアを取得
    get_enabled_floors(pos, w, h)
    # 進行方向リストをシャッフル
    |> shuffle(seed)
    （中略）
  end

実行関数

  @doc """
  実行
  （シード値、横幅、縦幅）
  """
  @spec run(integer, integer, integer) :: any
  def run(seed \\ 1, w \\ 18, h \\ 9) do
    IO.puts("#{w} x #{h}, seed = #{seed}")

    route =
      update_route(
        %{connects: Map.new(), visited: MapSet.new()},
        {w, h},
        {0, 0},
        seed
      )

    display(route, {w, h})
  end

結果

18 x 9, seed = 1
■--■--■--■--■--■--■--■--■--■--■--■--■--■--■--■--■--■--■
|  |        |                 |  |           |        |
■  ■--■  ■  ■  ■--■  ■--■--■  ■  ■  ■--■  ■  ■--■--■  ■
|     |  |     |     |     |  |  |     |  |           |
■--■  ■--■--■  ■  ■--■  ■  ■  ■  ■--■  ■  ■  ■--■--■--■
|  |        |  |  |  |  |  |  |        |  |  |        |
■  ■--■--■  ■--■  ■  ■  ■  ■  ■--■--■  ■  ■--■  ■--■  ■
|     |     |     |     |  |  |     |  |  |     |     |
■  ■--■  ■--■  ■--■  ■--■  ■  ■  ■  ■--■  ■  ■--■  ■  ■
|  |     |     |     |     |     |     |     |  |  |  |
■  ■  ■--■  ■--■  ■--■  ■--■--■--■--■  ■--■  ■  ■  ■--■
|     |     |     |     |           |     |     |     |
■  ■--■  ■  ■--■--■  ■  ■  ■--■  ■--■--■  ■  ■--■--■  ■
|     |  |        |  |  |  |  |  |        |  |        |
■--■  ■  ■--■--■  ■  ■--■  ■  ■  ■  ■--■--■--■  ■--■--■
|     |        |  |        |  |  |  |        |        |
■  ■--■--■--■--■  ■  ■--■--■  ■  ■  ■--■  ■  ■--■--■  ■
|                 |           |           |           |
■--■--■--■--■--■--■--■--■--■--■--■--■--■--■--■--■--■--■

18 x 9, seed = 2
■--■--■--■--■--■--■--■--■--■--■--■--■--■--■--■--■--■--■
|  |  |                       |                       |
■  ■  ■  ■--■--■--■  ■--■--■  ■  ■--■--■  ■  ■--■--■--■
|  |        |     |        |  |        |  |  |        |
■  ■--■--■  ■  ■  ■--■--■  ■--■--■--■  ■  ■--■  ■--■  ■
|        |  |  |  |     |              |           |  |
■--■--■  ■  ■--■  ■  ■  ■  ■--■--■--■--■--■--■--■--■  ■
|  |     |     |  |  |  |        |     |     |        |
■  ■  ■--■--■  ■  ■  ■  ■--■--■  ■  ■  ■--■  ■  ■--■  ■
|     |     |     |  |  |     |     |        |  |  |  |
■  ■--■  ■  ■--■  ■  ■  ■  ■  ■--■--■--■--■  ■  ■  ■  ■
|  |     |  |     |  |     |     |           |  |     |
■  ■  ■--■  ■--■--■  ■--■--■--■  ■--■--■--■--■  ■--■--■
|     |  |     |     |        |     |        |        |
■--■--■  ■--■  ■  ■--■  ■  ■--■--■  ■  ■--■  ■  ■--■  ■
|              |  |     |  |        |  |  |  |     |  |
■  ■--■--■--■--■  ■  ■  ■--■  ■--■--■  ■  ■  ■--■--■  ■
|                 |  |                 |              |
■--■--■--■--■--■--■--■--■--■--■--■--■--■--■--■--■--■--■

18 x 9, seed = 3
■--■--■--■--■--■--■--■--■--■--■--■--■--■--■--■--■--■--■
|        |           |        |     |        |        |
■--■--■  ■  ■--■--■--■  ■  ■  ■  ■  ■--■  ■  ■--■--■  ■
|     |  |  |           |  |     |     |  |           |
■  ■--■  ■  ■  ■--■--■--■  ■--■--■--■  ■  ■--■--■--■  ■
|  |     |     |           |        |  |  |        |  |
■  ■  ■--■--■  ■  ■--■--■--■  ■--■  ■  ■  ■  ■--■  ■  ■
|     |     |  |                 |  |     |  |  |  |  |
■  ■--■  ■  ■  ■--■--■  ■--■--■--■  ■--■--■  ■  ■  ■  ■
|  |     |  |  |     |     |        |        |     |  |
■  ■  ■--■  ■--■  ■  ■--■  ■  ■--■--■  ■  ■--■--■--■  ■
|     |  |     |  |  |     |  |     |  |              |
■--■--■  ■--■  ■  ■  ■--■--■  ■--■  ■  ■--■--■--■--■--■
|              |  |  |     |     |     |              |
■  ■--■--■--■--■  ■  ■  ■  ■--■  ■  ■--■  ■--■--■--■  ■
|  |        |     |     |     |  |     |  |        |  |
■  ■  ■--■  ■--■  ■--■--■--■  ■  ■--■  ■--■  ■--■  ■  ■
|     |           |              |           |        |
■--■--■--■--■--■--■--■--■--■--■--■--■--■--■--■--■--■--■

以降、seedの値を変える事で迷路のパターンが決定します。

参考文献

迷路生成（穴掘り法）- Algoful

完走した感想

組み始めた段階ではすぐ完成するだろうと高を括ってましたが、結局3回もやり直しました。誤差の範囲内とは言い難いですが、学習は失敗を繰り返してこそ習得できると誰かが言っていた気がするので、これを今後の糧として色々な言語やアルゴリズムに挑戦していきます。

過去投稿一覧

ライフゲームもやってます。

おわりに

ここまでご閲覧いただきありがとうございます。

今後も思いつくままに記事投稿を続けて行きたい所存であります。

星と深淵を目指せ！

10
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
10
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?