Pathfinding algorithm questions (not A*, oops)

[georgep]

Just had a go at the A* path-finding algorithm and although I think I've got it working, any constructive criticism would be much appreciated:

#include<iostream>

using namespace std;

int main()
{
	int h, w;
	cin >> h >> w;
	
	int map[h][w];
	
	for(int y=0; y < h; y++) {
	for(int x=0; x < w; x++) {
	
		cin >> map[y][x]; //-1 = blocked, 0 = clear
	
	}
	}
	
	int start_y, start_x;
	cin >> start_y >> start_x;
	
	map[start_y][start_x] = 1;
	
	int goal_y, goal_x;
	cin >> goal_y >> goal_x;
	
	bool update = false;
	
	
	do{
	 
	  update = false;
	
	  for(int a=0; a < h; a++) {
	  for(int b=0; b < w; b++) {
	  
	    
	    //for each node, check adjacent nodes, then update to lowest adjacent + 1
	    
	      if(a > 0)
	        if((map[a-1][b] > 0) && (((map[a-1][b] + 1) < map[a][b]) || (map[a][b] == 0)))
	        {  map[a][b] = map[a-1][b] + 1; update = true; }
	               
	      if(b > 0)
	        if((map[a][b-1] > 0) && (((map[a][b-1] + 1) < map[a][b]) || (map[a][b] == 0)))
	        {  map[a][b] = map[a][b-1] + 1; update = true; }
	      
	      if(a < (h - 1))
	        if((map[a+1][b] > 0) && (((map[a+1][b] + 1) < map[a][b]) || (map[a][b] == 0)))
	        {  map[a][b] = map[a+1][b] + 1; update = true; }
	      
	      if(b < (w - 1))
	        if((map[a][b+1] > 0) && (((map[a][b+1] + 1) < map[a][b]) || (map[a][b] == 0)))
	        {  map[a][b] = map[a][b+1] + 1; update = true; }   
	  
	  }
	  }
			
					
	} while(update == true);
	
	if(map[goal_y][goal_x])
  { 
      cout << map[goal_y][goal_x] - 1 << endl; //actual distance is 1 less than stored value
      
      for(int y=0; y < h; y++) {
	    for(int x=0; x < w; x++) {
	    
        if(map[y][x] == -1)
          cout << "X ";
        else
		      cout << map[y][x] - 1 << " ";
	
	    }
	      cout << endl;
	    }
    
      return 0; 
  }
  
	else
	  cout << "no route\n";
	

	return 0;
}

[code updated]

The main part I'm unhappy with is the way that I've stored clear squares: at the moment they are given the value 0, but this prevents 0 being used as the starting position and, as a result, all distances must be decreased by 1 when they are outputted.

Apologies also on the code formatting - it looked fine in my editor, but I switched to spaces instead of tabs about halfway through.

[Peter87]

First of all, this is not the A* algorithm.

Also, you are not checking if the neighbour squares is within the map. For instance, map[a-1][b] is out of bounds when a == 0.

[georgep]

- It isn't?

- Actually, that's exactly what line 41 does

[Peter87]

- Actually, that's exactly what line 41 does

Oh, I missed that. Good :)


Maybe you could have used some better names for i,j,a,b. Why not call i and a y and j and b x because that is what they represent.

You have also made a mistake. map[goal_x][goal_y] should be map[goal_y][goal_x]. Same with map[start_x][start_y].

[BlackSheep]

A* has some form of weight (or heuristic) which describes how close you think you are to the goal. It then tests nodes based on the lowest cost, so that instead of checking every node like your algorithm does, you only check the "cheapest" ones until you reach the goal.

It's a little more complex, and testing each single tile is a more complex/expensive calculation because you have more variables, but in the long run it's much faster, and guaranteed (with a correct heuristic) to give you the shortest path.

On your algorithm:

int h, w;
cin >> h >> w;
	
int map[h][w];

This isn't legal C++. I think some compilers allow it (I don't know what you're using), but generally if you need a variables amount of memory during runtime you need to use pointers/containers.

Your algorithm is a little odd. It won't work properly unless your startx and starty are both at 0. For example, a 3*3 with start at 2,2 and end at 0,0 would give:

1,2,3
2,3,4
3,4,1

So it would tell you that the cost is 0, which is obviously false.

[georgep]

@Peter87:

I'm weird about variable names. I know that the x and y are the wrong way round but that's just how I did it. I guess I'll switch that now, same with a, b, i & j

___________________________________________________________

@BlackSheep

-Thanks, didn't know that about A*. I was under the impression that it was just a brute force pathfinding algorithm.

-Not legal C++? Really? I've always been under the impression that this was fine, and it's worked on every compiler (at least 3) that I've used.

-That definitely isn't the output that I get:

4 3 2 
3 2 1 
2 1 0 

and from what I've tested, any start_x and start_y (within the map of course) work absolutely fine.

___________________________________________________________

Question: From this current algorithm, how would you find the route, rather than the distance?

[BlackSheep]

Nah, anything stack based needs to have a definitive size during compile time. Your compiler is probably implementing it as a pointer for you. MVC++ 2010 doesn't allow it.

And you're right, I totally misinterpreted your algorithm. Although looking at it (correctly) again, it looks rather inefficient. Why don't you start directly at startx and starty and work from there? That way you don't have to keep looping over the whole map.

[georgep]

Do you mean spiral outwards, starting at the starting position?

[georgep]

And how do I work out the route using the above algorithm?

[BlackSheep]

Yeah, something like that. Although keeping a list of "open" nodes like in A* or dijkstra's algo would probably be faster.

And for the route I'd say start at the goal and work your way backwards, always picking the lowest cost node?

[georgep]

Hey, BlackSheep, just wondering:

So if I were to use a vector instead of an array, would I then be allowed to use a variable as the size?