Forum: SDL RSS
Basit labirent oyunu
erdem (Moderatör) #1
Üye Tem 2009 tarihinden beri · 958 mesaj · Konum: Eskişehir
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
O zaman bunu bir oyuna çevirelim :)

X'ler geçilemez yerleri O'lar ise geçilebilir yerleri göstersin. Program ilk başladığında oyun tahtasını rastgele X ya da O'larla doldursun.

 O O X O X
 X X X O O  
 X O X O O  
 O X O X X  
 O O X O O

Sonra kullanıcıdan bir sayı istesin.
 0  1  2  3  4    
 5  6  7  8  9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24

Örneğin kullanıcı 12 girsin.

 O O X O X
 X X X O O  
 X O O O O  
 O X O X X  
 O O X O O

Hatta bilgisayara da bir seçenek verip onun da X koyup aşağı inen yolu kapatması sağlanabilir. Tekrar bir sayı istedik. 22 olsun

 O O X O X
 X X X O O  
 X O O O O  
 O X O X X  
 O O O O O

Yukarıdan aşağı giden bir yol oluştuğu için bilgisayar tebrikler oyunu kazandınız! yazsın.
Bu mesaj erdem tarafından değiştirildi; zaman: 2012-09-21, 05:48.
Avatar
Salih Dinçer #2
Üye Ock 2012 tarihinden beri · 1908 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Teşekkürler Erdem, çok güzel açıklamışsın...

Belki bu oyunu denemek hoş ve kolay olabilir. Bu oyun denemesini unutmadan önce konumuzu (sunduğu senaryo ile algoritmayı) düşünürsek; bu algoritmayı yanlış anlamadıysam, senaryonun oyunu kazandınız aşamasındayken 19 numaralı kutuyu kapamamız gerektiğini farz edelim. Böyle bir anda bilgisayar bize zaten alt-üst arası bağlantıyı kurduğumuzu söylemesi lazım değil mi?

Çünkü konunun gelişim aşamasından beri sadeleştirme gibi bir kavramı görmekteyim. Bu algoritmanın bu oyun da şart olup olmadığına da emin değilim.

Dip Not: Bu arada başlığın ismini değiştirsek mi? Çünkü bir sorudan önemli bir algoritmanın çok güzel örneklendirmeleri ile devam ettiğimiz bir tartışma oldu. İlk sorudan ziyade asıl konuyu vurgulayan bir başlık harika olabilir.

Başarılar...
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Bu mesaj erdem tarafından değiştirildi; zaman: 2012-09-21, 05:49.
erdem (Moderatör) #3
Üye Tem 2009 tarihinden beri · 958 mesaj · Konum: Eskişehir
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Salihcim bu algoritmalara isim verirken biraz zorlandım. Örneğin weighted quick-union with path compression gibi isimler vermişler. Hatta bu gün Basic Asymptotic Complexity karşılığını Temel Sonuşmaz Karmaşıklığı olarak çevirdim :)

Konu başlığı olarak union find'ın karşılığı olarak bağla bul algoritması mı desek?

Şimdi bu algoritmayı bu oyunda nasıl kullanacağız konusuna gelirsek.

