Theta*
Theta*
- Theta*** is an any-angle path planning algorithm that is based on the [[a*-search-algorithm]]. It can find near-optimal paths with run times comparable to those of A*.
Description For the simplest version of Theta, the main loop is much the same as that of A. The only difference is the <math>\text{update} \_ \text{vertex}()</math> function. Compared to A, the parent of a node in Theta does not have to be a neighbor of the node as long as there is a line-of-sight between the two nodes.
Pseudocode Adapted from.<syntaxhighlight lang="pascal"> function theta*(start, goal) // This main loop is the same as A* gScore(start) := 0 parent(start) := start // Initializing open and closed sets. The open set is initialized // with the start node and an initial cost open := {} open.insert(start, gScore(start) + heuristic(start)) // gScore(node) is the current shortest distance from the start node to node // heuristic(node) is the estimated distance of node from the goal node // there are many options for the heuristic such as Euclidean or Manhattan closed := {} while open is not empty s := open.pop() if s = goal return reconstruct_path(s) closed.push(s) for each neighbor of s // Loop through each immediate neighbor of s if neighbor not in closed if neighbor not in open // Initialize values for neighbor if it is // not already in the open list gScore(neighbor) := infinity parent(neighbor) := Null update_vertex(s, neighbor) return Null
function update_vertex(s, neighbor) // This part of the algorithm is the main difference between A and Theta if line_of_sight(parent(s), neighbor) // If there is line-of-sight between parent(s) and neighbor // then ignore s and use the path from parent(s) to neighbor if gScore(parent(s)) + c(parent(s), neighbor) < gScore(neighbor) // c(s, neighbor) is the Euclidean distance from s to neighbor gScore(neighbor) := gScore(parent(s)) + c(parent(s), neighbor) parent(neighbor) := parent(s) if neighbor in open open.remove(neighbor) open.insert(neighbor, gScore(neighbor) + heuristic(neighbor)) else // If the length of the path from start to s and from s to // neighbor is shorter than the shortest currently known distance // from start to neighbor, then update node with the new distance if gScore(s) + c(s, neighbor) < gScore(neighbor) gScore(neighbor) := gScore(s) + c(s, neighbor) parent(neighbor) := s if neighbor in open open.remove(neighbor) open.insert(neighbor, gScore(neighbor) + heuristic(neighbor))
function reconstruct_path(s) total_path = {s} // This will recursively reconstruct the path from the goal node // until the start node is reached if parent(s) != s total_path.push(reconstruct_path(parent(s))) else return total_path </syntaxhighlight>
Line-of-sight algorithm <syntaxhighlight lang="swift"> lineOfSight(node1, node2) { let x0 = node1.x; let y0 = node1.y; let x1 = node2.x; let y1 = node2.y; let dx = abs(x1 - x0); let dy = -abs(y1 - y0);
let sX = -1; let sY = -1; if (x0 < x1) { sX = 1; } if (y0 < y1) { sY = 1; }
let e = dx + dy; while (true) { let point = getNode(x0, y0); if (point does not exist OR point is not walkable) { return false; } if (x0 == x1 AND y0 == y1) { return true; } let e2 = 2 * e; if (e2 >= dy) { if (x0 == x1) { return true; } e += dy; x0 += sX; } if (e2 <= dx) { if (y0 == y1) { return true; } e += dx; y0 += sY; } } } </syntaxhighlight>
Variants The following variants of the algorithm exist:
- Lazy Theta* – Node expansions are delayed, resulting in fewer line-of-sight checks
- Incremental Phi – A modification of Theta that allows for dynamic path planning similar to D*