My paths technically work, but they don't work like given examples I've seen.

Here's what I've got:

The standard blue path is what my outcome is, the purple path is what I'm sort of expecting. (I added the purple path in paint, which is why it's there.)

My only assumption is that it's just going by whichever neighbor it checks first, which is a bit annoying. I tried randomizing which neighbors it checks in what order, and it did have a much more different effect, but a bit messy.

Anyway, code is below:

//Stuff from the header file struct Node { Position Pos; int fScore; int gScore; int hScore; bool isWall; Node* Parent; }; //... static const int MAX_WIDTH = 32; static const int MAX_HEIGHT = 25; Node* Map[MAX_WIDTH*MAX_HEIGHT]; Node* Start; Node* End; void GetNeighbours(Node* currentNode, vector<Node*>& Neighbours); int GetHeuristic(Position& A, Position& B)/>; void Search(); vector<Node*> Path;

//Main code file void menuMainState::Init() { srand(time(NULL)); for(int y = 0; y < 25; ++y) for(int x = 0; x < 32; ++x) { Node* tempNode = new Node; tempNode->Pos.X = x; tempNode->Pos.Y = y; tempNode->fScore = 0; tempNode->gScore = 0; tempNode->hScore = 0; tempNode->isWall = false; tempNode->Parent = NULL; Map[x + y * MAX_WIDTH] = tempNode; tempNode = NULL; } //for(int i = 0; i < 100; ++i) // Map[rand() % 800]->isWall = true; /*Start = Map[rand() % 800]; End = Map[rand() % 800];*/ Start = Map[0]; End = Map[799]; Start->isWall = false; End->isWall = false; Search(); printf("menuMainState Init\n"); } void menuMainState::Draw(gameEngine* game) { for(int x = 0; x < 32; ++x) for(int y = 0; y < 25; ++y) { if(Map[x + y * MAX_WIDTH] != NULL) { if (!Map[x + y * MAX_WIDTH]->isWall) al_draw_rectangle(x*32,y*32, x*32 + 32, y*32 + 32, al_map_rgb(0,0,0), 1); else al_draw_filled_rectangle(x*32,y*32, x*32 + 32, y*32 + 32, al_map_rgb(0,0,0)); } } for(int i = 0; i < Path.size(); ++i) al_draw_filled_rectangle(Path[i]->Pos.X*32,Path[i]->Pos.Y*32, Path[i]->Pos.X*32 + 31, Path[i]->Pos.Y*32 + 31, al_map_rgb(0,0,255)); al_draw_filled_rectangle(Start->Pos.X*32,Start->Pos.Y*32, Start->Pos.X*32 + 31, Start->Pos.Y*32 + 31, al_map_rgb(0,255,0)); al_draw_filled_rectangle(End->Pos.X*32,End->Pos.Y*32, End->Pos.X*32 + 31, End->Pos.Y*32 + 31, al_map_rgb(255,0,0)); } void menuMainState::GetNeighbours(Node* currentNode, vector<Node*>& Neighbours) { int x = currentNode->Pos.X; int y = currentNode->Pos.Y; if(x > 0) if(Map[(x-1)+(y)*MAX_WIDTH] != NULL) Neighbours.push_back(Map[(x-1)+(y)*MAX_WIDTH]); if(y > 0) if(Map[(x)+(y-1)*MAX_WIDTH] != NULL) Neighbours.push_back(Map[(x)+(y-1)*MAX_WIDTH]); if(y < MAX_HEIGHT-1) if(Map[(x)+(y+1)*MAX_WIDTH] != NULL) Neighbours.push_back(Map[(x)+(y+1)*MAX_WIDTH]); if(x < MAX_WIDTH-1) if(Map[(x+1)+(y)*MAX_WIDTH] != NULL) Neighbours.push_back(Map[(x+1)+(y)*MAX_WIDTH]); } int menuMainState::GetHeuristic(Position& A, Position& B)/> { int d1 = abs(B.X - A.X); int d2 = abs(B.Y - A.Y); return d1 + d2; } void menuMainState::Search() { vector<Node*> openList; vector<Node*> closedList; openList.push_back(Start); Start->hScore = GetHeuristic(Start->Pos, End->Pos); while(!openList.empty()) { //Get lowest f(x) in list int lowestF = 0; Node* currentNode; for(int i = 0; i < openList.size(); ++i) if(openList[i]->fScore < openList[lowestF]->fScore) lowestF = i; currentNode = openList[lowestF]; //End Case if(currentNode->Pos == End->Pos) { Node* curr = currentNode; while(curr->Parent != NULL) { Path.push_back(curr); curr = curr->Parent; } break; } //Normal Case closedList.push_back(currentNode); for(vector<Node*>::iterator it = openList.begin(); it != openList.end(); ++it) { if((*it)->Pos == currentNode->Pos) { openList.erase(it); break; } } vector<Node*> Neighbours; GetNeighbours(currentNode, Neighbours); for(int i = 0; i < Neighbours.size(); ++i) { bool isInClosed = false; Node* Neighbour = Neighbours[i]; for(vector<Node*>::iterator it = closedList.begin(); it != closedList.end(); ++it) { if((*it)->Pos == Neighbour->Pos) { isInClosed = true; break; } } if(Neighbour->isWall || isInClosed) continue; int curGScore = currentNode->gScore + 1; bool gScoreIsBest = false; bool isInOpen = false; for(vector<Node*>::iterator it = openList.begin(); it != openList.end(); ++it) { if((*it)->Pos == Neighbour->Pos) { isInOpen = true; break; } } if(!isInOpen) { gScoreIsBest = true; Neighbour->hScore = GetHeuristic(Neighbour->Pos, End->Pos); openList.push_back(Neighbour); } else if(curGScore < Neighbour->gScore) gScoreIsBest = true; if(gScoreIsBest) { Neighbour->Parent = currentNode; Neighbour->gScore = curGScore; Neighbour->fScore = Neighbour->gScore + Neighbour->hScore; } } } }

I've tried moving diagonally, and that worked much better, which kind of shows the algorithm is actually working, but I would just like some insight as to why it's doing it the way it is.

Oh, and before I get crucified, I am aware there's plenty of ugly code in there, this whole thing is for practice and research, so yeah, sorry.

This post has been edited by **Valeour**: 31 March 2012 - 01:22 PM