Allegro.cc Forums » Programming Questions » A* Pathfinding library help

 A* Pathfinding library help
 bhagabhi Member #1,660 November 2001 I dont know if this is it - but in the GenerateSuccessors method - you have every if-case pretty much the same... Shouldn't you add to the x and y in the if-case depending on direction? As it is now it looks as if you are checking one spot over and over again. (But with the only difference that the AllowDiagonalMovement check is added to every other if-case..)(edit)Another thing to take note of (a mistake I made when playing around with a-star) - If finding the path to an enemy - the block containing the enemy often reports as "non-walkable" - thus making the whole path invalid. - an approach would be to check for a path to a block one step from the enemy. (the same applies to the block where the player is). I did this mistake and it took a while to find the error.. Though - I say this without having looked very much at your source, so I am not sure it applies.(/edit)
DanielH
Member #934
January 2001

That's funny! It's my code. How did they get it?

The reason it uses x and y is because of the player's position. I could have easily used row and col and instead sent the player's position as ( x / tilesize ), ( y / tilesize ). I just didn't want the player to worry about such things. Let the ASTAR class do all that.

That code comes from here. There are others also including a couple of hexagon examples here.

Modifiying it to isometric really involves calculating the possible tiles to move from the position.

In the original there are 8 choices because one tile touches 8 more. With the maze I adjusted it to only worry about up,down,left,right.

```123
4X5
678
```

In the GenerateSuccessors function. You need to modify it to look for the tiles touching the iso tile. However your map is laid out.

```    if ( FreeTile( x = BestNode->x - TILESIZE , y = BestNode->y - TILESIZE ) )
GenerateSucc( BestNode , x , y , dest_x , dest_y );
```

This function tells if the tile you are looking at has a free tile above it. Modify the if statements to the center point of your tiles touching the tile at dest_x, dest_y.

