A* Pathfinding. Almost works 100%(SDL)

[zertech]

Hi
So i just finished a semester of C++. For my final project i attempted an implimentation of the A* pathfinding algorithm.

It almost works 100% except in some situations somehow the only available neighbor becomes viewed as the current node, creating an infinite loop. This is weird because i know for a fact that at the points when this happends there should be atleast 1 node that is traversable.

heres a picture of what the glitch looks like.
The green is the path, the start is the goal node. Grey are walls and tanned is a traversable node.
http://img442.imageshack.us/img442/638/thiscrapisfrustrating.png



The problem seems to lye somewhere in the Path class, specifically in the Next() method. However im not sure where or why.

Ive already handed in this as my project however id still like to figure out what the problem is. I spent allot of time on it so it would be a bummer to abandon it unfinished.

Here is the class declaration and whatnot, also take note the dummy node is a node that was create outside of the array.

A path object gets instantiated once the user presses a button and all the nodes are set up. The next method just gets executed like 50 times. eventually im gonna do a while loop that will keep executing until the goal node is in the path

	void Path::next(Node nodes[],Node dummy){
		int num_of_neighbors = 0;
		current = path[size-1];
		
		for(int i = 0; i <192;i++){
			if((nodes[i].x == current.x)&&(nodes[i].y == current.y-50)&&(nodes[i].state !=1)){//find northern neighbor
			//	apply_surface( nodes[i].x, nodes[i].y, tile_two, screen);
				neighbors[0] = nodes[i];
				num_of_neighbors++;
			}
			

			if((nodes[i].x == current.x)&&(nodes[i].y == current.y+50)&&(nodes[i].state !=1)){//find southern neighbor
			//	apply_surface( nodes[i].x, nodes[i].y, tile_two, screen);
				neighbors[1] = nodes[i];
				num_of_neighbors++;}

			if((nodes[i].x == current.x-50)&&(nodes[i].y == current.y)&&(nodes[i].state !=1)){//find eastern neighbor
				//apply_surface( nodes[i].x, nodes[i].y, tile_two, screen);

				neighbors[2] = nodes[i];
				num_of_neighbors++;}
			
			if((nodes[i].x == current.x+50)&&(nodes[i].y == current.y)&&(nodes[i].state !=1)){//find western neighbor
				//apply_surface( nodes[i].x, nodes[i].y, tile_two, screen);
				neighbors[3] = nodes[i];
				num_of_neighbors++;}
		
			if((nodes[i].x == current.x-50)&&(nodes[i].y == current.y-50)&&(nodes[i].state !=1)){//north-western neighbor
				//apply_surface( nodes[i].x, nodes[i].y, tile_two, screen);
				neighbors[4] = nodes[i];
				num_of_neighbors++;}
			
			if((nodes[i].x == current.x-50)&&(nodes[i].y == current.y+50)&&(nodes[i].state !=1)){//south-western neighbor
				//apply_surface( nodes[i].x, nodes[i].y, tile_two, screen);
				neighbors[6] = nodes[i];
				num_of_neighbors++;}

			if((nodes[i].x == current.x+50)&&(nodes[i].y == current.y+50)&&(nodes[i].state !=1)){//south-eastern neighbor
				//apply_surface( nodes[i].x, nodes[i].y, tile_two, screen);
				neighbors[7] = nodes[i];
				num_of_neighbors++;}

			if((nodes[i].x == current.x+50)&&(nodes[i].y == current.y-50)&&(nodes[i].state !=1)){//north eastern neighbor
				//apply_surface( nodes[i].x, nodes[i].y, tile_two, screen);
				neighbors[5] = nodes[i];
				num_of_neighbors++;}
			//cout<<"i have "<<num_of_neighbors << "     ";
			
	}



		if(num_of_neighbors > 0){
			int small = 0;
			for(int i = 0; i < 8; i++){
				if(neighbors[i].in_path != 1){
					small = i;}}
			for(int i = 0; i<8; i++){
				if(neighbors[i].state == 1){//if the neighbor is a wall, replace it with the dummy node. 
					neighbors[i] = dummy;
				}

					

				if(distance(neighbors[i]) <distance(neighbors[small])){//if distence of current node in neighbors is smaller than distance of node in neighbors list at small
					int ok = 1;
					for(int n = 0; n<size; n++){//this for loop finds out if neighbors[i] is already in the path list
						if(neighbors[i].my_index == path[n].my_index){
							ok = 0;}}
						if(ok == 1){
						small = i;
						}}}
			if(goal.my_index != current.my_index){
					size++;
					path.resize(size);
					path[size-1]=neighbors[small];
					nodes[neighbors[small].my_index].state = 1;
					apply_surface( neighbors[small].x, neighbors[small].y, tile_two, screen);
			} 
		
			for(int i = 0; i<8; i++){
				cout<<current.my_index<<endl;}
			}
		else{
			current.state = 2;
			//apply_surface( current.x, current.y, wall, screen);

			size -= 1;
			path.resize(size);
			

		}
	memset (neighbors,NULL,8);
	num_of_neighbors = 0;
}

};
Path::Path(){
	index = 0;
	size = 0;
	finished = 0;
}

