ProtoBot
Loading...
Searching...
No Matches
AStar Class Reference

AStar is a static utility class that any manager can call on to use A* pathfinding. It makes use of precaching and caching to optimize pathfinding, as well as some optimizations within the A* algorithm itself (using a priority queue for the open set, using an array for the closed set, etc.). More...

#include <A-StarPathfinding.h>

Static Public Member Functions

static Path GeneratePath (BWAPI::Position _start, BWAPI::UnitType unitType, BWAPI::Position _end, bool isInteractableEndpoint=false)
 Generates path from start to end using A* pathfinding algorithm.
static void drawPath (Path path)
 Draws path on map for debugging. Uses BWAPI::Broodwar->drawLineMap().
static void fillUncachedAreaPairs ()
 Fills UncachedAreaPairs with pairs of areas that are neighbours. All of these pairs will be used to precache paths in fillAreaPathCache().
static void fillAreaPathCache ()
 Loops through all area pairs from UncachedAreaPairs() and stores a path in-between them.
static void clearPathCache ()

Static Private Member Functions

static int TileToIndex (BWAPI::TilePosition tile)
 Used for indexing BWAPI::TilePositions in arrays. Converts a BWAPI::TilePosition to an integer index based on the map width and height. The index is calculated as (tile.y * mapWidth + tile.x).
static bool tileWalkable (BWAPI::UnitType unitType, BWAPI::TilePosition tile, BWAPI::TilePosition end, bool isInteractableEndpoint)
 Using the unit's unit type, checks if the tile is walkable.
This is done by using the unit's dimensions to determine if they would overlap with any structures or terrain if the unit was placed in the tile.
static double squaredDistance (BWAPI::Position pos1, BWAPI::Position pos2)
static double chebyshevDistance (BWAPI::Position pos1, BWAPI::Position pos2)
static double octileDistance (BWAPI::Position pos1, BWAPI::Position pos2)
static Path generateSubPath (BWAPI::Position _start, BWAPI::UnitType unitType, BWAPI::Position _end, bool isInteractableEndpoint=false)
 Almost identital to GeneratePath() except does not check for precache optimizations.
Used for when you want to find the path between two points without shortcuts that may change the returned waypoints.
static Path closestCachedPath (BWAPI::Position start, BWAPI::Position end)
 Loops through the precached paths between areas and chokepoints to find the closest path from start to end. This is used as an optimization for GeneratePath() when the start and end positions are in different areas.

Static Private Attributes

static map< pair< const BWEM::Area::id, const BWEM::Area::id >, const Path > AreaPathCache
static map< pair< const BWEM::ChokePoint *, const BWEM::ChokePoint * >, Path > ChokepointPathCache
static vector< pair< const BWAPI::WalkPosition, const BWAPI::WalkPosition > > UncachedAreaPairs
static vector< pair< const BWAPI::WalkPosition, const BWAPI::WalkPosition > > failedAreaPairs

Detailed Description

AStar is a static utility class that any manager can call on to use A* pathfinding. It makes use of precaching and caching to optimize pathfinding, as well as some optimizations within the A* algorithm itself (using a priority queue for the open set, using an array for the closed set, etc.).

Definition at line 106 of file A-StarPathfinding.h.

Member Function Documentation

◆ chebyshevDistance()

double AStar::chebyshevDistance ( BWAPI::Position pos1,
BWAPI::Position pos2 )
staticprivate

Definition at line 825 of file A-StarPathfinding.cpp.

825 {
826 double val = max(abs(pos2.x - pos1.x), abs(pos2.y - pos1.y));
827 /*if (pos1.x != pos2.x && pos1.y != pos2.y) {
828 return 1.414 * val;
829 }*/
830
831 return val;
832}

◆ clearPathCache()

void AStar::clearPathCache ( )
static

Definition at line 698 of file A-StarPathfinding.cpp.

698 {
699 AreaPathCache.clear();
700 ChokepointPathCache.clear();
701 UncachedAreaPairs.clear();
702}

◆ closestCachedPath()

Path AStar::closestCachedPath ( BWAPI::Position start,
BWAPI::Position end )
staticprivate

Loops through the precached paths between areas and chokepoints to find the closest path from start to end. This is used as an optimization for GeneratePath() when the start and end positions are in different areas.

Parameters
start
end
Returns

Definition at line 705 of file A-StarPathfinding.cpp.

705 {
706 const BWEM::Area* startArea = bwem_map.GetArea(BWAPI::WalkPosition(pos));
707 const BWEM::Area* endArea = bwem_map.GetArea(BWAPI::WalkPosition(goal));
708
709 const vector<const BWEM::Area*> neighbours = startArea->AccessibleNeighbours();
710
711 Path closestPath = Path();
712 int closestDist = INT_MAX;
713 int closestIdx = -1;
714 for (const auto& neighbour : neighbours) {
715 if (neighbour->Id() == endArea->Id()
716 || !AreaPathCache.contains(make_pair(startArea->Id(), neighbour->Id()))
717 || !AreaPathCache.contains(make_pair(neighbour->Id(), startArea->Id()))) {
718 continue;
719 }
720
721 Path precachedPath;
722 if (neighbour->Id() < endArea->Id()) {
723 if (!AreaPathCache.contains(make_pair(neighbour->Id(), startArea->Id()))) {
724 continue;
725 }
726 precachedPath = AreaPathCache[make_pair(neighbour->Id(), endArea->Id())];
727 }
728 else {
729 if (!AreaPathCache.contains(make_pair(startArea->Id(), neighbour->Id()))) {
730 continue;
731 }
732 precachedPath = AreaPathCache[make_pair(endArea->Id(), neighbour->Id())];
733 }
734
735 for (int i = 0; i < precachedPath.positions.size(); i++) {
736 const BWAPI::Position pathPos = precachedPath.positions.at(i);
737 const int dist = pos.getApproxDistance(pathPos);
738 if (dist < closestDist) {
739 closestPath = precachedPath;
740 closestDist = dist;
741 closestIdx = i;
742 }
743 }
744 }
745
746 // Need to chop off part of the closestPath thats not needed
747 vector<BWAPI::Position> finalVec(closestPath.positions.begin() + closestIdx, closestPath.positions.end());
748 int finalDist = 0;
749 for (int i = 0; i < finalVec.size(); i++) {
750 if (i == 0) {
751 continue;
752 }
753 finalDist += finalVec.at(i).getApproxDistance(finalVec.at(i - 1));
754 }
755
756 Path subPath = Path(finalVec, finalDist);
757
758 return subPath;
759}
Path::positions
vector< BWAPI::Position > positions
A vector of BWAPI::Positions representing the waypoints along the path to follow ///<.
Definition A-StarPathfinding.h:68

