连接的房间

Connecting Rooms

本文关键字：房间 连接      更新时间：2023-09-26

我为自己正在开发的一款游戏创造了一个简单的算法，即创造一个类似洞穴的结构。该算法输出一个代表开放区域的二维位数组。例子:

000000000000000000000000
010010000000000111100000
011110000000011111111000
011111110000011111111100
011111111001111111111110
011000000000001111000000
000000000000000000000000

(0代表墙，1代表开放区域)

问题是，算法有时会创建一个洞穴，其中有2个不连接的部分(如上面的例子)。我写了一个函数，它给了我一个数组的数组，其中包含每个区域开放点的所有x, y位置

我的问题是，给定一些包含每个开放区域的所有x,y坐标的列表，将这些区域"连接"起来的最快方法是什么?是一个至少2厚度宽的走廊。

(我在javascript中编写，但即使只是伪代码也会帮助我)

我试过比较从一个区域的每个点到另一个区域的每个其他区域的距离，找到距离最近的两个点，然后从这两个点切割出一条路径，但这种方法是一种缓慢的方法，我希望有另一种方法

给定两个洞穴A和B，选择A中的x点和B中的y点(随机选择，最接近的两个或局部最接近的两个更好)。在a和B之间钻一条厚度为2的走廊(使用布里森汉姆算法)。如果你有多个不相连的洞穴，对所有洞穴图的最小生成树的每条边(A,B)执行上述操作(边权是如果你选择这条边，你将钻出的走廊的长度)。

编辑为:要近似两个洞穴之间的距离，可以使用爬山。它将在O(n)内返回凸洞的全局最小值，而不是原始的O(n2)。对于非凸洞穴，进行多次迭代爬坡，随机选择初始猜测。

如果你需要精确的最小解，你可以考虑先建立洞穴的边界，然后应用O(nm)算法。这将消除比较洞穴内部点之间距离的需要。一旦你知道了每对洞穴之间的距离，你就可以建立最小生成树，然后你就可以钻隧道了。

由于我从你的描述中不知道太多，这里有一些我想考虑的提示:

你如何寻找最近的点对?您是否使用简单的蛮力方法，从而获得O(n*n)的运行时间?还是使用更有效的变种占用O(n log n)时间?

如果你已经得到了最近的点，我会使用一个简单的划线算法。

另一种方法可能是生成一个明确只有一个连接区域的结构。因此，您可以这样做:首先，您取一个随机单元(x,y)并将其设置为1。然后，你遍历它的所有邻居，并随机将其设置为1或将其保留在0。对于每个设置为1的单元格，您也可以这样做，即遍历它的邻居并将它们随机设置为1或0。这保证了你不会有两个独立的区域。

确保这一点的算法可以是以下(在python中):

def setCell(x,y,A):
    if x>=len(A) or y>=len(A[0]) or x<0 or y<0:
        return
    A[x][y] = 1
def getCell(x,y,A):
    if x>=len(A) or y>=len(A[0]) or x<0 or y<0:
        return 1
    return A[x][y]
def generate(height, width):
    A = [[0 for _ in xrange(width)] for _ in xrange(height)]
    from random import randint
    import Queue
    (x,y) = (randint(0, height-1), randint(0, width-1))
    setCell (x,y,A)
    q = Queue.Queue()
    q.put((x,y))
    while not q.empty():
        (x,y) = q.get()
        for (nx, ny) in [(x+1,y), (x-1,y), (x,y+1), (x,y-1)]:
            if randint(0,8)<=6:
                if getCell(nx,ny,A)==0:
                    setCell(nx,ny,A)
                    if randint(0,2)<=1:
                        q.put((nx,ny))
    return A
def printField(A):
    for l in A:
        for c in l:
            print (" " if c==1 else "X"), 
        print ""

然后printField(generate(20,30))完成工作。也许你需要调整参数来适应你的需要。

相关文章：