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
    Commented 14 дек. 2015 в 23:21
  • 2
    Вообще утечкам тут взяться неоткуда, т.к. вы нигде явно не выделяете память. Сама имплементация далеко не оптимальна, т.к. в качестве хранилища закрытых и открытых узлов используются списки, в которых на каждой итерации проводится линейный поиск.
    – dzhioev
    Commented 14 дек. 2015 в 23:31
  • codereview.stackexchange.com
    – theoden8
    Commented 15 дек. 2015 в 0:59
  • 2
    @theoden На нашем сайте подобные вопросы допустимы: meta.ru.stackoverflow.com/q/1761 Впрочем, конкретно в этом вопросе многовато кода, что говорит не в его пользу, конечно.
    – Kyubey
    Commented 15 дек. 2015 в 10:34
  • @Discord, спасибо за замечание, учту)
    – neitron
    Commented 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
    Commented 16 дек. 2015 в 14:42

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

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