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