迷路の自動生成

# 初めに

今回は迷路の自動生成に挑戦してみたいと思います。

# 使うアルゴリズム

穴掘り法です。

# C++版ソースコード

```cpp:main.cpp
#include <cstdio>
#include <vector>
#include <iostream>
#include <cstdlib>
#include <ctime>

class random_trun_class{

public:
  std::vector<double> p;
  void init(std::vector<double> p_data){
    p=p_data;
  }

  int Get(){
    double temp=(double)(rand())/(double)RAND_MAX;
    double temp2=0;
    for(int i=0;i<p.size();i++){
      if(temp2<=temp&&temp<temp2+p[i])return i;
      temp2+=p[i];
    }
    return -1;
  }

};

void PRINT_data_func(std::vector<std::vector<bool> > &v);


int startx=-1;
int starty=-1;
int ENDx=-1;
int ENDy=-1;

random_trun_class random_trun;

void resize_vec_func(std::vector<std::vector<bool> > &v,int n1,int n2){
  v.resize(n1);
  for (int i = 0; i < v.size(); i++) {
    v[i].resize(n2);
    for (int i2 = 0; i2 < v[i].size(); i2++) {
      v[i][i2]=true;
    }
  }
}


bool random_trun_END(std::vector<std::vector<bool> > &v,int x,int y){
  return
    (y-2>0&&
    v[y-2][x])||
    (y+2<v.size()&&
    v[y+2][x])||
    (x-2>0&&
    v[y][x-2])||
    (x+2<v[0].size()&&
    v[y][x+2])
  ;

}

void Make_data(std::vector<std::vector<bool> > &v,int x,int y){

  ENDx=x;
  ENDy=y;

  while(random_trun_END(v,x,y)){
  //  PRINT_data_func(v);
    int temp=random_trun.Get();
    if(temp==0){
      if((y-2>0&&
      v[y-2][x])){
        v[y-1][x]=false;
        v[y-2][x]=false;
        Make_data(v,x,y-2);
      }
    }
    if(temp==1){
      if((y+2<v.size()&&
      v[y+2][x])){
        v[y+1][x]=false;
        v[y+2][x]=false;
        Make_data(v,x,y+2);
      }
    }
    if(temp==2){
      if((x-2>0&&
      v[y][x-2])){
        v[y][x-1]=false;
        v[y][x-2]=false;
        Make_data(v,x-2,y);
      }
    }
    if(temp==3){
      if((x+2<v[0].size()&&
      v[y][x+2])){
        v[y][x+1]=false;
        v[y][x+2]=false;
        Make_data(v,x+2,y);
      }
    }
  }

}

bool Make_data_END(std::vector<std::vector<bool> > &v){

  for (int y = 1; y < int(v.size()/2-1); y+=2) {
    for (int x = 1; x < int(v[y].size()/2-1); x+=2) {
      if(random_trun_END(v,x,y))return true;
    }
  }

  return false;
}

void Make_data(std::vector<std::vector<bool> > &v){

    int x=2*(rand()%int(v.size()/2-1))+1;
    int y=2*(rand()%int(v[0].size()/2-1))+1;

    startx=x;
    starty=y;

    v[y][x]=false;

    Make_data(v,x,y);

}

void PRINT_data_func(std::vector<std::vector<bool> > &v){

  for(int y=0;y<v.size();y++){
    for(int x=0;x<v[y].size();x++){
      if(startx==x&&starty==y){
        std::cout<<"*";
      }
      else if(ENDx==x&&ENDy==y){
        std::cout<<"/";
      }
      else if(v[y][x]){
        std::cout<<"+";
      }
      else{
        std::cout<<" ";
      }
    }
    std::cout<<"\n";
  }

}

//壁 True 無し False
int main(int argc,char** args){

  int x,y;
  srand((unsigned)time(NULL));

  if(argc<3){
  std::cout << "y>";
  std::cin>> y;
  std::cout << "x>";
  std::cin>> x;
  }
  else{
    x=atoi(args[1]);
    y=atoi(args[2]);
  }

  std::vector<std::vector<bool> > data;

  resize_vec_func(data,y,x);

  random_trun.init(std::vector<double>{0.25,0.25,0.25,0.25});

  Make_data(data);

  PRINT_data_func(data);

  return 0;
}
```

