![]() |
![]() | #1 |
Профессор Join Date: 07 2004 Location: Own world Age: 39
Posts: 3,656
Downloads: 22 Uploads: 0
Reputation: 228 | 4 | ![]()
Класс-обёртка представлен ниже для нахождения кратчайшего пути меж двумя объектами при наличии барьеров. Был написан мною в студенческие годы для самообразования ![]() 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 |
![]() |
![]() |
Thread Tools | |
|
![]() | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
PHP Class Define | kernel | Web Development | 18 | 04.07.2007 11:14 |
Routing to gmail.com from arminco | acid | General | 0 | 06.08.2004 09: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 00:46 |
VPN routing il RH Linux 7.3 help please | putin | Unix | 1 | 25.04.2003 12:32 |
На правах рекламы: | |
![]() | |