◆ drawPath()

void AStar::drawPath ( Path path)
static

Draws path on map for debugging. Uses BWAPI::Broodwar->drawLineMap().

Parameters
path

Definition at line 841 of file A-StarPathfinding.cpp.

841 {
842 if (path.positions.size() <= 1) {
843 return;
844 }
845
846 BWAPI::Position prevPos = path.positions.at(0);
847 for (const BWAPI::Position pos : path.positions) {
848 BWAPI::Broodwar->drawLineMap(prevPos, pos, BWAPI::Colors::Yellow);
849 BWAPI::Broodwar->drawCircleMap(pos, 3, BWAPI::Colors::Black, true);
850 prevPos = pos;
851 }
852
853 BWAPI::Broodwar->drawCircleMap(path.positions.at(0), 5, BWAPI::Colors::Green, true);
854 BWAPI::Broodwar->drawCircleMap(path.positions.at(path.positions.size() - 1), 5, BWAPI::Colors::Red, true);
855}

◆ fillAreaPathCache()

void AStar::fillAreaPathCache ( )
static

Loops through all area pairs from UncachedAreaPairs() and stores a path in-between them.

Runs generateSubPath() to generate a Path object for every pair of areas.
The paths are stored in AreaPathCache with the key as the pair of area ids. This pair is stored as (lower id, higher id).

Definition at line 568 of file A-StarPathfinding.cpp.

568 {
569#ifdef DEBUG_PRECACHE
570 Timer pathCacheTimer = Timer();
571 pathCacheTimer.start();
572#endif
573
574 BWAPI::WalkPosition firstPos;
575 BWAPI::WalkPosition secondPos;
576
577 bool tryingFailedPair = false;
578 if (UncachedAreaPairs.empty()) {
579 return;
580 // If empty, try caching the failed pairs
581 /*if (failedAreaPairs.empty()) {
582 return;
583 }
584 else {
585 firstPos = failedAreaPairs.at(failedAreaPairs.size() - 1).first;
586 secondPos = failedAreaPairs.at(failedAreaPairs.size() - 1).second;
587 failedAreaPairs.pop_back();
588 tryingFailedPair = true;
589 }*/
590 }
591 else {
592 firstPos = UncachedAreaPairs.at(UncachedAreaPairs.size() - 1).first;
593 secondPos = UncachedAreaPairs.at(UncachedAreaPairs.size() - 1).second;
594 UncachedAreaPairs.pop_back();
595 }
596
597 const BWEM::Area& area1 = *bwem_map.GetArea(firstPos);
598 const BWEM::Area& area2 = *bwem_map.GetArea(secondPos);
599
600 const vector<const BWEM::ChokePoint*> chokepoints1 = area1.ChokePoints();
601 const vector<const BWEM::ChokePoint*> chokepoints2 = area2.ChokePoints();
602
603 if (chokepoints1.empty() || chokepoints2.empty()) {
604#ifdef DEBUG_PRECACHE
605 cout << "No checkpoints found between areas" << endl;
606#endif
607 return;
608 }
609
610 int closest = INT_MAX;
611 pair<const BWEM::ChokePoint*, const BWEM::ChokePoint*> closestCPPair;
612
613 for (const BWEM::ChokePoint* cp1 : chokepoints1) {
614 if (cp1->Blocked()) {
615 continue;
616 }
617
618 for (const BWEM::ChokePoint* cp2 : chokepoints2) {
619 if (cp2->Blocked()) {
620 continue;
621 }
622
623 const BWAPI::WalkPosition cp1_center = cp1->Center();
624 const BWAPI::WalkPosition cp2_center = cp2->Center();
625
626 const int dist = cp1_center.getApproxDistance(cp2_center);
627 if (dist < closest) {
628 closest = dist;
629 closestCPPair = make_pair(cp1, cp2);
630 }
631 }
632 }
633
634 // Group paths bewteen the shortest path of chokepoints between the chosen chokepoints of both areas
635 const BWEM::CPPath smallestCPPath = bwem_map.GetPath(BWAPI::Position(closestCPPair.first->Center()), BWAPI::Position(closestCPPair.second->Center()));
636
637 vector<BWAPI::Position> finalPositions;
638 int finalDistance = 0;
639
640 if (smallestCPPath.size() > 1) {
641 for (int k = 0; k < smallestCPPath.size() - 1; k++) {
642 const BWEM::ChokePoint* cp1 = smallestCPPath.at(k);
643 const BWEM::ChokePoint* cp2 = smallestCPPath.at(k + 1);
644
645 if (cp1 == nullptr || cp2 == nullptr) {
646 return;
647 }
648
649 // Caches the paths between chokepoints so that other paths between Areas don't generate them again
650 Path subPath;
651 pair<const BWEM::ChokePoint*, const BWEM::ChokePoint*> cpPair = make_pair(cp1, cp2);
652 if (ChokepointPathCache.find(make_pair(cp1, cp2)) != ChokepointPathCache.end()) {
653 subPath = ChokepointPathCache[make_pair(cp1, cp2)];
654 }
655 else {
656 try {
657 subPath = generateSubPath(BWAPI::Position(cp1->Center()), BWAPI::UnitTypes::Protoss_Probe, BWAPI::Position(cp2->Center()));
658 }
659 catch (const runtime_error& e) {
660#ifdef DEBUG_PATH
661 cout << e.what() << endl;
662#endif
663 // Don't add pair to chokepoint path cache
664 continue;
665 }
666 ChokepointPathCache[make_pair(cp1, cp2)] = subPath;
667
668#ifdef DRAW_PRECACHE
669 precachedPositions.insert(precachedPositions.end(), subPath.positions.begin(), subPath.positions.end());
670#endif
671 }
672
673 finalPositions.insert(finalPositions.end(), subPath.positions.begin(), subPath.positions.end());
674 finalDistance += subPath.distance;
675 }
676 }
677
678 pair<const BWEM::Area::id, const BWEM::Area::id> finalPair = make_pair(area1.Id(), area2.Id());
679 if (finalPositions.size() > 1) {
680 const Path finalPath = Path(finalPositions, finalDistance);
681 AreaPathCache.insert(make_pair(finalPair, finalPath));
682 }
683 else {
684 if (!tryingFailedPair) {
685 failedAreaPairs.push_back(make_pair(firstPos, secondPos));
686 }
687#ifdef DEBUG_PRECACHE
688 cout << "Failed precache stored" << endl;
689#endif
690 }
691
692#ifdef DEBUG_PRECACHE
693 pathCacheTimer.stop();
694 cout << "Time spent precaching path of size (" << finalPositions.size() << "): " << pathCacheTimer.getElapsedTimeInMilliSec() << endl;
695#endif
696}
AStar::generateSubPath
static Path generateSubPath(BWAPI::Position _start, BWAPI::UnitType unitType, BWAPI::Position _end, bool isInteractableEndpoint=false)
Almost identital to GeneratePath() except does not check for precache optimizations....
Definition A-StarPathfinding.cpp:345
Path::distance
int distance
The total distance of the path, calculated as the sum of the distances between each waypoint ///<.
Definition A-StarPathfinding.h:69

