Theta*
Variante de A* que permite tramos de ruta en cualquier ángulo en lugar de obligar al camino a seguir las ocho direcciones de la cuadrícula.
El A* clásico sobre una cuadrícula solo puede avanzar en pasos de 45 grados, así que la ruta más corta hacia un objetivo situado en diagonal sale como una escalera en zigzag que luego hay que suavizar. Theta* lo resuelve durante la propia búsqueda: cada vez que expande un nodo comprueba si hay línea de visión despejada desde el abuelo del nodo hasta el vecino, y de ser así se salta el paso intermedio. Los caminos resultantes son más cortos y rectos, del tipo que una persona recorrería de verdad.
Lo presentaron Kenny Daniel, Alex Nash, Sven Koenig y Ariel Felner (JAIR 2010). El precio son las comprobaciones de línea de visión, más costosas por nodo que la simple consulta de vecinos de A*. Lazy Theta* aplaza esas comprobaciones hasta que un nodo sale realmente de la lista abierta y elimina la mayoría.