[Resim: http://erdem.tk/resim/resim/adim1.png]

[Resim: http://erdem.tk/resim/resim/adim2.png]

Oyunun başında beyazlara karşılık gelen sayıları (bizim oyunumuzdaki O'lar) bağlıyoruz. Örneğin {0 1} {3 8 13 14} vs..

Şimdi bilgisayar hangi karelerin beyaz hangilerinin siyah olacağını seçti. İyi güzel.

[Resim: http://erdem.tk/resim/resim/adim3.png]

İşte bu noktada çok akıllıca bir yöntem uyguluyoruz. Üste ve alta iki tane sayı daha ekliyoruz, üst ve alt satırda bulunan sayıları da bu sayılara bağlıyoruz. Yani alt satırda bulunan sayıların kökü en alttaki sayımız oluyor.

Böylece bağlıMı() işlevini sadece bir kez çağırarak, alt kök ile üst kökün bağlı olup olmadığını anlayabiliyoruz.

[Resim: http://erdem.tk/resim/resim/adim4.png]

Peki bu kutulardan birini nasıl açacağız (beyazlar açık yolları gösteriyor)

[Resim: http://erdem.tk/resim/resim/adim5.png]

Üzerinde olduğumuz kutuyu açık olarak belirliyoruz. Sonra buna karşılık gelen sayıyı açık olan tüm komşu kenarlara bağlıyoruz. Örneğin buradaki karşılık gelen komut bağla(12, 11) bağla(12, 13) bağla(12, 17) gibi bir komut.

Bahsettiğim Monte Carlo yöntemi de bu mantıkla çalışıyor. Tek fark burada bilgisayar yukarıdan aşağı giden bir yol bulana kadar bu kutuları bizim için rastgele açıyor.
Bu mesaj erdem tarafından değiştirildi; zaman: 2016-02-01, 07:01.
acehreli (Moderatör) #4
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4513 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Bu oyunda bir aksaklık görüyorum: Bir oyuncu kendi hamlesini diğerinin karesinde kullanırsa oyun takılır kalır. Bunun bir biçimde önlenmesi gerek. Örneğin, her oyuncu iki hamle yapar ve bunlardan ancak birisi diğerininkini geri çevirmek olabilir. (Bu çözüm aklıma üç saniyede geldi; daha iyileri bulunabilir. :))

Ali
erdem (Moderatör) #5
Üye Tem 2009 tarihinden beri · 958 mesaj · Konum: Eskişehir
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Evet oyun tasarımı kağıt üzerinde gittikçe gelişiyor.

Ali beyle ben tasarımını yapıyoruz, bu durumda kodlama kısmı da Salih'e kaldı :)
Avatar
Salih Dinçer #6
Üye Ock 2012 tarihinden beri · 1908 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Yanıtlanan mesaj #4
Anlamaya başlıyorum...:)

Yani adım adım gidince sanki her şey daha kolay oluyor. Anladığım kısaca şu: seçilen kutuya komşu olan kutuları biz farkında olmadan bağlanıyor (12'nin 11, 13 ve 17'ye bağlanması gibi) ...

Bir de olayın başlayıp bittiği sanal kutular (kök) var ki onu anlamıştım ve/veya böyle olması gerektiğini düşünmüştüm. Bunlar iyi ve güzel şeyler tıpkı akım akan elektrik devreleri gibi...:)

Peki adım adım kodlardan gidersek (öyle ya işimiz kod) ilk iki basamağı "sözde kod" ile irdeleyebilir miyiz? Yani oyunun kurulduğu, verinin yapılandırıldığı ve oyunun devam ettiği aşamaları bahsetmiyorum; sanal bağlardan (kökden) komşusuna bağlan ilk adımdan itibaren neler oluyor?

Evet neler oluyor...:D
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
erdem (Moderatör) #7
Üye Tem 2009 tarihinden beri · 958 mesaj · Konum: Eskişehir
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Bu sorunun yanıtı kendin görebilirsin :)

https://github.com/erdemoncel/algoritmalar/blob/master/hiz…

Ağırlıklı hızlı bağlama, yani iki ağacı karşılaştırarak bağlamada ise her zaman küçük ağaç alta bağlanıyor.

Burada örneğin ana programı 10 elemanlı bir HızlıBağla nesnesi oluşturacak şekilde değiştirip sınıfın üye değişkenlerini yazdırarak görebilirsin. Hatta bir kağıt kalemle bu ağacı çizmek de çok faydalı oluyor.

Direkt dersi seyretmeni de tavsiye ederim. (Week1: Union Find)

https://www.coursera.org/course/algs4partI
Avatar
Salih Dinçer #8
Üye Ock 2012 tarihinden beri · 1908 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Ama bu kodlar bahsettiğim bölümün cevabını vermiyorlar. Peki şöyle gidelim:

Yukarıdaki iletinde dört (+1) resim ile ifade edilen bir senaryo var. Son resime bakarsak, 22 numaralı kutu beyaz renge boyanırsa sanal_iki_kök_arasındaki_bağ == true olacak. Bu nasıl olacak?

İlk bakışta şöyle olacak diye tahmin etmekteyim:

- Üst köke dolaylı olarak bağlı tüm bağları,
- Doğrudan bağlı olandan başlayarak sırayla (bir döngü ile) taramak ve
- Son bulduğu yerde (en uçtaki yakın noktada) "alt kök ile komşu mu değil mi?"

diye sormak...

Tabi bu oyunun kare sayısı, oyunun uzun sürmesi için tüm ekranı kaplayacak kadar olabilir. O yüzden sağa/sola dallanan bağlar, alt köke fazla yaklaşmasa bile taranmak zorunda mı değil mi?

Eğer cevap evetse, yani her şeyin taranması şartsa bu durumda algoritmanın çalışma süresi küçük tahtaya (game table surface) göre uzun olacak. İşte bu yüzden bu algoritma yavaş olanına göre ne kadar hızlı bunu karşılaştırabilir miyiz? Yani bahsi geçen algoritmanın (ismini "KAPALI DEVRE Mi" diye koyabiliriz) avantajını görmeyi çok istiyorum...:)
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
acehreli (Moderatör) #9
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4513 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Salih, önce kitaptan okumak ister misin? Bu gerçekten çok ilginç ve çok öğretici bir konu. Algoritma Sedgewick'in bendeki kitabının baş tarafında da var. Şuradan "1.2 A Sample Problem: Connectivity" başlığından (veya daha da iyisi, "Chapter One Introduction"dan itibaren) okuyabilirsin:

  http://books.google.com/books?id=ZCchAeprwvYC&printsec…

Ali
erdem (Moderatör) #10
Üye Tem 2009 tarihinden beri · 958 mesaj · Konum: Eskişehir
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
import std.stdio;
import std.format;
import std.array;
 
class HızlıBağla
{
    int[] bağ;
    int kaçTane;
 
    this(int N)
    {
        assert(N >= 0);
        bağ = new int[N];
        kaçTane = N;
        for (int i = 0; i < N; ++i) {
            bağ[i] = i;
        }
    }
 
    int say()
    {
        return kaçTane;
    }
 
    int bul(int p)
    {
        while (p != bağ[p])
            p = bağ[p];
        return p;
    }
 
    bool bağlıMı(int p, int q)
    {
        return bul(p) == bul(q);
    }
 
    void bağla(int p, int q)
    {
        int i = bul(p);
        int j = bul(q);
        if (i == j) return;
        bağ[i] = j;
        kaçTane--;
    }
}
 
void main()
{
    HızlıBağla sayılar = new HızlıBağla(28);
 
    sayılar.bağla(0, 1);
    sayılar.bağla(1, 26);
 
    write("bağ[] :");
    for (int i = 0; i < 28; ++i) {
        write(sayılar.bağ[i], " ");
    }
 
    writeln("\n0'ın kökü kaç : ", sayılar.bul(0));
    
}

İşte ağacın çalışma prensibini gösteren örnek bir program. HızlıBağla nesnesini oluşturduğumuz zaman içeriği şu oluyor.

bağ[] :0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

Üstteki köke 26 alttaki köke 27 dedim. Şimdi sayıları bağlıyoruz. bağla(0, 1)

bağ[] :1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

Üstteki dizi'de 0. sırada bulunan elemanın 0'ın 1'i gösterdiğine dikkat.
  1
 / 
0
Ağacımız oluşmaya başladı. Sonra en üstteki köke bağlıyorum. bağla(1, 26)

bağ[] :1 26 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

    26
   /
  1
 /
0
Bu şekilde ağacımız oluşmaya başlıyor. Dikkat edersen bul işlevi aslında ağacın kökünü veriyor. bul(0) bize 26 değerini verecek.
 
     26                            27
   / | \                          /| \
  1  2  3                       21 22 23
 /       \                     /        \
0         8                  20          24
           \                /
            13            15
             \
              14
Ağacımız tamamlandıktan sonraki durum bu. Tabi eğer ağırlıklı hızlı bağla yöntemini kullansaydık ağacın derinliği bu kadar artmayacaktı. Ağacın derinliğinin artması fazladan işlem gücü demek.

Bu iki ağaç üzerinde hangi elemanları karşılaştırdığımızın önemi yok. Çünkü örneğin 0'ın kökü de 26, 8'in kökü de 26.

Algoritmaların performanslarını verdiğim github bağlantısında karşılaştırabilirsin. Veri miktarı az olduğunda bu çok farkedilmiyor. Ancak içerisinde 2 milyon kadar satır bulunan büyük.txt dosyasını kullandığında farkı görebilirsin.
Avatar
Salih Dinçer #11
Üye Ock 2012 tarihinden beri · 1908 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Teşekkürler Erdem,

Şimdi bir kaç deneme yapmak istersek nereden devam etsek? Ya da ağaç veri yapısını denetleyen işlevlere şöyle sorabilir miyiz? Birbirine bağlı komşulardan (akımı ileten kutulardan) en sonda yer alan hangi satırda?

Aslında bahsettiğin denemeleri yapmıştım ve hala yapıyorum. Sayeden ilgilendiğin konular (damlalar) yer çekimi etkisiyle göle katılan bir su damlası misali çevresinde sürekli genişleyen bir dalga (bilgi çemberi) oluşturuyor. Öyle ki bu hepimizi içine alıyor...:)