◆ fillUncachedAreaPairs()

void AStar::fillUncachedAreaPairs ( )
static

Fills UncachedAreaPairs with pairs of areas that are neighbours. All of these pairs will be used to precache paths in fillAreaPathCache().

Stores all pairs of areas on the map by looping through all pairs of areas and checking if they are accessible neighbours. If so, adds the pair to UncachedAreaPairs vector.
This is kept in a separate function in order to load the structure at the start of the game.

The starting frame of the game is not confined to SSCAIT time limits, so we can afford to do some preprocessing before the game starts.

Definition at line 541 of file A-StarPathfinding.cpp.

541 {
542 const vector<BWEM::Area>& areas = bwem_map.Areas();
543 for (int i = 0; i < areas.size(); i++) {
544 for (int j = i + 1; j < areas.size(); j++) {
545 // Have to do this to since bwem_map.Areas() doesn't return pointers so you can't make pairs of pointers with them
546 const BWEM::Area& area1 = *bwem_map.GetArea(BWAPI::WalkPosition(areas.at(i).Top()));
547 const BWEM::Area& area2 = *bwem_map.GetArea(BWAPI::WalkPosition(areas.at(j).Top()));
548
549 // Avoid areas that cannot reach each other or areas that are already next to each other
550 const vector<const BWEM::Area*> neighbours = area1.AccessibleNeighbours();
551 if (!area1.AccessibleFrom(&area2) || find(neighbours.begin(), neighbours.end(), &area2) != neighbours.end()) {
552 continue;
553 }
554
555 // pair isn't working with const BWEM::Area& for some reason so switching to walkpositions so you can get area from bwem_map.GetArea(wp)
556 if (area1.Id() < area2.Id()) {
557 pair<const BWAPI::WalkPosition, const BWAPI::WalkPosition> areaPair = make_pair(area1.Top(), area2.Top());
558 UncachedAreaPairs.push_back(areaPair);
559 }
560 else {
561 pair<const BWAPI::WalkPosition, const BWAPI::WalkPosition> areaPair = make_pair(area2.Top(), area1.Top());
562 UncachedAreaPairs.push_back(areaPair);
563 }
564 }
565 }
566}

◆ GeneratePath()

Path AStar::GeneratePath ( BWAPI::Position _start,
BWAPI::UnitType unitType,
BWAPI::Position _end,
bool isInteractableEndpoint = false )
static

Generates path from start to end using A* pathfinding algorithm.

IF YOU WANT A PATH TO AN INTERACTABLE UNIT (Constructing a geyser, mining minerals, etc.), SET isInteractableEndpoint AS TRUE

Using the A* algorithm, this function steps through BWAPI::TilePositions on the map to find an optimal path to the target position.
This A* algorithm makes use of the precached paths between areas and chokepoints to optimize pathfinding.
If the start and end positions are in different areas, it will first find the path between the areas using the cached paths, then generate subpaths between the chokepoints in the area path, and finally generate subpaths from the start position to the first chokepoint and from the last chokepoint to the end position.

Heuristic: BWAPI's getApproxDistance() multiplied by a heuristic weight. This is because BWAPI's getApproxDistance() is optimized and runs in O(1) time, so we can afford to use it as a heuristic even if it sacrifices some accuracy.

Walkability: Checks tile walkability using tileWalkable() function. This function uses the unitType to get the unit's size and checks if any objects on the tile will collide with the unit.

Parameters
_start
unitType
_end
isInteractableEndpoint
Returns

Definition at line 21 of file A-StarPathfinding.cpp.

