I'v có một bảng (mảng 2d), c x r. Cần tạo ra một mẫu ngẫu nhiên của các ô được kết nối bên trong nó. Không có giao lộ tự và không có đường chéo. Xem hình ảnh liên quan chẳng hạn. ex. 1 с = 6, r = 7, mẫu được hiển thị bằng số.cách tốt nhất để tạo mẫu ngẫu nhiên bên trong một bảng
Tôi đã viết một chức năng cho điều này và nó hoạt động tốt, nhưng tôi đang tìm kiếm tối ưu hóa cứng. Trong đoạn code dưới đây bạn có thể thấy rằng nếu mẫu được đưa vào một ngõ cụt, nó chỉ tự xây dựng lại từ đầu. Điều đó rất không hiệu quả nếu chiều dài mẫu gần hoặc bằng với số lượng ô, c * r (42 trong ví dụ). Vì vậy, một số giải pháp thông minh là cần thiết cho việc này, như di chuyển toàn bộ mô hình đối xứng khi nó hết các động thái có thể hoặc để thêm một số phân tích vào hàm để nó không bao giờ tuôn ra ở đầu chết. Một lần nữa, đối với các giá trị thấp của c, r và patternLength ví dụ của tôi hoạt động tốt, nhưng tôi đang tìm kiếm sự hoàn hảo về thuật toán và hiệu suất cao ngay cả trên các con số khá cao.
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
Bất kỳ ý tưởng hay cách tiếp cận nào về việc này có thể được thực hiện sẽ được đánh giá cao. Có lẽ một số backtracker đệ quy hoặc một pathfinding hoặc một thuật toán đi bộ ngẫu nhiên?
Nếu bạn đạt đến một ngõ cụt bạn có thể sử dụng https://en.wikipedia.org/wiki/Backtracking để hoàn tác các bước thay vì đầu từ đầu một lần nữa. – MrSmith42
Có cần phải hoàn toàn ngẫu nhiên trong số tất cả các chuyến đi như vậy không? Hầu hết các phương pháp "vá nó lên đến một chút lớn hơn" sẽ không đảm bảo điều đó. – btilly
@ MrSmith42 Vâng, tôi đã nghĩ về nó. Nhưng có vẻ như yêu cầu phân tích khá thông minh. Cần bao nhiêu lần hoàn tác? Do nó đảm bảo rằng mô hình sẽ đi lên tốt sau đó? Hướng nào nên được sử dụng thay thế (nên thuật toán nhớ đó là sự lựa chọn)? Vv Nó có thể ảnh hưởng nghiêm trọng đến hiệu suất. (c = 1000, r = 1000, patternLength = 1000000 và chúng tôi cần tính toán tất cả các giải pháp có thể). Trong thực tế, nếu patternLength == c * r hoặc rất gần với nó, tôi nghĩ rằng nó sẽ được veryfied và mô hình nên hành động với một số sửa chữa trên ngẫu nhiên để _avoid_ chết kết thúc thay vì sử dụng undos. – Aleksei