For path planning in video games and robotics, one can discretize a continuous environment into an 8-neighbor grid with unblocked and blocked cells and search the grid graph with an optimal path-planning algorithm (such as A*) to find a shortest path on the graph. The resulting path can be longer than a shortest path in the continuous environment. A* with Post Smoothing shortens the path after the A* search by replacing parts of it with straight lines. However, the shortened path can still be long since shortening it does not change how it moves around around blocked cells. Any-angle path-planning algorithms, on the other hand, interleave the shortening and the search. One such any-angle path-planning algorithm, Theta*, is a simple extension of A*: When it expands a vertex v and generates a successor u, Theta* checks if the straight line between the parent of v and u intersects any blocked cell. If not, it changes the parent of u to be the parent of v if this decreases the g-value of u.
This applet demonstrates how A*, A* with Post Smoothing and Theta* operate on 8-neighbor grids with blocked and unblocked cells, where the vertices of the grid graph are placed at the corners of cells. Movement between two diagonally-touching blocked cells is not allowed.
Theta* uses the Euclidean distance between two vertices as heuristic, while A* and A* with Post Smoothing use the Octile distance instead. The search tree is displayed by drawing a line from each generated vertex to its parent. If a vertex has been expanded, the line to its parent is red. If it has been generated but not expanded, the line is beige. Blue vertices are in the open list, and the green path is the path from the start vertex to the goal vertex found by the search.
Sven Koenig (Professor)
Tansel Uras (Ph.D. student)
Jun Suh Lee (Undergraduate Student)
Jonathan Grant (Undergraduate Student)
Duncan Gammie (Undergraduate Student)