Subscribe to EdwinNameless' Fake Blog

Pathfinding: Walk on the Bridge (II)

Another constraint to the bridge exercise was to give the length of the bridge found. I had not looked into this as this has very little interest (it would be more relevant if we actually were looking for the shortest one...), but to be complete, here is the solution with the length. The idea is to keep track of the distance of a point. Candidates are considered 1 unit further than the current node -- so by iteration, it is easy to count the length.

```#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;
int distance;

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

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

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

~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, distance+1);
}

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

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

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

static std::list<point> visited;
static int length;

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)) {
length = current.distance;
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);

length = -1;

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

```

Again, this doesn't give the shortest path, but just says whether a bridge can be built or not. More on this later.

1 Comments On This Entry

Page 1 of 1

diego_pmc

07 November 2009 - 05:25 AM

Quote

I had not looked into this as this has very little interest (it would be more relevant if we actually were looking for the shortest one...)

Finding the shortest possible bridge is actually one of the requirements of the full exercise. I said previously, finding whether or not it is possible to build a bridge between two points is only part of the full exercise. The paper sheet with the instructions is in Romanian and it's quite a lot to translate so I only mentioned the details relevant to this particular algorithm. Besides, in order to find the shortest bridge you must first calculate the length of all bridges, right?

There are a few other things you are asked to do in that exercise. For example you have to find out how many islands* each country has on the map. I only mentioned the bridge part because that's the hardest one.

*Two elements belong to the same island if they are of the same value and they are neighbors, or if they are of the same value and if you can get from one element to the any other through neighbor elements.
```1 isle  2 isles  3 isles
0001    2020     0030
0011    0220     0300
0110    0000     3000
```
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
12345
6789101112
13141516171819
202122232425 26
27282930