21 {
22 Timer totalTimer = Timer();
23 totalTimer.start();
24#ifdef DEBUG_PATH
25 rectCoordinates.clear();
26 closedTiles.clear();
27 earlyExpansionTiles.clear();
28#endif
29
30 vector<BWAPI::Position> positions = vector<BWAPI::Position>();
31 int finalDistance = 0;
32 // Checks if either the starting or ending tile positions are invalid
33 // If so, returns early with no positions added to the path
34 if (!_start.isValid() || !_end.isValid()) {
35 cout << "ERROR: Starting point or ending point not valid" << endl;
36 return Path();
37 }
38
39 // Flying units can move directly to the end position without pathfinding
40 if (unitType.isFlyer()) {
41 positions.push_back(_end);
42 finalDistance = _start.getApproxDistance(_end);
43 return Path(positions, finalDistance);
44 }
45
46 BWAPI::TilePosition start = BWAPI::TilePosition(_start);
47 const BWAPI::TilePosition end = BWAPI::TilePosition(_end);
48
49 // Optimization using priority_queue for open set
50 // The priority_queue will always have the node with the lowest fCost at the top
51 // No need for O(N) lookup time :)
52 priority_queue<Node, vector<Node>, greater<Node>> openSet;
53
54 unordered_set<BWAPI::TilePosition, TilePositionHash> openSetNodes;
55
56 // Optimization using array for closed set
57 // O(1) lookup time :)
58 const int mapWidth = BWAPI::Broodwar->mapWidth();
59 const int mapHeight = BWAPI::Broodwar->mapHeight();
60 vector<bool> closedSet(mapWidth * mapHeight, false); // Default: no closed positions
61 vector<int> gCostMap(mapWidth * mapHeight, INT_MAX); // Default: all gCosts are as large as possible
62
63 // Store parents in an unordered_map for reconstructing path later
64 unordered_map<int, BWAPI::TilePosition> parent;
65
66 // Very first node to be added is the starting tile position
67 Node firstNode = Node(start, start, 0, 0, 0);
68 openSet.push(firstNode);
69 openSetNodes.insert(start);
70 gCostMap[TileToIndex(start)] = 0;
71 Node currentNode = Node();
72
73 bool earlyExpansion = false;
74 while (openSet.size() > 0) {
75 // Time limit for path generations
76 if (TIME_LIMIT_ENABLED && totalTimer.getElapsedTimeInMilliSec() > TIME_LIMIT_MS) {
77#ifdef DEBUG_PATH
78 cout << "TIME LIMIT EXCEEDED in main path: " << totalTimer.getElapsedTimeInMilliSec() << endl;
79#endif
80 totalTimer.stop();
81 return Path();
82 }
83
84 if (!earlyExpansion) {
85 currentNode = openSet.top();
86 openSet.pop();
87 openSetNodes.erase(currentNode.tile);
88 }
89 closedSet[TileToIndex(currentNode.tile)] = true;
90 closedTiles.push_back(std::make_pair(currentNode.tile, currentNode.fCost));
91
92 // Check if path is finishedx
93 if (currentNode.tile == end) {
94 BWAPI::Position prevPos = BWAPI::Position(currentNode.tile);
95 BWAPI::Position dir;
96 BWAPI::Position currentWaypoint;
97 BWAPI::Position prevWaypoint;
98
99 while (currentNode.tile != start) {
100 if (isInteractableEndpoint && currentNode.tile == end) {
101 positions.push_back(BWAPI::Position(currentNode.tile));
102 }
103 else {
104 positions.push_back(BWAPI::Position(currentNode.tile) + BWAPI::Position(16, 16));
105 }
106 currentNode.tile = parent[TileToIndex(currentNode.tile)];
107 const BWAPI::Position currentPos = BWAPI::Position(currentNode.tile);
108
109 if (positions.size() == 2) {
110 dir = positions.at(1) - positions.at(0);
111 finalDistance += positions.at(1).getApproxDistance(positions.at(0));
112 }
113 else if (positions.size() > 2) {
114 BWAPI::Position currentWaypoint = positions.at(positions.size() - 1);
115 BWAPI::Position prevWaypoint = positions.at(positions.size() - 2);
116 const BWAPI::Position newDir = currentWaypoint - prevWaypoint;
117 const double currentDistance = currentWaypoint.getApproxDistance(prevWaypoint);
118
119 if (dir == newDir) {
120 finalDistance += currentWaypoint.getApproxDistance(positions.at(positions.size() - 3));
121 positions.erase(positions.end() - 2);
122 }
123 else {
124 dir = newDir;
125 finalDistance += currentDistance;
126 }
127 }
128
129 const BWAPI::Unit closestObstacle = BWAPI::Broodwar->getClosestUnit(currentWaypoint, (BWAPI::Filter::IsBuilding || BWAPI::Filter::IsSpecialBuilding), unitType.width() / 2 + 5);
130 if (closestObstacle != nullptr && closestObstacle->exists()) {
131 const BWAPI::Position buildingDir = closestObstacle->getPosition() - currentWaypoint;
132 int xOffset = 0;
133 int yOffset = 0;
134
135 if (buildingDir.x < 0) {
136 xOffset += 5;
137 }
138 if (buildingDir.y < 0) {
139 yOffset += 5;
140 }
141
142 if (buildingDir.x > 0) {
143 xOffset -= 5;
144 }
145 if (buildingDir.y > 0) {
146 yOffset -= 5;
147 }
148
149 const BWAPI::Position newWaypoint = BWAPI::Position(currentWaypoint.x + xOffset, currentWaypoint.y + yOffset);
150 dir = newWaypoint - prevWaypoint;
151 positions.erase(positions.end() - 1);
152 positions.push_back(newWaypoint);
153 }
154
155 prevPos = currentPos;
156 }
157
158
159 // Since we're pushing to the tile vector from end to start, we need to reverse it afterwards
160 reverse(positions.begin(), positions.end());
161
162#ifdef DEBUG_PATH
163 cout << "Milliseconds spent generating path: " << totalTimer.getElapsedTimeInMilliSec() << " ms" << endl;
164#endif
165 totalTimer.stop();
166 return Path(positions, finalDistance);
167 }
168
169 // Before checking neighbours, see if the current node can get a precached location to the ending area
170 const BWEM::Area* area1 = bwem_map.GetArea(currentNode.tile);
171 const BWEM::Area* area2 = bwem_map.GetArea(end);
172
173 Path precachedPath = Path();
174 if (area1 != nullptr && area2 != nullptr && area1->Id() != area2->Id()) {
175 if ((AreaPathCache.contains(make_pair(area1->Id(), area2->Id())) || AreaPathCache.contains(make_pair(area2->Id(), area1->Id()))) && area1->AccessibleFrom(area2)) {
176 // Two cases:
177 // - area1 and area2 are not neighbours (get shortest path of chokepoints from 1 to)
178 // - area1 and area2 are neighbours (have to find closest path that goes to the chokepoint between area1 and area2)
179
180 // If area1 and area2 are not neighbours, simply path through the entire cached path
181 if (!contains(area1->AccessibleNeighbours(), area2)) {
182 pair<const BWEM::Area*, const BWEM::Area*> pair = make_pair(area1, area2);
183 precachedPath = AreaPathCache[make_pair(area1->Id(), area2->Id())];
184
185 // Since cached paths go from smaller ID to larger ID, if area1 has the larger ID, flip the positions in the precachedPath
186 if (area1->Id() > area2->Id()) {
187 precachedPath.flip();
188 }
189
190 if (precachedPath.positions.size() > 0) {
191 vector<BWAPI::Position> currentPositions;
192 int currentDistance = 0;
193 while (currentNode.tile != start) {
194 if (isInteractableEndpoint && currentNode.tile == end) {
195 currentPositions.push_back(BWAPI::Position(currentNode.tile));
196 }
197 else {
198 currentPositions.push_back(BWAPI::Position(currentNode.tile) + BWAPI::Position(16, 16));
199 }
200 currentDistance += currentNode.tile.getApproxDistance(parent[TileToIndex(currentNode.tile)]);
201 currentNode.tile = parent[TileToIndex(currentNode.tile)];
202 }
203
204 Path currentPath;
205 Path toStartOfPrecache;
206 Path toEnd;
207 Path finalPath;
208
209 try {
210 currentPath = Path(currentPositions, currentDistance);
211
212 toStartOfPrecache;
213 if (currentPath.positions.size() > 0) {
214 toStartOfPrecache = generateSubPath(currentPositions.at(currentPositions.size() - 1), unitType, precachedPath.positions.at(0));
215 }
216
217 toEnd = generateSubPath(precachedPath.positions.at(precachedPath.positions.size() - 1), unitType, _end);
218
219 finalPath = currentPath + toStartOfPrecache + precachedPath + toEnd;
220#ifdef DEBUG_PATH
221 cout << "Current node found cached path: " << "start size: " << currentPath.positions.size() + toStartOfPrecache.positions.size() << " | " << "precache size: " << precachedPath.positions.size() << " | " << "end size: " << toEnd.positions.size() << endl;
222#endif
223 }
224 catch (const runtime_error& e) {
225#ifdef DEBUG_PATH
226 cout << e.what() << endl;
227#endif
228 totalTimer.stop();
229 return Path();
230 }
231
232 totalTimer.stop();
233 return finalPath;
234 }
235 else {
236 totalTimer.stop();
237 return Path();
238 }
239 }
240 // If they are neigbours, try to find a nearby cached path to the end area that we can attach to
241 else {
242 Path subPath = closestCachedPath(_start, _end);
243 if (subPath == Path()) {
244 totalTimer.stop();
245 return Path();
246 }
247
248 Path startPath;
249 Path endPath;
250 Path finalPath;
251
252 try {
253 startPath = generateSubPath(_start, unitType, subPath.positions.at(0));
254 endPath = generateSubPath(subPath.positions.at(subPath.positions.size() - 1), unitType, _end);
255 }
256 catch (const runtime_error& e) {
257#ifdef DEBUG_PATH
258 cout << e.what() << endl;
259#endif
260 totalTimer.stop();
261 finalPath = Path();
262 }
263
264 finalPath = startPath + subPath + endPath;
265
266#ifdef DEBUG_PATH
267 cout << "Connected to nearby cached path: " << startPath.positions.size() << " | " << precachedPath.positions.size() << " | " << endPath.positions.size() << endl;
268#endif
269 totalTimer.stop();
270 if (finalPath.positions.size() > 0) {
271 totalTimer.stop();
272 return finalPath;
273 }
274 }
275 }
276 }
277
278 // Step through each neighbour of the current node. The first neighbour that has a lower fCost is instantly explored next
279 // Neighbour's walkability is already checked inside of getNeighbours()
280 Timer neighbourTimer = Timer();
281 neighbourTimer.start();
282 for (int x = -1; x <= 1; x++) {
283 for (int y = -1; y <= 1; y++) {
284
285 // Ignore self
286 if (x == 0 && y == 0) {
287 continue;
288 }
289
290 // Check
291 if (x != 0 && y != 0) {
292 BWAPI::TilePosition a(currentNode.tile.x + x, currentNode.tile.y);
293 BWAPI::TilePosition b(currentNode.tile.x, currentNode.tile.y + y);
294 if (!tileWalkable(unitType, a, end, isInteractableEndpoint) || !tileWalkable(unitType, b, end, isInteractableEndpoint))
295 continue;
296 }
297
298 const BWAPI::TilePosition neighbourTile = BWAPI::TilePosition(currentNode.tile.x + x, currentNode.tile.y + y);
299 // If the neighbour tile is walkable, creates a Node of the neighbour tile and adds it to the neighbours vector
300 if (tileWalkable(unitType, neighbourTile, end, isInteractableEndpoint)) {
301
302 // CHANGE: Using integers for gCost and hCost for efficiency while sacrificing some accuracy across long distances
303 // Makes use of how optimized BWAPI's getApproxDistance is
304 const int gCost = currentNode.gCost + currentNode.tile.getApproxDistance(neighbourTile) * ((x != 0 && y != 0) ? 14 : 10);
305 // If neighbour is revisited but doesn't have a lower cost than what was previously evaluated, skip it
306 if (closedSet[TileToIndex(neighbourTile)] && gCost >= gCostMap[TileToIndex(neighbourTile)]) {
307 continue;
308 }
309
310 if (!openSetNodes.contains(neighbourTile) || gCost < gCostMap[TileToIndex(neighbourTile)]) {
311 const int hCost = neighbourTile.getApproxDistance(end) * ((x != 0 && y != 0) ? 14 : 10);
312 const double fCost = gCost + (HEURISTIC_WEIGHT * hCost);
313
314 //cout << "Tile costs: " << gCost << " | " << hCost << " | " << fCost << endl;
315 const Node neighbourNode = Node(neighbourTile, currentNode.tile, gCost, hCost, fCost);
316
317 //cout << "Comparing neighbour and current fCost: " << neighbourNode.fCost << " | " << currentNode.fCost << endl;
318//
319 // NOTE: For now, not using early neighbour expansion. Having issues with how the algorithm explores neighbours.
320 /*if (neighbourNode.fCost < currentNode.fCost && earlyExpansion == false) {
321 earlyNode = neighbourNode;
322 cout << "Found early expansion" << endl;
323 earlyExpansionTiles.push_back(earlyNode.tile);
324 earlyExpansion = true;
325 }*/
326
327 if (!openSetNodes.contains(neighbourTile)) {
328 openSet.push(neighbourNode);
329 openSetNodes.insert(neighbourTile);
330 }
331 parent[TileToIndex(neighbourTile)] = currentNode.tile;
332 gCostMap[TileToIndex(neighbourTile)] = gCost;
333 }
334 }
335 }
336 }
337 neighbourTimer.stop();
338 }
339
340 totalTimer.stop();
341 return Path();
342}
AStar::closestCachedPath
static Path closestCachedPath(BWAPI::Position start, BWAPI::Position end)
Loops through the precached paths between areas and chokepoints to find the closest path from start t...
Definition A-StarPathfinding.cpp:705
AStar::TileToIndex
static int TileToIndex(BWAPI::TilePosition tile)
Used for indexing BWAPI::TilePositions in arrays. Converts a BWAPI::TilePosition to an integer index ...
Definition A-StarPathfinding.cpp:761
AStar::tileWalkable
static bool tileWalkable(BWAPI::UnitType unitType, BWAPI::TilePosition tile, BWAPI::TilePosition end, bool isInteractableEndpoint)
Using the unit's unit type, checks if the tile is walkable. This is done by using the unit's dimens...
Definition A-StarPathfinding.cpp:765
Path::flip
void flip()
Reverses the vector of positions in the path. Used when we want to flip a path from A to B into a pat...
Definition A-StarPathfinding.h:84

