プログラム解説 左手法

追記 - バグだらけだったので少し直しました。今までのコードをまとめているので、まとまったらまたどこかに貼ります。
データストラクチャーが大体まとまってきたので、次は迷路抜けのアルゴリズムです。
まずは基本的な左手法から。 
前回、ロボットの方角をuint8_tで保存しました。
方角は、North = 0, East = 1, South = 2, West = 3 と数字を振り当てると簡単に使えます。
なので、
#define NORTH 0
#define EAST 1
#define SOUTH 2
#define WEST 3
と宣言しておきましょう。
方角に数字を振り当てることで、
if(!d) {
  d = WEST;
} else {
  d--;
}
と簡単にロボットを左に回したり、
d++;
d %= 4;
とロボットを右に回したりできます。

これを使って、
uint8_t d_turn_left(uint8_t d) {
  if(!d) {
    return WEST;
  } else {
    return (d - 1);
  }
}

uint8_t d_turn_right(uint8_t d) {
  d++;
  return d % 4;
}

void solve_maze(void) {
  uint8_t d = robot.d;
  uint8_t x = robot.x;
  uint8_t y = robot.y;
  d = d_turn_left(d);
  uint8_t found_new_tile = 0;
  for(int i = 0; i < 3; i++) {
    switch(d) {
    case NORTH:
      if(!get_tile_visited(x, y + 1) && !get_north_wall(x, y)) {
        found_new_tile = 1;
        turn_to_new_tile(i);
      }
      break;
    case EAST:
      if(!get_tile_visited(x + 1, y) && !get_east_wall(x, y)) {
        found_new_tile = 1;
        turn_to_new_tile(i);
      }
      break;
    case SOUTH:
      if(!get_tile_visited(x, y - 1) && !get_south_wall(x, y)) {
        found_new_tile = 1;
        turn_to_new_tile(i);
      }
      break;
    case WEST:
      if(!get_tile_visited(x - 1, y) && !get_west_wall(x, y)) {
        found_new_tile = 1;
        turn_to_new_tile(i);
      }
      break;
    }
    if(found_new_tile) {
      break;
    }
    d = d_turn_right(d);
  }
  if(!found_new_tile) {
//    find_next_unvisited();
  } else {
    move_forward_tile();
  }
}


こんな感じで簡単な左手法ができます。
この左手法は普通のとは違いもう通過済みのタイルにはいきません。
こうすることて同じところをぐるぐる回るのは回避できます。
ただ、これだけだとコの字などのタイルで止まってしまいます。
なので、次の通過していないタイルへの最短距離を求めないといけません。
ちなみにmove_forward_tile()はロボットを1タイル前進させます。
   

プログラム解説 ロボット情報

前回は迷路の情報を保存しましたが、ロボットの現在地、チェックポイントなどなど他の情報の管理については書きませんでした。
ロボットの情報を記録するには一番簡単な方法はstructを使うことだと思います。
今回保存したい情報は
ロボットのx,y座標、チェックポイント、スタートタイル、ロボットの方角です。
ここで使うのはtypedef structです。
typedef struct {
  uint8_t x;  // x座標
  uint8_t y;  // y座標
  uint8_t d;  // ロボットの方角 
  uint8_t last_checkpoint_x;  // チェックポイントのx座標
  uint8_t last_checkpoint_y;  // チェックポイントのy座標
  uint8_t start_tile_x;  // スタートタイルのx座標
  uint8_t start_tile_y;  // スタートタイルのy座標
} robot_state; 
structはデータを簡単にまとめれるので便利です。
データを使うには、
robot_state.x などとrobot_stateの後に . とデータ名を書くだけです。
このようにデータをまとめることによって、関数内で渡すにしても、グローバル変数として使うとしても、間違って使うことが少なくなります。
例えば、x座標をグローバル変数で 
uint8_t x;
と宣言しても何のxなのか分かりづらいです。プログラムが大きくなっていくので、しっかりと最初にデータのストラクチャーを決めることは大切です。

なので、こんな感じでロボットの情報を一箇所にまとめることで、後々使う時に色々間違いが少なつなっていくはずです。
最初は面倒でも、最終的には役に立つので(ポインタなどを使い始めると)データをまとめる時はstructを使いましょう。 

プログラム解説 マップメモリ

