Hey merhaba ziyaretçi bize destek olmak ister misin ? Hemen Kayıt Ol Seni hiç sıkmadan kayıt edeceğiz endişelenmek bize destek olduğun için teşekkürler.



  • Toplam: 1 Oy - Ortalama: 5
  • 1
  • 2
  • 3
  • 4
  • 5
A-Star (A*) Algoritması
#1
Selamlar,

Bugün sizlere dünya çapında oldukça popüler olan a-star algoritmasından bahsetmek istiyorum.

A-Star Nedir?
Kısaca Linkleri görüntüleyebilmek için Kayıt ol manız veya Giriş yapmanız gerekiyor.Anlayışınız için teşekkürler.!, yol bulma ve veri görselleştirme gibi konularda kullanılan yaygın bir arama algoritmasıdır. Belirlenmiş node (grid) bir düzlem üzerinde arama yapmada kullanılan ideal yöntemlerden biridir. 1968 yılında Stanford Araştırma Enstitüsü (Linkleri görüntüleyebilmek için Kayıt ol manız veya Giriş yapmanız gerekiyor.Anlayışınız için teşekkürler.!) tarafından paylaşılmış, dünya çapında kabul görmüş bir algoritmadır.


Nerelerde Kullanılır?
Kullanım alanları çok yaygındır. Fakat bu forumda bizi ilgilendiren elbette oyun geliştirme eğilimli kullanımıdır.
Grid düzleme sahip oyunlarda (2D RPG, 2D/3D RTS benzeri) kullanımı yaygındır. Ağırlıklı olarak "nesnelerin hedefledikleri noktaya olan yollarını bulması" amacıyla kullanılmaktadır.

browserquest-4f720e2-intro.jpg
(Resim 1: Grid düzlem üzerinde çalışan örnek bir oyun - Linkleri görüntüleyebilmek için Kayıt ol manız veya Giriş yapmanız gerekiyor.Anlayışınız için teşekkürler.!)


A-Star algoritmasının aktif bir demosunu aşağıdaki linkte bulabilirsiniz:
Linkleri görüntüleyebilmek için Kayıt ol manız veya Giriş yapmanız gerekiyor.Anlayışınız için teşekkürler.!





En basit anlatımı ile, bir RTS oyununda X noktasına tıkladığınızda, seçili karakterin ilgili noktaya olan yolunu, aradaki engellerin etrafından dolaşarak bulması sistemini yazarken kullanabileceğiniz bir algoritmadır.




Algoritma Mantığı
Algoritma çok ileri seviyede kompleks olmamasına rağmen yazılı olarak anlatılması oldukça zor. Okumaya geçmeden önce aşağıdaki videoyu izlemenizi tavsiye ederim:




(Video 1: Kıskanılası aksanı ile "Linkleri görüntüleyebilmek için Kayıt ol manız veya Giriş yapmanız gerekiyor.Anlayışınız için teşekkürler.!" - Serinin devamında kendisi algoritmayı Unity'ye uyarlıyor, izlemenizi öneririm)


Kısaca birkaç tanım yaparak anlatımı kolaylaştırmak istiyorum:
  • Grid/Node Düzlem: Karelerden oluşan bir harita, alan. 
  • Grid/Node: Düzlemdeki karelerden biri. 
  • x: Anlatımda geçerli olacak olan başlangıç noktası
  • y: Anlatımda geçerli olacak olan hedef noktası


Algoritmaya göre, 
bir grid düzlemde X ile Y noktaları arasındaki en kısa mesafeyi, aralardaki engellerin etrafından, bulmanın yolu her bir noktanın kendi etrafındaki kareleri bir puanlama sistemi ile kontrol etmesi ve diğer karelerin puanları ile yaptığı karşılaştırmaya göre işleme devam edip etmeyeceğine karar verilmesi.

Çalışma sırasına göre,
  1. İşleme alınacak nokta başlangıç noktası olarak belirlenir
  2. İşleme alınan nokta etrafındaki 8 noktayı (yukarı, aşağı, sağ, sol ve 4 çapraz) belirler.
  3. Belirlenen gridler işleme alınır. 
  4. İşleme alınan her bir nokta üç değeri (puan) hesaplar: G, H ve F. 
    G: Karenin başlangıç noktasına olan uzaklığı
    H: Karenin varış noktasına olan uzaklığı
    F: G+H
  5. Bulunan F sonucuna göre, işleme alınmış olan tüm karelerin F değerlerinin karşılaştırılıp, F değeri en düşük olan karelerin tekrar belirlenmesi ve her biri için 2. adıma dönülmesi. İşleme alınan gridlerden biri ne zaman varış noktası olan grid olursa, 5. adıma geçilmesi
  6. Varış noktasına erişildiğinde algoritma tamamlanmış olur

Notlar:
  • 2. adımda belirtilen 8 grid, gereklilik durumuna göre değişebilir.
  • 4. adımda belirlenen puanlama sistemi aşağıdaki şekilde yürür:
    - Bir gridin sağındaki, solundaki, üstündeki, altındaki gridlere olan uzanlığı aradaki grid başına 10 birim olarak hesaplanır. Örneğin A gridi B gridinin 3 birim solundaysa, (arada 3 grid daha varsa) uzaklıkları 3*10=30 puan olarak hesaplanır.
    - Bir gridin çaprazındaki gridlere olan uzaklığı 14 puan olarak hesaplanır. Örneğin C gridi D gridinin 2 birim çaprazındaysa (arada 2 grid daha varsa) gridlerin uzaklığı 2*14=28 puan olarak hesaplanır.
  • 5. adımda, değeri en düşük değere eşit olmayan hiçbir grid tekrar işleme alınmaz
  • Hedef gride ulaşılana kadar 2-5 numaralı maddeler arasında döngü oluşur
  • Engel olarak tanımlanmış bir grid asla işleme alınmaz

Qaqg73.png
(Resim 2: A-Star Puanlama Algoritması çalışma örneği - Linkleri görüntüleyebilmek için Kayıt ol manız veya Giriş yapmanız gerekiyor.Anlayışınız için teşekkürler.!)


Yukarıdaki resimde, A noktası başlangıç, B noktası hedef olarak belirlenmiştir.
Gridlerin sol üzerinde yazan sayı A noktasına olan uzaklığı (G),
Gridlerin sağ üzerinde yazan sayı B noktasına olan uzaklığı (H),
Gridlerin ortasında yer alan sayı ise F değeri (G+H) olarak tanımlanmaktadır.
A noktasının etrafındaki 8 grid hesaba alınmıştır. 8 gridden F değeri en küçük olan kırmızı grid, en küçük değere (42) sahip olduğu için merkez noktası olarak kabul edilmiş ve bu kez de onun etrafındaki 8 grid işleme alınmıştır. Eğer 42 değerine sahip başka bir grid olsaydı, eş zamanlı olarak onun etrafındaki gridler de işleme alınacaktı.
Varış noktası (B) işleme alınana dek döngü bu şekilde devam edecektir. 



Yazılı olarak zannediyorum anlatabileceklerim bu kadar, ilgili videoyu ve aşağıdaki kaynakları okuyarak devamını keşfedebilirsiniz:
Linkleri görüntüleyebilmek için Kayıt ol manız veya Giriş yapmanız gerekiyor.Anlayışınız için teşekkürler.! | Sebastian Lague - A* Pathfinding EP01
Linkleri görüntüleyebilmek için Kayıt ol manız veya Giriş yapmanız gerekiyor.Anlayışınız için teşekkürler.! | A* Search Algorithm Wiki
Linkleri görüntüleyebilmek için Kayıt ol manız veya Giriş yapmanız gerekiyor.Anlayışınız için teşekkürler.! | Stanford A* Documentation



Teşekkürler

  Cevapla
#2
Çok güzel açıklamışsın tebrik ederim
|| Az olan çoğun ispatıdır ||
  Cevapla
#3
(17-05-2017, Saat: 14:26)undefined Nickli Kullanıcıdan Alıntı: Linkleri görüntüleyebilmek için Kayıt ol manız veya Giriş yapmanız gerekiyor.Anlayışınız için teşekkürler.!Çok güzel açıklamışsın tebrik ederim

Teşekkür ederim kardeşim.

  Cevapla
#4
Bunu bir VS'de form application olarak yada direk unity'de bir örneğini yapmak lazım aslında iyice anlamak için Big Grin oşuma gitti baya sistem daha önce duymuştum ama bu şekilde dinleyince daha da güzel olmuş eline sağlık dostum Big Grin
Bir gün her şey kodlanacak ... Idea

resim
  Cevapla
#5
(19-05-2017, Saat: 14:06)TheTudors Nickli Kullanıcıdan Alıntı: Linkleri görüntüleyebilmek için Kayıt ol manız veya Giriş yapmanız gerekiyor.Anlayışınız için teşekkürler.!Bunu bir VS'de form application olarak yada direk unity'de bir örneğini yapmak lazım aslında iyice anlamak için Big Grin oşuma gitti baya sistem daha önce duymuştum ama bu şekilde dinleyince daha da güzel olmuş eline sağlık dostum Big Grin

Teşekkürler kardeşim,
ben daha öne javascript ile yazmıştım bunun web versiyonunu duruma göre paylaşırım istersen.

  Cevapla
#6
çok güzel açıklanmış emeğinize sağlık
  Cevapla


Hızlı Menü:


Konuyu Okuyanlar: 1 Ziyaretçi