マイクロマウス：tkinterアニメーションで見せる，バックトラック
Python3(3.10)で動くソースコード（.pyファイル .ipynbファイル）あります
「anaconda3」on .py「PyCharm」.ipynb「Jupyter Notebook」
そのゴールを探している様子をアニメーションでお見せします。コンピュータによる試行が人間の思考のように見えます。
◆◆マイクロマウスクラシック◆◆
マイクロマウスクラシックの迷路は 16×16 のグリッドからできていて，終点は真ん中の4つのグリッドで，始点は四隅のいずれかであり時計回りに出発する。
詳細は競技会を主催している団体のWebサイトを参照してください。 http://www.ntf.or.jp/mouse/
『公益財団法人ニューテクノロジー振興財団』
詳細は競技会を主催している団体のWebサイトを参照してください。 http://www.ntf.or.jp/mouse/
『公益財団法人ニューテクノロジー振興財団』
（2023-11-14）Python3.10で動作確認済み
◆◆バックトラックに使われる再帰呼び出しとは◆◆
再帰呼び出し（recursive call）とは，次のようなものである。
・自分で自分を定義する
・自分が自分を呼び出す
簡単な例として階乗がある。次のように階乗を階乗で定義しているのである。
N ! = N×(N-1) !
これをプログラムすると，N ! を計算している途中で(N-1) ! の計算が始まることになる。単純にサブルーチンが自分を読んでしまうと計算途中のデータが破壊されてしまう。
これを解決するには，サブルーチンを再入可能（reentrant）な構造にすればよい。
再入可能な再帰呼び出しとバックトラックが実際にどのような構造になるのかはアルゴリズムの中で説明する。
◆◆バックトラック・アルゴリズム◆◆
１．イニシャライズする ２．ＣＡＬＬ ＳＵＢ（１番目のステップ） ３．ＥＮＤ ＳＵＢ（Ｎ番目のステップ） １．ＷＨＩＬＥ 方法がまだある Ａ．次の方法を探す Ｂ．ＩＦ その方法が可能なら ＴＨＥＮ １．その方法を実行する ２．ＩＦ ゴールに達したなら ＴＨＥＮ Ａ．解を出力する ３．ＥＬＳＥ Ａ．ＣＡＬＬ ＳＵＢ ４．その方法を取り消す ２．ＲＥＴＵＲＮ
命令文の簡単な説明は次である（特定の言語と関係ない）。
ＣＡＬＬ文はサブルーチンコールである。ＳＵＢは再入可能とする。ＷＨＩＬＥ文は，条件が満足すればループする（このプログラムではＲＥＴＵＲＮ文の前まで）。ＩＦ ＴＨＥＮ ＥＬＳＥ文は，条件が満足か否かにより分岐する。
下から３行目に再帰呼び出しがある。
再帰呼び出しするためには，再入可能でなければならない。
これを実現するために，もう少し詳細なアルゴリズムを説明する。
◆◆「マイクロマウス」の詳細アルゴリズム◆◆
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
Sub マイクロマウス
イニシャライズ
Gosub Mouse_Run
End Sub
Mouse_Run:
W=1
LoopStart:
If W=<3 Then
試行の計算
If Wが成功するなら Then
仮にマウスを進める
If マウス座標がゴール Then
解を出力
Else
Stackに保存する
Stack Pointer１増
Gosub Mouse_Run
次のステップがもうなく戻ってきた
次のWの準備
Goto LoopStart
Else
入ってきた方角に戻る
Stackがまだ残っていれば
Stack Pointer１減
Stackから戻す
Return
再帰的ＣＡＬＬ文は16～19行目で，再帰的ＲＥＴＵＲＮ文は23～27行目で実現している。ＷＨＩＬＥ文が終わるとＥＬＳＥ文が実行される。
７行目の変数 W は試行方法である。
「マイクロマウス」では，マスを出る方角である。戻り方角は含まれない。戻りはバックトラックで自動的に23行目で実施される。したがって，入った方向によって出る方角の順序は変わる。
ループの先頭で，ある方法を試行し，成功すればさらに再帰的に試行し，失敗すればその試行を破棄しループの先頭に戻る。これを繰り返すのである。
ある試行が成功しかつ問題全体が成功したら解を出力する。
実際のコードは巻末を見てください。
◆◆「マイクロマウス」の解◆◆
巻末の Python のソースコードをドラッグして PyScripter などの開発環境にコピペしてrunさせればよい。
○印はバックトラックの終りで斜めに走行したところである。経路リストの要素の追加と削除に改良の余地がある。
次項に最短経路を掲載してあるが，それに比べて遠回りしている感じだが，理由は2つある。
直進優先にしてあるが，迷路じしんが直進優先に不利になるように設定されているようだ。そして， バックトラックアルゴリズムを順守するため同じマスにバックトラック以外は入らないから戻りがさらに遠回りになる。
◆◆最短経路探索◆◆
このサイトに最短経路探索アルゴリズムを検証したWebがあります。
https://yamakatsusan.web.fc2.com/hp_software/python10.html
『マイクロマウスの迷路をPython3で解いた解答 最短経路探索A*（エイスター）アルゴリズムを検証した』
最短経路探索アルゴリズムが出した解は次の図です。
◆◆プログラミングの準備◆◆
◆◆描画プログラムに渡す壁コード◆◆
すべてのマスが独立に壁設定の情報を配列で持っています。
各方向の壁に対して2進数のビットを割り当てています。1, 2, 4, 8 が南，西，北，東になります。しかし，ビット演算はほとんどしていません。
◆◆描画プログラムに渡す壁の配列の自動生成◆◆
このWebの左上隅からソースファイルをダウンロードすると，壁の配列を自動生成してくれる「micromousesetting.xls」が付いています。
迷路の図のつくり方は簡単です。グリッドを選択ドラッグして，右クリックメニューのセルの書式設定 > 罫線タブ > 線幅を選択 > 線を描く位置を選択
複数グリッドを選択するには Ctrl を押しながら選択します。飛び飛びでも選択できますので，例えば，同じ「く」の字を選択するといっぺんに描くことができます。
全グリッドの全筋を描くには，全グリッドを選択してから「田」を入力します。
内側筋を使うときは正方4マスのときだけ判りやすいですが，その他はよく考えないと混乱するようです。
Python の配列を生成するには，起動時に現れるダイアログのボタンを押すだけです。"A1"セルに書かれているのでそのセルをコピーしてソースファイル「micromousesetting.py」の8行目の return 文の後に貼り付けてください。
Python では，カンマの後は改行してもよいことになっています。このときだけインデントをきれいに揃える必要はないです。
◆◆Tkinterによるアニメーション◆◆
描画プログラムはTkinterによるアニメーションを使っている。少々長いプログラムだが構造がしっかりしているので難しいところはない。
クラス Gboard が14行目で Tkinter.Canvasを継承している。19行目のコンストラクタも35行目で親コンストラクタを継承していて迷路を描いている。
この Canvas でマウスの移動を描くので，コンストラクタの27行目で探索プログラムからマウスの移動座標を受け取る。このクラスで重要な関数は，マウスの移動方向を決める102行目の関数 dir_steer() とマウスの位置を管理してマウスを描く124行目の関数 refresh() である。関数 refresh() はもう1つのクラスからアニメーションをつくるため繰り返し呼ばれている。
もう1つのクラス MouseGrid が145行目で Tkinter.Frameを継承している。Canvas の枠でありタイトルなどを設定する。
この Frame で「start」ボタンを設定して，そのボタンから関数 show_next() を呼び出す。そしてこの関数からマウスを描画する関数 refresh() を再帰的に呼び出す。
179行目からのプログラムはこのモジュールが起動されたとき自動的に走るプログラムであり，クラスで Tkinter を使っているときはこの決まり文句になる。
少々長いので複雑にみえるが，いろいろ応用しても決まった構造は変えないので理解しやすいと考える。
アニメーションのコマ送り間隔は，11行目で設定できる。1以上を設定すること。単位はミリ秒であるが「1」に設定しても描画のためかそれほど速くない。「250」くらいがほどよい。
◆◆壁設定プログラム◆◆
壁設定プログラムは壁配列を経路探索プログラムと描画プログラムに渡すだけである。壁配列は1マスごとに壁コードを持っていてマウスを移動方向を決めるのに便利な構造を持っている。
迷路の描画には1列ごとの壁位置コードの方が便利なのでそれに変換する関数も用意されている。
描画プログラムと別のモジュールになっているのは，迷路を変えることがあるからである。
◆◆ソースコード◆◆
このWebの左上隅からダウンロードできます。
ソースファイルは3つあります。
・micromouse.py；描画プログラム（メインプログラム：次の2つをインポートする）
・micromousesetting.py；壁設定プログラム（迷路の配列は8行目）
・micromouseBackTrack.py；経路探索プログラム（バックトラックアルゴリズム）
【おまけ】
迷路の壁を自由に設定できる「micromousesetting.xls」も付いてます。上の図の迷路は競技会主催団体のWebにあったものです。Excel の表に迷路を書けば自動的に Python の配列に変換できるように Excel VBA でプログラムしてあります。迷路の配列は"A1"セルに書き込まれます。壁設定プログラムにコピペしてください。
また別記事で紹介した迷路の文字壁を自動的につくることもできます。文字壁は"AA36"セルに書き込まれます。文字壁を使う経路探索プログラムにコピペしてください。
【micromouse.py】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182
# -*- coding: utf-8 -*-
"""
Micro Mouse
"""
import micromousesetting as St
import micromouseBackTrack as MM
import tkinter as Tk
No_grid = 16
THKwall = 4
Timer = 250 # ミリ秒；アニメーションのコマ送り間隔（1以上を設定）
class Gboard(Tk.Canvas):
"""Tk.Canvas for Mouse Grid
"""
grid_size = 25
def __init__(self, master):
"""コンストラクタ
"""
self.master = master
"""set initial value"""
endline = self.grid_size * (No_grid + 1)
z = self.grid_size * 0.36
"""read solution"""
path, visited, mouse_sol = MM.main_dungeon()
self.mouse_sol = mouse_sol
self.len_sol = len(mouse_sol)
print(self.mouse_sol) # debug
print(self.len_sol) # debug
"""親コンストラクタ"""
Tk.Canvas.__init__(self, master, relief=Tk.RAISED, bd=4, bg="#DDFFFF",
width=(No_grid+2)*self.grid_size,
height=(No_grid+2)*self.grid_size,
highlightthickness=0)
"""set initial value"""
self.No_step = 0 # マウスの歩行数
self.dir_next = 0 # 出る方向
"""drawing lines and coordinate"""
for i in range(No_grid+1):
x= (i + 1) * self.grid_size
"""グリッド細線を描く"""
"""drawing X axes"""
self.create_line(self.grid_size, x, endline, x, width = 1)
"""drawing y axes"""
self.create_line(x, self.grid_size, x, endline, width = 1)
"""drawing x coordinate"""
self.create_text(x, self.grid_size * (No_grid + 1) + z ,
text=str(i), justify=Tk.CENTER,
fill="#002010", font = ("Helvetica","6","normal"))
"""drawing y coordinate"""
self.create_text(self.grid_size - z, x, text=str(No_grid - i),
justify=Tk.RIGHT,
fill="#002010", font = ("Helvetica","6","normal"))
"""drawing x axes wall"""
for yg in range(No_grid):
ww = St.wall_x(yg)
y = (No_grid - yg + 1) * self.grid_size
for xg in range(No_grid):
if ww[xg] == 1:
self.create_line(self.grid_size * (xg + 1), y,
self.grid_size * (xg + 2), y,
width = THKwall)
self.create_line(self.grid_size, self.grid_size,
endline, self.grid_size, width = THKwall)
"""drawing y axes wall"""
for xg in range(No_grid):
ww = St.wall_y(xg)
x = (xg + 1) * self.grid_size
for yg in range(No_grid):
if ww[yg] == 1:
self.create_line(x, self.grid_size * (No_grid - yg),
x, self.grid_size * (No_grid - yg + 1),
width = THKwall)
self.create_line((No_grid+1) * self.grid_size, self.grid_size,
(No_grid+1) * self.grid_size, endline, width = THKwall)
"""コンストラクタ終"""
def put_a_mouse(self, xg, yg, dir):
"""draw a mouse
"""
xx = self.grid_size * (xg + 1.5)
yy = self.grid_size * (No_grid - yg + 0.5)
if dir == 1:
chr = '∨'
if dir == 2:
chr = '＜'
if dir == 4:
chr = '∧'
if dir == 8:
chr = '＞'
if dir == 0:
chr = '○'
self.delete(hex(xg) + hex(yg))
return self.create_text(
xx, yy, text = chr, justify=Tk.CENTER, fill="#000000",
font = ("MSゴシック","12","bold"), tag = hex(xg) + hex(yg))
def dir_steer(self, No_step):
"""出る方向を決定する
"""
"""一番最初は上方向"""
if No_step == 0:
return 4
"""今の座標と次の座標を比較して方向を選択"""
before = self.mouse_sol[No_step]
after = self.mouse_sol[No_step + 1]
if after[0] == before[0]:
if after[1] < before[1]:
return 1
else:
return 4
if after[1] == before[1]:
if after[0] < before[0]:
return 2
else:
return 8
return 0
def refresh(self, No_step):
"""マウスを指示どおりに動かす
経路探索アルゴリズムは１行目のdir_steer()関数に組み込むことができる
ここではマウスの軌跡を管理しているだけ
"""
if No_step == self.len_sol - 1:
return True
"""出る方向の指示を確認する"""
self.dir_next = self.dir_steer(No_step)
#print self.dir_next,
"""出るグリッドを描画"""
before = self.mouse_sol[No_step]
self.put_a_mouse(before[0], before[1], self.dir_next)
"""入るグリッドを描画"""
after = self.mouse_sol[No_step + 1]
self.put_a_mouse(after[0], after[1], self.dir_next)
return False
class MouseGrid(Tk.Frame):
""" Tk.Frame class of Mouse Grid """
def __init__(self, master=None):
"""コンストラクタ
creating mousegrid canvas
"""
"""親コンストラクタ"""
Tk.Frame.__init__(self, master, relief=Tk.FLAT, bd=2)
self.master.title("Micro Mouse")
"""title"""
l_title = Tk.Label(self, text='Micro Mouse',
font=('Times', '24', ('italic', 'bold')),
fg='#191970', bg='#E8B77D', width=12)
l_title.pack(padx=10, pady=10)
self.mousegrid = Gboard(self)
self.mousegrid.pack(padx=10,pady=10)
self.f_footer = Tk.Frame(self)
self.f_footer.pack()
self.a_button = Tk.Button(self.f_footer, text="start",
font = ("Times", 14), command = self.show_next)
self.a_button.pack(side=Tk.LEFT, padx=5,pady=5)
"""set initial value"""
self.No_step = 0
def show_next(self):
"""アニメーションのコマ送り
"""
sol = self.mousegrid.refresh(self.No_step)
if sol:
"""解発見"""
return
self.No_step += 1
self.after(Timer, self.show_next)
if __name__ == '__main__':
app = MouseGrid()
app.pack()
app.mainloop()
【micromouseBackTrack.py】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134
# -*- coding: utf-8 -*-
"""
micro mouse by backtrack
"""
import micromousesetting as St
dungeon = St.wall_setting()
init = [0, 0]
goal = [7, 7]
path = [tuple(init)]
pathtotal = [tuple(init)]
mouse_at = [[0 for i in range(16)] for j in range(16)]
mouse_at[0][0] = 1
way_to_dir = [[0 for i in range(16)] for j in range(16)]
way_to_dir[0][0] = 4
stackway = [0 for i in range(250)]
stackpointer = 1
def through_maze():
"""メインなサブルーチン
"""
global path, pathtotal, stackpointer, sol_pathtotal, sol_path
way = 1
while way < 4:
# while文中で今のマスから隣接マスに進める
# ここの座標
pos = list(path[-1])
# ３つの方法（方角）を試みる，４つめは戻りの方角
dir = get_dir(pos, way)
if mouse_can_go(pos, dir):
# 進むことができるなら仮に試みる
pos = mouse_has_gone(pos, dir)
path = path + [tuple(pos)]
pathtotal = pathtotal + [tuple(pos)]
if mouse_at[pos[0]][pos[1]] == 0:
# 未訪問，訪問済みにする
mouse_at[pos[0]][pos[1]] = 1
way_to_dir[pos[0]][pos[1]] = dir
if pos == goal:
# ゴールを発見
sol_pathtotal = pathtotal
sol_path = path
else:
# 次のステップに進める recursiveなcall
stackway[stackpointer] = way
stackpointer += 1
through_maze()
# 同じposで次のwayを試みる準備
way += 1
# while文の終了
else: # while文の終了後に実行
# recursiveなreturn
if stackpointer > 1:
stackpointer -= 1
way = stackway[stackpointer]
pathtotal.append(path.pop())
#return None
def get_dir(pos, ww):
"""最初（Way=1）に選ぶのは同じ方角，戻る方角は最後（Way=4）に選ぶ
"""
if way_to_dir[pos[0]][pos[1]] == 1:
if ww == 1:
return 1
if ww == 2:
return 2
if ww == 3:
return 8
if ww == 4:
return 4
if way_to_dir[pos[0]][pos[1]] == 2:
if ww == 1:
return 2
if ww == 2:
return 4
if ww == 3:
return 1
if ww == 4:
return 8
if way_to_dir[pos[0]][pos[1]] == 4:
if ww == 1:
return 4
if ww == 2:
return 8
if ww == 3:
return 2
if ww == 4:
return 1
if way_to_dir[pos[0]][pos[1]] == 8:
if ww == 1:
return 8
if ww == 2:
return 1
if ww == 3:
return 4
if ww == 4:
return 2
def mouse_can_go(pos, dir):
ww = dungeon[pos[0]][pos[1]]
if dir == 1 and ww & 1 != 1 and mouse_at[pos[0]][pos[1] - 1] == 0:
return True
if dir == 2 and ww & 2 != 2 and mouse_at[pos[0] - 1][pos[1]] == 0:
return True
if dir == 4 and ww & 4 != 4 and mouse_at[pos[0]][pos[1] + 1] == 0:
return True
if dir == 8 and ww & 8 != 8 and mouse_at[pos[0] + 1][pos[1]] == 0:
return True
return False
def mouse_has_gone(pos, dir):
if dir == 1:
pos[1] = pos[1] - 1
if dir == 2:
pos[0] = pos[0] - 1
if dir == 4:
pos[1] = pos[1] + 1
if dir == 8:
pos[0] = pos[0] + 1
return pos
def main_dungeon():
"""main program
"""
through_maze()
# 文字壁の探索プログラムのreturn文に合わせる
dummy =[]
return sol_path, dummy, sol_pathtotal
if __name__ == "__main__":
sol_path, dummy, sol_pathtotal = main_dungeon()
print(sol_path)
print(sol_pathtotal)
【micromousesetting.py】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
# -*- coding: utf-8 -*-
"""
micro mouse setting
"""
def wall_setting():
"""wall_setting
"""
return [
[11,2,6,7,7,7,3,10,10,10,6,3,10,2,10,6],
[3,12,1,0,0,0,4,11,2,10,12,5,3,8,6,5],
[9,6,5,13,13,13,9,6,9,2,10,12,5,3,12,5],
[3,12,9,10,10,10,6,9,6,13,3,6,5,9,6,5],
[9,6,3,10,10,10,8,14,9,10,12,9,12,3,12,5],
[3,8,4,11,2,10,10,10,10,10,10,10,10,8,6,5],
[5,7,1,6,5,3,2,2,14,11,2,10,2,14,5,5],
[5,1,12,5,5,5,5,1,6,3,12,3,8,6,5,5],
[5,5,3,12,5,5,5,9,12,9,6,9,2,12,5,5],
[5,5,9,6,5,5,5,11,2,6,5,3,8,6,5,5],
[5,5,3,8,4,5,1,6,5,1,12,9,2,12,5,5],
[1,0,8,2,12,1,12,9,4,5,3,6,9,6,5,5],
[5,5,3,12,11,8,10,10,8,4,5,9,6,9,4,5],
[9,8,12,3,6,3,10,10,10,12,9,6,9,6,5,5],
[3,10,10,12,9,8,10,10,10,10,10,8,14,9,4,5],
[9,10,10,10,10,10,10,10,10,10,10,10,10,10,8,12]]
def wall_code(x, y):
"""wall position of grid
"""
w = wall_setting()
return w[x][y]
def wall_x(y):
wall = [0 for i in range(16)]
w = wall_setting()
for i in range(16):
wall[i]= w[i][y] % 2
return wall
def wall_y(x):
wall = [0 for i in range(16)]
w = wall_setting()
for i in range(16):
wall[i]= int(bin(w[x][i]>>1),2) % 2
return wall
if __name__=='__main__':
print(wall_code(0,0), wall_code(15,15))
print(wall_x(0))
print(wall_x(1))
print(wall_x(2))
print(wall_x(3))
print(wall_y(0))
print(wall_y(1))
print(wall_y(2))
print(wall_y(3))