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 > rec: var width = round(rand_range(0.3,0.7) * rec) rec1 = [rec, rec, width, rec] rec2 = [rec+width, rec, rec-width, rec] else: var height = round(rand_range(0.3,0.7) * rec) rec1 = [rec, rec, rec, height] rec2 = [rec, rec + height, rec, rec - 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] > i.width and binary_things[g] > 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, coor ) var v = Vector2( coor, coor ) # In tests, it is found that the third element in the "coor" array is not filled. var q = Vector2( coor, coor ) # 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)