迷路クラスの設計と迷路エディタの実装 (Python)

迷路クラスの設計と迷路エディタの実装 (Python)

こんにちは.けりです.

今回はPythonで記述した迷路クラスと迷路エディタの紹介です.

作ったもの

Python3の勉強のためにマイクロマウスの迷路ファイルのエディタを作ってみました.

今回作ったのはこちらの動画のようなアプリケーションです.

ファイルから迷路情報を読み込み,クリックで壁を編集してから保存するアプリケーションです.

ソースコード

最新のソースコードは

に公開しています.

また,今回紹介するPythonによる迷路クラスは,私が普段マイクロマウスに使用しているC++によるマイクロマウス迷路ライブラリがベースになっています.

C++による実装に興味がある方はそちらも合わせてご覧ください.

執筆時点のソースコードの取得方法

以下では,執筆時点のソースコード の設計内容を説明します.

GitHubのリポジトリに v1.0 というタグをつけたので,以下のコマンドによって下記で説明されているバージョンのソースコードを取得できます.

git clone -b v1.0 https://github.com/kerikun11/micromouse-mazedata.git
cd micromouse-mazedata

zipファイルでのダウンロードは こちら

迷路クラスの設計

さて,マイクロマウスの迷路クラスの設計です.

Python スクリプト tools/maze.pyMaze クラスでは主に壁情報,スタートやゴール区画の管理を行います.

今回は迷路を以下のようにモデル化してクラス設計を行いました.

方向の表現

迷路内での方向は定数 East, North, West, South で表現します.

列挙型のような使い方です.

とりあえず今回の実装では方向は4方向としました.

今後,斜めも実装する気になったら8方向に拡張したいと思います.

以下, maze.py の冒頭部分です.

import numpy as np

class Maze:
    """
    a maze class includes wall data, start indexes, goal indexes
    """
    # constants
    East, North, West, South = range(4)

区画座標の表現

区画の座標は,直感的でわかりやすかったのでそのまま x, y 成分で使用しています.

区画座標は numpy.array で表すべきかとも思いましたが,表現の簡潔性からこの表現にしました.

壁の位置の表現

マイクロマウス迷路における壁の表現は結構厄介なものです.

座標 (x, y, d) というように,各区画 (x, y) に対して東西南北 d の4つの壁を保存してしまうと,1つの壁に対して2つの区画が接しているせいで冗長になってしまいます.

そこで私は壁の座標を (x, y, z) という別の表現で重複がなくなるようにしています.ただし, (x, y) は通常の区画位置ですが,z は壁の区画位置です.

区画内位置 z は 1bit の変数で, z=0 なら区画 (x, y) の東壁, z=1 なら区画 (x, y) の北壁であることを表します.

これによって, (x, y, z) で迷路内(と東と北の外周)の N * N * 2 個の壁を重複なく表現することができます.ただし, N は迷路サイズです.

そして,この座標 (x, y, z) をもとに壁ID wall_index = x + y * N + z * N * N を定義します.

このIDは,迷路内の全壁の通し番号となり,配列のアクセスなどに活用することができます.

ちなみにマイクロマウスでは, N が2の累乗数なので,Nの掛け算の代わりに log2(N) 個のビットシフトで計算することもできます.

最後に注意点として, wall_index の値はフィールド内の壁にのみ有効なので,メソッド is_inside_of_field() によって壁がフィールド内にあることを確認してから計算するようにします.

以下, maze.py の続きです.

    @classmethod
    def uniquify(cls, x, y, d):
        """
        returns a unique coordinates of a wall without redundancy on both sides of the wall

        Returns
        -------
        int x, int y, int z, int d
        """
        if d == cls.East:
            x, y, z, d = x, y, 0, cls.East
        elif d == cls.North:
            x, y, z, d = x, y, 1, cls.North
        elif d == cls.West:
            x, y, z, d = x-1, y, 0, cls.East
        elif d == cls.South:
            x, y, z, d = x, y-1, 1, cls.North
        return x, y, z, d

    def get_wall_index(self, x, y, z):
        """
        get a unique and sequential index of a wall inside of the maze

        Returns
        -------
        int index
        """
        if not self.is_inside_of_field(x, y, z):
            raise ValueError("out of field!")
        return x + y * self.size + z * self.size * self.size

    def is_inside_of_field(self, x, y, z=None):
        """
        determine if the wall or cell is inside of the field

        Returns
        -------
        bool result
        """
        s = self.size  # maze size
        if z == None:
            return x >= 0 and y >= 0 and x < s and y < s  # cell
        else:
            return x >= 0 and y >= 0 and x < s+z-1 and y < s-z  # wall

