Hello Steve:
Here are C++ code fragments for A* using Visual C++ 2.2. I apologize for
any spacing problems - my text editor seemed to chew up the source.
The code works, but it is slow on large maps with varying terrain. As far
as I know, the implementation of the algorithm is fine, so there must be
something else wrong (or else it's just slow in Windows). I have since
optimized this code a lot, but I'd like to see if anyone else can find ways
to optimize it. I'd also like to know how to make the paths straight. I have
some ideas, but I haven't had time to try them. Once I've compiled
feedback from others and finished my own optimizing, I will post a much
nicer set of code. I don't have time to explain the algorithm or its variables,
f, g, and h, but perhaps I or someone else will do that later.
Note: I ported the algorithm from someone's C source off of the net. The
file was called spath.zip - thanks to the author.
.h code fragments
=================
struct NODE {
long f,h;
UINT g,tmpg;
int x,y;
//int NodeNum;
CPoint NodeElement;
struct NODE *Parent;
struct NODE *Child[8]; /* a node may have upto 8+(NULL) children. */
struct NODE *NextNode; /* for filing purposes */
};
struct STACK {
struct NODE *NodePtr;
struct STACK *NextStackPtr;
};
// Algorithm stuff
struct NODE *OPEN;
struct NODE *CLOSED;
struct STACK *Stack;
// Algorithm stuff
BOOL FreeTile(int x, int y);
struct NODE* FindPath(int sx, int sy, int dx, int dy);
struct NODE* ReturnBestNode(void);
void GenerateSuccessors(struct NODE *BestNode, int dx, int dy);
void GenerateSucc(struct NODE *BestNode, int x, int y, int dx, int dy);
struct NODE *CheckOPEN(int x, int y);
struct NODE *CheckCLOSED(int x, int y);
void Insert(struct NODE *Successor);
void PropagateDown(struct NODE *Old);
void Push(struct NODE *Node);
struct NODE *Pop(void);
.cpp code fragments
===================
void Path::DefinePath(int x1, int y1, int x2, int y2)
{
struct NODE *path, *Node;
CApp* pApp = (CApp*) AfxGetApp();
MainMap* pMainMap = (MainMap*) pApp->GetMainMap();
path=(struct NODE *)FindPath(x1, y1, x2, y2);
// Draw the path on the main map
while (path->Parent != NULL)
{
path=path->Parent;
CPoint point(path->x, path->y);
Location* pLoc = pMainMap->GetLocation(point);
((MainMapLocation*)(pLoc))->m_bPath = TRUE;
}
// Free Nodes up
Node=OPEN->NextNode;
while (Node != NULL)
{
free(Node);
Node=Node->NextNode;
}
Node=CLOSED->NextNode;
while (Node != NULL)
{
free(Node);
Node=Node->NextNode;
}
}
/////////////////////////////////////////////////////////////////////////
// Algorithm to find shortest path (A*)
/////////////////////////////////////////////////////////////////////////
BOOL Path::FreeTile(int x, int y) // returns 1 if tile is free(nothing on it).
{
CPoint point(x, y);
// Check for points off of the map.
if (x < 0 || x >= m_pMap->GetWidth() || y < 0 || y >= m_pMap->GetHeight())
return (0);
Location* pLoc = m_pMap->GetLocation(point);
return (1);
// Check if this location's terrain is impassable to this army.
// ISPassable(pLoc->GetTerrain());
}
// A* Algorithm
struct NODE* Path::FindPath(int sx, int sy, int dx, int dy)
{
lPropagateDown=lPropLoop=lGenerateSuccessors=lGenerateSucc=lCheckOpen=lOpenLoop = 0;
lCheckClosed=lClosedLoop=lInsert=lInsertLoop=lPush=lPop=lReturnBestNode = 0;
struct NODE *Node, *BestNode;
CApp* pApp = (CApp*) AfxGetApp();
UINT deltaX, deltaY;
m_pMap = pApp->GetActiveMap();
OPEN=(struct NODE *)calloc(1,sizeof( struct NODE ));
CLOSED=(struct NODE *)calloc(1,sizeof( struct NODE ));
// Setup the Stack.
Stack=( struct STACK *)calloc(1,sizeof(struct STACK));
Node=(struct NODE *)calloc(1,sizeof( struct NODE ));
Node->g = 0;
deltaX = abs(sx-dx);
deltaY = abs(sy-dy);
Node->h = MAX(deltaX, deltaY);
Node->f = Node->g + Node->h;
Node->x = sx;
Node->y = sy;
OPEN->NextNode = Node; // make Open List point to first node
for (;;)
{
BestNode = (struct NODE *)ReturnBestNode();
// if we've found the end, break and finish
if (BestNode->x == dx && BestNode->y == dy)
break;
GenerateSuccessors(BestNode, dx, dy);
}
return (BestNode);
}
struct NODE* Path::ReturnBestNode(void)
{
lReturnBestNode += 1;
struct NODE *tmp;
if (OPEN->NextNode == NULL)
{
AfxMessageBox("ERROR: no more nodes on OPEN\n");
//RestoreKeyboard(); // restore BIOS keyboard handling
//closegraph();
//exit(0);
ASSERT(FALSE);
return NULL;
}
// 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 Path::GenerateSuccessors(struct NODE *BestNode, int dx, int dy)
{
lGenerateSuccessors += 1;
int x, y;
// Upper-Left
if (FreeTile(x = BestNode->x - 1, y = BestNode->y - 1))
GenerateSucc(BestNode, x, y, dx, dy);
// Upper
if (FreeTile(x = BestNode->x, y = BestNode->y - 1))
GenerateSucc(BestNode, x, y, dx, dy);
// Upper-Right
if (FreeTile(x = BestNode->x + 1, y = BestNode->y - 1))
GenerateSucc(BestNode, x, y, dx, dy);
// Right
if (FreeTile(x = BestNode->x + 1, y = BestNode->y))
GenerateSucc(BestNode, x, y, dx, dy);
// Lower-Right
if (FreeTile(x = BestNode->x + 1, y = BestNode->y + 1))
GenerateSucc(BestNode, x, y, dx, dy);
// Lower
if (FreeTile(x = BestNode->x , y = BestNode->y + 1))
GenerateSucc(BestNode, x, y, dx, dy);
// Lower-Left
if (FreeTile(x = BestNode->x - 1, y = BestNode->y + 1))
GenerateSucc(BestNode, x, y, dx, dy);
// Left
if (FreeTile(x = BestNode->x - 1, y = BestNode->y))
GenerateSucc(BestNode, x, y, dx, dy);
}
void Path::GenerateSucc(struct NODE *BestNode, int x, int y, int dx, int dy)
{
lGenerateSucc += 1;
UINT g; // total path cost - as stored in the linked lists.
int c = 0;
UINT nTerrainCost; // Movement cost of this terrain.
UINT deltaX, deltaY;
struct NODE *Old, *Successor;
// g(Successor)=g(BestNode)+cost of getting from BestNode to Successor
nTerrainCost = m_nMovementPenalty[m_pMap->GetLocation(x, y)->GetTerrainType()];
g = BestNode->g + nTerrainCost;
if ((Old = CheckOPEN(x, y)) != 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(x, y)) != 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 = (struct NODE *) calloc(1,sizeof( struct NODE ));
Successor->Parent = BestNode;
Successor->g = g;
deltaX = abs(x-dx);
deltaY = abs(y-dy);
Successor->h = MAX(deltaX, deltaY);
Successor->f = g + Successor->h;
Successor->x = x;
Successor->y = y;
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;
}
}
struct NODE* Path::CheckOPEN(int x, int y)
{
lCheckOpen += 1;
struct NODE *tmp;
tmp = OPEN->NextNode;
while (tmp != NULL)
{
lOpenLoop += 1;
if (tmp->x == x && tmp->y == y)
return (tmp);
else
tmp = tmp->NextNode;
}
return (NULL);
}
struct NODE* Path::CheckCLOSED(int x, int y)
{
lCheckClosed += 1;
struct NODE *tmp;
tmp = CLOSED->NextNode;
while (tmp != NULL)
{
lClosedLoop += 1;
if (tmp->x == x && tmp->y == y)
return (tmp);
else
tmp = tmp->NextNode;
}
return (NULL);
}
void Path::Insert(struct NODE *Successor)
{
lInsert += 1;
struct NODE *tmp1, *tmp2;
long 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))
{
lInsertLoop += 1;
tmp1 = tmp2;
tmp2 = tmp2->NextNode;
}
Successor->NextNode = tmp2;
tmp1->NextNode = Successor;
}
void Path::PropagateDown(struct NODE *Old)
{
lPropagateDown += 1;
int c;
UINT g;
UINT nTerrainCost;
struct NODE *Child, *Father;
g = Old->g; // alias.
for(c = 0; c < 8; c++)
{
Child = Old->Child[c]; // Create alias for faster access.
if (Child == NULL)
break;
nTerrainCost = m_nMovementPenalty[m_pMap->GetLocation(Child->x, Child->y)->GetTerrainType()];
if (g + nTerrainCost < Child->g)
{
Child->g = g + nTerrainCost;
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)
{
lPropLoop += 1;
Father = Pop();
for(c = 0; c < 8; c++)
{
Child = Father->Child[c];
if (Child == NULL) // we may stop the propagation 2 ways: either
break;
nTerrainCost = m_nMovementPenalty[m_pMap->GetLocation(Child->x, Child->y)->GetTerrainType()];
if (Father->g + nTerrainCost < 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 + nTerrainCost;
Child->f = Child->g + Child->h;
Child->Parent = Father;
Push(Child);
}
}
}
}
///////////////////////////////////////////////////////////////////////////
// STACK Functions
///////////////////////////////////////////////////////////////////////////
void Path::Push(struct NODE *Node)
{
lPush += 1;
struct STACK *tmp;
//tmp = (struct STACK *) calloc(1,sizeof(struct STACK));
tmp = (struct STACK *) malloc(sizeof(struct STACK));
if (!tmp)
ASSERT(FALSE);
tmp->NodePtr = Node;
tmp->NextStackPtr = Stack->NextStackPtr;
Stack->NextStackPtr = tmp;
}
struct NODE* Path::Pop()
{
lPop += 1;
struct NODE *tmp;
struct STACK *tmpSTK;
tmpSTK = Stack->NextStackPtr;
tmp = tmpSTK->NodePtr;
Stack->NextStackPtr = tmpSTK->NextStackPtr;
free(tmpSTK);
return (tmp);
}