二维阵列中的随机障碍生成算法

Question

我的问题是在一个充满障碍物（我无法访问的单元格）的二维数组中找到一条从给定起点到给定终点单元格的路径。虽然我认为我已经找到了一种算法，在已知障碍单元的情况下，每次都能找到最佳路径，但问题是这些障碍单元并不是事先指定的，每次启动程序时都必须随机生成。你知道吗

我一直在努力寻找一种算法，它可以伪随机地生成这些障碍，同时确保每次从开始到结束的路径都是可用的。有人有什么想法吗？提前谢谢。你知道吗

这就是我到目前为止对障碍（python）的看法：

free=N*N-4*(N-1)
obstacles=round(free*p)
#for j in (1, N):
obstacle_free_points = {S, F}
count=0
#j = j + 1
j=self.prims(N,S,F)
while count<obstacles:
    x=randrange(1,N-1)
    y=randrange(1,N-1)
    if (x,y) not in obstacle_free_points or j:
        self.grid[x][y]=1
        count=count+1

这是我以后寻找路径的BFS（python）：

def bfs(self,N,S,F):
   previous=np.zeros((N, N),dtype=object)
   seen=set()
   q=Queue()
   q.put(S)
   while not q.empty():
       node=q.get()
       if node==F:
           path=[F]
           while node!=S:
               path.append(previous[node[0]][node[1]])
               node=previous[node[0]][node[1]]
           return path
       for n in grid.adjacent(self,node):
           if n not in seen:
               q.put(n)
               previous[n[0]][n[1]]=node
       seen.add(node)

Answer 1

如果障碍物密度不是预先确定的，那么这可能对您很有用：

1. 从每个方块的障碍物开始，除了起点和终点。你知道吗
2. 随机清除方块，直到开始方块连接到结束方块。你知道吗
3. 清除任意多的附加方块。你知道吗

可以使用不相交的集合数据结构来确定开始和结束何时连接：https://en.wikipedia.org/wiki/Disjoint-set_data_structure。最初，每个正方形都在它自己的集合中，清除一个正方形时，它的集合将与其所有清除的邻居的集合合并。你知道吗