Python (パイソン) であそぼう 5
〜 プログラムで迷路を解く 〜
2022-09-09 作成 福島
TOP > asob > pygame-mazesolve
[ TIPS | TOYS | OTAKU | LINK | MOVIE | CGI | AvTitle | ConfuTerm | HIST | AnSt | Asob ]

自分で歩かせる

前章 Python であそぼう 4 のプログラムを変更して迷路の中を自動的に移動します。
「プログラミング的思考」の課題と似ています。

迷路を解くには様々なアルゴリズムがありますが、ここでは「場当たり式」と簡素かつ古典的な「右手法」(みぎてほう) で解いてみます。
「右手法」とは、右手で迷路の壁を離さないように前進する方法です。
同様に、「左手法」(ひだりてほう) もあり、こちらは左手で迷路の壁を離さないように前進する方法で、考え方は右手法と同じです。

「アルゴリズム」とは、考え方を「形」にしたものを指します。
その「形」と同じことを実施すれば、誰でも同じことが出来るものです。
「文書」「歯車」「方程式」「プログラム」「電子回路」等、様々な形式があります。
学校で習う科目にはありません。よく「算法」と訳されますが、多くの人はピンとこない事でしょう。

右手法を使うには一つ条件があります。それは、
· 壁が途切れていないこと。(独立した通路がないこと)
ということです。
どこか一か所でも独立した通路が存在すると、たどり着けない場所が出来てしまい、そこにゴールがあると迷路を解くことができません。

本稿では、右手法で作成したプログラムを改良し、右手法だけでは解けない迷路も解いてみます。

0. 事前準備

0-1. この章では、pygame を使います。
インストールがまだなら、ここ (Windows10) か ここ (CentOS) を参考にしてインストールしておいてください。

pygame と書いて「パイゲーム」と読みます。
Python を使ってゲームを作るためのパッケージのことです。
0-2. この章では、テキストエディタを使います。
Linux なら付属の「Vim」や「gedit」で十分です。
(Vim の初心者向け使い方はここにあります)

Windows なら「メモ帳」でも構いませんが、本格的なテキストエディタをお勧めします。
(強力なアンドゥや、キーマクロが使えるようになります)
インストールがまだなら、ここ (秀丸エディタ) を参考にしてインストールしておいてください。
また、プログラムを起動するには拡張子が重要となるので、エクスプローラーで拡張子が表示されるようにしておいてください。
0-3. 未経験者向けの情報を省いています。
プログラミング未経験の方は、予めこちら (Python であそぼう 1) を、
アニメーションの仕組みをまだ考えたことがない方は、こちら (Python であそぼう 2) を
学習しておくことを推奨します。

1. 前回 Python であそぼう 4 - 第 4 項 のおさらい

1-1. コントロールをクリアできるプログラム
<テキスト11> では以下の様に記述していました。
これを変更していきます。

<テキスト11> ファイル名「program.py」
import pygame

pygame.init()

screen = pygame.display.set_mode((320,240))
pgclock = pygame.time.Clock()

heya = [
"+---------------+",
"|     #       # |",
"| ### # # ### # |",
"| # #   #   # # |",
"| # ####### # # |",
"|     #     #   |",
"+---------------+",
]



# 部屋を表示する関数。
def HeyaDisplay(screen, heya, x, y):
    screen.fill((0,0,0))
    font = pygame.font.Font(None, 32)

    tate = 0
    for line in heya:
        yoko = 0
        for k in line:
            kabe = font.render(k, False, (255,255,255))
            screen.blit(kabe, [yoko*16,tate*32])
            yoko += 1
        tate += 1

    moji = font.render('A', False, (255,255,255))
    screen.blit(moji, [x*16,y*32])
    pygame.display.update()



# 周囲を調査する関数。
def Search(heya, cx, cy):
    ikeru = ' abc'
    idou = [ 0, 0, 0, 0 ]
    if heya[cy + 0][cx + 1] in ikeru: idou[0] = +1
    if heya[cy + 0][cx - 1] in ikeru: idou[1] = -1
    if heya[cy + 1][cx + 0] in ikeru: idou[2] = +1
    if heya[cy - 1][cx + 0] in ikeru: idou[3] = -1
    return idou



Controls = [
#      X, Y, Mark      コントロールの場所と記号
    [  1, 4, 'a' ],
    [  9, 5, 'b' ],
    [ 15, 1, 'c' ],
]

# コントロールを迷路に埋め込む。
for Mokuhyo in range(len(Controls)):
    mx, my, mm = Controls[Mokuhyo]
    heya[my] = heya[my][:mx] + mm + heya[my][mx+1:]

# 自分の横位置、縦位置
x, y = 1, 1

HeyaDisplay(screen, heya, x, y)

Mokuhyo = 0
mx, my, mm = Controls[Mokuhyo]

