Armenian Knowledge Base  

Go Back   Armenian Knowledge Base > Technical sections > Languages, Compilers, Interpreters > Algorithms
Register

Reply
 
LinkBack Thread Tools
Old 02.02.2014, 16:27   #1
The splendid
 
AvDav's Avatar
 
Join Date: 07 2004
Location: Universe
Age: 36
Posts: 3,413
Downloads: 22
Uploads: 0
Reputation: 222 | 3
Default Lee's maze routing algorithm (a wrapper class)

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

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
Reply With Quote
Reply

Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
PHP Class Define kernel Web Development 18 04.07.2007 12:14
Routing to gmail.com from arminco acid General 0 06.08.2004 10:41
Source routing in Windows? shatver Unix 4 17.11.2003 17:57
Maze - Armenian Rock Band From Lebanon HOB MusiCity 1 05.05.2003 01:46
VPN routing il RH Linux 7.3 help please putin Unix 1 25.04.2003 13:32


На правах рекламы:
реклама

All times are GMT. The time now is 14:00.


Powered by vBulletin® Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.