Nxn 'lik Bir Labirent üzerinde En Kısa Yol Problem

[wmismail]

Bu makalemde sizlere NxN 'lik bir labirent üzerinde belirlenen iki nokta arasındaki "en kısa yolu" ve "diğer alternatif yolları" bulan "PathFinder" adlı programımın nasıl çalıştığına dair bilgiler aktarmaya çalışacağım. Unutmadan, bu programın görsel öğelerini http://www.codeproject.com/ 'te yer alan "MazeSolver" adlı aynı işi yapmaya çalışan bir başka programdan aldım. Dolayısıyla bu programı gören birileri "Aaa ben bunu codeproject'te görmüştüm. Çalmış herif kodları! Cık, cık cık..." diyebilir, normaldir. Ama iki programın kodlarını alıp karşılaştırdığınızda arada hiçbir benzerlik olmadığını göreceksiniz... Hem benimki daha iyi, iddaa ediyorum

Programımızın ekran görüntüsü aşağıdaki gibi,

Şimdi genel olarak, ekran görüntüsü üzerinden kısaca programın nasıl çalıştığını, ne yaptığını anlatmaya çalışalım. Sol tarafta yer alan labirent NxN boyutlarında daha doğrusu, N 0-16 arası değer alabiliyor. Bu aralık değiştirilebilir elbette...

"Actions" bölümünden "Draw Wall" seçeneği seçili iken labirent üzerinde farenin sol tuşuyla duvar çizebiliyorsunuz, farenin sağ tuşuna sürekli basılı tutarak ta hızlıca duvar çizebilirsiniz, sol tuşla bir seferde bir tane duvar karesi belirleyebiliyorsunuz, sağ tuş ile sürekli duvar çizebilirsiniz. Herhangi bir boş kare üzerinde farenin sol tuşuna çift çıklatırsanız başlangıç ve bitiş noktalarını belirleyebilirsiniz. İlk seçtiğiniz nokta başlangıç noktası olacaktır. Başlangıç ve bitiş noktalarını silmek için de bu noktaların üzerinde yine farenin sol tuşuyla çift çıkmanız yeterli...

Bir defa labirenti oluşturup, başlangıç ve bitiş noktalarını belirlediktan sonra "Actions" bölümünden "Find Path " seçeneğini seçerseniz, program size kaç çözüm yolu bulduğunu, en kısa çözüm yolunu, diğer alternatif çözüm yollarını ve uyguladığı algoritmanın bir sonucu olarak detaylı bir "Yol Analizi" gösterecektir. Herbir yol analizi üzerine tıkladığınızda o yola ilişkin labirent üzerinde izlenen yolları ve programın o yolu nasıl değerlendirdiğini göreceksiniz.

Şimdi sıra programımızın temelindeki "Sınıf" yapılarına,

Öncelikle "Square" sınıfından başlayalım. Bu sınıf labirent üzerindeki bir kareyi temsil eden bir nesne. Bir karenin 3 ayrı tipi bulunuyor, bunlar;

Sınır (Border) Square (Kare) Wall (Duvara) Oluşturulan bir labirenti mutlaka kapalı bir sınır içerisinde tutmalısınız, aksi takdirde program çalışmayabilir. Hoş, şu haliyle zaten sınırları kendisi belirliyor, ileride kaynak kodlar üzerinde değişiklik yaptığınızda dikkat edin diye söylüyorum

Program size herhangi bir labirent ile ilgili sonuçları verdiğinde, karelerin yer yer farklı renklerde olduklarını göreceksiniz. Aşağıda karelerin sahip oldukları renklerin ne anlama geldiklerini gösteren tablomuz yer alıyor.

Yanlış (Wrong) Bilinmiyor (Unknown) Yol (Path) - Durumu belirli olmayan yol Kare (Square) Doğru (Correct) Şimdi de sınıflarımıza ait metotlar ve özelliklere bakalım.

Programımızda en önemli rol oynayan sınıfımız "PathManager" sınıfı. Bu sınıf kendisine atanan bir yol üzerinde, yani bütünün bir parçası üzerinde işlem yapmaktaktadır. Peki bir yolun bir PatManager sınıfına atanmasına nasıl karar vereceğiz ? Daha doğrusu bir yolu alt yollara nasıl ayıracağız ? Güzel soru ama cevabı çok basit...

Bir yolu alt yollara biz ayırmayacağız. Bu oluşturulan labirentin bir parçası zaten, biz yalnızca alt yolların hangileri olduklarına karar vereceğiz. Bu da oldukça basit... Eğer bir yol bir noktada iki ya da daha fazla (en fazla 4) yola ayrılıyorsa, ayrılan her bir yol bizim için bir alt yol olacak... Ve bu alt yolların her birine yeni bir "PathManager" atayacağız ve ilgili yolla yeni atanan PathManager' lar ilgilenecekler. Aşağıdaki labirent üzerinde, program çalıştığında oluşturulacak alt yolları görüyorsunuz.

Problemi çözmek üzere PathManager sınıfı ile oluşturulan yapı birebir bir ağaç yapısı aslında. Bir tane kök PathManager ile başlıyoruz ve problemin derinliğine göre kök PathManager alt PathManager'lara onlar da alt dallara ayrılıyorlar.

Yukarıda "PathManager" sınıfına ait diyagram üzerinden de anlaşılacağı üzere bir PathManager birden fazla alt PathManager'a sahip olabilmektedir. Alt PathManager'lar ilgili PathManager'a ait "SubPathManagers" adlı PathManager kolleksiyonunda saklanmaktadır.

Bir PathManager hedef noktaya ulaştığı ya da çözüm yolu bulamadığı anda, kendisini ve kendisinin üzerindeki tüm PathManager'ları durumdan haberdar eder ve çözümün bulunup bulunmadığını bildirir.

