AI for OpenTTD - A* Path Finder: Follow-up and unique_ptr slow performance

Question

Original review here: AI for OpenTTD - A* Path Finder

If you'd like to run the code yourself: https://github.com/marlonsmith10/empire_ai (use_smart_pointers branch)

Changes have been made based on the previous review. In particular, using std::priority_queue and std::unordered map have dramatically improved performance. However, using std::unique_ptr compared to raw pointers is slowing the code down by about a factor of 2. Since I'm new to unique_ptr, I would appreciate any comments on whether its being used appropriately, and whether performance can be improved. Something that stands out to me is that when using std::unique_ptr, any node in m_closed_nodes must be moved out, checked, and then moved back in. With a raw pointer, this isn't necessary unless the node is going to be re-opened.

The code also now checks to make sure that roads can be actually built based on the slope of the current tile, so there are no longer any broken connections in roads built along the discovered path.

As in the previous review, any comments on good C++ programming practices are welcome as well.

Update: Some notes on why pointers were used instead of objects in m_closed_nodes and m_open_nodes. Any feedback on the reasons here would be much appreciated.

1. Iterator can use nullptr to determine the Node before the start Node, which can't be done using TileIndex since all values of TileIndex are valid. This was a problem I could not find a good solution to, and was the main motivator for storing pointers.
2. Node member variables can be marked as const, which can't be done if they are stored directly in the containers.
3. cheapest_open_node can return nullptr instead of having to take in and modify a status variable.

I should also add that I'm working with C++11.

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;
}

Answer 1

Use of pointers in containers

In C++, it is often more efficient to store objects directly into a container, instead of just storing pointers to objects in a container. However, if you want to move an object in and out of containers a lot, and they are large, then of course it is better to just store the pointer. In your case, it's a bit of a borderline situation. You move Nodes from m_open_nodes to m_closed_nodes and back, however a Node is actually a relatively small data structure. On a 64-bit machine, it looks like it's 24 bytes, which means it's as big as three pointers. Copying and moving a Node should therefore be quite fast, and having a container of Node objects directly will avoid the need for indirection, and possibly lay out objects in memory in a more efficient way. So I recommend trying to change m_open_nodes and m_closed_nodes to:

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;

Of course, this requires changes in other parts of the code as well. I don't think you need to std::move() anything anymore; Node itself doesn't own any memory so there is no need for move operators.

One drawback is that you no longer have stable pointers to nodes. To get around that, you should use tile indices to refer to nodes; so instead of m_start_node and m_end_node, you just need m_start_tile_index and m_end_tile_index, and instead of previous_node you need previous_tile_index.

Choice of containers

The chosen containers are OK, however some small changes could be made that might improve performance. First, since a Node already contains a tile_index, it is redundant to store a copy of the tile index as the key in a std::unordered_map. What you could do instead is to use a std::set, and give it a custom comparison function so it compares on 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;

The extra overloads are to allow calling find() on the set with just a TileIndex as an argument. This does require C++14 support though, and the is_transparent type has to be defined in order for the second and third overload of operator() to be used.

Another possible optimization is the priority queue. You told it to use a std::vector<> to store the contents, however a std::deque<> might be more efficient, depending on the order in which elements are pushed into the queue.