◆ generateSubPath()

Path AStar::generateSubPath ( BWAPI::Position _start,
BWAPI::UnitType unitType,
BWAPI::Position _end,
bool isInteractableEndpoint = false )
staticprivate

Almost identital to GeneratePath() except does not check for precache optimizations.
Used for when you want to find the path between two points without shortcuts that may change the returned waypoints.

Parameters
_start
unitType
_end
isInteractableEndpoint
Returns

Definition at line 345 of file A-StarPathfinding.cpp.

345 {
346 Timer subTimer = Timer();
347 subTimer.start();
348
349 vector<BWAPI::Position> positions = vector<BWAPI::Position>();
350 vector<BWAPI::Position> subPathPositions = vector<BWAPI::Position>();
351 int finalDistance = 0;
352 // Checks if either the starting or ending tile positions are invalid
353 // If so, returns early with no positions added to the path
354 if (!_start.isValid() || !_end.isValid()) {
355 cout << "ERROR: Starting point or ending point not valid" << endl;
356 subTimer.stop();
357 return Path();
358 }
359
360 // Flying units can move directly to the end position without pathfinding
361 if (unitType.isFlyer()) {
362 positions.push_back(_end);
363 finalDistance = _start.getApproxDistance(_end);
364 subTimer.stop();
365 return Path(positions, finalDistance);
366 }
367
368 BWAPI::TilePosition start = BWAPI::TilePosition(_start);
369 const BWAPI::TilePosition end = BWAPI::TilePosition(_end);
370
371 // Optimization using priority_queue for open set
372 // The priority_queue will always have the node with the lowest fCost at the top
373 // No need for O(N) lookup time :)
374 priority_queue<Node, vector<Node>, greater<Node>> openSet;
375
376 unordered_set<BWAPI::TilePosition, TilePositionHash> openSetNodes;
377
378 // Optimization using array for closed set
379 // O(1) lookup time :)
380 const int mapWidth = BWAPI::Broodwar->mapWidth();
381 const int mapHeight = BWAPI::Broodwar->mapHeight();
382 vector<bool> closedSet(mapWidth * mapHeight, false); // Default: no closed positions
383 vector<int> gCostMap(mapWidth * mapHeight, INT_MAX); // Default: all gCosts are as large as possible
384
385 // Store parents in an unordered_map for reconstructing path later
386 unordered_map<int, BWAPI::TilePosition> parent;
387
388 // Very first node to be added is the starting tile position
389 Node firstNode = Node(start, start, 0, 0, 0);
390 openSet.push(firstNode);
391 openSetNodes.insert(start);
392 gCostMap[TileToIndex(start)] = 0;
393 Node currentNode = Node();
394
395 bool earlyExpansion = false;
396 while (openSet.size() > 0) {
397 // Time limit for path generations
398 if (TIME_LIMIT_ENABLED && subTimer.getElapsedTimeInMilliSec() > TIME_LIMIT_MS) {
399 subTimer.stop();
400#ifdef DEBUG_PATH
401 cout << "Time spent in subpath: " << subTimer.getElapsedTimeInMilliSec() << endl;
402#endif
403 throw runtime_error("TIME LIMIT REACHED IN PATH : Empty path returned.");
404 }
405
406 if (!earlyExpansion) {
407 currentNode = openSet.top();
408 openSet.pop();
409 openSetNodes.erase(currentNode.tile);
410 }
411 closedSet[TileToIndex(currentNode.tile)] = true;
412 closedTiles.push_back(std::make_pair(currentNode.tile, currentNode.fCost));
413
414 // Check if path is finishedx
415 if (currentNode.tile == end) {
416 BWAPI::Position prevPos = BWAPI::Position(currentNode.tile);
417 BWAPI::Position dir;
418 BWAPI::Position currentWaypoint;
419 BWAPI::Position prevWaypoint;
420
421 while (currentNode.tile != start) {
422 if (isInteractableEndpoint && currentNode.tile == end) {
423 positions.push_back(BWAPI::Position(currentNode.tile));
424 }
425 else {
426 positions.push_back(BWAPI::Position(currentNode.tile) + BWAPI::Position(16, 16));
427 }
428 currentNode.tile = parent[TileToIndex(currentNode.tile)];
429 const BWAPI::Position currentPos = BWAPI::Position(currentNode.tile);
430
431 finalDistance += currentPos.getApproxDistance(prevPos);
432
433 // Don't smooth cached paths since units need to grab the nearest path that will take them to the chokepoint of the area they want to go to
434
435 const BWAPI::Unit closestObstacle = BWAPI::Broodwar->getClosestUnit(currentWaypoint, (BWAPI::Filter::IsBuilding || BWAPI::Filter::IsSpecialBuilding), unitType.width() / 2 + 5);
436 if (closestObstacle != nullptr && closestObstacle->exists()) {
437 const BWAPI::Position buildingDir = closestObstacle->getPosition() - currentWaypoint;
438 int xOffset = 0;
439 int yOffset = 0;
440
441 if (buildingDir.x < 0) {
442 xOffset += 5;
443 }
444 if (buildingDir.y < 0) {
445 yOffset += 5;
446 }
447 if (buildingDir.x > 0) {
448 xOffset -= 5;
449 }
450 if (buildingDir.y > 0) {
451 yOffset -= 5;
452 }
453
454 const BWAPI::Position newWaypoint = BWAPI::Position(currentWaypoint.x + xOffset, currentWaypoint.y + yOffset);
455 dir = newWaypoint - prevWaypoint;
456 positions.erase(positions.end() - 1);
457 positions.push_back(newWaypoint);
458 }
459
460 prevPos = currentPos;
461 }
462
463
464 // Since we're pushing to the tile vector from end to start, we need to reverse it afterwards
465 reverse(positions.begin(), positions.end());
466
467#ifdef DEBUG_SUBPATH
468 subTimer.stop();
469 cout << "Milliseconds spent generating SUB path: " << subTimer.getElapsedTimeInMilliSec() << " ms" << endl;
470#endif
471 subTimer.stop();
472 return Path(positions, finalDistance);
473 }
474
475 // Step through each neighbour of the current node. The first neighbour that has a lower fCost is instantly explored next
476 // Neighbour's walkability is already checked inside of getNeighbours()
477 Timer neighbourTimer = Timer();
478 neighbourTimer.start();
479 for (int x = -1; x <= 1; x++) {
480 for (int y = -1; y <= 1; y++) {
481
482 // Ignore self
483 if (x == 0 && y == 0) {
484 continue;
485 }
486
487 // Check
488 if (x != 0 && y != 0) {
489 BWAPI::TilePosition a(currentNode.tile.x + x, currentNode.tile.y);
490 BWAPI::TilePosition b(currentNode.tile.x, currentNode.tile.y + y);
491 if (!tileWalkable(unitType, a, end, isInteractableEndpoint) || !tileWalkable(unitType, b, end, isInteractableEndpoint))
492 continue;
493 }
494
495 const BWAPI::TilePosition neighbourTile = BWAPI::TilePosition(currentNode.tile.x + x, currentNode.tile.y + y);
496 // If the neighbour tile is walkable, creates a Node of the neighbour tile and adds it to the neighbours vector
497 if (tileWalkable(unitType, neighbourTile, end, isInteractableEndpoint)) {
498
499 // CHANGE: Using integers for gCost and hCost for efficiency while sacrificing some accuracy across long distances
500 // Makes use of how optimized BWAPI's getApproxDistance is
501 const int gCost = currentNode.gCost + currentNode.tile.getApproxDistance(neighbourTile) * ((x != 0 && y != 0) ? 14 : 10);
502 // If neighbour is revisited but doesn't have a lower cost than what was previously evaluated, skip it
503 if (closedSet[TileToIndex(neighbourTile)] && gCost >= gCostMap[TileToIndex(neighbourTile)]) {
504 continue;
505 }
506
507 if (!openSetNodes.contains(neighbourTile) || gCost < gCostMap[TileToIndex(neighbourTile)]) {
508 const int hCost = neighbourTile.getApproxDistance(end) * ((x != 0 && y != 0) ? 14 : 10);
509 const double fCost = gCost + (HEURISTIC_WEIGHT * hCost);
510
511 //cout << "Tile costs: " << gCost << " | " << hCost << " | " << fCost << endl;
512 const Node neighbourNode = Node(neighbourTile, currentNode.tile, gCost, hCost, fCost);
513
514 //cout << "Comparing neighbour and current fCost: " << neighbourNode.fCost << " | " << currentNode.fCost << endl;
515//
516 // NOTE: For now, not using early neighbour expansion. Having issues with how the algorithm explores neighbours.
517 /*if (neighbourNode.fCost < currentNode.fCost && earlyExpansion == false) {
518 earlyNode = neighbourNode;
519 cout << "Found early expansion" << endl;
520 earlyExpansionTiles.push_back(earlyNode.tile);
521 earlyExpansion = true;
522 }*/
523
524 if (!openSetNodes.contains(neighbourTile)) {
525 openSet.push(neighbourNode);
526 openSetNodes.insert(neighbourTile);
527 }
528 parent[TileToIndex(neighbourTile)] = currentNode.tile;
529 gCostMap[TileToIndex(neighbourTile)] = gCost;
530 }
531 }
532 }
533 }
534 neighbourTimer.stop();
535 }
536
537 subTimer.stop();
538 return Path();
539}

