使用二进制空间分区来布置游戏中的场景

问:如何在大场面中随机摆放这些场景,使它们不重叠?

我正在使用Godot引擎来创建一个小型的2D RPG类游戏。 我正在以一种程序化的方式铺设一座村庄,最大的房子首先被放下,然后是小房子,等等。 这些房屋被设置在一个tilemap ,而它本身被设置在一个更大的tilemap场景中。 我尝试过使用Vector2对象中的随机值随机设置它们,但它们可能会相互重叠。 经过大量的实验,我发现了一篇关于二进制空间分区的文章,并试图find一个在Godot引擎中做出的例子。 我在YouTube上find了这个video ,并使用该代码来制作一个小function:

 func bsp(map_size_width, map_size_height): var rec1 var rec2 var back = [] var contents = [[0, 0, map_size_width, map_size_height]] for i in range(0, 4): back.clear() for rec in contents: randomize() if rec[2] > rec[3]: var width = round(rand_range(0.3,0.7) * rec[2]) rec1 = [rec[0], rec[1], width, rec[3]] rec2 = [rec[0]+width, rec[1], rec[2]-width, rec[3]] else: var height = round(rand_range(0.3,0.7) * rec[3]) rec1 = [rec[0], rec[1], rec[2], height] rec2 = [rec[0], rec[1] + height, rec[2], rec[3] - height] back.append(rec1) back.append(rec2) contents.clear() for r in back: contents.append(r) return contents 

为了使用它,我在tilemap传递场景的大小(以瓦片为单位),并且吐出一个包含每个矩形起点以及宽度和高度的数组。 示例输出如下所示:

 [[0, 0, 7, 7], [7, 0, 13, 7], [0, 7, 6, 14], [6, 7, 14, 14], [20, 0, 10, 4], [20, 4, 10, 7], [20, 11, 10, 4], [20, 15, 10, 6], [0, 21, 8, 4], [0, 25, 8, 5], [8, 21, 4, 5], [8, 26, 4, 4], [12, 21, 5, 5], [12, 26, 5, 4], [17, 21, 6, 9], [23, 21, 7, 9]] 

而一个可以使用这个函数的更可视化的例子如下所示:

二进制空间分区的可视化表示

现在我要做的就是弄清楚如何将一个房子分配给一个矩形。 我试着先把房子的大小匹配到数组中的匹配元素。 但是,这也会导致房屋重叠。 然后,我想在与一个房子元素匹配的时候拿出这个元素。 但是,这可能导致房屋的场面,甚至没有被计算在内。

FWIW,这里是我正在使用的当前代码:

 # House 1 var h1 = get_node("House1").get_used_rect().size # House2 var h2 = get_node("House2").get_used_rect().size # House 3 var h3 = get_node("House3").get_used_rect().size # Our function in action. var binary_things = bsp(world_tile_width, world_tile_height) # Holds the data for the house scenes var coor = [] # Set the largest house, "h3", first. for i in [h3,h2,h1]: # Go through and compare the sizes of the houses. for g in range( binary_things.size() ): # If there is a match, append it to the "coor" array. if binary_things[g][2] > i.width and binary_things[g][3] > i.height: coor.append(binary_things[g]) # Remove it from circulation. binary_things.remove(g) break # Create the Vector2 objects for the houses. var w = Vector2( coor[0][0], coor[0][1] ) var v = Vector2( coor[1][0], coor[1][1] ) # In tests, it is found that the third element in the "coor" array is not filled. var q = Vector2( coor[2][0], coor[2][1] ) # Convert the tile coordinates to pixel coordinates. var translated1 = map_to_world(w) var translated2 = map_to_world(v) var translated3 = map_to_world(q) # Set the scenes in the larger scenes. scene_1.set_pos(translated1) scene_2.set_pos(translated2) scene_3.set_pos(translated3)