[C++ -> AMXX] A* Pathfinder
I tried to convert this to AMXX, but i don't know much about C++
This code can find the way to move from point A to point B
The one thing is the most difficult: C++'s Struct and AMXX don't have it
AStar_PathFinder.h
PHP Code:
/*---------------------------------------------------------------------------------*/ /* _/_/_/ _/_/ _/_/ _/_/ _/_/ _/_/_/_/ */ /* _/ _/_/ _/_/ _/ _/ _/ _/ */ /* _/ _/_/_/ _/_/_/ _/ _/ _/ _/ _/ _/ _/ _/ */ /* _/ _/ _/ _/_/ _/ _/ _/ _/ _/ */ /* _/_/_/ _/_/ _/ _/_/ _/_/_/_/ _/_/_/_/_/ */ /* */ /*---------------------------------------------------------------------------------*/
#if !defined(ASTARPATHFINDER_INCLUDE_) #define ASTARPATHFINDER_INCLUDE_
#include <windows.h> #include <stdio.h> #include <stdlib.h> #include "Internal.h"
#if _MSC_VER >= 1000 #pragma once #endif // _MSC_VER >= 1000 #define SHIFT 6 // change this to reflect the the size. // Ex. 64x64 tile equals 2^6. or a shift of 6 #define TILESIZE 1 // change this also to reflect tile size. 64x64.
class AstarPathfinder { private: int ROWS, // tilemap data members, need to be initialisize COLS, // with current map's width and height TOTAL_TILES; // to allocate memory for the struct NODE { // node structure long f, h; int g, tmpg; int x, y; int NodeNum; NODE *Parent; NODE *Child[8]; // a node may have upto 8+(NULL) children. NODE *NextNode; // for filing purposes }; NODE *OPEN; // the node list pointers NODE *CLOSED; NODE *PATH; // pointer to the best path struct STACK { // the stack structure NODE *NodePtr; STACK *NextStackPtr; }; STACK *Stack; BOOL isPath;
public: AstarPathfinder(void); ~AstarPathfinder();
//void ChangeAstarTileMap(MAPBLOCK *pMap,int clearx,int cleary,int disablex,int disabley);
void InitAstarTileMap(MAPBLOCK * pMap, int w,int h); BOOL NewPath(int sx, int sy, int &dx, int &dy); // Must be called and be true // before getting the node entries. It frees the lists, // calls ::Findpath() and returns true if path is accessible BOOL ReachedGoal(void); // Call and check this function before using these 3 following void PathNextNode(void) { PATH=PATH->Parent; } int NodeGetX(void) { return PATH->x; } int NodeGetY(void) { return PATH->y; } // other usefull functions (do not change them they are used by the A* algorithm) int TileNum(int x, int y); // returns tilenum int FreeTile(int x, int y); // returns 1 = true if we can move on it
private: // The A* Algorithm and it's stuff int FindPath(int sx, int sy, int dx, int dy); void FreeNodes(void);// frees lists memory void GenerateSuccessors(NODE *BestNode, int dx, int dy); void GenerateSucc(NODE *BestNode,int x, int y, int dx, int dy); void Insert(NODE *Successor); void PropagateDown(NODE *Old); void Push(NODE *Node); // stack functions NODE *CheckOPEN(int tilenum); NODE *CheckCLOSED(int tilenum); NODE *ReturnBestNode(void); NODE *Pop(void); };
#endif // ASTARPATHFINDER_INCLUDE_ ...
AStar_PathFinder.cpp
PHP Code:
/*---------------------------------------------------------------------------------*/ /* _/_/_/ _/_/ _/_/ _/_/ _/_/ _/_/_/_/ */ /* _/ _/_/ _/_/ _/ _/ _/ _/ */ /* _/ _/_/_/ _/_/_/ _/ _/ _/ _/ _/ _/ _/ _/ */ /* _/ _/ _/ _/_/ _/ _/ _/ _/ _/ */ /* _/_/_/ _/_/ _/ _/_/ _/_/_/_/ _/_/_/_/_/ */ /* */ /*---------------------------------------------------------------------------------*/ #include "AstarPathFinder.h"
// wish this could be a good way to share tile map, [wy] char *TileMap; // pointer to the A* own tilemap data array
char first_time=1;
//////////////////////////////////////////////////////////////////////////////// // Constructor Destructor // ////////////////////////////////////////////////////////////////////////////////
AstarPathfinder::AstarPathfinder() { Stack = ( STACK* )calloc(1,sizeof( STACK )); isPath = FALSE; OPEN = NULL; CLOSED = NULL; PATH = NULL; }
////////////////////////////////////////////////////////////////////////////////
AstarPathfinder::~AstarPathfinder() { FreeNodes(); free(Stack); if ( TileMap ) delete [] TileMap; }
////////////////////////////////////////////////////////////////////// // Public Member Functions // //////////////////////////////////////////////////////////////////////
void AstarPathfinder::InitAstarTileMap(MAPBLOCK *pMap, int w,int h) { COLS = w; // note the cols should be 2 more than the map size ROWS = h; // because if we have a point at the extremes and we check TOTAL_TILES = ROWS*COLS; // to see if we can go in all directions, we don't need a // special case to check these. (same for rows)
if (first_time) { TileMap = new char[TOTAL_TILES]; int index = 0; // A* map index int CDXMapIndex = 0; for (int i = 0; i < ROWS; i++) // fill up the area with current map data { // 1 = obstacle for (int j = 0; j < COLS; j++) // 0 = free { if ( pMap[CDXMapIndex].bMoveAble==true && pMap[CDXMapIndex].bHaveAnother==false) // the first "forbidden" tiles TileMap[index] = 1; // in the CDX-tiles-bitmap are not else TileMap[index] = 0; CDXMapIndex++; // reachable index++; } } first_time=0; } }
////////////////////////////////////////////////////////////////////////////////
// ?????..?????????,??????..???????,????.[wy] BOOL AstarPathfinder::NewPath(int sx,int sy, int &dx,int &dy) { int ret; if ( FreeTile(dx,dy) && /*FreeTile(sx,sy) &&*/ (TileNum(sx,sy)!=TileNum(dx,dy)) ) { FreeNodes(); // clear node lists ret=FindPath(sx,sy,dx,dy); if (ret) return (isPath=TRUE); else return (isPath=FALSE); } else if ( FreeTile(dx-1,dy-1) && (TileNum(sx,sy)!=TileNum(dx-1,dy-1)) ) { dx--;dy--; FreeNodes(); // clear node lists ret=FindPath(sx,sy,dx,dy); if (ret) return (isPath=TRUE); else return (isPath=FALSE); } else if ( FreeTile(dx-1,dy) && (TileNum(sx,sy)!=TileNum(dx-1,dy)) ) { dx--; FreeNodes(); // clear node lists ret=FindPath(sx,sy,dx,dy); if (ret) return (isPath=TRUE); else return (isPath=FALSE); } else if ( FreeTile(dx-1,dy+1) && (TileNum(sx,sy)!=TileNum(dx-1,dy+1)) ) { dy++;dx--; FreeNodes(); // clear node lists ret=FindPath(sx,sy,dx,dy); if (ret) return (isPath=TRUE); else return (isPath=FALSE); } else if ( FreeTile(dx,dy-1) && (TileNum(sx,sy)!=TileNum(dx,dy-1)) ) { dy--; FreeNodes(); // clear node lists ret=FindPath(sx,sy,dx,dy); if (ret) return (isPath=TRUE); else return (isPath=FALSE); } else if ( FreeTile(dx,dy+1) && (TileNum(sx,sy)!=TileNum(dx,dy+1)) ) { dy++; FreeNodes(); // clear node lists ret=FindPath(sx,sy,dx,dy); if (ret) return (isPath=TRUE); else return (isPath=FALSE); } else if ( FreeTile(dx+1,dy-1) && (TileNum(sx,sy)!=TileNum(dx+1,dy-1)) ) { dx++; dy--; FreeNodes(); // clear node lists ret=FindPath(sx,sy,dx,dy); if (ret) return (isPath=TRUE); else return (isPath=FALSE); } else if ( FreeTile(dx+1,dy) && (TileNum(sx,sy)!=TileNum(dx+1,dy)) ) { dx++; FreeNodes(); // clear node lists ret=FindPath(sx,sy,dx,dy); if (ret) return (isPath=TRUE); else return (isPath=FALSE); } else if ( FreeTile(dx+1,dy+1) && (TileNum(sx,sy)!=TileNum(dx+1,dy+1)) ) { dx++;dy++; FreeNodes(); // clear node lists ret=FindPath(sx,sy,dx,dy); if (ret) return (isPath=TRUE); else return (isPath=FALSE); } else return (isPath=FALSE); }
////////////////////////////////////////////////////////////////////////////////
BOOL AstarPathfinder::ReachedGoal(void) // check it's return value before getting { // the node entries if ( !isPath ) return TRUE; // this looks a little bit strange if ( PATH->Parent != NULL ) // but prevents illegal calls of ::PathNextNode() return FALSE; // or ::PathGet*() else return TRUE; }
////////////////////////////////////////////////////////////////////////////////
int AstarPathfinder::TileNum(int x, int y) { if (x<0 || x>=COLS || y<0 || y>=ROWS) return 0; return (y*COLS + x); // The reason I add COLS+1 to // tile number is because I want the tile number to start at the 2nd // the column and the 2nd row. Because if we do this we don't have to have // a special case to test if at a boundary. In the function BoundaryTiles // I place 1's around the boundary, in this way when I call the function // FreeTile() it returns false because we can't go there. }
////////////////////////////////////////////////////////////////////////////////
int AstarPathfinder::FreeTile(int x, int y) { // returns 1 if tile is free(nothing on it). // Note: if TileMap[equation]==0 it means free so just !(not) it. if (x<0 || x>=COLS || y<0 || y>=ROWS) return 0; if (TileMap[y*COLS + x]!=1) // if 0, means cannot be reached . if 2, have another return 0; else return 1; // return(TileMap[y*COLS + x]); }
//////////////////////////////////////////////////////////////////////////////// // Private Member Functions // ////////////////////////////////////////////////////////////////////////////////
void AstarPathfinder::FreeNodes(void) { NODE *Node, *OldNode;
if ( OPEN != NULL ) { Node = OPEN->NextNode; while ( Node != NULL ) { OldNode = Node; Node = Node->NextNode; free(OldNode); } }
if ( CLOSED != NULL ) { Node = CLOSED->NextNode; while ( Node != NULL ) { OldNode = Node; Node = Node->NextNode; free(OldNode); } } }
//////////////////////////////////////////////////////////////////////////////// // A* Algorithm // ////////////////////////////////////////////////////////////////////////////////
int AstarPathfinder::FindPath(int sx, int sy, int dx, int dy) { NODE *Node, *BestNode; int TileNumDest;
TileNumDest = TileNum(sx, sy);
OPEN=( NODE* )calloc(1,sizeof( NODE )); CLOSED=( NODE* )calloc(1,sizeof( NODE ));
Node=( NODE* )calloc(1,sizeof( NODE )); Node->g = 0; Node->h = (dx-sx)*(dx-sx) + (dy-sy)*(dy-sy); // should really use sqrt(). Node->f = Node->g+Node->h; Node->NodeNum = TileNum(dx, dy); Node->x = dx; Node->y = dy;
OPEN->NextNode=Node; // make Open List point to first node for (;;) { BestNode=ReturnBestNode(); if (BestNode==NULL) return 0; if (BestNode->NodeNum == TileNumDest) // if we've found the end, break and finish break; GenerateSuccessors(BestNode,sx,sy); } PATH = BestNode; return 1; }
////////////////////////////////////////////////////////////////////////////////
AstarPathfinder::NODE *AstarPathfinder::ReturnBestNode(void) { NODE *tmp; char message[128];
if ( OPEN->NextNode == NULL ) { return NULL; // wsprintf(message,"No more nodes on OPEN: Perhaps tilenum destination not reachable!"); // MessageBox(0, message, "Error A* Pathfinder", MB_OK | MB_ICONERROR); // PostQuitMessage(0); //exit(1); }
// Pick Node with lowest f, in this case it's the first node in list // because we sort the OPEN list wrt lowest f. Call it BESTNODE.
tmp = OPEN->NextNode; // point to first node on OPEN OPEN->NextNode = tmp->NextNode; // Make OPEN point to nextnode or NULL.
// Next take BESTNODE (or temp in this case) and put it on CLOSED
tmp->NextNode = CLOSED->NextNode; CLOSED->NextNode = tmp;
return(tmp); }
////////////////////////////////////////////////////////////////////////////////
void AstarPathfinder::GenerateSuccessors(NODE *BestNode, int dx, int dy) { int x, y;
// Upper-Left if ( FreeTile(x=BestNode->x-TILESIZE, y=BestNode->y-TILESIZE) ) GenerateSucc(BestNode,x,y,dx,dy); // Upper if ( FreeTile(x=BestNode->x, y=BestNode->y-TILESIZE) ) GenerateSucc(BestNode,x,y,dx,dy); // Upper-Right if ( FreeTile(x=BestNode->x+TILESIZE, y=BestNode->y-TILESIZE) ) GenerateSucc(BestNode,x,y,dx,dy); // Right if ( FreeTile(x=BestNode->x+TILESIZE, y=BestNode->y) ) GenerateSucc(BestNode,x,y,dx,dy); // Lower-Right if ( FreeTile(x=BestNode->x+TILESIZE, y=BestNode->y+TILESIZE) ) GenerateSucc(BestNode,x,y,dx,dy); // Lower if ( FreeTile(x=BestNode->x, y=BestNode->y+TILESIZE) ) GenerateSucc(BestNode,x,y,dx,dy); // Lower-Left if ( FreeTile(x=BestNode->x-TILESIZE, y=BestNode->y+TILESIZE) ) GenerateSucc(BestNode,x,y,dx,dy); // Left if ( FreeTile(x=BestNode->x-TILESIZE, y=BestNode->y) ) GenerateSucc(BestNode,x,y,dx,dy); }
////////////////////////////////////////////////////////////////////////////////
void AstarPathfinder::GenerateSucc(NODE *BestNode,int x, int y, int dx, int dy) { int g, TileNumS, c = 0; NODE *Old, *Successor;
g = BestNode->g+1; // g(Successor)=g(BestNode)+cost of getting from BestNode to Successor TileNumS = TileNum(x,y); // identification purposes
if ( (Old=CheckOPEN(TileNumS)) != NULL ) // if equal to NULL then not in OPEN list, else it returns the Node in Old { for( c = 0; c < 8; c++) if( BestNode->Child[c] == NULL ) // Add Old to the list of BestNode's Children (or Successors). break; BestNode->Child[c] = Old;
if ( g < Old->g ) // if our new g value is < Old's then reset Old's parent to point to BestNode { Old->Parent = BestNode; Old->g = g; Old->f = g + Old->h; } } else if ( (Old=CheckCLOSED(TileNumS)) != NULL ) // if equal to NULL then not in OPEN list, else it returns the Node in Old { for( c = 0; c< 8; c++) if ( BestNode->Child[c] == NULL ) // Add Old to the list of BestNode's Children (or Successors). break; BestNode->Child[c] = Old;
if ( g < Old->g ) // if our new g value is < Old's then reset Old's parent to point to BestNode { Old->Parent = BestNode; Old->g = g; Old->f = g + Old->h; PropagateDown(Old); // Since we changed the g value of Old, we need // to propagate this new value downwards, i.e. // do a Depth-First traversal of the tree! } } else { Successor = ( NODE* )calloc(1,sizeof( NODE )); Successor->Parent = BestNode; Successor->g = g; Successor->h = (x-dx)*(x-dx) + (y-dy)*(y-dy); // should do sqrt(), but since we don't really Successor->f = g+Successor->h; // care about the distance but just which branch looks Successor->x = x; // better this should suffice. Anyayz it's faster. Successor->y = y; Successor->NodeNum = TileNumS; Insert(Successor); // Insert Successor on OPEN list wrt f for( c =0; c < 8; c++) if ( BestNode->Child[c] == NULL ) // Add Old to the list of BestNode's Children (or Successors). break; BestNode->Child[c] = Successor; } }
////////////////////////////////////////////////////////////////////////////////
AstarPathfinder::NODE *AstarPathfinder::CheckOPEN(int tilenum) { NODE *tmp;
tmp = OPEN->NextNode; while ( tmp != NULL ) { if ( tmp->NodeNum == tilenum ) return (tmp); else tmp = tmp->NextNode; } return(NULL); }
////////////////////////////////////////////////////////////////////////////////
AstarPathfinder::NODE *AstarPathfinder::CheckCLOSED(int tilenum) { NODE *tmp;
tmp = CLOSED->NextNode;
while ( tmp != NULL ) { if ( tmp->NodeNum == tilenum ) return(tmp); else tmp = tmp->NextNode; } return(NULL); }
////////////////////////////////////////////////////////////////////////////////
void AstarPathfinder::Insert(NODE *Successor) { NODE *tmp1, *tmp2; int f;
if ( OPEN->NextNode == NULL ) { OPEN->NextNode = Successor; return; }
// insert into OPEN successor wrt f f = Successor->f; tmp1 = OPEN; tmp2 = OPEN->NextNode;
while ( (tmp2 != NULL) && (tmp2->f < f) ) { tmp1 = tmp2; tmp2 = tmp2->NextNode; }
Successor->NextNode = tmp2; tmp1->NextNode = Successor; }
////////////////////////////////////////////////////////////////////////////////
void AstarPathfinder::PropagateDown(NODE *Old) { int c, g; NODE *Child, *Father;
g = Old->g; // alias. for ( c = 0; c < 8; c++) { if ( (Child=Old->Child[c]) == NULL ) // create alias for faster access. break; if ( g+1 < Child->g) { Child->g = g+1; Child->f = Child->g + Child->h; Child->Parent = Old; // reset parent to new path. Push(Child); // Now the Child's branch need to be } // checked out. Remember the new cost must be propagated down. }
while ( Stack->NextStackPtr != NULL ) { Father = Pop(); for (c = 0; c<8; c++) { if ( (Child=Father->Child[c]) == NULL ) // we may stop the propagation 2 ways: either break; if ( Father->g+1 < Child->g ) // there are no children, or that the g value of { // the child is equal or better than the cost we're propagating Child->g = Father->g+1; Child->f = Child->g+Child->h; Child->Parent = Father; Push(Child); } } } }
//////////////////////////////////////////////////////////////////////////////// // STACK FUNCTIONS // ////////////////////////////////////////////////////////////////////////////////
void AstarPathfinder::Push(NODE *Node) { STACK *tmp;
tmp =( STACK* )calloc(1,sizeof( STACK )); tmp->NodePtr = Node; tmp->NextStackPtr = Stack->NextStackPtr; Stack->NextStackPtr = tmp; }
////////////////////////////////////////////////////////////////////////////////
AstarPathfinder::NODE *AstarPathfinder::Pop(void) { NODE *tmp; STACK *tmpSTK;
tmpSTK = Stack->NextStackPtr; tmp = tmpSTK->NodePtr;
Stack->NextStackPtr = tmpSTK->NextStackPtr; free(tmpSTK); return(tmp); }
/* void AstarPathfinder::ChangeAstarTileMap(MAPBLOCK *pMap,int clearx,int cleary,int disablex,int disabley) { TileMap[clearx + cleary*COLS] = 1; // free node TileMap[disablex + disabley*COLS] = 0; // obstacle node } */ ...
Here is all i can do
PHP Code:
#include <amxmodx> #include <fakemeta>
#define PLUGIN "A-Star" #define VERSION "1.0" #define AUTHOR "Dias"
#define SHIFT 6 // change this to reflect the the size. // Ex. 64x64 tile equals 2^6. or a shift of 6 #define TILESIZE 1 // change this also to reflect tile size. 64x64.
new ROWS // tilemap data members, need to be initialisize new COLS // with current map's width and height new TOTAL_TILES // to allocate memory for the
new NODE[7] new NODE_PARENT, NODE_CHILD[8], NODE_NEXTNODE new TileMap[64]
enum { NODE_F = 0, NODE_H, NODE_G, NODE_TMPG, NODE_X, NODE_Y, NODE_NODENUM }
public plugin_init() { register_plugin(PLUGIN, VERSION, AUTHOR) }
stock TileNum(x, y) { if(x < 0 || x >= COLS || y < 0 || y >= ROWS) return 0 return (y * COLS + x) // The reason I add COLS+1 to // tile number is because I want the tile number to start at the 2nd // the column and the 2nd row. Because if we do this we don't have to have // a special case to test if at a boundary. In the function BoundaryTiles // I place 1's around the boundary, in this way when I call the function // FreeTile() it returns false because we can't go there. }
stock FreeTile(x, y) { // returns 1 if tile is free(nothing on it). // Note: if TileMap[equation]==0 it means free so just !(not) it. if (x < 0 || x >= COLS || y < 0 || y >= ROWS) return 0; if (TileMap[y * COLS + x] != 1) // if 0, means cannot be reached . if 2, have another return 0 else return 1 // return(TileMap[y*COLS + x]); }
|