Theta*

2 boyutlu haritalarda yol bulmak için kullanılan algoritmalardan biri de Theta*. Bu algoritma da Jump Point Search (JPS), Swamp Search ve diğer hemen tüm yol bulma algoritmaları gibi A* tabanlı.

JPS, gereksiz node’ları atlayarak en kısa yolu bulduğu için gayet iyi bir algoritma. Fakat JPS’nin optimal olduğu durumlar, en azından ilk halinde, hareketin sadece 8 yöne yapıldığı durumlar için geçerli (Her açıda hareket için de bir JPS versiyonu var, o makaleyi henüz okumadım). Theta* ise bu kısıtı kaldırarak, hareketin herhangi bir açıyla yapıldığı durumdaki en kısa yolu buluyor.

En kısa yolu garanti etme kısmı A*’ın doğru h(x) fonksiyonu ile kullanıldığı zaman optimal çözümü bulması ile aynı. Burada değişen kısım ise, g(x) fonksiyonu olarak bir önceki node’un maliyetini almaktansa 2 önceki node’dan mevcut node’a uzaklığı hesaplıyoruz.

Diyelim ki aşağıdaki haritada maviden kırmızıya gideceğiz.

initial

A*, JPS veya diğer tüm sadece 8 yöne hareket eden algoritmaların bulacağı yol aşağıdaki gibi olacak.

a_star

Theta*’ın farkı ise burada ortaya çıkıyor. Adım adım incelersek, Theta* algoritması ilk adımı aşağıdaki gibi atacak.

theta_1

Başlangıç noktasına p_0, ilk adımdan sonra ulaştığımız noktaya ise p_1 diyelim. Sonrasındaki adımda ise kırmızı noktaya ulaşacak. Ulaştığında ise, sonucu dönmektense bu noktaya p_0‘dan direkt olarak bir yol var mı diye kontrol edip, eğer varsa p_1‘i sonuçtan çıkaracak ve sonuç p_0 -> p_1 olacak.

theta_2

Böylece 2 nokta arasındaki Öklid uzaklığını yani en kısa yolu bulmuş olduk.

Theta*, özellikle JPS’ye göre daha maliyetli bir algoritma. A*’a getirdiği ek maliyet ise her adımda daha kısa bir yol var mı diye kontrol edilmesi.

Son olarak, uzaklıkların farkının görülebilmesi açısından aşağıdaki gibi bir haritada deneme yaptım.

last_1 Sonuçlar aşağıdaki gibi;

Algoritma Yol Uzunluğu
A* 7.242
JPS 7.242
Theta* 7.064