Problems implementing A* - Need a knowledgeable eye to look at my code

Pether Pettersson · 2015-02-27T23:43:44

So I decided a few days ago that i would write my own implementation of A* since my earlier luck trying to add other peoples code and refactoring it to it'll work with my game failed all the time and only worked as time sinks. I followed this guide here: http://homepages.abdn.ac.uk/f.guerin/pages/teaching/CS1015/practicals/aStarTutorial.htm I am not really sure where the problems occur, but looking trough the open list it seems duplicates gets added even though i have a check that wouldn't enable that behavior. The algorithm just keeps going until i stop it, having thousands of Nodes in the lists from a 15 by 15 map. (The size is currently hardcoded) Pathfinding.h #include <vector> #include <algorithm> struct Position{ Position(){} Position(int x, int y){ this->x = x; this->y = y; } int x, y; }; class Node { public: Node(Position pos) { this->pos = pos; } Node* getParent() { return parent; }; void setParent(Node *parent) { this->parent = parent; } Position getPosition(){ return pos; } int getFcost(){ return g + h; } int getGcost(){ return g; } int getHcost(){ return g; } void setGcost(int g) { this->g = g; } void setHcost(int h) { this->h = h; } bool operator < (Node& str){ return (f < str.getFcost()); } private: Position pos; int f = 0; int g = 0; int h = 0; Node *parent; }; class Pathfinding { public: Pathfinding(){}; bool findPath(Position, Position, std::vector<std::vector<int>>); std::vector<Node*> getPath(){ return path; } //void checkNeighbours(Node*, Node*); void addToClosed(Node* current){ closed.push_back(current); } void addToOpen(Node* current) { open.push_back(current); } void removeFromOpen(Node*) { open.erase(open.begin()); } int calculateManhattanHeuristic(Position current, Position target) { return (10 * (std::abs(current.x - target.x) + std::abs(current.y - target.y))); } Node* getCurrentPoint(); bool inClosedList(Node*); bool inOpenList(Node*); private: std::vector<Node*> open; std::vector<Node*> closed; std::vector<Node*> path; }; Pathfinding.cpp #include "Pathfinding.h" bool Pathfinding::inClosedList(Node *current) { bool inClosed = false; for (int i = 0; i < closed.size(); i++) if (closed.at(i) == current) inClosed = true; return inClosed; } bool Pathfinding::inOpenList(Node *current) { bool inOpen = false; for (int i = 0; i < open.size(); i++) if (open.at(i) == current) inOpen = true; return inOpen; } Node* Pathfinding::getCurrentPoint(){ std::sort(open.begin(), open.end()); return open.at(0); } bool Pathfinding::findPath(Position startPos, Position targetPos, std::vector<std::vector<int>> map){ // Add starting and target position as Nodes. // No check if it's blocked or if they are the same yet. Node *start = new Node(startPos); Node *target = new Node(targetPos); // Add the start Node to the open list. addToOpen(start); do{ // Get the Node with the least F-score. Node *current = getCurrentPoint(); // Removes the current node from the open list. removeFromOpen(current); // Adds the current node to the closed list. addToClosed(current); // Creates temp neighbour Node, initializes g-cost to 0., creates node to see if it's diagonal movement. Node *neighbour; int newGcost = 0; bool corner; // For every position in a 3x3 area, all neighbours plus current position.. for (int x = -1; x < 2; x++) for (int y = -1; y < 2; y++) { // If it's the current position, skip. if (x == 0 && y == 0) { continue; } // If the neighbour's position is outside the map, skip. if (current->getPosition().x + x < 0 || current->getPosition().x + x > 14 || current->getPosition().y + y < 0 || current->getPosition().y + y > 14) { continue; } else{ // If the neighbour's is not blocked.. if (map.at(current->getPosition().x + x).at(current->getPosition().y + y) == 0) { // Check if diagonal. if (x != 0 && y != -1 && y != 1) corner = true; else corner = false; // Create neighbour at position. neighbour = new Node(Position(current->getPosition().x + x, current->getPosition().y + y)); // If the neighbour is not in the closed list. if (!inClosedList(neighbour)) { // Add G-cost dependand on corner, diagonal from current position. if (corner) { newGcost += 14 + current->getGcost(); } else newGcost += 10; // Add the G and H-cost. F-cost is calculated in the Node-class, getFcost(). neighbour->setGcost(newGcost); neighbour->setHcost(calculateManhattanHeuristic(current->getPosition(), target->getPosition())); // If neighbour is not in the open list. if (!inOpenList(neighbour)) { // Set current Node as neighbour's parent. neighbour->setParent(current); // Add neighbour to the open list. addToOpen(neighbour); } // If neighbour is in the open list. else { // Calculate new G-cost.. if (corner) { newGcost += 14 + current->getGcost(); } else newGcost += 10; // If the new G-cost is better then old G-cost for neighbour, change parent. Cheaper path found. if (current->getGcost() < neighbour->getGcost() + newGcost) { neighbour->setParent(current); } } } } // end neighbour blocked if. } } // Continue to look for a path until Open list is empty, there are no more Nodes to check. } while (!open.empty()); // If target Node is in closed list we have found a path. if (inClosedList(target)) { // Reverse the path trough the targets parents until we have gotten to the start position. // Set as path, get path with getPath(). Node* reverse = target; while (reverse != start) { //I noticed now that i hadn't completed this part. path.push_back(reverse); } // Return true as we have found a path. return true; } // Return false as we have not been able to find a path. else return false; } I am at loss at what to try next...

Artificial Intelligence Programming

Started by Pether February 20, 2015 04:48 PM

10 comments, last by Pether 9 years, 11 months ago

alvaro

21,610

February 23, 2015 12:51 AM

Did you manage to fix your code? If you can post a complete program that I can compile and run myself, I'll give you a hand. But you should learn how to debug your programs.

Pether

Author

497

February 27, 2015 11:43 PM

Heya,

no, I haven't got it to work. But I haven't had any time to look at it since last time as I've had three assignments due today and another one this weekend. In a world with unlimited time I would have created a better environment to test the pathfinding, showing all the values and behind able to create obstacles and new paths while it's running, but haven't had time to do that. But I have thought of doing a desk test since the fault most likely lies somewhere in the code that calculates the costs of moving, so I should be able to see where if I just write it down.

I cut the code down to the bare minimum to run and show the pathfinding.

https://www.dropbox.com/s/to7ljzjiuzlxlbd/Gamestuff.rar?dl=0

*edit*

I actually got it to work correctly, turns out the sortfunction for the vector didn't work as planned so I replaced it.