running = True
while running:
    pgclock.tick(10)

    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            running = False
        elif event.type == pygame.KEYDOWN:
            idou = Search(heya, x, y)
            dx, dy = 0, 0
            if   event.key == pygame.K_RIGHT: dx = idou[0]
            elif event.key == pygame.K_LEFT : dx = idou[1]
            elif event.key == pygame.K_DOWN : dy = idou[2]
            elif event.key == pygame.K_UP   : dy = idou[3]
            x += dx
            y += dy

    HeyaDisplay(screen, heya, x, y)

    if x == mx and y == my:
        if mm == 'c':
            running = False
        else:
            heya[my] = heya[my][:mx] + ' ' + heya[my][mx+1:]
            Mokuhyo += 1
            mx, my, mm = Controls[Mokuhyo]

2. 場当たり式の進行

2-1. 気まぐれに進むプログラムの作成。
深く考えずにとりあえず通路を直進し、曲がり角を見つけたらその場で適当に行き先を決める
という方法で迷路を解いてみます。
「乱数」を使って運任せに方向を変えているので、アルゴリズムとも呼べないほどの解決方法です。
(乱数は、Python にあらかじめ用意されている機能「random.randint(··)」を使います)

また、前項までは自分の位置を「A」として表示していましたが、これに向きを加えて表示するようにします。

曲がり角ではなく、交差点で行き先を決めたほうが効率が良いのですが、
ここではプログラムの簡便さを優先しました。
このプログラムを理解できた人は、交差点で行き先を決めるプログラムに改造してみてください。

<テキスト12> ファイル名「program.py」
import pygame

pygame.init()

screen = pygame.display.set_mode((320,240))
pgclock = pygame.time.Clock()

heya = [
"+---------------+",
"|     #       # |",
"| ### # # ### # |",
"| # #   #   # # |",
"| # ####### # # |",
"|     #     #   |",
"+---------------+",
]



# 部屋を表示する関数。
def HeyaDisplay(screen, heya, x, y, cc):
    screen.fill((0,0,0))
    font = pygame.font.Font(None, 32)

    tate = 0
    for line in heya:
        yoko = 0
        for k in line:
            kabe = font.render(k, False, (255,255,255))
            screen.blit(kabe, [yoko*16,tate*32])
            yoko += 1
        tate += 1

    moji = font.render(cc, False, (255,255,255))
    screen.blit(moji, [x*16,y*32])
    pygame.display.update()



# 周囲を調査する関数。
def Search(heya, cx, cy):
    ikeru = ' abc'
    idou = [ 0, 0, 0, 0 ]
    if heya[cy + 0][cx + 1] in ikeru: idou[0] = +1
    if heya[cy + 0][cx - 1] in ikeru: idou[1] = -1
    if heya[cy + 1][cx + 0] in ikeru: idou[2] = +1
    if heya[cy - 1][cx + 0] in ikeru: idou[3] = -1
    return idou



# 移動の可否を一人称視点の前後左右に変換する関数。
def GetFPV(dir, idou):
    henkan = (
        (3,0,1,2),
        (0,2,3,1),
        (2,1,0,3),
        (1,3,2,0),
    )
    return idou[henkan[dir][0]], \
            idou[henkan[dir][1]], \
            idou[henkan[dir][2]], \
            idou[henkan[dir][3]]



# 自動で歩かせる関数。
def HeadTurn(dir, fpv):
    mae    = fpv[0]
    migi   = fpv[1]
    hidari = fpv[2]
    ushiro = fpv[3]

    import random

    if   migi   != 0 and random.randint(0, 1) == 0:
        dir = (dir + 1) % 4
    elif hidari != 0 and random.randint(0, 1) == 0:
        dir = (dir + 3) % 4
    elif mae == 0:
        dir = (dir + 2) % 4

    return dir



Controls = [
#      X, Y, Mark      コントロールの場所と記号
    [  1, 4, 'a' ],
    [  9, 5, 'b' ],
    [ 15, 1, 'c' ],
]

# コントロールを迷路に埋め込む。
for Mokuhyo in range(len(Controls)):
    mx, my, mm = Controls[Mokuhyo]
    heya[my] = heya[my][:mx] + mm + heya[my][mx+1:]

# 自分の横位置、縦位置、方向
x, y, dir = 1, 1, 0 # 方向 0:↑ / 1:→ / 2:↓ / 3:←
myChr = 'A>V<'

HeyaDisplay(screen, heya, x, y, myChr[dir])

Mokuhyo = 0
mx, my, mm = Controls[Mokuhyo]

running = True
while running:
    pgclock.tick(10)

    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            running = False
        elif event.type == pygame.KEYDOWN:
            pass

    idou = Search(heya, x, y)
    fpv = GetFPV(dir, idou)
    dir = HeadTurn(dir, fpv)
    dx, dy = 0, 0
    if   dir == 1: dx = idou[0]
    elif dir == 3: dx = idou[1]
    elif dir == 2: dy = idou[2]
    elif dir == 0: dy = idou[3]
    x += dx
    y += dy

    HeyaDisplay(screen, heya, x, y, myChr[dir])

    if x == mx and y == my:
        if mm == 'c':
            running = False
        else:
            heya[my] = heya[my][:mx] + ' ' + heya[my][mx+1:]
            Mokuhyo += 1
            mx, my, mm = Controls[Mokuhyo]
