Theta*
Variant av A* som tillåter vägkanter i godtycklig vinkel i stället för att tvinga vägen att följa rutnätets åtta riktningar.
Vanlig A* på ett rutnät kan bara gå i steg om 45 grader, så den kortaste vägen till ett mål snett framåt blir en trappstegig sicksack som sedan måste slätas ut i efterhand. Theta* löser det under sökningen: varje gång en nod expanderas testar den om det går en fri siktlinje från nodens förälders förälder rakt till grannen, och om så är fallet hoppar den över mellansteget. Resultatet är kortare, rakare vägar som ser ut som något en människa skulle gått.
Algoritmen beskrevs av Kenny Daniel, Alex Nash, Sven Koenig och Ariel Felner (JAIR 2010). Priset är siktlinjekontrollerna, som kostar mer per nod än grannkollen i ren A*. Lazy Theta* skjuter upp kontrollerna tills en nod faktiskt tas ur kön och skär bort merparten av dem.