C言語で迷路！
プログラムをつくる場合の手順
1.壁の設定
初期状態では全てのマスが壁であるとする。 これに穴を掘っていきそれを道とするように考える。
2.穴ほり
2.1：一本目の道
出発点をとりあえず左上にとり、そこを起点として穴をほっていくことにする。
掘る方向を乱数で決めれば、きちんと迷路になるはずである。
ただし、穴を掘るのは1列ごととなる。
というのも、道と道の間には壁がなくてはならないからだ。
また、穴を掘ってよい条件は、行く先がまだ壁であることである。
この工程をどの方向にも行けなくなるまで繰り返すことによって一本の道を完成させる。
2.2：二本目の道以降
出発点はすでにほってあるマスのうちx,yがともに奇数で、掘り出すことのできる方向が１つ以上あるものの中から選ぶ。
そのためにまずは全てのx,yについてマスが道であるかどうか・そこから掘り進めることができるかどうかということを検索することで候補を列挙する。
そして乱数を用いて次の穴掘りの起点を決めた。
穴掘りの手順は上に示したとおりであるので省略する。
この作業を起点の候補がなくなるまでひたすら繰り返す。
そうすることによって道が何本もできていく。
3.経路の検索
与えられた座標から出発し、全方位を検索していくことによってその迷路の解答経路を求めればよい。
すなわち、始点出発して至った点全てにおいて全方位を検索することを繰り返し、最終的に終点に至ったらそこまでの経路を解答経路として判断するようにすればよい。
4.描写
C言語にはGUI環境はないので、文字を用いて迷路をあらわすことにした。
描写はあらかじめ各座標に二次元の配列をとり、そこに属性(壁or道or解答経路)を与え、最後にまとめて表示するようにした。
フローチャート
関数名 dig
関数名 Root
関数名 main
ソース
ソース
1: #include<stdio.h>
2: #include<stdlib.h>
3: #include<time.h>
4:
5: #define SizeX 19 /*迷路の横幅*/
6: #define SizeY 19 /*迷路の縦幅*/
7:
8: int map[SizeX][SizeY]; /*座標属性格納用*/
9: int i = 0; /*候補座標選定用カウンタ*/
10: int X[SizeX*SizeY] ; /*候補座標格納用*/
11: int Y[SizeX*SizeY] ; /*候補座標格納用*/
12: int c; /*検索実行回数カウンタ*/
13: int a = 0; /*経路探索状況*/
14: /*穴掘り*/
15: int dig(int x, int y)
16: {
17: int dx,dy,r;
18: c =0;
19: r = rand(); /*ランダム方向*/
20:
21: while(c < 4)
22: {
23: switch ((r + 4 + c) % 4 )
24: {
25: case 0:
26: dx = 0;
27: dy = -1;
28: break;
29: case 1:
30: dx = -1;
31: dy = 0;
32: break;
33: case 2:
34: dx = 0;
35: dy = 1;
36: break;
37: case 3:
38: dx = 1;
39: dy = 0;
40: break;
41: }
42: if(x+dx*2 <= 0 || y+dy*2 <= 0 || x+dx*2 >= SizeX-1 || y+dy*2 >= SizeY-1 || map[x+dx*2][y+dy*2] == 0)
43: {
44: c++;
45: }
46: else if (map[x+dx*2][y+dy*2] == 1)
47: {
48: map[x+dx][y+dy] = 0;
49: map[x+dx*2][y+dy*2] = 0;
50: x = x + dx*2;
51: y = y + dy*2;
52: c = 0;
53: r = rand();
54: }
55: }
56: }
57:
58: /*経路探索*/
59: void Root(int x,int y)
60: {
61: map[x][y] = 2;
62: if (x == SizeX-2 && y == SizeY-2)
63: {
64: a = 1;
65: }
66: /*上*/
67: if (a !=1 && map[x][y-1] == 0 )
68: {
69: Root(x,y-1);
70: }
71: /*下*/
72: if (a !=1 && map[x][y+1] == 0 )
73: {
74: Root(x,y+1);
75: }
76: /*左*/
77: if (a !=1 && map[x-1][y] == 0 )
78: {
79: Root(x-1,y);
80: }
81: /*右*/
82: if (a !=1 && map[x+1][y] == 0 )
83: {
84: Root(x+1,y);
85: }
86: if (a !=1)
87: {
88: map[x][y] = 0;
89: }
90: }
91:
92: void main(void)
93: {
94: int x,y,a;
95: /*マップ初期化*/
96: for( x = 0; x < SizeX; x++ ){
97: for ( y = 0; y < SizeY; y++ ){
98: map[x][y] = 1;
99: }
100: }
101: map[1][1] = 0;
102:
103: /*候補座標選定*/
104: while(1)
105: {
106: i = 0;
107: for(y = 1; y < SizeY-1 ; y += 2 )
108: {
109: for(x = 1; x < SizeX-1 ; x += 2 )
110: {
111: if ( map[x][y] == 0)
112: {
113: if(x-2 >= 0 && map[x-2][y] == 1 )
114: {
115: X[i] = x;
116: Y[i] = y;
117: i++;
118: }
119: else if(y-2 >= 0 && map[x][y-2] == 1)
120: {
121: X[i] = x;
122: Y[i] = y;
123: i++;
124: }
125: else if((y==SizeY-2) && (x==SizeX-2))
126: {
127: break;
128: }
129: else if(x+2 < SizeX && map[x+2][y] == 1)
130: {
131: X[i] = x;
132: Y[i] = y;
133: i++;
134: }
135: else if(y+2 < SizeY && map[x][y+2] == 1)
136: {
137: X[i] = x;
138: Y[i] = y;
139: i++;
140: }
141: }
142: }
143:
144: }
145: if (i==0)
146: {
147: break;
148: }
149: else
150: {
151: srand((unsigned) time(NULL));
152: a = rand() % i;
153: x = X[a];
154: y = Y[a];
155: dig(x,y);
156: }
157: }
158:
159: /*経路探索*/
160: Root(1,1);
161:
162: /*後処理＆描写*/
163: map[1][0] = 2;
164: map[SizeX-2][SizeY-1] = 2;
165:
166: for(y = 0; y < SizeY ; y++ ){
167: for(x = 0; x < SizeX ; x++ ){
168: if( map[x][y] == 0){
169: printf(" ");
170: }else if( map[x][y] == 1){
171: printf("■") ;
172: }else if( map[x][y] == 2){
173: printf("・") ;
174: }
175: }
176: printf("\n");
177: }
178: }
実行結果
■・■■■■■■■■■■■■■■■■■
■・■・・・・・・・■・・・・・・・■
■・■・■■■■■・■・■■■■■・■
■・・・■ ■・・・■ ■・・・■
■■■ ■ ■ ■■■■■ ■・■■■
■ ■ ■ ■ ■ ■・■ ■
■ ■■■■■■■ ■ ■ ■・■ ■
■ ■ ■・・・■ ■
■■■■■■■ ■■■■■・■ ■ ■
■ ■・・・・・■ ■
■ ■■■■■ ■・■■■■■■■■■
■ ■ ■・・・・・■・・・■
■■■■■ ■ ■■■■■・■・■・■
■ ■ ■ ■・・・■・■
■ ■■■■■ ■ ■ ■■■■■・■
■ ■ ■ ・・・・・■
■■■■■ ■■■■■■■・■■■■■
■ ■・・・・・■
■■■■■■■■■■■■■■■■■・■
Press any key to continue
[ともやん☆/Top]