C++

Forum

 
Problem with pathfinding

Dever1954 (12)
Hey guys!
I have to write a program which checks if a cat can reach every blank tile of a garden. The garden could look sth.like this: 
1
2
3
4
 
######
#  # #
##   #
######


Where the #'s would be obstacles and the whitespaces would be walkable. 
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
 
#include <iostream>
#include <cstdlib>
#include <string>
#define WIDTH 6
#define HEIGHT 4

void print(char Garden[HEIGHT][WIDTH]);

int main()
{
	bool everyTileReachable = true;
	int walkableTiles = 0;
	int x;
	int y;
	std::string result;
	char Garden[HEIGHT][WIDTH] = { 
{'#','#','#','#','#','#'},
{'#','C',' ','#',' ','#'},
{'#','#',' ',' ',' ','#'},
{'#','#','#','#','#','#'}};


	for (int i = 0; i < HEIGHT; i++)
	{
		for (int j = 0; j < WIDTH; j++)
		{
			if (Garden[i][j] == ' ')
			{
				walkableTiles++;
			}
			if (Garden[i][j] == 'C')
			{
				y = i;
				x = j;
			}
		
		}
	}
	
	while (walkableTiles != 0)
	{
		if (Garden[y][x] == ' '||Garden[y][x]=='C')
		{
			if (Garden[y-1][x] != '#')
			{
				Garden[y][x] = '#';
				y--;
				walkableTiles--;
				print(Garden);
				std::cout << std::endl;
			}
			else if (Garden[y][x-1] != '#')
			{
				Garden[y][x] = '#';
				x--;
				walkableTiles--;
				print(Garden);
				std::cout << std::endl;
			}
			else if (Garden[y+1][x] != '#')
			{
				Garden[y][x] = '#';
				y++;
				walkableTiles--;
				print(Garden);
				std::cout << std::endl;
			}
			else if (Garden[y][x+1] != '#')
			{
				Garden[y][x] = '#';
				x++;
				walkableTiles--;
				print(Garden);
				std::cout << std::endl;
			}
			else
			{
				break;
			}
		}
	}

	if (walkableTiles == 0)
	{
		result = "yes";
	}
	else
	{
		result = "no";
	}
	std::cout << "Can the cat reach every tile: " << result << std::endl;
	system("pause");
	return 0;
}


void print(char Garden[HEIGHT][WIDTH])
{
	for (int i = 0; i < HEIGHT; i++)
	{
		for (int j = 0; j < WIDTH; j++)
		{
			std::cout << Garden[i][j];
		}
		std::cout << std::endl;
	}
}


It works for this one, but if I change the garden to e.g. 
1
2
3
4
5
 
#########
#  c    #
# ###   #
#       #
#########

it doesn't work anymore and tells me that not every tile is reachable even though they are...

Can anybody help me please?
Last edited on
cire (8284)
First, if you change the garden, the constants specifying its dimensions must also change.

Second, you are modifying the walkability of areas of the garden as you iterate. It shouldn't be any surprise that this can affect your results.
Dever1954 (12)
First, if you change the garden, the constants specifying its dimensions must also change.

Sorry for not being clear on this one, I changed the values of HEIGHT and WIDTH when I changed the garden.

Second, you are modifying the walkability of areas of the garden as you iterate. It shouldn't be any surprise that this can affect your results.

Could you give me a hint on how to solve this without changing the walkability of a tile?
Last edited on
cire (8284)
Generally, you use another grid to keep track of whether you've visited a particular location or not.
Dever1954 (12)
Thank you very much for this hint! Would you mind telling me how I stop the cat from always going left and right in the first example I provided? If I start the program now, the cat goes right, and after that left again then right again... how would I make her go down?
cire (8284)
Moving the cat isn't necessary. The cat is just a way of selecting the area you need to explore.

You might want to google "floodfill algorithm" or "Djikstra's algorithm." The goal of Djikstra's algorithm is a little different than yours, but it can enumerate all reachable locations in the process.

And, if you've any interest in pathfinding at all, visit:
http://www.redblobgames.com/pathfinding/a-star/introduction.html
Dever1954 (12)
Thank you again for the floodfill algorithm, it helped me solve the first problem. however now I have to find out if its possible to walk through the garden by visiting each tile exactly once and print out the directions the cat has to take. Do you have an algorithm for that too ;) ?

Btw: The website you have there is amazing!
Last edited on
cire (8284)
Do you have an algorithm for that too ;) ?

It is essentially a graph traversal problem. A depth first search for paths that contain each node or location without duplicates would do the trick.

One needn't form an actual graph. It should be sufficient to think of the location the cat occupies as the beginning node and each adjacent, reachable location as a connected node. (Again, you'll find a "parallel grid" useful in determining if a node has been visited.)


Btw: The website you have there is amazing!

Not my website.
Dever1954 (12)
It should be sufficient to think of the location the cat occupies as the beginning node and each adjacent, reachable location as a connected node.


