読者です 読者をやめる 読者になる 読者になる

hantas's blog

ブログ移転しました→ http://blog.taniho.net/

壁情報の記録

マイクロマウスは壁情報を記録しながら走行し,その壁情報から最短経路を導出する競技なわけですが,さてこの壁情報はどうやって記録すべきなのでしょうか。

少なくともサークル内では次に紹介されている記録方法が主流なようです。
座標系・迷路表現の定義 | マイクロマウス委員会 関西支部

要約するならば,

迷路の各マスごとに次の8ビットの情報を持っている
・マスに隣接する壁の有無(4方向4ビット)
・マスに隣接する壁の到達情報(4方向4ビット)

といったところでしょうか。
したがってクラシックサイズの迷路を格納する場合,
8ビット × 縦16マス × 横16マス = 2048ビット(256バイト)
ものメモリ領域を食いつぶします。

今回は今作で採用している壁情報の記録法を簡単に紹介しておきます。
(そんな大げさなことじゃないですが,この方法をサークル内に普及させることが必要に感じたのでまとめています)
考え方は単純で,

外周の壁を除いた各壁1枚ずつに1ビットを割り当て,存在情報を記録する
各マスに1ビットを割り当て,到達情報をマスごとに記録する

といった感じです。
この格納法の場合,
|壁が1列に16枚 × 15列 + ー壁が1列に16枚 × 15列 + 縦16マス × 横16マス = 736ビット(92バイト)
のメモリ領域で話が済んでしまいます。
(前述した方法のおよそ35%の使用量)

具体的には次のクラスを作成しました。
(実際の実装は少し異なっています)

class Map{
private:
	/**
	 * @brief 一番上の壁がMSB,一番下の壁がLSB,左から順
	 */
	unsigned short column[15];

	/**
	 * @brief 一番左の壁がMSB,一番右の壁がLSB,下から順
	 */
	unsigned short row[15];

	/**
	 * @brief 一番左のマスがMSB,一番右のマスがLSB,下から順
	 */
	unsigned short reached[16];

	/**
	 * @brief マウスから見たWalldataを絶対方向に変換します
	 * @param wall 変換元の壁情報
	 * @param ang マウスの向いている方向
	 * @return 変換後のWalldataを返します
	 */
	Walldata rotateWallToAbsolute(Walldata wall, EMouseAngle ang);

	/**
	 * @brief 絶対方向のWalldataをマウスから見た方向に変換します
	 * @param wall 変換元の壁情報
	 * @param ang 変換したい方向
	 * @return 変換後のWalldataを返します
	 */
	Walldata rotateWallToRelative(Walldata wall, EMouseAngle ang);

public:
	Map();

	/**
	 * @brief 迷路データを初期化する
	 */
	void resetMap();

	/**
	 * @brief 到達マップを初期化する
	 */
	void resetReachedMap();

	/**
	 * @brief 壁を追加します
	 * @param x 壁を追加する区画のx座標
	 * @param y 壁を追加する区画のy座標
	 * @param angle 今自分が向いている絶対方向
	 * @param wall 今見えている壁情報
	 */
	void addWall(int x, int y, EMouseAngle angle, Walldata wall);

	/**
	 * @brief 壁を設定します
	 * @param x 壁を追加する区画のx座標
	 * @param y 壁を追加する区画のy座標
	 * @param angle 今自分が向いている絶対方向
	 * @param wall 今見えている壁情報
	 */
	void setWall(int x, int y, EMouseAngle angle, Walldata wall);

	/**
	 * @brief 壁を追加します。絶対方向でのみ指定が可能です。
	 * @param x 壁を追加する区画のx座標
	 * @param y 壁を追加する区画のy座標
	 * @param angle 今自分が向いている絶対方向
	 */
	void addSingleWall(int x, int y, EMouseAngle angle);

	/**
	 * @brief 壁を設定します。絶対方向でのみ指定が可能です。
	 * @param x 壁を追加する区画のx座標
	 * @param y 壁を追加する区画のy座標
	 * @param angle 今自分が向いている絶対方向
	 * @param wall 今見えている壁情報
	 */
	void setSingleWall(int x, int y, EMouseAngle angle, int wall);

	/**
	 * @brief 絶対方向から見て壁があるか確認します
	 * @param x 壁を追加する区画のx座標
	 * @param y 壁を追加する区画のy座標
	 * @param ang 今自分が見ている絶対方向
	 * @return 壁が存在したら1,なかったら0を返します
	 */
	int isExistWall(int x, int y, EMouseAngle ang);

	/**
	 * @brief 到達マップを設定します
	 * @param x 到達設定する区画のx座標
	 * @param y 到達設定する区画のy座標
	 */
	void setReached(int, int);

	/**
	 * @brief 到達したか確認します
	 * @param x 到達確認する区画のx座標
	 * @param y 到達確認する区画のy座標
	 * @return 到達していたら1,していなかったら0を返します
	 */
	int hasReached(int, int);

	/**
	 * @brief =演算子のオーバーロード。Mapクラスを代入します
	 */
	Map& operator= (Map tmp);

	~Map();
};

Walldata,EMouseAngle型は触れていませんが,適宜置き換えてください。
概ね上記の通りに実装すれば,それなりに使えると思います。

一応サークルの人(主に初めてプログラムを書く人)向けに補足を入れておきます。

  • 今回作成したメンバ変数(グローバル変数として宣言したかもしれません)は,用意したメンバ関数(関数)以外からアクセスすべきではありません。とりわけ,今回のメンバ変数は直感的に操作できなさそうです。直感的に扱えないような変数を直感的に扱うために,メンバ関数を作成しました。したがって迷路情報を書き換えるときは必ずこのメンバ関数を利用することになります。
  • このMapクラスは迷路情報の格納と操作のみを任されたクラスです。それぞれのクラス・変数・関数の担う範囲をよく考えてコードを書いてください。例えば,マウスのセンサ情報をこのクラス内で扱う必要は一切ありません。
  • この設計では,迷路の外周壁データは用意していません。従って,外周壁を読み書きするように求められた場合は例外処理を書く必要があります。配列の範囲外アクセス,ダメ,絶対
  • 実際に使用する際はaddWall関数を呼び出しています。しかし,3枚の壁情報を同時に格納する良い方法が思いつかなかったので,内部的にaddSingleWall関数を3回呼び出しています。

他の人がどうやって迷路情報を保存しているのか全然知らないので,意見などお待ちしています。