C++

Forum

 
Find all paths of a maze. Different than most.

Darkpony (4)
I need to find all paths of a maze. I have looked up examples but they aren't any help. Please dont link me to any. I am using a 1D vector that acts like a 2D vector. I am given a board with a hole(I treat this hole as a visited square) a start position and a finish position. I am to find all possible paths from the start to finish. I must touch all squares except for the hole of course.

Here is how I implement my code
Test base case
(squaresleft - 2 == 0) && on finish positions I increment my count.

1.Check to see if my vector is in range
2.Check to see if I visited the Cell
3. Decrement -- squares
3.Change my pos_x and pos_y values
4.Change the value in that cell to 1
5.Begin recursion
6.Now begins backtracking. Change the value to 0
7.Increment squares
8.Revert my position.

I am passing everything by value atm because my code isnt returning the right values.


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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
 
#include "counthsr.h"
#include <iostream>
#include <vector>


/*
is the recursion function. Checks if the vector is in range and moves the x and y position
*/

int SpiderCount::countHSR_recurse(std::vector<int> ary,
	int dim_x, int dim_y,
	int finish_x, int finish_y,
	int pos_x, int pos_y,
	int _squaresLeft)
{
	/*
	BASE CASE RETURNS IF SQUARES LEFT = 0 AND ON THE FINISH LINE INCREMENT TOTAL
	*/
	if ((_squaresLeft == 0) && (pos_x == finish_x) && (pos_y == finish_y))
	{
		std::cout << "Increminting the total";
		total++;
	}

	/*
	MOVE RIGHT
	*/
	if (isCell(pos_x + 1, pos_y, dim_x, dim_y))
	{
		if (ary[(pos_x + 1)*(dim_y) + pos_y] == 0) // means we havent been there
		{
			--_squaresLeft; // decrement the squares left
			(pos_x) += 1; // move our position
			ary[(pos_x)*(dim_y) + (pos_y)] = 1; // set that position to visited
			countHSR_recurse(ary, dim_x, dim_y, finish_x, finish_y, pos_x, pos_y, _squaresLeft); // recursion
			ary[(pos_x)*(dim_y) + (pos_y)] = 0; // backtracking set our position to 0
			++_squaresLeft; // increment our squares left
			pos_x -= 1; // move back
		}
	}

	// MOVE UP
	if (isCell(pos_x, pos_y + 1, dim_x, dim_y))
	{
		if (ary[(pos_x)*(dim_y) + (pos_y + 1)] == 0)
		{
			--_squaresLeft;
			pos_y += 1;
			ary[(pos_x)*(dim_y) + (pos_y)] = 1;
			countHSR_recurse(ary, dim_x, dim_y, finish_x, finish_y, pos_x, pos_y, _squaresLeft);
			ary[(pos_x)*(dim_y) + (pos_y)] = 0;
			++_squaresLeft;
			pos_y -= 1;
			
		}
	}

	// MOVE LEFT
	if (isCell(pos_x - 1, pos_y, dim_x, dim_y))
	{
		if (ary[(pos_x)*(dim_y) + pos_y ] == 0)
		{
			--_squaresLeft;
			pos_x += -1;
			ary[(pos_x)*(dim_y) + (pos_y)] = 1;
			countHSR_recurse(ary, dim_x, dim_y, finish_x, finish_y, pos_x, pos_y, _squaresLeft);
			ary[(pos_x)*(dim_y) + (pos_y)] = 0;
			++_squaresLeft;
			pos_x += 1;
		}
	}

	// MOVE DOWN
	if (isCell(pos_x, pos_y - 1, dim_x, dim_y))
	{
		if (ary[(pos_x)*(dim_y) + (pos_y - 1)] == 0)
		{
			--_squaresLeft;
			pos_y += -1;
			ary[(pos_x)*(dim_y) + (pos_y)] = 1;
			countHSR_recurse(ary, dim_x, dim_y, finish_x, finish_y, pos_x, pos_y, _squaresLeft);
			ary[(pos_x)*(dim_y) + (pos_y)] = 0;
			++_squaresLeft;
			pos_y += 1;
		}
	}

	//MOVE LEFT/DOWN
	if (isCell(pos_x - 1, pos_y - 1, dim_x, dim_y))
	{
		if (ary[(pos_x-1)*(dim_y)+(pos_y - 1)] == 0)
		{
			--_squaresLeft;
			pos_y += -1;
			pos_x += -1;
			ary[(pos_x)*(dim_y)+(pos_y)] = 1;
			countHSR_recurse(ary, dim_x, dim_y, finish_x, finish_y, pos_x, pos_y, _squaresLeft);
			ary[(pos_x)*(dim_y)+(pos_y)] = 0;
			++_squaresLeft;
			pos_y += 1;
			pos_x += 1;
		}
	}

	// MOVE RIGHT/DOWN
	if (isCell(pos_x + 1, pos_y - 1, dim_x, dim_y))
	{
		if (ary[(pos_x+1)*(dim_y)+(pos_y - 1)] == 0)
		{
			--_squaresLeft;
			pos_y += -1;
			pos_x += 1;
			ary[(pos_x)*(dim_y)+(pos_y)] = 1;
			countHSR_recurse(ary, dim_x, dim_y, finish_x, finish_y, pos_x, pos_y, _squaresLeft);
			ary[(pos_x)*(dim_y)+(pos_y)] = 0;
			++_squaresLeft;
			pos_y += -1;
			pos_x += 1;
		}
	}

	//MOVE RIGHT/UP
	if (isCell(pos_x + 1, pos_y + 1, dim_x, dim_y))
	{
		if (ary[(pos_x + 1)*(dim_y)+(pos_y + 1)] == 0)
		{
			--_squaresLeft;
			pos_y += 1;
			pos_x += 1;
			ary[(pos_x)*(dim_y)+(pos_y)] = 1;
			countHSR_recurse(ary, dim_x, dim_y, finish_x, finish_y, pos_x, pos_y, _squaresLeft);
			ary[(pos_x)*(dim_y)+(pos_y)] = 0;
			++_squaresLeft;
			pos_y += -1;
			pos_x += -1;
		}
	}

	//MOVE LEFT/UP
	if (isCell(pos_x - 1, pos_y + 1, dim_x, dim_y))
	{
		if (ary[(pos_x - 1)*(dim_y)+(pos_y + 1)] == 0)
		{
			--_squaresLeft;
			pos_y += +1;
			pos_x += -1;
			ary[(pos_x)*(dim_y)+(pos_y)] = 1;
			countHSR_recurse(ary, dim_x, dim_y, finish_x, finish_y, pos_x, pos_y, _squaresLeft);
			ary[(pos_x)*(dim_y)+(pos_y)] = 0;
			++_squaresLeft;
			pos_y += -1;
			pos_x += 1;
		}
	}
	
	return total;
}
 /*
 Creates the board and calls our recursion function to to print out the count. This is our wrapper function
 */
