python マイクロマウス tkinterアニメーションで見せる，足立法歩数マップの最短経路は最短経路探索A*（A-Star）アルゴリズムと同じ

Update 2023.11.14 2018.11.08

マイクロマウス：tkinterアニメーションで見せる
足立法歩数マップの最短経路は最短経路探索A*（A-Star）アルゴリズムと同じ
Python3(3.10)で動くソースコード（.pyファイル .ipynbファイル）あります
「anaconda3」on .py「PyCharm」.ipynb「Jupyter Notebook」

マイクロマウスの足立法歩数マップは実に簡単なアルゴリズムで最短経路を探すことができます。その経路が最短経路探索A*（A-Star；エースター）アルゴリズムと同じであったことがその優秀性を示しています。

その最短経路を探している様子をアニメーションでお見せします。コンピュータによる試行が人間の思考のように見えます。

◆◆マイクロマウスクラシック◆◆

マイクロマウスクラシックの迷路は 16×16 のグリッドからできていて，終点は真ん中の4つのグリッドで，始点は四隅のいずれかであり時計回りに出発する。
詳細は競技会を主催している団体のWebサイトを参照してください。 http://www.ntf.or.jp/mouse/
『公益財団法人ニューテクノロジー振興財団』

（2023-11-14）Python3.10で動作確認済み

◆◆足立法の歩数マップのアルゴリズム◆◆

足立法で最短経路を求めるための歩数マップのアルゴリズムを見てみよう。

【歩数マップのアルゴリズム】

・終点に 0 番を付ける
・ 0 番の隣接マスのうち行くことができるマスに 1 番を付ける
・ 1 番の隣接マスのうち行くことができるマスに 2 番を付ける
　　・・・
・ N 番の隣接マスのうち行くことができるマスに N+1 番を付ける
　　　・・・
・始点に番号が付いたら終了
・始点の番号から 1 を引いた番号の隣接マスを探す
・そのマスの番号から 1 を引いた番号の隣接マスを探す
　　・・・
・ 0 番の終点を見つけたら終了

◆◆足立法の歩数マップの例◆◆

上で紹介したマイクロマウスの主催団体のＨＰに掲載されていた迷路を使い，歩数マップと最短経路をアニメーションで見せる Python のプログラムをつくってみた。

結果が次の図である。

上の図の最短経路はこのサイトの別記事の A*（エースター）アルゴリズムが見つけた最短経路と同じであった（あたりまえかな）。

◆◆足立法の歩数マップの使い方◆◆

足立法では経路探索の途中でも，探索していないところの壁をないものとして暫定歩数マップを作成する。その例が次の図である。

上の図の例では， [0,9] , [3,10] , [5,4] が open である。足立法アルゴリズムでは，暫定的な最短経路（最少コスト経路）である [0,9] 経由で， [0,9] の先へ進めということになる。

実はこの考え方は A*（エースター）アルゴリズムと同じである。マンハッタン距離を採用すればコスト予測値も同じになる。違うのは A*アルゴリズムではマスを1つ進めた瞬間に open な経路のうちの最小コスト経路はヒープによって判明していることである。

足立法では歩数マップを再計算する必要がある。が，歩数マップの計算はほとんど時間がかからない。このプログラムでは高速法といわれる隣接マスのみ計算する方法を採用しているが，実は無条件に16×16のマス全部を計算した方が速いかもしれないのである。

足立法と A*アルゴリズムを比較すると，コスト予測値の計算方法が違っていても，コスト予測値は同じになり，さらに最小コスト経路も同じになるのです。

足立法や A*アルゴリズムだけではマウス走行アルゴリズムにならない。最小コスト経路を優先する最良優先探索では最小コスト経路がめまぐるしく変わる。このときマウスを戻すアルゴリズムが必要である。

実はここにも足立法や A*アルゴリズムがそのまま使えるのである。上の図の探索済みの迷路を仮に閉じた迷路にすればこれらのアルゴリズムの適用ができ，最短経路でマウスを戻すことができるのである。

◆◆歩数マップ作成プログラム◆◆

巻末にソースコードを掲載してあります。

歩数マップは 19行目の関数 pedometer() でつくります。23行目で最大250ステップまで対応していますが渦巻型の袋小路があったらオーバーするかもしれません。

24行目でステップ数を key，そのステップ数のマスの座標のリストを value としたハッシュを呼んでいます。呼び出されたマスの隣接マスを36行目の関数 neighbor() で確認します。

34行目で隣接マスの座標のリストをハッシュに登録します。

◆◆最短経路の配列作成プログラム◆◆

最短経路の配列作成は55行目の関数 through_maze() がつくります。この関数が外のモジュールから呼ばれたときのために59行目で関数 pedometer()を呼んでいます。単体 debug で両方の関数を呼ぶ場合は歩数マップのステップ数 map_step[][] が global なので59行目は不要となります。

