0

Я написал реализацию алгоритма поиска пути А*. Проблем с кодом вроде бы нет, но убедительная просьба - пожалуйста, кому не лень, выскажите свои мнения о реализации (именно реализация, а не поиск факта неуместного имени объекта). Особенно хотелось бы знать, видит ли кто места утечек, заранее огромное спасибо откликнувшимся.

//класс 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;
}
};
6
  • 1
    Вопрос не по теме. Для автоматического поиска утечек, рекомендую воспользоваться Address Sanitizer (clang.llvm.org/docs/AddressSanitizer.html) или Valgrind (valgrind.com). Оба только под Linux, первый пошустрее.
    – dzhioev
    14 дек 2015 в 23:21
  • 2
    Вообще утечкам тут взяться неоткуда, т.к. вы нигде явно не выделяете память. Сама имплементация далеко не оптимальна, т.к. в качестве хранилища закрытых и открытых узлов используются списки, в которых на каждой итерации проводится линейный поиск.
    – dzhioev
    14 дек 2015 в 23:31
  • codereview.stackexchange.com
    – theoden8
    15 дек 2015 в 0:59
  • 2
    @theoden На нашем сайте подобные вопросы допустимы: meta.ru.stackoverflow.com/q/1761 Впрочем, конкретно в этом вопросе многовато кода, что говорит не в его пользу, конечно.
    – Kyubey
    15 дек 2015 в 10:34
  • @Discord, спасибо за замечание, учту)
    – neitron
    16 дек 2015 в 14:41

1 ответ 1

3

Утечки определяются с помощью инструментов и тестов, а не с помощью пристального разглядывания кода, поэтому ничем помочь вам с этим не могу. А вот по коду — выскажусь.

  1. Ваш код, как реализованный в стиле ООП, претендует на общее решение, но в нём нарушается SRP. Почему класс Node, по сути служебный, отвечает за вычисление эвристики? Это понятие вне алгоритма, оно приходит извне как параметр для поиска.

  2. Названия методов оставляют желать лучшего. Названия в стиле "f", "g" и "h" допустимы в математике, но неприемлемы в программировании. Здесь нужно использовать нормальные названия, например, "heuristic", "cost" и т. п.

  3. Вы бездумно понаписали публичных геттеров и сеттеров, хотя они не используются. Например, метод setF нигде не используется, по сути работает только computeF. Вам следует определиться с публичным интерфейсом классов.

  4. Использование коллекции list — в большинстве случаев плохая идея. Вам нужна коллекция, в которой быстро совершается проверка на включение элемента: set, unordered_set/hash_set.

1
  • Очень благодарен вам за подробные комментарии!!!)
    – neitron
    16 дек 2015 в 14:42

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.