クラシックマウス 作ってみた その8 足立法

はじめに

• 作成したクラシックマウスの解説。
• 今回は機体に実装した足立法の解説です。その７（座標の設定）と合わせてお読みください。
• 機体写真、動画などは「その1」をご参照。

足立法の考え方

ゴールからの最短歩数を数える、と言っても具体的な方法を考えないとプログラムは書けない。
自分なりに以下のような作業で最短歩数を考えてみました。

• まずゴールを0として、0の隣にある区画を1とする。ただし壁がある場合は進めないので壁がない場所だけ1とする。これを0の場所すべてで行う。
• 次に1の場所の隣を2とする。同じように壁のないところだけ2とする。ただし、もともと0や1が書いてあったらそのままとする。これをすべての1の場所で行う。
• 次に同じように2の隣で壁のないところを3とする。ただし、すでに2以下が書いてあったらそのままとする。これをすべての2の場所で行う。
• これを繰り返す。歩数の最大値は16*16-1(=255)なので、255の区画まで行えばよいことになる。実際には255になる前に全ての区画が書き込まれる場合がほとんどだと思いますが。
• これで足立法での歩数MAPができあがることになります。

プログラムの書き方

上の考え方をプログラムにした時のポイント。

• まず、歩数の初期値ですが、ゴールの場所はもちろん0ですが、その他の場所は最大値(255)としています。これはプログラムを簡素化するための工夫です。
• 0の場所はわかっていますが、1の場所がどこにあるかはわからない（目で見ればわかりますが）。なので、すべての場所を順番に見て、その場所が1であれば作業をする、ということにしています。プログラム上は0かどうかから始めているので、ゴールの場所が変わっても対応可能。
• 作業は簡単で、自分の区画の周囲の壁を見て、壁が無ければ、その向こうの区画に一つ大きい数字を書き込むだけです。ただし、その際にすでに小さな数が書いてあれば更新する必要はありません。プログラム上はmin(すでにかいてある数字,一つ大きな数字）を書き込むことにしています。初期値が最大値なので、これで同じ結果となります。
• これを0から始めて、255まで行えばよいことになります。プログラム上は以下の形です。
  • (0,0)から(0,15)までの間に0があれば、作業をする。
  • (1,0)から(1,15)までの間に0があれば、作業をする。
  • 以下(15,15)までの間に0があれば作業をする。
  • もとに戻って1の場所があれば作業をする。
  • これを255の場所まで繰り返す。
  • 以上の作業をfor文とif文で表現しています。
• 作業は4つのif文です。周囲の壁情報と隣の座標はわかっているので、「壁情報が0なら、隣の区画にmin(現在の歩数、一つ大きな歩数）を書き込む」という内容を4つの方向に行っています。
• 実はひとつ懸念していた点がありました。端の区画（例えば(15,1))の場合、if文の中にs[16][1]が出てくることになります。ところが、s[16][1]は宣言外の配列です。これを心配していたのですが、実際にはかならず壁があるので、s[16][1]が参照されることはないのでエラーにならないようです。
• 結果的に、足立法のコードは意外と簡単なコードになりました。for文が３つ入れ子になっているので、繰り返しは多いですが、逆に言うとそれしかない感じです。
• なお、本機のプログラムでは、壁情報が更新されるたびに、歩数情報を全てリセットして足立法を適用しています。つまり、一区画進むたびに、最初からやり直していることになります。部分的な更新でも良い気もしたのですが、どうも上手く整理できませんでした。
• 壁情報が同じであれば、やり直す必要はないわけですが、その判定をするのも面倒なので、一歩進むたびに足立法を更新しています。

コード

• 実際のスケッチを下においてあります。
  • void step_update() として関数になっています。
  • MAPは「2022　関西地区　クラシックマウス」のものを使っています。画像ご参照。
  • シリアルモニターに結果が表示されます。
  • MAPで閉じているところは、探索が行われず、255のままになっていることがわかると思います。
• 処理時間は計測していないのですが、あまり気にならない程度の時間で処理できているようです。

const uint8_t m_gyou = 16;   //最大16*16　超えるときはs[][]の型を要検討
const uint8_t n_retu = 16;

uint8_t s[m_gyou][n_retu];

//各区画の上の壁情報//
bool wu[m_gyou+1][n_retu]= {
  {1,1,1,1,1,1,1,1,1,1,1, 1, 1, 1, 1, 1},
  {0,1,1,1,0,1,1,1,0,0,1, 0, 1, 0, 1, 0},
  {0,0,1,0,0,0,1,0,0,0,0, 0, 1, 1, 0, 0},
  {0,0,1,1,0,0,0,0,0,0,1, 0, 1, 0, 0, 0},
  {1,1,1,0,0,0,0,0,0,1,1, 1, 1, 0, 1, 0},
  {1,1,0,0,0,0,0,0,0,1,1, 0, 1, 0, 0, 0},
  {1,1,1,0,0,0,1,0,0,0,1, 0, 0, 0, 0, 0},
  {1,1,0,1,1,1,0,1,1,0,0, 0, 0, 0, 0, 0},
  {0,1,0,0,1,1,1,0,0,0,0, 0, 0, 0, 0, 0},
  {1,1,0,0,0,1,0,1,1,0,0, 0, 0, 0, 0, 0},
  {0,1,1,0,0,0,0,0,0,0,1, 0, 0, 0, 0, 0},
  {1,0,1,0,0,0,0,0,0,1,1, 0, 1, 0, 0, 0},
  {1,1,1,0,0,0,0,0,0,1,1, 1, 1, 1, 1, 0},
  {0,1,0,1,0,0,0,0,0,0,1, 0, 1, 0, 0, 0},
  {0,0,0,0,0,1,1,0,0,0,0, 0, 1, 1, 0, 0},
  {0,0,1,0,0,0,1,1,0,0,1, 0, 1, 0, 1, 0},
  {1,1,1,1,1,1,1,1,1,1,1, 1, 1, 1, 1, 1}};
//{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}

//各区画の左の壁情報//
bool wl[m_gyou][n_retu+1]= {
  {1,0,0,0,0,0,0,0,0,0,0, 0, 0, 0, 0, 0, 1},
  {1,1,1,0,1,1,0,0,1,1,1, 1, 1, 1, 0, 1, 1},
  {1,1,1,0,1,1,1,1,1,1,1, 1, 0, 0, 1, 1, 1},
  {1,0,0,0,1,1,1,1,1,1,0, 1, 0, 1, 1, 0, 1},
  {1,1,0,1,1,1,1,1,1,0,0, 1, 0, 1, 0, 1, 1},
  {1,1,0,1,1,1,1,1,1,1,0, 0, 0, 1, 1, 1, 1},
  {1,0,0,0,1,0,1,0,1,1,1, 1, 1, 1, 1, 0, 1},
  {1,0,0,1,0,0,0,1,0,0,1, 1, 1, 0, 1, 1, 1},
  {1,0,0,1,0,0,0,1,0,1,1, 1, 1, 1, 1, 1, 1},
  {1,0,0,0,1,1,1,0,0,1,1, 1, 1, 1, 1, 1, 1},
  {1,1,0,0,1,1,1,1,1,1,0, 0, 1, 1, 1, 1, 1},
  {1,1,0,0,1,1,1,1,1,0,0, 1, 0, 0, 0, 1, 1},
  {1,0,0,0,1,1,1,1,1,1,0, 0, 0, 1, 1, 1, 1},
  {1,1,1,1,1,1,0,0,1,0,1, 1, 0, 0, 1, 0, 1},
  {1,1,1,0,1,1,0,0,1,1,1, 1, 1, 1, 0, 1, 1},
  {1,1,0,0,1,0,0,0,0,1,0, 0, 0, 0, 1, 1, 1}};
//{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}

const uint8_t goal_gyou1 = 7,goal_retu1 = 7; //GOALの座標
const uint8_t goal_gyou2 = 7,goal_retu2 = 8; //GOALの座標
const uint8_t goal_gyou3 = 8,goal_retu3 = 7; //GOALの座標
const uint8_t goal_gyou4 = 8,goal_retu4 = 8; //GOALの座標

void setup() {
  Serial.begin(9600);
  // put your setup code here, to run once:

Serial.println("start");
step_update(); 
Serial.println("end");
}

void loop() {
  // put your main code here, to run repeatedly:

}

void step_update(){
//s[][]をリセット
for (int i = 0; i < m_gyou; i++) {
    for (int j = 0; j < n_retu; j++) {
      s[i][j] = m_gyou * n_retu -1;
    }
 }
s[goal_gyou1][goal_retu1]=0;  // GOAL設定！！
s[goal_gyou2][goal_retu2]=0;  // GOAL設定！！
s[goal_gyou3][goal_retu3]=0;  // GOAL設定！！
s[goal_gyou4][goal_retu4]=0;  // GOAL設定！！
 
 for(int k=0; k<m_gyou * n_retu; k++){
  for(int i=0; i< m_gyou; i++){
   for(int j=0; j< n_retu; j++){
    if(s[i][j]==k){
     if(wu[i][j]==0){s[i-1][j]=min(s[i-1][j],k+1);}
     if(wu[i+1][j]==0){s[i+1][j]=min(s[i+1][j],k+1);}
     if(wl[i][j+1]==0){s[i][j+1]=min(s[i][j+1],k+1);}
     if(wl[i][j]==0){s[i][j-1]=min(s[i][j-1],k+1);}
     }
    }
  }
 }

 for (int i = 0; i < m_gyou; i++){
  for (int j = 0; j < n_retu; j++){
   Serial.print(s[i][j]);
   Serial.print("\t");
   }  
 Serial.println();
 }

}

以上