プログラミングの備忘録

プログラムをつくる過程を残すもの

processingの備忘録 -迷路-

こんにちは。
今回は、processingで迷路を作る、という題でやっていきます。


なんで迷路?と思われるかもしれませんが、それはこんなツイートを見つけたからです。


「数学を愛する会」さんのツイートは面白いものが多くて結構好きです。
(ケーキの切り方選手権はみなさんも知っているかもしれません。)

その中で、先程挙げた雷の軌跡を迷路でシミュレートできるというツイートがあり、これはprocessingでやってみたいという思いで記事を書いています。


これをやる上では、迷路を作って、解くという2つの処理が必要になります。
作り方、解き方それぞれいろいろな方法があるようですが、作る方は有名っぽい方法を3つ試してみたいと思います。
解く方はできるだけ簡単そうなもの1つを実装してみます。

また、本題は迷路に設定したので、雷の軌跡の描画はまたいつの日か記事にしようと思います。


追記 (2022/09/24)

雷の軌跡についても記事にしました。
良ければこちらもどうぞ。

taq.hatenadiary.jp

以上


目次


迷路を作る

棒倒し法

棒倒し法は比較的簡単な迷路作成法です。
1マス毎に壁(道)を置いておき、各壁から上下左右のどこかにもうひとつ壁(道)を配置する、という方法です。


int n = 51; //迷路の大きさ
float len;
int[][] c = new int[n][n];
boolean[][] f = new boolean[n][n];

void setup(){
  size(700, 700);
 
  len = width/float(n); //1マスの長さ
  
  //盤面の初期設定(c = 0:道, 1:壁)
  for(int i = 0; i < n; i ++){
    //周囲を壁に
    c[i][0] = 1;
    c[i][n-1] = 1;
    c[0][i] = 1;
    c[n-1][i] = 1;
  }
  
  //1マス毎に
  for(int i = 1; i < n/2; i ++){
  for(int j = 1; j < n/2; j ++){
    c[2*i][2*j] = 1; //"棒"を作る
    f[2*i][2*j] = false; //"棒を倒したか"の情報
  }
  }
}

void draw(){
  background(255);
  
  //盤面の描画
  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); }
    stroke(230);
    rect(i*len, j*len, len, len);
  }
  }
  
  //"棒を倒す"処理
  for(int i = 1; i < n/2; i ++){
  for(int j = 1; j < n/2; j ++){
    if(f[2*i][2*j] == false){
      int a = 0;
      int b = 0;
      float p = random(0, 4); //上下左右のどこに倒すか
      if(p < 1){ a = 1; b = 0; } //右に
      else if(1 <= p && p < 2){ a = -1; b = 0; } //左に
      else if(2 <= p && p < 3){ a = 0; b = 1; } //下に
      else if(3 <= p && p < 4){ a = 0; b = -1; } //上に
      
      c[2*i+a][2*j+b] = 1; //倒す
      
      f[2*i][2*j] = true; //倒したことを保存
    }
  }
  }
}

実行すると、

迷路ができました。
ただし、ところどころに壁に囲まれてしまって、「ロ」のようになっている部分があります。

これについては、2段目以降の棒については上に倒さない、という条件を加えることで解決できます。
float p = random(0, 4);の部分を以下の処理に変更すればOKです。

int max;
if(2*j == 2){ max = 4; } //1段目の棒は上に倒すことも可能
else{ max = 3; } //2段目以降は上は除く
float p = random(0, max);


また、すでに倒れているところには倒さないという条件もあるようですが、入れなくてもそれほど変わらない感じがします。

一応実装するなら、c[2*i+a][2*j+b] = 1;の前に以下を追加すればOKです。

if(c[2*i+a][2*j+b] == 1){ return; } //倒した先が壁ならやり直す

このやり方だと迷路が大きくなるにつれて時間もかかるようになりますが、挙動に迷路を作っている感があって割と好きです。


というわけで、最終的なコードで実行してみると、


ここでは左上から順に棒を倒していきましたが、これもランダムな順番で行うようにすればまた違った雰囲気の迷路になるかもしれません。


穴掘り法

続いては穴掘り法です。
これは、一面壁にしておき、そこにランダムな位置から道を作っていく、という方法です。


int n = 51; //迷路の大きさ
float len;
int[][] c = new int[n][n];

void setup(){
  size(700, 700);
 
  len = width/float(n); //1マスの長さ
  
  //盤面の初期設定(c = 0:道, 1:壁)
  for(int i = 0; i < n; i ++){
  for(int j = 0; j < n; j ++){
    c[i][j] = 1; //一面壁にしておく
  }
  }
}

void draw(){
  background(255);
  
  //盤面の描画
  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); }
    stroke(230);
    rect(i*len, j*len, len, len);
  }
  }
  
  //"穴を掘る"処理
  int col, row;
  col = floor(random(2, n-2)); //ランダムに
  row = floor(random(2, n-2)); //1ヶ所を選ぶ
  if(col % 2 == 1 && row % 2 == 1 && c[col][row] == 1){ //選んだ座標が奇数で壁のとき
    makeRoute(col, row); //道を作る
  }
}

