Yol bulma algoritmaları özellikle oyun, coğrafi bilgi sistemleri ve network gibi alanlarda kullanılan, temelini matematikteki graph’lardan alan bilgisayar biliminin en önemli konularından birisidir. Yolu mümkün olabildiğince kısaltıp bir aracın yakıt tüketimini azaltmak, oyunlarda sanal karakterin yapay zekasının bir parçası olarak bulunduğu noktadan gideceği noktaya izleyeceği yolun tespiti, network paketlerinin yönlendirilmesi sırasında izleyeceği en uygun yolun belirlenmesi gibi konularda farklı algoritmalar öne çıkar.

Bu algoritmaların kullanılan alana bağlı olarak farklı pek çok varyasyonu olabildiği gibi parametreler de olabildiğince sağlıklı girilmelidir. Zira, bir aracı en kısa yola yönlendiren bir algoritma zemini bozuk toprak yolları, tepeleri hesaba katmadan, trafik faktörü gibi konuları gözardı ederek en kısa yolu gösterdiğinde yarardan çok zarara sebep olabilir. Bu sebeple, mesafe olarak en kısa yolu değil de, en uygun en kısa yolu seçmek gerekebilir.

Bu temsiller graph’lar ile yapılır. Örneğin A, B, C şehirleri birer node veya diğer ismiyle vertex, yollar ise edge’lerdir. Bu graph’ta edge'ler hem gidiş hem de dönüş olduğundan bu bir undirected graph’tır. Kapalı olduğundan cyclic’tir.

Açık olsaydı acyclic graph olacaktı.



Şayet, tek yönlü gidiş olsa idi directed graph olacaktı.



Undirected graph’ın en önemli yönlerinden birisi gidiş – dönüşün farklı weight'ler ile temsil edilebilir olmasıdır. Örneğin B şehrinin bulunduğu konumun yüksekliği C şehrinden biraz yüksek olabilir ve B şehrinden C şehrine giderken aşağıya doğru gidildiğinden, C'den B'ye gitmeye göre daha kolaydır. Bu sebeple B şehrinden C şehrine gidişe verilen değer 5 birim ise, C şehrinden B şehrine dönüşün değeri 6 birim ile ifade edilebilir.



En kısa yol, havayolu firmaları için uçak yakıtı çok maliyetli olduğundan çok kritik iken, bir oyunda karakterin en kısa yol yerine biraz daha uzun olan alternatif yolu tercih etmesi çok da önemli değildir. Aksine doğal bir görünüm dahi yaratabilir. Zira gerçek hayatta insanlar ve diğer canlılar en kısa yola eğilim gösterseler de, en ince ayrıntısına kadar hesap yaparak mümkün olabilecek en kısa yolu izlemeye çalışmazlar. Çizilen yol sezgiseldir.

En kısa yolu bulma işlemi, vertex ve edge sayısına bağlı olarak çok fazla zaman alabilir. Algoritmanın kompleksitesine bağlı olarak bu zaman vertex, edge sayısına bağlı olarak hızla katlanabilir. Oyunlarda zaten fazlasıyla yük bulunmakta iken, bir de en kısa yolun hesaplanmaya çalışılması fazlasıyla sıkıntıya yol açabilir. Bu sebeple, en kısa yol olduğundan emin olunan algoritmalar değil de, sezgisel algoritmalar kullanılır. Karakter belki biraz daha uzun olan yolu izler ama bu yolu hesaplaması çok daha kısa sürer.

Bu noktada, A* algoritması öne çıkar. Algoritma heuristic fonksiyonun kalitesine bağlı olarak en kısa yolu başarılı bir şekilde hesaplayabilmektedir. Ancak ondan önce Dijkstra algoritmasına değinmek istiyorum. Zira A* ve Dijkstra birbirine çok benzemekle beraber Dijkstra’nın farkı heuristic fonksiyonun 0 olmasıdır. Yani,

A*;
f(x) = g(x) + h(x)

Dijkstra;
f(x) = g(x)

g: Gerçek mesafe
h: Sezgisel mesafe

Dijkstra’da başlangıç vertex’inden tüm vertex’lere olarak uzaklık kesin bir sonuçla elde edilir, A*’da ise sadece hedefe odaklı heuristic yaklaşım sergilenir. Dijkstra ile elde edilen en kısa yol kesin olarak en kısa yoldur.

