# Using binary space partition to lay out scenes in game

Q: How can I randomly lay out these house scenes in the larger scene such that they don't overlap?

I'm using the Godot Engine to create a little 2D RPG kind of game. I'm laying out a village in a procedural fashion where the largest house is first put down, then the smaller house, and so on. These houses are set in a tilemap, and that itself is set in a larger tilemap scene. I've tried randomly setting them up by using a random value in a Vector2 object, but they may overlap one another. After a lot of experimentation, I happened upon an article about binary space partitions and sought to find an example of this made in the Godot Engine. I found this video on YouTube and used that code to make a small 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


To use it, I pass the size of the scene (in units of tiles) in the tilemap and it spits out an array which holds the origin of each rectangle, as well as its width and height. An example output looks like this:

[[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]]


And a more visual example that could use this function looks like this:

Now all I need to do is figure out how to assign one house to one fitting rectangle. I have tried first matching the size of the house scene to a matching element in the array. However, this, too, can lead to overlapping houses. Then I thought of taking out the element when it's matched with a house element. But this can lead to house scenes which don't even get counted.

FWIW, here's the current code that I'm using:

# 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)

• Presumably h3 is the one that isn't fitting. If so, then I think you are splitting up the map too many times. If I understand that bsp function correctly then changing the range in for i in range(0, 4): to something smaller should work. You might still want a fallback layout in case all the houses don't fit if that makes them fit most of the time. Commented Oct 20, 2017 at 10:19
• Yeah, I was thinking of using a fallback layout. Commented Oct 20, 2017 at 18:03