Qtを使用した迷路シミュレーターを作る (迷路アルゴリズムの実装から動作テスト編)
マイクロマウス関連記事のまとめはこちら。
https://garberas.com/archives/2177今回で、Qtを使用した迷路シミュレータの最終回です。左手法の動作をシミュレーションできるようにしていきます。
足りないものを考える
迷路アルゴリズムが何も実装されていないことです。このままでは、迷路シミュレータでシミュレーションすることができません。今回は迷路アルゴリズムの一つである左手法(右手法)と呼ばれる迷路探索アルゴリズムを実装していきます。また、動作を動かすプログラムも実装しないといけないということが言えます。
左手法とは
アルゴリズムについて
このアルゴリズムを使用した迷路の解き方は以下の流れになります。
- 左に壁があるかどうか確認する
- 壁がなければ左に曲がる。 あった場合は、前壁を確認する
- 壁がなければ直進する。あった場合は、右壁を確認する
- 壁がなければ右に曲がる。あった場合は、Uターンする。
マイクロマウスの場合は常に左壁が西壁であるとは限りません。マシンがターンをして向きが変わるためです。そのため、マウスの向きに対してのどの壁をみればいいのか考える必要があります。今回の実装では、迷路に対して出発時のマウスの方向を北とおいて、東西南北それぞれの方向に対して、対応する壁について考えていきます。
実装の仕方を考える
今回のシミュレータでは、次のようなクラス(構造体)を構成して迷路アルゴリズムやシミュレータとしての動きを作っていこうと考えました。
- Position 構造体 : マシンの座標、方向を保持、動作に対応して座標、向きの更新を行う
- Maze クラス : 迷路を解くアルゴリズムの実装
- MazeRunBaseクラス : 迷路を解くアルゴリズムを実行する、外部から得た壁情報を保持
- SimulateMazeRunクラス : MazeRunBaseを継承したクラス、迷路シミュレータにおける、迷路の解き方の動作を定義する
MazeRunBaseクラスを定義した主な理由は、迷路シミュレータとマシンのプログラムのプログラムでSimulateMazeRunクラス以外は、同じプログラムを移植できるようにするためです。
迷路シミュレータと実機で、別々のプログラムや実装をしないといけないのでは、非効率的であると考えているためです。
迷路アルゴリズムの実装
初めに、迷路の方向や、動作をmazeconfig.hに次のように定義しました。
numでは、数字を指定しない場合は上から0,1,と連番で値を設定してくれます。
#ifndef MAZECONFIG_H
#define MAZECONFIG_H
#include <stdint.h>
enum Direction :uint8_t
{
North,
West,
South,
East,
};
enum Action :uint8_t
{
Front,
Left,
Rear,
Right,
};
#endif // MAZECONFIG_H
続いて、迷路アルゴリズムの実装と座標系の実装についてのプログラムです。
Positionの構造体は次のように定義しています。C++では、構造体にもメンバ関数を持つことができるので、座標の更新関数を構造体に持ちました。
updateの最初の行にある
next = (direction+act)%4
のところでは、先程の列挙の値を代入して計算することで意味が分かると思います。例を示すと、アップデートする前のdirectionがNorth、次の動作がrightだとすると、
next = (0+3)%4 = 3
ここで計算された3は、Directionの定義より東になっています。マシンの向きが北向きの時に右に曲がると東向きになります。directionがEast、次の動作がleftの時を考えてみると
next = (3+1)%4 = 0
マシンの向きが東の時に左に曲がると北、Directionの定義ではNorth:0なので正しい向きに変更できていることが読み取れます。その後は、向きに合わせて座標の更新を行っています。
左手法の実装の実装は、それぞれの向きに対して壁情報のどの向きをとればいいか考えて実装しました。
関数の返り値は次の動作に設定をしています。
#ifndef MAZE_H
#define MAZE_H
#include "mazeconfig.h"
#include <stdint.h>
struct Position
{
public:
uint8_t x;
uint8_t y;
uint8_t direction;
void init(){
x = 0;
y = 0;
direction = North;
}
void update(uint8_t act)
{
uint8_t next = (direction + act) % 4;
direction = next;
if ( direction == North ){
y++;
} else if ( direction == West ){
x--;
} else if ( direction == South ){
y--;
} else {
x++;
}
}
};
class Maze
{
public:
Maze();
~Maze();
uint8_t leftHands(Position *pos, uint8_t wall[16][16]);
};
#endif // MAZE_H
#include "maze.h"
Maze::Maze()
{
}
Maze::~Maze()
{
}
uint8_t Maze::leftHands(Position *pos, uint8_t wall[16][16])
{
uint8_t act = Rear;
uint8_t north = wall[pos->x][pos->y] & 0x01;
uint8_t east = (wall[pos->x][pos->y] & 0x02) >> 1;
uint8_t west = (wall[pos->x][pos->y] & 0x04) >> 2;
uint8_t south = (wall[pos->x][pos->y] & 0x08) >> 3;
if (pos->direction == North){
if(west == 0){
act = Left;
} else if(north == 0){
act = Front;
} else if(east == 0){
act = Right;
}
} else if(pos->direction == South) {
if(east == 0){
act = Left;
} else if(south == 0){
act = Front;
} else if(west == 0){
act = Right;
}
} else if(pos->direction ==West){
if(south == 0){
act = Left;
} else if(west == 0){
act = Front;
} else if(north == 0){
act = Right;
}
} else {
if(north == 0){
act = Left;
} else if(east == 0){
act = Front;
} else if(south == 0){
act = Right;
}
}
return act;
}
シミュレーション用のプログラムを実装する
迷路アルゴリズムをシミュレーションで動かすためのクラスの実装や、プログラムの拡張を行っていきます。
MazeRunBaseクラスの実装
このクラスでは、左手法で次の動作を決定し、座標の更新をする迷路アルゴリズムの動作をさせたり、壁情報の保持、初期化などを行うようにしました。
#ifndef MAZERUNBASE_H
#define MAZERUNBASE_H
#include "mazeconfig.h"
#include "maze.h"
class MazeRunBase
{
public:
MazeRunBase();
MazeRunBase(uint8_t x, uint8_t y);
virtual ~MazeRunBase();
void setGoal(uint8_t x, uint8_t y);
uint8_t leftHand();
void wall_init();
protected:
Position pos;
uint8_t gx;
uint8_t gy;
uint8_t wall[16][16];
Maze *maze;
};
#endif // MAZERUNBASE_H
#include "mazerunbase.h"
MazeRunBase::MazeRunBase()
{
maze = new Maze();
pos.init();
wall_init();
}
MazeRunBase::~MazeRunBase()
{
delete maze;
}
MazeRunBase::MazeRunBase(uint8_t x, uint8_t y)
{
gx = x;
gy = y;
}
void MazeRunBase::setGoal(uint8_t x, uint8_t y)
{
gx = x;
gy = y;
}
uint8_t MazeRunBase::leftHand()
{
uint8_t act = Rear;
act = maze->leftHands(&pos, wall);
pos.update(act);
return act;
}
void MazeRunBase::wall_init()
{
for(int x = 0; x< 16; x++){
for(int y = 0; y< 16; y++){
wall[x][y] = 0;
}
}
}
SimulateMazeRunクラスの実装
左手法の動作を呼び、迷路シミュレータの時の動作を書いています。leftHandSearch関数ないで、カウントという変数を定義し、動作をするたびに-1をして値がマイナスになったら処理を打ち切るというプログラムを書いています。この処理を入れている理由は、日本のマイクロマウスの公式大会で出題される迷路では、左手法ではゴールにたどり着くことができないような迷路になっているためです。打ち切りのプログラムを入れておかないと無限に動作を繰り返してしまうため、ある一定回数以上動作したら打ち切りという処理を入れました。
#ifndef SIMULATEMAZERUN_H
#define SIMULATEMAZERUN_H
#include "mazerunbase.h"
#include <stdint.h>
#include "drawmaze.h"
class SimulateMazeRun : public MazeRunBase
{
public:
SimulateMazeRun();
virtual ~SimulateMazeRun();
void leftHandSearch(QGraphicsScene *scene);
void copyNowMazeData(uint8_t wall_data[16][16]);
private:
void addSimulateWall();
DrawMaze *draw_maze;
void msleep(int _time);
uint8_t simulate_wall[16][16];
};
#endif // SIMULATEMAZERUN_H
#include "simulatemazerun.h"
#include <QtCore/QEventLoop>
#include <QtCore/QTimer>
SimulateMazeRun::SimulateMazeRun()
{
draw_maze = new DrawMaze();
}
SimulateMazeRun::~SimulateMazeRun()
{
delete draw_maze;
}
void SimulateMazeRun::copyNowMazeData(uint8_t wall_data[16][16])
{
for(int x = 0; x < 16; x++){
for(int y = 0; y < 16; y++){
simulate_wall[x][y] = wall_data[x][y];
}
}
}
void SimulateMazeRun::leftHandSearch(QGraphicsScene *scene)
{
uint8_t act = Front;
wall_init();
pos.init();
// 左手法の場合ゴールにたどり着けない可能性があるため、
// ある一定以上の回数で終わりにする
int count = 200;
while(1){
addSimulateWall();
draw_maze->drawSimulate(scene, pos.x, pos.y, wall);
act = leftHand();
count--;
msleep( 100 );
if(gx == pos.x && gy == pos.y) break;
if(count < 0) break;
}
draw_maze->drawSimulate(scene, pos.x, pos.y, wall);
}
void SimulateMazeRun::msleep(int _time)
{
QEventLoop loop;
QTimer::singleShot( _time, &loop, SLOT( quit() ) );
loop.exec();
}
void SimulateMazeRun::addSimulateWall()
{
wall[pos.x][pos.y] = simulate_wall[pos.x][pos.y];
}
DrawMazeクラスを拡張する
マシンの表示と、壁の表示を一つの関数を定義しました。drawSimulate関数を呼ぶことで、マシンの表示と迷路の表示を同時に行えるようにしました。マシンの表示は、四角形で行いました。
void DrawMaze::drawMachine(QGraphicsScene *scene, uint8_t x, uint8_t y)
{
int dx = 7+step;
int dy = 17 * step - 35;
int box_size = 30;
QBrush brush(Qt::SolidPattern);
QPen pen;
pen.setColor(Qt::cyan);
brush.setColor(Qt::cyan);
dx += x * step;
dy -= y * step;
scene->addRect(dx, dy, box_size, box_size, pen, brush);
}
void DrawMaze::drawSimulate(QGraphicsScene *scene, uint8_t x, uint8_t y, uint8_t (*wall)[16])
{
drawWall(scene, wall);
drawMachine(scene, x, y);
}
mainwindow.ui、MainWindowクラスの変更点
今回のレイアウトの変更点は、ボタンの追加を2つ行っていることです。プッシュボタンはSLOTにクリックされたときとして登録をしています。レイアウトは完成図を参考にしていただければと思います。
追加、変更した機能は以下の通りです
- 迷路をロードした後にsimulate startボタンを押すことでシミュレーションを実行可能にした。
- 迷路のロードができていない場合迷路シミュレーションを実行することがきないようにするといった例外処理もいくつか追加した。
- 右上の閉じるボタンを消した
- quitボタンから終了をするようにした。
MainWindowの変更したプログラムです。
#include "mainwindow.h"
#include "ui_mainwindow.h"
MainWindow::~MainWindow()
{
delete ui;
delete drawmaze;
delete simulate_run;
}
void MainWindow::init()
{
this->setWindowFlags(Qt::CustomizeWindowHint|Qt::WindowTitleHint);
scene = new QGraphicsScene;
ui->filePathEdit->setReadOnly(true);
ui->actionHistoryEdit->setReadOnly(true);
for(int i = 0; i < 16; i++) {
for(int j =0; j < 16; j++ ){
maze[i][j] = 0;
}
}
drawmaze = new DrawMaze();
simulate_run = new SimulateMazeRun();
simulate_run->setGoal(7,7);
drawmaze->init(scene);
ui->graphicsView->setScene(scene);
}
void MainWindow::on_loadButton_clicked()
{
QString fileName = QFileDialog::getOpenFileName(this, tr("Open File"), "", tr("Text File (*.txt);;"));
if ( !fileName.isEmpty() ){
QFile file(fileName);
if ( !file.open(QIODevice::ReadOnly)){
QMessageBox::critical(this, tr("Error"), tr("This System could not open File"));
return;
}
ui->filePathEdit->setText(fileName);
QTextStream stream(&file);
loadMazeData(&stream, maze );
maze_read = true;
} else {
ui->actionHistoryEdit->setText("Not Exsit File");
}
}
void MainWindow::on_SimulateStart_clicked()
{
if(maze_read){
simulate_run->copyNowMazeData(maze);
simulate_run->leftHandSearch(scene);
ui->graphicsView->setScene(scene);
} else {
ui->actionHistoryEdit->setText("Not Include Maze Data");
}
}
void MainWindow::on_quitButton_clicked()
{
qApp->quit();
}
private:
bool maze_read = false;
SimulateMazeRun *simulate_run;
完成図
コンパイルをして実行をした後に、迷路を読み込みstart maze runボタンを押すと、迷路をボックスが走るようになりました。
これは、シミュレータの動作を始めてすぐにとった写真です。同じところを何回も周り、ゴールにたどりつきませんでしたが、一定回数で動作が止まったことからプログラム通りに動いていることの確認ができました。
さいごに
迷路シミュレーターで迷路アルゴリズムに乗っとって迷路を走らせることができるようになりました。
大会で完走するためには拡張左手法や足立法、独自のオリジナルなどのアルゴリズムを実装する必要があります。このプログラムを拡張することで足立法などのシミュレーションも可能なのでぜひやっていただければと思います。
もし、わからないことや、ソフトウェアのバグを見つけた等あった場合は、connectからフィードバックをしていただければと思います。
GitHub リポジトリ
このまでの内容を動かすことのできるプログラムの入ったリポジトリです。
問題等があればissueを投げていただければと思います。確認して対応します。