maze traversal I need help.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
01	#include <stdio.h>
02	 
03	#define FALSE 0
04	#define TRUE 1
05	 
06	#define NROWS 6
07	#define MCOLS 6
08	 
09	// Symbols:
10	// '.' = open
11	// '#' = blocked
12	// 'S' = start
13	// 'G' = goal
14	// '+' = path
15	// 'x' = bad path
16	char maze[NROWS][MCOLS] = {
17	    "S...##",
18	    "#.#...",
19	    "#.##.#",
20	    "..#.##",
21	    "#...#G",
22	    "#.#..."
23	};
24	 
25	 
26	void display_maze(void);
27	int find_path(int x, int y);
28	 
29	 
30	int
31	main(void)
32	{
33	    display_maze();
34	 
35	    if ( find_path(0, 0) == TRUE )
36	        printf("Success!\n");
37	    else
38	        printf("Failed\n");
39	 
40	    display_maze();
41	 
42	    return 0;
43	}
44	// main()
45	 
46	 
47	void
48	display_maze(void)
49	{
50	    int i;
51	 
52	    printf("MAZE:\n");
53	    for ( i = 0; i < NROWS; i++ )
54	        printf("%.*s\n", MCOLS, maze[i]);
55	    printf("\n");
56	 
57	    return;
58	}
59	 
60	 
61	int
62	find_path(int x, int y)
63	{
64	    // If x,y is outside maze, return false.
65	    if ( x < 0 || x > MCOLS - 1 || y < 0 || y > NROWS - 1 ) return FALSE;
66	 
67	    // If x,y is the goal, return true.
68	    if ( maze[y][x] == 'G' ) return TRUE;
69	 
70	    // If x,y is not open, return false.
71	    if ( maze[y][x] != '.' && maze[y][x] != 'S' ) return FALSE;
72	 
73	    // Mark x,y part of solution path.
74	    maze[y][x] = '+';
75	 
76	    // If find_path North of x,y is true, return true.
77	    if ( find_path(x, y - 1) == TRUE ) return TRUE;
78	 
79	    // If find_path East of x,y is true, return true.
80	    if ( find_path(x + 1, y) == TRUE ) return TRUE;
81	 
82	    // If find_path South of x,y is true, return true.
83	    if ( find_path(x, y + 1) == TRUE ) return TRUE;
84	 
85	    // If find_path West of x,y is true, return true.
86	    if ( find_path(x - 1, y) == TRUE ) return TRUE;
87	 
88	    // Unmark x,y as part of solution path.
89	    maze[y][x] = 'x';
90	 
91	    return FALSE;
92	}
93	// find_path() 



the algorithm is from this site http://www.cs.bu.edu/teaching/alg/maze/

I want to understand the algorithms of the maze traversal and generation of mazes. Please guys.
Last edited on
What is your question?
This isn't C++.
Strings are null terminated (the last char is '\0') so the strings used to initialize maze is of length 7 but MCOLS is only 6. If you want to use string literals to initialize the maze you will have to make the maze one bigger.
1
2
3
4
5
6
7
8
char maze[NROWS][MCOLS + 1] = {
	"S...##",
	"#.#...",
	"#.##.#",
	"..#.##",
	"#...#G",
	"#.#..."
};
It's actually REALLY easy. I done this in 15 minutes. I'm not gonna give you the solution if you want to keep trying, buf if you give up, just say the word!
Last edited on
viliml wrote:
It's actually REALLY easy.

Everything is easy if you know how to do it.
True... So I might as well say "I actually REALLY know how to do it.":D Seriously though, the only thing I see at first sight in that code that's wrong is that it's not C++, but pure C, if not worse...
The code is valid C code and valid C++ code.
OK,you want me to post my soslution?
i need your help guys. i don't know how to write the maze traversing application i need some pseudo-code or anything that will help me understand how to do it my self. the code is not mine, i need to do mine.
Topic archived. No new replies allowed.