|
A* Pathfinding library help |
Rick
Member #3,572
June 2003
|
Via
http://libaxl.googlecode.com/svn/trunk/tests/tranzam/develop/code/version9/ I'm trying to use the A star part. The AStar Library here seems to want the x and y values instead of the row and col values. So I removed any reference to tilesize, since I already know the row and col for the start and end. I don't want the library to find the row and col based off an x and y value. Maily because this is an isometric map and the way it does it doesn't work for an isometric map. The problem is I can't get it to work. Here is the changed code: header [code] #ifndef retrospec_game_astar #define retrospec_game_astar //header for astar algorithm #define for if( false ) {} else for #define MAX_CHILDREN 8 //* A * class //steps for using /* 1. create new AstarClass passing in a 1/0 array represent the map (0=open, 1=blocked) 2. To start a path, call NewPath(...) followed by GetNodeX/GetNodeY to get the location of the tile element 3. When a path has been found (step 2) and we wish to simply get the next one use PathNextNode() and again GetnodeX/GetNodeY 4. To determine if a new node is required determine that !ReachedGoal() and the current position is the same as the current 'next tile to find' found in step 2 Others 1. If map is modified then call RedoAstarTileMap 2. Use FreeTile to see if we can move to a tile (it is not a blocked tile) 3. Use TileNum to return the tile number from a pixel location */ class AstarClass { //node represents a tile on our map typedef struct NODE { long f; // g+h (for calculating next/best node) long h; // distance from node to destination int g; // cost of travel (distance from source to node) int x; // destination stored here int y; // int NodeNum; // tile number (y*mapwidth+x effectively) NODE *Parent; // parent NODE *Child[ MAX_CHILDREN ]; // surrounding nodes NODE *NextNode; // for linked list } NODE; //our linked list of nodes, FIFO typedef struct STACK { NODE *NodePtr; //pointer to the inserted node STACK *NextStackPtr; //linked list } STACK; private: //moved from public int Height; //size of map int Width; //purely for TileNumFromPixelLocation() int TotalSize; //height*width int *TileMap; //map to an array of the same size as the real map //array of 1's and 0's for open (0) or blocked (1) NODE *OpenNode; //where we haven't been NODE *ClosedNode; //where we've been NODE *PathNode; //current path node STACK *Stack; //list of best nodes NODE *First; // NW added, to go back to start of list public: AstarClass( int *map, int width, int height); //constructor. pass in map contain open/blocked items ~AstarClass(); //destructor. frees up everything void RedoAstarTileMap( int *map ); //recreate map array (in case original tile map is modified) bool NewPath( int source_x , //create and find a path. returns true if there is one int source_y , int dest_x , int dest_y, bool allowDiag=true ); bool ReachedGoal(); //are we there yet void PathNextNode(); //next node in the path int NodeGetX(); //x,y of the current path node int NodeGetY(); void NodeGoFirst(); //reset current path to the first one (NW) bool FreeTile( int x , int y ); //is tile at x/y (pixels) open (Available to be moved to) int TileNum( int x , int y ); //return array element of map using x/y in pixels private: void FreeNodes(); //cleanup. called by destructor void FindPath( int source_x , //generate the path. called by newpath int source_y , int dest_x , int dest_y ); NODE *ReturnBestNode(); //these are called by findpath for creating the path void GenerateSuccessors( NODE *BestNode , int dest_x , int dest_y ); void GenerateSucc( NODE *BestNode , int x , int y , int dest_x , int dest_y ); NODE *CheckOPEN( int tilenum ); NODE *CheckCLOSED( int tilenum ); void Insert( NODE *Successor ); void PropagateDown( NODE *Old ); void Push( NODE *NODE ); NODE *Pop(); //stuff moved from public bool isPath; //if true then we have a path from src to dst //allegro specific stuff int distance( int x , int y ); bool AllowDiagonalMovement; }; #endif [/code] cpp [code] #ifndef astarclass #define astarclass #include <allegro.h> #include "AStar.h" AstarClass::AstarClass( int *map, int width, int height ) { Stack = ( STACK * )calloc( 1 , sizeof( STACK ) ); isPath = false; OpenNode = NULL; ClosedNode = NULL; PathNode = NULL; AllowDiagonalMovement=true; //lines below used to be a method called InitAstarTileMap( map ); //but pointless as never called really outside of constructor Width = width; Height = height; TotalSize = Height *Width; int i,j; TileMap = new int[ TotalSize ]; for ( i = 0; i < Width; i ++ ) { for ( j = 0; j < Height; j ++ ) { TileMap[ i + j * Width ] = map[ i + j * Width ]; } } First=NULL; } AstarClass::~AstarClass() { FreeNodes(); free( Stack ); if ( TileMap ) delete []TileMap; } // If we did any changes to the map then we would have to fix the astar class void AstarClass::RedoAstarTileMap( int *map ) { for ( int i = 0; i < Width; i ++ ) { for ( int j = 0; j < Height; j ++ ) { TileMap[ i + j * Width ] = map[ i + j * Width ]; } } } //find a new path using source and destination //can be time consuming so maybe link to a timer or know only when changed locations bool AstarClass::NewPath( int source_x , int source_y , int dest_x , int dest_y, bool dm ) { this->AllowDiagonalMovement=dm; if ( FreeTile( dest_x , dest_y ) && FreeTile( source_x , source_y ) && ( TileNum( source_x , source_y ) != TileNum( dest_x , dest_y ) ) ) { isPath = true; FreeNodes(); FindPath( source_x , source_y , dest_x , dest_y ); return ( isPath ); } First=NULL; return ( isPath = false ); } //have we reached our goal yet //returns true if // a) there is no path // b) there is a path and no more items in list bool AstarClass::ReachedGoal() { //is there an open path to the destination if ( !isPath ) return true; if ( PathNode->Parent != NULL ) return false; return true; } //get the tile bit using a pixel location int AstarClass::TileNum( int x , int y ) { return ( ( x ) + ( y * Width ) ); } //is there an empty tile at block location x/y bool AstarClass::FreeTile( int x , int y ) { if(x<0 || y<0 || x >= (Width)) return false; //can't go off edge (bottom already ok) if ( TileMap[ ( x ) + ( y ) * Width] == 0 ) return true; return false; } void AstarClass::PathNextNode() { PathNode = PathNode->Parent; if(!First) First=PathNode; } int AstarClass::NodeGetX() { return PathNode->x; } int AstarClass::NodeGetY() { return PathNode->y; } void AstarClass::NodeGoFirst() { PathNode=First; } /* private stuff */ void AstarClass::FreeNodes() { NODE *NODE , *OldNODE; if ( OpenNode != NULL ) { NODE = OpenNode->NextNode; while ( NODE != NULL ) { OldNODE = NODE; NODE = NODE->NextNode; free( OldNODE ); } } if ( ClosedNode != NULL ) { NODE = ClosedNode->NextNode; while ( NODE != NULL ) { OldNODE = NODE; NODE = NODE->NextNode; free( OldNODE ); } } } void AstarClass::FindPath( int source_x , int source_y , int dest_x , int dest_y ) { NODE *Node , *BestNode; int TileNumDest; isPath = true; TileNumDest = TileNum( source_x , source_y ); OpenNode = ( NODE * )calloc( 1 , sizeof( NODE ) ); ClosedNode = ( NODE * )calloc( 1 , sizeof( NODE ) ); Node = ( NODE * )calloc( 1 , sizeof( NODE ) ); Node->g = 0; Node->h = distance( ( dest_x - source_x ) , ( dest_y - source_y ) ); Node->f = Node->g + Node->h; Node->NodeNum = TileNum( dest_x , dest_y ); Node->x = dest_x; Node->y = dest_y; OpenNode->NextNode = Node; for ( ;; ) { BestNode = ReturnBestNode(); if ( BestNode == NULL ) break; if ( BestNode->NodeNum == TileNumDest ) break; GenerateSuccessors( BestNode , source_x , source_y ); } PathNode = BestNode; First=PathNode; } AstarClass::NODE *AstarClass::ReturnBestNode() { NODE *tmp; if ( OpenNode->NextNode == NULL ) { isPath = false; tmp = NULL; return tmp; } tmp = OpenNode->NextNode; OpenNode->NextNode = tmp->NextNode; tmp->NextNode = ClosedNode->NextNode; ClosedNode->NextNode = tmp; return( tmp ); } void AstarClass::GenerateSuccessors( NODE *BestNode , int dest_x , int dest_y ) { int x , y; // Upper - Left if ( AllowDiagonalMovement && FreeTile( x = BestNode->x , y = BestNode->y ) ) GenerateSucc( BestNode , x , y , dest_x , dest_y ); // Upper if ( FreeTile( x = BestNode->x , y = BestNode->y ) ) GenerateSucc( BestNode , x , y , dest_x , dest_y ); // Upper - Right if ( AllowDiagonalMovement && FreeTile( x = BestNode->x , y = BestNode->y ) ) GenerateSucc( BestNode , x , y , dest_x , dest_y ); // Right if ( FreeTile( x = BestNode->x , y = BestNode->y ) ) GenerateSucc( BestNode , x , y , dest_x , dest_y ); // Lower - Right if ( AllowDiagonalMovement && FreeTile( x = BestNode->x , y = BestNode->y ) ) GenerateSucc( BestNode , x , y , dest_x , dest_y ); // Lower if ( FreeTile( x = BestNode->x , y = BestNode->y ) ) GenerateSucc( BestNode , x , y , dest_x , dest_y ); // Lower - Left if ( AllowDiagonalMovement && FreeTile( x = BestNode->x , y = BestNode->y ) ) GenerateSucc( BestNode , x , y , dest_x , dest_y ); // Left if ( FreeTile( x = BestNode->x , y = BestNode->y ) ) GenerateSucc( BestNode , x , y , dest_x , dest_y ); } void AstarClass::GenerateSucc( NODE *BestNode , int x , int y , int dest_x , int dest_y ) { int g , TileNumS , c = 0; NODE *Old , *Successor; g = BestNode->g + 1; TileNumS = TileNum( x , y ); if ( ( Old = CheckOPEN( TileNumS ) ) != NULL ) { for( c = 0; c < MAX_CHILDREN; c ++ ) { if( BestNode->Child[ c ] == NULL ) { break; } } BestNode->Child[ c ] = Old; if ( g < Old->g ) { Old->Parent = BestNode; Old->g = g; Old->f = g + Old->h; } } else if ( ( Old = CheckCLOSED( TileNumS ) ) != NULL ) { for( c = 0; c < MAX_CHILDREN; c ++ ) { if ( BestNode->Child[ c ] == NULL ) break; } BestNode->Child[ c ] = Old; if ( g < Old->g ) { Old->Parent = BestNode; Old->g = g; Old->f = g + Old->h; PropagateDown( Old ); } } else { Successor = ( NODE* )calloc( 1 , sizeof( NODE ) ); Successor->Parent = BestNode; Successor->g = g; Successor->h = distance( ( x - dest_x ) , ( y - dest_y ) ); Successor->f = g + Successor->h; Successor->x = x; Successor->y = y; Successor->NodeNum = TileNumS; Insert( Successor ); for( c = 0; c < MAX_CHILDREN; c ++ ) { if ( BestNode->Child[ c ] == NULL ) break; } BestNode->Child[ c ] = Successor; } } AstarClass::NODE *AstarClass::CheckOPEN( int tilenum ) { NODE *tmp; tmp = OpenNode->NextNode; while ( tmp != NULL ) { if ( tmp->NodeNum == tilenum ) { return ( tmp ); } else { tmp = tmp->NextNode; } } return( NULL ); } AstarClass::NODE * AstarClass::CheckCLOSED( int tilenum ) { NODE *tmp; tmp = ClosedNode->NextNode; while ( tmp != NULL ) { if ( tmp->NodeNum == tilenum ) { return( tmp ); } else { tmp = tmp->NextNode; } } return( NULL ); } void AstarClass::Insert( NODE *Successor ) { NODE *tmp1 , *tmp2; int f; if ( OpenNode->NextNode == NULL ) { OpenNode->NextNode = Successor; return; } // insert into OpenNode successor wrt f f = Successor->f; tmp1 = OpenNode; tmp2 = OpenNode->NextNode; while ( ( tmp2 != NULL ) && ( tmp2->f < f ) ) { tmp1 = tmp2; tmp2 = tmp2->NextNode; } Successor->NextNode = tmp2; tmp1->NextNode = Successor; } void AstarClass::PropagateDown( NODE *Old ) { int c , g; NODE *Child , *Father; g = Old->g; for ( c = 0; c < MAX_CHILDREN; c ++ ) { if ( ( Child = Old->Child[ c ] ) == NULL ) break; if ( g + 1 < Child->g ) { Child->g = g + 1; Child->f = Child->g + Child->h; Child->Parent = Old; Push( Child ); } } while ( Stack->NextStackPtr != NULL ) { Father = Pop(); for ( c = 0; c < MAX_CHILDREN; c ++ ) { if ( ( Child = Father->Child[ c ] ) == NULL ) break; if ( Father->g + 1 < Child->g ) { Child->g = Father->g + 1; Child->f = Child->g + Child->h; Child->Parent = Father; Push( Child ); } } } } void AstarClass::Push( NODE *NODE ) { STACK *tmp; tmp = ( STACK * )calloc( 1 , sizeof( STACK ) ); tmp->NodePtr = NODE; tmp->NextStackPtr = Stack->NextStackPtr; Stack->NextStackPtr = tmp; } AstarClass::NODE *AstarClass::Pop() { NODE *tmp; STACK *tmpSTK; tmpSTK = Stack->NextStackPtr; tmp = tmpSTK->NodePtr; Stack->NextStackPtr = tmpSTK->NextStackPtr; free( tmpSTK ); return( tmp ); } int AstarClass::distance( int x , int y ) { //return abs(abs(x)+abs(y)); return fixtoi( fhypot( itofix( x ) , itofix( y ) ) ); } /* // Global Variables BITMAP *buffer; BITMAP *sprite; AstarClass *astar; int posX; int posY; int tilemap[ MAZE_WIDTH * MAZE_HEIGHT ] = { 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1, 1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,1,0,1,1, 1,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,1,0,1,1, 1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,0,1,1, 1,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,0,0,0,1,1, 1,0,1,1,1,0,1,1,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1, 1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,1,1,1,1, 1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,0,1,1, 1,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,1,1, 1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,1, 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1, 1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1, 1,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,1, 1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1,1,1,1,0,1,0,1,1, 1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,1,0,1,1, 1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,0,1,0,1,1, 1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,0,1,1, 1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1, 1,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,0,1,1, 1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,1,0,1,1, 1,0,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,0,1,0,1,1, 1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,1,0,1,1,1,1, 1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0,0,0,0,1,1, 1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,1,1,1,1,1,0,1,1, 1,0,1,0,1,0,1,1,1,0,1,1,0,1,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,0,0,0,0,1,0,1,1, 1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,0,1,0,1,1, 1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,1,0,1,1, 1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 }; BITMAP *create_ball(); void deleteAll(); void drawAll(); void drawMouse( BITMAP *bmp ); int initAll(); int random( int u ); int main(); int random( int u ) { return ( rand() % u ); } void drawMouse( BITMAP *bmp ) { triangle( bmp , mouse_x , mouse_y , mouse_x - 5 , mouse_y + 15 , mouse_x + 5 , mouse_y + 15 , makecol( 0 , 80 , 0 ) ); triangle( bmp , mouse_x , mouse_y + 1 , mouse_x - 4 , mouse_y + 14 , mouse_x + 4 , mouse_y + 14 , makecol( 0 , 255 , 0 ) ); } void drawAll() { int color[ 2 ]; color[ 0 ] = makecol( 0 , 0 , 0 ); color[ 1 ] = makecol( 255 , 0 , 0 ); clear_bitmap( buffer ); for ( int i = 0; i < MAZE_WIDTH; i ++ ) { for ( int j = 0; j < MAZE_HEIGHT; j ++ ) { rectfill( buffer , i * TileSize , j * TileSize , ( i + 1 ) * TileSize - 1 , ( j + 1 ) * TileSize - 1 , color[ tilemap[ i + j * MAZE_WIDTH ] ] ); } } draw_sprite( buffer , sprite , posX - TileSize / 2 , posY - TileSize / 2 ); drawMouse( buffer ); acquire_screen(); blit( buffer , screen , 0 , 0 , 0 , 0 , SCREEN_W , SCREEN_H ); release_screen(); } BITMAP *create_ball() { BITMAP * temp = create_bitmap( TileSize , TileSize ); clear_to_color( temp , makecol( 255 , 0 , 255 ) ); circlefill( temp , temp->w / 2 , temp->h / 2 , TileSize / 3 , makecol( 0 , 255 , 0 ) ); return temp; } int initAll() { allegro_init(); install_keyboard(); install_timer(); install_mouse(); set_color_depth( 16 ); if ( set_gfx_mode( GFX_AUTODETECT , 640 , 480 , 0 , 0 ) < 0 ) { allegro_message( "Unable initialize graphics module\n%s\n" , allegro_error ); return - 1; } srand( time( NULL ) ); buffer = create_bitmap( SCREEN_W , SCREEN_H ); clear( buffer ); sprite = create_ball(); astar = new AstarClass( tilemap ); posX = posY = TileSize + TileSize / 2; return 0; } void deleteAll() { if ( astar ) delete astar; if ( buffer ) destroy_bitmap( buffer ); if ( sprite ) destroy_bitmap( sprite ); } int main() { bool done = false; int destX , destY , mx , my , ky = 0; if ( initAll() < 0 ) return - 1; destX = posX; destY = posY; while ( !done ) { drawAll(); if ( key[ KEY_ESC ] ) done = true; if ( mouse_b & 1 ) { mx = mouse_x - ( mouse_x % TileSize ) + TileSize / 2; my = mouse_y - ( mouse_y % TileSize ) + TileSize / 2; if ( mx < ( MAZE_WIDTH * TileSize ) && my < ( MAZE_HEIGHT * TileSize ) ) { if ( astar->NewPath( posX , posY , mx , my ) ) { astar->PathNextNode(); destX = astar->NodeGetX(); destY = astar->NodeGetY(); } } } if ( !astar->ReachedGoal() && ( destX == posX ) && ( destY == posY ) ) { astar->PathNextNode(); destX = astar->NodeGetX(); destY = astar->NodeGetY(); } for ( int i = 0; i < ( TileSize / 4 ); i ++ ) { if ( destX > posX ) posX ++ ; if ( tilemap[ ( posX / TileSize ) + ( ( posY / TileSize ) * MAZE_WIDTH ) ] == 1 ) posX -- ; if ( destY > posY ) posY ++ ; if ( tilemap[ ( posX / TileSize ) + ( ( posY / TileSize ) * MAZE_WIDTH ) ] == 1 ) posY -- ; if ( destX < posX ) posX -- ; if ( tilemap[ ( posX / TileSize ) + ( ( posY / TileSize ) * MAZE_WIDTH ) ] == 1 ) posX ++ ; if ( destY < posY ) posY -- ; if ( tilemap[ ( posX / TileSize ) + ( ( posY / TileSize ) * MAZE_WIDTH ) ] == 1 ) posY ++ ; } } deleteAll(); return 0; } END_OF_MAIN(); */ #endif [/code] the example line I put in [code] int row, col; //init a star map for(row=0;row<MAP_ROW;row++) { for(col=0;col<MAP_COL;col++) { if(board[row][col].hasUnit()) mapPath[row*MAP_COL+col] = 1; else mapPath[row*MAP_COL+col] = 0; } } aStar = new AstarClass( mapPath, MAP_COL, MAP_ROW); if(!aStar->NewPath(1, 3, 2, 3, false)) allegro_message("Can't find path"); [/code] It returns false, which I don't know why. ======================================================== |
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) 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.
|
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 coords ======================================================== |
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.
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, 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 Neil. 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 respectively Optional If you don't supply 4. then the default is 1 NOTE: 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] in NewPath you have this->isFree( destCol, destRow ) && 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 different change 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 ); }
======================================================== |
DanielH
Member #934
January 2001
|
You're right on both accounts. if ( !( sourceRow == destRow && sourceCol == destCol ) && this->isFree( destCol, destRow ) )
EDIT: |
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. Neil. 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. ======================================================== |
|