Исходный обзор здесь: AI для OpenTTD — A * Path Finder

Если вы хотите запустить код самостоятельно: https://github.com/marlonsmith10/empire_ai (ветка use_smart_pointers)

Изменения внесены на основании предыдущего обзора. В частности, использование std :: priority_queue и std :: unordered map значительно повысило производительность. Однако использование std :: unique_ptr по сравнению с необработанными указателями замедляет код примерно в 2 раза. Поскольку я новичок в unique_ptr, я был бы признателен за любые комментарии о том, правильно ли он используется и можно ли улучшить производительность. Что меня выделяет, так это то, что при использовании std :: unique_ptr любой узел в m_closed_nodes должен быть перемещен, проверен и затем возвращен обратно. С необработанным указателем в этом нет необходимости, если только узел не будет повторно -открыт.

Код также теперь проверяет, можно ли построить дороги на основе наклона текущего тайла, чтобы больше не было разорванных соединений на дорогах, построенных вдоль обнаруженного пути.

Как и в предыдущем обзоре, приветствуются любые комментарии о хороших практиках программирования на C ++.

path.hh

#ifndef PATH_HH
#define PATH_HH


#include "stdafx.h"
#include "command_func.h"
#include <queue>
#include <unordered_map>

namespace EmpireAI
{
    class Path
    {
    public:

        enum Status
        {
            IN_PROGRESS,
            FOUND,
            UNREACHABLE
        };

        Path(const TileIndex start, const TileIndex end);

        // Find a partial path from start to end, returning true if the full path has been found
        Status find(const uint16_t max_node_count = DEFAULT_NODE_COUNT_PER_FIND);

    private:

        struct Node
        {
            Node(TileIndex in_tile_index, int32 in_h)
            : tile_index(in_tile_index), h(in_h)
            {
            }

            Node()
            : tile_index(0), h(0)
            {}

            // Update the Node's g and h values, as well as its previous node. Returns true if the
            // new values are lower than the previous ones.
            bool update_costs(Node* const adjacent_node);

            const TileIndex tile_index;
            Node* previous_node = nullptr;
            int32 g = 0;
            const int32 h;
            int32 f = -1;
        };

        struct NodeCostCompare
        {
            bool operator()(const std::unique_ptr<Node>& node1, const std::unique_ptr<Node>& node2)
            {
                return node1->f > node2->f;
            }
        };


        void parse_adjacent_tile(Node* const current_node, const int8 x, const int8 y);

        // Return the corresponding node or create a new one if none is found
        std::unique_ptr<Node> get_node(const TileIndex tile_index);

        // Get the cheapest open node, returns nullptr if there are no open nodes
        std::unique_ptr<Node> cheapest_open_node();

        // Returns true if a road can be built from one node to the next
        bool nodes_can_connect_road(const Node* const node_from, const Node* const node_to) const;

        // Check this many nodes per call of find()
        static const uint16 DEFAULT_NODE_COUNT_PER_FIND = 20;

        void open_node(std::unique_ptr<Node> node);
        void close_node(std::unique_ptr<Node> node);

        Status m_status;

        Node* m_start_node;
        Node* m_end_node;
        const TileIndex m_end_tile_index;

        // Containers for open and closed nodes
        std::unordered_map<TileIndex, std::unique_ptr<Node>> m_closed_nodes;
        std::priority_queue<Node*, std::vector<std::unique_ptr<Node>>, NodeCostCompare> m_open_nodes;

    public:

        class Iterator
        {
        public:

            Iterator(const Path::Node* node)
            : m_iterator_node(node)
            {}

            bool operator==(const Iterator& iterator) const
            {
                return m_iterator_node == iterator.m_iterator_node;
            }

            const Iterator& operator=(const Path::Node* node)
            {
                m_iterator_node = node;
                return *this;
            }

            bool operator!=(const Iterator& iterator) const
            {
                return m_iterator_node != iterator.m_iterator_node;
            }

            const Iterator& operator++()
            {
                m_iterator_node = m_iterator_node->previous_node;
                return *this;
            }

            Iterator operator++(int)
            {
                Iterator iterator = *this;
                m_iterator_node = m_iterator_node->previous_node;
                return iterator;
            }

            TileIndex operator*() const
            {
                if(m_iterator_node == nullptr)
                {
                    return 0;
                }

                return m_iterator_node->tile_index;
            }

