Ho una tabella (array 2d), c x r. È necessario generare un modello casuale di celle collegate al suo interno. Nessun autoincrocio e nessuna mossa diagonale. Vedi l'immagine correlata per esempio. ex. 1 с = 6, r = 7, il modello è mostrato in numeri.qual è il modo migliore per generare pattern casuali all'interno di una tabella
Ho scritto una funzione per questo e funziona bene, ma sto cercando un'ottimizzazione difficile. Nel codice qui sotto puoi vedere che se il modello finisce in un vicolo cieco si ricostruisce da solo dall'inizio. Questo è molto inefficiente se la lunghezza del pattern è vicina o uguale al numero di celle, c * r (42 nell'esempio). Quindi, per questo è necessaria una soluzione intelligente, come spostare l'intero schema simmetricamente quando si esaurisce le possibili mosse o aggiungere qualche analisi alla funzione in modo che non entri mai nei vicoli ciechi. Ancora una volta, per i bassi valori di c, r e patternLength il mio esempio funziona bene, ma sto cercando la perfezione algoritmica e prestazioni elevate anche su numeri piuttosto alti.
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
Qualsiasi idea o approccio su come questo potrebbe essere realizzato sarebbe molto apprezzato. Forse qualche backtracker ricorsivo o un path-finding o un algoritmo random-walk?
Se si hanno raggiunto un vicolo cieco si potrebbe usare https://en.wikipedia.org/wiki/Backtracking per annullare passi invece di cominciare dall'inizio di nuovo. – MrSmith42
Deve essere perfettamente casuale tra tutte queste passeggiate? La maggior parte degli approcci "patch-up per essere un po 'più grandi" non lo garantiranno. – btilly
@ MrSmith42 Sì, ci stavo pensando. Ma sembra richiedere un'analisi piuttosto intelligente. Quanti annullamenti devono essere eseguiti? Garantisci che il modello si presenterà bene dopo? Quali direzioni dovrebbero essere usate al posto (l'algoritmo dovrebbe ricordare le sue scelte)? Ecc. Può seriamente influire sulle prestazioni. (c = 1000, r = 1000, patternLength = 1000000 e abbiamo bisogno di calcolare tutte le possibili soluzioni). In effetti, se patternLength == c * r o molto vicino ad esso, penso che potrebbe essere molto influenzato e il pattern dovrebbe agire con alcune correzioni casuali su dead end, invece di usare undos. – Aleksei