C++

Forum

 
Shortest path of maze using BFS

Kallan (1)
Hi, I´m trying to make maze solver using Breadth-first search and my program can already find the way out of the maze but I don´t know how to keep track of the way and find the shortest one. This is the program:
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
 
#include <fstream>
#include <queue>
#include <iostream> 

using std::queue;

struct s_maze
{
	char place;
	int c;
	int r;
	bool used;
};

int main()
{
	using std::ifstream;
	using std::ofstream;

	ifstream fin;
	ofstream fout;

	fin.open("maze.in");
	if (fin.is_open() == false)
		return 0;
	int row, column, start_c, start_r;
	fin >> row >> column;
	
	s_maze maze[50][50];
	s_maze test_maze;
	for (int c = 0; c < column; ++c)
	{
		for (int r = 0; r < row; ++r)
		{
			fin >> maze[c][r].place;
			maze[c][r].used = false;
			maze[c][r].c = c;
			maze[c][r].r = r;
			if (maze[c][r].place == 'S')
			{
				start_c = c;
				start_r = r;
			}
		}
	}
	
	queue <s_maze> q;

	q.push(maze[start_c][start_r]);
	
	while(q.empty() != true)
	{
		test_maze = q.front();
		maze[test_maze.c][test_maze.r].used = true;
		std::cout << test_maze.c <<" " << test_maze.r << std::endl;
		q.pop();
		if (test_maze.place == 'C')
		{
			std::cout << "exit at " << test_maze.c << " " << test_maze.r;
			std::cin.get();
			return 0;
		}
	

	if (test_maze.c - 1 >= 0)
	{	
		if (maze[test_maze.c - 1][test_maze.r].place != '#' && (maze[test_maze.c - 1][test_maze.r].place == '.' || maze[test_maze.c - 1][test_maze.r].place == 'S' || maze[test_maze.c - 1][test_maze.r].place == 'C') && (maze[test_maze.c - 1][test_maze.r].used == 0))
		{
			q.push(maze[test_maze.c - 1][test_maze.r]);
		}
	}




	if (test_maze.c + 1 <= column)
	{
		if (maze[test_maze.c + 1][test_maze.r].place != '#' && (maze[test_maze.c + 1][test_maze.r].place == '.' || maze[test_maze.c + 1][test_maze.r].place == 'S' || maze[test_maze.c + 1][test_maze.r].place == 'C') && (maze[test_maze.c + 1][test_maze.r].used == 0))
		{
			q.push(maze[test_maze.c + 1][test_maze.r]);
		}
	}



	if (test_maze.r + 1 <= row)
	{

		if (maze[test_maze.c][test_maze.r + 1].place != '#' && (maze[test_maze.c][test_maze.r + 1].place == '.' || maze[test_maze.c][test_maze.r + 1].place == 'S' || maze[test_maze.c][test_maze.r + 1].place == 'C') && (maze[test_maze.c][test_maze.r + 1].used == 0))
		{
			q.push(maze[test_maze.c][test_maze.r + 1]);
		}
	}



	if (test_maze.r - 1 >= 0)

	{

		if (maze[test_maze.c][test_maze.r - 1].place != '#' && (maze[test_maze.c][test_maze.r - 1].place == '.' || maze[test_maze.c][test_maze.r - 1].place == 'S' || maze[test_maze.c][test_maze.r - 1].place == 'C') && (maze[test_maze.c][test_maze.r - 1].used == 0))
		{
			q.push(maze[test_maze.c][test_maze.r - 1]);
		}
	}
	
	}







	for (int c = 0; c < column; ++c)
	{
		for (int r = 0; r < row; ++r)
		{
			std::cout << maze[c][r].place;
		}
		std::cout << std::endl;
	}
	std::cout << start_r << "  " << start_c;
	std::cin.get();
	return 0;
}


in the maze.in file is number of rows,columns and the maze(example -
8 3
S#....#F
.#.##.#.
........

(S - start # - wall . - empty space F - finish)

My questions:
1)Am I using the BFS the right way?

2)Is there a way to make the maze structure size acording to one written in the maze.in so i don´t have to use some big maze like 50x50?

3)How can i keep track of the track in maze? I was thinking about writing coordinates of every step and the number of steps and then compare the numbers of steps to find the shortest way but I don´t know what to do when the ways splits like in the example file

Thanks

Last edited on
Topic archived. No new replies allowed.