DFSの探索手順と歩数を可視化するプログラム

　ChatGPT に食わせたコードを微調整して $5$ 分でできたものを記事として公開していいのかという葛藤はありますが、普通に面白いものができたのに、一時ファイルとして消えさせるのは惜しいので、記事という形で公開します。

目的

　DFS（深さ優先探索、つまりいけるところまで直進する探索）の軌跡と歩数をアニメーションで観察したい。壁や初期位置による変化も見たい。

結果

ソースコード

import matplotlib.pyplot as plt
import matplotlib.animation as animation
import numpy as np

# DFS の移動方向（右, 下, 左, 上の順で時計回り）
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

# スタート位置 's' を見つける
def find_start(grid):
    for i, row in enumerate(grid):
        for j, cell in enumerate(row):
            if cell == 's':
                return i, j
    return None

# DFS のアルゴリズム
def dfs(grid, x, y, visited, path, images, step_count, darkness):
    if grid[x][y] == '#' or visited[x][y] > 0:
        return False
    
    # 現在のステップを記録
    visited[x][y] = step_count
    path.append((x, y))
    
    # 探索中のグリッドを保存
    current_position = (x,y)
    images.append(visualize_grid(grid, visited, darkness, current_position))
    
    # 時計回りに探索
    for dx, dy in directions:
        nx, ny = x + dx, y + dy
        if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and visited[nx][ny] == 0:
            if dfs(grid, nx, ny, visited, path, images, step_count + 1, darkness):
                return True
    
    # 後退時に探索済みを消さない（探索済みの記録は残す）
    path.pop()
    
    # 後退した状態のグリッドを保存
    images.append(visualize_grid(grid, visited, darkness, current_position))
    
    return False

# グリッドのビジュアライズ
def visualize_grid(grid, visited, darkness, current_position):
    max_step = np.max(visited)
    color_grid = np.zeros((len(grid), len(grid[0]), 3))
    
    for i, row in enumerate(grid):
        for j, cell in enumerate(row):
            if cell == '#':
                color_grid[i][j] = [0, 0, 0]  # 壁は黒
            elif visited[i][j] > 0:
                # 歩数に応じて暗くなる緑 (歩数が増えるほど暗くなる)
                darkness_factor = visited[i][j] / max_step if max_step > 0 else 1
                # color_grid[i][j] = [0, 1 - darkness_factor, 0]  # 緑から黒に近づく
                color_grid[i][j] = [0, 1 - visited[i][j]/50, 0]  # 緑から黒に近づく
            else:
                color_grid[i][j] = [1, 1, 1]  # 未探索は白

    # 現在位置を赤で表示
    if current_position:
        i, j = current_position
        color_grid[i][j] = [1, 0, 0]  # 赤で現在位置を表示
    
    return color_grid

# アニメーション作成
def create_animation(images):
    fig = plt.figure()
    
    def update(frame):
        plt.clf()
        plt.imshow(images[frame])
    
    ani = animation.FuncAnimation(fig, update, frames=len(images), interval=20)
    plt.show()

# メイン処理
def main(grid_str):
    # グリッドを2Dリストに変換
    grid = [list(row) for row in grid_str.strip().split('\n')]
    start = find_start(grid)
    
    if not start:
        print("スタート地点が見つかりません")
        return
    
    visited = np.zeros((len(grid), len(grid[0])), dtype=int)
    path = []
    images = []
    darkness = 1.0  # 初期の暗さ
    
    # DFS を実行
    dfs(grid, start[0], start[1], visited, path, images, 1, darkness)
    
    # アニメーションを作成して表示
    create_animation(images)

# グリッド例

grid_str = '''
.#....#
....#s.
..#..#.
...#...
...#...
.#.....
'''
print(grid_str)
main(grid_str)

使い方

　コード中の grid_str を編集すれば初期状態をいじれます。

感想

　昔だったら一日がかりだったと思いますが、爆速で出来てしまった……AI はおそろしい。