// INT_VEC is a vector (in the geometry sense) with two properties:// INT_VEC.x --> Integer// INT_VEC.y --> Integervector<INT_VEC> GAME_MAP::Pathfind(INT_VEC start, INT_VEC finish) { // Pathfinding using the A* algorithm and the // "Diagonal" heuristic. Thanks to the following: // -- http://www.policyalmanac.org/games/aStarTutorial.htm // -- http://theory.stanford.edu/%7Eamitp/GameProgramming/Heuristics.html // NOT COMPLETE: // this will possibly go into endless loop if the finish can't be reached! // used to symbolise A* states const int OPEN = 1; const int SEARCH = 0; const int CLOSED = -1; // used to return the result vector<INT_VEC> Result; // used to traverse the map INT_VEC cPoint; map< int, map<int, int> > List; map< int, map<int, INT_VEC> > Parent; // used to find the lowest "F" value. double lowF; int lowX, lowY; // clear the List. -1 is closed, 1 is open, 0 is neither for (int i = 0; i < Width; ++i) for (int j = 0; j < Height; ++j) { List[i][j] = SEARCH; } // add starting point to OPEN LIST cPoint = start; List[cPoint.x][cPoint.y] = OPEN; // add any valid points around to OPEN LIST with starting point as PARENT for (int i = cPoint.x - 1; i <= cPoint.x + 1; ++i) for (int j = cPoint.y - 1; j <= cPoint.y + 1; ++j) { if (i >= 0 && j >= 0 && i < Width && j < Height && Tiles[i][j].Passable) { List[i][j] = OPEN; Parent[i][j] = cPoint; } } // switch starting point to CLOSED LIST List[cPoint.x][cPoint.y] = CLOSED; // once finishing point is in CLOSED LIST, stop while (List[finish.x][finish.y] != CLOSED) { // find lowest F value in OPEN LIST, F = (G) + (H) lowF = -1.0; for (int i = 0; i < Width; ++i) for (int j = 0; j < Height; ++j) { if (List[i][j] == OPEN) { double tempF = (Tiles[i][j].Movement) + (0.5 * max(abs(i-finish.x), abs(j-finish.y))); if ((lowF > tempF || lowF < 0.0)) { lowF = tempF; lowX = i; lowY = j; } } } // we will use this point from now on cPoint.x = lowX; cPoint.y = lowY; // add any valid points around to OPEN LIST with this as PARENT, // as long as they aren't already OPEN or CLOSED. for (int i = cPoint.x - 1; i <= cPoint.x + 1; ++i) for (int j = cPoint.y - 1; j <= cPoint.y + 1; ++j) { if (i >= 0 && j >= 0 && i < Width && j < Height && Tiles[i][j].Passable && List[i][j] == SEARCH) { List[i][j] = OPEN; if (i != cPoint.x || j != cPoint.y) Parent[i][j] = cPoint; } } // switch this point to CLOSED LIST List[cPoint.x][cPoint.y] = CLOSED; } // trace back parents and add to result vector cPoint = finish; Result.push_back(cPoint); while (cPoint.x != start.x || cPoint.y != start.y) { Result.push_back(Parent[cPoint.x][cPoint.y]); cPoint = Parent[cPoint.x][cPoint.y]; } // return the reverse std::reverse(Result.begin(), Result.end()); return Result;}