algorithm - 在表内生成随机模式的最佳方法是什么

Question

我有一个表(二维数组)，c x r。需要在其中生成连接单元格的随机模式。没有 self 交叉，也没有对角线移动。例如，参见相关图片。 ex. 1 с = 6，r = 7，图案以数字显示。

我为此编写了一个函数并且运行良好，但我正在寻找硬优化。在下面的代码中，您可以看到，如果模式进入死胡同，它只会从头开始重建自己。如果模式长度接近或等于单元格数 c*r(示例中为 42)，则效率非常低。因此，为此需要一些智能解决方案，例如在用完可能的移动时对称地移动整个模式，或者向函数添加一些分析，这样它就不会陷入死胡同。同样，对于 c、r 和 patternLength 的低值，我的示例工作正常，但我正在寻找算法的完美性和高性能，即使在相当大的数字上也是如此。

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

任何关于如何实现这一点的想法或方法都将受到高度赞赏。也许是一些递归回溯或寻路或随机游走算法？

Answer 1

蛇式增长不足以获得良好的性能。
主要思想是通过添加小弯路来随机修改正在生成的路径，如下所示:

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

(注意在 4-5 段的左侧添加了额外的两个单元格)

这样的实现对于区域填充 < 95% 非常快速

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

使用示例:

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}}

结果示例:

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