Şimdi bellekte graph’ların tanımlanması konusundan bahsettikten sonra C++ kodu ile açıklamaya başlamak istiyorum. Kodu Google C++ standartlarına göre yazdım. Standarda Google C++ Style Guide linkinden ulaşılabilir.

Öncelikle, vertex'lerin birbiriyle bağlantısını (edge’leri) tutmanın başlıca iki ayrı yolundan bahsetmek istiyorum. İlki "adjacency matrix", ikincisi ise "adjacency list". Yani, ilk yöntemde vertexlerin birbiriyle olan bağlantısı matriste tutulurken diğerinde liste halinde tutuluyor.



(Bu resim alıntıdır)

Her ikisinin birbirine göre avantajları ve dezantajları bulunmakta. Graph, adjacency matrix ile temsil edilmişse, kodu yazması ve matriste dolaşması daha kolay olurken, bu matris üzerinde birbiriyle bağlantısı olmayan vertex bilgisi de tutulduğundan kullanılan gereksiz alan fazladır. Bu sebeple büyük graph’larda gereksiz alan kullanımı muazzam boyutlara ulaşabilir.

Adjacency list kullanılmış ise, geliştirmesi adjacency matrix’e daha fazla zaman alsa da, gerekli olduğu kadarıyla bellek kullanılır.

Ben yazıma adjacency list ile devam edeceğim. Zira, adjacency list ufak graph’lar için gerekli olmasa da boyut büyüdükçe bir zorunluluk halini alabiliyor. Bu sebeple, geleceği düşünerek ihtiyaç olabileceğinden böyle bir tercih yapıyorum.


Adjacency matrix: Matriste görüldüğü üzere vertex'ler satır ve sütunlarla temsil ediliyor. Bu graph weighted olmadığından tüm değerler 1(bağlantı var) veya 0(bağlantı yok)'lardan oluşuyor. Örneğin 1'den 2'ye bağlantı olup olmadığına bakmak için 1. satıra gidip 2. sütuna bakıyoruz. Orada 1 yazdığından bağlantı olduğunu anlıyoruz.

Adjacency list: Adı üzerinde komşuluklar liste halinde tutuluyor. Her vertex'in bir linked list'i var ve herhangi bir komşuluk söz konusu ise o listeye ekleme yapılıyor. Örneğin 2. vertex'in listesine gittiğimizde 1, 5 ,3 ,4 ile bağlantısı olduğunu görüyoruz.


Şimdi kod üzerinden anlatımıma devam edip öncelikle vertex’in tanımlanmasından başlayacağım.

struct Vertex {
  int weight;
  int dest;
};

Vertex görüldüğü üzere weight ve dest(ination) bilgisi tutan bir yapı. Burada destination olarak belirtilen Vertex’e bağlı komşu vertex’in numarası, weight ise uzaklığı. Yani aşağıdaki çizimde görüleceği üzere dest 2, weight 3 ise şu şekildedir.

Bununla beraber, C++’ta struct görmek istemeyenler için alternatif bir vertex tanımlaması daha yapmak istiyorum. Google C++ standartlarına göre pasif olması, sadece data bulundurması durumunda struct kullanımında sakınca yoktur. Duruma bağlı olarak farklı tercihler ya da tanımlamalar da yapılabilir.

class Vertex {
 private:
  int weight;
  int dest;
 
  friend class Graph;
};

Devamında, Graph class’ını tanımlamaya başlıyoruz.