ロボカップが終わって少し経ちましたが、今年のロボットはハードよりもプログラムの方に気合が入っています。
また、レスキューメイズのアルゴリズムなのは基本的に秘密主義というかあまり公開されているものが少なく(teamohnenameぐらいですかね) しかも複雑なので初心者には厳しい競技です。
しかもロボカップの迷路抜けアルゴリズムは有名なTremauxアルゴリズムが使えなかったり(確か広い空間があるとTremaux法はうまくいかないので)色々試行錯誤しないといけません。
また、レスキューラインと違い膨大な量のデータをArduinoやNXT、EV3などに保管しないといけないので色々メモリの整理が難しくなっていきます。

なので一番最初に必要なメモリの整理について書いていきます。(ちなみに詳しいことは色々長くなるので省きます、もしも解説が欲しい方はコメントで質問してください)
まずは、ロボットやパソコンがどのように数字をデータとして保存しているかについて。
パソコンはデータをすべて0と1で保管しています。
数字もこのように保管されているため
int x = 0; 
とArduinoに書き込むと(確かintは32ビットだったので)
0000 0000 0000 0000 0000 0000 0000 0000
と32個の0で表されます。ちなみに1は
0000 0000 0000 0000 0000 0000 0000 0001 という感じです。
2進法なので-2^31 ~ (2^31 - 1)までの数字を表せます(-2,147,483,648 ~ 2,147,483,647)
まあ、プログラムで使う大体の数字は32ビットあれば表せます。
マイナスなどは色々な表せ方がありますが確か2の補数表示が使われているはずです。
説明が面倒なので、省きますが0を1度しか表さない表示方法なので人気です。(他の表示方法の場合0を2回表す場合があるので)
ともかくパソコン上のデータは全部このようにビットで保管しています。
少し脱線しましたが、話を戻すとマップをデータとして保管する場合
-タイルの情報(通過済み、黒タイルかどうが)
-壁情報(どこに壁があるか、被災者がどの壁にいるか)
などなどを保管しなくてはいけません。
このデータは簡単に2次配列で表せます。
2次配列は
#define MAP_SIZE_X 30
#define MAP_SIZE_Y 30
uint16_t maze_data[MAP_SIZE_X][MAP_SIZE_Y];

という感じで2次配列を作れます。
今回は30x30の迷路のデータを保管できる分の2次配列を作りました。
ちなみにuint16_tとは16ビットの自然数です、まあなぜ16ビットなどは後ほど。
ここで注意したいのはこの2次配列の中身です。
何も入れていないので0が入っている気が最初はしますが、実際は何が入っているかは全くわかりません。
なので、使う際は必ず 0などに上書きしましょう。
すべての数字を0にしたい場合
memset(maze_data, 0, sizeof(maze_data[0][0]) * MAP_SIZE_X * MAP_SIZE_Y);
と前のデータを書き換えましょう。
ここでややこしいですが、memsetはmaze_dataポインターからsizeof(maze_data[0][0]) (2バイト)* 30 * 30 = 1800バイトを0に変えていきます。なので数字の型がint8_tだろうがuin16_tだろうが8ビット、1バイトずつ変えていきます。なので、0以外の数字をuint16_tの配列で設定したい場合は
for(int y = 0; y < MAP_SIZE_Y; y++) {
  for(int x = 0; x < MAP_SIZE_X; x++) {
    maze_data[x][y] = 1;
  }
}
とこんな感じで設定していきましょう(1を好きな数字に変えてください)

こんな感じで、0がたくさんありますが、これでは意味がありません。
最初は簡単に壁、タイル、被災者の情報を入れていきましょう。
ここで最初に、壁について
壁のデータを1つのタイルごとに4つ設定していくと色々もったいないことになります。
なぜかというと隣接しているタイルは必ず同じ壁情報を使います。
なので、もしも各タイルで4つの壁情報を保管すると約2倍の数の壁のデータを保管しないといけません。これはもったいないですよね。
なので、初めにロボットを置いた方向をNorthとすると、SouthとWestの壁情報だけを保存します。
2つの壁だけを各タイル保存していくことによって、一番上の行と一番右の列のタイルが使えませんが、他のタイルの壁情報を半分に出来るのでまあ安上がりです。
被災者情報は各タイルに4つの方向すべてに必要です、なぜなら壁の面を見ているので。
一つの壁の両面に被害者がいる場合もあるので。
また、タイル情報は2つで1つは突破済みか、もう一つは黒タイルかどうかです。
チェックポイントは他の場所で保管するのがオススメです(毎回変わっているので)

