AnswerBun.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!

Related Questions

Website parser for advertisements

1  Asked on October 27, 2021 by viktor-v

     

Knuth Morris Pratt substring search algorithm

0  Asked on October 27, 2021 by gil-fernandes

       

XMLGregorianCalendar to LocalDateTime

1  Asked on October 27, 2021 by mrsmith42

   

Multiplying numpy arrays

2  Asked on October 27, 2021 by galacticponderer

       

Sum of integers in an interval

6  Asked on October 27, 2021 by james-ross

   

First-time F#: A simple Rock Paper Scissors

1  Asked on October 27, 2021 by cimnine

   

C++ : Red-Black Tree with std::unique_ptr

1  Asked on October 27, 2021 by frozenca

   

get-release npm module

1  Asked on October 27, 2021 by khushraj-rathod

         

Checking String with is_numeric in C

2  Asked on October 27, 2021 by ndogac

 

Use case of nesting an enum into a struct

2  Asked on October 27, 2021 by matthias-burger

   

Reload configs in memory basis on a trigger efficiently

1  Asked on October 27, 2021 by dragons

     

Memoizing a tree’s parent pointers in Python

1  Asked on October 27, 2021 by mark-karavan

     

College Billing System – Java

2  Asked on October 27, 2021 by ashwin2125

     

Ask a Question

Get help from others!

© 2022 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP, SolveDir