Theta*
Variante di A* che consente ai segmenti del percorso di avere qualsiasi angolazione, invece di vincolare il tragitto alle otto direzioni cardinali della griglia.
A* semplice su una griglia può procedere solo a scatti di 45 gradi, quindi il percorso più breve verso un bersaglio con angolazione irregolare esce come uno zigzag a scalini, da lisciare poi a posteriori. Theta* risolve il problema già durante la ricerca: ogni volta che espande un nodo verifica se esiste una linea di vista libera dal nonno di quel nodo direttamente al vicino e, in caso positivo, salta il passaggio intermedio. I percorsi che ne risultano sono più brevi e più dritti, il tipo di linea che una persona seguirebbe davvero.
È stato introdotto da Kenny Daniel, Alex Nash, Sven Koenig e Ariel Felner (JAIR 2010). Il prezzo sono i controlli di linea di vista, più pesanti per nodo della semplice consultazione dei vicini di A*. Lazy Theta* rimanda questi controlli finché un nodo non viene effettivamente estratto dalla lista aperta ed elimina la maggior parte di essi.