maze.c to …
Table of Contents
see maze.c
前回は、C言語アルゴリズム辞典に出てた迷路作成プログラムをhaskell様に作 成させて実行してみた。勿論一発で動くはずはなく、永久ループの迷路に突入。 自ら体現させてくれるChatGPTは偉いなあ。そんな事を言ってる場合じゃない でしょう。
アルゴリズム辞典には、壁延長法による例が掲載されてたんだけど、他にどん な方法が有る？ 野次馬根性で調べてみたら、 迷路生成(壁伸ばし法) こんな楽しいのに出あった。動く物大好きって、ガラ ガラ大好きな赤ちゃ んだな。
dump map
maze.c を久し振りにgdbにかけてみた。迷路のサイズは小さ目で 8x8にした。
下記は、迷路の初期化が終了した時の配列データ。1が壁(wall)、0が通路(path)に相当。
(gdb) x/64cx map 0x3b5fa340 <map>: 0x01 0x01 0x01 0x01 0x01 0x01 0x01 0x01 0x3b5fa348 <map+8>: 0x01 0x01 0x01 0x01 0x01 0x01 0x01 0x01 0x3b5fa350 <map+16>: 0x01 0x01 0x01 0x01 0x01 0x00 0x01 0x01 0x3b5fa358 <map+24>: 0x01 0x01 0x01 0x01 0x01 0x01 0x00 0x00 0x3b5fa360 <map+32>: 0x00 0x01 0x01 0x01 0x01 0x01 0x01 0x00 0x3b5fa368 <map+40>: 0x00 0x00 0x01 0x01 0x01 0x01 0x01 0x01 0x3b5fa370 <map+48>: 0x00 0x00 0x00 0x01 0x01 0x01 0x01 0x01 0x3b5fa378 <map+56>: 0x01 0x01 0x01 0x00 0x01 0x01 0x01 0x01
こちらが普段使いのコマンドの結果。上記と微妙に結果が違うな。コードと照 らし合わせると、p/x の方が正しい。なんで？
(gdb) p/x map
$1 = {
{0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1},
{0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1},
{0x1, 0x1, 0x1, 0x0, 0x1, 0x1, 0x1, 0x1, 0x1},
{0x1, 0x1, 0x1, 0x0, 0x0, 0x0, 0x1, 0x1, 0x1},
{0x1, 0x1, 0x1, 0x0, 0x0, 0x0, 0x1, 0x1, 0x1},
{0x1, 0x1, 0x1, 0x0, 0x0, 0x0, 0x1, 0x1, 0x1},
{0x1, 0x1, 0x1, 0x1, 0x1, 0x0, 0x1, 0x1, 0x1},
{0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1},
{0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1, 0x1}}
そしてこちらが壁を成長させていくべき始点となる座標。コメント上ではサイ トって呼称してる。
(gdb) p xx
$1 = {4, 4, 2, 6, 0 <repeats 12 times>}
(gdb) p yy
$2 = {2, 6, 4, 4, 0 <repeats 12 times>}
これが登録完了すると、後は乱数でサイトを選択して壁を成長。もう壁を延長 できなくなったら、次のサイトを選択して同様に繰り返し。全部のサイトを実 施したら、迷路完成ってこと。大事な構造を確認しましたからね。
Main.hs
何度かChatGPTとチャットして、コンパイルエラーを潰した。奴はコンパイラー を持っていないので、オイラーが代行するのさ。奴もコンパイラーを内包して くれればいいのに。pythonなら人口が多いから内包するかも。いや、そりゃ無 理だろうよ。昔々のCGI問題にぶちあたるからね。その点、コンパイラー系な ら、コンパイルと実行とは全く別物だから、容易だろう。
外観検査
[sakae@fb /tmp/c2hmaze]$ grep :: app/Main.hs | cut -b-75
xMax, yMax, maxSite :: Int
dx, dy :: [Int]
dirTable :: [[Direction]]
add :: [(Int, Int)] -> (Int, Int) -> [(Int, Int)]
selsite :: [(Int, Int)] -> IO ([(Int, Int)], Maybe (Int, Int))
isValid :: Maze -> (Int, Int) -> Bool
generateMaze :: IO Maze
generateMaze' :: [(Int, Int)] -> Maze -> IO ([(Int, Int)], Maze)
generatePath :: (Int, Int) -> [(Int, Int)] -> Maze -> IO ([(Int, Int)], Maz
generatePathHelper :: [(Int, Int)] -> Maze -> IO ([(Int, Int)], Maze)
let neighbors = [(x + dx !! fromEnum (dir :: Direction), y + dy
generatePath' :: (Int, Int) -> [(Int, Int)] -> Maze -> IO ([(Int, Int)], Ma
generatePath'' :: (Int, Int) -> [Direction] -> [(Int, Int)] -> Maze -> IO (
updateMaze :: Maze -> Int -> Int -> Int -> Int -> Int -> Int -> Maze
replaceElem :: [a] -> Int -> a -> [a]
main :: IO ()
maze.cでは、主要ロジックがmainの中に閉じ込められていたけど、それが適当 な単位に分割されて関数になってる。補助関数もwhereで内包するのを嫌って 分離してる。
main = do
maze <- generateMaze
mapM_ putStrLn maze
haskellではmainを数行内に収めるってのが鉄則。やりたい主張が良くわかる。 なお、maze.cでmainに集中してるのは、辞書と言う事で、圧縮した記述になっ ているのだろう。
小手調べで、独立した関数の比較
maze.cで独立した関数になってるサイトを乱数で選ぶ部分を、haskellと対比 させてみる。尚オリジナルでは、selectとなってたけど、これだとCのライブ ラリィーと名前がバッティングするので、変更してる。
int xselect(int *i, int *j) {
int r;
if (nsite == 0) return 0; /* サイトが尽きた */
nsite--; r = (int)(nsite * (rand() / (RAND_MAX + 1.0)));
*i = xx[r]; xx[r] = xx[nsite];
*j = yy[r]; yy[r] = yy[nsite]; return 1; /* 成功 */
}
この関数は、whileの中からcallされるので、その制御用に return 0/1 が用 意されてる。肝心の選んだサイトのX,Y座標は、i/jを更新する事で、親側に伝 えてる。これが、haskellだと、ちょっと関数名が異なるけど
selsite :: [(Int, Int)] -> IO ([(Int, Int)], Maybe (Int, Int))
selsite [] = return ([], Nothing)
selsite sites = do
r <- randomRIO (0, length sites - 1)
let selected = sites !! r
let remaining = take r sites ++ drop (r + 1) sites
return (remaining, Just selected)
サイトを表現するsitesが入力。よく見ると複数を表わすsが変数名になってる。 見落しがちだけど、大事な情報だ。座標はタプル表現。出力は、タプル。 Maybeを付けてある方は、選択できたらって意味だ。
乱数で、入力のうちの一つを選ぶ。選んだ物を取り除けば、残りになる。 takeとdropを上手に使って、残り物を計算してるね。結局、Just selectedが 肝。これがNotiingなら、maze.cのreturn 0になるし、Justならば、その中身 のタプルが、i/j 相当となる。
今度は冒頭から構造の比較
char map[XMAX + 1][YMAX + 1]; /* 地図 */
int nsite = 0; /* 登録サイト数 */
int xx[MAXSITE], yy[MAXSITE]; /* 登録サイト座標 */
int dx[4] = { 2, 0, -2, 0 }; /* 変位ベクトル */
int dy[4] = { 0, 2, 0, -2 }; /* 変位ベクトル */
int dirtable[24][4] = { /* 方向表 */
0,1,2,3, 0,1,3,2, 0,2,1,3, 0,2,3,1, 0,3,1,2, 0,3,2,1,
:
map,xx,yyがしっかり配列として鎮座してる。その他、方向を決定する為のテー ブルも配列として、グローバルな場所に用意してる。haskell側はどうよ？
type Maze = [[Char]]
data Direction = North | East | South | West deriving (Enum, Bounded)
dx, dy :: [Int]
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]
dirTable :: [[Direction]]
dirTable =
[ [North, East, South, West]
, [North, East, West, South]
:
mapに相当する配列は、Mazeって名前で呼んでくれって宣言が有るのみ。それ から、サイト座標を表わす xx/yy配列に至っては、名前すら出てこない。
方向テーブルはhaskellの拘りの表現になってる。日本人なら、東西南北より、 上下左右を選ぶだろうけど、あちらの人は、この表現の方を好むのか。 そうか、上下って、ちと曖昧な表現だな。平面じゃなくて、立体での上下って 解釈もできるからね。
昔のパソコンの中身の説明でCPUを中心に置いて、ノースブリッジやらサウス ブリッジなんてのが出てきて、しばし何の事やらと悩んだものだ。それから、 javaでお絵書きした時も、東西南北が出てたので、普通の事なんだな。
迷路中心 generateMaze
いよいよ核心部分に迫って行く。こんな定義だ。
generateMaze :: IO Maze
generateMaze = do
let initialMaze = replicate yMax (replicate xMax '#')
let sites = foldl add [] [(i, j) | i <- [0, 2 .. xMax - 2], j <- [0, 2 .. yMax - 2]]
(_, maze) <- generateMaze' sites initialMaze
return maze
本当の核心は、ダッシュの付いた generateMaze' なんだけどね。だから、こ の関数は、generateMaze' を呼び出す準備をしてるんだな。引数は、ここで作 成した、初期状態のMazeとサイトだ。だから、グローバルに配列を用意するっ て事は無いんだ。そして、変更されて作成されたmazeが、最終結果になるとな。
ちょいと実験
debuggerを使うのは難儀なので、ghci上で実験。
λ> let wall = replicate yMax (replicate xMax '#') λ> mapM_ putStrLn wall ######## ######## ######## ######## ######## ######## ######## ########
立っている者は、親でも使えって言われているので、mainの中の出力方法を利 用してみた。望み通りの結果。続いて、サイトの作成。
λ> let sites = foldl add [] [(i, j) | i <- [0, 2 .. xMax - 2], j <- [0, 2 .. yMax - 2]] λ> sites [(6,6),(6,4),(6,2),(6,0),(4,6),(4,4),(4,2),(4,0),(2,6),(2,4),(2,2),(2,0),(0,6),(0,4),(0,2),(0,0)]
配列の変更
立っている者は親でも使えの第二弾。ChatGPTが提示してきた、replaceElemを 利用して、ピンポイントで、2次元配列を変更する関数を作成。それなりに英 語チックに読めるのは、提示された関数だ。オイラーのは意味不。
pinW :: Int -> Int -> Maze -> Maze
pinW x y maze =
replaceElem maze y (replaceElem (maze !! y) x '.')
replaceElem :: [a] -> Int -> a -> [a]
replaceElem lst idx val = take idx lst ++ [val] ++ drop (idx + 1) lst
本当は、Maze -> Int -> Int -> Maze にしたいんだけど、後の都合を考えて こうしてる。とりあえずテスト。
λ> mapM_ putStrLn $ pinW 5 2 wall ######## ######## #####.## ######## ######## ######## ######## ########
良さそうなので、発展させる。複数の場所の変更バージョン。
λ> let z = foldr (\s -> pinW (fst s) (snd s)) wall [(2,3), (7,5)] λ> mapM_ putStrLn z ######## ######## ######## ##.##### ######## #######. ######## ########
何は無くとも、要素技術を追加したぞ。GPTがアイデアを提示してくれるんで 楽だ。丁度スタートアップ企業で 0 -> 1 にするアイデア出しがGPT担当で、1 -> 2 にするのがオイラーの役目って所かな。
ちゃんと構築してるか？
C言語は普通に何でもできる奴。それに対してhaskellは小回りが効かない風。 適当にやっちゃっていないか？
maze.cでの初期化部分だ。
for (i = 0; i <= XMAX; i++) /* 地図を初期化 */
for (j = 0; j <= YMAX; j++) map[i][j] = 1;
for (i = 3; i <= XMAX - 3; i++)
for (j = 3; j <= YMAX - 3; j++) map[i][j] = 0;
map[2][3] = 0; map[XMAX - 2][YMAX - 3] = 0;
for (i = 4; i <= XMAX - 4; i += 2) { /* サイトを加える */
add(i, 2); add(i, YMAX - 2);
}
for (j = 4; j <= YMAX - 4; j += 2) {
add(2, j); add(XMAX - 2, j);
}
B => while (selran(&i, &j)) { /* サイトを選ぶ */
上で出てきた、generateMazeと比べてみると、明らかに手抜きした感がある。 例えば、sitesの登録部分。適当に内包表記してる。3,4番目のforを実現する のは、下記だろう。こうして取り出した物を使って、add関数を呼び出す必要 がある。
λ> let q = [(i, j) | i <- [4,6 .. xMax - 4], j <- [4,6 .. yMax - 4]] λ> q [(4,4)]
裏のmain
本当のmainはgenerateMaze' になる。
enerateMaze' :: [(Int, Int)] -> Maze -> IO ([(Int, Int)], Maze)
generateMaze' [] maze = return ([], maze)
generateMaze' sites maze = do
(sites', maybeSite) <- selsite sites
case maybeSite of
Nothing -> return (sites', maze)
Just (x, y) -> do
(_, maze') <- generatePath (x, y) sites' maze
generateMaze' sites' maze'
注目は、この関数の終了条件。ちゃんとsitesが尽きた時って指定されている。 それ以外は、selsiteを呼出、壁を成長させる作業を実施。何か玉葱の皮を永 遠と剥いて行く風だな。きりが無いので、generatePathに注目してみる。
generatePathの中
更に奥の所に、こんなのが出てきてた。提示されたものは、一行で表現されて たけど、内包表記の構造が分かり易いように、変更してみた。
let neighbors = [(x + dx !! fromEnum (dir :: Direction),
y + dy !! fromEnum (dir :: Direction))
| dir <- [minBound .. maxBound]]
見慣れない関数が出てきた。調べてみると、Enumの値を数値に変換するみたい。 minBoundとかは、その範囲ね。EnumなんてC語にも普通に出てくるけど、 haskellでは、面倒な事を強いる訳ね。まあ、それが安心材料になるんだけど ね。
λ> fromEnum North 0 λ> fromEnum West 3
続いて実行
λ> dx
[0,1,0,-1]
λ> dy
[-1,0,1,0]
λ> let x = 0
λ> let y = 0
λ> let near = [(x + dx !! fromEnum (dir :: Direction),
y + dy !! fromEnum (dir :: Direction))
| dir <- [minBound .. maxBound]]
λ> near
[(0,-1),(1,0),(0,1),(-1,0)]
何か無駄な空振りしてないか。単に自慢したいだけ？
足りないぞ
maze.cでは、方向テーブルから方向を乱数で選択してる。
tt = dirtable[(int)(24 * (rand() / (RAND_MAX + 1.0)))];
対してhaskell側では、こんなのだ。ここ一箇所しかない。別な角度って事で randを探しても、selsiteの中だけだ。よって、インチキ捏造が確定した。
let directions = dirTable !! fromEnum (maze !! snd current !! fst current == ' ')
これ以上、探索しても無駄だな。
せいぜい、部品取りとか、普段ではお目にかかる事が無い関数に遭遇して、そ れ調べてみろぐらいにしか、使い道がない。
今回の試行で得る所が有ったとするなら、リストを1次元もしくは2次元と見做 した時の、更新方法を手に入れた事だろう。それとて、演算量は、O(n) なの で、使う場所を選ぶだろう。
今回は、不本意ながら、これで終了する。