◆ octileDistance()

double AStar::octileDistance ( BWAPI::Position pos1,
BWAPI::Position pos2 )
staticprivate

Definition at line 833 of file A-StarPathfinding.cpp.

833 {
834 double dx = abs(pos2.x - pos1.x);
835 double dy = abs(pos2.y - pos1.y);
836 double D1 = 1.0;
837 double D2 = 1.414;
838 return (D1 * max(dx, dy)) + ((D2 - D1) * min(dx, dy));
839}

◆ squaredDistance()

double AStar::squaredDistance ( BWAPI::Position pos1,
BWAPI::Position pos2 )
staticprivate

Definition at line 822 of file A-StarPathfinding.cpp.

822 {
823 return pow((pos2.x - pos1.x), 2) + pow((pos2.y - pos1.y), 2);
824}

◆ TileToIndex()

int AStar::TileToIndex ( BWAPI::TilePosition tile)
staticprivate

Used for indexing BWAPI::TilePositions in arrays. Converts a BWAPI::TilePosition to an integer index based on the map width and height. The index is calculated as (tile.y * mapWidth + tile.x).

Parameters
tileTile position of the node
Returns

Definition at line 761 of file A-StarPathfinding.cpp.

761 {
762 return (tile.y * BWAPI::Broodwar->mapWidth()) + tile.x;
763}