コンストラクタ

Maze クラスのコンストラクタでは,迷路サイズを受け取って必要な変数を初期化します.

壁情報は論理値の配列 np.array(dtype=bool) で確保しました.

C++の場合は std::bitset で確保しているのですが,Pythonにはないようなのでこのように bool の配列にしました.

以下, maze.py の続きです.

    def __init__(self, size=32, start=[], goals=[]):
        """
        construct a maze object with a maze size
        """
        self.size = size  # number of cells on one side of the maze
        # the number of cells in the maze: x * y
        self.cell_index_size = size * size
        # the number of walls to save: x * y * z
        self.wall_index_size = size * size * 2
        # wall data; wall states and known flags
        self.walls = np.zeros(self.wall_index_size, dtype=bool)
        self.knowns = np.zeros(self.wall_index_size, dtype=bool)
        # start and goal cells
        self.start = start
        self.goals = goals

壁の取得

次に壁情報の取得や更新の部分です.

実装を共通化するため,壁の更新と取得はひとつのメソッドで行います.

以下, maze.py の続きです.

    def wall(self, x, y, d, new_state=None, new_known=None):
        """
        get or update a wall flag, and optionally update a known flag

        Returns
        -------
        bool flag
        """
        x, y, z, d = self.uniquify(x, y, d)
        # If it is out of the field, the wall is assumed to exist.
        if not self.is_inside_of_field(x, y, z):
            return True
        i = self.get_wall_index(x, y, z)
        if new_state != None:
            self.walls[i] = new_state
        if new_known != None:
            self.knowns[i] = new_known
        return self.walls[i]

    def known(self, x, y, d, new_known=None):
        """
        get or update a known flag of a wall

        Returns
        -------
        bool flag
        """
        x, y, z, d = self.uniquify(x, y, d)
        # If it is out of the field, the wall is assumed to be known.
        if not self.is_inside_of_field(x, y, z):
            return True
        i = self.get_wall_index(x, y, z)
        if new_known != None:
            self.knowns[i] = new_known
        return self.knowns[i]

迷路情報の表示

迷路サイズやゴールの位置などの迷路情報を表示するメソッドです.

以下, maze.py の続きです.

    def __str__(self):
        """
        show information of the maze

        Returns
        -------
        string
        """
        return f'size: {self.size}x{self.size}' + '\n' + \
            'start: ' + ', '.join([f'({x}, {y})' for x, y in self.start]) + '\n' + \
            'goals: ' + ', '.join([f'({x}, {y})' for x, y in self.goals])

迷路ファイルの解析と生成

次に説明するのは,迷路の保存形式です.

私は過去の大会の迷路情報を以下に示すようなテキスト形式で保存しています.

+---+---+---+---+---+---+---+---+---+
|   |       |       |       | G   G |
+   +   +   +   +   +   +   +   +   +
|       |       |       |   | G   G |
+   +   +---+   +   +---+   +---+   +
|   |           |       |           |
+   +---+   +---+   +---+---+   +---+
|       |       |           |       |
+---+   +   +   +---+---+   +---+   +
|       |   |       |       |       |
+   +   +---+---+   +   +   +   +   +
|   |   |       |       |       |   |
+   +   +   +   +---+   +---+   +   +
|   |       |       |           |   |
+   +---+   +---+   +---+   +---+   +
|       |   |       |           |   |
+   +   +   +   +---+   +---+   +   +
| S |       |                       |
+---+---+---+---+---+---+---+---+---+

この形式の迷路を読み込んだり書き出したりする部分のコードです.

