AI for OpenTTD - A* Path Finder

Question

I'm writing an AI in C++ for OpenTTD, and the first component is a path finder. If you'd like to run it yourself, it's on Github here: https://github.com/marlonsmith10/empire_ai. Currently, it will pick two random towns and build a road between them.

The pathfinder class Path is used by calling find() repeatedly until a path is found. It provides an iterator that can be used to get the index of each tile in the path, once it has been found. The class works correctly to find a 2D list of tiles that are able to have roads built on them. It does not take slope into account, so sometimes roads will not connect after they're built, but I'd prefer to leave that out of the review for now (to be implemented in the future).

My goal is to improve my C++ skills, so any C++ comments or advanced techniques would be appreciated. Comments on the algorithm or general code style are welcome as well.

path.hh

#ifndef PATH_HH
#define PATH_HH


#include "stdafx.h"
#include "command_func.h"
#include <vector>

namespace EmpireAI
{
    class Path
    {
    public:

        Path(TileIndex start, TileIndex end);
        ~Path();

        // Find a partial path from start to end, returning true if the full path has been found
        bool find();

    private:

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

            bool update_costs(Node* adjacent_node);

            const TileIndex tile_index = 0;
            Node* previous_node = NULL;
            bool open = true;
            int32 g = 0;
            const int32 h = 0;
            int32 f = -1;
        };

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

        // Return the corresponding node or create a new one if none is found
        Node* get_node(TileIndex tile_index);

        // Get the open node with the cheapest f cost
        Node* cheapest_open_node();

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

        void open_node(Node* node);
        void close_node(Node* node);

        bool m_path_found = false;

        Node* m_start_node;
        Node* m_current_node;
        TileIndex m_end_tile_index;

        std::vector<Node*> m_open_nodes;
        std::vector<Node*> m_closed_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_current_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 <algorithm>
#include <iostream>

using namespace EmpireAI;


Path::Path(TileIndex start, TileIndex end)
{
    // Save start node
    m_current_node = m_start_node = get_node(start);
    m_current_node->update_costs(m_current_node);

    m_end_tile_index = end;
}


bool Path::find()
{
    if(m_path_found)
    {
        return true;
    }

    // While not at end of path
    for(uint8 node_count = 0; node_count < NODE_COUNT_PER_CALL; node_count++)
    {
        // Find the cheapest open node
        m_current_node = cheapest_open_node();

        // Mark the current node as closed
        close_node(m_current_node);

        // If we've reached the destination, return true
        if(m_current_node->tile_index == m_end_tile_index)
        {
            m_path_found = true;
            break;
        }

        // Calculate the f, h, g, values of the 4 surrounding nodes
        parse_adjacent_tile(m_current_node, 1, 0);
        parse_adjacent_tile(m_current_node, -1, 0);
        parse_adjacent_tile(m_current_node, 0, 1);
        parse_adjacent_tile(m_current_node, 0, -1);
    }

    return m_path_found;
}


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

    // Create a node for this tile only if it is buildable
    if(ScriptTile::IsBuildable(adjacent_tile_index) || ScriptRoad::IsRoadTile(adjacent_tile_index))
    {
        Node* adjacent_node = get_node(adjacent_tile_index);
        if(adjacent_node->update_costs(current_node))
        {
            open_node(adjacent_node);
        }
    }
}


Path::Node* Path::get_node(TileIndex tile_index)
{
    // Return the node if it already exists
    for(Node* node : m_open_nodes)
    {
        if(node->tile_index == tile_index)
        {
            return node;
        }
    }

    // Return the node if it already exists
    for(Node* node : m_closed_nodes)
    {
        if(node->tile_index == tile_index)
        {
            return node;
        }
    }

    Node* node = new Node(tile_index, ScriptMap::DistanceManhattan(tile_index, m_end_tile_index));
    m_open_nodes.push_back(node);

    return node;
}


Path::Node* Path::cheapest_open_node()
{
    // Get the first open node to start
    Node* cheapest_open_node = m_open_nodes.front();

    // Compare the first open node to all other open nodes to find the cheapest
    for(Node* node : m_open_nodes)
    {
        if(node->f < cheapest_open_node->f)
        {
            cheapest_open_node = node;
        }

        // Break ties by choosing closest to destination
        if(node->f == cheapest_open_node->f && node->h < cheapest_open_node->h)
        {
            cheapest_open_node = node;
        }
    }

    return cheapest_open_node;
}


void Path::open_node(Node* node)
{
    // Find the node in the list of closed nodes
    auto it = std::find(m_closed_nodes.begin(), m_closed_nodes.end(), node);

    if(it != m_closed_nodes.end())
    {
        node->open = true;
        m_open_nodes.push_back(node);
        m_closed_nodes.erase(it);
    }
}


void Path::close_node(Node* node)
{
    // Find the node in the list of open nodes
    auto it = std::find(m_open_nodes.begin(), m_open_nodes.end(), node);

    if(it != m_open_nodes.end())
    {
        node->open = false;
        m_closed_nodes.push_back(node);
        m_open_nodes.erase(it);
    }
}


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

    int32 new_f = new_g + h;

    if(new_f < f || f == -1)
    {
        g = new_g;
        f = new_f;
        previous_node = adjacent_node;
        return true;
    }

    return false;
}


Path::~Path()
{
    for(Node* node : m_open_nodes)
    {
        delete node;
    }

    for(Node* node : m_closed_nodes)
    {
        delete node;
    }
}

Answer 1

Node-count limit:

for(uint8 node_count = 0; node_count < NODE_COUNT_PER_CALL; node_count++)

A uint8 may be too small (especially if we want to find a complete path in one call).

It would be nice to specify a maximum number of nodes to search when calling the function (maybe a function argument that defaults to NODE_COUNT_PER_CALL).

A time-based limit might be more useful in some situations (e.g. providing a consistent framerate on a variety of hardware).

---

Don't call new directly:

We should use a std::unique_ptr instead of doing manual memory management of Nodes.

(However, see below...)

---

Handle edge cases:

TileIndex adjacent_tile_index = current_node->tile_index + ScriptMap::GetTileIndex(x, y);

Presumably there are map edges, so at some point the -1 and +1 added to the x and y are not valid. Does this (and the rest of the algorithm) work correctly in those cases?

---

Wrong data structures!

This A* implementation stores Nodes in a flat vector, which means we have to do linear searches to check the search frontier and visited nodes, and to find the cheapest node (see get_node(), cheapest_open_node() etc.). This is going to be horribly slow for larger maps.

We should use a std::unordered_map for the visited nodes (with the tile_index as the key), and a std::priority_queue to store the search frontier, so that we can quickly access the cheapest node.

(It's usually easier to store "open" and "closed" nodes in a single map.)

(Note that with these changes it will probably faster to store the previous tile_index, instead of doing extra memory allocation and storing a pointer).

---

Inaccessible nodes?

What happens when the destination is inaccessible? It looks like we'll call Node* cheapest_open_node = m_open_nodes.front(); on an empty m_open_nodes and cause undefined behaviour (e.g. a crash).

Note that we really have three return states: "still searching", "search complete - path found", "search complete - path not found". Perhaps we need to return an enum from find() instead of a bool.

Do we need to worry about the start node being inaccessible?

What do we really need in terms of accessibility? Is it correct to find a path up to a destination that isn't buildable or a road, even if we can't move onto the final tile?