Subscribe to EdwinNameless' Fake Blog        RSS Feed
-----

Pathfinding: Walk on the Bridge

Icon 3 Comments
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 Icon

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 111113: 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 115117 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 Icon

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 Icon

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

About...

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

July 2014

S M T W T F S
  12345
6789101112
13141516171819
20212223 24 2526
2728293031  

Recent Entries

Recent Comments

Search My Blog

0 user(s) viewing

0 Guests
0 member(s)
0 anonymous member(s)