Oyunlarda yol bulma algoritmaları hakkında kısaca

Genişlik ilk arama

Genişlik İlk Arama – her yöne tek tip keşif.

Bu algoritma, grafik teorisi problemlerini çözmede, bir yol bulmada, dünyaların prosedürel olarak üretilmesinde, baskılı devre kartlarının tasarımında ve daha birçoklarında kullanılır, ancak bugün bir grafikteki en kısa yolu bulmamız gerekiyor.
Henüz piyasaya sürülmemiş S&Box oyunu (Garry’nin modunun halefi) için bir mod oluştururken, odalardan prosedürel olarak bir harita oluşturuyoruz, odaların her biri formatta bir indeks alıyor. [x, y, z]. Burada x,y -32.768 ile 32.767 arasında ve z 0 ile 2 arasında değişebilir, çünkü şimdi sadece 3 katın olacağını varsayıyoruz.
Modumuz kooperatif kaçış olmalı ve oyuncular her zaman 1 yerde değil. Dolayısıyla rakipler AI. En yakındaki oyuncuyu ararlar ve ona doğru hareket ederler. Gerçekten en yakın oyuncuyu bulmak için koordinatlarını karşılaştıramazsınız. Odalar şu şekilde düzenlenebileceğinden:

Resmin biraz yanlış olduğunu hemen söyleyeceğim. Odalar arasındaki mesafeler her zaman aynıdır ve odalar eşittir.
Koordinatlı olarak, 0:0’daki kırmızı nokta -1:0 içindeki mor noktaya daha yakındır, ancak ona ulaşması 1:1’deki mor noktaya göre çok daha uzun sürer. Burada Genişlik İlk Aramayı uygulayabiliriz.
Kırmızı noktada, mevcut odanın dizinini alan en yakın oyuncuyu bulma yöntemi çağrılır – [0,0,z] Bu odayı ziyaret edildi olarak işaretler. Daha sonra bu indekslerle odaların saklandığı (graf teorisinde tepe noktalarıdır) sözlüğe döner ve odanın hangi pasajlara sahip olduğunu (graf teorisinde kenarlardır) bulur, sonra onların hangi indekslerinin zaten olduğunu kontrol eder. ziyaret edilir ve 1’den fazla ziyaret edilmemiş köşeler varsa, bu odayı ziyaret edilmeyen taraf sayısı ile kuyruğa (Dal – dallanma) ekler. 1 iplik bir seferde sadece 1 işlem yapabildiğinden, 0:1’den 1:1 ve -1:1’e hemen hareket edemiyoruz, bu nedenle ilk önce mevcut konum ile sonraki konum arasındaki en küçük açıya sahip yönde hareket ediyoruz. trigonometrik daireye göre. Bir oyuncu bulduğumuzda oda indeksli bir liste gönderiyoruz, elimizde olacak :([0,0,z]; [0,1,z]; [1:1,z])
Bu algoritmanın hızı = O(Köşeler + Kenarlar)

Dijkstra’nın algoritması

Dijkstra Algoritması – A.k.a. Tekdüzen Maliyet Arama Algoritması. En iyi rotaları bulmak için kullanılır
Odalar arasındaki geçişin farklı olduğu görülür. Örneğin, kapısı olmayan bir odaya girmek için geçiş maliyeti 1 puan, kapı olduğu yerde ise 1.2 puan, çünkü açılması zaman alıyor. Buna göre yolu en ucuz yoldan seçebiliriz. Odalar arasındaki geçişlerimiz her zaman eşit olduğundan ve oda içindeki hareket hızı hiçbir şeye bağlı olmadığından bu algoritmayı kullanmadık. Ayrıca, bu algoritma tüm düğümler için “en ucuz” yolları bulmayı gerektirir. Dijkstra’nın algoritmasının uygulanması genişlik öncelikli aramaya benzer, ancak hücreler arasındaki geçiş maliyetlerinin bir listesi görünür ve bir yol seçerken dikkate alınır.
Bu algoritmanın hızı = O(N2) – doğrusal arama için
Bu algoritmanın hızı = O(M Log N) – ikili aramada

Algoritma görselleştirme:

UPD: Burada A* yok çünkü bununla ilgili bilgiler oldukça hacimli, ancak makaleyi beğendiyseniz, bir dahaki sefere A* algoritması hakkında konuşabilirim

Similar Posts

Leave a Reply

Your email address will not be published.