色々書きましたが、まだデータの保存方法について書いていませんね。
今回保存するデータはすべて2択です。
壁がありますか?被害者はこの壁にいますか?このタイルは突破済みですか?
と答えがYes or Noつまり0と1です。
0と1を保存するのはコンピューターが得意なことです。
2択の質問の答えをintやboolで保存するのはメモリがもったいないです。
boolはtrue, falseしか保存しませんが、1バイトのデータを取ります。
ここで、このデータを全部boolで表したとしましょう。
今回は8つのデータを保存しているので8*8*30*30 と7200バイト取ります。
Arduino Unoは32000バイトあるので全然足りますが、他のデータを保存したり、またこのマップデータは 2階建ての迷路の場合2倍の容量を取るので、できるだけデータの使用量は抑えたいところです。
ここで使えるのはビット演算です。
ビット演算とはビットを直接いじることによって例えばuint16_tの場合16個の2択のデータを保存できます。もちろん3択4択の質問の答えなども色々使い方次第では保存できます。
で今回使うビット演算ですが使い方は簡単で
#define WEST_WALL_MASK      0x0001u
#define SOUTH_WALL_MASK    0x0002u
#define WEST_VICTIM_MASK    0x0004u
#define SOUTH_VICTIM_MASK  0x0008u
#define EAST_VICTIM_MASK     0x0010u
#define NORTH_VICTIM_MASK  0x0020u
#define TILE_VISITED_MASK     0x0040u
#define BLACK_TILE_MASK       0x0080u

という感じでマスクを作ります。右の数字はHEX表記です、まあバイナリーを書きやすくしたようなものです。
この数字は特別で、どれもバイナリ表記に直すと1が1つしかありません。しかも全部1つずつ左に1がずれています。
なのでこんな感じの関数を作ると(ちなみにポインタでマップデータをグローバル変数でなくメインのローカル変数に設定できますが、ポインタの説明を省きたいので)
void set_south_wall(uint8_t x, uint8_t y, uint8_t val) {
  if(val) {
    maze_data[x][y] |= SOUTH_WALL_MASK;
  } else {
    maze_data[x][y] &= ~SOUTH_WALL_MASK;
  }

こんな感じでmaze_dataのsouth_wallをセットできます。
valは壁を消したい場合0、壁を追加したい場合0以外の数字を入れてください。
C言語は0以外の数字をtrueと扱ってくれるので。逆に0はfalseです。
なので、if(val) などif条件に数字を入れても平気です。
ここで使った&=や|=はショートカットで
本当は、
maze_data[x][y] = maze_data[x][y] & SOUTH_WALL_MASK;
などになります。
&はbitwise AND で | は bitwise OR
です。日本語ではよくわからないので気になる人は調べてください。
こんな感じで、似たようなのを全部のデータように作りましょう。
set_north_wallとset_east_wallは少し工夫が必要です。
void set_north_wall(uint8_t x, uint8_t y, uint8_t val) {
  if(y + 1 >= MAP_SIZE_Y) {
     return;
  }
  if(val) {
    maze_data[x][y + 1] |= SOUTH_WALL_MASK;
  } else {
    maze_data[x][y + 1] &= ~SOUTH_WALL_MASK;
  }

という感じで1つ上のタイルのsouth_wallを設定することで擬似的にnorth wallをセットできます。
この際、間違ってもマップ以上のデータを書き込まないように最初の条件文を入れておきましう。
また、似た感じでset_east_wallも作れるはずです。
 
これで、データを色々セットできますが次は読み込んでみましょう。
 
uint8_t get_south_wall(uint8_t x, uint8_t y) {
  return maze_data[x][y] & SOUTH_WALL_MASK;
}

はいこれだけです(笑)
セーブするよりもずっと簡単です。
この関数の返す値は
壁がない場合→0
壁がある場合→SOUTH_WALL_MASKの値
なので、0と1ではありません。けれど、先ほど書いたようにC言語では0以外の数字はtrueと扱われます。なので、返す値が0以外ならなんでもいいんです。
こんな感じで、他の関数も完成させていきましょう。
get_north_wallやget_east_wallはさっき書いたように1つずれたタイルの情報を読めばいいです。

こんな感じでビット演算を使うことによってとってもコンパクトにデータを保管できます。もちろん今回は8つのデータしか保存しなかったのでuint8_tの配列でもいいですが、まあもっと色々な情報を保存したいときの場合ように今回はuint16_tを使いました。
uint16_tを使う場合2バイト* 30 * 30 =1800バイト、boolを使った場合の4分の1です。
また、uint8_tを使えば8分の1のデータ量ですみます。
色々急ぎ足の解説でしたが、もしも質問などがあったらコメントで、できる限り説明します。 
livedoor プロフィール
アクセスカウンター

    最新コメント