class Graph {
 private:
  list<Vertex*> *adjList;
  int vCount;
 public:
  ...

Görüldüğü üzere adjacency list'ler, adjList pointer’ı ile tutulmakta. Bu kısımda C++ STL’den faydalanarak list kullandım. Bu pointer, vertex listelerinin dizisini tutacak.  Bu listenin kaç tane olacağı yukarıda anlattığım üzere vertex sayısına bağlı o da vCount’ta tutulmakta. 

Bununla beraber, kod C’de yazılıyorsa bu kısımda en temel haliyle bir linked list’ler dizisi olacaktı. C++ STL list ile biraz daha derli toplu bir görüntü yakalamış olduk.

Şimdi bu class’ın constructor kısmından bahsedersem,

explicit Graph(int vCount) {
  adjList = new list<Vertex*>[vCount];
  this->vCount = vCount;
}

Öncelikle "explicit" keyword’ünü hatırlatmak isterim. Bu keyword ile,

Graph g = 4;

şeklinde bir atama ile vCount’u set etmiyor,

Graph g(4);

şeklinde bir kullanıma zorluyoruz.

Söz konusu kullanım, tek argümanı olan fonksiyonlar için bir Google C++ standartı.  

Devam edersem, bu constructor’da vertex sayısına (vCount) bağlı olarak listeler yaratıyoruz ve parametre ile gelen vCount değerini saklıyoruz. Tabii, devamında bu list<Vertex*> dizisini dinamik olarak yarattığımızdan destructor içerisinde kaldırmayı da unutmamalıyız.

Şimdi vertex ve edge ekleme kısmına gelelim,

Vertex* createVertex(int dest, int weight) {
  Vertex* newVertex = new Vertex;
  newVertex->dest = dest;
  newVertex->weight = weight;
  return newVertex;
}
 
void addEdge(int src, int dest, int weight) {
  Vertex* newVertex = createVertex(dest, weight);
  adjList[src].push_back(newVertex);
 
  /*newVertex = createVertex(src, weight);
  adjList[dest].push_back(newVertex);*/
}

Bu kısım klasik graph oluşturma yöntemlerinden birisi. Edge eklenir ve eklenirken source, destination ve weight bilgileri girilerek vertexler yaratılır. Görülen addEdge fonksiyonu directed graph yaratmaktadır. Comment olarak belirtilmiş ekstra satırlar eklenirse undirected graph yaratılabilir.

Adjacency list kısmında belirtildiği üzere her vertex’in kendine ait bir listesi vardır ve komşular bu listede belirtilir. Bir vertex’in komşularını elde etmek için tek yapılması gereken  adjList[index] ile o listeyi almak ve gezmektir.

Buradaki vertex ve edge ekleme yöntemine uygun kullanım şu şekildedir,

Graph g(4);
g.addEdge(0, 1, 3); // 0->1 (3)
g.addEdge(0, 2, 2); // 0->2 (2)
g.addEdge(1, 2, 3); // 1->2 (3)
g.addEdge(2, 3, 5); // 2->3 (5)
g.addEdge(3, 0, 2); // 3->0 (2)

Graph üzerinde gezinme kısmına gelirsem, öncelikle bir binary tree üzerinden örnek vermenin daha anlaşılır olacağını düşünmekteyim. Daha anlaşılır olması için aşağıdaki resimlere de bakınız. Diyelim ki, DFS(depth first search) ya da BFS(breadth first search) algoritması ile binary tree’yi dolaşmak istiyoruz. DFS bildik recursive kullanım ile en dibe ulaşıp yukarıya çıkma şeklinde dolaşmaktır. Ancak ağaç çok derin ise stack overflow gerçekleşebileceğinden bunun yerine C++ STL’deki stack veri yapısından faydalanılarak buna uygun implementasyon yapılabilir.


(Resim alıntıdır)

Fakat asıl konumuz BFS olduğu için asıl ona yönelmek istiyorum. Zira buradan ilerleyerek gideceğiz. Öncelikle burada önemli olan nokta BFS’te level level dolaşılmasıdır. Yani DFS’de olduğu gibi bir koldan başlayıp en ucuna gidene kadar ilerlemez, önce aynı leveldaki tüm node’ları dolaşır ondan sonra alt level'a iner. Yani BFS ile dolaşırken vertex’imizin komşularını, en yakınında olanları gezerek ilerleyeceğiz.

void bfs(int index) {
  bool* visited = new bool[vCount];
 
  for (int i = 0; i < vCount; i++) {
    visited[i] = false;
  }
 
  // İlk vertex'i queue'ya ekle
  queue<int> q;
  q.push(index);
  visited[index] = true;
 
  // Queue dolu olduğu sürece işleme devam
  while (!q.empty()) {
    int current = q.front();
    q.pop();
 
    cout << current << endl;
 
    // Komşuların listesini al
    list<Vertex*> neighbours = adjList[current];
   
    list<Vertex*>::iterator itr;
    for (itr = neighbours.begin(); itr != neighbours.end(); itr++) {
      int destIndex = (*itr)->dest;
    
      // Komşu ziyaret edilmemişme listeye ekle  
      if (!visited[destIndex]) {
        q.push(destIndex);
        visited[destIndex] = true;
      }
    }
  }
 
  delete[] visited;
}

BFS algoritmasında görüldüğü üzere komşular, en yakında olanlar gezildiğinden haliyle queue kullanılır. Kod’ta görülen vertex indexlerini tutan C++ STL queue’dur.

"visited" dizisini açıklarsam, "visited" adı üzerinde vertex’in ziyaret edilip edilmediğini kontrol etmek için kullanılır, diğer yandan bu işlem yapılmazsa, bu bir cyclic graph ise sürekli dolaşacaktır.

İlk başlangıç vertex’inin index’i queue’ya push edilir, bu index tutulur, queue’dan pop edilir, komşularına erişilir ve bunların indexleri ziyaret edilme durumuna göre push edilir ve ziyaret edilmiş şeklinde işaretlenir. Queue boş ise durulur. Özeti budur.

Şimdi bunun üzerine meşhur Dijkstra algoritmasına geçebiliriz. Daha önceden söylediğim üzere, bir vertex’ten diğer vertex’lere en kısa yolu bulan bu algoritma kesin sonuç verir ve heuristic değildir. Ancak bunun maliyeti de haliyle büyüktür. Bizim için önemli olan nokta, başlangıç vertex’inden bitiş vertex’ine giden yoldur ve bu yol bunu bir oyunda kullanacak isek en iyi yol olmak zorunda olmayabilir. Biraz daha uzun olur ama hesaplaması daha kolaysa işimize gelir.

Neyse, bu aşamada konumuz Dijkstra iken ona odaklanalım,

void dijkstra(int index) {
  unsigned int* distance = new unsigned int[vCount];
  bool* visited = new bool[vCount];
 
  for (int i = 0; i < vCount; i++) {
    distance[i] = -1;
    visited[i] = false;
  }
 
  // Optimizasyon için priority queue
  priority_queue<iPair, std::vector<iPair>, CompareVertexDistances> pq;
  
  // İlk vertex'i queue'ya ekle
  pq.push(pair<int, int>(index, 0));
  distance[index] = 0;
  visited[index] = true;
 
  // Queue dolu olduğu sürece işleme devam
  while (!pq.empty()) {
    cout << pq.top().second << endl;
    int currentIndex = pq.top().first;
    list<Vertex*> neighbours = adjList[currentIndex];
    pq.pop();
 
    list<Vertex*>::iterator itr;
    for (itr = neighbours.begin(); itr != neighbours.end(); itr++) {
      int destIndex = (*itr)->dest;
      if (!visited[destIndex]) {
        unsigned int temp = distance[currentIndex] + (*itr)->weight;
 
        if (distance[destIndex] > temp) {
          distance[destIndex] = temp;
        }
 
        pq.push(iPair(destIndex, distance[destIndex]));
        visited[destIndex] = true;
      }
    }
  }
 
  // Mesafeleri listele
  for (int i = 0; i < vCount; i++) {
    cout << distance[i] << endl;
  }
 
  delete[] visited;
  delete[] distance;
}

Gördüğünüz üzere BFS yine orada.

Dijkstra’yı baştan sona anlatmaya başlarsam, öncelikle daha önceden anlattığım visited’ın yanında distance array’ini de görürüz. Bu distance array’i başlangıç vertex’i için haliyle kendisine olan mesafe 0 olduğundan 0’dır. Bunun dışında olan tüm vertex’ler -1’dir. Dijkstra algoritmasında, -1 olarak belirtilen değerler gerçekte sonsuz olarak ifade edilmiştir. Biz ise bilgisayarda sonsuzluğu ifade edemeyeceğimizden unsigned bir veri tipinde mümkün olabilecek en büyük değeri veriyoruz. Aslında -1 olarak belirtilen değer unsigned ise, 0xFFFFFFFF (32 Bit),  0xFFFFFFFFFFFFFFFF (64 Bit)'tir.

Burada mümkün olan en büyük sayıyı vermenin amacı, başlangıçta karşılaştırmaları yaparken karşılaştırma yapabileceğimiz bir şeyin, mümkün olan en büyük değerin olmasıdır. Küçük olan değer büyük olanın yerine geçeceğinden bunlar değiştirilir. Dijkstra’da vertex vertex ilerledikçe distance’lar güncellenir. Bu şekilde en kısa olanı ilerleyerek hesaplar.

Şimdi burada önemli olan bir diğer nokta, queue yerine priority_queue kullanılması. Buradaki amaç bu işlemi daha optimize bir şekilde gerçekleştirmek. Zira, standart haliyle Dijkstra’nın kompleksitesi  iken optimize edilmiş haliyle  dir.

Buradaki queue aslında C++’ta STL’in bir lütfu denilebilir. Diğer yandan min-heap veri yapısı oluşturmamız gerekecekti. Burada bahsedilen heap, low level ile uğraşanların aklına ilk gelen, bellek alanı olan heap değil, veri yapısı olan heap’tir. Heap tree’sinde, parent’ların değeri children’ların değerinden büyüktür ya da küçüktür. Bu heap’in min-heap ya da max-heap oluşuna göre değişir. Özetle, priority queue sayesinde bizim queue’ya gönderdiğimiz elemanlar sıralanır. Böylece, en küçük olan eleman en başa geçmiş olur.


(Resim alıntıdır)

Ancak bizim amacımız için C++ STL’in default olarak sunduğu priority queue doğrudan işe yaramaz. Zira, küçükten büyüğe değil de, büyükten küçüğe doğru sıralamaktadır. Bununla beraber vertex index’i ile distance’ı pair olarak göndereceğiz. Bu sebeple, kendi comparator class’ımızı yazmamız lazım. Aslında sadece tek bir integer gönderecek olsaydık greater<int> yazmamız da yeterli olabilirdi ancak yaptığımız iş biraz daha sofistike. vertex index’inin yeri distance’a bakılarak belirlenecek.

Öncelikle her yere pair<int, int> yazarak kodun satır uzunluğunu uzatıp 80 karakteri geçerek standartların dışına çıkmamak için yukarda typedef tanımlaması yaparak pair<int, int> ‘ı iPair olarak belirliyoruz. 

typedef pair<int, int> iPair;

Devamında comparator class’ımızı yazıyoruz. Class’ımız görüldüğü üzere sadece vertex’lerin mesafelerini kıyaslamak gibi bir misyona sahip.

class CompareVertexDistances {
 public:
  bool operator()(const pair<int, int>& v1, const pair<int, int>& v2) {
    if (v1.second > v2.second)
      return true;
    else
      return false;
  }
};

Nihayet sıra A* algoritması, A Star algoritması, Türkçe adıyla A Yıldız algoritmasına geldi. Buraya kadar temelden başlayarak sürekli bir şeyler ekleyerek geldik. Bundan sonrası da öyle olacak. Zira bahsettiğim üzere A* algoritmasının en önemli farkları hedef vertex’e odaklı ve sezgisel olması.

A* algoritmasında, vertex’lerden bitiş vertex’ine olan mesafeyi sezgisel olarak hesaplamamız gerekecek. Bu mesafe dikkat edilirse, edgeler üzerinden değil doğrudan olan mesafedir. Yani, A ve B şehri arasında bir dağ varsa, çevresinden dolanan yol 80 km uzunluğunda olabilir ancak iki şehir arasındaki mesafe yukardan bakıldığında gerçekte 40 km’dir. İşte A* algoritması bu noktada doğrudan olan mesafeyi 40 km’yi de göz önüne alarak ilerler. En yakın olana yönelim gösterir.

Ancak bu noktada daha açıklayıcı olabilmek adına ufak bir konsept değişikliğine gitmemiz gerecek. Zira şu ana kadar vertex’lerin arasındaki mesafeleri göz önüne aldık ancak bulundukları konum bizim için önemli değildi. Şu anki konsept üzerinden ilerlersek sezgisel mesafeleri önceden hesaplanmış bir şekilde tutmamız  gerekir. Yani bitiş vertex’ine diğer vertex’lerin uzaklıklarını kendimiz belirleyip bellekte tutmalıyız.

Fakat daha genel ve dinamik bir çözüm sunabilmek adına bunu değiştirip vertex’lerin konum bilgilerini de tutarak bir grid üzerinde temsil etmek istiyorum. Grid bildiğiniz ızgara görünümü. Ufak kareler var ve bu karelerin her biri farklı bir lokasyonu temsil ediyor. Oyunlarda da zaten kullanım bu şekilde. Her kare birer vertex iken engeller ise bu vertex’lerin silinmiş/çıkartılmış hali. Komşu vertexler arasındaki mesafe de haliyle grid olduğundan eşit.


(Resim alıntıdır)

Grid kullanımına geçip vertex’leri lokasyonlarda temsil etmeye başlıktan sonra artık her birinin x ve y koordinatları olacak. Böylece iki vertex arasında dinamik olarak mesafe ölçümü yapabilir hale geleceğiz.

Şimdi A* algoritmasında önemli rol oynayan heuristic yaklaşımlar hakkında detaylıca konuşmadan önce bir başka BFS’e Best First Search’e geçelim. Adı üzerinde, best first search en iyi olma ihtimali olan node üzerinden ilerlemeyi amaç edinmiştir. Greedy olan ise her zaman ilkine yönelim gösterir. Bu node'lar heuristic fonksiyona bağlı olarak değerlendirilir. Best First Search’te heuristic fonksiyona göre ilerlenir.

Bu noktada daha önceden ele aldığımız, küçükten büyüğe sıralama yaptığımız min-heap priority queue’nun önemini görmüş oluyoruz. Zira priority queue sayesinde en kısa mesafeye sahip node’u en başta görmüş oluruz.

Heuristic fonksiyonlar ise ihtiyaca bağlı olarak pek çok farklı şekilde olabilir. Bunlardan öne çıkan Manhattan Distance ile Euclidean Distance’tan bahsedeceğim.

Manhattan Distance aşağıda görüldüğü üzere koordinat düzlemindeki iki nokta arasındaki mesafenin dik açılı doğrularla ölçülmesini sağlıyor.

int getManhattanDistance(const Vertex& start, const Vertex& end) {
  int distX = abs(start.x – end.x); // X farkı
  int distY = abs(start.y – end.y); // Y farkı
  
  return D * (distX + distY); // D her kare değiştirmenin maliyeti. Örneğin yan kareye geçmenin bedeli 1 olabilir.
}

Grid üzerinde çalıştığımızdan haliyle oldukça faydalı oluyor.

Bir diğer heuristic fonksiyon ise Euclidean, bildik Öklit.

Burada, her yöne hareket eden bir karakter var ise üstteki fonksiyonu biraz modifiye ediyoruz.

int getEuclideanDistance(const Vertex& start, const Vertex& end) {
  int distX = abs(start.x – end.x);
  int distY = abs(start.y – end.y);
  
  return D * sqrt(dx*dx + dy*dy); // D her kare değiştirmenin maliyeti. Örneğin yan kareye geçmenin bedeli 1 olabilir.
}

(Resim alıntıdır)

Heuristic fonksiyonlar da bu şekilde. Hesaplanacak sezgisel değerler atacağımız adımları etkileyecek. Kod A* algoritmasına doğru evrilirken eklenecek çok fazla şey kalmadı.

Bu noktadan itibaren A* algoritması için yapılacak olan modifikasyonlar belli. Öncelikle fonksiyonumuz sadece başlangıç değil bitiş noktasını da alacak. Daha önceden anlatıldığı üzere bitiş noktası heuristic hesaplamalar ve her yeri dolaşıp tek tek bakma gibi bir kaygımız olmadığından önemli. İlerlerken bitiş vertex’ine geldiğimiz an işlemi sonlandırıyoruz.

Bu sebeple, öncelikle başlangıç vertex’ini belirttiğimiz index parametresinin yanına bitiş vertex’inin index’ini de eklememiz lazım.

void aStar(int startIndex, int finishIndex) {
...

Bunun yanında yapılacak bir diğer modifikasyon ise bitiş vertex’ine gelindiği an işlemin sonlandırılması.

...
 
while (!pq.empty()) {
  cout << pq.top().second << endl;
  int currentIndex = pq.top().first;
 
  if(currentIndex == finishIndex)
    break;
 
  list<Vertex*> neighbours = adjList[currentIndex];
  pq.pop();
 
...

Priority queue zaten best first search için hazırdı. Şimdi Manhattan Distance heuristic fonksiyonunu koda dahil edip priority’ye heuristic hesaplamayı da eklersek A* bir algoritmamız olur.

...
pq.push(iPair(destIndex, distance[destIndex] + getManhattanDistance(currentVertex, finishVertex)));
...

Görüldüğü üzere A* algoritmasına temelinde yatanları inceleyerek adım adım ulaştık. Aynı zamanda, farklı yöntemlerin bir araya geldiğinde ne kadar efektik olabileceğini de görmüş olduk. A* algoritması bu açıdan güzel bir örnek teşkil ediyor. Ancak tabii ki A* da klasik haliyle kalmış değil. Onun da pek çok varyasyonu bulunmakta.

Saygılarımla.