AlliedModders

AlliedModders (https://forums.alliedmods.net/index.php)
-   Scripting Help (https://forums.alliedmods.net/forumdisplay.php?f=11)
-   -   [C++ -> AMXX] A* Pathfinder (https://forums.alliedmods.net/showthread.php?t=197121)

dias 09-29-2012 04:23

[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 fh;
               
int gtmpg;
            
int xy;
            
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 pMapint w,int h);                
        
BOOL NewPath(int sxint syint &dxint &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 xint y); // returns tilenum
        
int FreeTile(int xint y); // returns 1 = true if we can move on it

    
private:
        
// The A* Algorithm and it's stuff
        
int  FindPath(int sxint syint dxint dy);
        
void FreeNodes(void);// frees lists memory
        
void GenerateSuccessors(NODE *BestNodeint dxint dy);
        
void GenerateSucc(NODE *BestNode,int xint yint dxint 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,sizeofSTACK ));
   
isPath FALSE;
   
OPEN NULL;
   
CLOSED NULL;
   
PATH NULL;
}

////////////////////////////////////////////////////////////////////////////////

AstarPathfinder::~AstarPathfinder()
{
   
FreeNodes();
   
free(Stack);
   if ( 
TileMap delete [] TileMap;
}

//////////////////////////////////////////////////////////////////////
//                   Public Member Functions                        //
//////////////////////////////////////////////////////////////////////

void AstarPathfinder::InitAstarTileMap(MAPBLOCK *pMapint 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 0ROWSi++)       // fill up the area with current map data
       
{                                      // 1 = obstacle
           
for (int j 0COLSj++)    // 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 syint &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 xint y)
{
    
    if (
x<|| x>=COLS || y<|| 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 xint y)
{   
//  returns 1 if tile is free(nothing on it).
    //  Note: if TileMap[equation]==0 it means free so just !(not) it.
    
if (x<|| x>=COLS || y<|| 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 sxint syint dxint dy)
{
   
NODE *Node, *BestNode;
   
int TileNumDest;

   
TileNumDest TileNum(sxsy);

   
OPEN=( NODE* )calloc(1,sizeofNODE ));
   
CLOSED=( NODE* )calloc(1,sizeofNODE ));

   
Node=( NODE* )calloc(1,sizeofNODE ));
   
Node->0;
   
Node->= (dx-sx)*(dx-sx) + (dy-sy)*(dy-sy);  // should really use sqrt().
   
Node->Node->g+Node->h;
   
Node->NodeNum TileNum(dxdy);
   
Node->dx;
   
Node->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 *BestNodeint dxint dy)
{
   
int xy;

            
// Upper-Left
   
if ( FreeTile(x=BestNode->x-TILESIZEy=BestNode->y-TILESIZE) )
      
GenerateSucc(BestNode,x,y,dx,dy);
            
// Upper
   
if ( FreeTile(x=BestNode->xy=BestNode->y-TILESIZE) )
      
GenerateSucc(BestNode,x,y,dx,dy);
            
// Upper-Right
   
if ( FreeTile(x=BestNode->x+TILESIZEy=BestNode->y-TILESIZE) )
      
GenerateSucc(BestNode,x,y,dx,dy);
            
// Right
   
if ( FreeTile(x=BestNode->x+TILESIZEy=BestNode->y) )
      
GenerateSucc(BestNode,x,y,dx,dy);
            
// Lower-Right
   
if ( FreeTile(x=BestNode->x+TILESIZEy=BestNode->y+TILESIZE) )
      
GenerateSucc(BestNode,x,y,dx,dy);
            
// Lower
   
if ( FreeTile(x=BestNode->xy=BestNode->y+TILESIZE) )
      
GenerateSucc(BestNode,x,y,dx,dy);
            
// Lower-Left
   
if ( FreeTile(x=BestNode->x-TILESIZEy=BestNode->y+TILESIZE) )
      
GenerateSucc(BestNode,x,y,dx,dy);
            
// Left
   
if ( FreeTile(x=BestNode->x-TILESIZEy=BestNode->y) )
      
GenerateSucc(BestNode,x,y,dx,dy);
}

////////////////////////////////////////////////////////////////////////////////

void AstarPathfinder::GenerateSucc(NODE *BestNode,int xint yint dxint dy)
{
   
int gTileNumS0;
   
NODE *Old, *Successor;

   
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( 
08c++)
           if( 
BestNode->Child[c] == NULL // Add Old to the list of BestNode's Children (or Successors).
               
break;
        
BestNode->Child[c] = Old;

        if ( 
Old->)  // if our new g value is < Old's then reset Old's parent to point to BestNode
        
{
            
Old->Parent BestNode;
           
Old->g;
           
Old->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( 
0c8c++)
        if ( 
BestNode->Child[c] == NULL // Add Old to the list of BestNode's Children (or Successors).
               
break;
        
BestNode->Child[c] = Old;

        if ( 
Old->)  // if our new g value is < Old's then reset Old's parent to point to BestNode
        
{
               
Old->Parent BestNode;
               
Old->g;
               
Old->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,sizeofNODE ));
        
Successor->Parent BestNode;
        
Successor->g;
        
Successor->= (x-dx)*(x-dx) + (y-dy)*(y-dy);  // should do sqrt(), but since we don't really
        
Successor->g+Successor->h;     // care about the distance but just which branch looks
        
Successor->x;                 // better this should suffice. Anyayz it's faster.
        
Successor->y;
        
Successor->NodeNum TileNumS;
        
Insert(Successor);     // Insert Successor on OPEN list wrt f
        
for( =08c++)
            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
   
Successor->f;
   
tmp1 OPEN;
   
tmp2 OPEN->NextNode;

   while ( (
tmp2 != NULL) && (tmp2->f) )
   {
        
tmp1 tmp2;
       
tmp2 tmp2->NextNode;
   }

   
Successor->NextNode tmp2;
   
tmp1->NextNode Successor;
}

////////////////////////////////////////////////////////////////////////////////

void AstarPathfinder::PropagateDown(NODE *Old)
{
   
int cg;
   
NODE *Child, *Father;

   
Old->g;            // alias.
   
for ( 08c++)
   {
       if ( (
Child=Old->Child[c]) == NULL )   // create alias for faster access.
          
break;
        if ( 
g+Child->g)
        {
            
Child->g+1;
            
Child->Child->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 (
0c<8c++)
        {
           if ( (
Child=Father->Child[c]) == NULL )  // we may stop the propagation 2 ways: either
                  
break;
          if ( 
Father->g+Child->// there are no children, or that the g value of
              
{                          // the child is equal or better than the cost we're propagating
              
Child->Father->g+1;
                
Child->Child->g+Child->h;
                
Child->Parent Father;
                
Push(Child);
          }
       }
   }
}


////////////////////////////////////////////////////////////////////////////////
//                              STACK FUNCTIONS                               //
////////////////////////////////////////////////////////////////////////////////

void AstarPathfinder::Push(NODE *Node)
{
   
STACK *tmp;

   
tmp =( STACK* )calloc(1,sizeofSTACK ));
   
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_PARENTNODE_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(PLUGINVERSIONAUTHOR)
}


stock TileNum(xy)
{
    if(
|| >= COLS || || >= ROWS
        return 
0
        
    
return (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(xy)
{   
//  returns 1 if tile is free(nothing on it).
    //  Note: if TileMap[equation]==0 it means free so just !(not) it.
    
if (|| >= COLS || || >= ROWS
        return 
0;
    if (
TileMap[COLS x] != 1// if 0, means cannot be reached . if 2, have another
        
return 0
    
else 
        return 
1
//    return(TileMap[y*COLS + x]);



claudiuhks 09-29-2012 04:32

Re: [C++ -> AMXX] A* Pathfinder
 
What exactly are you trying to do?

dias 09-29-2012 05:24

Re: [C++ -> AMXX] A* Pathfinder
 
I want to create an NPC, that can find way and move to the Player
The A* PathFinder is the last thing i still can't do


All times are GMT -4. The time now is 08:22.

Powered by vBulletin®
Copyright ©2000 - 2024, vBulletin Solutions, Inc.