5
\$\begingroup\$

I wrote a little A* implementation by my own and would like to have some feedback ;) The code is in OOP way, thus we can use an other pathfinding algorithm easily. The "Base" is just the interface class, thus is should not matter here.

Before we look at the code, let me say one or two senteces about it behaviour and motivations.

I like to write reusable code. Thus I looked for a possibility to abstract the behaviour of the algorithm from its underlying data model. Because of this I decided to implement a connection object for these two tasks. This is the "AreaVisitor". If you want to use this header, you have to subclass the "AreaVisitor" class and adapt it to your own data model. It doesn´t matter if you have a tiled 2d array or just some abstract nodes. You decide the important informations, the algorithm just use this in its usual way. I know this is not as special as it sounds, but I think its useful to explain it first ;)

#pragma once

#include <memory>
#include <assert.h>
#include "Base.hpp"

namespace sfw {
namespace pathfinder {

    template <class Identifier>
    class AStar : public Base<Identifier>
    {
    public:
        template <class Identifier>
        class Node_ : sl::NonCopyable
        {
        private:
            const Node_* m_Parent = nullptr;

            Identifier m_ID;
            int m_Heuristic = 0;
            int m_Cost = 0;

        public:
            Node_(const Identifier& _id, int _cost, int _heuristic, const Node_* _parent) :
                m_ID(_id),
                m_Cost(std::move(_cost)),
                m_Heuristic(std::move(_heuristic)),
                m_Parent(_parent)
            {
                assert(m_Cost >= 0 && m_Heuristic >= 0);
            }

            Node_(Node_&& _node)
            {
                *this = std::move(_node);
            }

            Node_& operator =(Node_&& _node)
            {
                if (this != &_node)
                {
                    m_ID = std::move(_node.m_ID);
                    m_Cost = std::move(_node.m_Cost);
                    m_Heuristic = std::move(_node.m_Heuristic);
                    m_Parent = std::move(_node.m_Parent);
                }
                return *this;
            }

            const Identifier& getIdentifier() const
            {
                return m_ID;
            }

            int getCost() const
            {
                if (m_Parent)
                    return m_Parent->getCost() + m_Cost;
                return m_Cost;
            }

            int getHeuristic() const
            {
                return m_Heuristic;
            }

            int getFinalCost() const
            {
                return getCost() + getHeuristic();
            }

            const Node_* getParent() const
            {
                return m_Parent;
            }
        };
        using Node = Node_<Identifier>;
        using NodePtr = std::unique_ptr<Node>;

        template <class Identifier>
        class AreaVisitor_ : sl::NonCopyable
        {
        public:
            using Node = Node;
            using NodePtr = NodePtr;

            virtual ~AreaVisitor_() = default;

            virtual std::vector<NodePtr> getNeighborNodes(const Node& _pos) = 0;

            virtual int calculateHeuristic(const Identifier& _id) const = 0;
            virtual void setFinalChecked(const Node& _node) = 0;
            virtual void setInOpenList(const Node& _node) = 0;
            virtual bool isInOpenList(const Node& _node) = 0;
            virtual void removeFromOpenList(const Node& _node) = 0;
            virtual void setup(const Identifier& _destinationID) = 0;
        };
        using AreaVisitor = AreaVisitor_<Identifier>;
        using AreaVisitorPtr = std::unique_ptr<AreaVisitor>;

    private:
        AreaVisitorPtr m_AreaVisitor;

    public:
        AStar(AreaVisitorPtr&& _visitor) :
            m_AreaVisitor(std::move(_visitor))
        {
            assert(m_AreaVisitor);
        }