2-2. 気まぐれに進むプログラムの実行

ゴールするまで 5 分以上かかるので、最後まで見るのは時間と心に余裕があるときに。
2-3. 気まぐれに進むプログラムの説明
<テキスト12> ファイル名「program.py」
import pygame

pygame.init()

screen = pygame.display.set_mode((320,240))
pgclock = pygame.time.Clock()

heya = [
"+---------------+",
"|     #       # |",
"| ### # # ### # |",
"| # #   #   # # |",
"| # ####### # # |",
"|     #     #   |",
"+---------------+",
]



# 部屋を表示する関数。
def HeyaDisplay(screen, heya, x, y, cc): # 自分の記号を呼び元で指定できるように変更。
    screen.fill((0,0,0))
    font = pygame.font.Font(None, 32)

    tate = 0
    for line in heya:
        yoko = 0
        for k in line:
            kabe = font.render(k, False, (255,255,255))
            screen.blit(kabe, [yoko*16,tate*32])
            yoko += 1
        tate += 1

    moji = font.render(cc, False, (255,255,255)) # 呼び元から指定された自分の記号を描画する。
    screen.blit(moji, [x*16,y*32])
    pygame.display.update()



# 周囲を調査する関数。
def Search(heya, cx, cy):
    ikeru = ' abc'
    idou = [ 0, 0, 0, 0 ]
    if heya[cy + 0][cx + 1] in ikeru: idou[0] = +1
    if heya[cy + 0][cx - 1] in ikeru: idou[1] = -1
    if heya[cy + 1][cx + 0] in ikeru: idou[2] = +1
    if heya[cy - 1][cx + 0] in ikeru: idou[3] = -1
    return idou



# 移動の可否を一人称視点の前後左右に変換する関数。
def GetFPV(dir, idou):
    # 部屋 → 自分視点の変換テーブル
    henkan = (
        (3,0,1,2),   # 上向きの場合: 前=-y, 右:+x, 左:-x, 後ろ=+y
        (0,2,3,1),   # 右向きの場合: 前=+x, 右:+y, 左:-y, 後ろ:-x
        (2,1,0,3),   # 下向きの場合: 前=+y, 右:-x, 左:+x, 後ろ:-y
        (1,3,2,0),   # 左向きの場合: 前=-x, 右:-y, 左:+y, 後ろ:+x
    )

    # 一人称視点に変換したゆか情報を呼び元へ返す。
    return idou[henkan[dir][0]], \  # 前方
            idou[henkan[dir][1]], \  # 右側
            idou[henkan[dir][2]], \  # 左側
            idou[henkan[dir][3]]     # 後方



# 自動で歩かせる関数。
# 現在の方向と前後左右のゆか情報を受け取り、新しい方向を返す。
def HeadTurn(dir, fpv):

    # 前後左右の情報を読みやすい変数に入れる。
    mae    = fpv[0]  # 前方
    migi   = fpv[1]  # 右側
    hidari = fpv[2]  # 左側
    ushiro = fpv[3]  # 後方 (今回は使用しない)

    import random    # 乱数の用意。

    if   migi   != 0 and random.randint(0, 1) == 0:
        # 右へ進むことができ、そちらへ行くと乱数で決めた場合。*1
        dir = (dir + 1) % 4  # 右を向く*2
    elif hidari != 0 and random.randint(0, 1) == 0:
        # 左へ進むことができ、そちらへ行くと乱数で決めた場合。*1
        dir = (dir + 3) % 4  # 左を向く*2
    elif mae == 0:
        # 右、左、前のどこへも進むことができない場合。
        dir = (dir + 2) % 4  # 後ろを向く

    return dir   # 新しく決めた方向を呼び元へ返す。



Controls = [
#      X, Y, Mark      コントロールの場所と記号
    [  1, 4, 'a' ],
    [  9, 5, 'b' ],
    [ 15, 1, 'c' ],
]

# コントロールを迷路に埋め込む。
for Mokuhyo in range(len(Controls)):
    mx, my, mm = Controls[Mokuhyo]
    heya[my] = heya[my][:mx] + mm + heya[my][mx+1:]

# 自分の横位置、縦位置、方向
# 最初に自分が向いている方向を決めておく。前後左右、どの方向でも構わない。
# 数字が増えるにしたがって時計回りに割り振るものとし、上向きを 0 としている。
x, y, dir = 1, 1, 0 # 方向 0:↑ / 1:→ / 2:↓ / 3:←

# 自分の向きを表示するための記号。
myChr = 'A>V<'

HeyaDisplay(screen, heya, x, y, myChr[dir])  # 自分の向きも指定する。

Mokuhyo = 0
mx, my, mm = Controls[Mokuhyo]

