[AvDav]

Класс-обёртка представлен ниже для нахождения кратчайшего пути меж двумя объектами при наличии барьеров. Был написан мною в студенческие годы для самообразования

#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