再帰法を使っています。
ランダムで向きを決める部分の確率指定も出来ます。
C++11です。
コンパイルオプションではstackオプションで容量を増やさないとサイズを大きくしたときにエラーを吐きます。


## 結果

*がスタートで/がゴールです。

```text
+++++++++++++++++++++++++++++++++++++++++++++++++++
+           +     +   +           +             + +
+++++++++++ + +++ + + + +++++++++ +++++++++ +++ + +
+   +     +   +   + +   +       + +       +   +   +
+ + + +++ +++++ + + +++++ +++++ + + +++++ + + +++ +
+ +   + +       + + +   +     +   +  /+   + +   + +
+ +++++ +++++++++ + + +++++++ +++++ +++ +++ +++ +++
+ + +       +     + +     +   +   + +   +   +*+   +
+ + + + + +++ +++++ + + +++ +++ + + + +++++++ +++ +
+ +   + + +       + + +   + +   +   +         +   +
+ + +++ + + +++++++ + +++ + + +++++++++++++++++ + +
+ + +   + + + +     +   + +   +           + +   + +
+ + + +++ + + + +++++++++ +++++ +++++++++ + + + +++
+ + +   + + + +         +       +       + +   +   +
+ + +++ + + + +++++++++ + +++++++ +++++ + +++ +++ +
+ + + + + +       +     +     +   + +   +   + +   +
+ + + + + +++ +++++ +++++++++ + +++ + +++++ +++ + +
+ +   + + +   +     +   +     +   + +     +     + +
+ + +++ + + +++ +++++ + + +++++++ + +++++ +++++++ +
+ + +   + + +   +   + +   +       +     + +   +   +
+ + + +++ + + +++ + + +++ + +++++++ +++++ +++ + +++
+ + +   + + +     + +   + + +       +     +   + + +
+ + +++ +++ +++++++ +++ + + + +++++ + +++++ +++ + +
+ + + +           +   + + +   +     + +   +     + +
+ + + +++++++++++++++ + +++++++ +++++ + + + +++++ +
+ +       +           +         +   + + + + +   + +
+ +++++++ + +++++++++++ +++++++++++ + + +++ + + + +
+     +   +       +     +         + + + +   + + + +
+++++ + +++++++++ +++ +++++ +++++ + + + + +++ + + +
+     +   +   + +   +       +       + + + +   +   +
+ +++++++ + + + +++ +++++++++ +++++++ + + +++ +++++
+       + + +     +     + +   + +   + + +   +     +
+ +++++ + + + +++++++++ + + +++ + + + + +++ +++++ +
+     + + + + +       + + +   + + +   +   +       +
+++++++ + + +++ + +++++ + +++ + + +++++ + +++++++ +
+   +   +   +   +       +   + + +     + +   +   + +
+ + + +++++++ +++++++++++ + + + +++++ + +++ + + + +
+ + +       +         +   +     +   + +   +   + + +
+ + +++++++ +++++++++ + +++++++++ + + +++++++ + + +
+ +     +   +   +   + + + +   +   + + +     + +   +
+ +++++ + + + + + + + + + + + + +++ + + +++ +++ +++
+ +   + + + + + + + + +   + + + + + +     +   + + +
+ + + + + + + + +++ + +++ + + + + + +++++++++ + + +
+   + +   +   +     + + + + +   + +     +     +   +
+ +++ + +++++++++++++ + + + +++++ +++++ + +++++++ +
+ +   + +             +   +     +   +   + +     + +
+ + +++++ +++++++++++++++++ +++ + + + +++ + + + + +
+ + +   +       +         + +   + + +     + + + + +
+ + + + +++++++ + +++++++ +++ +++ + +++++++ + +++ +
+ +   +           +           +   +         +     +
+++++++++++++++++++++++++++++++++++++++++++++++++++
```

ゴール指定の方法が多分、間違っていますね。
簡単すぎます。
が、迷路の生成自体は無事成功しています。