running = True
while running:
    pgclock.tick(10)

    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            running = False
        elif event.type == pygame.KEYDOWN:
            pass # キーで移動するのをやめる。

    idou = Search(heya, x, y)
    fpv = GetFPV(dir, idou)   # ゆか状況を自分視点の前後左右に変換する。
    dir = HeadTurn(dir, fpv)  # 進路を変更する。
    dx, dy = 0, 0
    if   dir == 1: dx = idou[0]   # 右向きなら dx に +1 (または 0) を入れる。
    elif dir == 3: dx = idou[1]   # 左向きなら dx に -1 (または 0) を入れる。
    elif dir == 2: dy = idou[2]   # 下向きなら dy に +1 (または 0) を入れる。
    elif dir == 0: dy = idou[3]   # 上向きなら dy に -1 (または 0) を入れる。
    x += dx
    y += dy

    HeyaDisplay(screen, heya, x, y, myChr[dir])  # 自分の向きも指定する。

    if x == mx and y == my:
        if mm == 'c':
            running = False
        else:
            heya[my] = heya[my][:mx] + ' ' + heya[my][mx+1:]
            Mokuhyo += 1
            mx, my, mm = Controls[Mokuhyo]
*1 このやり方には左よりも右を優先するという偏りがあります。
*2「右を向く」「左を向く」について
どうして 1 や 3 を加算するだけで右向きや左向きが実現できるかというと、
方向を 0 から 1, 2, 3 と時計回りに割り振った数値にして、演算子「%」で計算していることに意味があります。
(「a % b」は a を b で割った余りを求める計算式)

例えば、方向が 0 のときの右は 1 で、左は 3 なので、
Case-A. 前が上 (dir = 0) のとき。
  0 + 1 = 1 → 右
0 + 3 = 3 → 左		    
0
前
 3 左 ↑ 右 1 
後
2  
となることが分かると思います。

同様に、方向が 1 のときの右は 2 で、左は 0 なので、
Case-B. 前が右 (dir = 1) のとき。
  1 + 1 = 2 → 右
1 + 3 = 4 → 左 (?)		    
0
左
 3 後 → 前 1 
右
2
  
となります。
(Case-A, Case-B どちらも +1 で右向き、+3 で左向きになる)

重要なのは演算子「%」によって、あまりの計算をすることで、これにより Case-B の (?) は、
1 + 3 = 4 ,
4 % 4 = 0 → 左
(4 を 4 で割ったあまりは 0)
とすることが出来ます。

時計の針と同じ理屈です。(以下は長針の例)
· 長針の場合は、右向き: +15 分, 左向き: +45 分。
変更前の長針加える時間変更後の長針
0 分 +15 分15 分
+45 分45 分
15 分 +15 分30 分
+45 分0 分
30 分 +15 分45 分
+45 分15 分
45 分 +15 分0 分
+45 分30 分

3. 分割したプログラム

3-1. プログラムを分割する。
プログラムが長くなったせいで、全体の見通しが悪くなってきました。

Python には、別ファイルのプログラムを取り込む機能があります。
その機能 (すでに使っている import という命令) を利用してプログラムを 2 つのファイル
  • program.py
  • lib.py
