Класс-обёртка представлен ниже для нахождения кратчайшего пути меж двумя объектами при наличии барьеров. Был написан мною в студенческие годы для самообразования
Code:
#ifndef PATHBUILDER_H
#define PATHBUILDER_H
#include <vector>
#include <iterator>
using namespace std;
class CPathBuilder {
public:
//posible values of i,j element:
//0 -- emty field;
//-1 -- point
//-2 -- wall
//the path will be returned as a POINT structure array
//each element shows i,j pair.
CPathBuilder(int **matrix, int w, int h, POINT start, POINT finish) :
m_matrix(matrix), m_width(w), m_height(h), m_start(start),
m_finish(finish), m_len(-1), m_path(NULL) {}
virtual ~CPathBuilder() {
if(m_path) {
delete[] m_path;
m_path = NULL;
}
}
void MakeWave() {
bool doBreak = false;
int count = 1, iter = 0;
POINT pt, *pts = &m_start;
vector<POINT> vec;
struct Area {
bool pred;
int i;
int j;
};
while(pts) {
int newCount = 0;
for(int i = 0; (i < count) && !doBreak; i++) {
Area area[4] = { {pts[i].x > 0 && pts[i].y < m_width, pts[i].x - 1, pts[i].y},
{pts[i].x < m_height - 1 && pts[i].y < m_width, pts[i].x + 1, pts[i].y},
{pts[i].y > 0 && pts[i].x < m_height, pts[i].x, pts[i].y - 1},
{pts[i].y < m_width - 1 && pts[i].x < m_height, pts[i].x, pts[i].y + 1} };
for(int j = 0; j < 4; j++)
if(area[j].pred && m_matrix[area[j].i][area[j].j] == 0) {
m_matrix[area[j].i][area[j].j] = iter + 1;
pt.x = area[j].i;
pt.y = area[j].j;
if((doBreak = Stop(pt))) {
m_len = iter + 1;
BuildPath(pt);
break;
}
vec.push_back(pt);
newCount++;
}
}
if(doBreak || newCount == 0) {
if(pts && iter) delete[] pts;
vec.clear();
break;
}
if(iter) delete[] pts;
pts = new POINT[newCount];
memcpy(pts, &vec[0], sizeof(POINT)*vec.size());
count = newCount;
vec.clear();
iter++;
}
}
POINT* GetPath() const {return m_path;}
int GetLength() const {return m_len;}
private:
bool Stop(const POINT& pnt) const {
return ((m_finish.x && pnt.x == m_finish.x - 1) && (pnt.y == m_finish.y) ||
((m_finish.x < m_height - 1 && pnt.x == m_finish.x + 1) && (pnt.y == m_finish.y)) ||
((m_finish.y && pnt.y == m_finish.y - 1) && (pnt.x == m_finish.x)) ||
((m_finish.y < m_width - 1 && pnt.y == m_finish.y + 1) && (pnt.x == m_finish.x)));
}
void BuildPath(const POINT& pt) {
int length = m_len;
if(m_path) {
delete[] m_path;
m_path = NULL;
}
m_path = new POINT[m_len];
m_path[0] = pt;
for(int j = 1; j < m_len; j++) {
if(m_path[j - 1].x && m_matrix[m_path[j - 1].x - 1][m_path[j - 1].y] == length - 1) {
m_path[j].x = m_path[j - 1].x - 1;
m_path[j].y = m_path[j - 1].y;
length--;
continue;
}
if(m_path[j - 1].x < m_height - 1 && m_matrix[m_path[j - 1].x + 1][m_path[j - 1].y] == length - 1) {
m_path[j].x = m_path[j - 1].x + 1;
m_path[j].y = m_path[j - 1].y;
length--;
continue;
}
if(m_path[j - 1].y && m_matrix[m_path[j - 1].x][m_path[j - 1].y - 1] == length - 1) {
m_path[j].x = m_path[j - 1].x;
m_path[j].y = m_path[j - 1].y - 1;
length--;
continue;
}
if(m_path[j - 1].y < m_width - 1 && m_matrix[m_path[j - 1].x][m_path[j - 1].y + 1] == length - 1) {
m_path[j].x = m_path[j - 1].x;
m_path[j].y = m_path[j - 1].y + 1;
length--;
continue;
}
}
}
int **m_matrix, m_width, m_height, m_len;
POINT m_start, m_finish, *m_path;
};
#endif