Subscribe to EdwinNameless' Fake Blog

## Pathfinding: Walk on the Bridge

diego_pmc posted an interesting exercise involving pathfinding. I am new to this field, so despite being aware that there are some algorithms out there to solve this kind of problems (like A*, Dijkstra, etc.), I thought I would give it a bash myself and see if I can come up with something acceptable. And here it is. Comments to follow.

```#include <list>
#include <cmath>
#include <string>
#include <iostream>
#include <cassert>
#include <cstdlib>
#include <algorithm>

const int X_MAX = 6;
const int Y_MAX = 6;

class point {
public:
int x;
int y;

point() : x(0), y(0) {
}

point(int x, int y) : x(x), y(y) {
}

~point() {
}

void print() const {
std::cout << "(" << x << "," << y << ")" << std::endl;
}

bool operator==(point p) const {
return x == p.x && y == p.y;
}

bool is_neighbour(point p) {
return ((std::abs((double) x - p.x) == 1 && y == p.y) ||
(std::abs((double) y - p.y) == 1 && x == p.x));
}

point west() {
assert((y - 1) > 0);
return point(x, y - 1);
}

point east() {
assert(y + 1 < Y_MAX);
return point(x, y + 1);
}

point north() {
assert(x - 1 > 0);
return point(x - 1, y);
}

point south() {
assert(x + 1 < X_MAX);
return point(x + 1, y);
}
};

static std::list<point> visited;

bool is_point_visited(point p) {
std::list<point>::iterator result = std::find(visited.begin(), visited.end(), p);
return *result == p;
}

// Adjust coordinates to have (0,0) at the bottom left-hand corner.
char get_char(point p, std::string* map) {
return map[Y_MAX - p.y - 1][p.x];
}

// Will be useful for the terminating condition.
bool has_arrived(point current, point end) {
return current.is_neighbour(end);
}

std::list<point> find_candidates(point current, std::string* map) {
std::list<point> candidates;

// West
if (current.y - 1 > 0 && get_char(current.west(), map) == '0') {
if (!is_point_visited(current.west()))
candidates.push_back(current.west());
}

// East
if (current.y + 1 < Y_MAX && get_char(current.east(), map) == '0') {
if (!is_point_visited(current.east()))
candidates.push_back(current.east());
}

// North
if (current.x - 1 > 0 && get_char(current.north(), map) == '0') {
if (!is_point_visited(current.north()))
candidates.push_back(current.north());
}

// South
if (current.x + 1 < X_MAX && get_char(current.south(), map) == '0') {
if (!is_point_visited(current.south()))
candidates.push_back(current.south());
}

return candidates;
}

bool iter(point current, point end, std::string* map) {
visited.push_front(current);
if (has_arrived(current, end)) {
return true;
}
std::list<point> candidates = find_candidates(current, map);
if (candidates.empty()) {
return false;
} else {
while (!candidates.empty()) {
if (iter(candidates.front(), end, map)) {
return true;
} else {
candidates.pop_front();
}
}
return false;
}
}

int main() {

std::string map[] = {"1000020",
"0100113",
"3003000",
"2033000",
"2003111",
"2000010"};

point start(0, 0);
point end(5, 5);

if (iter(start, end, map)) {
std::cout << "indeed" << std::endl;
} else {
std::cout << "nope" << std::endl;
}
std::cout << "visited " << visited.size() << " nodes." << std::endl;
}

```

The core of all this is the point class; it is able to return its neighbours, which is key to the discovering of the regions. The "searching" work is all done in the iter function (which probably deserves a better name, come to think of it) which works by recursion:
• Put the current point into the "visited" list. This list holds the points that have already been visited.
• Check if the end point is the neighbour. If it is, then a bridge can be built.
• If not, look for candidates, i.e. neighbour points which hold '0', and not already visited. For each of these neighbour points, call the iter function.

The "visited" list is key to make sure we don't loop over points we've already looked at. All in all, we have a depth-first approach which is appropriate fir the current situation where we just want to find whether a bridge can be built or not (whether a solution exists or not).

One of the tricky "things" was to map the string array into a coordinate system that makes sense. I wanted to have (0,0) at the bottom left-hand corner. To avoid getting into tedious thought gymnastics between the string array and my coordinate system, I wrote the get_char that makes it all transparent.

### 3 Comments On This Entry

Page 1 of 1

#### diego_pmc

07 November 2009 - 05:03 AM
Nice approach. It's a lot cleaner than what I originally thought about doing. There are two minor issues however:

• On lines 111–113: criteria #1 and #2 demand that the bridge starts and ends on a segment covered by water, which means there must be at least one '0' in between the two territories. So it should return false if the start and end points are neighbors.
```    if (has_arrived(current, end)) {
return true;
}
```

However it appears that this if statement is the exit out of the recursive function, so it might need a little rethinking in order to fix.

• I don't think lines 115–117 are really needed. You could just keep the while loop and it will work exactly the same.This...
```    if (candidates.empty()) { // this condition is checked again in the loop below
return false;
} else {
while (!candidates.empty()) {
if (iter(candidates.front(), end, map)) {
return true;
} else {
candidates.pop_front();
}
}
return false;
}
```

... could be written like this...
```    while (!candidates.empty()) {
if (iter(candidates.front(), end, map)) {
return true;
} else {
candidates.pop_front();
}
}
return false;
```
0

#### EdwinNameless

07 November 2009 - 05:14 AM

diego_pmc, on 7 Nov, 2009 - 04:03 AM, said:

Nice approach. It's a lot cleaner than what I originally thought about doing. There are two minor issues however:

2 very good points indeed. Thanks a mil for that.
0

#### diego_pmc

08 November 2009 - 04:28 AM
A quick fix would be:

```	if ((has_arrived(current, end)) && (map[current.y][current.x] == '0')) {
return true;
}
```
0
Page 1 of 1

This is my fake blog. 'Cause I also have a real blog with real stuff in it.

S M T W T F S
1234
567891011
12131415161718
19 202122232425
2627282930