Let's say that you are at S you need to check the six tiles next to S. Each tile is 64x32.
[center]{"name":"590309","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/f\/f\/ff59ff7420eb9c039f3551b266ea6ff2.png","w":320,"h":240,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/f\/f\/ff59ff7420eb9c039f3551b266ea6ff2"}[/center]
[center][/center]

 1 TILEWIDTH b 2 TILEHEIGHT c 3 TILEOFFSET ( ( b - a ) / 2 ) 4 5 6 // Tile # 1 7 if ( FreeTile( x = BestNode->x, y = BestNode->y + TILEHEIGHT ) ) 8 GenerateSucc( BestNode , x , y , dest_x , dest_y ); 9 10 // Tile # 2 11 if ( FreeTile( x = BestNode->x - ( TILEWIDTH - TILEOFFSET ), y = BestNode->y + TILEHEIGHT / 2 ) ) 12 GenerateSucc( BestNode , x , y , dest_x , dest_y ); 13 14 // etc.

 Rick Member #3,572 June 2003 Is it safe to assume that the only reason you care about x & y values is because:1) you do the transaltion to map coords2) you aren't doing the manhatten thingy to calc the h value ========================================================Actually I think I'm a tad ugly, but some women disagree, mostly Asians for some reason.
DanielH
Member #934
January 2001

Why I care about the x and y values is because the player has to move to that direction. If you don't need them then don't use them.

I also forgot in the last post you will have to modify the map variable of the the A* class.

 1 2 // map is currently an array, you need to change it to what you have 3 int i,j; 4 TileMap = new int[ TotalSize ]; 5 for ( i = 0; i < Width; i ++ ) 6 { 7 for ( j = 0; j < Height; j ++ ) 8 { 9 TileMap[ i + j * Width ] = map[ i + j * Width ]; 10 } 11 } 12 13 //get the tile bit using a pixel location 14 int AstarClass::TileNum( int x , int y ) 15 { 16 return ( ( x ) + ( y * Width ) ); 17 } 18 19 //is there an empty tile at block location x/y 20 bool AstarClass::FreeTile( int x , int y ) 21 { 22 if(x<0 || y<0 || x >= (Width)) return false; //can't go off edge (bottom already ok) 23 // if ( TileMap[ ( x ) + ( y ) * Width] == 0 ) return true; 24 if ( TileMap[ TileNum( x, y ) ] == 0 ) return true; 25 26 return false; 27 }

```2) you aren't doing the manhatten thingy to calc the h value
```

You can do the manhatten thingy if you would like. I was just making it simple for the tutorial purpose.

If you would like I could come up with a isometric A* program. It will be small and simple, but would work. Let me know.

 Neil Walker Member #210 April 2000 Hello,Glad you came out of the shadows A while ago when I was just learning A* I asked for some good tutorials, which were all good (I'd link but the search facility here doesn't work very well), but in the end I find the code at AGDN and asked here if anyone knew who wrote it, but nobody came forward You should always stick your name in your code so somebody can credit it at some time wii:0356-1384-6687-2022, kart:3308-4806-6002. XBOX:chucklepie
 DanielH Member #934 January 2001 The fact that it was on AGDN should have said 'Hey, Dan wrote this'. . No worries though.I rewrote the code, cleaned it up abit, and added some new functions that might be useful. The attachment above is the new class that handles 2darrays only. To make it simple, you need only to supply:1. 2d array: of 0's and 1's for unblocked or blocked respectively2. width3. heightOptional4. function calcWeight( col, row ): calc's weight of tile at col, row5. function calcDistance( sourceCol, sourceRow, destCol, destRow ): calc's distance from tile at sourceCol, sourceRow to destCol, destRow. If you don't supply 4. then the default is 1If you don't supply 5. then the default is 0NOTE: that I haven't tested it. I didn't write a tester program. I might be able to, but not at the moment. Maybe in a couple of days when I have more time.
 Rick Member #3,572 June 2003 Thanks DanielH, I'll give it a try.[EDIT]1 quick changein NewPath you have this->isFree( destCol, destRow ) && this->isFree( sourceCol, sourceRow ) )The sourceRow and Col wouldn't be open since that is where the unit that should move to dest row and col is standing.``` if ( sourceRow != destRow && sourceCol != destCol && this->isFree( destCol, destRow )) { this->isPath = true; this->freeNodes(); this->findPath( sourceCol, sourceRow, destCol, destRow ); } ``` Bug when either the rows are the same and the cols are different or cols are the same and rows are differentchange isFree to check 0 instead of 1 since 0 is open and 1 is closed I beleive ```bool Astar::isFree( int col, int row ) { return ( this->array[ getNumber( col, row ) ] == 0 ); } ``` ========================================================Actually I think I'm a tad ugly, but some women disagree, mostly Asians for some reason.
 DanielH Member #934 January 2001 You're right on both accounts.```if ( !( sourceRow == destRow && sourceCol == destCol ) && this->isFree( destCol, destRow ) ) ``` EDIT:If anyone would like. The original AStar code is attached. I took it from a CDXlib addon and modified it to my uses. It had a bug that would make the game crash if there was not an available path from source to dest. I fixed it.
 Neil Walker Member #210 April 2000 Quote: The fact that it was on AGDN should have said 'Hey, Dan wrote this' Perhaps it's not as well known as you'd like Perhaps I should give you my code modifications too, I changed the heuristic to give the option of euclidean, manhatten and diagonal.I think what it needs though is the ability to support weighted tiles, e.g. instead of just 1 or 0, have the number be a weighting factor. wii:0356-1384-6687-2022, kart:3308-4806-6002. XBOX:chucklepie
 Rick Member #3,572 June 2003 DanielH, I still couldn't get that code to work. I just created my own AStar class without diangle movement. It seems to work. On a side note, something that I did that I think makes sense is just store the 2d array in the class. Then provide an open(int row, int col), and closed(int row, int col) to the class. Now the user doesn't need to create an extra 2d array of ints. Once the constructor is called with rows and cols, the array is dynamically created in the class and that is what's used. I just found this easier. ========================================================Actually I think I'm a tad ugly, but some women disagree, mostly Asians for some reason.
 Go to: Allegro Development Installation, Setup & Configuration Allegro.cc Comments Off-Topic Ordeals The Depot Game Design & Concepts Programming Questions Recent Threads