=Paper=
{{Paper
|id=Vol-3217/paper26
|storemode=property
|title=Pathfinding and Map Feature Learning in RTS Games with Partial Observability
|pdfUrl=https://ceur-ws.org/Vol-3217/paper26.pdf
|volume=Vol-3217
|authors=Hao Pan
|dblpUrl=https://dblp.org/rec/conf/aiide/Pan21
}}
==Pathfinding and Map Feature Learning in RTS Games with Partial Observability==
https://ceur-ws.org/Vol-3217/paper26.pdf
Pathfinding and Map Feature Learning in RTS Games with Partial Observability
Hao Pan
QOMPLX, Inc.
1775 Tysons Boulevard
McLean, Virginia, 22102
hao.pan@qomplx.com
Abstract for the current query. The authors further demonstrated that
both heuristics reduced the exploration and time complex-
In this paper we deal with the pathfinding problem in Real
Time Strategy (RTS) games with partial observability for Ar- ity of A* search significantly over a standard distance met-
tificial Intelligence (AI) agents. We first propose a Bootstrap ric. Jump Point Search (JPS) (Harabor and Grastien 2011)
JPS algorithm to perform pathfinding efficiently alongside a is considered an improvement over the A* algorithm as it
routine to preprocess terrain features. We then establish a grid facilitates the search procedure by means of graph prun-
system to learn map features systematically considering both ing, eliminating certain nodes in the grid based on assump-
mobile and immobile units. Utilizing the learned map fea- tions that can be made about the current node’s neighbors.
tures, we employ a waypoint-based pathfinding technique to This means the algorithm can consider long jumps from the
navigate pathfinding agents away from threats efficiently. Us- current node, while traditional A* only considers adjacent
ing maps from a few established RTS games, we demonstrate nodes. In the following years, the authors further optimized
the performance of our pathfinding framework and compare
JPS by considering a preprocessing grid and stronger jump
it with a few alternative approaches.
rules (Harabor and Grastien 2012, 2014).
It can be demanding when applying pathfinding in games,
1 Introduction as one has to consider extra factors such as map proper-
Pathfinding is the process of searching a graph and finding ties and algorithm efficiency. (Björnsson and Halldórsson
a path between the start and the destination nodes. There 2006; Sturtevant and Buro 2005) used maps from differ-
can be map features such as obstacles along the way, mak- ent games and of different sizes. They evaluated the per-
ing the process potentially challenging to solve. Pathfind- formance of pathfinding methods based on multiple criteria
ing is not a new topic, and various algorithms have already such as the number of nodes expanded, path-length, and run-
been developed. There are mainly two schools of such algo- time. (Zarembo and Kodors 2015) studied pathfinding algo-
rithms. Breadth-first search and depth-first search approach rithms including A*, BFS, Dijkstra’s algorithm, HPA* and
this problem by examining all possible paths exhaustively. LPA* (Koenig, Likhachev, and Furcy 2004), and compared
The other school of algorithms focus more on finding the op- them based on execution time and the number of traversed
timal path. Dijkstra’s algorithm (Dijkstra 1959) maintains an nodes. (Sturtevant et al. 2019) improved pathfinding effi-
“open set” and examines the node in the set with the short- ciency by planning in an abstract space and then refining
est distance from the start. Once the destination is marked abstract paths to traversable paths. The authors took into ac-
as visited, the shortest path is determined by tracing back all count terrain costs and dynamic terrain, and achieved a good
the visited nodes. (Wagner, Willhalm, and Zaroliagis 2005) balance between memory usage, path quality, and pathfind-
reduced the search space of Dijkstra’s algorithm by extract- ing speed. (Hatem, Stern, and Ruml 2013) studied the sub-
ing geometric information from a given layout of the graph optimal search algorithms and proposed a linear space ana-
and by encapsulating precomputed shortest-path informa- logue of Explicit Estimation Search (EES) to alleviate the
tion in the so-called geometric containers. A* (Doran and problem of the memory being overrun on large problems.
Michie 1966) is an extension of Dijkstra’s algorithm. The Additional considerations were needed when applying
main difference is that A* assigns a weight to each node in pathfinding in Real Time Strategy (RTS) games such as
the open set equal to the cost from the starting node to that StarCraft. On a general level, the prevalent approach is to
node plus the approximate cost between that node and the couple terrain learning/analysis methods and pathfinding.
destination. The approximate distance is found by heuris- (Hagelbäck 2015) coupled pathfinding with two techniques:
tic. (Björnsson and Halldórsson 2006) used the dead-end 1) Potential Field (PF); and 2) Flocking. They discovered
heuristic to eliminate certain map areas that are provably ir- that PF techniques require much more computational re-
relevant, and the so-called gateways to improve estimates sources than the counterpart which is relatively simpler.
Copyright c 2021 for this paper by its authors. Use permitted un- (Amador and Gomes 2019) combined Influence Maps and
der Creative Commons License Attribution 4.0 International (CC pathfinding in a way that the influence costs replaced the
BY 4.0). traditional distance-based costs. Utilizing repulsors and at-
tractors in the game world, the authors constructed bounded- ing downhill or uphill). We deal with single-agent pathfind-
search pathfinders that avoid obstacles (repulsors) and fol- ing problems and the pathfinding agent does not have size.
low check points (attractors). (Ninomiya et al. 2014) intro- We also assume that the unit collision does not exist. The
duced hybrid environment representations that balance com- solution to the problem is expected to yield an optimal path
putational efficiency and search space density to provide a safe for pathfinding agents to travel on from enemy threats
minimal, yet sufficient, discretization of the search graph for which can damage or even kill the agents.
constraint-aware navigation.
There are still challenges present for pathfinding in RTS
games with partial observability. Even for a well established
2.2 Terrain Preprocessing
algorithm such as the A*, it can be improved much fur- We believe terrain preprocessing is a necessary step to per-
ther. An AI agent with poorly performing pathfinding rou- form before the actual pathfinding process begins. More
tines slows down the game and hurts a human’s experience specifically, this is about performing obstacle filling which
of playing against it. Additionally, in tournaments there are is achieved by completing the following sub-tasks:
limits on how much time an agent can spend within each
logical step (also known as frame) for doing everything in- i Identify U-/L- shaped islands which are adjacent obstacle
cluding pathfinding. For example, a bot will be given a game nodes connected to each other either horizontally or ver-
loss if it spends more than one second in at least ten game tically. We do not consider diagonally connected nodes as
frames in the AIIDE StarCraft AI competition1 . Last but not doing so could potentially identify two different islands
least, the Fog of War (FoW) obscures the position informa- as a single one.
tion of opponent units, making pathfinding difficult. FoW is
the common way partial observability presents itself in RTS ii Mark the nodes bounded by those islands identified pre-
games. (Hagelback and Johansson 2008) illustrated that a viously as obstacles.
bot using potential fields can deal with imperfect informa-
tion equally well as one with the perfect information, while The motivation here is that the U-/L-shaped islands could
being computationally more efficient, using the game Open lead to the exploration of nodes which are not on the optimal
Real Time Strategy (ORTS). However, ORTS is a much sim- path and cause an algorithm to get stuck. Subtask i can be ac-
pler game than StarCraft and these authors did not consider complished by sweeping through every node on the map and
unit movement under the FoW. Furthermore, potential field conducting a depth-first search (DFS). In each DFS traver-
based methods are prone to get stuck in local minima. sal we recursively call for the 4 neighbours. We keep track of
In this paper, we propose a pathfinding framework to the visited nodes so that they are not visited again. Subtask
tackle the aforementioned challenges by means of: 1) per- ii is fulfilled by examining every node on the map to see if
forming preprocessing to eliminate nodes deemed unnec- they are bounded by the obstacles in at least three out of the
essary to explore; 2) devising the Bootstrap JPS to further four directions (up, down, left, right). We only care about
improve the efficiency of the exploration; 3) establishing a the L-shaped islands when at least one of the ends touches
grid system which is capable of both efficiently storing the the boundary of the map. If that is the case, the map bound-
learned position of immobile units and predicting the po- ary effectively acts as an obstacle, and combined with the
tential position a mobile unit may move to under the FoW; L-shaped island, they together form a U-shaped island. To
and 4) employing a waypoint-based pathfinding technique ease the understanding, one can consider the map boundary
to navigate the pathfinding agents out of danger efficiently. as an artificially added obstacle which is to be welded to the
L-shaped island (see fig. 1 for a visual demonstration). Note
2 Methodology that for cases where the destination node or nodes from an-
2.1 Problem Definition and Assumptions other island are bounded by the U-/L-shaped islands, obsta-
cle filling is not to be performed, otherwise one runs the risk
First we describe some details of the pathfinding problem we of blocking the agent from finding the destination by adding
are dealing with here. The input of the pathfinding problem obstacles unnecessarily. All the procedures discussed here
is a map where some parts are covered by the FoW which are summarized in algorithm 1.
can be lifted once the influenced area is explored. The pres-
ence of the FoW conceals certain information such as the In algorithm 1, grid is a matrix storing the status of each
position of an enemy unit and the shape of the terrain. Even node. A value of 0 means the current node is not an ob-
with perfect information, the built-in pathfinding algorithm stacle, 1 means it is an obstacle, and 2 means the current
can sometimes fail to find a valid path, causing units to get node is already visited for island counting purposes. count
stuck indefinitely when being issued a move command. Fur- is the number of the islands identified. The size of a par-
thermore, certain information such as the start and destina- ticular island, Islandk , is the number of nodes constituting
tion nodes can be potentially changing. We utilize the 8- this island. There are three blocks of code in algorithm 1.
connected grid map representation. We further assume there The first defines the M arkIsland() function which is to be
is no traveling cost (e.g., it is equally easy to traverse grass- recursively called by the second block of code. The execu-
lands and deserts, and there is no extra difficulty when mov- tion of the first two blocks of code identifies all the islands if
they exist. The last block of code examines if a node is sur-
1 rounded by a U-/L-shaped island and artificially marks the
AIIDE StarCraft AI tournament has rules on frame times:
https://www.cs.mun.ca/ dchurchill/starcraftaicomp/rules.shtml node as an obstacle if so.
Algorithm 1 Obstacle Filling
MarkIsland(grid, p, q, ROWS, COLS)
if Node(p, q) is within the map boundaries then
Mark current cell as visited: grid[p][q] = 2
MarkIsland(grid, p, q-1, ROWS, COLS)
MarkIsland(grid, p, q+1, ROWS, COLS)
MarkIsland(grid, p-1, q, ROWS, COLS)
MarkIsland(grid, p+1, q, ROWS, COLS)
end if
for i0 in 1:ROWS do
for j 0 in 1:COLS do
if grid[i0 ][j 0 ] == 1 then
count++
MarkIsland(grid, i0 , j 0 , ROWS, COLS)
end if
Figure 1: Illustration of filling an L-shaped island end for
end for
for i in 1:ROWS do
2.3 Bootstrap Jump Point Search for j in 1:COLS do
Jump Point Search (JPS) speeds up pathfinding on uniform- if Node(i, j) is surrounded by an island or a map
cost grid maps by “jumping over” many locations that would boundary in any three of the four directions (left,
otherwise need to be explicitly considered. Here we aim at right, top, bottom) then
expediting the exploration further by using JPS itself (hence Mark Node(i, j) as an obstacle
the term bootstrap) to compute the cost function between a end if
node and the destination instead of calculating the heuristics end for
using traditional means such as the Euclidean or Manhat- end for
tan distance. Depending on the complexity of the terrain,
Euclidean or Manhattan distance may sometimes provide
an overly optimistic estimation because neither metric con- the cost it estimates to reach the goal is not higher than the
siders obstacles along the way. The Bootstrap JPS is to be lowest possible cost from the current point in the path.
used after the completion of the terrain preprocessing as dis- An algorithm will terminate on the shortest path if an ad-
cussed previously. The time complexity associated with the missible heuristic is used and the algorithm progresses per
bootstrap JPS is O(n2 ) considering the worst case scenario iteration only along the path that has the lowest total ex-
where every possible (source, destination) pairing must be pected cost of several candidate paths and terminates the
evaluated. However, this process is easily parallelizable. moment any path reaches the goal. In short, using an admis-
Memoization routine for Bootstrap JPS We store the sible heuristic guarantees the optimality of the path found if
path found and its length for each node, hoping to further such a path exists.
speed up the search process. At each iteration of Bootstrap Our proposed approach computes the heuristic by cal-
JPS, a few sub-pathfinding problems are solved and poten- culating the lengths of the paths found by JPS and mem-
tially the solution to one of them is a part of the optimal orizes them for all following intermediate calculations. It
path. The solution to each of these sub problems consists of is already proven that the JPS yields optimal paths (Hara-
a series of nodes leading to the destination from the current bor and Grastien 2011, 2012). This means our heuristic can
node. Storing such nodes can potentially allow us to termi- never overestimate the cost and consequently the heuristic
nate the Bootstrap JPS at a much earlier point and further is indeed admissible. At this point we can say our proposed
improve the efficiency. approach also guarantees the optimality of the paths.
To determine when to terminate the Bootstrap JPS, we
rely on two simple conditions: 2.4 Unit movement estimation under the FoW
i Terminate the Bootstrap JPS when an optimal path from When one applies pathfinding methods in an RTS game en-
the current node to the destination is found. vironment where the Fog of War is present, the optimal path
may sometimes backfire, as the obstacles/threats may have
ii Terminate the Bootstrap JPS when an optimal path from
changed their position without being detected, and as a re-
the next node (a jump point) to the destination is found.
sult hinder/damage the pathfinding agent(s). The corrrect es-
Optimality of Bootstrap JPS Often in a pathfinding pro- timation of unit movement under the FoW becomes vital to
cess, a heuristic is used to estimate the cost of reaching the solving the pathfinding problem in this setting.
goal state. A heuristic function is said to be admissible if it The core of the solution to address the estimation of unit
never overestimates the cost of reaching the goal. That is, movement with partial observability is the velocity of the
unit. Such quantity is available via BWAPI2 which enables
an AI bot to interact with the game StarCraft. BWAPI pro-
vides the kind of information a human player would have
access to. The velocity information is not always available,
as it would become inaccessible if the unit in question is un-
der the FoW.
In order to estimate the unit movement, the question to
consider is, how far into the future would we like to perform
the forecast? Our approach is to set the time window to be
the duration tdur it takes for a unit to cover its sight range
dsight while traveling at its speed v:
dsight
tdur = (1)
v
In StarCraft, a unit has both a sight range and an attack
range, with the sight range being oftentimes greater than the Figure 2: Illustration of the decay model with varying decay
attack range. If an enemy unit were to attack ours, it needs to rate
travel to a point where the target is within the attack range.
By having it to cover the entire sight range, we ensure that
the estimation serves as the upper ceiling.
What happens when we do not have access to a unit’s Terrain Features (Altitudes) Here we identify terrain
velocity (i.e., the unit is covered by the FoW)? We turn to features such as a plateau which cannot be moved/destroyed
heuristics by first acquiring the last known position and the at all times. The identification of such features needs to be
velocity of the unit. Using such information, the velocity is done only once. Depending on the destination, ground units
then modeled as one that decays over time. This means that will have to find either the way around the plateau, or the
as time goes by, we grow more and more uncertain about the ramp leading up to the plateau, thus posing a challenge for
velocity, and as a result, the magnitude of the velocity will pathfinding.
gradually reach zero, indicating that any obscured area in Enemy Units’ Position It is easy to mark a unit’s position
the contiguous FoW is possible for the unit to travel to. The if we can see the unit, but otherwise this matter becomes
interpretation in this context is that, given enough time, if a difficult, as a unit can move, and under the FoW, we would
unit is still under the FoW, it becomes reasonable to assume not be able to know the direction of the movement. This is
that it is not actively trying to come out of FoW/chasing our exactly the place where section 2.4 can become useful.
unit(s). As a result, it would be safe to assume that the mag- Next, we categorize all mobile units as follows:
nitude of its velocity is zero as the unit can be traveling in
i Workers: these units are the primary targets for us to ha-
any direction. This approach is similar to the particle model
rass as much as possible, so that we can disrupt the oppo-
(Weber, Mateas, and Jhala 2011). However, our decay model
nent’s economy. After all, “having more units” remains a
has the advantage of being flexible to account for the threat
fundamental winning condition in many RTS games.
level perceived, and this is controlled by the power parame-
ter p in the decay model: ii Units that can attack ground targets
iii Units that can attack air targets
v0
v = v0 − · tp (2) Separating items ii and iii is essential because pathfind-
tpdur ing for ground units and pathfinding for air units are very dif-
Here v0 is the last known velocity of the unit before it ferent: they depend on the opponent’s ground and air threats.
entered the FoW and became inaccessible. The model is fur- Having the position of the units is not enough. We also
ther illustrated in fig. 2. care about the attack range a unit has. This means the attack
range of both the opponent’s units and our own. This kind
of information together with the position information would
2.5 Map Feature Learning help a pathfinding routine to discover the position that would
Having the correct unit movement estimation alone is not allow us to fire on the opponent’s units at our maximum at-
enough to solve the pathfinding problem in an RTS game tack range while staying out of theirs.
environment. There are not only the usual terrain obstacles Enemy Buildings’ Position We learn only the opponent’s
we see, but also enemy units and buildings which can spawn defensive buildings here. An immobile defensive structure
or move throughout the game, and affect the traversability of has its own attack range. Together with its position, all the
nodes. We deemed the following features necessary to learn areas under the influence of such buildings are marked as
to facilitate the pathfinding process. red grids (as in fig. 3) indicating positions to avoid. Unlike
a unit, a building cannot move, so what we once discovered
2
The GitHub page of BWAPI: https://github.com/bwapi/bwapi remains there unless the building gets destroyed. There are
opponent’s workers alongside the defensive buildings, com- We couple the waypoint-based pathfinding technique with
plicating the learning process. However, we were still able the proposed Bootstrap JPS based on the state of the
to find the few green grids which are safe places for the at- pathfinding agent. In the normal state where the agent has no
tackers to harass the workers. threat nearby, it proceeds to the destination using the Boot-
strap JPS. We switch immediately to the waypoint-based
pathfinding technique once there are threats close to the
agent, in order to minimize the potential damage dealt to
the agent. The waypoint-based technique also pairs with the
unit movement estimation smoothly as the position of the
waypoints can be readily updated based on the estimated po-
sition of the threats.
Figure 3: Marking the optimal positions to harass the en-
emy’s worker line while avoiding defensive buildings
2.6 Waypoint-based Pathfinding Technique
Waypoint-based pathfinding techniques (Zhu et al. 2015) of-
fer an easy way to specify the space and handle obstacles.
The motivation of us employing it here is to establish way- Figure 4: Demonstration of the waypoint-based pathfinding
points around any identified threat, and in turn facilitate the technique
pathfinding process. The simplest way to do so is to set up a
few corner points around the threat. fig. 4 illustrates a simple
example. The pathfinding agent first identifies a threat which
was previously unknown (potentially due to the Fog of War).
At the time of the discovery, the agent is already within the 3 Case Study
radius of the effect exerted by the threat. The agent must The purpose of the case study is to compare the proposed
choose a set of waypoints in order to return to safety. First pathfinding framework with a few alternative approaches,
path #1 is chosen because waypoint D is the closest to the namely, A* and JPS. We applied all three pathfinding tech-
agent. It is desirable to evade the threat as soon as possi- niques on two maps which are illustrated by figs. 5 and 6,
ble. Then path #2 is chosen because waypoint C is closer to respectively. The maps were taken from a benchmark map
the destination than waypoint B. Waypoint A is out of ques- set3 created by (Sturtevant 2012). The two maps are from
tion as an agent is only allowed to travel between adjacent the RTS Game WarCraft III (published in July, 2002) and
waypoints. Finally path #3 is chosen since it leads to the StarCraft (published in March, 1998), respectively. On each
destination directly and is deemed safe to travel upon. map we randomly chose 1000 pairs of starting and desti-
Compared to conventional pathfinding techniques such as nation nodes. Throughout the case study we assumed partial
A*, the waypoint-based one has the advantage of exploring observability. For each pair of starting and destination nodes,
much fewer nodes at the cost of the optimality of the path. we insert either a static or mobile enemy unit at a random
This is an acceptable tradeoff in an RTS game environment location along the optimal path which was pre-computed by
where speedy reactions are important. A*. Both the static and mobile enemy units were initially
There are a few small caveats here: 1) the agent is forbid- unknown to the computer-controlled pathfinding agent due
den from traveling through all the waypoints as that would to the partial observability. We programmed a set of simple
mean the agent is stuck travelling around the threat indefi- rules to govern the behavior of the mobile enemy unit. This
nitely; 2) it is forbidden to set waypoints (illustrated as the enemy unit always tries to move to or stay at its starting po-
grey circles on fig. 4) directly on the edge of the threat ra- sition if the pathfinding agent is outside of its sight range.
dius. This would endanger the agent as it travels between Once the pathfinding agent is within the sight range but out-
such waypoints; and 3) the number of waypoints estab- side of its attack range, the enemy unit will begin to chase
lished around the threat can have an impact on the agent’s the agent. The enemy unit will attack the agent if the agent
evasion from the threat as well as the computation effi- is within its attack range. When using A* and JPS, the en-
ciency. In practice we found that eight waypoints around emy unit is handled by marking all the nodes within its sight
each threat usually suffice to ensure that there are enough range as obstacles. Whenever a certain amount of nodes are
safe nodes/options for the agent to choose from while not
3
inducing too much additional computation burden. The map set is available from here: http://movingai.com
points around the threats it established. As these nodes are
easily obtained, the resulting RT is slightly lower than that
of JPS. Both the A* and JPS scored poorly in terms of RHP
as they are not dedicated to this particular pathfinding prob-
lem where partial observability is present. The matter be-
comes worse when the enemy threat is mobile. While by
design, the proposed framework handles this problem more
sophisticately and significantly reduced the amount of dam-
age received from the enemy threat. Overall, the proposed
pathfinding framework performed the best here.
Table 1: Peformance of various pathfinding routines
C RITERION A* JPS P ROPOSED
M AP #1 (391 × 388, AVG PATH LENGTH = 270)
Figure 5: Map #1 (hillsofglory.map) and a sample optimal NE 17803 213 216
path RT( S ) 3.04 1.72 1.68
RHP 52% 51% 82%
M AP #2 (512 × 512, AVG PATH LENGTH = 446)
NE 42346 220 224
RT( S ) 8.89 1.97 1.94
RHP 68% 69% 92%
4 Conclusions and Future Work
In this paper we proposed a pathfinding framework to ad-
dress the challenges encountered when performing pathfind-
ing in RTS games with partial observability by means of:
1) preprocessing terrain/map features to prevent pathfind-
ing routines to get stuck locally; 2) creating the Bootstrap
JPS to compute the cost function more accurately and in
turn further eliminate nodes deemed unnecessary to explore;
3) constructing the velocity decay model to predict unit
movement under the FoW; and 4) employing a waypoint-
Figure 6: Map #2 (Sanctuary.map) and a sample optimal
based pathfinding technique to help pathfinding agents to
path
maneuver around threats efficiently. We demonstrated that
the proposed framework was superior than a few mainstream
pathfinding routines such as A* and JPS.
In the future we would like to augment this work by: 1) so-
newly marked as obstacles, every pathfinding technique is lidifying an effective way to learn the decay rate used in the
going to be rerun as the map they operate on has effectively decay model either in-game on the fly or from past data; 2)
changed. All experiments were run on a 2.2 GHz CPU com- considering other possibilities of velocity development un-
puter. der the FoW. Currently we assume the worst case where an
Due to the complexity of the environment for pathfind- enemy unit would immediately begin to chase our units at
ing, we use a few criteria to evaluate the performance of all costs. This can be highly situational and depends on sev-
pathfinding routines quantitatively: 1) number of nodes ex- eral things such as the opponent’s stance (defensive or of-
plored/evaluated (NE); 2) runtime (RT) measured in sec- fensive); 3) optimizing the resolution of the grid system. We
onds; and 3) remaining hit points (RHP) of the pathfinding have noticed that occasionally units can still catch enemy’s
agent after reaching the destination. The RHP is expressed fire while maneuvering around using Bootstrap JPS and the
as a percentage of the agent’s total hit points. The results grid system. This was mainly caused by a grid falsefully be-
for all the scenarios are summarized in table 1. We can see ing marked as safe due to the relatively coarse resolution and
that A* explored many more nodes than the other two tech- not accounting for unit sizes; 4) parallelizing the preprocess-
niques and the RT is much longer as a result. Both the JPS ing procedure to further speed up pathfinding; and 5) com-
and our proposed pathfinding framework greatly reduced the paring results with those from D* (Stentz 1994) and/or D*
NE values. The proposed framework explored a few more Lite (Koenig and Likhachev 2005), especially for scenarios
nodes on average than JPS mainly due to the additional way- where the obstacles are changing their position.
5 Acknowledgment navigation in dynamic environments. Computer Animation
The authors would like to specifically thank Nathan Roth and Virtual Worlds .
(MSc) for his dedicated effort in helping to construct our Stentz, A. 1994. Optimal and Efficient Path Planning for
own StarCraft bot. The authors would also like to thank the Partially-Known Environments. In Proceedings of the In-
SSCAIT community for their kind support. The authors are ternational Conference on Robotics and Automation, 3310–
equally thankful for Dennis Waldherr and his BASIL lad- 3317.
der, as it provided an invaluable test-bed like environment to Sturtevant, N.; and Buro, M. 2005. Partial Pathfinding Us-
see replays in a timely fashion, ensuring our StarCraft bot is ing Map Abstraction and Refinement. In Proceedings of
performant and bug-free. the 20th National Conference on Artificial intelligence, vol-
ume 3, 1392–1397.
References
Sturtevant, N. R. 2012. Benchmarks for Grid-Based
Amador, G.; and Gomes, A. J. 2019. Bounded-Search Pathfinding. IEEE Transactions on Computational Intel-
Pathfinders Based on Influence Maps Generated by Attrac- ligence and AI in Games 4(2): 144–148. doi:10.1109/
tors and Repulsors. IEEE Transactions on Games 99. TCIAIG.2012.2197681.
Björnsson, Y.; and Halldórsson, K. 2006. Improved Heuris- Sturtevant, N. R.; Sigurdson, D.; Taylor, B.; and Gibson, T.
tics for Optimal Pathfinding on Game Maps. In Artificial 2019. Pathfinding and Abstraction with Dynamic Terrain
Intelligence and Interactive Digital Entertainment Confer- Costs. In Proceedings of the AAAI Conference on Artifi-
ence, 9–14. cial Intelligence and Interactive Digital Entertainment, vol-
Dijkstra, E. W. 1959. A note on two problems in connexion ume 15, 80–86.
with graphs. Numerische Mathematik 1: 269–271. doi:10. Wagner, D.; Willhalm, T.; and Zaroliagis, C. 2005. Geo-
1007/BF01386390. metric Containers for Efficient Shortest-Path Computation.
Doran, J. E.; and Michie, D. 1966. Experiments with the ACM Journal of Experimental Algorithmics 10(1.3): 1–30.
Graph Traverser program. In Lockwood, M., ed., Proceed- Weber, B. G.; Mateas, M.; and Jhala, A. 2011. A Particle
ings of the Royal Society A, 235–259. London, United King- Model for State Estimation in Real-Time Strategy Games.
dom: Royal Society. In Proceedings of the Seventh AAAI Conference on Artificial
Hagelback, J.; and Johansson, S. J. 2008. Dealing with Intelligence and Interactive Digital Entertainment.
Fog of War in a Real Time Strategy game environment. In Zarembo, I.; and Kodors, S. 2015. Pathfinding Algorithm
2008 IEEE Symposium On Computational Intelligence and Efficiency Analysis in 2D Grid. In Proceedings of the Inter-
Games, 55–62. doi:10.1109/CIG.2008.5035621. national Scientific and Practical Conference. doi:10.17770/
Hagelbäck, J. 2015. Hybrid Pathfinding in StarCraft. etr2013vol2.868.
IEEE Transactions on Computational Intelligence and AI in Zhu, W.; Jia, D.; Wan, H.; Yang, T.; Hu, C.; Qin, K.; and
Games 8: 1–1. doi:10.1109/TCIAIG.2015.2414447. Cui, X. 2015. Waypoint Graph Based Fast Pathfinding in
Harabor, D.; and Grastien, A. 2011. Online Graph Prun- Dynamic Environment. International Journal of Distributed
ing for Pathfinding on Grid Maps. In Proceedings of the Sensor Networks 11. doi:10.1155/2015/238727.
Twenty-Fifth AAAI Conference on Artificial Intelligence,
1114–1119. San Francisco, CA, USA: AAAI.
Harabor, D.; and Grastien, A. 2014. Improving Jump Point
Search. In Chien, S.; and Fern, A., eds., Proceedings Inter-
national Conference on Automated Planning and Schedul-
ing, ICAPS, 128–135. Portsmouth, NH, USA: AAAI.
Harabor, D. D.; and Grastien, A. 2012. The JPS Pathfind-
ing System. In Proceedings of the Fifth Annual Symposium
on Combinatorial Search, 207–208. Niagara Falls, Canada:
AAAI.
Hatem, M.; Stern, R.; and Ruml, W. 2013. Bounded Subop-
timal Heuristic Search in Linear Space. In Proceedings of
the Symposium on Combinatorial Search (SoCS-13).
Koenig, S.; and Likhachev, M. 2005. Fast Replanning for
Navigation in Unknown Terrain. Transactions on Robotics
21: 254–363. doi:10.1109/tro.2004.838026.
Koenig, S.; Likhachev, M.; and Furcy, D. 2004. Lifelong
Pathplanning A*. Artificial Intelligence 155: 93–146.
Ninomiya, K.; Kapadia, M.; Shoulson, A.; Garcia, F.; and
Badler, N. 2014. Planning approaches to constraint-aware