C++ Maze Solver

C++ kullanılarak geliştirilmiş, özel bir Stack veri yapısı ve geri izleme (backtracking) mantığı ile labirent çözümü gerçekleştiren bir projedir.

Projede hazır bir Stack yapısı kullanılmamış, bağlı liste tabanlı özel bir Stack sınıfı geliştirilmiştir. Labirent içerisindeki konumlar ve yön bilgileri bu yığın yapısında tutulmakta, çıkmaz bir yola girildiğinde önceki konumlara geri dönülerek farklı yollar denenmektedir.

Özellikler

• C++ ile geliştirilmiş labirent çözme uygulaması
• Özel Stack veri yapısı
• Bağlı liste tabanlı Stack implementasyonu
• Push, pop, top ve isEmpty işlemleri
• Labirent haritasının metin dosyasından okunması
• Başlangıç ve çıkış konumlarının belirlenmesi
• Dört farklı yönde hareket kontrolü
• Engel kontrolü
• Çıkmaz yollarda geri dönme
• Backtracking mantığı ile çıkışın aranması
• Labirent çözüm sürecinin konsol üzerinde gösterilmesi

Kullanılan Teknolojiler

• C++
• Object-Oriented Programming
• Data Structures
• Stack
• Linked List
• Backtracking
• Makefile

Proje Yapısı

• include/Stack.hpp — Bağlı liste tabanlı özel Stack veri yapısı
• include/Konum.hpp — Konum ve yön bilgilerinin tanımlandığı yapı
• include/Labirent.hpp — Labirent sınıfının tanımları
• src/Konum.cpp — Konum ve hareket fonksiyonlarının implementasyonu
• src/Labirent.cpp — Labirent okuma, hareket ve engel kontrol işlemleri
• src/Test.cpp — Labirent çözüm algoritmasının çalıştırıldığı ana program
• Harita.txt — Labirent haritası
• makefile — Projenin derleme ve çalıştırma komutları

Stack Veri Yapısı

Projede kullanılan Stack sınıfı hazır bir kütüphane yerine özel olarak geliştirilmiştir.

Her düğüm bir veri ve bir sonraki düğümü gösteren işaretçi içermektedir.

Stack içerisinde aşağıdaki temel işlemler bulunmaktadır:

• push() — Yeni eleman ekleme
• pop() — En üstteki elemanı çıkarma
• top() — En üstteki elemana erişme
• isEmpty() — Stack boş mu kontrolü
• makeEmpty() — Stack içerisindeki tüm elemanları temizleme

Labirent içerisinde ziyaret edilen konumlar Stack yapısında tutulmaktadır.

Labirent Çözüm Mantığı

Program başlangıç konumundan itibaren mevcut yönde ilerlemeyi dener.

Eğer mevcut yönde bir engel varsa diğer yönler saat yönünde kontrol edilir.

Bir konuma ilerlenebildiğinde önceki konum Stack yapısına eklenir.

Eğer tüm yönlerde engel bulunuyorsa Stack içerisindeki önceki konuma geri dönülür.

Bu işlem çıkış konumuna ulaşılana kadar devam eder.

Bu yaklaşım sayesinde çıkmaz yollar tespit edildiğinde geri izleme yapılarak alternatif yollar denenmektedir.

Hareket Yönleri

Projede dört temel hareket yönü kullanılmaktadır:

• Aşağı
• Sol
• Yukarı
• Sağ

Konum yapısı x ve y koordinatlarının yanında mevcut yön bilgisini de tutmaktadır.

Labirent Haritası

Labirent Harita.txt dosyasından okunmaktadır.

Haritada:

• # karakteri engelleri temsil eder.
• Boş alanlar hareket edilebilir yolları temsil eder.
• Program tarafından ziyaret edilen yollar takip edilerek çıkış aranır.

Projede kullanılan labirent boyutu 20 satır ve 50 sütundur.

Başlangıç ve Çıkış Noktası

Programdaki başlangıç ve çıkış konumları:

• Başlangıç: (0, 20)
• Çıkış: (19, 11)

Program çıkış noktasına ulaştığında:

CIKISA GELDI

mesajını ekrana yazdırır.

Derleme

Proje Makefile kullanılarak derlenebilir.

Terminal üzerinden:

make derle

komutu ile proje derlenebilir.

Derleme sonucunda kaynak dosyalarından nesne dosyaları oluşturulur ve çalıştırılabilir program hazırlanır.

Çalıştırma

Projeyi çalıştırmak için:

make calistir

komutu kullanılabilir.

Tüm işlemleri tek komutla gerçekleştirmek için:

make

komutu da kullanılabilir.

Projenin Amacı

Bu projenin amacı Stack veri yapısının gerçek bir problem üzerinde uygulanmasını sağlamaktır.

Özel olarak geliştirilen Stack yapısı kullanılarak labirent içerisindeki konumlar saklanmış ve geri izleme yöntemi ile çıkış yolu bulunmuştur.

Bu sayede Stack, bağlı liste, yön kontrolü ve backtracking gibi temel veri yapıları ve algoritma kavramları uygulamalı olarak kullanılmıştır.

Proje Notu

Bu proje Veri Yapıları dersi kapsamında geliştirilmiş akademik bir çalışmadır.