マイクロマウス：tkinterアニメーションで見せる
探索回数が少ない最短経路探索A*（A-Star，エースター）アルゴリズム
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で動作確認済み
◆◆最短経路探索 A*（エースター）アルゴリズム◆◆
迷路の経路探索アルゴリズムは10種類ほどあるそうで詳細は次のWebを参照してください。下の迷路のリストの中で最良優先探索（best-first search）が「10種類の中でも特に探索回数が少なくて済むアルゴリズム」らしい。最良優先探索はいくつか種類があるらしいが最も有名なのが A*（エースター）アルゴリズムである。次に有名なダイクストラアルゴリズムは A*アルゴリズムに含まれています。
http://gigazine.net/news/20150619-search-algorithm-visualize/
『探索アルゴリズムを視覚的に楽しむ「迷路で眺める探索アルゴリズム」』
上のWebで検証しているアルゴリズムは，
・深さ優先（depth-first）
・幅優先（breadth-first）
・反復深化深さ優先（iterative deepening）
・山登り法（hill climbing）
・最良優先（best-first）
・間違い優先（limited discrepancy）
・幅優先ビーム（breadth-first beam）
・最良優先ビーム（best-first beam）
・優良優先（good-first）
・二重制限（double limit）
迷路に A*アルゴリズムを適用しソースコードを公開しているのは少ない。次の3つのWebを紹介する。
http://d.hatena.ne.jp/pashango_p/20090713/1247455609
『PythonでA(A-Star)アルゴリズム - Pashango’s Blog』
http://d.hatena.ne.jp/bellbind/20090715/1247656342
『自分ならこう書く - pythonでA - ラシウラ』
http://qiita.com/masashi0127/items/0c794e28f4b295ad82c6
『Aアルゴリズム（Python編） - Qiita』
実はこの3つのWebはお互いに参照していて迷路が同じものなのである。知的財産権の問題がない範囲で参考にすることはプログラミングの世界では奨励される。
ラシウラ氏はA*アルゴリズムのソースコードを「特定の実装に依存しない汎用的な関数にし」ているので私はそれをアレンジして使わせていただくことにした。
このプログラムが出した最短経路が次である。
同じ迷路をバックトラックアルゴリズムで解いたものが次のWebです。
https://yamakatsusan.web.fc2.com/hp_software/python07.html
『「マイクロマウス」の迷路をPythonで解いた解答 Tkinterによるアニメーション』
◆◆経路探索プログラムの解答結果◆◆
訪問済みのマスの訪問順序をみてみよう。
番号を詳細に追ってゆけば判るが，探索された経路のコストが最小のものの先を探索することを続けている。つまり，最小コストの経路はめまぐるしく変わるので不連続になる。それでも A*アルゴリズムはその探索回数がかなり少ない方なのだそうだ。
実は足立法を研究してて判ったことは，足立法と A*アルゴリズムはコストの計算方法が違うだけでコスト予測値や探索アルゴリズムがほとんど同じである。ただ最小コスト経路が不連続のところでマウスをどのように戻すのかが課題となる。
A*アルゴリズムをPythonで実装するとなぜこうなるのかを詳細に知りたい方は次のWebを参照してください。8パズルの例です。ヒープを自作しているのでヒープの中身まで理解できます。
http://www.nct9.ne.jp/m_hiroi/light/pyalgo28.html
『Algorithms with Python - ヒューリスティック探索』
◆◆評価関数◆◆
A*アルゴリズムの評価関数の定義はこのアルゴリズムの最大の特徴である。micromouseAstar.pyの41行目の
pos_score = distance(newpath) + heuristic(pos)
である。distance は79行目の関数であり，このマスまでのステップ数である。heuristicは73行目の関数であり，このマスからゴールまでの直線距離である。
実はダイクストラアルゴリズムはこの heuristic を 0 にするつまり削除するだけで実装できるのである。
アルゴリズム理論では初期状態からゴールまでの手順の数（重みを付ける場合もある）をコストと呼ばれる。コスト予測の手段が評価関数に反映される。
distance は訪問済みのマスまでのステップ数の実績値であるが全部を訪問していないので理論上はこのマスまでのコスト予測値と説明される。
heuristic はこのマスからゴールまでのコスト予測値であるが，理論上，必ず実際のコストより小さくなければならない。具体的にはここからの最短経路のステップ数よりも少ない必要がある。heuristic は直線でゴールに行く理論的なステップ数ということになる。
heuristic はこのルールを遵守すればどんな関数でもかまわない。ルールを遵守しなければ最適解（つまり，最良，最短）が得られないことが証明されているそうだ。直線距離をユークリッド距離というが，碁盤の筋を通るマンハッタン距離でも良いわけである。
マンハッタン距離を採用するとコスト予測値が足立法と同じになる。
他のアルゴリズムの評価関数では直線距離を採用する場合にルートしなくても大小関係が変わらないのでルートを省略してしまうが，A*アルゴリズムではコスト予測値として distance と heuristic の単位を合わせるためルートは省略できない。
マンハッタン距離を採用しても最短経路は同じになりました。実際に検証してみよう。次のようにコードを書き換えます。マンハッタン距離の方が直線距離（ユークリッド距離）よりも計算時間は圧倒的に短くなります（引き算と累乗の違い）。
修正前
def heuristic(pos):
return ((pos[0] - goal[0]) ** 2 + (pos[1] - goal[1]) ** 2) ** 0.5
修正後
def heuristic(pos):
return (abs(pos[0] - goal[0]) + abs(pos[1] - goal[1]))
◆◆ヒープ◆◆
アルゴリズムと関係ないがプログラミング技法としてのヒープを理解しないとプログラムが読めない。
ヒープは使う側からみると，1次元の配列みたいなスタックである。ただ1番上にはいつもデータのうち最小値がいる。つまりいつもソートしているので特別な構造をしているわけである。しかしこの特別な構造をしらなくてもヒープは使うことができる。知っておかなければならないのは，最上位は最小値ということだけである。
特別なデータ構造とソートアルゴリズムを知る必要はまったくないが，なぜそんなことができるのかを知ることはおもしろい。
これはツリーというデータ構造である。ツリーが10段あれば最下段は1024コのデータが並ぶ。
ある特別なアルゴリズムで枝を渡っていくとする。
ツリーからデータを探すのに最大10回の操作ですむ。
データを加えてツリーのしかるべき位置におさまるのに
最大10回の操作ですむ。
1次元配列で1000コの要素があれば1つのデータを探すのに平均500回の操作が必要である。データを1つ加えてそれを正しい位置までソートするのにもまた平均500回の操作が必要である。ヒープではそれが10回の操作ですむ。
くどいようだがヒープは使う側からみると，1次元の配列みたいなスタックである。中身をみても上のツリーのようにはなっていない。あくまでも配列のソートの考え方だけのことである。
◆◆A*（A-Star，エースター）アルゴリズムの詳細◆◆
さまざまな探索において状態や局面のことを node といい，継続 node をすべて生成した状態を close といい，生成してない継続 node が残っている状態を open という。
これは航空路や物流などのグラフ理論で地点を node というのとニュアンスが違うので注意してほしい。8パズルや15パズル，または詰め将棋や詰め碁でもよいがある盤状態・局面を最短経路探索では node という。つまり 1手先はツリーが枝分かれして新しい node となる。迷路でも 1手先は別の局面として扱う。
迷路探索では進んできた経路1つ1つが個別の node になり，隣接マスに進むと継続 node として別の node になる。そして隣接マスすべてに出た元のマスまでの経路 node が close になり，入ったマスまでの経路 node が open となる。
探索では open-node を待ち行列にに登録して，適当な順序で取り出して継続 node を展開することを繰り返す。待ち行列を open-list と呼ぶこともある。 close-node も close-list に登録しておくのが普通である。
探索プログラム micromouseAstar.py では50行目で継続 node つまり次の経路を open-list に追加する。このプログラムでは close-list は用意してなく，48行目で訪問済みのマスとコストを記録している。8パズルのような探索では close-list を持つ必要がある。
ここまではさまざまな探索において共通の一般論である。
A*アルゴリズムの特徴の1つは open-list に priority queue （優先度付き待ち行列）を採用すること，もう1つは優先度を決める評価関数である。
評価関数は以前の項で述べたように，今いるマスまでの最短経路のコスト（ステップ数）とゴールまでのコスト予測値（具体的には直線距離またはマンハッタン距離）の和である。open-node についてつまり探索途中の経路についてコストと共に open-list に登録されている。A*アルゴリズムを実現するために open-list は前項で述べたヒープを採用している。
待ち行列 open-list から探索途中経路 open-node を取り出し探索を繰り返すところを詳しくみてみよう。
24行目の while 文は待ち行列がある限り探索を続ける。 while 文を抜けたら探索は失敗である。
ループの最初に待ち行列の中の最小コスト経路を取り出して（27行目），その経路の最後の座標を取り出す（29行目）。最後の座標がゴールか判断して（33行目），ゴールでなければ隣接マスがあるだけ（38行目）そのコスト予測値を算出する（41行目）。
この隣接マスが訪問済みならば今回の経路コスト予測値が小さいときだけ待ち行列 open-list に登録する（50行目）。訪問済みでないならばこの隣接マスの経路を待ち行列 open-list に登録する（50行目）。新しい待ち行列 open-list ができたので while文を繰り返す。
8パズルのように close-list を持っているプログラムでは，ループの最初で取り出された open-node は while文の最後で隣接マス経路の待ち行列 open-list への登録が終わり close になるので close-list に登録する。訪問済みのマスの経路も close-list に登録されているはずなので上のようにコストで再評価されて open-list に登録されたときは close-list から抹消する。
このプログラムは close-list がなくても A*アルゴリズムはきちんと動くが，応用する場合は close-list の要不要を検討しなければならない。
◆◆曲がる回数を少なくしたい◆◆
評価関数のうち distance は今のマスまでの経路コストの実績値である。上のプログラムでは今のマスまでのステップ数である。
曲がる回数を少ないしたいときは曲がったら distance を加算すればよい。プログラムの修正を下に示す。曲がることを隣接3マスの座標で判断している。x, y がともに 0 なら直進である。加算の重みは1ステップと同じにしている。
最短経路の結果を下の図に示す。上の最短経路の図はステップ数が最少であるが，曲がる回数がかなり多いのが判る。マイクロマウスのコース設定はかなり巧みだなと感心させられる。
実際のプログラムの修正は，探索プログラム micromouseAstar.py の80行目の return 文をコメントアウトするだけでよい。
修正前
def distance(path):
return len(path)
修正後
def distance(path):
dist = 0
for n in range(len(path)-2):
p0 = path[n]
p1 = path[n+1]
p2 = path[n+2]
x = p0[0] - 2 * p1[0] + p2[0]
y = p0[1] - 2 * p1[1] + p2[1]
if x != 0 or y != 0:
dist += 1
return len(path) + dist
◆◆プログラミングの準備◆◆
◆◆描画プログラムに渡す壁コード◆◆
すべてのマスが独立に壁設定の情報を配列で持っています。
各方向の壁に対して2進数のビットを割り当てています。1, 2, 4, 8 が南，西，北，東になります。しかし，ビット演算はほとんどしていません。
◆◆描画プログラムに渡す壁の配列の自動生成◆◆
このWebの左上隅からソースファイルをダウンロードすると，壁の配列を自動生成してくれる「micromousesetting.xls」が付いています。
迷路の図のつくり方は簡単です。グリッドを選択ドラッグして，右クリックメニューのセルの書式設定 > 罫線タブ > 線幅を選択 > 線を描く位置を選択
複数グリッドを選択するには Ctrl を押しながら選択します。飛び飛びでも選択できますので，例えば，同じ「く」の字を選択するといっぺんに描くことができます。
全グリッドの全筋を描くには，全グリッドを選択してから「田」を入力します。
内側筋を使うときは正方4マスのときだけ判りやすいですが，その他はよく考えないと混乱するようです。
Python の配列を生成するには，起動時に現れるダイアログのボタンを押すだけです。"A1"セルに書かれているのでそのセルをコピーしてソースファイル「micromousesetting.py」の8行目の return 文の後に貼り付けてください。
Python では，カンマの後は改行してもよいことになっています。このときだけインデントをきれいに揃える必要はないです。
◆◆Tkinterによるアニメーション◆◆
描画プログラムはTkinterによるアニメーションを使っている。少々長いプログラムだが構造がしっかりしているので難しいところはない。
メインプログラム micromouse2.py の クラス 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つあります。
・micromouse2.py；描画プログラム（メインプログラム：次の2つをインポートする）
（別記事のものと同じものです。importするモジュールだけ替えてあります）
・micromousesetting.py；壁設定プログラム（迷路の配列は8行目）
（別記事のものと同じものです）
・micromouseAstar.py；経路探索プログラム（A*アルゴリズム）
【おまけ】
迷路の壁を自由に設定できる「micromousesetting.xls」も付いてます。上の図の迷路は競技会主催団体のWebにあったものです。Excel の表に迷路を書けば自動的に Python の配列に変換できるように Excel VBA でプログラムしてあります。迷路の配列は"A1"セルに書き込まれます。壁設定プログラムにコピペしてください。（別記事のものと同じものです）
【micromouse2.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 micromouseAstar 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()
【micromouseAstar.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
# -*- coding: utf-8 -*-
"""
path search by A* algorithim
"""
from heapq import heappush, heappop
import micromousesetting as St
dungeon = St.wall_setting()
init = (0, 0)
goal = (7, 7)
def astar(init, goal):
"""A* algorithim
"""
queue = []
visited = [init] # debug
# 評価関数 初期値
init_score = distance([init]) + heuristic(init)
# close-listの代わりに訪問済みリストを用意
checked = {init: init_score}
# open-listのstart-node
heappush(queue, (init_score, [init]))
No = 0
while len(queue) > 0:
No += 1
# open-listからコスト最小の探索済み経路を取り出す
score, path = heappop(queue)
# コスト最小経路の最後の座標
last = path[-1]
# 訪問済みとして登録，debug用でありアルゴリズムに関係ない
visited.append(last) # debug
# print(len(path), len(visited), last) # debug
if last == goal:
# ゴールを発見
print(No)
return path, visited
# コスト最小経路の最後の座標の四方を探索
for pos in nexts(last):
newpath = path + [pos]
# 評価関数でコスト予測値
pos_score = distance(newpath) + heuristic(pos)
# コスト最小経路の最後の座標が，
# 訪問済みで今回のコストのほうが大きいならば次の四方の座標の探索へ
if pos in checked and checked[pos] <= pos_score:
continue
# 訪問済みで今回のコストのほうが小さいならばor訪問済みでなくても
# 訪問済みリストに格納
checked[pos] = pos_score
# open-listに今回のコストと経路を追加
heappush(queue, (pos_score, newpath))
# pass
# pass
# while文を抜けたら探索失敗
return None
def nexts(pos):
"""マウスが四方に行くことが可能か判定
"""
# north
if (dungeon[pos[0]][pos[1]]) & 4 != 4:
yield (pos[0], pos[1] + 1)
# south
if (dungeon[pos[0]][pos[1]]) & 1 != 1:
yield (pos[0], pos[1] - 1)
# west
if (dungeon[pos[0]][pos[1]]) & 2 != 2:
yield (pos[0] - 1, pos[1])
# east
if (dungeon[pos[0]][pos[1]]) & 8 != 8:
yield (pos[0] + 1, pos[1])
# pass
def heuristic(pos):
"""直線距離；ユークリッド距離"""
# return ((pos[0] - goal[0]) ** 2 + (pos[1] - goal[1]) ** 2) ** 0.5
"""マンハッタン距離"""
return (abs(pos[0] - goal[0]) + abs(pos[1] - goal[1]))
def distance(path):
return len(path)
dist = 0
for n in range(len(path)-2):
p0 = path[n]
p1 = path[n+1]
p2 = path[n+2]
x = p0[0] - 2 * p1[0] + p2[0]
y = p0[1] - 2 * p1[1] + p2[1]
if x != 0 or y != 0:
dist += 1
return len(path) + dist
def main_dungeon():
"""main program
"""
mdpath, mdvisited = astar(init, goal)
# 文字壁の探索プログラムのreturn文に合わせる
return mdpath, mdvisited, mdpath
if __name__ == "__main__":
mpath, mvisited, mpath = main_dungeon()
print(mpath)
'''
print(nexts([0,0]))
print(nexts([15,15]))
for i in range(16):
print(i&8,)
'''
【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))