Theta* es un algoritmo de planificación de rutas de cualquier ángulo que se basa en el algoritmo de búsqueda A* . Puede encontrar rutas casi óptimas con tiempos de ejecución comparables a los de A*. [1]
En la versión más simple de Theta*, el bucle principal es muy similar al de A*. La única diferencia es la función. En comparación con A*, el padre de un nodo en Theta* no tiene que ser vecino del nodo siempre que haya una línea de visión entre los dos nodos. [ cita requerida ]
Adaptado de. [2]
function theta * ( start , goal ) // Este bucle principal es el mismo que A* gScore ( start ) := 0 parent ( start ) := start // Inicializando conjuntos abiertos y cerrados. El conjunto abierto se inicializa // con el nodo de inicio y un costo inicial open := {} open . insert ( start , gScore ( start ) + heuristic ( start )) // gScore(node) es la distancia actual más corta desde el nodo de inicio hasta el nodo // heuristic(node) es la distancia estimada del nodo desde el nodo objetivo // hay muchas opciones para la heurística, como Euclidean o Manhattan closed := {} while open is not empty s := open . pop () if s = goal return reconstruct_path ( s ) closed . push ( s ) para cada vecino de s // Recorre cada vecino inmediato de s si el vecino no está en cerrado si el vecino no está en abierto // Inicializa valores para el vecino si // no está ya en la lista abierta gScore ( neighbourhood ) := infinity parent ( neighbourhood ) := Null update_vertex ( s , neighbor ) return Null function update_vertex ( s , neighbor ) // Esta parte del algoritmo es la principal diferencia entre A* y Theta* if line_of_sight ( parent ( s ) , neighbor ) // Si hay una línea de visión entre el padre(s) y el vecino // entonces ignora s y usa la ruta del padre(s) al vecino if gScore ( parent ( s )) + c ( parent ( s) ) , vecino ) < gScore ( vecino ) // c(s, vecino) es la distancia euclidiana de s al vecino gScore ( vecino ) := gScore ( padre ( s )) + c ( padre ( s ) , vecino ) padre ( vecino ) := padre ( s ) if vecino in open open . remove ( vecino ) open . insert ( vecino , gScore ( vecino ) + heuristic ( vecino )) else // Si la longitud de la ruta desde el inicio hasta s y desde s hasta // vecino es más corta que la distancia más corta actualmente conocida // desde el inicio hasta el vecino, entonces actualiza el nodo con la nueva distancia if gScore ( s ) + c ( s , vecino ) < gScore ( vecino ) gScore ( vecino ) := gScore ( s ) + c ( s , vecino ) padre ( vecino ) := s if vecino in open open . remove ( vecino ) open . insertar ( vecino , gScore ( vecino ) + heurística ( vecino )) función reconstruct_path ( s ) total_path = {s} // Esto reconstruirá recursivamente la ruta desde el nodo de destino hasta que se alcance el nodo de inicio si padre ( s ) ! = s total_path.push ( reconstruct_path ( padre ( s ))) de lo contrario devolverá total_path lineaDeVisualizacion ( nodo1 , nodo2 ) { sea x0 = nodo1.x ; sea y0 = nodo1.y ; sea x1 = nodo2.x ; sea y1 = nodo2.y ; sea dx = abs ( x1 - x0 ) ; sea dy = - abs ( y1 - y0 ) ; sea sX = - 1 ; sea sY = - 1 ; si ( x0 < x1 ) { sX = 1 ; } si ( y0 < y1 ) { sY = 1 ; } sea e = dx + dy ; while ( true ) { sea punto = getNode ( x0 , y0 ); if ( el punto no existe O el punto no es transitable ) { devuelve falso ; } if ( x0 == x1 AND y0 == y1 ) { devuelve verdadero ; } sea e2 = 2 * e ; if ( e2 > = dy ) { if ( x0 == x1 ) { devuelve verdadero ; } e += dy ; x0 += sX ; } if ( e2 <= dx ) { if ( y0 == y1 ) { devuelve verdadero ; } e += dx ; y0 += sY ; } } } Existen las siguientes variantes del algoritmo: [ cita requerida ]