マッピング、とか - 地面。's Note

ソフトウェアの概要のところで丸投げしたマッピングと移動方向判断についてのことを書いていきます。(マッピングのことはまだです(殴))

ソフトウェア概要のところで書いたように、pallasのロボットは進行方向の判断材料に”各タイルの通った回数”と”優先して進む方向”を用意し、それらを使って拡張右手法を使った探索をしています。

”優先して進む方向”はあらかじめ右→前→左の順に優先して進む、とプログラムに書いて置けるのですが、”各タイルの通った回数”はロボットが移動するごとに変わるのであらかじめ書いておきようがありません。

そのためロボットは移動するときに ”各タイルの通った回数”を記録し、必要なときに読み出して比較したりしています。
"各タイルの通った回数"はそのタイルの座標と紐付いていないといけないので、座標と"各タイルの通った回数"を一緒に保存します。
また、ちょっとした嬉しいこと*1があるのでpallasでは床の色(白/銀/黒)も同時に保存しています。

実装は適当に

struct node{
  short x,y; //座標
  short count; //何回通ったか
  char tilecolor; //タイルの色
};

node nodeArr[100];

こんな感じで。
一つ一つのタイル(ノード)情報を構造体にまとめてそれを一次元配列で大量に用意します。(1回の競技で100タイル以上の広さなんてないよね.....??)

ロボットは移動する前に、次に移動可能なタイルのノードがすでに作成されてるかを検索し、もしすでに作成されていた(つまり通ったことがある)ならばそこの通った回数を比較し、移動方向を決定します。

移動方向決定はこんな感じ

task read_judge(){

  Wall_L=getWall(LEFT);
  Wall_C=getWall(CENTER);
  Wall_R=getWall(RIGHT);
  underColor=getUnderColor(LightSensor);


  if(us_l<=Thre){//壁のあるなし判定
      leftNode=255;//〇〇Nodeはその方向のノードの通った回数を入れる変数。
  }//実際の壁があれば255を入れる
  else{
      leftNode=searchNode(IsNewNode,sL)://この関数は指定した方向の
  }//ノードの通った回数を返す

  if(us_c<=Thre){
      centerNode=255;
  }
  else{
      centerNode=searchNode(IsNewNode,sC):
  }

  if(us_r<=Thre){
      rightNode=255;
  }
  else{
      rightNode=searchNode(IsNewNode,sR):
  }
  if(underColor==SILVER){//チェックポイントの処理
      //checkPoint
  }
  else if(underColor==BLACK){//黒タイル。そのままバック
      moveAngle=GOBACK;//go back
  }
  else if(rightNode==255 && centerNode==255 && leftNode==255){//行き止まり
      moveAngle=GORETURN;//turn around//クルッと回って引き返す
  }
  else if(rightNode<=centerNode){//右のノードのほうが通った回数が少ない
      moveAngle=GORIGHT;//go right
      }
      putInZahyo(robot1);//現在位置更新用関数
  }
  else if(centerNode<=leftNode){
      moveAngle=GOFWD;//go fwd
      putInZahyo(robot1);
  }
  else{
      moveAngle=GOLEFT;//go left
  }

}

雑なプログラム&怪しい英語はお許しください

こんな感じで実装することで、最も通った回数の少ない方向へ進む&右を優先する動きになります。

補足 : 拡張右手法を使う理由

ただの右手法だとこの図のように赤く表示したタイルを通ることができません。
そうするともしこの赤タイルのところに被災者がいると発見できないため、拡張右手法を使います。

拡張右手法だと下図のように赤タイルも通ることが出来るので全探索をすることができます。
この図のマップでは緑のタイルでの動きがポイントになっています。
一回目に通るとき(赤矢印)は普通に右に沿って進みますが、二回目(青矢印)は進行方向に対して右と正面を一度通っているため左に曲がります。
そして三回目は左右正面どれも一度通っているため右を優先して進む動きになっています。

質問は僕のツイッターかコメント欄までお気軽にどうぞ～

*1:同じ黒タイルに二度突っ込まずにすむ