소개

미로를 푸는 유명한 알고리즘 중 하나는 왼쪽 방법 (오른쪽 방법)입니다. 이것은 "왼손으로 항상 벽을 만져 계속 앞으로 나아가면 반드시 목표에 도달할 수 있다"는 생각에 근거합니다. 단순한 미로라면 골에 도착할 수 있습니다만, 스타트 지점이나 골 지점을 의지 나쁘거나 미로가 입체적으로 되거나 하면, 골에 도착하지 않는 경우가 있습니다. 보다 유용한 알고리즘은 다수 있습니다만, 이해와 구현이 간단하고, 그리드를 취급하는 입문에 적합한 소재라고 생각합니다.

이 기사에서는 왼손 기법을 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