初めに
今回は迷路の自動生成に挑戦してみたいと思います。
使うアルゴリズム
穴掘り法です。
C++版ソースコード
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オプションで容量を増やさないとサイズを大きくしたときにエラーを吐きます。
結果
*がスタートで/がゴールです。
+++++++++++++++++++++++++++++++++++++++++++++++++++
+ + + + + + +
+++++++++++ + +++ + + + +++++++++ +++++++++ +++ + +
+ + + + + + + + + + + +
+ + + +++ +++++ + + +++++ +++++ + + +++++ + + +++ +
+ + + + + + + + + + /+ + + + +
+ +++++ +++++++++ + + +++++++ +++++ +++ +++ +++ +++
+ + + + + + + + + + + +*+ +
+ + + + + +++ +++++ + + +++ +++ + + + +++++++ +++ +
+ + + + + + + + + + + + + +
+ + +++ + + +++++++ + +++ + + +++++++++++++++++ + +
+ + + + + + + + + + + + + + +
+ + + +++ + + + +++++++++ +++++ +++++++++ + + + +++
+ + + + + + + + + + + + +
+ + +++ + + + +++++++++ + +++++++ +++++ + +++ +++ +
+ + + + + + + + + + + + + + +
+ + + + + +++ +++++ +++++++++ + +++ + +++++ +++ + +
+ + + + + + + + + + + + + +
+ + +++ + + +++ +++++ + + +++++++ + +++++ +++++++ +
+ + + + + + + + + + + + + + +
+ + + +++ + + +++ + + +++ + +++++++ +++++ +++ + +++
+ + + + + + + + + + + + + + + +
+ + +++ +++ +++++++ +++ + + + +++++ + +++++ +++ + +
+ + + + + + + + + + + + + +
+ + + +++++++++++++++ + +++++++ +++++ + + + +++++ +
+ + + + + + + + + + + +
+ +++++++ + +++++++++++ +++++++++++ + + +++ + + + +
+ + + + + + + + + + + + +
+++++ + +++++++++ +++ +++++ +++++ + + + + +++ + + +
+ + + + + + + + + + + + +
+ +++++++ + + + +++ +++++++++ +++++++ + + +++ +++++
+ + + + + + + + + + + + + +
+ +++++ + + + +++++++++ + + +++ + + + + +++ +++++ +
+ + + + + + + + + + + + + + +
+++++++ + + +++ + +++++ + +++ + + +++++ + +++++++ +
+ + + + + + + + + + + + + +
+ + + +++++++ +++++++++++ + + + +++++ + +++ + + + +
+ + + + + + + + + + + + +
+ + +++++++ +++++++++ + +++++++++ + + +++++++ + + +
+ + + + + + + + + + + + + + + +
+ +++++ + + + + + + + + + + + + +++ + + +++ +++ +++
+ + + + + + + + + + + + + + + + + + + + +
+ + + + + + + + +++ + +++ + + + + + +++++++++ + + +
+ + + + + + + + + + + + + + +
+ +++ + +++++++++++++ + + + +++++ +++++ + +++++++ +
+ + + + + + + + + + + +
+ + +++++ +++++++++++++++++ +++ + + + +++ + + + + +
+ + + + + + + + + + + + + + +
+ + + + +++++++ + +++++++ +++ +++ + +++++++ + +++ +
+ + + + + + + +
+++++++++++++++++++++++++++++++++++++++++++++++++++
ゴール指定の方法が多分、間違っていますね。
簡単すぎます。
が、迷路の生成自体は無事成功しています。
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++をそのまま移植したような感触です。
結果
+++++++++++++++++++++++++++++++++++++++++++++++++++
+ + + + + + + + + + + +
+ + + + + + +++ + +++ + + + + + + + + + + + + + + +
+ + + + + + + + + + + + + + +
+ +++++++++++ +++ + +++++++++++++++++++++++++++++ +
+ +/ + + + + + + + + + + + +
+++ +++ + + +++ +++ + +++ + + + + + + + + + + + +++
+ + + + + + + + + + + + + + +
+ +++ +++++ + +++ +++ + +++ +++++++++++++++++++++ +
+ + + + + + + + + + + + + +
+++ +++ + +++++ +++ +++ + +++ + + + + + + + + + + +
+ + + + + + + + + + + + + +
+ +++ +++++ + +++ +++ +++ + +++++++++++++++++++++ +
+ + + + + + + + + + + + + +
+++ +++ + +++++ +++ +++ +++ + +++ + + + + + + + +++
+ + + + + + + + + + + + + + +
+ +++ +++++ + +++ +++ +++ +++++ + +++++++++++++++ +
+ + + + + + + *+ + + + + +
+++ +++ + +++++ +++ +++ +++++ +++++ +++ + + + + + +
+ + + + + + + + + + + + + +
+ +++ +++++ + +++ +++ +++ + +++ + +++ +++++++++++ +
+ + + + + + + + + + + + + +
+++ +++ + +++++ +++ +++ +++++ + +++ +++ + + + + +++
+ + + + + + + + + + + + + +
+ +++ +++++ + +++ +++ +++ + + +++ +++ +++++++++++ +
+ + + + + + + + + + + + + +
+++ +++ + +++++ +++ +++ + +++++ +++ +++ + + + + + +
+ + + + + + + + + + + + + +
+ +++ +++++ + +++ +++ +++++ + +++ +++ +++++++++++ +
+ + + + + + + + + + + + + +
+++ +++ + +++++ +++ +++ + +++++ +++ +++ + + + + +++
+ + + + + + + + + + + + + +
+ +++ +++++ + +++ +++ +++++ + +++ +++ +++ +++++++ +
+ + + + + + + + + + + + +
+++ +++ + +++++ +++ +++ + +++++ +++ +++ +++ +++ + +
+ + + + + + + + + + + + + +
+ +++ +++++ + +++ +++ +++++ + +++ +++ +++ +++ +++ +
+ + + + + + + + + + + + + +
+++ +++ + +++++ +++ +++ + +++++ +++ +++ +++ +++ + +
+ + + + + + + + + + + + + +
+ +++ +++++ + +++ +++ +++++ + +++ +++ +++ +++ +++ +
+ + + + + + + + + + + + + +
+++ +++ + +++++ +++ +++ + +++++ +++ +++ +++ +++ + +
+ + + + + + + + + + + + + +
+ +++ +++++ + +++ +++ +++++ + +++ +++ +++ +++ +++ +
+ + + + + + + + + + + + + +
+++ +++ + +++++ +++ +++ + +++++ +++ +++ +++ +++ + +
+ + + + + + + + + + + + + +
+ +++ +++++ + +++ +++ +++++ + +++ +++ +++ +++ +++ +
+ + + + + + + +
+++++++++++++++++++++++++++++++++++++++++++++++++++
線形合同法のせいなのか、同じパターンが繰り返し出ていますね。
C++版との違い
- 向き計算の確率を廃止
- ゴール部分の計算方法の変更
- 乱数の初期値の固定
- 乱数生成の自作
- コマンドライン引数の廃止