以下, maze.py の続き:

    @staticmethod
    def parse_maze_string(file):
        """
        parse a maze string from file and construct a maze object

        Returns
        -------
        Maze object
        """
        lines = file.readlines()
        maze_size = max(len(lines)//2, len(lines[0])//4)
        maze = Maze(maze_size)  # construct a maze object
        for i, line in enumerate(reversed(lines)):
            line = line.rstrip()  # remove \n
            # +---+---+---+---+
            if i % 2 == 0:
                for j, c in enumerate(line[2:: 4]):
                    if c == '-':
                        maze.wall(j, i//2, Maze.South, True, new_known=True)
                    elif c == ' ':
                        maze.wall(j, i//2, Maze.South, False, new_known=True)
            # |   |   | G |   |
            else:
                for j, c in enumerate(line[0:: 4]):
                    if c == '|':
                        maze.wall(j, i//2, Maze.West, True, new_known=True)
                    elif c == ' ':
                        maze.wall(j, i//2, Maze.West, False, new_known=True)
                for j, c in enumerate(line[2:: 4]):
                    if c == 'S':
                        maze.start.append([j, i//2])
                    if c == 'G':
                        maze.goals.append([j, i//2])
        return maze

    def get_maze_string(self):
        """
        generate a maze string to be saved in text format

        Returns
        -------
        string
        """
        res = ''  # result string
        for y in reversed(range(-1, self.size)):
            # +---+---+---+---+
            res += '+'  # first pillar
            for x in range(self.size):
                # horizontal wall
                if not self.known(x, y, Maze.North):
                    res += ' . '
                elif self.wall(x, y, Maze.North):
                    res += '---'
                else:
                    res += '   '
                res += '+'  # pillar
            res += '\n'
            # |   |   | G |   |
            if y == -1:
                break
            res += '|'  # first wall
            for x in range(self.size):
                # cell space
                if [x, y] in self.start:
                    res += ' S '
                elif [x, y] in self.goals:
                    res += ' G '
                else:
                    res += '   '
                # vertical wall
                if not self.known(x, y, Maze.East):
                    res += '.'
                elif self.wall(x, y, Maze.East):
                    res += '|'
                else:
                    res += ' '
            res += '\n'
        return res

Mazeクラスの使用例

ここまでに紹介した maze.py の使用例を紹介します.

ターミナルで迷路ファイルを指定して実行すると以下のように表示されます.

$ python3 tools/maze.py data/04_test_01.maze

size: 4x4
start: (0, 0)
goals: (1, 0)
+---+---+---+---+
|       |       |
+   +   +   +   +
|   |   |   |   |
+   +   +   +   +
|   |       |   |
+   +---+---+   +
| S | G         |
+---+---+---+---+

以下, maze.py の最後の部分です.

import sys

# example
if __name__ == "__main__":
    # check arguments
    if len(sys.argv) < 2:
        print('please specify a maze file.')
        sys.exit(1)

    # set filepath
    filepath = sys.argv[1]

    # read maze file
    with open(filepath, 'r') as file:
        maze = Maze.parse_maze_string(file)

    # show info
    print(maze)
    print(maze.get_maze_string())

迷路エディタの設計

次に,迷路エディタアプリケーションの紹介です.

Python スクリプト tools/maze_editor.pyMazeEditor クラスは,迷路をウィンドウに描画して壁を編集する機能を搭載します.

冒頭部分

ここでは numpy モジュール, matplotlib モジュールと上記で紹介した迷路モジュール maze.py を読み込みます.

MazeEditor のコンストラクタでは, Maze class のオブジェクトを受け取ります.

以下, maze_editor.py の冒頭の部分です.

import math
import numpy as np
import matplotlib.pyplot as plt

from maze import Maze  # calls ./maze.py

class MazeEditor:
    """
    paint a maze with matplotlib.pyplot
    """

    def __init__(self, maze):
        """
        construct a maze editor object with a maze object
        """
        self.maze = maze  # maze object

迷路の表示

次に,迷路の表示部分です.

Pythonの数値プロットライブラリ matplotlib を用いて迷路を描画します.

以下, maze_editor.py の続き:

    @staticmethod
    def draw_wall(maze, x, y, d, fmt='k', **kwargs):
        x, y, z, d = Maze.uniquify(x, y, d)
        if z == 0:
            x, y = [x+1/2, x+1/2], [y-1/2, y+1/2]
        else:
            x, y = [x-1/2, x+1/2], [y+1/2, y+1/2]
        plt.plot(x, y, 'w', lw=2)  # erase wall
        plt.plot(x, y, fmt, **kwargs)  # draw new wall
        plt.plot(x, y, 'k.')  # draw pillars

    def draw_maze(self):
        maze = self.maze
        # print walls
        for i in range(maze.size+1):
            for j in range(maze.size):
                # +---+---+
                if maze.wall(i, j, Maze.South):
                    self.draw_wall(maze, i, j, Maze.South)
                else:
                    self.draw_wall(maze, i, j, Maze.South, ':', color='gray')
                # |   |   |
                if maze.wall(j, i, Maze.West):
                    self.draw_wall(maze, j, i, Maze.West)
                else:
                    self.draw_wall(maze, j, i, Maze.West, ':', color='gray')
        # print start and goal character
        for ps, t in [[maze.start, 'S'], [maze.goals, 'G']]:
            for p in ps:
                plt.text(p[0], p[1], t, ha='center', va='center')
        plt.axes().set_aspect('equal')  # set the x and y axes to the same scale
        plt.xticks(range(0, maze.size+1, 1))
        plt.yticks(range(0, maze.size+1, 1))
        plt.xlim([-1/2, maze.size-1/2])
        plt.ylim([-1/2, maze.size-1/2])
        plt.tight_layout()

壁の編集機能

次に,迷路中の壁の編集部分です.

壁の付近をクリックしたときに,その壁が反転するようにしています.

また,編集した壁はわかりやすいように色を変えて表示しています.

以下, maze_editor.py の続き:

    def attach_wall_toggle(self):
        plt.connect('button_press_event', self.button_press_event)

    def button_press_event(self, event):
        maze = self.maze
        x, y = event.xdata, event.ydata
        xf, xi = math.modf(x)
        yf, yi = math.modf(y)
        z, d = [0, Maze.East] if abs(xf-1/2) < abs(yf-1/2) else [1, Maze.North]
        if z == 0:
            x, y = int(round(x-1/2)), int(round(y))
        else:
            x, y = int(round(x)), int(round(y-1/2))
        w = not maze.wall(x, y, d)
        c = 'r' if w else 'r:'
        maze.wall(x, y, d, w, new_known=True)
        MazeEditor.draw_wall(maze, x, y, d, c)
        plt.draw()
        print(maze.get_maze_string())

迷路エディタの使用例

以下, maze_editor.py の最後の部分です.

import os
import sys
import datetime

# example
if __name__ == "__main__":
    # check arguments
    if len(sys.argv) < 2:
        print('please specify a maze file.')
        sys.exit(1)

    # set filepath
    filepath = sys.argv[1]

    # read maze file
    with open(filepath, 'r') as file:
        maze = Maze.parse_maze_string(file)
    print(maze)
    print(maze.get_maze_string())

    # prepare figure
    figsize = maze.size / 2
    fig = plt.figure(figsize=(figsize, figsize))

    # setup maze editor
    mp = MazeEditor(maze)
    mp.draw_maze()
    mp.attach_wall_toggle()

    # start
    plt.show()

    # save modified maze
    os.makedirs('output', exist_ok=True)
    datetime_string = datetime.datetime.now().strftime('%Y%m%d-%H%M%S')
    basename_without_ext = os.path.splitext(os.path.basename(filepath))[0]
    output_filepath = f'./output/{basename_without_ext}-{datetime_string}.maze'
    with open(output_filepath, 'w') as file:
        file.write(maze.get_maze_string())
        print('modified maze data saved: ' + output_filepath)

ターミナルで迷路ファイルを指定して以下のコマンドを実行すると迷路ウィンドウが表示されます.

$ python3 tools/maze.py data/04_test_01.maze

window1

壁の近くを適当にクリックすることでその壁の有無を切り替えることができます.

window2

ウィンドウを閉じると以下のようにファイル名に日時を付加して保存されます.

...
modified maze data saved: ./output/04_test_01-20200504-162035.maze
$ cat ./output/04_test_01-20200504-162035.maze
+---+---+---+---+
|       |       |
+   +   +   +   +
|   |       |   |
+   +   +   +   +
|       |       |
+   +---+---+   +
| S | G         |
+---+---+---+---+

これで迷路ファイルの編集ができました!

まとめ

今回は Python で実装した迷路クラスと迷路エディタを紹介しました.

迷路クラスの設計は実際にマウスで使用する C/C++ での実装にも役に立つと思いますので是非参考にしてみてください.

Python はちょっとしたアプリケーションを作る際にとても便利なので,慣れておきたいところです.

もし,もっといい書き方があるよと気づいた方は是非教えてください!

よろしくおねがいします.