Asıl kararları ve sonuçları veren PathManager ise tabii ki bizim belirlediğimiz kök PathManager. Sonuçta bütün alt PathManager'lar ona bağlı ve ona buldukları sonuçları bildiriyorlar. Kök PathManager'ımızın elde ettiği sonuçları ve kararları ise zaten programın çıktısı olarak görüyorsunuz.

Genel olarak programımızın işleyiş biçimi bu şekilde. Şimdi de isterseniz kaynak kodlarına bakalım PathManager sınıfımızın. Bu sınıf ile ilgili olarak BeginManagePath, FindSolution, EndManagePath metotlarını inceleyeceğiz.

public void BeginManagePath()

{

if (this != null)

this.FindSolution(this.StartSquare.X, this.StartSquare.Y);

else

throw new Exception("Object not implemented yet!");

}

Bu metot aslında FindSolution metodunu çağıran bir ön kontrol metodu.

private void FindSolution(int row, int column)

{

SquareCollection neighBours = new SquareCollection();

SelectSquare(new Square(row, column));

// increment the cost for this path manager

this.totalCost_++;

// look for the neighbour squares

neighBours = FindNeighBourSquares(row, column);

// determine what to do about the neighbours

if (!endManagePath_)

{

if (row == this.TargetSquare.X && column == this.TargetSquare.Y)

{

// first check if we have found the solution

EndManagePath(new Square(row, column), true);

}

else if (neighBours.Count == 0)

{

// no more solution

EndManagePath(new Square(row, column), true);

}

else if (neighBours.Count == 1)

{

// continue managing the path

FindSolution(neighBours[0].X, neighBours[0].Y);

}

else if (neighBours.Count > 1)

{

// more than one neighbours found, so end managing process with the current square

// then assing new pathmanagers for the rest of the neighbours

EndManagePath(new Square(row, column), false);

// assign new path managers

for (int i = 0; i < neighBours.Count; i++)

{

// assign this object as parent path for the sub path manager

// and indicate that sub manager is not root

PathManager subPathManager = new PathManager(this, i,

new Square(neighBours.X, neighBours.Y),this.SourceSquare,

this.TargetSquare, this.innerBoard_, false);

subPathManager.BeginManagePath();

// add sub path managers to current manager collections

this.subPathManagers_.Add(subPathManager);

}

}

}

else

{

// this situation is not normal, not expected to happen; even if it happens assume no more solution

EndManagePath(new Square(row, column), true);

}

}Dananın kuyruğunu koparan bu metot aslında, bütün her şey bu metotun yaptıkları ve sonuçları ile çözülüyor. Önce seçilen kare "Dolu" olarak işaretleniyor. Ardından ilgili yolun toplam maliyet değeri arttırılıyor. Ardından seçilen karenin komşuları bulunuyor ve komşu sayısına göre izlenecek yollar belirleniyor. Eğer seçili karenin hiç komşusu yoksa ve hedef kareye ulaşılamamışsa çözüm bulunamamış demektir. Eğer yalnızca bir komşu varsa "recursive" olarak metot yeni komşu kare için yeniden çağırılıyor. Birden fazla komşu varsa eğer, üzerinde bulunulan yolun alt yollara ayrıldığını anlıyoruz ve alt yolların her birine yeni bir "PathManager" atıyoruz ve onların bize buldukları sonuçları iletmelerini bekliyoruz. Yapılan işlem bu kadar basit!

private void EndManagePath(Square endPointSquare, bool noMoreNeighBour)

{

SelectSquare(endPointSquare);

// if no more solution found then indicate that this is a wrong path

if (noMoreNeighBour)

{

this.endPointSquare_ = endPointSquare;

if (this.endPointSquare_.X == this.TargetSquare.X && this.endPointSquare_.Y == this.TargetSquare.Y)

{

// we have found the solution

this.pathStatus_ = SquarePathStatus.CORRECT;

// found the solution

this.SolutionFound = true;

// also indicate that we have found the solution for parent managers // and add it to the solution list

PathManager tmpManager = this;

while (tmpManager != null)

{

tmpManager.SolutionFound = true;

tmpManager.Solutions.Add(this);

tmpManager = tmpManager.ParentPathManager;

}

}

else

{

// we have not found the solution

this.pathStatus_ = SquarePathStatus.WRONG;

// found the solution

this.SolutionFound = false;

}

}

this.endManagePath_ = true;

}

EndManagePath metodunun yaptığı yalnızca üzerinde bulunulan yolu doğru, bilinmiyor ya da yanlış olarak işaretlemek. PathManager işaretlendikten sonra sonuç diğer "Baba" PathManger' lara da bildiriliyor.

Programın kaynak kodlarını indirip açtığınızda karşınızda iki proje göreceksiniz. Bunlardan ikincisi programımızın PathManager sınıflarının ayrı Thread'lerle kontrol edildiği versiyonu. Bu versiyonu da programın daha hızlı çalışacağını düşünerek yaptım ama çok ilginç sonuçlar elde ettim. Program aksine Thread kullanılan versiyonda daha yavaş çalışıyor. Çok ilginç. Burada bir soru işareti var! Yakında çözerim umarım. Bu konuyla ilgili sizin de yardımlarınızı bekliyorum...

Kaynak kodlarda kullandığım İngilizce yorum satırları için hepinizden özür diliyorum, programın İngilizce olması için de tabii... Esasen bu programı CodeProject'te yayınlamak üzere hazırladığım için oldu bunlar. En kısa zamanda Türkçe versiyonunu hazırlayacağım...

Evet, makalemizin sonuna geldik arkadaşlar. Hepinize sağlıklı günler diliyorum...

http://www.ahmetbutun.net/Download/Default.aspx?id=76 Kaynak kodu indir