jaki jest najlepszy sposób wygenerowania losowego wzoru wewnątrz tabeli

Question

Mam stół (tablica 2d), c x r. Musisz wygenerować losowy wzorzec połączonych komórek w środku. Bez samokrytycyzmu i bez ruchów ukośnych. Zobacz powiązane zdjęcie na przykład. ex. 1 с = 6, r = 7, wzór jest pokazany w liczbach.

Napisałem do tego funkcję i działa dobrze, ale szukam ciężkiej optymalizacji. W poniższym kodzie widać, że jeśli wzór przechodzi w ślepy zaułek, po prostu odbudowuje się od samego początku. Jest to bardzo nieefektywne, jeśli długość wzoru jest bliska lub równa liczbie komórek, c * r (42 w przykładzie). Potrzebne jest więc pewne inteligentne rozwiązanie, takie jak przesuwanie całego wzoru symetrycznie, gdy zabraknie mu możliwych ruchów lub dodanie funkcji analitycznych do funkcji, aby nigdy nie znalazły się w ślepych uliczkach. Ponownie, dla niskich wartości c, r i patternLength mój przykład działa dobrze, ale szukam algorytmicznej doskonałości i wysokiej wydajności nawet na dość wysokich liczbach.

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 

Wszelkie pomysły lub podejścia do tego, jak mogłoby to zostać zrealizowane, byłyby wysoko cenione. Może jakiś rekurencyjny backtracker, algorytm ścieżki lub algorytm "spacer"?

Answer 1

Uprawa w stylu węża nie wystarcza do uzyskania dobrej wydajności.
Główną ideą jest, aby zmodyfikować ścieżkę losowo generowane przez dodanie małych objazdów tak:

- - 6 - -   - - 8 - - 
- - 5 - -   - 6 7 - - 
- - 4 1 - ===> - 5 4 1 - 
- - 3 2 -   - - 3 2 - 
- - - - -   - - - - - 

(zwrócić uwagę na dodatkowe dwie komórki dodane do lewej 4-5 segmentów)

taka realizacja działa bardzo szybko na obszarze napełniania < 95% przykład

