Graflardan Gride

Graflar, düğümler ve bu düğümler arasındaki bağlantıların oluşturduğu ağ yapılarıdır. Graf temelli yol bulma algoritmaları birbiri ile bağlantıları düğümleri kullanır. Bu düğümler arasındaki bağlantılarınyönleri ve ağırlıkları (hareket bedeli)vardır. Bu özellikler düğümler arasındaki hareketin yönünü ve bedelini belirler. Bu yöntemi kafes(grid) sistemlerinde de kullanabiliriz. Aslında kafesler de bir çeşit graflardır.

Graf temelli yol bulma algoritmalarının kullandığı bilgiler düğümler ve bu düğümlerin birbirine nasıl bağlı olduğudur. Biz bu bilgilerden çok daha fazlasını bilebiliriz (düğümün kordinatı veya düğüm sıklığı gibi) ama yol bulma algoritmalarının gerçekte bunları bilmesine gerek yoktur. Aşağıda örnek bir graf görmektesiniz.

Her hangi bir graf için bilmemiz gereken iki şey vardır.

1. Graflar kümesi
2. Her bir grafın sahip olduğu hatların kümesi

Yukarıdaki örnek için bunları oluşturursak

1. Düğüm kümesi:
2. Herbir düğümün hatlarının kümesi
   A→ABADAF
   B→BABEBF
   C→CDCECF
   D→DADCDF
   E→EBECEF
   F→FAFBFCFDFE

Düğümlerin yukarıdaki bilgilere dayanarak düğümlerin kod yapısı aşağıdaki gibi yazılabilir.

Düğümleri görselleştirilirken yerleştirilen pozisyona dikkat edilmemesi gerekir. Yukarıdaki görsel düğümleri görselleştirirken anlatımı kolaylaştırmak için yapılmıştır. Düğümlerin hangi pozisyonda olduğu bilgisinin graflar için bir önemi yoktur.

Bağlantılar aşağıdaki şekilde yazılabilir.

Grid yapıları için grafların bir pozisyona sahip olması gerekmetedir. Bu pozisyondan yola çıkarak düğüm bağlantılarını kendimiz oluştururz. Dikdörtgen grid yapıları için üst, alt ve sağ, sol düğümlerinin birbirine eşit uzaklıkta olması gerekir. Graf yapılarından farklı olarak düğümlere pozisyonu yazılabilir.

Haritalar belirlenen komşu kordinatları belirtilir. Belirlenen bir alanda düğümler oluşturulur. Sonra oluşturulmuş düğümlere komşulara göre bağlantılar eklenir.

En yaygın kullanım yukarıdaki olsa da komşu düğümlere yeni düğümler ekleyebiliriz hatta en yakın düğümleri çıkartabiliriz. Yukarıdaki örnekte kullanılan komşular[[0, 1], [0, -1], [1, 0], [-1, 0]]'dır. Eğer düğümler arası çapraz harekette olmasını istiyorsak[[0, 1], [0, -1], [1, 0], [-1, 0], [1, 1], [1, -1], [-1, -1], [-1, 1]]yapmalıyız. Elde edeceğimiz grid yapısı aşağıdaki gibi olacaktır.

Siz de ihtiyacınıza uygun bir şekilde komşu düğüm kordinatlarını düzenleyebilirsiniz.

Grid yapılarında engellerin gösterilmesinde 3 yaygın yöntem kullanılır.

1. Düğümü kaldırmak:Eğer engel tam bir düğüme karşılık geliyorsa düğümü kaldırarak o noktaya grid üzerinden ulaşımı engelleyebiliriz
2. Bağlantıyı kaldırmak:Engel olan bağlantıları kaldırmak grid üzerinde daha hassas ayarlar yapmamıza olanak sağlayabilir. Eğer engel 2 boyutlu bir şekil yerine 1 boyutlu çizgi şeklinde ise engelin kesiştiği bağlantıları silerek düğüm hareketlerini kısıtlayabiliriz. Eğer engel 2 boyutlu ise engelin içinde kalan düğümlerin tüm bağlantılarını silebiliriz.
3. Bağlantıların ağırlıklarını sonsuz yapmak:Hemen hemen bağlantıları kaldırmakla aynı işlevi görsede çeşitli durumlarda nesne bağlantısız düğüme gittiğinde yazılımsal hatalara sebep olabilmekte. Bu hatayı engellemenin bir yoluda bağlantıyı silmek yerine ağırlığını çok yükselterek her koşulda bu bağlantıyı kullanmayı verimsiz kılmak. Bu sayede nesne bir şekilde bağlantısız düğüme gitse bile bağlantılar sayesinde yazılımsal bir hataya sebep olmayacaktır. Dahası daha sonradan bu engelin değişebileceğini düşünüyorsanız ise de sadece ağırlıkları ile oynayıp engel kaldırıp oluşturabilirsiniz.

Bu yazıda graftların ne olduğunu, graftlardan grid yapısını nasıl oluşturabileceğimizi anlattım bir daha ki yazıda graft bağlantılarının özelleklerinden bahsedeceğim.