Jump to content
  • Advertisement
  • entries
    5
  • comment
    1
  • views
    8369

A*, a first attempt, and learned tips.

Sign in to follow this  
adam4813

636 views

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.
Sign in to follow this  


1 Comment


Recommended Comments

Simple problems cause big errors. i forgot to include a check to see if no path exists. I will update later with the correction.

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!