So I am creating a simple puzzle game with basic path-finding in a 2d environment, and I figured the simplest place to start would be an A* algorithm. After finding a few web sources I sat down and just started programming. After 15 minutes or so I managed to craft a basic heuristic A* algorithm.

Here is my NodeMap header:

#pragma once

#include
#include
#include

enum STATE {SOLID, PICKUP, FREE};

struct Coord {
int x,y;
bool operator<(const Coord& c) const {
if (x != c.x)
{
return x < c.x;
}
else
{
return y < c.y;
}

}
};

struct Node {
int id;
STATE state;
Node(int i = 0, STATE s = FREE) : id(i), state(s) { }
};

struct pathNode {
Node n;
int f, g;
float h;
Coord pos;
pathNode* parent;
};

struct Tiles {
std::string fname;
int x, y, w, h;
};

typedef std::map< Coord, Node > NodeGrid;
typedef std::map< Coord, pathNode > PathNodeGrid;

class NodeMap {
public:
NodeMap() {

}

~NodeMap() {

}

// Retrieves the node at x,y
Node getNode(Coord c) {
return this->grid[c];
}

// Sets the specified node at x,y to n
void setNode(Coord c, Node n) {
this->grid[c] = n;
}

// Shortcut to set the node at x,y to an empty,free node
void removeNode(Coord c) {
setNode(c, Node(0, FREE));
}

// Retrieves the begin iterator
NodeGrid::iterator begin() {
return this->grid.begin();
}

// Retrieves the end iterator
NodeGrid::iterator end() {
return this->grid.begin();
}

// Finds the path to the target node starting at x,y
void FindPath(Coord player);

// Get the iterator to the path
std::vector::iterator GetPath() {
if (path.size() > 0) {
return path.begin();
}
}

void SetGoal(int x, int y) {
this->goal.x = x;
this->goal.y = y;
}
private:
NodeGrid grid;
std::vector path;
Coord goal;
PathNodeGrid openList;
PathNodeGrid closedList;
};



Here is the guts of the A*. The input is simply where the player is now. Previously you will need to set the goal by calling NodeMap::SetGoal.

#include "NodeMap.h"


void NodeMap::FindPath(Coord player) {

pathNode playerNode = {this->grid[player], 0,0,0, player, nullptr};
pathNode targetNode;
this->openList[player] = playerNode;

while (this->openList.size() > 0) {
// Find the lowest f cost in the this->openList,
// set it as our loc node,
// and move it to the this->closedList
PathNodeGrid::iterator lowest = this->openList.begin();
for (PathNodeGrid::iterator itr = this->openList.begin(); itr != this->openList.end(); ++itr) {
if (itr->second.f < lowest->second.f) {
lowest = itr;
}
}

if (lowest == openList.end()) { // Make sure we have a valid element
return;
}

this->closedList.insert(*lowest);
pathNode* curNode = &this->closedList[lowest->second.pos]; // grab the pointer to the closed list item as the one in open list will be removed
this->openList.erase(lowest);
if ((curNode->pos.x == goal.x) && (curNode->pos.y == goal.y)) {
targetNode = *curNode;
// We have reach out goal so lets store the path
pathNode* parent = &targetNode
while (parent != nullptr) {
this->path.push_back(parent->pos);
parent = parent->parent;
}
return;
}


// Get the surrounding nodes
pathNode temp;
int cost;
Coord loc = player;
for (int x = -1; x < 2; ++x) {
for (int y = -1; y < 2; ++y) {
if ((x == 0) && (y == 0)) { // We don't need to check the current node
continue;
} else if ((x == 0) || (y == 0)) {
cost = 10;
} else {
cost = 14;
}
loc.x = curNode->pos.x + x;
loc.y = curNode->pos.y + y;
if (this->grid.find(loc) != this->grid.end()) { // Node at coords exists
if ((this->openList.find(loc) == this->openList.end()) && (this->closedList.find(loc) == this->closedList.end())) { // Not on open or closed list
if (this->grid[loc].state == FREE) {
temp.g = cost + curNode->g;
temp.h = sqrt((float)((this->goal.x - curNode->pos.x)^2 + (this->goal.y - curNode->pos.y)^2));
temp.f = (float)temp.g + temp.h;
temp.pos = loc;
temp.parent = curNode;
this->openList[loc] = temp;
}
} else if (this->openList.find(loc) != this->openList.end()) {
if (this->openList[loc].g > (curNode->g + cost)) {
this->openList[loc].parent = curNode;
this->openList[loc].g = (curNode->g + cost);
this->openList[loc].f = (float)this->openList[loc].g + this->openList[loc].h;
}
}
}
}
}
}
}


My choice in using a map for my open and closed list is what I am going to talk about. First when doing the open list, you don't need to sort it as most tutorials say. This is just a waste of time. you need to iterate over the list one way or another to find the smallest f. By sorting by f values you my end up going through the whole list anyway. Another tip is to always look for the quick out. I am constantly checking to make sure the coord exists to exit the loop early. This may seem like a waste, but if I can save several inner loops I will.