rendered paste bodytypedef struct ListInfo{ int x; int y; int cost; int startCost;}ListInfoType;typedef struct PointType{ int x; int y;}Point;//Constructor of PathFind classPathFind::PathFind(){ OpenList = ListInit(); OpenP = ListAnchor(OpenList); CloseList = ListInit(); CloseP = ListAnchor(CloseList); Path = ListInit(); PathP = ListAnchor(Path);}//Get points Costint PathFind::GetPointCost(int x, int y, Map *map){ //Block not passable if(map->GetMapBlockStatus(x, y) != PASSABLE) return -1; else return 1;}//Find Path using A* algorithmint PathFind::CreatePath(int srcX, int srcY, int dstX, int dstY, Map *map){ if((dstX == srcX) && (dstY == srcY)) //reached the target return -1; if(((srcX + dstX) / 2) > (WSCREEN / BLOCKW)) //cant move beyond screen o.O return -1; if(((srcY + dstY) / 2) > (HSCREEN / BLOCKH)) //cant move beyond screen 0.0 return -1; //Clear the lists ListClear(&OpenList); ListClear(&CloseList); ListClear(&Path); int pCost; int pStartCost; int pEndCost; int i, j; bool found = false; ListInfoType ParentPoint; ListInfoType CurrentPoint; int minCost; PosType minP; bool minFound; //start point ParentPoint.x = srcX; ParentPoint.y = srcY; ParentPoint.cost = 1; ParentPoint.startCost = 0; //add start point to open list ListInsert(&OpenList, OpenP, ParentPoint); OpenP = ListNext(OpenList, OpenP); while((ListIsEmpty(OpenList) == 0) && (found == false)) { //add parent point to close list ListInsert(&CloseList, CloseP, ParentPoint); CloseP = ListNext(CloseList, CloseP); //remove parent point from open list ListDelete(&OpenList, &OpenP); OpenP = ListAnchor(OpenList); //retrieve parent point ListRetrieve(CloseList, CloseP, &ParentPoint); if((ParentPoint.x == dstX) && (ParentPoint.y == dstY)) { found = true; break; } //add closest points to open list for(j = -1; j <= 1; j++) { for(i = -1; i <= 1; i++) { //skip if we checking the same point we start from if((i == 0) && (j == 0)) continue; CurrentPoint.x = ParentPoint.x + i; CurrentPoint.y = ParentPoint.y + j; //skip if point bigger or smaller then map if((CurrentPoint.x > map->GetMapWidth()) || (CurrentPoint.x < 0)) continue; if((CurrentPoint.y > map->GetMapHeight()) || (CurrentPoint.y < 0)) continue; pCost = GetPointCost(CurrentPoint.x, CurrentPoint.y, map); if(pCost == -1) continue; pStartCost = ParentPoint.startCost + pCost; pEndCost = (int)sqrt(((dstX - srcX) + (dstY - srcY)) * ((dstX - srcX) + (dstY - srcY))); CurrentPoint.cost = pCost + pStartCost + pEndCost; CurrentPoint.startCost = pStartCost; //if all ok add the point to open list ListInsert(&OpenList, OpenP, CurrentPoint); } } //Search for minimun cost point minFound = false; OpenP = ListAnchor(OpenList); OpenP = ListNext(OpenList, OpenP); minP = OpenP; ListRetrieve(OpenList, OpenP, &CurrentPoint); minCost = CurrentPoint.cost; OpenP = ListNext(OpenList, OpenP); while((OpenP != ListEnd(OpenList)) && (minFound == false)) { ListRetrieve(OpenList, OpenP, &CurrentPoint); if((CurrentPoint.x == dstX) && (CurrentPoint.y == dstY)) { minP = OpenP; minFound = true; break; } if(CurrentPoint.cost < minCost) { minP = OpenP; minCost = CurrentPoint.cost; } OpenP = ListNext(OpenList, OpenP); } ListRetrieve(OpenList, minP, &CurrentPoint); ParentPoint = CurrentPoint; OpenP = minP; } // At this Point we suppose to have a full // path form source to destanation points // If we dont have it we in problems :) // Correct the path: Take the last coordinate // from close list and add it to Path list CloseP = ListPrev(CloseList, ListEnd(CloseList)); while(CloseP != ListAnchor(CloseList)) { ListRetrieve(CloseList, CloseP, &CurrentPoint); ListInsert(&Path, PathP, CurrentPoint); PathP = ListAnchor(Path); CloseP = ListPrev(CloseList, CloseP); } return 0;}//Get stepPoint PathFind::GetStep(){ PathP = ListNext(Path, ListAnchor(Path)); ListInfoType inf; Point p; if(PathP != ListEnd(Path)) { if(ListIsEmpty(Path) == 0) { ListRetrieve(Path, PathP, &inf); p.x = inf.x; p.y = inf.y; ListDelete(&Path, &PathP); } else { p.x = -1; p.y = -1; } } else { p.x = -1; p.y = -1; } return p;}