c++ – AI for OpenTTD – A* Path Finder


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