TransWikia.com

A* using a Priority Queue

Code Review Asked by Ryan Swann on October 17, 2020

I’ve implemented an A* with a priority queue. I am not getting any performance issues in this little game that I am making but it would be interesting to know how to improve this.

I am doing a few o(n) searches in getNode & isSuccessorValid. I thought about using an unordered map and pointing to each node location but when erasing from the vector, that pointer might not be valid anymore.

Thank you in advance.

    struct PriorityQueueNode
{
    PriorityQueueNode(const glm::ivec2& position, const glm::ivec2& parentPosition, float g, float h);

    float getF() const;

    glm::ivec2 position;
    glm::ivec2 parentPosition;
    float g;
    float h;
};

const auto nodeCompare = [](const auto& a, const auto& b) -> bool { return b.getF() < a.getF(); };
class PriorityQueue : private std::priority_queue<PriorityQueueNode, std::vector<PriorityQueueNode>, decltype(nodeCompare)>
{
public:
    PriorityQueue(size_t maxSize)
        : priority_queue(nodeCompare),
        m_maxSize(maxSize),
        m_addedNodePositions()
    {
        c.reserve(maxSize);
    }

    size_t getSize() const
    {
        assert(c.size() == m_addedNodePositions.size());
        return c.size();
    }

    bool isEmpty() const
    {
        assert(c.empty() && m_addedNodePositions.empty() || !c.empty() && !m_addedNodePositions.empty());
        return c.empty();
    }

    bool contains(const glm::ivec2& position) const
    {
        return m_addedNodePositions.find(position) != m_addedNodePositions.cend();
    }

    const PriorityQueueNode& getTop() const
    {
        assert(!isEmpty());
        return top();
    }

    const PriorityQueueNode& getNode(const glm::ivec2& position) const
    {
        auto node = std::find_if(c.cbegin(), c.cend(), [&position](const auto& node) -> bool
        {
            return node.position == position;
        });

        assert(node != c.end());
        return (*node);
    }

    bool isSuccessorNodeValid(const PriorityQueueNode& successorNode) const
    {
        auto matchingNode = std::find_if(c.cbegin(), c.cend(), [&successorNode](const auto& node) -> bool
        {
            return successorNode.position == node.position;
        });

        return matchingNode != c.cend() && successorNode.getF() < matchingNode->getF();
    }

    void changeNode(const PriorityQueueNode& newNode)
    {
        assert(isSuccessorNodeValid(newNode) && contains(newNode.position));

        eraseNode(newNode.position);
        add(newNode);
    }

    void add(const PriorityQueueNode& node)
    {
        assert(!contains(node.position) && c.size() + 1 <= m_maxSize);

        push(node);
        m_addedNodePositions.insert(node.position);
    }

    void popTop()
    {
        assert(!isEmpty());

        auto iter = m_addedNodePositions.find(top().position);
        assert(iter != m_addedNodePositions.end());
        m_addedNodePositions.erase(iter);

        pop();
    }

    void clear()
    {
        c.clear();
        m_addedNodePositions.clear();
    }

private:
    const size_t m_maxSize;
    std::unordered_set<glm::ivec2> m_addedNodePositions;

    void eraseNode(const glm::ivec2& position)
    {
        auto node = std::find_if(c.begin(), c.end(), [&position](const auto& node)
        {
            return node.position == position;
        });
        assert(node != c.cend());

        m_addedNodePositions.erase(position);
        c.erase(node);
    }
};

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP