Allegro.cc - Online Community

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

This thread is locked; no one can reply to it. rss feed Print
A* Pathfinding library help
Rick
Member #3,572
June 2003
avatar

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.

========================================================
Actually I think I'm a tad ugly, but some women disagree, mostly Asians for some reason.

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
avatar

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"}590309[/center]
[center]590308[/center]

1TILEWIDTH b
2TILEHEIGHT c
3TILEOFFSET ( ( 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
avatar

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
2) 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
avatar

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
14int 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
20bool 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
avatar

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 :)

Neil.
MAME Cabinet Blog / AXL LIBRARY (a games framework) / AXL Documentation and Tutorial

wii:0356-1384-6687-2022, kart:3308-4806-6002. XBOX:chucklepie

DanielH
Member #934
January 2001
avatar

The fact that it was on AGDN should have said 'Hey, Dan wrote this'. ;D. 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
2. width
3. height

Optional
4. function calcWeight( col, row ): calc's weight of tile at col, row
5. 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 1
If you don't supply 5. then the default is 0

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
avatar

Thanks DanielH, I'll give it a try.

[EDIT]
1 quick change

in 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 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 );
}

========================================================
Actually I think I'm a tad ugly, but some women disagree, mostly Asians for some reason.

DanielH
Member #934
January 2001
avatar

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
avatar

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.
MAME Cabinet Blog / AXL LIBRARY (a games framework) / AXL Documentation and Tutorial

wii:0356-1384-6687-2022, kart:3308-4806-6002. XBOX:chucklepie

Rick
Member #3,572
June 2003
avatar

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: