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

Swamp Search

Grid şeklindeki haritalar, yapıları basit olduğundan ve grid üzerinde hareket edecek olan nesnenin (robot, oyun karakteri vs.) hareketi gerçek bir nesneden çok daha basit olduğundan bu haritalar için birçok heuristic yöntemi üretilebilir. Jump Point Search algoritmasında olduğu gibi yeni algoritmaların genelde iyileştirmeye çalıştıkları konu değerlendirilen node sayısı oluyor. Swamp Search algoritması da node sayısını iyileştiren algoritmalardan bir tanesi.

swamp

Algoritma harita içindeki swamp, yani bataklık alanları buluyor. Bataklık alanları şöyle açıklayabiliriz: Elimizde, grid üzerinde bir nokta kümesi olduğunu varsayalım. Bu kümenin dışında kalan tüm nokta çiftlerinin arasındaki en kısa yolları da hesapladığımızı düşünelim. Eğer bu kısayollardan hiçbiri elimizdeki kümeden geçmiyorsa bu alan bataklık olarak adlandırılır (Yukarıdaki resimde S = \{S1, S2, S3, S4\} kümesi bataklık olarak değerlendirilebilir). Eğer tüm bataklık alanları hesaplayabilirsek, iki nokta arasındaki yolu hesaplarken bu alanları yoksayabiliriz. Bu da çok fazla engelin olduğu bir haritada işimizi epey kolaylaştıracaktır. En azından şimdilik öyle görünüyor. Bakalım :)

Algoritmanın ilk adımında seed (tohum) olarak adlandırılan noktaları bulmak gerekiyor. Bu noktalar için basitçe bataklıkların yetişeceği noktalar denilebilir. Kendisi bir engel olmayan, düşey ve yatay eksende en az birer komşusu engel olan noktalar seed noktalar olarak alınabilir. Örneğin yukarıdaki resimdeki S4 noktası solundaki ve yukarısındaki noktalarda engel olduğu için bir seed noktasıdır.

İkinci adımda r=1 yarıçapı ile başlayarak seed noktayı genişletmek gerekiyor. Her seferinde seed noktadan en fazla r adımda ulaşılabilecek noktaları buluyoruz. Bu bizim bataklık olarak belirlediğimiz bölge oluyor.

Son adımda ise, ikinci adımda belirlediğimiz bataklıktaki noktaların sağlamasını yapmamız gerekiyor (gereksiz yere bir noktayı bataklığa dahil ettiysek çıkarmamız gerekecek). Bunun için bataklık bölgenin sınırındaki noktaları alıyoruz. (Sınırdaki noktalar = Bataklığa komşu olan ve bataklığa dahil olmayan noktalar). Sınırdaki her nokta çifti için en kısa yolu hesaplıyoruz. Eğer yeni bulduğumuz bataklık bu iki nokta arasındaki yolu uzatmışsa, yol üzerinde bulunan ve bataklığa dahil olan tüm noktaları bataklıktan çıkarıyoruz.

2. ve 3. adımları her seed nokta için, r‘yi arttırarak tekrarlayabiliriz. Bataklığı büyütme işi maksimum yarıçap, maksimum bataklık büyüklüğü gibi çeşitli kriterlere göre sınırlanabilir.

Benim bu algoritmada sevmediğim şey çok fazla statik olması. Evet hesaplama bittikten sonra A*’ın çalışmasını epey azaltabiliyor ama asıl sancılı olan da bu hesaplama süresi. Büyük haritalarda r kısıtını yüksek tutmak gerektiğinden değişken haritalar için kullanılabilir bir yöntem olmayacaktır. Az engelin bulunduğu haritalar içinse A*’ın çalışma zamanına yakınsayacaktır.

Neticede çok kullanışlı bir algoritma olmasa da mantığı ilginç. Detaylı okuma buradan yapılabilir.