# Scheme版

```scheme:main.scm

(define (PRINT_data_func v n X Y)
(if (< n (* X Y))
(begin
(if (= 0 (my_mod_func n X))
(newline)
)
(display (if (= n (set_xy_2dim startx starty X))
"*"
(if (= n (set_xy_2dim ENDx ENDy X))
"/"
(if (= 1 (vector-ref v n))
"+"
" "
))))

(PRINT_data_func v (+ n 1) X Y)
))
)

(define startx 0)
(define starty 0)
(define ENDx (- 1))
(define ENDy (- 1))


(define my_get_random_x 102)

(define (my_mod_func x1 x2)
(- x1 (* (truncate (/ x1 x2)) x2))
)

(define (my_get_random)
(set! my_get_random_x (my_mod_func (+ (* 1664525 my_get_random_x) 1013904223) 4294967296))
)

(define (set_xy_2dim x y X)
(+ y (* X x))
)

(define (random_trun)
(my_mod_func (my_get_random) 4)
)

(define (Make_data2_next_Is_ok v x1 y1 x2 y2 X Y)
(and
  (<= 0 (+ x1 x2)) (< (+ x1 x2) X)
  (<= 0 (+ y1 y2)) (< (+ y1 y2) Y)
  (= 1 (vector-ref v (set_xy_2dim (+ x1 x2) (+ y1 y2) X)))
)
)

(define (Make_data2_next v x1 y1 x2 y2 X Y)
(begin
(vector-set! v (set_xy_2dim (+ x1 x2) (+ y1 y2) X) 0)
(vector-set! v (set_xy_2dim (+ x1 (/ x2 2)) (+ y1 (/ y2 2)) X) 0)
(Make_data2 v (+ x1 x2) (+ y1 y2) X Y)
)
)

(define (random_trun_END v x y X Y)
(or
   (Make_data2_next_Is_ok v x y 2 0 X Y)
   (Make_data2_next_Is_ok v x y (- 2) 0 X Y)
   (Make_data2_next_Is_ok v x y 0 2 X Y)
   (Make_data2_next_Is_ok v x y 0 (- 2) X Y)
)
)

(define (Make_data2 v x y X Y)
(if (random_trun_END v x y X Y)
(let ((temp 0))
(begin
(set! temp (random_trun))
(if (and (= temp 0) (Make_data2_next_Is_ok v x y 2 0 X Y)) (Make_data2_next v x y 2 0 X Y))
(if (and (= temp 1) (Make_data2_next_Is_ok v x y (- 2) 0 X Y)) (Make_data2_next v x y (- 2) 0 X Y))
(if (and (= temp 2) (Make_data2_next_Is_ok v x y 0 2 X Y)) (Make_data2_next v x y 0 2 X Y))
(if (and (= temp 3) (Make_data2_next_Is_ok v x y 0 (- 2) X Y)) (Make_data2_next v x y 0 (- 2) X Y))
(Make_data2 v x y X Y)
)
)
(if (< ENDx 0)
(begin (set! ENDx x)
(set! ENDy y)
))
)
(begin v)
)


(define (Make_data v X Y)
(let ((x 0) (y 0))
(begin
(set! y (+ (* 2 (my_mod_func (my_get_random) (truncate (- (/ Y 2) 1)))) 1))
(set! x (+ (* 2 (my_mod_func (my_get_random) (truncate (- (/ X 2) 1)))) 1))
(set! startx x)
(set! starty y)
(vector-set! v (set_xy_2dim x y X) 0)
(set! v (Make_data2 v x y X Y))
)
)
(begin v)
)



(let ((x 0) (y 0) (data '()))
(print "x>")
(set! x (read))
(print "y>")
(set! y (read))
(set! data (make-vector (* y x) 1))
(set! data (Make_data data x y))
(PRINT_data_func data 0 x y)
(newline)
)

```

再帰関数の嵐ですね。
ただ、このソースコード全くLISPらしくないです。
まるで、C++をそのまま移植したような感触です。

## 結果