Dip Not: GitHub depondaki verileri Windows ortamında çalıktıramadım çünkü hata veriyorlar. Ama şurada takip ettiğin derslerin UTF ile kodlanmış verilerde hiç bir sıkıntı olmadı ve 3 bileşen buldu.
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Avatar
Salih Dinçer #12
Üye Ock 2012 tarihinden beri · 1908 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
acehreli on 2012-09-21, 14:12:
Salih, önce kitaptan okumak ister misin? Bu gerçekten çok ilginç ve çok öğretici bir konu. Algoritma Sedgewick'in bendeki kitabının baş tarafında da var. Şuradan "1.2 A Sample Problem: Connectivity" başlığından...
Ali hocam kitabı temin ettim. Çok güzel bir kapağı var ve ilk olarak çizit(graph) olayına girdim. Öyle ki beni bir mıknatıs gibi çekti diyebilirim. Zaten bahsettiğin başlık da bu bölüm içinde; sayfa 437...

Teşekkürler, leziz bir kitap...:)
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
acehreli (Moderatör) #13
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4513 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Salih, sevdiğine sevindim. :) Ama doğrusu, bende çizit algoritmaları kitabı yok. Bendeki ondan önceki bölümlerden oluşan kitap: arama, sıralama, vs.

Ali
erdem (Moderatör) #14
Üye Tem 2009 tarihinden beri · 958 mesaj · Konum: Eskişehir
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Yanıtlanan mesaj #11
Salih Dinçer:
Şimdi bir kaç deneme yapmak istersek nereden devam etsek?

