teratail
回答率
85.47%
質問するログイン新規登録
トップに関する質問C言語　経路探索アルゴリズム実装についての質問

編集履歴

質問編集履歴

3

プログラムについて不備がありましたので編集させて頂きました。

2019/02/25 07:53

投稿

missile_l700
missile_l700

スコア10

test CHANGED
File without changes
test CHANGED
@@ -742,6 +742,10 @@
742
742
 
743
743
 
744
744
 
745
+ コード
746
+
747
+ ```
748
+
745
749
 
746
750
 
747
751
  #### 試したこと

2

プログラムについて不備がありましたので編集させて頂きました。

2019/02/25 07:53

投稿

missile_l700
missile_l700

スコア10

test CHANGED
File without changes
test CHANGED
@@ -742,6 +742,8 @@
742
742
 
743
743
 
744
744
 
745
+
746
+
745
747
  #### 試したこと
746
748
 
747
749
 

1

プログラムについて不備がありましたので編集させて頂きました。

2019/02/25 07:52

投稿

missile_l700
missile_l700

スコア10

test CHANGED
File without changes
test CHANGED
@@ -1,4 +1,4 @@
1
- - リスト### 前提・実現したいこと
1
+ # 前提・実現したいこと
2
2
 
3
3
 
4
4
 
@@ -8,7 +8,7 @@
8
8
 
9
9
 
10
10
 
11
- ### 発生している問題・エラーメッセージ
11
+ ## 発生している問題・エラーメッセージ
12
12
 
13
13
  ---
14
14
 
@@ -16,6 +16,10 @@
16
16
 
17
17
  E0028　式には定数値が必要です。
18
18
 
19
+ C3863 配列型を割り当てることは出来ません。
20
+
21
+ C2228　ｙの左側はクラス・構造体・共用体でなければなりません。
22
+
19
23
 
20
24
 
21
25
  ---
@@ -24,7 +28,351 @@
24
28
 
25
29
  ### 該当のソースコード
26
30
 
31
+ ```#include <stdio.h>
32
+
33
+ #include <stdlib.h>
34
+
35
+ #include <time.h>
36
+
37
+ #define MAXX 256
38
+
39
+ #define MAXY 256
40
+
41
+
42
+
43
+ /* 迷路自動生成プログラム*/
44
+
45
+
46
+
47
+ // 迷路盤面の座標は構造体で管理する。
48
+
49
+
50
+
51
+ typedef struct {
52
+
53
+ int x;
54
+
55
+ int y;
56
+
57
+ }coord_t;
58
+
59
+
60
+
61
+ int meiro[MAXX][MAXY] = { { 0 } }; // 迷路盤
62
+
63
+ coord_t nodes[MAXX*MAXY]; // 未開発の（壁が伸びていない）柱のリスト
64
+
65
+ int nodend = 0; // nodesリストの長さ
66
+
67
+ coord_t path[MAXX*MAXY]; // 探索した柱のリスト（スタック）
68
+
69
+ int pathend = 0; // pathリストの長さ
70
+
71
+
72
+
73
+
74
+
75
+ // 構造体の値を設定
76
+
77
+
78
+
79
+ coord_t newcoord (int x , int y)
80
+
81
+ {
82
+
83
+ coord_t newcoord;
84
+
85
+ newcoord,x = x;
86
+
87
+ newcoord,y = y;
88
+
89
+ return newcoord;
90
+
91
+ }
92
+
93
+
94
+
95
+ // リストに新たな要素を追加(nodes)
96
+
97
+ void insert_node(coord_t c) {
98
+
99
+ nodes[nodend] = c;
100
+
101
+ nodend++;
102
+
103
+ }
104
+
105
+ // リストに新たな要素を追加(path)
106
+
107
+ void insert_path(coord_t c) {
108
+
109
+ path[pathend] = c;
110
+
111
+ pathend++;
112
+
113
+ }
114
+
115
+
116
+
117
+
118
+
119
+ // nodesリストの任意の要素を取り出す
120
+
121
+ coord_t remove_node(int k) {
122
+
123
+ coord_t out;
124
+
125
+ if (k > nodend) {
126
+
127
+ printf("error: Not found");
128
+
129
+ return newcoord(-1, -1);
130
+
131
+ }
132
+
133
+ else {
134
+
135
+ out = nodes[k]; // 取り出す
136
+
137
+ for (int i = k; i < nodend - 1; i++) // 取り出したぶん詰める
138
+
139
+ nodes[i] = nodes[i + 1];
140
+
141
+ nodend--;
142
+
143
+ }
144
+
145
+ return out;
146
+
147
+ }
148
+
149
+ // pathリストの†末尾†の要素を取り出す
150
+
151
+ coord_t remove_path(void) {
152
+
153
+ coord_t out;
154
+
155
+ out = path[pathend - 1]; // 取り出す
156
+
157
+ pathend--;
158
+
159
+ return out;
160
+
161
+ }
162
+
163
+
164
+
165
+ // リスト総当たり検索(nodes)
166
+
167
+ int search_node(coord_t c) {
168
+
169
+ for (int i = 0; i <= nodend - 1; i++) {
170
+
171
+ if ((nodes[i].x == c.x) && (nodes[i].y == c.y))
172
+
173
+ return i;
174
+
175
+ }
176
+
177
+ return -1;
178
+
179
+ }
180
+
181
+ // リスト総当たり検索(path)
182
+
183
+ int search_path(coord_t c) {
184
+
185
+ for (int i = 0; i <= pathend - 1; i++) {
186
+
187
+ if ((path[i].x == c.x) && (path[i].y == c.y))
188
+
189
+ return i;
190
+
191
+ }
192
+
193
+ return -1;
194
+
195
+ }
196
+
197
+
198
+
199
+ // 上下左右シャッフル
200
+
201
+ void shuffle(coord_t *direction) {
202
+
203
+ int j;
204
+
205
+ coord_t tmp;
206
+
207
+ for (int i = 0; i < 4; i++) {
208
+
209
+ j = rand() % 4;
210
+
211
+ tmp = direction[i];
212
+
213
+ direction[i] = direction[j];
214
+
215
+ direction[j] = tmp;
216
+
217
+ }
218
+
219
+ }
220
+
221
+
222
+
223
+
224
+
225
+ // 柱を探索（再帰）
226
+
227
+ int choose_node(coord_t c) {
228
+
229
+ int s, r;
230
+
231
+ coord_t p_1, p_2;
232
+
233
+ coord_t d[4] = { newcoord(0, 2),
234
+
235
+ newcoord(0, -2),
236
+
237
+ newcoord(2, 0),
238
+
239
+ newcoord(-2, 0) }; // 壁を伸ばす方向
240
+
241
+
242
+
243
+ // printf("x:%d, y:%d\n", c.x, c.y);
244
+
245
+ if (search_path(c) != -1) { // cが探索済の時
246
+
247
+ return 1; // 生成失敗
248
+
249
+ }
250
+
251
+ else {
252
+
253
+ insert_path(c); // pathに追加
254
+
255
+ s = search_node(c);
256
+
257
+ if (s != -1) { // cが未探索の時
258
+
259
+ remove_node(s); // nodeから消す
260
+
261
+ // 上下左右のいずれかに壁を伸ばす
262
+
263
+ shuffle(d);
264
+
265
+ for (int i = 0; i < 4; i++) {
266
+
267
+ r = choose_node(newcoord(c.x + d[i].x, c.y + d[i].y));
268
+
269
+ if (r == 0) break;
270
+
271
+ }
272
+
273
+ if (r == 1)
274
+
275
+ insert_node(remove_path());
276
+
277
+ return r;
278
+
279
+ }
280
+
281
+ else { // cがすでに壁の時
282
+
283
+ // pathリストの末尾から一つずつ取り出し壁を作る
284
+
285
+ p_2 = remove_path();
286
+
287
+ do {
288
+
289
+ p_1 = p_2;
290
+
291
+ p_2 = remove_path();
292
+
293
+ // printf("wall(%d, %d)\n",(p_1.x + p_2.x) / 2, (p_1.y + p_2.y) / 2);
294
+
295
+ meiro[(p_1.x + p_2.x) / 2][(p_1.y + p_2.y) / 2] = 1;
296
+
297
+ } while (pathend);
298
+
299
+ return 0;
300
+
301
+ }
302
+
303
+ }
304
+
305
+ }
306
+
307
+
308
+
309
+
310
+
311
+ // 迷路の自動生成
312
+
313
+ void make_meiro(int w, int h) {
314
+
315
+ coord_t c;
316
+
317
+ while (nodend) {
318
+
319
+ choose_node(nodes[rand() % nodend]);
320
+
321
+ }
322
+
323
+ // 外壁
324
+
325
+ for (int j = 0; j < h; j++) {
326
+
327
+ meiro[0][j] = 1;
328
+
329
+ meiro[w - 1][j] = 1;
330
+
331
+ }
332
+
333
+ for (int i = 0; i < w; i++) {
334
+
335
+ meiro[i][0] = 1;
336
+
337
+ meiro[i][h - 1] = 1;
338
+
339
+ }
340
+
341
+ }
342
+
343
+
344
+
345
+
346
+
347
+ /*******/
348
+
349
+ /* 探索 */
350
+
351
+ /*******/
352
+
353
+
354
+
355
+ /** 迷路作成に用いたpathスタックの領域をキューとして再利用 **/
356
+
357
+ // pathリストの†先頭†の要素を取り出す
358
+
359
+ coord_t remove_path_h(void) {
360
+
361
+ coord_t out = path[0]; // 取り出す
362
+
363
+ for (int i = 0; i < pathend; i++) // 詰める
364
+
365
+ path[i] = path[i + 1];
366
+
367
+ pathend--;
368
+
369
+ return out;
370
+
371
+ }
372
+
373
+
374
+
27
- ```// 地点pから最も遠い点を検索(幅優先)
375
+ // 地点pから最も遠い点を検索(幅優先)
28
376
 
29
377
  coord_t search_far(int w, int h, coord_t p) {
30
378
 
@@ -56,11 +404,345 @@
56
404
 
57
405
  }
58
406
 
407
+
408
+
409
+ // スタートを追加
410
+
411
+ pathend = 0;
412
+
413
+ insert_path(p);
414
+
415
+
416
+
417
+ // 繰り返し探索
418
+
419
+ while (pathend) {
420
+
421
+ n = remove_path_h();
422
+
423
+ // printf("search = (%d, %d)\n", n.x, n.y); 可能であれば表示させてみる
424
+
425
+ // printf ("%d\n", pathend);　　上同様
426
+
427
+
428
+
429
+ meiro_2[n.x][n.y] = 2; // 対応する座標を探索済みにする
430
+
431
+ shuffle(d); // ランダム性を持たせるためシャッフル
432
+
433
+ // printf("%d,%d\n",d[0].x,d[0].y);
434
+
435
+
436
+
437
+
438
+
439
+ for (int i = 0; i < 4; i++) {
440
+
441
+ sx = n.x + d[i].x; // 隣接マスのx座標
442
+
443
+ sy = n.y + d[i].y; // 隣接マスのy座標
444
+
445
+ if (meiro_2[sx][sy] == 0) { // 隣接マスが未探索の道のとき
446
+
447
+ insert_path(newcoord(sx, sy));
448
+
449
+ }
450
+
451
+ }
452
+
453
+ }
454
+
455
+ return n;
456
+
457
+ }
458
+
459
+
460
+
461
+
462
+
463
+ // 幅優先探索
464
+
465
+ int search_meiro(int w, int h, coord_t start, coord_t goal) {
466
+
467
+ coord_t n;
468
+
469
+ int sx, sy;
470
+
471
+ coord_t direction[w][h]; // 辿ってきた方向を記憶する配列
472
+
473
+ coord_t d[4] = { newcoord(0, 1),
474
+
475
+ newcoord(0, -1),
476
+
477
+ newcoord(1, 0),
478
+
479
+ newcoord(-1, 0) }; // 進む方向
480
+
481
+
482
+
483
+ // スタートを追加
484
+
485
+ pathend = 0;
486
+
487
+ insert_path(start);
488
+
489
+
490
+
491
+ // 繰り返し探索
492
+
493
+ while (pathend) {
494
+
495
+ n = remove_path_h();
496
+
497
+ // printf("search = (%d, %d)\n", n.x, n.y);
498
+
499
+ // printf ("%d\n", pathend);
500
+
501
+ meiro[n.x][n.y] = 2; // 対応する座標を探索済みにする
502
+
503
+ if (n.x == goal.x && n.y == goal.y) { // ゴール処理
504
+
505
+ while (n.x != start.x || n.y != start.y) {
506
+
507
+ // 値を更新
508
+
509
+ sx = n.x;
510
+
511
+ sy = n.y;
512
+
513
+ // printf("PATH = (%d, %d)\n", n.x, n.y);
514
+
515
+ // マーキング
516
+
517
+ meiro[n.x][n.y] = 3;
518
+
519
+ // 経路回帰
520
+
521
+ n.x -= direction[sx][sy].x;
522
+
523
+ n.y -= direction[sx][sy].y;
524
+
525
+ }
526
+
527
+ return 0;
528
+
529
+ }
530
+
531
+ else { // 探索処理
532
+
533
+ for (int i = 0; i < 4; i++) {
534
+
535
+ sx = n.x + d[i].x; // 隣接マスのx座標
536
+
537
+ sy = n.y + d[i].y; // 隣接マスのy座標
538
+
539
+ if (meiro[sx][sy] == 0) { // 隣接マスが未探索の道のとき
540
+
541
+ insert_path(newcoord(sx, sy));
542
+
543
+ direction[sx][sy] = d[i];
544
+
545
+ }
546
+
547
+ }
548
+
549
+ }
550
+
551
+ }
552
+
553
+ printf("ゴールを見つけられませんでしたorz...\n");
554
+
555
+ return 1;
556
+
557
+ }
558
+
559
+
560
+
561
+ // 迷路を表示
562
+
563
+ void show_meiro(int w, int h, coord_t start, coord_t goal) {
564
+
565
+ for (int j = 0; j < h; j++) {
566
+
567
+ for (int i = 0; i < w; i++) {
568
+
569
+ if ((i == start.x) && (j == start.y)) {
570
+
571
+ printf("\x1b[41m");
572
+
573
+ printf("\x1b[37m");
574
+
575
+ printf("S "); // スタート
576
+
577
+ }
578
+
579
+ else if ((i == goal.x) && (j == goal.y)) {
580
+
581
+ printf("\x1b[41m");
582
+
583
+ printf("\x1b[37m");
584
+
585
+ printf("G "); // ゴール
586
+
587
+ }
588
+
59
- ```
589
+ else {
590
+
60
-
591
+ switch (meiro[i][j]) {
592
+
61
-
593
+ case 0: // 探索されていない道
594
+
62
-
595
+ printf("\x1b[0m");
596
+
597
+ break;
598
+
599
+ case 1: // 壁
600
+
601
+ printf("\x1b[42m");
602
+
603
+ break;
604
+
605
+ case 2: // 探索された道
606
+
607
+ printf("\x1b[0m");// [47mで薄く表示
608
+
609
+ break;
610
+
611
+ case 3: // 正解ルート
612
+
613
+ printf("\x1b[45m");
614
+
615
+ break;
616
+
617
+ default:
618
+
619
+ printf("\x1b[0m");
620
+
621
+ }
622
+
623
+ printf(" ");
624
+
625
+ }
626
+
627
+ }
628
+
629
+ printf("\x1b[0m");
630
+
631
+ printf("\n");
632
+
633
+ }
634
+
635
+ printf("\n\n");
636
+
637
+ }
638
+
639
+
640
+
641
+
642
+
643
+ /***********/
644
+
645
+ /* メイン */
646
+
647
+ /***********/
648
+
649
+
650
+
651
+
652
+
653
+ int main(void) {
654
+
655
+ srand((unsigned)time(NULL));
656
+
657
+ int i, j;
658
+
659
+ int width, height; //壁の厚さを0、道の太さを1とした時の迷路の幅、高さ
660
+
661
+ printf("width> ");
662
+
663
+ scanf("%d", &width);
664
+
665
+ printf("height> ");
666
+
667
+ scanf("%d", &height);
668
+
669
+
670
+
671
+ // 柱リストの作成
672
+
673
+ for (j = 1; j < height; j++) {
674
+
675
+ for (i = 1; i < width; i++) {
676
+
677
+ insert_node(newcoord(2 * i, 2 * j));
678
+
679
+ // printf("%d\n", nodend);
680
+
681
+ meiro[2 * i][2 * j] = 1;
682
+
683
+ }
684
+
685
+ }
686
+
687
+
688
+
689
+ // 迷路盤の使用領域を設定
690
+
691
+ int w = 2 * width + 1; // 迷路盤の幅
692
+
693
+ int h = 2 * height + 1; // 迷路盤の高さ
694
+
695
+
696
+
697
+ // 迷路の自動生成
698
+
699
+ make_meiro(w, h);
700
+
701
+
702
+
703
+ // スタート、ゴールを設定
704
+
705
+ coord_t start = search_far(w, h, newcoord((rand() % width) * 2 + 1, (rand() % height) * 2 + 1));
706
+
707
+ coord_t goal = search_far(w, h, start);
708
+
709
+
710
+
711
+
712
+
713
+ // 迷路の表示
714
+
715
+ show_meiro(w, h, start, goal);
716
+
717
+
718
+
719
+ // 迷路の探索
720
+
721
+ char yn[2];
722
+
723
+ printf("Show the answer?");
724
+
725
+ scanf("%s", yn);
726
+
727
+ if (yn[0] == 'yn') {
728
+
729
+ search_meiro(w, h, start, goal);
730
+
731
+ show_meiro(w, h, start, goal);
732
+
733
+ }
734
+
735
+
736
+
737
+ printf("[end of 'long_meiro.c']\n");
738
+
739
+ return 0;
740
+
741
+ }
742
+
743
+
744
+
63
- ### 試したこと
745
+ #### 試したこと
64
746
 
65
747
 
66
748