◆ tileWalkable()

bool AStar::tileWalkable ( BWAPI::UnitType unitType,
BWAPI::TilePosition tile,
BWAPI::TilePosition end,
bool isInteractableEndpoint )
staticprivate

Using the unit's unit type, checks if the tile is walkable.
This is done by using the unit's dimensions to determine if they would overlap with any structures or terrain if the unit was placed in the tile.

Parameters
unitTypeUnit's BWAPI unit type
tileTarget tile
endThe target tile of the path
isInteractableEndpointBoolean flag set by user for if the point should be interactable (won't be walkable but shouldn't stop the path)
Returns

Definition at line 765 of file A-StarPathfinding.cpp.

765 {
766 if (!tile.isValid()) {
767 return false;
768 }
769
770 // If the tile is the end tile, returns true. Further processing will depend on the boolean isInteractableEndpoint set in GeneratePath()
771 if (tile == end && isInteractableEndpoint) {
772 return true;
773 }
774
775 for (const auto& staticBuilding : bwem_map.StaticBuildings()) {
776 BWAPI::TilePosition topLeft = staticBuilding.get()->TopLeft();
777 BWAPI::TilePosition bottomRight = staticBuilding.get()->BottomRight();
778
779 // check if tile is in this static building's tiles
780 if (tile.x >= topLeft.x && tile.x <= bottomRight.x) {
781 if (tile.y >= topLeft.y && tile.x <= bottomRight.y) {
782 return false;
783 }
784 }
785 }
786
787 // Gets measurements in terms of WalkPositions (8x8)
788 const int unitWidth = unitType.width() / 8;
789 const int unitHeight = unitType.height() / 8;
790 const BWAPI::Position tileCenter = BWAPI::Position(tile) + BWAPI::Position(16, 16);
791 if (!tileCenter.isValid()) {
792 return false;
793 }
794
795 // Checks all WalkPositions the unit would inhabit if it reached the center of the tile
796 for (int xOffset = -unitWidth / 2; xOffset < unitWidth / 2; xOffset++) {
797 for (int yOffset = -unitHeight / 2; yOffset < unitHeight / 2; yOffset++) {
798 const BWAPI::WalkPosition pos = BWAPI::WalkPosition(tileCenter) + BWAPI::WalkPosition(xOffset, yOffset);;
799 if (!BWAPI::Broodwar->isWalkable(pos)) {
800 return false;
801 }
802 }
803 }
804
805 const BWAPI::Position topLeft = BWAPI::Position(tileCenter.x - (unitType.width() / 2), tileCenter.y - (unitType.height() / 2));
806 const BWAPI::Position bottomRight = BWAPI::Position(tileCenter.x + (unitType.width() / 2), tileCenter.y + (unitType.height() / 2));
807 // Checks if any buildings are touching where the unit would be in the middle of the tile
808 const BWAPI::Unitset& unitsInRect = BWAPI::Broodwar->getUnitsInRectangle(topLeft, bottomRight, BWAPI::Filter::IsBuilding || (BWAPI::Filter::IsNeutral && !BWAPI::Filter::IsCritter));
809 if (!unitsInRect.empty()) {
810 return false;
811 }
812
813#ifdef DEBUG_PATH
814 if (rectCoordinates.size() < 10000) {
815 rectCoordinates.push_back(std::make_pair(topLeft, bottomRight));
816 }
817#endif
818
819 return true;
820}

Member Data Documentation

◆ AreaPathCache

map< pair< const BWEM::Area::id, const BWEM::Area::id >, const Path > AStar::AreaPathCache
staticprivate

Definition at line 108 of file A-StarPathfinding.h.

◆ ChokepointPathCache

map< pair< const BWEM::ChokePoint *, const BWEM::ChokePoint * >, Path > AStar::ChokepointPathCache
staticprivate

Definition at line 109 of file A-StarPathfinding.h.

◆ failedAreaPairs

vector< pair< const BWAPI::WalkPosition, const BWAPI::WalkPosition > > AStar::failedAreaPairs
staticprivate

Definition at line 111 of file A-StarPathfinding.h.

◆ UncachedAreaPairs

vector< pair< const BWAPI::WalkPosition, const BWAPI::WalkPosition > > AStar::UncachedAreaPairs
staticprivate

Definition at line 110 of file A-StarPathfinding.h.

The documentation for this class was generated from the following files: