One of the central problems in game AI is finding short and realistic looking paths. Path planning is typically divided into two parts: discretize simplifies a continuous environment into a graph and search propagates information along this graph to find path from a given start location to a given goal location. Video game developers (and roboticists) have developed several methods for solving the discretize problem: two dimensional regular grids composed of squares (square grid), hexagons or triangles, three dimensional regular grids composed of cubes, visibility graphs, circle based waypoint graphs, space filling volumes, navigation meshes, hierarchical methods such as framed quad trees, probabilistic road maps (PRMs) and rapidly exploring random trees (RRTs) , , .
However, due to its simplicity and optimality guarantees, A* is almost always the search method of choice. This is because A* is guaranteed to find a shortest path on the graph. The problem with A* is that a shortest path on the graph is not equivalent to a shortest path in the continuous environment. A* propagates information on the graph and constrains paths to be formed by edges of the graph which artificially constrains path headings. Consider Figures 1 and 2, in which a continuous environment has been discretized into a square grid and a navigation mesh, respectively. The shortest path on both the square grid and the navigation mesh (Figures 1 and 2 left) is much longer and more unrealistic looking (i.e has a heading change in free space) than the shortest path in the continuous environment (Figures 1 and 2 right).
Figure 1: Square Grid: Grid Path versus Shortest Path
Figure 2: Navigation Mesh: Grid Path versus Shortest Path (adapted from )
The fact that A* searches find long and unrealistic looking paths is well known in the video game community . The typical solution to this problem is to apply a post processing technique to smooth the paths found by an A* search. However, choosing the post processing technique that efficiently finds a realistic looking path can be difficult. One reason for this is that an A* search (with certain types of heuristics) is only guaranteed to find one of many shortest paths on the graph, some of which can be smoothed more efficiently than others. For example A* with the octile heuristic finds paths very efficiently on square grids, but it finds paths which are both very difficult to smooth and very unrealistic looking (a bad combination) because it tends to find paths in which all diagonal moves appear before all unit length moves. This is depicted by the dashed red path in Figure 3.
On the other hand A* with the straight-line heuristic on square grids finds paths that are the same length as A* with the octile heuristic, albeit significantly slower due to an increase in the number of vertex expansions, however these paths are smoothed very effectively because the paths it finds tend to follow the shortest path. This is depicted by the dotted green path in Figure 3. In general, these aesthetic optimizations do improve paths, but they provide difficult tradeoffs and they do not address the fundamental issue; namely that the A* search only considers paths that are constrained to graph edges. Therefore these post processing techniques are often not effective   because they have no knowledge of the post processed paths. Thus, there is a need for smarter solutions to the search problem.
Figure 3: Paths found by A* with different Post Smoothing techniques(A* PS)
A* Aesthetic Optimizations
This was the topic of a recent paper  that I co-wrote with Sven Koenig, Kenny Daniel and Ariel Felner and which was presented at AAAI'07. In the paper we presented a new solution to the search problem, called Theta*. Theta* is a variant of A* that propagates information along graph edges (to achieve a short runtime) without constraining the paths to graph edges (to find "any-angle" paths). Theta* is simple (to understand and to implement), fast and finds short and realistic looking paths. The pseudo code for Theta* has only four more lines than the pseudo code for A* and has a similar runtime, but finds paths that are nearly identical to the shortest paths (without post processing the paths found by Theta*!).
For simplicity, this article will focus on square grids in which a two-dimensional continuous environment is discretized into square cells that are either blocked (grey) or unblocked (white). Furthermore, we map vertices to the corners of grid cells as opposed to the centers of unblocked cells. Neither of these two assumptions is required for Theta* to function correctly. Our goal is to find a short and realistic looking path from the start location to the goal location (both at the corners of cells) that does not pass through blocked cells, as shown in Figure 1. Theta* was motivated by combining the desirable properties of two existing path planning techniques.
Visibility Graphs: Visibility graphs contain the start vertex, the goal vertex and the corners of all blocked cells . A vertex is connected via a straight line to another vertex if and only if it has line-of-sight to the other vertex, that is, the straight line from it to the other vertex does not pass through a blocked cell. Shortest paths on visibility graphs are also shortest paths in the continuous terrain, as shown in Figure 1 (right). However, path planning is slow on large visibility graphs since the number of edges can be quadratic in the number of cells.
Grids: Path planning is faster on grids than visibility graphs since the number of edges is linear in the number of cells. However, paths formed by grid edges can be sub-optimal and unrealistic looking since the path headings are artificially constrained , as shown in Figure 1 (left)
We assume an eight-neighbor grid throughout this article, where V is the set of all grid vertices, sstart in V is the start vertex of the search, and sgoal in V is the goal vertex of the search. c(s,s') is the straight line distance between vertices s and s', and lineofsight(s,s') is true if and only if they have line-of-sight. nghbrvis(s) in V is the set of neighbors of vertex s in V that have line-of-sight to s.
Figure 4: Pseudo Code for A*
Theta* builds upon A* (Figure 4)[*] and it's worth quickly introducing it here. A* uses h-values h(s) that approximate the goal distances of the vertices s in V to focus its search. A* maintains two values for every vertex s: (1) The g-value g(s) is the length of the shortest path from the start vertex to s found so far. (2) The parent parent(s) is used to extract the path after the search halts. Path extraction is done by repeatedly following the parent pointers from the goal vertex to the start vertex. A* also maintains two global data structures: (1) The open list is a priority queue that contains the vertices to be considered for expansion. (2) The closed list contains the vertices that have already been expanded. A* updates the g-value and parent of an unexpanded visible neighbor s' of vertex s (procedure ComputeCost) by considering the path from the start vertex to s [= g(s)] and from s to s' in a straight line [= c(s,s')], resulting in a length of g(s) + c(s,s'). It updates the g-value and parent of s' if this new path is shorter than the shortest path from the start vertex to s' found so far [= g(s')].
As noted in , the paths found by A* often look like they were constructed by someone who was drunk. This is both because the paths are longer than the shortest paths and because the path headings are artificially constrained by the grid. The most common technique for addressing this problem is to post process the paths found by A*. One such technique is to pull the paths tight, such that they look like "rubber bands" around obstacles. Post processing techniques shorten the paths found by A*, but are cosmetic in the sense that A* only considers paths that are constrained to grid edges during the search and thus the search cannot make informed decisions. This follows from the fact that the topology of the path is determined by the A* search, which has no knowledge of the shorter post processed paths. Furthermore, as we saw in Figure 3, choosing a post smoothing technique that efficiently finds paths with a toplogy that can be easily smoothed can be difficult. In some cases post smoothing cannot reduce the lengths of the paths constrained to grid edges at all, and the paths found by A* on grids can be up to 8% longer than the shortest path and very unrealistic looking. We therefore develop Theta*, which considers paths that are not constrained to grid edges during the search and thus can make more informed decisions during the search.
Figure 5: Pseudo Code for Theta*
The key difference between Theta* (Figure 5) and A* is that Theta* allows the parent of a vertex to be any vertex, unlike A* where the parent must be a visible neighbor. Procedure Main and UpdateVertex are identical to that of Figure 4 and thus are not shown. We use the consistent straight line distances h(s) = c(s,sgoal) to focus the search. Theta* is identical to A* except that Theta* updates the g-value and parent of an unexpanded visible neighbor s' of vertex s by considering the following two paths (procedure ComputeCost):
Path 1: As done by A*, Theta* considers the path from the start vertex to s [= g(s)] and from s to s' in a straight line [= c(s,s')], resulting in a length of g(s) + c(s,s') (Line 9).
- Path 2: To allow for any-angle paths, Theta* also considers the path from the start vertex to parent(s) [= g(parent(s))] and from parent(s) to s' in a straight line [= c(parent(s),s')], resulting in a length of g(parent(s)) + c(parent(s),s') if s' has line-of-sight to parent(s) (Line 4). The idea behind considering Path 2 is that Path 2 is no longer than Path 1 due to the triangle inequality if s' has line-of-sight to parent(s).
Figure 6: Theta* updates a vertex according to Path 1 (left) and Path 2 (right)
Theta* updates the g-value and parent of s' if either path is shorter than the shortest path from the start vertex to s' found so far [= g(s')]. For example, consider Figure 6 where B3 (with parent A4) gets expanded. B2 is an unexpanded visible neighbor of B3 which does not have line-of-sight to A4 and thus is updated according to Path 1 (right). C3 is an unexpanded visible neighbor of B3 which does have line-of-sight to A4 and thus is updated according to Path 2 (left).
Figure 7: Example Trace of Theta*
Figure 7 shows a complete trace of Theta*. Each vertex is labeled with its g-value and an arrow pointing to its parent vertex. The hollow circle indicates which vertex is currently being expanded. The start vertex A4 is expanded first, followed by B3, B2 and C1.
Figure 8: Theta* Path (blue) versus A* Path (red)
Figures 8 compares the path found by Theta* (blue) and the path found by A* (red) on a game map from Bioware's popular RPG Baldurs Gate, which has been discretized into a 100*100 square grid. The Theta* path is significantly shorter and more realistic looking than the path found by A*. Furthermore, notice that a post processing step would not be able to smooth the A* path into the Theta* path because the topologies of the two paths are different.
Line-of-sight checks can be performed very efficiently with only integer operations on square grids. The reason for this is that performing a line-of-sight check is similar to determining which points to plot on a raster display when drawing a straight line between two points. The plotted points correspond to the cells that the straight line passes through. Thus, two vertices have line-of-sight if and only if none of the plotted points correspond to blocked cells. This allows Theta* to perform its line-of-sight checks with a standard line-drawing method from computer graphics  that uses only fast logical and integer operations rather than floating-point operations, as shown in Figure 9 where grid represents the grid and grid[x,y] is true if and only if the corresponding cell is blocked. For simplicity, the pseudo code in Figure 9 returns true for paths that pass between diagonally touching blocked cells. However, Theta* is complete and correct whether or not paths are allowed to pass between diagonally touching blocked cells.
Figure 9: Pseudo Code for Line-of-Sight checks on a square grid
While Theta* is not guaranteed to find shortest paths in the continuous environment (for reasons explained in ), it does find shortest paths a large percentage of the time. For example, in Figure 10, Theta* found the shortest path in the continuous environment from the large red dot to each blue dot. We performed an extensive analysis using both small and large square grids from Bioware's popular RPG Baldur’s Gate (game maps) and square grids with given percentages of randomly blocked cells (random maps).
We found that on average the ratio of the lengths of the paths found by Theta* and the shortest paths was 1.007 on game maps and 1.002 on random maps. This is significantly better than the 1.04 ratio for paths found by A* (remember that A* paths can be up to 8% longer than the shortest paths). Theta* was only approximately a factor of 2 slower than a version of A* that was optimized for performance using the octile distance heuristic (to significantly reduce the number of expansions and thus the runtime). However, when you incorporate the post smoothing technique the runtimes can far more favorable for Theta*. While Theta* was slower than A* PS with the octile heuristic, it was significantly (approximately a factor of 2) faster than A* PS with the straight-line heuristic. Furthermore it is worth noting that on NavMeshes highly optimized heurisitcs such as the octile heuristic do not exist. Theta* is orders of magnitude faster than standard implementations of A* searches on visibility graphs[*].
Figure 10: Shortest paths found by Theta*
I hope this article will serve to highlight the usefulness of any-angle path planning methods for efficiently finding short realistic looking paths. For more information on Theta* I suggest taking a look at the original paper  or visiting our any-angle path planning web page. If you like Theta*, you may also like Field D* , which uses linear interpolation to find any-angle paths, but is restricted to regular grids composed of squares.
If you have specific questions or comments regarding anything described in this article, please feel free to contact me.
[*] open.Insert(s,x) inserts vertex s with key x into open. open.Remove(s) removes vertex s from open. open.Pop() removes a vertex with the smallest key from open and returns it.
[*] Visibility graphs have been studied extensively in robotics. Thus, many optimizations exist such as reduced visibility graphs, plane sweeps and nearest neighbor tricks, which can significantly reduce runtimes, especially in sparse outdoor environments. However, for cluttered indoor environments, the quadratic worst case complexity of visibility graphs significantly degrades their performance. Furthermore, these optimizations are far more complex than A* or Theta*.
Theta*: Any-Angle Path Planning on Grids A. Nash, K. Daniel, S. Koenig and A. Felner (2007) Proceedings of the AAAI Conference on Artificial Intelligence, pp. 1177--1183  Download (PDF)
Comparison of Different Grid Abstractions for Pathfinding on Maps Y. Bjornsson, M. Enzenberger, R. Holte, J. Schaeffer and P. Yap (2003) Proceedings of the International Joint Conference on Artificial Intelligence, pp. 1511-1512  Download (PDF)
Principles of Robot Motion  H. Choset, K. M. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. E. Kavraki and S. Thrun (2004) MIT Press (google books entry)
AI Game Programming Wisdom 2: Search Space Representations  P. Tozour (2004) Charles River Media, pp. 85-102 Purchase
Game Programming Gems: A* Aesthetic Optimizations  S. Rabin (2000) Charles River Media, pp. 264-271 Purchase
Using Interpolation to Improve Path Planning: The Field D* Algorithm  D. Ferguson and A. Stentz (2006) Journal of Field Robotics, Volume 23, Issue 2, pp. 79-101 Download FILE
An Algorithm for Planning Collision-free Paths among Polyhedral Obstacles  T. Lozano-Perez and M. Wesley (1979) Communication of the ACM, Volume 22, pp. 560-570 Download FILE
Grid-Based Path-Finding  P. Yap (2002) Proceedings of the Canadian Conference on Artificial Intelligence, pp. 44-55 Download FILE
Formal Basis for the Heuristic Determination of Minimum Cost Paths  P.E. Hart, N.J Nilsson, B. Raphael (1968) IEEE Transactions on Systems Science and Cybernetics, Volume 4, Issue 2, pp. 100-107 Download FILE
Amit's Game Programming Information  (2000) A. Patel Online
Algorithm for Computer Control of a Digital Plotter  J. Bresenham (1965) IBM Systems Journal, Volume 4, Issue 1, pp. 25-30 Download FILE