マイクロマウスの中身を少し考えてみた

2013年7月30日 by admin | Filed under 未分類.

cap020

先日、マイクロマウスな方々とお話する機会がありまして、今までは観戦者って立場でマイクロマウスを見ていたのですが、ちょっと中身がどうなっているのだろうと考え、試験プログラムを作ってみました。といっても、マウスがあるわけでもなく、ただWindows上のCアプリで迷路データから経路を探るプログラムを書いてみただけです。キャプチャー画像は、そのプログラムに2011年マイクロマウスの予選迷路を入力して、どんな結果が出るかを見てみたものです。
マップデータは、こちらのサイトを参考にさせて頂きました。

プログラムは、スタックを使って再帰呼び出しを行うアプローチと、スタックに途中経過を頼らず、1ステップごとに確定データで解いていく方法があるように思います。もちろん、もっとすごいアルゴリズムがあるのかもしれません。たぶん、前者はメモリがふんだんにある場合には速度的に有利で、後者は使用メモリ量が抑えられる代わりに速度的に不利なのではないかと思います。プログラムは後者で書いただけなので、比較試験を行ったわけではありません。あくまで想像です。

//
//	ルート検索
//
int map_calcr(void )
	{
	int i,x,y;

	// ステップデータエリアを全て1(=最大値)にする
	for (y = 0;y < MAPMY;y++)
		{
		for (x = 0;x < MAPMX;x++)
			{
			setsd(x,y,MD_STEP);
			}
		}

	// スタート位置のステップ番号を0にする
	setsd(MSSX,MSSY,0);

	// ステップスキャン
	for (i = 0;i < MAPMX * MAPMY;i++)	// ステップ数は最大でも全マス数
		{
		for (y = 0;y < MAPMY;y++)
			{
			for (x = 0;x < MAPMX;x++)
				{
				if (getsd(x,y) == i)	// 当該ステップ番号を発見
					{
					if (chkwall(x,y,WALL_N)==0)	// 北側に壁がない
						{
						if (getsd(x,y+1) > i) setsd(x,y+1,i+1);	// 新しいステップ番号を登録
						}
					if (chkwall(x,y,WALL_S)==0)	// 南側に壁がない
						{
						if (getsd(x,y-1) > i) setsd(x,y-1,i+1);	// 新しいステップ番号を登録
						}
					if (chkwall(x,y,WALL_E)==0)	// 東側に壁がない
						{
						if (getsd(x+1,y) > i) setsd(x+1,y,i+1);	// 新しいステップ番号を登録
						}
					if (chkwall(x,y,WALL_W)==0)	// 西側に壁がない
						{
						if (getsd(x-1,y) > i) setsd(x-1,y,i+1);	// 新しいステップ番号を登録
						}
					}
				}
			}
		// ここで、1ステップ分の処理完了
		if (getsd(MSGX,MSGY) < MD_STEP) break;		// ゴールにたどり着いた
		}

	return i;	// ステップ数を返す
	}

実質的なコードはこれだけです。各ステップごとにXYスキャンを行うので、速度は結構かかると思います。(27行にあるif文が真となる確率が極めて低くなります。)

本当に稼動しているマイクロマウスは、どんなプログラムで動いているんでしょうね。

プログラムダウンロード
VisualC++2010 のコマンドプロンプトでコンパイル・実行確認済み
たぶん、Unixでもコンパイル&実行できると思います。

← Previous