        Path calculatePath(const Identifier& _startID, const Identifier& _destinationID) const override
        {
            assert(m_AreaVisitor);
            m_AreaVisitor->setup(_destinationID);

            std::vector<NodePtr> openList, closedList;
            openList.emplace_back(std::make_unique<Node>(_startID, 0, m_AreaVisitor->calculateHeuristic(_startID), nullptr));
            while (!openList.empty())
            {
                auto node = std::move(openList.back());
                assert(node);
                openList.pop_back();
                m_AreaVisitor->removeFromOpenList(*node);

                // check if node is destination
                if (node->getIdentifier() == _destinationID)
                {
                    Path result;
                    for (const Node* curNode = node.get(); curNode != nullptr; curNode = curNode->getParent())
                        result.push_back(curNode->getIdentifier());
                    std::reverse(std::begin(result), std::end(result));
                    return std::move(result);
                }

                // fill open nodes with new neighbors
                for (auto& newNode : m_AreaVisitor->getNeighborNodes(*node))
                {
                    // try to override older node
                    if (m_AreaVisitor->isInOpenList(*newNode))
                    {
                        auto itr = std::find_if(std::begin(openList), std::end(openList), [&newNode](const NodePtr& _node){
                            return newNode->getIdentifier() == _node->getIdentifier();
                        });
                        if ((*itr)->getFinalCost() > newNode->getFinalCost())
                            *(*itr) = std::move(*newNode);
                    }
                    // insert new node
                    else
                    {
                        m_AreaVisitor->setInOpenList(*newNode);
                        openList.insert(std::lower_bound(std::rbegin(openList), std::rend(openList), newNode->getFinalCost(),
                            [](const NodePtr& _node, int _value){
                            return _node->getFinalCost() < _value;
                        }).base(), std::move(newNode));
                    }
                }

                // current node to closed list
                m_AreaVisitor->setFinalChecked(*node);
                closedList.push_back(std::move(node));
            }
            // return empty path
            return Path();
        }
    };
} // namespace pathfinder
} // namespace sfw

I would be really thankfull for any constructive feedback ;) I am also thankful about a better name than "AreaVisitor" for the AStar internal object.

\$\endgroup\$
  • \$\begingroup\$ I know A* is supposed to be a more efficient version of Dijkstra's algorithm but that's about all I know. Do you have a link to a description of the algorithm? \$\endgroup\$ – Martin York Feb 1 '16 at 22:26
  • \$\begingroup\$ The A* searchs in a more efficient way. While the Dijkstra searchs the area in a radial way, the A* uses a estimated cost to the end node which reduces the affected nodes significant. I think this one is a good tutorial to get a basic understanding how it works: raywenderlich.com/4946/introduction-to-a-pathfinding \$\endgroup\$ – DNKpp Feb 2 '16 at 8:12
  • \$\begingroup\$ More accurately. A* uses a heuristic that attempts to reduce the search area. Like all heuristics it attempts to optimize for a good solution trading an optimal solution for getting a result in a reasonable time. Do you need the optimal solution or just a probably good solution? \$\endgroup\$ – Martin York Feb 2 '16 at 8:59
  • 1
    \$\begingroup\$ Seems like you don't understand the meaning of heuristic. Unless you scan the whole graph you can't know its the optimal solution. If you scan the whole graph you have not optimized Dijkstra its just as complex in terms of time. Now the 2D tile grid is a very simplistic graph and thus it is much more likely to find the optimal solution, but guaranteed I am not sure I believe that. \$\endgroup\$ – Martin York Feb 2 '16 at 23:08
  • 1
    \$\begingroup\$ A*_search_algorithmFor the algorithm to find the actual shortest path, the heuristic function must be **admissible**, meaning that it never overestimates the actual cost to get to the nearest goal node. The heuristic function is problem-specific and must be provided by the user of the algorithm. \$\endgroup\$ – Martin York Feb 2 '16 at 23:25
1
\$\begingroup\$

This is not portable

#pragma once

Prefer include guards. Its not that hard to make them unique. Make sure they include the full namespace and file name

#ifndef SFW_PATHFINDER_ASTAR_H
#define SFW_PATHFINDER_ASTAR_H
// STUFF
#endif

