[Valeour]

Hey, I'm in the middle of developing an A* algorithm mainly for testing, and I've hit a bit of an issue:
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

[ButchDean]

Although you might think it's clearly obvious, your implementation is telling the agent to get to its destination along the wall one way or another. You need to debug the sections of the code to make sure that your bools are updating correctly.

[Valeour]

I don't get quite what you mean. Are you referring to the bools that are checking if the neighbours are in respective lists? Or the ones that define if they're a wall? Because I left them out (somewhat) intentionally in the screenshot.

I forgot to add a picture with walls, so I'll add one here:

[ButchDean]

Well it works a lot better by leaving them out. What did you leave out?

[Valeour]

It's in the menuMainState::Init() function commented out. I was just setting the Node->isWall bool to true at random places.

I'm just wondering if this is actually a form of A* path finding, or just a regular "Move-till-hit-wall-then-try-another-direction" kind of path finding.

It looks like a mix of both to be honest. I'm just wondering why it doesn't look like other implementations I've seen.

I implemented it using the Wikipedia's pesudocode example.

[ButchDean]

Well, it doesn't look like it is finding the shortest path to me - you can see that movement is either vertical or horizontal. From the Wikipedia article you have pointed to it states that Dijkstra's Algorithm is employed to find the minimum cost from the start to end locations, so your agent needs to be able to move diagonally as well in order to achieve this.

[Valeour]

So the A* is literally diagonal movement only? I mean, I tried the diagonal before, and it worked perfectly, but it wasn't what I was after.

I just found this documentation on A* and the example it shows that's similar to mine states that it's Dijkstra.

Meh. Looks like I've got some reading in store for me tonight!

Thank you Butch.

[ButchDean]

No, not diagonal only. Diagonal movement is part of the agent being able to execute the shortest path to the goal.

A* Pathfinding has tow goals:

1. Obstacle avoidance.
2. Finding the shortest path to the goal.

Enjoy your studying and good luck.

[Valeour]

Right, did some studying, most of it blew my mind still, but I'm pretty certain that it's finding the shortest path. All I need is the 'tie-breaker' to get the path that I wanted, but I think that's a bit too much for what I need right now. The effect I'm getting appears to be a Manhattan one, which you can test here, however my path finder works a bit differently:


Honestly, as long as it works, I guess there isn't much of a problem. I checked various other attempts, and I do indeed get the shortest path, or an equivalent one. (Which is why I need a 'tie-breaker')

Anyway, thanks for the help.

This post has been edited by Valeour: 01 April 2012 - 04:23 AM

[ButchDean]

No problem, and good work.