```text
+++++++++++++++++++++++++++++++++++++++++++++++++++
+   +   +   +         +   +   +   +   +   +   +   +
+ + + + + + +++ + +++ + + + + + + + + + + + + + + +
+ +   +   +   + +   +   +   +   +   +   +   +   + +
+ +++++++++++ +++ + +++++++++++++++++++++++++++++ +
+   +/    + +   + +   +   +   +   +   +   +   +   +
+++ +++ + + +++ +++ + +++ + + + + + + + + + + + +++
+   +   +   + +   + +   +   +   +   +   +   +   + +
+ +++ +++++ + +++ +++ + +++ +++++++++++++++++++++ +
+   +   +   +   +   + +   +   +   +   +   +   +   +
+++ +++ + +++++ +++ +++ + +++ + + + + + + + + + + +
+   +   +   +     +   + +   +   +   +   +   +   + +
+ +++ +++++ + +++ +++ +++ + +++++++++++++++++++++ +
+   +   +   +   +   +   + +   +   +   +   +   +   +
+++ +++ + +++++ +++ +++ +++ + +++ + + + + + + + +++
+   +   +   +   +   + +   + +   +   +   +   +   + +
+ +++ +++++ + +++ +++ +++ +++++ + +++++++++++++++ +
+   +   +   +   +   +   +  *+   +   +     +   +   +
+++ +++ + +++++ +++ +++ +++++ +++++ +++ + + + + + +
+   +   +   +   +   +     +   + +   +   +   +   + +
+ +++ +++++ + +++ +++ +++ + +++ + +++ +++++++++++ +
+   +   +   +   +   +   +   + +   +   +   +   +   +
+++ +++ + +++++ +++ +++ +++++ + +++ +++ + + + + +++
+   +   +   +   +   +   +   +   +   +   +   +   + +
+ +++ +++++ + +++ +++ +++ + + +++ +++ +++++++++++ +
+   +   +   +   +   +   + +   +   +   +   +   +   +
+++ +++ + +++++ +++ +++ + +++++ +++ +++ + + + + + +
+   +   +   +   +   +   +   +   +   +   +   +   + +
+ +++ +++++ + +++ +++ +++++ + +++ +++ +++++++++++ +
+   +   +   +   +   +   +   +   +   +   + +   +   +
+++ +++ + +++++ +++ +++ + +++++ +++ +++ + + + + +++
+   +   +   +   +   +   +   +   +   +   +   +   + +
+ +++ +++++ + +++ +++ +++++ + +++ +++ +++ +++++++ +
+   +   +   +   +   +   +   +   +   +   +   +     +
+++ +++ + +++++ +++ +++ + +++++ +++ +++ +++ +++ + +
+   +   +   +   +   +   +   +   +   +   +   +   + +
+ +++ +++++ + +++ +++ +++++ + +++ +++ +++ +++ +++ +
+   +   +   +   +   +   +   +   +   +   +   +   + +
+++ +++ + +++++ +++ +++ + +++++ +++ +++ +++ +++ + +
+   +   +   +   +   +   +   +   +   +   +   +   + +
+ +++ +++++ + +++ +++ +++++ + +++ +++ +++ +++ +++ +
+   +   +   +   +   +   +   +   +   +   +   +   + +
+++ +++ + +++++ +++ +++ + +++++ +++ +++ +++ +++ + +
+   +   +   +   +   +   +   +   +   +   +   +   + +
+ +++ +++++ + +++ +++ +++++ + +++ +++ +++ +++ +++ +
+   +   +   +   +   +   +   +   +   +   +   +   + +
+++ +++ + +++++ +++ +++ + +++++ +++ +++ +++ +++ + +
+   +   +   +   +   +   +   +   +   +   +   +   + +
+ +++ +++++ + +++ +++ +++++ + +++ +++ +++ +++ +++ +
+     +       +       +       +       +       +   +
+++++++++++++++++++++++++++++++++++++++++++++++++++
```

線形合同法のせいなのか、同じパターンが繰り返し出ていますね。

## C++版との違い

- 向き計算の確率を廃止
- ゴール部分の計算方法の変更
- 乱数の初期値の固定
- 乱数生成の自作
- コマンドライン引数の廃止