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