C++ ve SFML ile Labirent Algoritmalarının Görselleştirilmesi

Bilgisayar mühendisliği ve oyun programlamada “yol bulma” (pathfinding) algoritmaları temel konulardan biridir. Biz de Veri Yapıları ve Algoritmalar dersi özelinde yaptığımız proje ödevinde bu algoritmaları en işlevsel haliyle gösterebileceğimizi düşündüğümüz bir “Labirent Çözücü” program yaptık.

Ben Samet, ekip arkadaşlarım Yiğit ve Emin ile birlikte; hazır oyun motorlarını kullanmak yerine C++ ve SFML kütüphanesini kullanarak kendi “Maze Engine” projemizi geliştirdik.

Bu yazıda projenin teknik altyapısından, labirent oluşturma mantığından ve DFS, BFS, A* algoritmalarının kod tarafındaki uygulamalarından bahsedeceğiz.

Neden C++ ve SFML Tercih Ettik?

Projeye başlarken performans bizim için önemliydi. Labirent boyutu büyüdüğünde algoritmaların milisaniyeler (hatta mikrosaniyler) içindeki tepkisini ölçmek istiyorduk. Bu yüzden bellek yönetimi üzerinde tam kontrol sağlayan C++ dilini seçtik.

Görselleştirme tarafında ise Unity veya Unreal Engine gibi ağır motorlar yerine, sadece 2D çizim işlemlerini hızlıca halledebileceğimiz SFML (Simple and Fast Multimedia Library) kütüphanesini kullandık.

Labirentteki her bir kareyi (hücreyi) tanımlamak için şöyle bir struct yapısı oluşturduk:

C++

struct Cell {
    int x, y;
    bool walls[4] = {true, true, true, true};
    bool visitedBySolver = false;
    int parentIndex = -1;
    bool isPath = false;
    bool isStart = false;
    bool isEnd = false;

};

1. Labirent Oluşturma: Kruskal Algoritması

Rastgele bir labirent oluşturmak kolay gibi görünse de, labirentin “çözülebilir” olması ve kapalı alan kalmaması gerekir. Araştırmalarımız sonucunda bunun için en uygun yöntemin Randomized Kruskal Algoritması olduğuna karar verdik.

Mantık şu şekilde işliyor:

• Başlangıçta tüm hücrelerin arası duvarlarla kapalıdır.
• Rastgele bir duvar seçilir.
• Eğer duvarın ayırdığı iki hücre arasında zaten bir bağlantı yoksa duvar yıkılır.

Burada hücrelerin birbirine bağlı olup olmadığını kontrol etmek için Union-Find (Ayrık Kümeler) veri yapısını kendimiz kodladık. Bu sayede labirentte döngü oluşmasını engelledik ve her noktanın ulaşılabilir olmasını sağladık.

class UnionFind
{
private:
    vector<int> parent;

public:
    UnionFind(int n)
    {
        parent.resize(n);
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }
    int find(int i)
    {
        if (parent[i] == i)
            return i;
        return parent[i] = find(parent[i]);
    }
    void unite(int i, int j)
    {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j)
            parent[root_i] = root_j;
    }
};

2. Çözüm Algoritmaları ve Karşılaştırma

Labirenti oluşturduktan sonra, aynı labirent üzerinde üç farklı algoritmayı çalıştırarak sonuçları kıyasladık.

Derinlemesine Arama (DFS — Depth First Search)

DFS, bir yola girdiğinde sonuna kadar gitmeyi dener. Çıkmaza girdiğinde ise geri dönerek (backtracking) diğer yolları arar. Kodlamada bu “geri dönme” mantığını yönetmek için Stack (Yığın) veri yapısını kullandık.

C++

