左手法のアルゴリズムの可視化 (Python in Processing)

はじめに

迷路を解く有名なアルゴリズムの一つに，左手法(右手法)があります．これは，「左手で常に壁を触り続けて前に進めば，必ずゴールに到達できる」という考えに基づくものです．単純な迷路であればゴールにたどり着けますが，スタート地点やゴール地点を意地悪されたり，迷路が立体的になったりすると，ゴールにたどり着けない場合があります．より有用なアルゴリズムは多数ありますが，理解と実装が簡単で，グリッドを扱う入門に適した題材だと思います．

この記事では，左手法を Processing (Pythonモード) で実装し，動きを可視化します．簡単のためグローバル変数を多用していますが，本当はよくないです．

環境

• Processing 3.5.3
• Python Mode for Processing 3 3056

動画

実装

left_hand_method.pyde

# 解く対象のマップ
# 壁は1, 通路は0
# grid[y][x] でアクセス
grid = [
        [1, 1, 1, 1, 1, 1, 1],
        [1, 0, 1, 0, 0, 1, 1],
        [1, 0, 1, 1, 0, 0, 1],
        [1, 0, 0, 0, 1, 0, 1],
        [1, 0, 1, 0, 1, 0, 1],
        [1, 0, 1, 0, 0, 0, 1],
        [1, 1, 1, 1, 1, 1, 1]
]

# マス目の表示サイズ
S = 500 / 7

# 上下左右の相対座標 [←,↑,→,↓] の順
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

# ゴールの座標
goal_x, goal_y = 1, 5

# エージェントの座標と向き
px, py = 1, 1
p_dir = 0

# 定期実行するための変数たち
dt = 15
next_frame = dt * 3

def setup():
    frameRate(30)
    size(S * 7, S * 7)
    textSize(30)
    textAlign(CENTER, TOP)

def draw():
    background(255)
    draw_grid()
    draw_agent()
    
    # 定期的に左手法を1回実行
    global next_frame
    if next_frame < frameCount:
        left_hand_method()
        next_frame += dt

# 左手法のアルゴリズム
# 左隣に壁がある && 前に壁がある => 右回転
# 左隣に壁がある && 前に壁がない => 前進
# 左隣に壁がない => 左回転して前進
def left_hand_method():
    global px, py, p_dir

    # ゴール済み判定
    if (px, py) == (goal_x, goal_y):
        return

    # エージェントから見て左側の向きと座標
    left_dir = (p_dir + 4 - 1) % 4
    lx, ly = px + dx[left_dir], py + dy[left_dir]

    # 左に壁があるかどうか
    if grid[ly][lx] == 1:
        # 前に壁があるかどうか
        if grid[py + dy[p_dir]][px + dx[p_dir]] == 1:
            p_dir = (p_dir + 1) % 4
        else:
            px += dx[p_dir]
            py += dy[p_dir]
    else:
        p_dir = left_dir
        px, py = lx, ly


# --- 描画用の補助関数 ---

# マップの描画
def draw_grid():
    fill(0)
    for y in range(7):
        for x in range(7):
            if grid[y][x] == 1:
                rect(x * S, y * S, S, S)
    textHeight = textAscent() + textDescent()
    text("G", (goal_x + 0.5) * S, (goal_y + 0.5) * S - textHeight / 2)

# エージェントの描画
# 未ゴールは赤, ゴール済みは青
def draw_agent():
    if (px, py) == (goal_x, goal_y):
        fill(0, 0, 255)
    else:
        fill(255, 0, 0)
    pushMatrix()
    translate((px + 0.5) * S, (py + 0.5) * S)
    rotate(p_dir * HALF_PI)
    triangle(
        -S / 4, 0,
        S / 4, -S / 8,
        S / 4, S / 8
    )
    popMatrix()

参考

迷路 - Wikipedia