• entries
5
• comment
1
• views
8291

# A*, a first attempt, and learned tips.

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

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

## 1 Comment

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

## Create an account

Register a new account