Day17. テキストベースの迷路生成＆探索 - 勝手にChatGPTチャレンジ (Python)

前提

本日のお題

---

20. テキストベースの迷路生成＆探索

何を作る？
ランダム生成した迷路を # とスペースで表示し、人間が矢印キーで動いてゴールを目指すゲーム（or 自動探索）。

学べること

• 2次元リスト・グリッドの表現
• 迷路生成アルゴリズム（穴掘り法など、シンプルなもの）
• キーボード入力（curses や簡単版なら入力ごとに描画）

面白いところ

• アルゴリズムが目に見える形で結果に出る
• 自動的に最短経路を探すアルゴリズム（BFS/DFS）を追加して楽しめる

---

回答

コード

20_maze_game.py

#!/usr/bin/env python3
"""
テキストベース迷路（生成 + 探索）

- 生成: 穴掘り法（ランダム DFS / Recursive Backtracker）
- 表示: # (壁), ' ' (通路)
- 手動: WASD で移動、q で終了
- 自動: BFS で最短経路を探して表示

使い方:
  python maze_game.py
  python maze_game.py --w 31 --h 21 --mode auto
  python maze_game.py --seed 123 --mode play
"""

from __future__ import annotations

import argparse
import random
from collections import deque
from dataclasses import dataclass
from typing import List, Tuple, Optional, Dict


WALL = "#"
PATH = " "


@dataclass(frozen=True)
class Pos:
    x: int
    y: int


def parse_args() -> argparse.Namespace:
    p = argparse.ArgumentParser(description="テキスト迷路 生成＆探索")
    p.add_argument("--w", type=int, default=31, help="迷路の幅（奇数推奨）")
    p.add_argument("--h", type=int, default=21, help="迷路の高さ（奇数推奨）")
    p.add_argument("--seed", type=int, default=None, help="乱数シード（再現用）")
    p.add_argument(
        "--mode",
        choices=["play", "auto"],
        default="play",
        help="play: 手動プレイ / auto: 自動で最短経路を表示",
    )
    return p.parse_args()


def ensure_odd(n: int, minimum: int = 5) -> int:
    """幅・高さを最低値以上の奇数に丸める。"""
    n = max(n, minimum)
    if n % 2 == 0:
        n += 1
    return n


def make_grid(w: int, h: int) -> List[List[str]]:
    """全部壁で初期化したグリッドを作る。"""
    return [[WALL for _ in range(w)] for _ in range(h)]


