はじめに
（迷路アルゴリズムは）初投稿です。
古来より伝わる「迷路生成アルゴリズム」をElixir言語で実装しよう…としたのですが…
色々あって何度もやり直してしまって投稿が間に合わなそうなので途中経過を公開します。
開発環境
- MacStudio2023(M2 Max)
- macOS Tahoe(26.1)
- Erlang/OTP 27
- Elixir 1.19.3
色々と問題のあるコード
defmodule Maze do
@moduledoc """
Documentation for `Maze`.
"""
# ---- 初期化 ----
# 最初の壁情報の配列を取得
# 左上
defp get_first_walls(x, y, _w, _h) when x == 0 and y == 0, do: %{0 => true, 3 => true}
# 右上
defp get_first_walls(x, y, w, _h) when x == w - 1 and y == 0, do: %{0 => true, 1 => true}
# 左下
defp get_first_walls(x, y, _w, h) when x == 0 and y == h - 1, do: %{2 => true, 3 => true}
# 右下
defp get_first_walls(x, y, w, h) when x == w - 1 and y == h - 1, do: %{1 => true, 2 => true}
# 左
defp get_first_walls(x, _y, _w, _h) when x == 0, do: %{3 => true}
# 右
defp get_first_walls(x, _y, w, _h) when x == w - 1, do: %{1 => true}
# 上
defp get_first_walls(_x, y, _w, _h) when y == 0, do: %{0 => true}
# 下
defp get_first_walls(_x, y, _w, h) when y == h - 1, do: %{2 => true}
# その他
defp get_first_walls(_x, _y, _w, _h), do: %{}
# ---- 初期化 ----
defp apply_maze_floor(maze, {w, h}, {x, y}) do
maze = Map.put(maze, {x, y}, %{walls: get_first_walls(x, y, w, h), visited: false})
if x == w - 1 and y == h - 1 do
maze
else
if x == w - 1 do
apply_maze_floor(maze, {w, h}, {0, y + 1})
else
apply_maze_floor(maze, {w, h}, {x + 1, y})
end
end
end
def create_first_maze({w, h}) do
maze = %{}
apply_maze_floor(maze, {w, h}, {0, 0})
end
# ---- 迷路生成 ----
# 反対の方向を取得
defp get_anti_direction(0), do: 2
defp get_anti_direction(1), do: 3
defp get_anti_direction(2), do: 0
defp get_anti_direction(3), do: 1
# 次のx座標を取得
defp get_next_x(x, 3), do: x - 1
defp get_next_x(x, 1), do: x + 1
defp get_next_x(x, _), do: x
# 次のy座標を取得
defp get_next_y(y, 0), do: y - 1
defp get_next_y(y, 2), do: y + 1
defp get_next_y(y, _), do: y
# 現在地を訪問済みにする
defp update_visited(maze, {x, y}) do
floor = Map.get(maze, {x, y})
Map.put(maze, {x, y}, %{walls: floor.walls, visited: true})
end
defp find_free_directions(walls) do
[1, 2, 3, 0] |> Enum.filter(fn d -> Map.get(walls, d) == nil end)
end
# 次のフロアの座標を決める
defp find_next_position(maze, {x, y}) do
now_floor = Map.get(maze, {x, y})
next_direction = find_free_directions(now_floor.walls) |> Enum.shuffle() |> Enum.at(0)
next_x = get_next_x(x, next_direction)
next_y = get_next_y(y, next_direction)
{next_x, next_y}
end
# フロアの壁を更新
defp update_walls(maze, {x, y}, walls, visited) do
Map.put(maze, {x, y}, %{walls: walls, visited: visited})
end
defp crave_safe(maze, {x, y}) do
IO.inspect({x, y})
# 現在地を訪問済みにする
maze = update_visited(maze, {x, y})
IO.inspect(Map.get(maze, {x, y}))
# 現在フロア
floor = Map.get(maze, {x, y})
walls = floor.walls
# 移動可能方向を決める
free_directions = find_free_directions(walls)
# 移動可能方向が1つしか無いなら
if length(free_directions) == 1 do
next_position = find_next_position(maze, {x, y})
{maze, next_position}
else
# 移動方向が2個以上ある前提
wall_direction = Enum.shuffle(free_directions) |> Enum.at(1)
# 置く方向にあるフロアを取得
pair_x = get_next_x(x, wall_direction)
pair_y = get_next_y(y, wall_direction)
IO.inspect({pair_x, pair_y})
# ペアが無い場合は次のフロアを探す
if Map.has_key?(maze, {pair_x, pair_y}) == false do
next_position = find_next_position(maze, {x, y})
{maze, next_position}
else
pair_floor = Map.get(maze, {pair_x, pair_y})
IO.inspect(pair_floor)
# ペアが訪問済みの場合は次のフロアを探す
if pair_floor.visited do
next_position = find_next_position(maze, {x, y})
{maze, next_position}
else
pair_direction = get_anti_direction(wall_direction)
maze = update_walls(maze, {x, y}, Map.put(walls, wall_direction, true), floor.visited)
maze =
update_walls(
maze,
{pair_x, pair_y},
Map.put(pair_floor.walls, pair_direction, true),
pair_floor.visited
)
next_position = find_next_position(maze, {x, y})
{maze, next_position}
end
end
end
end
def crave(maze, {x, y}) do
# フロアチェック
if Map.has_key?(maze, {x, y}) == false do
{maze, {0, 0}}
else
crave_safe(maze, {x, y})
end
end
# ---- 表示文字列 ----
defp get_horizontal_wall_row_str(maze, w, h, y) do
for x <- 0..(w - 1) do
if Map.has_key?(maze, {x, y}) do
floor = Map.get(maze, {x, y})
direction = 0
if Map.get(floor.walls, direction) do
"◯--"
else
"◯ "
end
else
"***"
end
end
|> Enum.join()
end
defp get_vertical_wall_row_str(maze, w, y) do
for x <- 0..(w - 1) do
if Map.has_key?(maze, {x, y}) do
floor = Map.get(maze, {x, y})
direction = 3
if Map.get(floor.walls, direction) do
if floor.visited do
"|* "
else
"| "
end
else
if floor.visited do
" * "
else
" "
end
end
else
" "
end
end
|> Enum.join()
end
defp get_bottom_wall_str(w) do
for x <- 0..w do
if x == w do
"◯"
else
"◯--"
end
end
|> Enum.join("")
end
defp get_maze_unfinished_str(maze, {w, h}) do
for y <- 0..(h - 1) do
get_horizontal_wall_row_str(maze, w, h, y) <>
"◯\n" <> get_vertical_wall_row_str(maze, w, y) <> "|"
end
|> Enum.join("\n")
end
def get_maze_str(maze, {w, h}) do
get_maze_unfinished_str(maze, {w, h}) <> "\n" <> get_bottom_wall_str(w)
end
# ---- main ---
defp loop(maze, {w, h}, {x, y}, last \\ 20) do
if last < 0 do
IO.puts("Finished!")
else
new_package = crave(maze, {x, y})
{new_maze, {new_x, new_y}} = new_package
IO.puts(get_maze_str(new_maze, {w, h}))
loop(new_maze, {w, h}, {new_x, new_y}, last - 1)
end
end
def run(w \\ 6, h \\ 6) do
# IO.inspect({w, h})
maze = create_first_maze({w, h})
IO.puts(get_maze_str(maze, {w, h}))
loop(maze, {w, h}, {0, 0})
end
end
色々と問題のある結果
◯--◯--◯--◯--◯--◯--◯
|* |* |
◯ ◯ ◯--◯ ◯ ◯ ◯
|* |* * * |
◯ ◯ ◯ ◯ ◯ ◯ ◯
|* * * |
◯--◯--◯--◯ ◯ ◯ ◯
| |
◯ ◯ ◯ ◯ ◯ ◯ ◯
| |
◯ ◯ ◯ ◯ ◯ ◯ ◯
| |
◯--◯--◯--◯--◯--◯--◯
迷走している原因
迷路なだけに（喧）
- 参考にした文献の解釈を間違えたままコードを書いてしまい、結果何度も最初から作り直すことに
- ElixirにC言語のような手続き形式で書いてしまい、何度もエラーになったり期待動作しなかったり
とはいえ不完全ながら形は整ってきたので、近いうちに完全版を投稿目指します。
そうだな、私は「結果」だけを求めたりはしない。
「結果」だけを求めると、人は手を抜きたがるものだ。楽をして「結果」を求めてもまず上手くいかない、いつまでたってもたどり着かなければ、しだいにやる気を無くしてしまう。
大切なのは「真実に近づこうとする意思」だと思っている。
たとえ今完成していなくても、「真実に近づく」ことを忘れずに進み続ければ、いずれは完成するはずだ。
違うかい？
過去投稿一覧
ライフゲームもやってます。
- ライフゲームをモダンな書き方で・Swift編・探究の章
- ライフゲームをモダンな書き方で・Swift編・発動の章
- ライフゲームをモダンな書き方で・Rust接触編
- ライフゲームをモダンな書き方で・Elixir接触編
- ライフゲームをElixir言語で並列化したかっただけなのに…
おわりに
ここまでご閲覧いただきありがとうございます。
今後も思いつくままに記事投稿を続けて行きたい所存であります。
…そうだ…思い出した…行かなくては…あの場所に…