Theta*

For the simplest version of Theta*, the main loop is much the same as that of A*. The only difference is the $\backslash text\{update\}\; \backslash \_\; \backslash text\{vertex\}()$ 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.{{citation needed|date=December 2016}}

Adapted from.{{Cite web|url=http://idm-lab.org/bib/abstracts/papers/aaai07a.pdf|title=Theta*: Any-Angle Path Planning of Grids}}

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

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;

}

}

}

The following variants of the algorithm exist:{{citation needed|date=December 2016}}

• Lazy Theta*{{Cite web | url=http://idm-lab.org/bib/abstracts/papers/aaai10b.pdf | title=Lazy Theta*: Any-Angle Path Planning and Path Length Analysis in 3D | website=idm-lab.org | first1=Alex | last1=Nash | first2=Sven | last2=Koeni | first3=Craig | last3=Tovey}} – 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*

• Any-angle path planning
• A*

{{reflist}}

{{DEFAULTSORT:Theta}}

Category:Graph algorithms

Category:Path planning

Category:Search algorithms

Category:Game artificial intelligence