How could I accomplish this? A DFS checks the edges a node has to another, but in a 2 dimensional array you don't have any edges.
cire (8284)
How could I accomplish this? A DFS checks the edges a node has to another, but in a 2 dimensional array you don't have any edges.


As I said, an adjacent reachable location is a connected node. The edge is an implied one.
Last edited on
Dever1954 (12)
I'm sorry if I'm annoying, but I don't really understand how I could make the computer check for a way and print out the directions... I know it's more or less a no-go to ask for yode, but could you provide a small example program? Doesn't have to be anything too complex, just so I can have a look at it to understand the whole thing.
Last edited on
cire (8284)
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
 
#include <iostream>
#include <vector>
#include <string>

struct vec
{
    unsigned x, y;
};

using grid_type = std::vector<std::string>;

vec operator+(vec a, vec b)
{
    return{ a.x + b.x, a.y + b.y };
}

vec dir [] = { {0,-1}, {0,1}, {-1, 0}, {1, 0} };

char& at(grid_type& grid, vec pos)
{
    return grid[pos.y][pos.x];
}

void display(const grid_type& grid)
{
    for (auto& row : grid)
        std::cout << row << '\n';
    std::cout << '\n';
}

void iterate_path(grid_type& grid, vec pos, unsigned node = 0 )
{
    if (at(grid, pos) != ' ')
        return;

    std::cout << "Row: " << pos.y << ", Col: " << pos.x << '\n';
    at(grid, pos) = '0' + node;
    display(grid);
    std::cin.ignore(1000, '\n');

    for (auto dir_vec : dir)
        iterate_path(grid, pos + dir_vec, node + 1);

    std::cout << "Backtracking..\n";
    at(grid, pos) = ' ';
}

int main()
{
    std::vector<std::string> grid =
    {
        "#####",
        "#   #",
        "#   #",
        "#    #",
        "######",
    };

    vec start_pos = { 1,1 };

    iterate_path(grid, start_pos);
}


If it's not obvious, hit <ENTER> to advance the iteration.
Last edited on
Dever1954 (12)
That's truly amazing, thanks a lot! I'll spend the next time studying your code :)
cire (8284)
The members of the vec type should logically be int and not unsigned although it (as you've probably noticed) should work as-is.
Last edited on
Dever1954 (12)
One last question, I modified it a bit to end as soon as one way is found and now I'd like to save the directions taken in a string. So far so good, but I somehow can't manage to append them correctly, could you have a look at this part of the code please?
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
 
for (auto dir_vec : Richtung){
		if (dir_vec.y == -1)
		{
			Way.append("N");

		}
		if (dir_vec.y == 1)
		{
			Way.append("S");

		}
		if (dir_vec.x == 1)
		{
			Way.append("E");

		}
		if (dir_vec.x == -1)
		{
			Way.append("W");

		}
		iterate_path(grid, pos + dir_vec, node + 1);
	}

	std::cout << "Backtracking..\n";

	if (!Way.empty())
       {
		Way.pop_back();
	}
	at(grid, pos) = ' ';
}

It returns completly strange ways...
1
2
3
4
5
6
 
#########
#__#____#
#__#_#__#
#__C_#__#
#____#__#
#########

The output for this garden is:
1
2
3
4
 
NSNSWNNNNSWNSNSNSNSWWWWSWNNSWONSSNSNSWWWSWNNNSWONSNSWSWONNSWNSWSSNSWWSWNNNNSWONS
NSNSWWSWONNSWNSWSNSWSWONNNSWNSNSWWSWNNSWONSSWSSWONNNNSWONSWONSNSNSNSWONNNNSWSWSW
SWONNNSWSWSNSWNSWWONNSWSNSNSWNNSWSWWNSNSWONSWWONSNSNSNSWNNNSWSWSWWNNSWSNSWONSWWN
SNSNSWONNSWSWONSNSWNSSWSWSWNNNSWNSNSNSNSWONSWONSWONNNNSWONSWONSNSNSNSWONNN
Last edited on
cire (8284)
For a given invocation of iterate_path up to 4 items can be added to your string, so when you're backtracking, all of those items should be removed.

(And, in fact, you probably want to remove them in the same loop that adds them, since you don't want calls to iterate_path with extra directions in the string.)

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
 
or (auto dir_vec : Richtung){
		if (dir_vec.y == -1)
		{
			Way.append("N");

		}
		if (dir_vec.y == 1)
		{
			Way.append("S");

		}
		if (dir_vec.x == 1)
		{
			Way.append("E");

		}
		if (dir_vec.x == -1)
		{
			Way.append("W");

		}
		iterate_path(grid, pos + dir_vec, node + 1);
                Way.pop_back();
	}

	std::cout << "Backtracking..\n";
	at(grid, pos) = ' ';
}
Last edited on
Dever1954 (12)
It works! You're the best! Thank you very much :D
Topic archived. No new replies allowed.