# 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.

    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),
{
c.reserve(maxSize);
}

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

bool isEmpty() const
{
return c.empty();
}

bool contains(const glm::ivec2& position) const
{
}

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

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

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

push(node);
}

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

pop();
}

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

private:
const size_t m_maxSize;

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());

c.erase(node);
}
};


## Related Questions

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

### Checking if an integer is a palindrome using either a string or a dict

6  Asked on October 27, 2021

### get-release npm module

1  Asked on October 27, 2021 by khushraj-rathod

### Sending a CSV file for a client list from a database

1  Asked on October 27, 2021 by escarta

### A proxy replacement for getters and setters

2  Asked on October 27, 2021

### 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

### I have a input grid with more than 40 input-fields hardcoded

1  Asked on October 27, 2021 by darjusch

### Is there a better way to avoid repeated ‘Len == 1’ when interpreting booleans from strings?

1  Asked on October 27, 2021 by user227432

### Reload configs in memory basis on a trigger efficiently

1  Asked on October 27, 2021 by dragons

### Swift Struct-based Factory Pattern

0  Asked on October 27, 2021

### 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

### Creating a Chart Worksheet from scratch with VBA / OOP Design

1  Asked on October 27, 2021 by jose-cortez