に分割します。
(もっとたくさん分割することもできますが、細分化すると管理の労力が増えるので、ここでは 2 つにします。

プログラムを分割するにはコツがあって、それは
·変更の少ないプログラムをまとめて別ファイルにする。
というものです。
(専門的には「疎結合の関数群をライブラリ化する」と表現します)

<テキスト13> ファイル名「program.py」
プログラムを分割しただけなので、内容に変化はありません。
Python では、別ファイルの関数を使用するときに、そのファイル名 (モジュール名と言います) を明示する必要があり、
このことにより、異なる役割の同じ関数名を別ファイルで宣言することが可能になっています。
import pygame
import lib   # lib.py を取り込む。

pygame.init()

screen = pygame.display.set_mode((320,240))
pgclock = pygame.time.Clock()

heya = [
"+---------------+",
"|     #       # |",
"| ### # # ### # |",
"| # #   #   # # |",
"| # ####### # # |",
"|     #     #   |",
"+---------------+",
]



## ここにあった関数を「lib.py」として別ファイルに切り出した ##



# 自動で歩かせる関数。
def HeadTurn(dir, fpv):
    mae    = fpv[0]
    migi   = fpv[1]
    hidari = fpv[2]
    ushiro = fpv[3]

    import random

    if   migi   != 0 and random.randint(0, 1) == 0:
        dir = (dir + 1) % 4
    elif hidari != 0 and random.randint(0, 1) == 0:
        dir = (dir + 3) % 4
    elif mae == 0:
        dir = (dir + 2) % 4

    return dir



Controls = [
#      X, Y, Mark      コントロールの場所と記号
    [  1, 4, 'a' ],
    [  9, 5, 'b' ],
    [ 15, 1, 'c' ],
]

# コントロールを迷路に埋め込む。
for Mokuhyo in range(len(Controls)):
    mx, my, mm = Controls[Mokuhyo]
    heya[my] = heya[my][:mx] + mm + heya[my][mx+1:]

# 自分の横位置、縦位置、方向
x, y, dir = 1, 1, 0 # 方向 0:↑ / 1:→ / 2:↓ / 3:←
myChr = 'A>V<'

lib.HeyaDisplay(screen, heya, x, y, myChr[dir])  # lib.*** で関数が lib にあることを明示している。

Mokuhyo = 0
mx, my, mm = Controls[Mokuhyo]

running = True
while running:
    pgclock.tick(10)

    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            running = False

    idou = lib.Search(heya, x, y)    # lib.*** で関数が lib にあることを明示している。
    fpv = lib.GetFPV(dir, idou)      # lib.*** で関数が lib にあることを明示している。
    dir = HeadTurn(dir, fpv)
    dx, dy = 0, 0
    if   dir == 1: dx = idou[0]
    elif dir == 3: dx = idou[1]
    elif dir == 2: dy = idou[2]
    elif dir == 0: dy = idou[3]
    x += dx
    y += dy

    lib.HeyaDisplay(screen, heya, x, y, myChr[dir])  # lib.*** で関数が lib にあることを明示している。

    if x == mx and y == my:
        if mm == 'c':
            running = False
        else:
            heya[my] = heya[my][:mx] + ' ' + heya[my][mx+1:]
            Mokuhyo += 1
            mx, my, mm = Controls[Mokuhyo]

<テキスト14> ファイル名「lib.py」(エル・アイ・ビー・ドット・ピー・ワイ)
・「program.py」と同じディレクトリに置くこと。 
import pygame    # HeyaDisplay() で使用するため pygame を取り込む。

# 部屋を表示する関数。
def HeyaDisplay(screen, heya, x, y, cc):
    screen.fill((0,0,0))
    font = pygame.font.Font(None, 32)

    tate = 0
    for line in heya:
        yoko = 0
        for k in line:
            kabe = font.render(k, False, (255,255,255))
            screen.blit(kabe, [yoko*16,tate*32])
            yoko += 1
        tate += 1

    moji = font.render(cc, False, (255,255,255))
    screen.blit(moji, [x*16,y*32])
    pygame.display.update()



# 周囲を調査する関数。
def Search(heya, cx, cy):
    ikeru = ' abc'
    idou = [ 0, 0, 0, 0 ]
    if heya[cy + 0][cx + 1] in ikeru: idou[0] = +1
    if heya[cy + 0][cx - 1] in ikeru: idou[1] = -1
    if heya[cy + 1][cx + 0] in ikeru: idou[2] = +1
    if heya[cy - 1][cx + 0] in ikeru: idou[3] = -1
    return idou



# 移動の可否を一人称視点の前後左右に変換する関数。
def GetFPV(dir, idou):
    henkan = (
        (3,0,1,2),
        (0,2,3,1),
        (2,1,0,3),
        (1,3,2,0),
    )
    return idou[henkan[dir][0]], \
           idou[henkan[dir][1]], \
           idou[henkan[dir][2]], \
           idou[henkan[dir][3]]

4. 高度なアルゴリズム

「2. 場当たり式の進行」では進行方向を乱数で決めていたので、かなりもどかしい動作をしていたと思います。
それなりに面白い動きでしたが、本稿の冒頭で紹介した解法を実装します。

4-1. 右手法によるプログラムの作成
<テキスト15> ファイル名「program.py」
import pygame
import lib

pygame.init()

screen = pygame.display.set_mode((320,240))
pgclock = pygame.time.Clock()

heya = [
"+---------------+",
"|     #       # |",
"| ### # # ### # |",
"| # #   #   # # |",
"| # ####### # # |",
"|     #     #   |",
"+---------------+",
]

# 自動で歩かせる関数。
def HeadTurn(dir, fpv):
    mae    = fpv[0]
    migi   = fpv[1]
    hidari = fpv[2]
    ushiro = fpv[3]

    #import random

    if migi == 0:
        if mae == 0: dir = (dir + 3) % 4
    else:
        dir = (dir + 1) % 4

    return dir



Controls = [
#      X, Y, Mark      コントロールの場所と記号
    [  1, 4, 'a' ],
    [  9, 5, 'b' ],
    [ 15, 1, 'c' ],
]

# コントロールを迷路に埋め込む。
for Mokuhyo in range(len(Controls)):
    mx, my, mm = Controls[Mokuhyo]
    heya[my] = heya[my][:mx] + mm + heya[my][mx+1:]

# 自分の横位置、縦位置、方向
x, y, dir = 1, 1, 0 # 方向 0:↑ / 1:→ / 2:↓ / 3:←
myChr = 'A>V<'

lib.HeyaDisplay(screen, heya, x, y, myChr[dir])

Mokuhyo = 0
mx, my, mm = Controls[Mokuhyo]

running = True
while running:
    pgclock.tick(10)

    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            running = False

    idou = lib.Search(heya, x, y)
    fpv = lib.GetFPV(dir, idou)
    dir = HeadTurn(dir, fpv)
    dx, dy = 0, 0
    if   dir == 1: dx = idou[0]
    elif dir == 3: dx = idou[1]
    elif dir == 2: dy = idou[2]
    elif dir == 0: dy = idou[3]
    x += dx
    y += dy

    lib.HeyaDisplay(screen, heya, x, y, myChr[dir])

    if x == mx and y == my:
        if mm == 'c':
            running = False
        else:
            heya[my] = heya[my][:mx] + ' ' + heya[my][mx+1:]
            Mokuhyo += 1
            mx, my, mm = Controls[Mokuhyo]
import lib は前述の<テキスト14>を取り込んでいます。
lib.py を program.py と同じディレクトリに置いてください。
4-2. 右手法によるプログラムの実行

右側の壁に沿って進んでいることが分かると思います。
4-3. 右手法によるプログラムの説明
<テキスト15> ファイル名「program.py」
import pygame
import lib

pygame.init()

screen = pygame.display.set_mode((320,240))
pgclock = pygame.time.Clock()

heya = [
"+---------------+",
"|     #       # |",
"| ### # # ### # |",
"| # #   #   # # |",
"| # ####### # # |",
"|     #     #   |",
"+---------------+",
]

# 自動で歩かせる関数。
def HeadTurn(dir, fpv):
    mae    = fpv[0]
    migi   = fpv[1]
    hidari = fpv[2]
    ushiro = fpv[3]

    #import random    # 前段で使用した乱数モジュールは使用しない。

    if migi == 0:
        # 右側に壁がある*3
        if mae == 0: dir = (dir + 3) % 4 # 前にも壁があるので左を向く*4
    else:
        # 右側に壁がない*5
        dir = (dir + 1) % 4  # 右を向く

    return dir



Controls = [
#      X, Y, Mark      コントロールの場所と記号
    [  1, 4, 'a' ],
    [  9, 5, 'b' ],
    [ 15, 1, 'c' ],
]

# コントロールを迷路に埋め込む。
for Mokuhyo in range(len(Controls)):
    mx, my, mm = Controls[Mokuhyo]
    heya[my] = heya[my][:mx] + mm + heya[my][mx+1:]

# 自分の横位置、縦位置、方向
x, y, dir = 1, 1, 0 # 方向 0:↑ / 1:→ / 2:↓ / 3:←
myChr = 'A>V<'

lib.HeyaDisplay(screen, heya, x, y, myChr[dir])

Mokuhyo = 0
mx, my, mm = Controls[Mokuhyo]

running = True
while running:
    pgclock.tick(10)

    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            running = False

    idou = lib.Search(heya, x, y)
    fpv = lib.GetFPV(dir, idou)
    dir = HeadTurn(dir, fpv)
    dx, dy = 0, 0
    if   dir == 1: dx = idou[0]
    elif dir == 3: dx = idou[1]
    elif dir == 2: dy = idou[2]
    elif dir == 0: dy = idou[3]
    x += dx
    y += dy

    lib.HeyaDisplay(screen, heya, x, y, myChr[dir])

    if x == mx and y == my:
        if mm == 'c':
            running = False
        else:
            heya[my] = heya[my][:mx] + ' ' + heya[my][mx+1:]
            Mokuhyo += 1
            mx, my, mm = Controls[Mokuhyo]
*3 *4 *5 は、それぞれ以下の場合を想定しています。
また、行き止まりの場合でも後ろへ向かうことが出来ます。
 *3 右に壁がある場合。→ 進行方向はそのまま前へ。
壁⇑
こっち
  ↑壁
  

右へ曲がることは出来ないが、前に進むことが出来る。

 *4 右と前に壁がある場合。→ 進行方向は左へ。
壁壁
⇐
こっち		↑壁
  

右へ曲がることは出来ない。前に進むこともできない。

 *5 右に壁がない場合。→ 進行方向は右へ。
壁壁
  ↑⇒
こっち
  

右へ曲がることが出来る。

行き止まりの場合。→ 進行方向は後ろへ。(左向きを 2 回)
自動的に *4 を一度行うことになり、そのあと左へ進めるようになる。
壁壁
壁↑壁
  
  ⇒ 
壁壁
壁←壁
 こっち
⇓		 

5. 別ルートも探索するアルゴリズム

冒頭で述べたように、右手法には独立した通路にゴールがあると、そこへたどり着けないという欠点があります。
これを補うため、「右手法によるプログラム」を改良して、右手法だけでは行けない通路へも進行できるようにします。

5-1. 別ルートも探索するプログラムの作成
<テキスト16>ファイル名「program.py」
import pygame
import lib

pygame.init()

screen = pygame.display.set_mode((320,240))
pgclock = pygame.time.Clock()

heya = [
"+---------------+",
"|     #       # |",
"| ### # # ### # |",
"| #     #   # # |",  # 左から 2 番目の # を ' ' に変更する。
"| # ####### # # |",
"|     #     #   |",
"+---------------+",
]



# 自動で歩かせる関数。
def HeadTurn(dir, fpv):
    mae    = fpv[0]
    migi   = fpv[1]
    hidari = fpv[2]
    ushiro = fpv[3]

    otherDir = -1

    if migi == 0:
        if mae != 0:
            if hidari != 0: otherDir = (dir + 3) % 4
        else:
            dir = (dir + 3) % 4
    else:
        if mae != 0:
            otherDir = dir
        elif hidari != 0:
            otherDir = (dir + 3) % 4
        dir = (dir + 1) % 4

    return dir, otherDir



bunkiSpots = []

def BunkiAdd(dir, x, y):
    global bunkiSpots
    bunkiSpots.append([dir, x, y])

def BunkiDel(turnPoint):
    global bunkiSpots
    bunkiSpots = bunkiSpots[:turnPoint] + bunkiSpots[turnPoint + 1:]

def BunkiSearch(x, y):

    turnPoint = -1

    global bunkiSpots
    index = range(len(bunkiSpots))

    for i in reversed(index):
        if bunkiSpots[i][1:3] == [x, y]:
            turnPoint = i
            break

    return turnPoint



Controls = [
#      X, Y, Mark      コントロールの場所と記号
    [  1, 4, 'a' ],
    [  9, 5, 'b' ],
    [ 15, 1, 'c' ],
]

# コントロールを迷路に埋め込む。
for Mokuhyo in range(len(Controls)):
    mx, my, mm = Controls[Mokuhyo]
    heya[my] = heya[my][:mx] + mm + heya[my][mx+1:]

# 自分の横位置、縦位置、方向
x, y, dir = 1, 1, 0 # 方向 0:↑ / 1:→ / 2:↓ / 3:←
myChr = 'A>V<'

lib.HeyaDisplay(screen, heya, x, y, myChr[dir])

Mokuhyo = 0
mx, my, mm = Controls[Mokuhyo]

running = True
while running:
    pgclock.tick(10)

    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            running = False

    idou = lib.Search(heya, x, y)

    turnPoint = BunkiSearch(x, y)
    if turnPoint >= 0:
        newDir = bunkiSpots[turnPoint][0]
        BunkiDel(turnPoint)
        if newDir == (dir + 2) % 4:
            pass
        else:
            dir = newDir
    else:
        fpv = lib.GetFPV(dir, idou)
        dir, otherDir = HeadTurn(dir, fpv)
        if otherDir != -1: BunkiAdd(otherDir, x, y)

    dx, dy = 0, 0
    if   dir == 1: dx = idou[0]
    elif dir == 3: dx = idou[1]
    elif dir == 2: dy = idou[2]
    elif dir == 0: dy = idou[3]
    x += dx
    y += dy

    lib.HeyaDisplay(screen, heya, x, y, myChr[dir])

    if x == mx and y == my:
        if mm == 'c':
            running = False
        else:
            heya[my] = heya[my][:mx] + ' ' + heya[my][mx+1:]
            Mokuhyo += 1
            mx, my, mm = Controls[Mokuhyo]
5-2. 別ルートも探索するプログラムの実行

5-3. 別ルートも探索するプログラムの説明
<テキスト16>ファイル名「program.py」
import pygame
import lib

pygame.init()

screen = pygame.display.set_mode((320,240))
pgclock = pygame.time.Clock()

heya = [
"+---------------+",
"|     #       # |",
"| ### # # ### # |",
"| #     #   # # |",  # 左から 2 番目の # を ' ' に変更する。
"| # ####### # # |",
"|     #     #   |",
"+---------------+",
]



# 自動で歩かせる関数。
def HeadTurn(dir, fpv):
    mae    = fpv[0]
    migi   = fpv[1]
    hidari = fpv[2]
    ushiro = fpv[3]

    otherDir = -1    # 他通路への選択肢は発見するまで「無し」にしておく。

    if migi == 0:
        # 右側に壁がある
        if mae != 0:
            # 前側に壁がない → 向きはそのまま。
            if hidari != 0: otherDir = (dir + 3) % 4 # 左へも行けることを発見。選択肢を残す。
        else:
            # 右、前ともに壁があるので左を向く。
            dir = (dir + 3) % 4
    else:
        # 右側に壁がない → 右を向く。
        if mae != 0:
            # 前側に壁がない。
            otherDir = dir   # 前へも行けることを発見。選択肢を残す。
        elif hidari != 0:
            # 前側に壁があるが、左側にはない。
            otherDir = (dir + 3) % 4 # 左へも行けることを発見。選択肢を残す。
        dir = (dir + 1) % 4 # 右を向く。

    return dir, otherDir # 新しい方向とともに、他の選択肢も関数の呼び元に返す。



bunkiSpots = []  # 履歴格納用リストの用意

# 選択しなかった他通路をひとつ履歴用リストに追加する関数。
def BunkiAdd(dir, x, y):
    global bunkiSpots    # 関数の外側の変数を使うため、キーワード「global」を使う。
    bunkiSpots.append([dir, x, y])  # 方向、横位置、縦位置をリストにして履歴用リストに追加する。

# 他通路の履歴をひとつ履歴用リストから削除する関数。
def BunkiDel(turnPoint):
    global bunkiSpots    # 関数の外側の変数を使うため、キーワード「global」を使う。

    # 指定位置以外のデータで履歴用リストを再構築する。
    bunkiSpots = bunkiSpots[:turnPoint] + bunkiSpots[turnPoint + 1:]

# 履歴用リストに現在位置のデータがあるか検索する関数。
# データがあれば、その位置 (添え字) を返す。無ければ -1 を返す。
def BunkiSearch(x, y):

    turnPoint = -1   # 履歴の位置をデータが無い時の値で初期化しておく。

    global bunkiSpots    # 関数の外側の変数を使うため、キーワード「global」を使う。
    index = range(len(bunkiSpots))   # 履歴の添え字をすべて用意する。

    # 履歴を最新から古いものへ検索する。
    for i in reversed(index):    # すべての添え字を逆順に使う。(reversed() を使用)
        if bunkiSpots[i][1:3] == [x, y]:
            # 現在位置に合致するデータが存在する。
            # 履歴の位置を覚えてループから抜け出す。
            turnPoint = i
            break

    return turnPoint # 履歴の位置を関数の呼び元へ返す。



Controls = [
#      X, Y, Mark      コントロールの場所と記号
    [  1, 4, 'a' ],
    [  9, 5, 'b' ],
    [ 15, 1, 'c' ],
]

# コントロールを迷路に埋め込む。
for Mokuhyo in range(len(Controls)):
    mx, my, mm = Controls[Mokuhyo]
    heya[my] = heya[my][:mx] + mm + heya[my][mx+1:]

# 自分の横位置、縦位置、方向
x, y, dir = 1, 1, 0 # 方向 0:↑ / 1:→ / 2:↓ / 3:←
myChr = 'A>V<'

lib.HeyaDisplay(screen, heya, x, y, myChr[dir])

Mokuhyo = 0
mx, my, mm = Controls[Mokuhyo]

running = True
while running:
    pgclock.tick(10)

    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            running = False

    idou = lib.Search(heya, x, y)

    # 過去の分岐点から現在位置と同じものを探す。
    turnPoint = BunkiSearch(x, y)
    if turnPoint >= 0:
        # 現在位置と同じものがあった。
        # 過去の分岐点を回収して回頭する。
        newDir = bunkiSpots[turnPoint][0]    # 選択しなかった方向を履歴から取得する。
        BunkiDel(turnPoint)  # 方向を取得したので履歴から削除する。
        if newDir == (dir + 2) % 4:
            pass # 取得した方向が結果的に後ろ向きなら無視する。
        else:
            dir = newDir # 取得した向きへ回頭する。
    else:
        # 普通に回頭する。
        fpv = lib.GetFPV(dir, idou)
        dir, otherDir = HeadTurn(dir, fpv)  # ほかにも行けるゆかがあれば、
                                             # otherDir に -1 以外の方向 (0 ～ 3) が入る。

        # 向きを変える選択肢が他にもあったら履歴に追加する。
        if otherDir != -1: BunkiAdd(otherDir, x, y)

    dx, dy = 0, 0
    if   dir == 1: dx = idou[0]
    elif dir == 3: dx = idou[1]
    elif dir == 2: dy = idou[2]
    elif dir == 0: dy = idou[3]
    x += dx
    y += dy

    lib.HeyaDisplay(screen, heya, x, y, myChr[dir])

    if x == mx and y == my:
        if mm == 'c':
            running = False
        else:
            heya[my] = heya[my][:mx] + ' ' + heya[my][mx+1:]
            Mokuhyo += 1
            mx, my, mm = Controls[Mokuhyo]
履歴用リストについて (選択しなかった方向の履歴)
曲がり角において、自分が選択した進行方向と別の進行可能方向があった場合、
その別の進行可能方向を縦位置、横位置とともに履歴用リストに格納 (追加) し、
再度その位置を訪れたら、格納されていた進行可能方向を採用する。
という方法を採っています。
ただし、その進行可能方向が結果的に後ろを指し示した場合は無視します。
(無視しないと、必要ないところで引き返してしまう)

<テキスト16> では、これを 3 つの関数で実装しています。
  1. BunkiAdd - 履歴にデータを追加する。
    [1] 方向, 横, 縦 [2] 方向, 横, 縦
    		 (追加)← 
    方向, 横, 縦

  2. BunkiDel - 履歴から指定位置のデータを削除する。
    [1] 方向, 横, 縦 [2] 方向, 横, 縦 [3] 方向, 横, 縦
    		 (削除)→ 
    [2] 方向, 横, 縦

  3. BunkiSearch - 履歴から合致する位置を検索する。
    [1] 方向, 横, 縦 [2] 方向, 横, 縦 [3] 方向, 横, 縦
    		 (検索結果)→ 
    2
末尾にデータを追加し、末尾からデータを取り出す方式を LIFO (Last In First Out) やスタックと呼称します。
当プログラムでは、LIFO を改造したデータ構造を取り入れています。
(純粋な LIFO にすると、ループ状の通路に複数の分岐点があった場合にうまく動かない)
この章は、ここで終了です。