I wrote the implementation of the pathfinding algorithm A *. There seems to be no problems with the code, but please, please, please feel free to express your opinions on the implementation (it is the implementation, not the search for the fact that the object name is inappropriate). I would especially like to know if anyone sees the places of leaks, many thanks in advance to those who responded.

//класс 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 ( &currentNode ); // Текущий узел рассмотрен 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; } };
  • one
    The question is off topic. To automatically search for leaks, I recommend using Address Sanitizer ( clang.llvm.org/docs/AddressSanitizer.html ) or Valgrind ( valgrind.com ). Both are only for Linux, the first is faster. - dzhioev
  • 2
    In general, there is nowhere to take the leaks, because you don't explicitly allocate memory anywhere. The implementation itself is far from optimal, since as a repository of closed and open nodes, lists are used in which a linear search is performed at each iteration. - dzhioev
  • codereview.stackexchange.com - theoden
  • 2
    @theoden On our site, such questions are permissible: meta.ru.stackoverflow.com/q/1761 However, there is a lot of code in this question that speaks not in his favor, of course. - Athari
  • @Discord, thanks for the comment, I will consider) - neitron

1 answer 1

Leaks are detected with the help of tools and tests, and not with the help of intently looking at the code, so I cannot help you with this. But on the code - speak out.

  1. Your code, as implemented in OOP style, claims a common solution, but SRP is broken in it. Why is the Node class, essentially a service one, responsible for calculating heuristics? This concept is outside the algorithm, it comes from the outside as a parameter for the search.

  2. The names of the methods leave much to be desired. Names in the style of "f", "g" and "h" are valid in mathematics, but unacceptable in programming. Here you need to use normal names, for example, "heuristic", "cost", etc.

  3. You have thoughtlessly written public getters and setters, although they are not used. For example, the setF method is not used anywhere; in fact, only computeF . You should decide on the public interface of classes.

  4. Using the list collection is a bad idea in most cases. You need a collection that quickly checks for the inclusion of the element: set , unordered_set / hash_set .

  • Very grateful to you for the detailed comments !!!) - neitron