Bir tablo var (2d dizisi), c x r. İçinde rastgele bağlı bir hücreler oluşturması gerekiyor. Kendinden geçişler ve çapraz hareketler yok. Örneğin ilgili resme bakın. ex. 1 с = 6, r = 7, desen sayılarla gösterilmiştir.Bir tablo içinde rastgele desen oluşturmanın en iyi yolu nedir
Bunun için bir işlev yazdım ve gayet iyi çalışıyor, ancak sabit optimizasyon arıyorum. Aşağıdaki kodda, eğer desen ölü bir çıkıntıya dönüşürse, sadece baştan başlayıp kendini yeniden başlattığını görebilirsiniz. Eğer model uzunluğu hücre sayısına yakınsa veya eşitse, bu çok verimsizdir, c * r (örnekte 42). Bu nedenle, olası tüm hareketler bittiğinde simetrik olarak simetrik olarak hareket etmek ya da fonksiyona bazı analitikler eklemek gibi ölü bir uçta hiçbir zaman katlanmaması gibi bazı akıllı çözümlere ihtiyaç vardır. Yine, c, r ve patternLength'un düşük değerleri için benim örneğim iyi çalışıyor, ama oldukça yüksek sayılarda bile algoritmik mükemmellik ve yüksek performans arıyorum.
function ClassLogic:generatePattern()
--[[ subfunctions ]]
--choosing next point for the pattern
local move = function(seq)
--getting the last sequence point
local last = seq[#seq]
-- checking the nearness of walls
local
wallLeft,
wallRight,
wallUp,
wallDown =
(last.c==1),
(last.c==config.tableSize.c),
(last.r==1),
(last.r==config.tableSize.r)
-- checking the nearness of already sequenced points
local
spLeft,
spRight,
spUp,
spDown =
(utilities.indexOfTable(seq, { c = last.c - 1, r = last.r })~=-1),
(utilities.indexOfTable(seq, { c = last.c + 1, r = last.r })~=-1),
(utilities.indexOfTable(seq, { c = last.c, r = last.r - 1 })~=-1),
(utilities.indexOfTable(seq, { c = last.c, r = last.r + 1 })~=-1)
local leftRestricted = (wallLeft or spLeft)
local rightRestricted = (wallRight or spRight)
local upRestricted = (wallUp or spUp)
local downRestricted = (wallDown or spDown)
if (leftRestricted and rightRestricted and upRestricted and downRestricted) then
-- dead end
print('d/e')
return nil
else
-- go somewhere possible
local possibleDirections = {}
if (not leftRestricted) then possibleDirections[#possibleDirections+1] = 1 end
if (not rightRestricted) then possibleDirections[#possibleDirections+1] = 2 end
if (not upRestricted) then possibleDirections[#possibleDirections+1] = 3 end
if (not downRestricted) then possibleDirections[#possibleDirections+1] = 4 end
local direction = possibleDirections[math.random(1, #possibleDirections)]
if (direction==1) then
--next point is left
return { c = last.c - 1, r = last.r }
elseif (direction==2) then
--next point is right
return { c = last.c + 1, r = last.r }
elseif (direction==3) then
--next point is up
return { c = last.c, r = last.r - 1 }
elseif (direction==4) then
--next point is down
return { c = last.c, r = last.r + 1 }
end
end
end
--[[ subfunctions end ]]
-- choose random entry point
local entry = { c = math.random(1, config.tableSize.c),
r = math.random(1, config.tableSize.r) }
-- start points sequence
local pointSequence = { [1] = entry }
-- building the pattern
local succeed = false
while (not succeed) do
for i = 2, self.patternLength do
local nextPoint = move(pointSequence)
if (nextPoint~=nil) then
pointSequence[i] = nextPoint
if (i==self.patternLength) then succeed = true end
else
pointSequence = { [1] = entry }
break
end
end
end
return pointSequence
end
Bunun nasıl gerçekleştirilebileceğine dair herhangi bir fikir veya yaklaşım çok takdir edilecektir. Belki bazı özyineli backtracker veya bir yol bulma veya rasgele yürüyüş algoritmaları?
Eğer tekrar baştan adımları yerine başlangıcını geri almak için https://en.wikipedia.org/wiki/Backtracking kullanabileceği bir çıkmaza edin. – MrSmith42
Tüm bu yürüyüşler arasında mükemmel rastgele olması gerekir mi? Çoğu “biraz daha büyüyün” yaklaşımları bunu garanti etmeyecektir. – btilly
@ MrSmith42 Evet, bunu düşünüyordum. Ama oldukça akıllı bir analiz gerektiriyor gibi görünüyor. Kaç tane eksik yapılmalı? Desenin bundan sonra iyi olacağını garanti eder mi? Wich yönleri yerine kullanılmalıdır (algoritma seçimlerini hatırlamalı mıdır)? Vb Ciddi performansı etkileyebilir. (c = 1000, r = 1000, patternLength = 1000000 ve tüm olası çözümleri hesaplamalıyız). Aslında, eğer patternLength == c * r ya da ona çok yakınsa, bunun çok iyi anlaşılabileceğini düşünüyorum ve desen, kullanım hataları yerine _avoid_ ölü uçlarına rastgele bazı düzeltmelerle hareket etmelidir. – Aleksei