Я написал реализацию алгоритма поиска пути А*. Проблем с кодом вроде бы нет, но убедительная просьба - пожалуйста, кому не лень, выскажите свои мнения о реализации (именно реализация, а не поиск факта неуместного имени объекта). Особенно хотелось бы знать, видит ли кто места утечек, заранее огромное спасибо откликнувшимся.
//класс Node - представляет узел графа (в данном случае это ячейка сетки)
class Node
{
public:
Node ( ) { }
Node ( const vector2df &position, Node* cameFrom ) : m_position ( position ), m_cameFrom ( cameFrom ) { }
Node ( const Node& node )
{
m_position = node.m_position;
m_g = node.m_g;
m_h = node.m_h;
m_f = node.m_f;
m_cameFrom = node.m_cameFrom;
}
~Node ( )
{
m_cameFrom = nullptr;
}
vector2df getPosition ( ) const
{
return m_position;
}
void setPosition ( const vector2df &position )
{
m_position = position;
}
Node* getCameFrom ( ) const
{
return m_cameFrom;
}
void setCameFrom ( Node* cameFrom )
{
m_cameFrom = cameFrom;
}
float getG ( ) const
{
return m_g;
}
float getH ( ) const
{
return m_h;
}
float getF ( ) const
{
return m_f;
}
void setG ( float G )
{
m_g = G;
}
void setH ( float H )
{
m_h = H;
}
void setF ( float F )
{
m_f = F;
}
void computeF ( )
{
m_f = m_g + m_h;
}
// Compute heruistic path length
static float computeH ( const vector2df &start, const vector2df &goal )
{
return std::abs ( start.x - goal.x ) + std::abs ( start.y - goal.y );
}
// Neighbours nodes
static std::list<Node> getNeighbours ( const Grid &gridMap, std::list<Node> &closedNodes, const vector2df goal)
{
Node &core = closedNodes.back ( );
auto neighboursCell = gridMap.getNeighboursForCell ( core.getPosition ( ) );
std::list<Node> neighboursNodes;
for ( auto nodePosition : neighboursCell )
{
Node currentNeighbour ( nodePosition, &core );
if ( nodePosition.x == core.getPosition ( ).x || nodePosition.y == core.getPosition ( ).y )
currentNeighbour.setG ( core.getG ( ) + 1.0f );
else
currentNeighbour.setG ( core.getG ( ) + 1.5f );
currentNeighbour.setH ( computeH ( nodePosition, goal ) );
currentNeighbour.computeF ( );
neighboursNodes.push_back ( currentNeighbour );
}
return neighboursNodes;
}
static std::list<Node>::iterator Insert ( std::list<Node> &listNodes, const Node &currNode)
{
std::list<Node>::iterator iter = listNodes.begin ( );
while ( iter != listNodes.end ( ) && iter->m_f <= currNode.m_f )
iter++;
iter = listNodes.insert ( iter, currNode );
return iter;
}
bool operator < ( const Node &n2 ) const
{
return m_f < n2.m_f;
}
bool operator == ( const Node &n2 )
{
return m_position == n2.m_position;
}
private:
vector2df m_position;
Node* m_cameFrom;
float m_g; // path length from Start
float m_h; // heruistic estimate path length to Goal
float m_f; // estimate full path length
};
class PathFinder
{
public:
PathFinder ( ) { }
// Поиск кратчайшего пути
static std::list<vector2df> AStar ( Grid &gridMap, vector2df &start, vector2df &goal )
{
// Списки узлов
std::list<Node> closed; // рассмотренные узлы
std::list<Node> opened; // на рассмотрении
// Стартовый узел
Node startNode( start, nullptr ); // его позиция и предок
startNode.setG ( 0.0f ); // сколько пройти пришлось до этого узла
startNode.setH ( Node::computeH( start, goal ) ); // сколько приблизительно еще топать
startNode.computeF ( ); // общая оценка пути
// Помещаем его в список на рассмотрение
opened.push_back ( startNode );
// Пока есть узлы на рассмотрении
while ( !opened.empty ( ) )
{
// Текущий узел на рассмотрении
Node currentNode ( opened.front ( ) );
// Если текущий узел наша цель возвращаем его
if ( currentNode.getPosition ( ) == goal )
return PathRetrive ( ¤tNode );
// Текущий узел рассмотрен
closed.push_back ( currentNode );
opened.pop_front ( );
// Находим соседей (разворачиваем узел)
auto neighbours = currentNode.getNeighbours ( gridMap, closed, goal );
if ( neighbours.empty ( ) )
return std::list<vector2df> ( );
// Для каждого соседа
for (auto currentNeighbour : neighbours)
{
// Если он закрыт, пропускаем его и переходим к следующему
auto closeNodeIter = std::find ( closed.begin ( ), closed.end ( ), currentNeighbour );
if ( closeNodeIter != closed.end ( ) )
continue;
// Ищем соседа в открытом векторе
auto openNodeIter = std::find ( opened.begin ( ), opened.end ( ), currentNeighbour );
if ( openNodeIter == opened.end ( ) )
{
Node::Insert ( opened, currentNeighbour );
}
else if ( openNodeIter->getG ( ) > currentNeighbour.getG ( ) )
{
openNodeIter->setCameFrom ( &closed.back ( ) );
openNodeIter->setG ( currentNeighbour.getG ( ) );
openNodeIter->computeF ( );
}
}
}
return std::list<vector2df> ( );
}
private:
static std::list<vector2df> PathRetrive ( Node* goalNode )
{
std::list<vector2df> Path;
while ( goalNode )
{
Path.push_front ( goalNode->getPosition ( ) );
goalNode = goalNode->getCameFrom ( );
}
return Path;
}
};