[cire]

My first thoughts are:

if((nodes[i].x == current.x-50)&&(nodes[i].y == current.y)&&(nodes[i].state !=1)){//find eastern neighbor 

implies that x increases as one goes west and decreases as one goes east.

if((nodes[i].x == current.x+50)&&(nodes[i].y == current.y)&&(nodes[i].state !=1)){//find western neighbor

reinforces that, but

if((nodes[i].x == current.x-50)&&(nodes[i].y == current.y-50)&&(nodes[i].state !=1)){//north-western neighbor

implies the opposite, and so do the other non-cardinal directions.

Other thoughts: You're looking for 8 neighbors. Why do you need to loop 192 times?

Why are nodes 50 units apart? Wouldn't they be simpler to manipulate if they were 1 unit apart (and so could be represented by say an array with indexes, removing the need to iterate over every node in the map just to find neighbors?)

[zertech]

I actually re-wrote alot of the code, made it more efficient, and than your post helped me. figure out that last part.

The nodes are 50 units apart because each tile is 50x50 pixels.

It works perfectly now.

I changed the neighbors array to a vector so i could resize it to 0 and clear it.
I also just kinda cleaned it all up.
so yeah, thanks!!

heres the modified code.

void Path::next(Node nodes[],Node dummy){
int num_of_neighbors = 0;
current = path[sizep-1];

for(int i = 0; i <192;i++){
if((nodes[i].x == current.x)&&(nodes[i].y == current.y-50)&&(nodes[i].state !=1)){//northern
sizen++;
neighbors.resize(sizen);
neighbors[sizen-1] = nodes[i];

}


if((nodes[i].x == current.x)&&(nodes[i].y == current.y+50)&&(nodes[i].state !=1)){//find southern neighbor
sizen++;
neighbors.resize(sizen);
neighbors[sizen-1] = nodes[i];}

if((nodes[i].x == current.x+50)&&(nodes[i].y == current.y)&&(nodes[i].state !=1)){//find eastern neighbor
sizen++;
neighbors.resize(sizen);
neighbors[sizen-1] = nodes[i];}

if((nodes[i].x == current.x-50)&&(nodes[i].y == current.y)&&(nodes[i].state !=1)){//find western neighbor
sizen++;
neighbors.resize(sizen);
neighbors[sizen-1] = nodes[i];}

if((nodes[i].x == current.x-50)&&(nodes[i].y == current.y-50)&&(nodes[i].state !=1)){//north-western neighbor
sizen++;
neighbors.resize(sizen);
neighbors[sizen-1] = nodes[i];}

if((nodes[i].x == current.x-50)&&(nodes[i].y == current.y+50)&&(nodes[i].state !=1)){//south-western neighbor
sizen++;
neighbors.resize(sizen);
neighbors[sizen-1] = nodes[i];}

if((nodes[i].x == current.x+50)&&(nodes[i].y == current.y+50)&&(nodes[i].state !=1)){//south-eastern neighbor
sizen++;
neighbors.resize(sizen);
neighbors[sizen-1] = nodes[i];}

if((nodes[i].x == current.x+50)&&(nodes[i].y == current.y-50)&&(nodes[i].state !=1)){//north eastern neighbor
sizen++;
neighbors.resize(sizen);
neighbors[sizen-1] = nodes[i];}

}


//if there are traversable neighbor
if(sizen>0){
int smallest = 0;
//loop through neighbors vector
for(int i = 0; i<sizen; i++){
//see if this neighbor is got a better f scor than the one at endex smallest
if(distance(neighbors[i],current) < distance(neighbors[smallest],current)){
smallest = i;
}
}
cout<<sizen<<endl;
//expand the sizep
sizep++;
//add a spot for the new node in the path
path.resize(sizep);
//put the node in the path vector
path[sizep-1] = neighbors[smallest];
path[sizep-1].state = 1;
nodes[path[sizep-1].my_index].state= 1;
//apply_surface(path[sizep-1].x, path[sizep-1].y, tile_two, screen);
}
else{
sizep--;
path.resize(sizep);

}
sizen = 0;
neighbors.resize(sizen);



}