我怎样才能递归地划分迷宫中的网格？

Question

我正在尝试使用递归除法创建迷宫生成器。我用这个 link： Maze generation - recursive division (how it works?) 作为我解决问题的指南。

到目前为止，这是我的代码：

import random
# Maze: 0 - N : 4 x 4 Grid
# Grid: 0 - (2n + 1) : 9 x 9 Array

# TODO: Now, Find a way to save the previous walls and not just only one at a time 

rows = 9
cols = 9
start = 2
end  = 7
# -------------------------------------------------------------------------------------
# Lists for all even / odd numbers in given range
evens = [n for n in range(start, end+1) if n % 2 == 0]
odds = [m for m in range(start, end+1) if m % 2 != 0]
# Generate random even/odd integer value for walls/ passages respectively
# Walls: Not sure if 2 variables are necessary-----------------------------------------
wallX = random.choice(evens)
wallY = random.choice(evens)
# Passages
passageX = random.choice(odds)
passageY = random.choice(odds)
#--------------------------------------------------------------------------------------
# Random direction: True = Horizontal Slice, False = Vertical Slice
randomDirection = random.choice([True, False])

arr = [['0' for i in range(cols)] for j in range(rows)] 

def displayBoard(arr):
  print()
  for i in range(len(arr)):
    for j in range(len(arr[i])):
    # Print just the edges 
      if i == 0 or i == 8 or j == 0 or j == 8:
        print('*', end = ' ')
      # Print wall
      elif arr[i][j] == 1:
        print('.', end = ' ')
      else:
        print (' ', end = ' ')
    print()

# Function choose direction to slice
def chooseDir(arr):
  for i in range(len(arr)):
    for j in range(len(arr[i])):
      # Horizontal Direction Slice
      if randomDirection:
        arr[wallX][j] = 1
        arr[wallX][passageY] = 2
        print(arr[i][j], end = ' ')
      # Vertical Slice
      else:
        arr[i][wallY] = 1
        arr[passageX][wallY] = 2
        print(arr[i][j], end = ' ')
    print()
  displayBoard(arr)

print()

mazeX = 0
mazeY = 0
# Write the recursive division function:
def divide():
  chooseDir(arr)
  print()
divide()

这会产生一个网格，该网格在偶数索引处随机切片（创建墙）并在奇数索引处创建通道。输出：1 = wall，2 = passage made

0 0 0 0 1 0 0 0 0 
0 0 0 0 1 0 0 0 0 
0 0 0 0 1 0 0 0 0 
0 0 0 0 2 0 0 0 0 
0 0 0 0 1 0 0 0 0 
0 0 0 0 1 0 0 0 0 
0 0 0 0 1 0 0 0 0 
0 0 0 0 1 0 0 0 0 
0 0 0 0 1 0 0 0 0 

* * * * * * * * * 
*       .       * 
*       .       * 
*               * 
*       .       * 
*       .       * 
*       .       * 
*       .       * 
* * * * * * * * *

我的问题是我不知道如何编写递归函数。我是不是在建墙时创建的两个新单元格上调用分裂并不断划分“子单元格”。

或者我知道 4 x 4 单元格网格将提供 9 x 9 的阵列，我将总共有 16 个单元格。然后我可以调用除法直到满足某个条件，递增到下一个单元格直到访问所有 16 个单元格。在这两种情况下，我都不确定如何表示新创建的 walls/cells 以便我可以编写除法函数。到目前为止，我一直在使用网格坐标。

Answer 1

您问“我是否在制作墙壁时创建的两个新单元格上调用分裂并不断划分“子单元格””？是的，这就是递归的本质。解决大问题，解决小问题。重复较小的问题。最终，问题小到可以轻松解决。然后把所有的小问题重新组合起来解决原来的问题。

对于迷宫，第一面墙将迷宫分成两个较小的迷宫。使用相同的算法将它们分开，并且没有 4 个较小的迷宫。重复直到子迷宫太小不能再分裂。

你的分割迷宫的代码应该放在一个函数中。如果子迷宫大到可以拆分，函数会拆分子迷宫，然后在两个较小的子迷宫上调用自己。

我怎样才能递归地划分迷宫中的网格？

How can I recursively divide the grid in my maze?

python

recursion

maze