dmd -O -release -inline yolkisaltagirliklihizlibagla.d

Mesela şu seçeneklerle dosyayı derledim. Sonuçlar şöyle:

time ./yolkisaltagirliklihizlibagla < buyuk.txt

real    0m37.389s
user    0m10.981s
sys    0m10.953s

time ./agirliklihizlibagla < buyuk.txt


real    0m37.677s
user    0m11.493s
sys    0m10.929s

Diğerlerini denersen çok daha fazla zaman alacağını tahmin ediyorum.

Salih Dinçer:
Dip Not: GitHub depondaki verileri Windows ortamında çalıktıramadım çünkü hata veriyorlar.

Bunu biraz önce denedim ama sorunsuz derlendi. Zaten github üzerindeki dosyaların kodlaması da UTF.
erdem (Moderatör) #15
Üye Tem 2009 tarihinden beri · 958 mesaj · Konum: Eskişehir
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Yanıtlanan mesaj #12
Salih Dinçer:
Çok güzel bir kapağı var ve ilk olarak çizit(graph) olayına girdim.

Eğer C++ kitabını aldıysan Ali beyin de bahsettiği gibi 5. bölüm olmalı. Kitabı ikiye ayırmışlar.

Araştırmaya denemeye meraklı olduğun için o konuları çok beğeneceğini düşünüyorum. Zaten çizit kuramı, arama, yol bulma algoritmaları zevkli konulardır.
Doğrulama Kodu: VeriCode Lütfen resimde gördüğünüz doğrulama kodunu girin:
İfadeler: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Özel Karakterler:
Forum: SDL RSS
Bağlı değilsiniz. · Şifremi unuttum · ÜYELİK
This board is powered by the Unclassified NewsBoard software, 20100516-dev, © 2003-10 by Yves Goergen
Şu an: 2017-10-22, 01:08:41 (UTC -07:00)