A* algorithm in C++

I wanted to know if my A* algorithm is well-implemented and if it could be optimized in any way.

```
#include
#include
#include
#include
#include

class Vector2
{
int x, y;
public:
Vector2(int _x, int _y) : x(_x), y(_y) {}
Vector2() = default;
Vector2 operator +(const Vector2& other) {
Vector2 temp;
temp.x = this->x + other.x;
temp.y = this->y + other.y;
return temp;
}
int getX() const { return x; }
int getY() const { return y; }

friend class Map;
};

struct Node
{
Vector2 position;
int G, H, F;
Node* parent = nullptr;

Node() = default;
Node(const Node& other) = default;
Node(Vector2 pos):position(pos) {};

void calc(const Vector2& endPos) {
H = static_cast((abs(static_cast(position.getX() - endPos.getX())) + abs(static_cast(position.getY() - endPos.getY()))));
G = parent ? parent->G + 1 : 1;
F = G + H;
}

bool operator==(const Node& other) const {
return (position.getX() == other.position.getX() && position.getY() == other.position.getY());
}
bool operator!=(const Node& other) const {
return !(*this == other);
}
bool operator data;
int size;
public:
Map() = default;
Map(int _size) : size(_size) {
data.resize(size * size);
for (int i = 0; i = 20) position.y = size - 1;
if (position.x >= 20) position.x = size - 1;
return(data[position.getX() + (position.getY() * size)] == 'X');
}
void setElement(char&& asda, Vector2 position) {
data[position.getX() + (position.getY() * size)] = asda;
}
};

class Solver
{
Vector2 startPos, endPos;
std::vector directions;
Map map;
public:
Solver(Vector2 _startPos, Vector2 _endPos, int size) : startPos(_startPos), endPos(_endPos){
Map temp(size);
map = temp;

map.setElement('X', Vector2(14, 15));
map.setElement('X',Vector2(15,15));
map.setElement('X', Vecto

Avoid numbered names

class Vector2

What about this makes it a Vector2? It seems like it holds position data. Why not just call it Position? Alternately consider Vector2D, CartesianVector, or defining your own namespace, e.g. nonstandard::Vector to differentiate it (please find a better name than nonstandard though). Names should be descriptive if possible. The 2 doesn't tell me why you aren't just using a std::vector there.

Don't repeat yourself

data.resize(size * size);
        for (int i = 0; i < size * size; ++i) data[i] = '.';

You calculate size * size on every iteration of the for loop and once previous. Why not just calculate it once? Even if the original would get optimized out by the compiler, this makes it clearer that the resize and the for loop are operating on the same value.

std::size_t area = size * size;
        data.resize(area);
        for (std::size_t i = 0; i < area; ++i) {
            data[i] = '.';
        }

I also changed to size_t as being a better type for indexing an array. Note that this would make no functional difference in this case. It is a good habit though.

I changed from the statement form of the for loop to the block form. This can also be a good habit, both for readability and to avoid a bug where someone tries to put two statements into a for loop without the block notation.

for (int i = 1; i <= size * size; ++i) {

Similar problem with a similar solution.

for (std::size_t i = 1, area = size * size; i <= area; ++i) {

Another alternative is

std::size_t i = 0;
        std::size_t area = size * size;
        while (i < area) {
            std::cout << data[i];
            ++i;
            std::cout << ((0 == i % size) ? "\n" : " ");
        }

This saves an unnecessary subtraction but may be less readable.

Note that it also saves adding an unnecessary space at the end of each line. I find that neater, but it's not a big deal either way.

A third version would be

for (std::size_t i = 0, area = size * size; i < area; ++i) {
            for (std::size_t endOfRow = i + size - 1; i < endOfRow; ++i) {
                 std::cout << data[i] << " ";
            }

            std::cout << data[i] << "\n";
        }

This saves calculating the modulus on each iteration. Instead it calculates a sum of three values every size iterations. I'll leave it up to you whether this is more or less readable than the previous versions. It should be more efficient but not necessarily enough to matter.

Avoid magic values

if (position.y = 20) position.y = size - 1;
        if (position.x >= 20) position.x = size - 1;
        return(data[position.getX() + (position.getY() * size)] == 'X');

Why 20? Looking through the code, it's because you set size to 20. So why not say that?

if (position.y = size) {
            position.y = size - 1;
        }
        if (position.x >= size) {
            position.x = size - 1;
        }

        return data[getIndexFrom(position)] == 'X';

And now we need a getIndexFrom

std::size_t getIndexFrom(Position p) const {
        return p.getX() + p.getY() * size;
    }

This not only reads easier to me, it avoids accidentally doing the conversion differently somewhere.

Consider a Priority Queue

std::list openList;

Rather than store this in a std::list and use the \$O(n)\$ std::min every iteration, consider a std::priority_queue.

std::priority_queue unexploredNodes;

Note that you may need to put the indexes in the queue rather than the Node values themselves to get a performance improvement.

std::priority_queue, CompareNodes> unexploredNodes;

You'd have to benchmark all three versions to see which gives the best performance.

You also may want to consider writing your own priority queue implementation.

I also changed the name from openList to unexploredNodes as being more descriptive.

Save visited nodes in an array rather than a list

You store each visited node in closedList and use std::find to check if it's there. Instead, consider using a boolean array:

bool *explored = new bool[size * size];
        for (auto& e : explored) {
            e = false;
        }
        explored[map.getIndexFrom(current.position)] = true;
            || explored[map.getIndexFrom(successor.position)]) {
        delete(explored);

This turns an \$O(n)\$ std::find into a constant time array access.

Bug

if (!openList.size()) {
            std::cout << "No path has been found\n";
            return false;
        }

I'd prefer

if (openList.empty()) {

as more readable, but that's not the bug.

What if the last open path is the correct one? Then openList will have a size of zero and it will say that no path has been found. You can fix this by changing

```
openList.remove(current);
if (current == goalNode) br

StackExchange Code Review Q#97834, answer score: 2