        private:
            const Path::Node* m_iterator_node;
        };

        Iterator begin()
        {
            return Iterator(m_end_node);
        }

        Iterator end()
        {
            return Iterator(m_start_node);
        }
    };
}


#endif // PATH_HH

path.cc

#include "path.hh"

#include "script_map.hpp"
#include "script_road.hpp"
#include "script_tile.hpp"
#include "map_func.h"

#include <algorithm>

using namespace EmpireAI;


Path::Path(const TileIndex start, const TileIndex end)
: m_end_tile_index(end)
{
    // Create an open node at the start
    std::unique_ptr<Node> start_node = get_node(start);
    start_node->f = start_node->h;

    // Keep a pointer to the start node, for use by the iterator once a path has been found
    m_start_node = start_node.get();

    open_node(std::move(start_node));

    m_status = IN_PROGRESS;
}


Path::Status Path::find(const uint16_t max_node_count)
{
    if(m_status != IN_PROGRESS)
    {
        return m_status;
    }

    // While not at end of path
    for(uint16 node_count = 0; node_count < max_node_count; node_count++)
    {
        // Get the cheapest open node
        std::unique_ptr<Node> current_node = cheapest_open_node();

        // If there are no open nodes, the path is unreachable
        if(current_node == nullptr)
        {
            m_status = UNREACHABLE;
            break;
        }

        // If we've reached the destination, return true
        if(current_node->tile_index == m_end_tile_index)
        {
            // Keep a pointer to the end node, for use by the iterator
            m_end_node = current_node.get();
            close_node(std::move(current_node));
            m_status = FOUND;
            break;
        }

        // Calculate the f, h, g, values of the 4 surrounding nodes
        parse_adjacent_tile(current_node.get(), 1, 0);
        parse_adjacent_tile(current_node.get(), -1, 0);
        parse_adjacent_tile(current_node.get(), 0, 1);
        parse_adjacent_tile(current_node.get(), 0, -1);

        // Mark the current node as closed
        close_node(std::move(current_node));
    }

    return m_status;
}


void Path::parse_adjacent_tile(Node* const current_node, const int8 x, const int8 y)
{
    TileIndex adjacent_tile_index = current_node->tile_index + ScriptMap::GetTileIndex(x, y);

    std::unique_ptr<Node> adjacent_node = get_node(adjacent_tile_index);

    // Check to see if this tile can be used as part of the path
    if(nodes_can_connect_road(current_node, adjacent_node.get()))
    {
        if(adjacent_node->update_costs(current_node))
        {
            open_node(std::move(adjacent_node));
        }
        else
        {
            close_node(std::move(adjacent_node));
        }
    }
    else
    {
        close_node(std::move(adjacent_node));
    }
}


bool Path::nodes_can_connect_road(const Node* const node_from, const Node* const node_to) const
{
    // The start node doesn't connect to a previous node, so we can't check it for the correct slope.
    // The pathfinder can only ensure that the next node in the path can connect to the start node.
    if(node_from->previous_node == nullptr)
    {
        return true;
    }

    int32 supports_road = ScriptRoad::CanBuildConnectedRoadPartsHere(node_from->tile_index, node_from->previous_node->tile_index, node_to->tile_index);

    if(supports_road <= 0)
    {
        return false;
    }

    if(!ScriptTile::IsBuildable(node_to->tile_index) && !ScriptRoad::IsRoadTile(node_to->tile_index))
    {
        return false;
    }

    return true;
}


std::unique_ptr<Path::Node> Path::cheapest_open_node()
{
    // While there are open nodes available
    while(!m_open_nodes.empty())
    {
        // Remove the cheapest node from the open nodes list
        std::unique_ptr<Node> current_node = std::move(const_cast<std::unique_ptr<Node>&>(m_open_nodes.top()));
        m_open_nodes.pop();

        // If this node has already been closed, discard it and skip to the next one. Duplicates are expected
        // here because get_node() doesn't check for duplicates for performance reasons.
        if(m_closed_nodes.find(current_node->tile_index) != m_closed_nodes.end())
        {
            continue;
        }

        return current_node;
    }

    // There are no more open nodes
    return nullptr;
}


