Rastgele Yürüyüş Algoritmasının 'sıkışmış' olmasını nasıl önleyebilirim?

Question

Ben haydut gibi bir oyun yapıyorum ve bir 'mağara' sistemi oluşturmak için bir ızgara içinde rastgele bir yürüyüş kullanıyorum. Bununla birlikte, geldiğim rastgele yürüyüş sıkışıyor - özellikle de yürüteç ızgara kenarına yakın ve 'delikler' ile çevriliyken.

Bu, projemde kullandığım kod değil, koduma işten erişemiyorum. Ancak, evde kullandığım aynı algoritmanın bir örneğini yazdım.

Esasen, 20x20'lik bir tamsayı ızgarası aldım ve 1'lerle doldurdum. Yürürken her adımda 0 atarım.

void walk(int grid[][20]){ 
    int x = rand() % 10 + 9; 
    int y = rand() % 10 + 9; 

    int walk_count; 

    for(walk_count = rand() % 1000 + 500; walk_count >= 0; walk_count--){ 
    switch(rand() % 4){ 
     case 0: if(grid[x][y - 1] == 1 && y - 1 >= 1){ y--; grid[x][y] = 0;} break; 
     case 1: if(grid[x][y + 1] == 1 && y + 1 < 20){ y++; grid[x][y] = 0;} break; 
     case 2: if(grid[x - 1][y] == 1 && x - 1 >= 1){ x--; grid[x][y] = 0;} break; 
     case 3: if(grid[x + 1][y] == 1 && x + 1 < 20){ x++; grid[x][y] = 0;} break; 
     default: break; 
    } 
    } 
} 

Answer 1

İlk olarak, kodunuzdaki asimetriyi açıklayın. 1 durumunda, && y + 1 < 20 var. Durum 3'te, && x + 1 < 20 olmasını beklerim && x + 1 >= 1 var.

Bunu bir sorun çözme hatası/yazım hatası olarak ele alacağım ve sorunun kaynağını çizmeyeceğim. Anladığım kadarıyla, problemin, yere boyayan ve kendini bir köşeye boyayan rasgele bir yürüyüşçünüz olması. Bu davranış bekleniyor, değil mi? Sorun şu ki, sadece rastgele bir yürüyüş yapmak ve rastgele olmaktan daha zekice davranan bir davranış beklemenizdir. Kendinizi bir köşeye boyamaktan kaçınmak istiyorsanız, bunu algoritmanıza yerleştirin. Bu rastgele yürüyüşçüler oyuncuya ulaşmak istediklerini varsayarsak, eğer her bir doldurulan, eğer varsa, oyuncu için hala bir yolun olacağını kontrol et. Ardından, rastlantısal olarak doğru olan yönlerden seçim yapın.

ilk kullanımı grafikleri: her hücre köşe ve iki olarak hücreler bitişik olduğu ve her ikisi de 1 ise daha sonra köşelerden arasında grafikte bir kenar vardır

Answer 2

Sana bir çözüm vardır.

Şimdi yeni bir hücreye doğru yürürken ve içine 0 koyduğunuzda, tüm kenarları kırdığınızda, bunlar tepe noktasına bağlandı.

Şu an burada bulunan grafikteki bağlı bileşenlere bakabiliyor ve iki hücre arasında bir yol olup olmadığını anlatabiliyorsunuz (eğer aynı bağlı bileşendeyse bir yol var). Muhtemelen mağaradan bir çeşit çıkış var, bu yüzden özel bir hücre olacak, ve şimdi bir kural hava inşa edebilirsiniz hücrenin "iyi" sadece özel hücre ile aynı bağlı bileşende ise.

Sonunda: Yürüme durumunuz sadece bitişik hücre "iyi" ise (bundan önce) bu durumla asla bitmeyen bir uçta bitmeyecektir :) çünkü her zaman bir yolunuz olacaktır. çıkış (olabilir tek :) hiçbir prob daha sonra)

bu çözümün gibi umut burada grafikler hakkında daha kontrol edin:

http://en.wikipedia.org/wiki/Graph_theory

http://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29