def neighbors_2step(p: Pos) -> List[Tuple[Pos, Pos]]:
    """
    穴掘り法用：2マス先の候補（通路セル）と、その間の壁セルを返す。
    (next_cell, between_wall)
    """
    dirs = [(2, 0), (-2, 0), (0, 2), (0, -2)]
    res = []
    for dx, dy in dirs:
        nxt = Pos(p.x + dx, p.y + dy)
        mid = Pos(p.x + dx // 2, p.y + dy // 2)
        res.append((nxt, mid))
    return res


def in_bounds(p: Pos, w: int, h: int) -> bool:
    return 0 <= p.x < w and 0 <= p.y < h


def generate_maze(w: int, h: int, rng: random.Random) -> Tuple[List[List[str]], Pos, Pos]:
    """
    穴掘り法（ランダム DFS）で迷路生成。
    - (1,1) をスタート、(w-2,h-2) をゴールにする（どちらも通路）
    """
    grid = make_grid(w, h)

    start = Pos(1, 1)
    goal = Pos(w - 2, h - 2)

    # 開始地点を通路に
    grid[start.y][start.x] = PATH

    stack = [start]
    while stack:
        cur = stack[-1]

        # 2マス先が壁の候補だけ集める
        candidates = []
        for nxt, mid in neighbors_2step(cur):
            if not in_bounds(nxt, w, h):
                continue
            if grid[nxt.y][nxt.x] == WALL:
                candidates.append((nxt, mid))

        if not candidates:
            stack.pop()
            continue

        nxt, mid = rng.choice(candidates)
        grid[mid.y][mid.x] = PATH
        grid[nxt.y][nxt.x] = PATH
        stack.append(nxt)

    # ゴールが壁のままの可能性は低いが、念のため通路にする
    grid[goal.y][goal.x] = PATH

    return grid, start, goal


def render(grid: List[List[str]], player: Pos, start: Pos, goal: Pos, path: Optional[set[Pos]] = None) -> str:
    """
    グリッドを文字列にして返す。
    - player: 'P'
    - start : 'S'
    - goal  : 'G'
    - path  : 自動探索の経路（'.'）
    """
    h = len(grid)
    w = len(grid[0])
    path = path or set()

    lines = []
    for y in range(h):
        row_chars = []
        for x in range(w):
            p = Pos(x, y)
            if p == player:
                row_chars.append("P")
            elif p == start:
                row_chars.append("S")
            elif p == goal:
                row_chars.append("G")
            elif p in path and grid[y][x] == PATH:
                row_chars.append(".")
            else:
                row_chars.append(grid[y][x])
        lines.append("".join(row_chars))
    return "\n".join(lines)


def bfs_shortest_path(grid: List[List[str]], start: Pos, goal: Pos) -> Optional[List[Pos]]:
    """BFS で最短経路（Pos のリスト）を返す。見つからなければ None。"""
    h = len(grid)
    w = len(grid[0])

    def walkable(p: Pos) -> bool:
        return in_bounds(p, w, h) and grid[p.y][p.x] == PATH

    q = deque([start])
    prev: Dict[Pos, Optional[Pos]] = {start: None}

    dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    while q:
        cur = q.popleft()
        if cur == goal:
            break
        for dx, dy in dirs:
            nxt = Pos(cur.x + dx, cur.y + dy)
            if nxt in prev:
                continue
            if not walkable(nxt):
                continue
            prev[nxt] = cur
            q.append(nxt)

    if goal not in prev:
        return None

    # 復元
    path = []
    cur: Optional[Pos] = goal
    while cur is not None:
        path.append(cur)
        cur = prev[cur]
    path.reverse()
    return path


def clear_screen():
    # 端末依存だが、簡単にクリア
    print("\033[2J\033[H", end="")


def play(grid: List[List[str]], start: Pos, goal: Pos):
    """WASD でプレイする簡易ループ。"""
    player = start

    while True:
        clear_screen()
        print(render(grid, player, start, goal))
        print("\n操作: w/a/s/d で移動, q で終了")

        if player == goal:
            print("\n=== ゴール！おめでとう！ ===")
            return

        cmd = input("> ").strip().lower()
        if not cmd:
            continue
        if cmd[0] == "q":
            print("終了します。")
            return

        dx, dy = 0, 0
        if cmd[0] == "w":
            dy = -1
        elif cmd[0] == "s":
            dy = 1
        elif cmd[0] == "a":
            dx = -1
        elif cmd[0] == "d":
            dx = 1
        else:
            continue

        nxt = Pos(player.x + dx, player.y + dy)
        if grid[nxt.y][nxt.x] == PATH:
            player = nxt
        # 壁なら何もしない（そのまま）


def auto_solve(grid: List[List[str]], start: Pos, goal: Pos):
    """自動探索（BFS）で最短経路を表示する。"""
    path = bfs_shortest_path(grid, start, goal)
    clear_screen()
    if path is None:
        print("最短経路が見つかりませんでした（生成が変かも）。")
        print(render(grid, start, start, goal))
        return

    path_set = set(path)
    print(render(grid, start, start, goal, path=path_set))
    print(f"\n最短経路（長さ）: {len(path)-1} 手")
    print("'.' が最短経路です。")


def main():
    args = parse_args()
    w = ensure_odd(args.w)
    h = ensure_odd(args.h)

    rng = random.Random(args.seed)

    grid, start, goal = generate_maze(w, h, rng)

    if args.mode == "auto":
        auto_solve(grid, start, goal)
    else:
        play(grid, start, goal)


if __name__ == "__main__":
    main()

実行例

$python 20_maze_game.py --mode auto
###############################
#P#  ...#...#   #       #   # #
#.###.#.#.#.# # # ### # # # # #
#.....#...#.# # # # # # # # # #
###########.# # # # # # # # # #
#...  #.....# # #   # #   #   #
#.#.# #.##### # ### # #########
#.#.# #...#   #     #         #
#.#.#####.# ################# #
#.#.#.....# #           #...# #
#.#.#.##### ##### #######.#.# #
#.#...#   # #     #.......#...#
#.##### ### # ### #.#########.#
#.....#       # # #.#.......#.#
#####.######### # #.#.#####.#.#
#   #.#.....#     #.#.#   #...#
# # #.#.###.#######.#.### #####
# # #.#...#.....#...#.........#
# ###.###.#####.#.###########.#
#    .....#    ...#          G#
###############################

最短経路（長さ）: 142 手
'.' が最短経路です。

感想

• 自動回答は幅優先探索(BFS)で出している

【完】