std::unique_ptr<Path::Node> Path::get_node(const TileIndex tile_index)
{
    // If the node is not closed, create a new one.
    // Duplicate open nodes are considered an acceptable tradeoff since it's not easy to search std::priority_queue for
    // an already existing open node
    if(m_closed_nodes.find(tile_index) == m_closed_nodes.end())
    {
        return std::unique_ptr<Node>(new Node(tile_index, ScriptMap::DistanceManhattan(tile_index, m_end_tile_index)));
    }

    std::unique_ptr<Node> node = std::move(m_closed_nodes.at(tile_index));

    // Remove the (now null) node from the closed list
    m_closed_nodes.erase(tile_index);

    return node;
}


void Path::open_node(std::unique_ptr<Node> node)
{
    // Push the node into the open node list. Does not check open nodes, instead allowing
    // duplicates to be created in the open node priority queue, since checking for already open nodes is slower
    // than just processing a node twice.
    m_open_nodes.push(std::move(node));
}


void Path::close_node(std::unique_ptr<Node> node)
{
    m_closed_nodes[node->tile_index] = std::move(node);
}


bool Path::Node::update_costs(Node* const adjacent_node)
{
    int32 new_g = adjacent_node->g + 1;

    int32 new_f = new_g + h;

    // If this node is closed but cheaper than it was via previous path, or
    // if this is a new node (f == -1), return true to indicate the node should be opened again
    if(new_f < f || f == -1)
    {
        g = new_g;
        f = new_f;
        previous_node = adjacent_node;

        return true;
    }

    return false;
}

Использование указателей в контейнерах

В C ++ часто более эффективно хранить объекты непосредственно в контейнере, а не просто хранить указатели на объекты в контейнере. Однако, если вы хотите много перемещать объект в контейнеры и из них, и они большие, то, конечно, лучше просто сохранить указатель. В вашем случае это немного пограничная ситуация. Вы двигаетесь Nodeс от m_open_nodes к m_closed_nodes и обратно, однако Node на самом деле представляет собой относительно небольшую структуру данных. На 64-битной машине это выглядит как 24 байта, что означает, что он равен трём указателям. Копирование и перемещение Node поэтому должен быть довольно быстрым и иметь контейнер Node объекты напрямую избавят от необходимости косвенного обращения и, возможно, будут размещать объекты в памяти более эффективным способом. Поэтому я рекомендую попробовать изменить m_open_nodes и m_closed_nodes к:

struct NodeCostCompare {
    bool operator()(const Node& node1, const Node& node2) {
        return node1.f > node2.f;
    }
};

std::unordered_map<TileIndex, Node> m_closed_nodes;
std::priority_queue<Node, std::vector<Node>, NodeCostCompare> m_open_nodes;

Конечно, это требует изменений и в других частях кода. Я не думаю, что тебе нужно std::move() больше ничего; Node сам по себе не владеет какой-либо памятью, поэтому нет необходимости в операторах перемещения.

Одним из недостатков является то, что у вас больше нет стабильных указателей на узлы. Чтобы обойти это, вы должны использовать индексы тайлов для ссылки на узлы; так что вместо m_start_node и m_end_nodeтебе просто нужно m_start_tile_index и m_end_tile_index, а вместо previous_node тебе нужно previous_tile_index.

Выбор тары

Выбранные контейнеры в порядке, однако можно внести небольшие изменения, которые могут улучшить производительность. Во-первых, поскольку Node уже содержит tile_index, избыточно хранить копию индекса тайла в качестве ключа в std::unordered_map. Вместо этого вы могли бы использовать std::set, и дайте ему настраиваемую функцию сравнения, чтобы он сравнивал tile_index:

struct NodeTileCompare {
    using is_transparent = void;
    bool operator()(const Node &node1, const Node &node2) {
        return node1.tile_index < node2.tile_index;
    }
    bool operator()(const Node &node, TileIndex tile_index) {
        return node.tile_index < tile_index;
    }
    bool operator()(TileIndex tile_index, const Node &node) {
        reutrn tile_index < node.tile_index;
    }
};

std::set<Node, NodeTileCompare> m_closed_nodes;

Дополнительные перегрузки позволяют вызывать find() на съемочной площадке всего лишь TileIndex в качестве аргумента. Однако для этого требуется поддержка C ++ 14, и is_transparent тип должен быть определен для второй и третьей перегрузки operator() использоваться.

Еще одна возможная оптимизация — это приоритетная очередь. Вы сказали ему использовать std::vector<> для хранения содержимого, однако std::deque<> может быть более эффективным, в зависимости от порядка, в котором элементы помещаются в очередь.