local function generate_path(W, H, L) 
    -- W = field width (number of columns) -- c = 1..W 
    -- H = field height (number of rows) -- r = 1..H 
    -- L = path length, must be within range 1..W*H 

    assert(L >= 1 and L <= W * H, "Path length is greater than field area") 

    local function get_idx(x, y) 
     return x >= 1 and x <= W and y >= 1 and y <= H and (y - 1) * W + x 
    end 

    local function get_x_y(idx) 
     local x = (idx - 1) % W + 1 
     local y = (idx - x)/W + 1 
     return x, y 
    end 

    local function random_sort(array) 
     for last = #array, 2, -1 do 
     local pos = math.random(last) 
     array[pos], array[last] = array[last], array[pos] 
     end 
    end 

    local path_sum_x = 0 
    local path_sum_y = 0 
    local path_ctr = 0 

    local is_unused = {} -- [idx] = true/nil (or idx recently swapped with) 

    local function mark_as_unused(idx, value) 
     local x, y = get_x_y(idx) 
     path_sum_x = path_sum_x - x 
     path_sum_y = path_sum_y - y 
     path_ctr = path_ctr - 1 
     is_unused[idx] = value or true 
    end 

    local function mark_as_path(idx) 
     local x, y = get_x_y(idx) 
     path_sum_x = path_sum_x + x 
     path_sum_y = path_sum_y + y 
     path_ctr = path_ctr + 1 
     is_unused[idx] = nil 
    end 

    for x = 1, W do 
     for y = 1, H do 
     is_unused[get_idx(x, y)] = true 
     end 
    end 

    -- create path of length 1 by selecting random cell 
    local idx = get_idx(math.random(W), math.random(H)) 
    mark_as_path(idx) 
    local path = {first = idx, last = idx, [idx] = {}} 
    -- path[idx] == {next=next_idx/nil, prev=prev_idx/nil} 

    local function grow() 
     local variants = { 
     {dx=-1, dy=0, origin="last"}, {dx=1, dy=0, origin="last"}, 
     {dx=0, dy=-1, origin="last"}, {dx=0, dy=1, origin="last"}, 
     {dx=-1, dy=0, origin="first"}, {dx=1, dy=0, origin="first"}, 
     {dx=0, dy=-1, origin="first"}, {dx=0, dy=1, origin="first"} 
     } 
     random_sort(variants) 
     for _, vector in ipairs(variants) do 
     local x, y = get_x_y(path[vector.origin]) 
     local idx = get_idx(vector.dx + x, vector.dy + y) 
     if is_unused[idx] then 
      if vector.origin == 'first' then 
       -- add new first cell of the path 
       local old_first = path.first 
       path[old_first].prev = idx 
       path[idx] = {next = old_first} 
       path.first = idx 
      else 
       -- add new last cell of the path 
       local old_last = path.last 
       path[old_last].next = idx 
       path[idx] = {prev = old_last} 
       path.last = idx 
      end 
      mark_as_path(idx) 
      return true 
     end 
     end 
    end 

    local function shrink() 
     if math.random(2) == 2 then 
     -- remove first cell of the path 
     local old_first = path.first 
     local new_first = assert(path[old_first].next) 
     path[old_first] = nil 
     path.first = new_first 
     path[new_first].prev = nil 
     mark_as_unused(old_first) 
     else 
     -- remove last cell of the path 
     local old_last = path.last 
     local new_last = assert(path[old_last].prev) 
     path[old_last] = nil 
     path.last = new_last 
     path[new_last].next = nil 
     mark_as_unused(old_last) 
     end 
    end 

    local function inflate() 
     local variants = {} 
     local idx1 = path.first 
     repeat 
     local idx4 = path[idx1].next 
     if idx4 then 
      local x1, y1 = get_x_y(idx1) 
      local x4, y4 = get_x_y(idx4) 
      local dx14, dy14 = x4 - x1, y4 - y1 
      local dx, dy = dy14, dx14 
      for side = 1, 2 do 
       dx, dy = -dx, -dy 
       local x2, y2 = x1 + dx, y1 + dy 
       local idx2 = get_idx(x2, y2) 
       local idx3 = get_idx(x2 + dx14, y2 + dy14) 
       if is_unused[idx2] and is_unused[idx3] then 
        table.insert(variants, {idx1, idx2, idx3, idx4}) 
       end 
      end 
     end 
     idx1 = idx4 
     until not idx4 
     if #variants > 0 then 
     local idx1, idx2, idx3, idx4 = 
      (table.unpack or unpack)(variants[math.random(#variants)]) 
     -- insert idx2 and idx3 between idx1 and idx4 
     path[idx1].next = idx2 
     path[idx2] = {prev = idx1, next = idx3} 
     path[idx3] = {prev = idx2, next = idx4} 
     path[idx4].prev = idx3 
     mark_as_path(idx2) 
     mark_as_path(idx3) 
     return true 
     end 
    end 

    local function euclid(dx, dy) 
     return dx*dx + dy*dy 
    end 

    local function swap() 
     local variants = {} 
     local path_center_x = path_sum_x/path_ctr 
     local path_center_y = path_sum_y/path_ctr 
     local idx1 = path.first 
     repeat 
     local idx2 = path[idx1].next 
     local idx3 = idx2 and path[idx2].next 
     if idx3 then 
      local x1, y1 = get_x_y(idx1) 
      local x2, y2 = get_x_y(idx2) 
      local x3, y3 = get_x_y(idx3) 
      local dx12, dy12 = x2 - x1, y2 - y1 
      local dx23, dy23 = x3 - x2, y3 - y2 
      if dx12 * dx23 + dy12 * dy23 == 0 then 
       local x, y = x1 + dx23, y1 + dy23 
       local idx = get_idx(x, y) 
       local dist2 = euclid(x2 - path_center_x, y2 - path_center_y) 
       local dist = euclid(x - path_center_x, y - path_center_y) 
       if is_unused[idx] and dist2<dist and is_unused[idx]~=idx2 then 
        table.insert(variants, {idx1, idx2, idx3, idx}) 
       end 
      end 
     end 
     idx1 = idx2 
     until not idx3 
     if #variants > 0 then 
     local idx1, idx2, idx3, idx = 
      (table.unpack or unpack)(variants[math.random(#variants)]) 
     -- swap idx2 and idx 
     path[idx1].next = idx 
     path[idx] = path[idx2] 
     path[idx3].prev = idx 
     path[idx2] = nil 
     mark_as_unused(idx2, idx) 
     mark_as_path(idx) 
     return true 
     end 
    end 

    local actions = {grow, inflate, swap} 

    repeat 
     random_sort(actions) 
     local success 
     for _, action in ipairs(actions) do 
     success = action() 
     if success then 
      break 
     end 
     end 
     if not success and path_ctr < L then 
     -- erase and rewind 
     while path_ctr > 1 do 
      shrink() 
     end 
     end 
    until path_ctr >= L 

    while path_ctr > L do 
     shrink() 
    end 

    local pointSequence = {} 
    local idx = path.first 
    local step = 0 
    repeat 
     step = step + 1 
     path[idx].step = step 
     local x, y = get_x_y(idx) 
     pointSequence[step] = {c = x, r = y} 
     idx = path[idx].next 
    until not idx 
    local field = 'W = '..W..', H = '..H..', L = '..L..'\n' 
    for y = 1, H do 
     for x = 1, W do 
     local c = path[get_idx(x, y)] 
     field = field..(' '..(c and c.step or '-')):sub(-4) 
     end 
     field = field..'\n' 
    end 
    print(field) 

    return pointSequence 

end 

Zastosowanie:

math.randomseed(os.time()) 

local pointSequence = generate_path(6, 7, 10) 
-- pointSequence = {[1]={r=r1,c=c1}, [2]={r=r2,c=c2},...,[10]={r=r10,c=c10}} 

przykłady wynikowe:

W = 5, H = 5, L = 10 

- - - 9 10 
- 6 7 8 - 
- 5 4 1 - 
- - 3 2 - 
- - - - - 


W = 5, H = 5, L = 19 

15 16 17 18 19 
14 1 2 3 4 
13 12 11 6 5 
- - 10 7 - 
- - 9 8 - 



W = 6, H = 7, L = 35 

- 35 34 25 24 23 
- - 33 26 21 22 
- 31 32 27 20 19 
- 30 29 28 - 18 
- 1 10 11 12 17 
3 2 9 8 13 16 
4 5 6 7 14 15 



W = 19, H = 21, L = 394 

77 78 79 84 85 118 119 120 121 122 123 124 125 126 127 128 129 254 255 
76 75 80 83 86 117 116 115 114 141 140 139 138 135 134 131 130 253 256 
73 74 81 82 87 88 89 112 113 142 145 146 137 136 133 132 - 252 257 
72 69 68 67 92 91 90 111 - 143 144 147 148 149 150 151 152 251 258 
71 70 65 66 93 108 109 110 163 162 161 160 159 158 157 156 153 250 259 
58 59 64 63 94 107 166 165 164 191 192 193 196 197 - 155 154 249 260 
57 60 61 62 95 106 167 168 189 190 - 194 195 198 241 242 243 248 261 
56 55 54 53 96 105 170 169 188 203 202 201 200 199 240 239 244 247 262 
47 48 51 52 97 104 171 172 187 204 205 206 231 232 237 238 245 246 263 
46 49 50 99 98 103 174 173 186 209 208 207 230 233 236 267 266 265 264 
45 42 41 100 101 102 175 184 185 210 211 228 229 234 235 268 269 270 271 
44 43 40 39 38 177 176 183 214 213 212 227 226 225 276 275 274 273 272 
33 34 35 36 37 178 179 182 215 216 217 218 223 224 277 278 279 280 281 
32 29 28 23 22 - 180 181 12 11 10 219 222 287 286 285 284 283 282 
31 30 27 24 21 18 17 14 13 8 9 220 221 288 289 290 291 292 293 
380 381 26 25 20 19 16 15 394 7 4 3 304 303 300 299 296 295 294 
379 382 383 384 387 388 391 392 393 6 5 2 305 302 301 298 297 312 313 
378 371 370 385 386 389 390 347 346 343 342 1 306 307 308 309 310 311 314 
377 372 369 364 363 350 349 348 345 344 341 340 333 332 319 318 317 316 315 
376 373 368 365 362 351 352 353 354 355 338 339 334 331 320 321 322 323 324 
375 374 367 366 361 360 359 358 357 356 337 336 335 330 329 328 327 326 325