void solve(vector<T>& grid,int rows,int cols,int startIndex,int endIndex,RenderWindow& window,bool visualize = true) {
        stack<int> s;
        s.push(startIndex);

        grid[startIndex].parentIndex = -1;
        grid[startIndex].visitedBySolver=true;

        bool found=false;

        while(!s.empty()) {
            if (visualize) {
                if (!window.isOpen())
                    break;
                window.clear(Color::Black);
                for(auto& cell : grid) cell.draw(window);
                window.display();
                sleep(milliseconds(1));
            }
            int index=s.top();
            s.pop();

            if (index==endIndex) {
                found=true;
                break;
            }

            //0 üst, 1sağ, 2 alt, 3 sol duvar

            //yukarı kontrolü (index-cols)
            if (index >= cols && !grid[index].walls[0]) {
                int neighbor = index - cols;
                if (!grid[neighbor].visitedBySolver) {
                    grid[neighbor].visitedBySolver=true;
                    grid[neighbor].parentIndex = index;
                    s.push(neighbor);
                }
            }
            // Aynı kontrol tüm yönler için de yapılmakta 
            // sağ kontrolü (index+1)
            // alt kontrolü (index+cols)
            // sol kontrolü (index-1)
        }
        //geri yol çizme
        if (found) {
            int current=endIndex;
            while (current!=startIndex && current!=-1) {
                grid[current].isPath=true;
                current=grid[current].parentIndex;
                if (visualize) {
                    window.clear(Color::Black);
                    for(auto& cell : grid) cell.draw(window);
                    window.display();
                    sleep(milliseconds(1));
                }
            }
            grid[startIndex].isPath=true;
            cout << "Yol bulundu ve cizildi!!" << endl;
        }else {
            cout << "Yol bulunamadi!" << endl;
        }
    }

if (index >= cols && !grid[index].walls[0]) {

int neighbor = index - cols;

if (!grid[neighbor].visitedBySolver) {

grid[neighbor].visitedBySolver=true;

grid[neighbor].parentIndex = index;

s.push(neighbor);

}

Gözlemimiz: DFS yolu buluyor ancak bulduğu yol genellikle çok uzun ve dolambaçlı oluyor. En kısa yolu bulma garantisi yok.

Genişlemesine Arama (BFS — Breadth First Search)

BFS, başlangıç noktasından itibaren dalga dalga yayılır. Kod tarafında bunu Queue (Kuyruk) yapısı ile sağladık. İlk giren ilk çıkar (FIFO) mantığı, algoritmanın merkeze yakın kareleri önce taramasını sağlar.

C++

// BFS Algoritması (Queue Kullanımı)
std::queue<int> q;
q.push(startIndex);

while (!q.empty()) {
    int index = q.front(); 
    q.pop();

    // Komşuları sıraya ekle
    if (neighbor != -1 && !grid[neighbor].visitedBySolver) {
        grid[neighbor].parentIndex = index;
        q.push(neighbor); 
    }
}

Gözlemimiz: BFS, matematiksel olarak en kısa yolu kesinlikle buluyor. Ancak hedefi bulana kadar çok geniş bir alanı taradığı için işlem yükü DFS’e göre daha fazla olabiliyor.

A* (A-Star) Algoritması

Projenin en verimli kısmı burasıydı. A*, BFS’in garantici yapısını bir “tahmin” mekanizmasıyla birleştiriyor. Hedefe ne kadar kaldığını hesaplamak için Manhattan Mesafesi formülünü kullandık.

Veri yapısı olarak, maliyeti en düşük olan kareyi her zaman en üstte tutan std::priority_queue kullandık.

C++

// A* için Öncelik Kuyruğu Yapısı
struct Node {
    int index;
    float fCost; // Gidilen yol + Tahmini kalan yol
    // Küçük maliyetli olanı öne al
    bool operator>(const Node& other) const { return fCost > other.fCost; }
};

Gözlemimiz: A*, BFS gibi en kısa yolu buluyor ama tüm haritayı taramıyor. Sadece hedefe yönelik kareleri denediği için çok daha hızlı sonuç veriyor.

Sonuç

Bu proje sayesinde Stack, Queue ve Priority Queue gibi veri yapılarının, bir algoritmanın davranışını ne kadar değiştirdiğini pratik ederek öğrenmiş olduk.

Projenin tüm kaynak kodlarına ve çalıştırılabilir dosyalarına aşağıdaki GitHub adresinden ulaşabilirsiniz.

🔗 GitHub Linki: https://github.com/SametERILTER/Maze-Engine