//道を作る関数
void makeRoute(int col, int row){      
  //ランダムに進む方向を決める
  IntList array = new IntList();
  array.append(1);
  array.append(2);
  array.append(3);
  array.append(4);
  array.shuffle();
  
  for(int i = 0; i < 4; i ++){
    int p = array.get(i);
  
    int a = 0;
    int b = 0;
    if(p == 1){ a = 1; b = 0; } //右に
    else if(p == 2){ a = -1; b = 0; } //左に
    else if(p == 3){ a = 0; b = 1; } //下に
    else if(p == 4){ a = 0; b = -1; } //上に
  
    if(col+2*a < 0 || n-1 < col+2*a || row+2*b < 0 || n-1 < row+2*b){ //進んだ先が画面外のとき
      continue; //for文を抜ける
    }
    
    if(c[col+2*a][row+2*b] == 0){ //進んだ先が道のとき
      continue; //for文を抜ける
    }
    
    //道を掘る
    c[col][row] = 0;
    c[col+a][row+b] = 0;
    c[col+2*a][row+2*b] = 0;
    
    //掘り進んだ先を次の始点として道を作っていく
    makeRoute(col+2*a, row+2*b);
  }
}

結局、手法は参考にさせていただいたQiitaのページをまねました。

IntListとshuffle()を使って進む向きを決め、そのリストの最初の方向に進もうとしたとき、進んだ先が穴掘り法での禁止事項(col+2*a < 0 || n-1 < col+2*a || row+2*b < 0 || n-1 < row+2*bc[col+2*a][row+2*b] == 0)を満たすならばcontinueでその下の処理を飛ばしてリストの2番目の方向について検討、…と3番目、4番目の要素についても繰り返していきます。
ですが、禁止事項に触れることがなかった方向ではcontinueが実行されないので、その下にある「道を掘る」処理や「掘り進んだ先を次の始点とする」処理が実行され、道が伸びていきます。


これを実行すると、

なんとなく、棒倒し法とは違った雰囲気の迷路ができました。


壁伸ばし法

最後は壁伸ばし法です。
これは、一面道にしておいて外壁から壁を伸ばしていく、という方法です。

やることは穴掘り法と似ています。
ですが、うまく実装できなかったので今は鋭意制作中ということにして、完成したときに追記することにします。(アドバイス求む)


追記 (2022/09/24)

壁伸ばし法も実装できました。
少しくどい感じはしますが、動くので良しとします。


穴掘り法と似た感じで壁(候補)を伸ばしていき、一定の条件を満たしたときに壁(候補)を壁に確定させる、という感じです。

ただ、穴掘り法と同じ構成だと生成に時間がかかってしまったので、壁伸ばし開始点を配列stackに入れておきそこからランダムに取り出す、という方法をとることにしました。
さらにwhile文で繰り返すことで、描画する頃には迷路は完成していることになります。


int n = 51; //迷路の大きさ
float len;
int[][] c = new int[n][n];
ArrayList<PVector> history = new ArrayList<PVector>();
ArrayList<PVector> stack = new ArrayList();

void setup(){
  size(700, 700);
 
  len = width/float(n); //1マスの長さ
  
  //盤面の初期設定(c = 0:道, 1:壁)
  for(int i = 0; i < n; i ++){
    //周囲を壁に
    c[i][0] = 1;
    c[i][n-1] = 1;
    c[0][i] = 1;
    c[n-1][i] = 1;
  }
  
  //壁伸ばし開始点を配列に格納
  for(int i = 1; i < n/2; i ++){
  for(int j = 1; j < n/2; j ++){
    stack.add(new PVector(2*i, 2*j));
  }
  }
}

void draw(){
  background(255);
  
  //迷路の生成
  while(stack.size() > 0){
    //壁を伸ばす
    int r = floor(random(0, stack.size())); //stackの中からランダムに取り出す
    int col = int(stack.get(r).x); //選んだ点を
    int row = int(stack.get(r).y); //colとrowに入れる

    stack.remove(r); //選んだ点を消す

    if(c[col][row] == 0){ //選んだ座標が道のとき
      makeWall(col, row); //壁を作る
    }
  }

  //盤面の描画
  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(100); }
    stroke(230);
    rect(i*len, j*len, len, len);
  }
  }
}

