迷路の最短経路から雷の軌跡をモデル化する

こんにちは。
前回も書いたように、迷路を使って雷の軌跡をモデル化します。

前回の記事はこちらです。

taq.hatenadiary.jp

迷路の準備
最短経路の探索→雷のモデル化
まとめ
参考

迷路の準備

まずは迷路を用意します。

前回の方法に従って、迷路を生成し、書き出しておきます。

taq.hatenadiary.jp

最短経路の探索→雷のモデル化

ねらいは雷の軌跡なので、始点は決まっていても終点は決めません。
そして、始点（雲）から最下点（地面）までの距離が最も短いものを答えとします。

これを求めるのは前回紹介したような、行き止まりを埋める方法ではできそうになかったので、別の方法を採用します。

「幅優先探索」と呼ばれる、同時に全ての経路を試していく方法です。

流れとしては、
①幅優先探索で上から下までの最短経路を探し、下に着いたときのiを保存
②最短経路以外を塗りつぶす
という感じです。

回りくどい感じはしますが、絵が完成すればよいということにして目をつぶります。

Table t;
int n;
float len;
int[][] c;
boolean findRoute = false;
boolean initialize = false;
IntList endi = new IntList();

void setup(){
  size(700, 700);

  t = loadTable("maze.csv");
  n = t.getRowCount();

  c = new int[n][n];

  len = width/float(n);

  for(int i = 0; i < n; i ++){
  for(int j = 0; j < n; j ++){
    c[i][j] = t.getInt(j, i);

    if(c[i][j] == 0){ fill(255); }
    else if(c[i][j] == 1){ fill(0); }
    stroke(230);
    rect(i*len, j*len, len, len);
  }
  }
}

void draw(){
  if(findRoute == false){
    //幅優先探索
    c[ceil(n/2)][1] = 2; //始点
    
    for(int i = 1; i < n-1; i ++){ //全範囲について
    for(int j = 1; j < n-1; j ++){
      //そこが道で、周りに2（雷の軌跡候補）があれば
      if(c[i][j] == 0 && (c[i-1][j] == 2 || c[i+1][j] == 2 || c[i][j-1] == 2 || c[i][j+1] == 2)){
        c[i][j] = 2; //そこも2にする
      }
    }
    }
  }

  //終点の保存
  for(int i = 1; i < n-1; i ++){ 
    if(c[i][n-2] == 2){ //一番下の行で2になったところがあれば
      endi.append(i); //そのiを保存
      
      findRoute = true; //最短経路が見つかった
    }
  }

  //盤面の描画
  for(int i = 0; i < n; i ++){
  for(int j = 0; j < n; j ++){
    if(c[i][j] == 0){ fill(255); }
    else if(c[i][j] == 1){ fill(0); }
    else if(c[i][j] == 2){ fill(255, 255, 0); }
    stroke(230);
    rect(i*len, j*len, len, len);
  }
  }

  if(findRoute == true){ //最短経路が見つかったら
    if(initialize == false){
      //盤面を初期化
      for(int j = 1; j < n-1; j ++){
      for(int k = 1; k < n-1; k ++){
        c[j][k] = t.getInt(k, j);

        initialize = true; //初期化完了
      }
      }
    }
    else{ //初期化できたら
      //始点と終点を結ぶ経路以外を塗りつぶす
      for(int i = 1; i < n-1; i ++){
      for(int j = 1; j < n-1; j ++){
        int z = c[i-1][j] + c[i+1][j] + c[i][j-1] + c[i][j+1];
        
        if(z >= 3){
          c[i][j] = 1;
        }

        //スタートとゴールは常に0（道）
        c[ceil(n/2)][1] = 0;
        c[endi.get(0)][n-2] = 0;
      }
      }
    }
  }
}