Because you use template on the outside. You don't need to repeat it on the inside

    template <class Identifier>
    class AStar : public Base<Identifier>
    {
        ....
        template <class Identifier>
        class Node_ : sl::NonCopyable
        {...}
        using Node = Node_<Identifier>;
        using NodePtr = std::unique_ptr<Node>;

        template <class Identifier>
        class AreaVisitor_ : sl::NonCopyable
        {...};
        using AreaVisitor = AreaVisitor_<Identifier>;
        using AreaVisitorPtr = std::unique_ptr<AreaVisitor>;

Your internal nodes don't need to be templtized because they are part of an already templatized class. You can simplify the above with

    template <class Identifier>
    class AStar : public Base<Identifier>
    {
        ....
        class Node : sl::NonCopyable
        {...}
        using NodePtr = std::unique_ptr<Node>;

        class AreaVisitor : sl::NonCopyable
        {...};
        using AreaVisitorPtr = std::unique_ptr<AreaVisitor>;

Your use of underscore is perfectly correct. Unfortunately not all coders are aware of all the rules around underscore. So I prefer to avoid them, especially at the beginning of identifiers.

Your nodes use move semantics only. Which is fine. But your move constructor and assignment should be marked as noexcept. In your specific case it will make no difference but it is a good habit to get into (especially if these methods are actually noexcept).

            Node_(Node_&& _node) noexcept;
            Node_& operator =(Node_&& _node) noexcept;

This makes a difference when you have copy semantics and you are using standard containers. There are situations where the standard will rather use the copy than the move to preserve the strong exception guarantee.

I know you are trying to optimize the use of the assignment here.

            Node_& operator =(Node_&& _node)
            {
                if (this != &_node)
                {
                    m_ID = std::move(_node.m_ID);
                    m_Cost = std::move(_node.m_Cost);
                    m_Heuristic = std::move(_node.m_Heuristic);
                    m_Parent = std::move(_node.m_Parent);
                }
                return *this;
            }

But the case you are trying to optimize is rare (at best) and this causes the normal case to be worsened (failed branch predication can be very costly). As result I tend to not bother and just use the standard swap technique

            Node_& operator =(Node_&& _node) noexcept
            {
                _node.swap(*this);
                return *this;
            }

Since you should have a swap method anyway. This also makes writing the move constructor more intuitive as you can also just use the swap method.

Also note your move constructor has undefined behavior.

            Node_(Node_&& _node)
            {
                *this = std::move(_node);
            }

I know it looks simple. But if this node is default initialized some of its members are in an indeterminate state (as you have no initializer list and some values are POD). When you perform the std::move on these members it needs to read them to move their value. If you read a variable that has indeterminate state this is undefined behavior.

If you really on zero initialization in your code to make sure the members are initialized. Then your code becomes brittle. As a change in the use case in a different part of the code may result in the use of default initialization and you are back to undefined behavior. So make sure you initialize all members in a constructor.

I would use the dead simple:

            Node_(Node_&& _node) noexcept
                : m_ID()          // IT does assume these values can
                , m_Cost()        // be default initialized but if
                , m_Heuristic()   // I though about it more I am sure 
                , m_Parent()      // we could make it work in all sits.
            {
                _node.swap(*this)
            }

Then you add a swap method.

            Node_::swap(Node_& other) noexcept
            {
                using std::swap;
                std::swap(m_ID,        _node.m_ID);
                std::swap(m_Cost,      _node.m_Cost);
                std::swap(m_Heuristic, _node.m_Heuristic);
                std::swap(m_Parent,    _node.m_Parent);
            }

Using std::forward Vs std::move

I have not had time to understand the algorithm yet so I have no comments on that. But I may come back and have a look if I have time.

\$\endgroup\$
  • \$\begingroup\$ First, sry for the long time to answer. \$\endgroup\$ – DNKpp Feb 8 '16 at 11:44
  • \$\begingroup\$ You are right, #pragma once is not portable, but it works for my compiler. I use this in all of my code, thus this doesn´t matter here. You are right, I can avoid the template in the template class. That´s just stupid :D I have to look at the "noexecpt" keyword, never used it anywhere. Thanks for the remark. I am not sure, but I think I can not use the std::swap in my move operator. The node class is not compiable, which in fact means, the copy operator/constructor is = delete. swap use copy construction, thus I can not use it. \$\endgroup\$ – DNKpp Feb 8 '16 at 11:51
  • \$\begingroup\$ The UB in move constructor: I think its not UB, but I might be wrong. I initialize all members in class definition, this should be enough to avoid UB? I don´t know the exact differences of std::forward vs std::move, but I do not think that move is wrong here. \$\endgroup\$ – DNKpp Feb 8 '16 at 11:55
  • \$\begingroup\$ std::swap uses move semantics. The method I describe above is the standard way of implementing move semantics. Doing it your way is brittle and susceptible to maintenance problems. \$\endgroup\$ – Martin York Feb 8 '16 at 17:25
  • \$\begingroup\$ Yep: Removed the part of std::forward. \$\endgroup\$ – Martin York Feb 8 '16 at 17:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.