//道を作る関数
void makeWall(int col, int row){      
  //ランダムに進む方向を決める
  IntList array = new IntList();
  array.append(1);
  array.append(2);
  array.append(3);
  array.append(4);
  array.shuffle();
  
  int count = 0;

  for(int i = 0; i < 4; i ++){
    int p = array.get(i);
  
    int a = 0;
    int b = 0;
    if(p == 1){ a = 1; b = 0; } //右に
    else if(p == 2){ a = -1; b = 0; } //左に
    else if(p == 3){ a = 0; b = 1; } //下に
    else if(p == 4){ a = 0; b = -1; } //上に

    if(c[col][row] == 1){ //選んだ点が壁のとき
      continue; //for文を進める
    }

    if(c[col+2*a][row+2*b] == 1){ //進んだ先が壁のとき
      //履歴に経路を残す
      history.add(new PVector(col, row));
      history.add(new PVector(col+a, row+b));
      history.add(new PVector(col+2*a, row+2*b));

      for(PVector v: history){ //履歴全てについて
        c[int(v.x)][int(v.y)] = 1; //壁にする
      }
      history.clear(); //履歴を消す

      break; //for文を抜ける
    }

    if(c[col+2*a][row+2*b] == 2){ //進んだ先が壁候補のとき
      count ++;

      if(count >= 4){ //周りを壁候補に囲まれたとき
        for(PVector v: history){ //履歴全てについて
          c[int(v.x)][int(v.y)] = 0; //道に戻す
        }
        history.clear(); //履歴を消す

        break; //for文を抜ける
      }
      
      continue; //for文を進める
    }
    
    //壁候補を伸ばす
    c[col][row] = 2;
    c[col+a][row+b] = 2;
    c[col+2*a][row+2*b] = 2;

    history.add(new PVector(col, row));
    history.add(new PVector(col+a, row+b));
    history.add(new PVector(col+2*a, row+2*b));

    //伸ばした先を次の始点として壁を作っていく
    makeWall(col+2*a, row+2*b);
  }
}

makeWall()内にif(c[col][row] == 1)の条件式がありますが、これはなぜか開始点1つに対して壁伸ばしが2回以上行われてしまうことがあったためです。
(詳しい理由はわかりませんでした。わかった方がいたら教えてください…)


これを実行すると、

雰囲気は棒倒し法と似ています。


迷路の書き出し、読み込み

迷路は完成したのでこれから解くわけですが、迷路のデータをファイル化できた方が扱いやすいです。

ということで、csvファイルにして出力してみます。


過去にファイルの出入力を記事にしたことがあるので、詳細(言うほど詳しくはないですが)はこちらにあります。

taq.hatenadiary.jp

taq.hatenadiary.jp


書き出し

迷路を作るコードの最後にでも以下を貼り付ければ、同じフォルダ内に「maze.csv」というファイル名で保存されます。

PrintWriter file = createWriter("maze.csv");    
for(int j = 0; j < n; j ++){
  for(int i = 0; i < n; i ++){
    file.print(c[i][j] + ",");
  }
  file.println();
}
file.flush();
file.close();


読み込み

先程作った「maze.csv」をスケッチフォルダに入れ、以下のコードを実行すればできます。

Table t;
int n;
float len;
int[][] c;

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(){
  
}


迷路を解く

では、つくった迷路を解いてきます。


こちらのツイートを参考にさせていただきました。


これなら、かなり単純なセル・オートマトンで迷路を解くことができます。


ここでは左上をスタート、右下をゴールとします。

Table t;
int n;
float len;
int[][] c;

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(){
  //盤面の描画
  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); }
    stroke(230);
    rect(i*len, j*len, len, len);
  }
  }

  //迷路を解く
  for(int i = 1; i < n-1; i ++){ //全範囲について
  for(int j = 1; j < n-1; j ++){
    if(i != 1 && j != n-2 || i != n-2 && j != 1){ //(ただしスタートとゴールは除く)
      int w = c[i-1][j] + c[i+1][j] + c[i][j-1] + c[i][j+1]; //そのマスの上下左右の壁の数を数え
      if(w >= 3){ //壁の数が3つ以上なら
        c[i][j] = 1; //埋める
      }
    }
  }
  }
}


追記 (2022/09/23)

スタートとゴールの座標のx成分かy成分のどちらかが同じだと(例えば(1, n-2)と(1, 1))正常に経路が求められないことがわかりました。

修正案として以下を載せておきます。
解く部分を置き換えればOKです。

//迷路を解く
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){ //壁の数が3つ以上なら
    c[i][j] = 1; //埋める
  }
  //スタートとゴールは常に0(道)
  c[1][n-2] = 0;
  c[1][1] = 0;
}
}


例えば、スタートとゴールを(1, n-2)と(1, 1)としたときを考えると、掃引範囲が以下のようになっており、一部外れている部分があったことが理由だと思います。

これを、行き止まりを埋めた後でもスタートとゴールだけは必ず0になるようにすることで、強引かもしれませんが正しいルートを示してくれるようにはなりました。

以上


n = 51の穴掘り法で作った迷路について実行すると、

なぜか左下が[1][1]、右上が[n-1][n-1]となってしまいましたが、一応は任意の始点と終点に対してそれらを結ぶ経路を求めることができました。


まとめ

以上で、迷路を作って解くということについてprocessingに実装することができました。

コードは載せてありますがまだver.1なので、ここからさらにブラッシュアップしていければいいなとは思っています。


始めにも書きましたが、この記事を書くきっかけとなった雷の軌跡については、また別の記事で書くことにしようと思います。


追記 (2022/09/24)

こちらも始めにも追記しましたが、雷の軌跡についても記事にしました。
良ければこちらもどうぞ。

taq.hatenadiary.jp

以上


最後まで読んでいただいてありがとうございました。また次回。


参考