int SpiderCount::countHSR(int dim_x, int dim_y, int hole_x, int hole_y, int start_x, int start_y, int finish_x, int finish_y)
{
	int pos_x = start_x; //create are start x
	int pos_y = start_y; // create are start y
	int _squaresleft = (dim_y*dim_x)-2; // because we start off with two squares taken away
	size = dim_x*dim_y; // size of the array
	std::vector<int> ary(dim_x*dim_y); // make the board
	ary[hole_x*dim_y + hole_y] = 1; // set our obstacle
	ary[start_x*dim_y + start_y] = 1; // set our start path as visited.
	return countHSR_recurse(ary, dim_x, dim_y, finish_x, finish_y, pos_x, pos_y, _squaresleft);
	

}

// checks if the vector is in range returns false if its not in range.
bool SpiderCount::isCell(int pos_x, int pos_y, int dim_x, int dim_y)
{
	if ((pos_x >= dim_x) || (pos_y >= dim_y)||(pos_x*dim_y + pos_y < 0))
		return false;
	return true;
}


int main()
{
	// run a test
	SpiderCount test;
	int count = test.countHSR(3, 2, 2, 1, 1, 1, 2, 0); // should return 2 but returns 5.
	std::cout << count;
}
Last edited on
jonnin (11340)
most of the algorithms online are either looking for the shortest path or some approximation of the shortest path (balance of best path vs speed).

To find them all is just a brute force search; you can tie segments together if you track all the intersections and when you hit an intersection you spawn N paths where N is the # of branches from the intersection.

By all paths, do you really mean it? What if there is a place where you can go in a loop, is going around it once one path, and going around twice another path? What about paths that end up in a dead end? Are you looking for solutions ONLY (get from 'start' to 'end') or every possible path of travel (no matter where it leads)?

Duthomhas (13143)
It is very odd that you are able to move diagonally. That allows movement like A to B:

    ██B
    A ██

Is that really correct?

Now, the way you have phrased your question leads us to believe that it is possible to get from start to finish multiple ways. If so, this complicates your program:

No matter how many paths you may take, each one may return that a successful path to finish is found in that direction. You must keep hold of information for all currently-encountered valid solutions as you backtrack. I am not convinced that this is likely your actual assignment.

If your assignment is to find a solution, then storing the solution becomes so much easier as you backtrack.
Darkpony (4)
It is my assignment. I must find all paths. That is why I increment total in my base case meaning I find a path. Also I'm not checking for impossible boards yet as I can't solve an easy 3x2. My backtracking after recursion seems right. My code from my point of view should work.
ne555 (10692)
> It is very odd that you are able to move diagonally.
8-connected is in no way odder than 4-connected

> I must find all paths.
¿do you want the paths (the order in which the cells are visited) or do you just care about the count of the number of paths?

> My code from my point of view should work.
perhaps, but your description is awful and the implementation quite dirty.
you've got a lot of repeated code when you visit the neighbours, not going to analyse it to find that you forgot to reset a state. Simplify it.

By the way
1
2
3
4
5
6
7
8
9
10
11
 
--_squaresLeft;
pos_x += -1;
ary[(pos_x)*(dim_y) + (pos_y)] = 1;
countHSR_recurse(ary, dim_x, dim_y, finish_x, finish_y, pos_x, pos_y, _squaresLeft);
ary[(pos_x)*(dim_y) + (pos_y)] = 0;
++_squaresLeft;
pos_x += 1;

//instead you may do
//(visit current cell as the first step in the recursion)
countHSR_recurse(ary, dim_x, dim_y, finish_x, finish_y, pos_x-1, pos_y, _squaresLeft-1);

there you may also do a loop 
1
2
3
 
for(int K=-1; K<=1; ++K)
	for(int L=-1; L<=1; ++L)
		countHSR_recurse(ary, dim_x, dim_y, finish_x, finish_y, pos_x-K, pos_y+L, _squaresLeft-1);

and it would be better if you use the return value instead of having a global `total'


> int count = test.countHSR(3, 2, 2, 1, 1, 1, 2, 0); // should return 2 but returns 5.
¿could you draw it?
Last edited on
Topic archived. No new replies allowed.