Haskellで棒倒し法による迷路作成プログラム

Cyber Tribe

2025年1月3日 10:11

棒倒し法を使用して迷路を作成するプログラムをHaskellで実装します。この手法では、壁で埋めたグリッドにランダムな通路を追加して迷路を生成します。

1. 棒倒し法の概要

棒倒し法のステップは次のとおりです。

壁で埋められたグリッドを用意します。
任意の位置からランダムな方向に「棒」を倒すことで通路を作成します。

特徴

ランダムに選択した方向に1マス分壁を壊すため、迷路に規則性が少なくなります。

2. 環境構築

Haskellの環境構築は、こちらを確認してください。

3. プログラム実装

乱数を扱うために下記を実行してパッケージをインストールしてください

stack install random

Maze.hsという名前で以下のコードを保存してください。

{-# LANGUAGE ScopedTypeVariables #-}

import System.Random (randomRIO)
import Control.Monad (forM_, foldM)

data Maze = Maze { width :: Int, height :: Int, grid :: [[Char]] }

createMaze :: Int -> Int -> Maze
createMaze w h = Maze w h (replicate h (replicate w '#'))

knockDownWall :: Maze -> Int -> Int -> IO Maze
knockDownWall maze x y = do
    let directions = [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]
    let validDirections = filter (isValid (width maze) (height maze)) directions
    if null validDirections
        then return maze
        else do
            (dx, dy) <- randomElement validDirections
            let newMaze = updateMaze maze x y dx dy
            knockDownWall newMaze (x + dx) (y + dy)

isValid :: Int -> Int -> (Int, Int) -> Bool
isValid w h (x, y) = x > 0 && x < w - 1 && y > 0 && y < h - 1

randomElement :: [(Int, Int)] -> IO (Int, Int)
randomElement xs = do
    index <- randomRIO (0, length xs - 1)
    return (xs !! index)

updateMaze :: Maze -> Int -> Int -> Int -> Int -> Maze
updateMaze maze x y dx dy = 
    let newGrid = take y (grid maze) ++ 
                  [take x (grid maze !! y) ++ [' '] ++ drop (x + 1) (grid maze !! y)] ++ 
                  drop (y + 1) (grid maze)
    in maze { grid = newGrid }

generateMaze :: Maze -> IO Maze
generateMaze maze = do
    newMaze <- foldM (\m y -> foldM (\m' x -> knockDownWall m' x y) m [1, 3..(width maze - 2)]) maze [1, 3..(height maze - 2)]
    return newMaze

printMaze :: Maze -> IO ()
printMaze maze = mapM_ putStrLn (grid maze)

main :: IO ()
main = do
    let maze = createMaze 21 21
    generatedMaze <- generateMaze maze
    printMaze generatedMaze

4. 実行

以下のコマンドを使用してプログラムを実行します。

runhaskell Maze.hs

コンソールに生成された迷路が出力されます。
実行するたびに新しい迷路が生まれます。

#####################
#☆      #   #   #   #
# # # ####### # # ###
# # # #       # #   #
# # ### # ### ### ###
# # # # #   # #   # #
# # # # ####### # # #
# #   # #   #   # # #
### ##### ######### #
# # #   # #   #   # #
# ##### ######### ###
#   # # #     #     #
##### # ##### ### # #
#     # #       # # #
####### ##### ##### #
#   #     # # #   # #
# # ####### ##### # #
#   #     # #   #   #
# # ### ### # #######
# # #       #      ☆#
#####################

まとめ

Haskellの実装を通じて、棒倒し法のシンプルなアルゴリズムを紹介しました。コードの応用や改良を試してみてください。