歩数マップのステップ数は61行目の map_step[][] を使っています。受け取った関数値（戻り値）を使ってもいいのですが，map_step[][] が global なのでこちらを使いました。

63行目で歩数ステップを順に減じていき 0 番が見つかるまで隣接マスの番号を確認していきます。

70行目に隣接マスの１つ小さい番号を確認する関数　next_grid()　があります。本来，壁の有無と関係なく確認できるのですが，1番外側のマスでさらに外の座標を呼ぶと bug るので壁のない隣接マスだけ確認しています。

アニメーションのコマ送り間隔は，micromouse3.pyの11行目で設定できる。1以上を設定すること。単位はミリ秒であるが「1」に設定しても描画のためかそれほど速くない。「250」くらいがほどよい。

◆◆ソースコード◆◆

このWebの左上隅からダウンロードできます。

ソースファイルは7つあります。
① micromouse3.py；描画プログラム（メインプログラム：次の2つをインポートする）
　（別記事のものと同じものです。importするモジュールだけ替えてあります）
② micromousesetting.py；壁設定プログラム（迷路の配列は8行目）
　（別記事のものと同じものです）
③ micromouseAdachiPedometer.py；経路探索プログラム（足立法）
④ micromouse4stepmap.py；歩数マップ描画（メインプログラム：上の2つをインポートする）
⑤ micromousesetting2.py；壁設定プログラム（②と同じですが壁が途中までしかありません）
　（メインプログラム ①，④ ，経路探索 ③ の import 文のモジュール名を替えてください）

【おまけ】
⑥ micromousesetting.xls；② の壁設定を出力します
⑦ micromousesetting2.xls；⑤ の壁設定を出力します

【micromouseAdachiPedometer.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

    

# -*- coding: utf-8 -*-
"""
Micro Mouse 足立法　歩数マップ
"""
# import numpy as np
# import matplotlib.pyplot as plt
# import sys
# from heapq import heappush, heappop

import micromousesetting as St

dungeon = St.wall_setting()
map_hash = {}
map_hash[0] = [[7, 7],[7, 8],[8, 7],[8, 8]]
max = 255
map_step = [[max for i in range(16)] for j in range(16)]
init = [0, 0]

def pedometer():
    """メインなサブルーチン
       足立法　歩数マップ
    """
    for step in range(250):
        coord = map_hash[step]
        next = []
        for pos in coord:
            map_step[pos[0]][pos[1]] = step
        for pos in coord:
            nextnext = neighbor(pos)
            if nextnext != []:
                next = next + neighbor(pos)
        if next == []:
            return map_step, map_hash
        map_hash[step + 1] = next

def neighbor(pos):
    """隣接マスの処理の済んでいない座標を返す
    """
    bb = []
    ww = dungeon[pos[0]][pos[1]]
    # north
    if ww & 4 != 4 and map_step[pos[0]][pos[1] + 1] == max:
        bb = bb + [(pos[0], pos[1] + 1)]
    # south
    if ww & 1 != 1 and map_step[pos[0]][pos[1] - 1] == max:
        bb = bb + [(pos[0], pos[1] - 1)]
    # west
    if ww & 2 != 2 and map_step[pos[0] - 1][pos[1]] == max:
        bb = bb + [(pos[0] - 1, pos[1])]
    # east
    if ww & 8 != 8 and map_step[pos[0] + 1][pos[1]] == max:
        bb = bb + [(pos[0] + 1, pos[1])]
    return bb

def through_maze():
    """メインなサブルーチン
       足立法　歩数マップの最短経路
    """
    a, b = pedometer()
    pos = init
    max = map_step[init[0]][init[1]]
    path =[pos]
    while max > 0:
        pos_next = next_grid(pos, max-1)
        pos = pos_next
        path = path + [pos]
        max -= 1
    return path

def next_grid(pos, max):
    """隣接マスの歩数のうち１つ小さいものを探す
    """
    ww = dungeon[pos[0]][pos[1]]
    # north
    if ww & 4 != 4 and map_step[pos[0]][pos[1] + 1] == max:
        return [pos[0], pos[1] + 1]
    # south
    if ww & 1 != 1 and map_step[pos[0]][pos[1] - 1] == max:
        return [pos[0], pos[1] - 1]
    # west
    if ww & 2 != 2 and map_step[pos[0] - 1][pos[1]] == max:
        return [pos[0] - 1, pos[1]]
    # east
    if ww & 8 != 8 and map_step[pos[0] + 1][pos[1]] == max:
        return [pos[0] + 1, pos[1]]

def main_dungeon():
    """main program
    """
    aa = through_maze()
    dummy = []
    # 文字壁の探索プログラムのreturn文に合わせる
    return dummy, dummy, aa


if __name__ == "__main__":

    a,b = pedometer()
    print(len(b))
    print(a)
    print(b)

    a, b, c = main_dungeon()
    print(c)

    

トップページに戻る