Theta*
Introduction '''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  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.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) === Line-of-sight algorithm ===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 = dy) {      if(x0 == x1) {        return true;      }      e += dy;      x0 += sX;    }    if(e2
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*
See also * Any-angle path planning* A*
References