[Lua help] Function to jigsaw rectangles as closely / optimally

[MirceaKitsune]

This is a rather general maths and Lua question, but since it's for a Minetest mod I posted here. I've been struggling to figure out a formula for hours but with no success, so I need help. This is the problem:

Let's say I have a table consisting of other tables, each containing x and z coordinates of a rectangle's size. For example:

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

Code: Select all

local rectangles = { }
table.insert(rectangles, { size_x = 10, size_y = 15 }

The 'rectangles' table would contain any count of such sub-tables, each specifying various sizes. Next I have a vector position which is a location in the world. I want to add all rectangles in such a way to fill an area from that position (left-to-right and top-to-bottom) and have as little empty spaces between the rectangles as possible, aiming for a rectangular pattern to place them in. Each rectangle is ok to place anywhere randomly as long as this purpose is met, but must never overlap another. My aim is to obtain the center origin (node) at which I'd have to place each rectangle as x and z coordinates from this calculation. Since Lua is slow so we'd want as few loops and checks as possible.

Imagine you have a rectangular table. You also have a number of paper cutouts which can be of any size and shape, but all of them are squares / rectangles. You need to jigsaw them in such a way to leave as little empty spaces between them, starting from the upper-left corner of the table. All of them must be used up and their placement should resemble a square / rectangular coverage. The end objective is to know the center of each rectangle.

Can anyone figure the Lua formula for doing this? It would allow me to have a much more correct pattern in my Structures mod and an optimal natural villages spawn system. Thanks.

[MirceaKitsune]

Still haven't written any code, but I thought of a smarter way to get this done since yesterday: First we fill a row with rectangles (up to down) and only get to the next column after that row is filled, repeating the process slightly to the right.

One idea would be to store the right edges of all buildings in the previous column and analyze them for the next column. So whenever a building is placed in the next column, its length is checked (up and down). We scan how many right edges from the left buildings it takes up. If it takes more than one, we add from the topmost point and against the rightmost edge.

This is a doable system that would allow accurate enough placement. Only problem is figuring out how to write it in Lua code, but I guess that shouldn't be a big problem. Will see how it goes.

[Sokomine]

Keep it simple. There's not much time at mapgen for complex algorithms, and real towns/villages are chaotic to some degree as well. Plus you don't have to create too big cities - a few houses more or less next to each other may look well enough for a village already.

[MirceaKitsune]

Keep it simple. There's not much time at mapgen for complex algorithms, and real towns/villages are chaotic to some degree as well. Plus you don't have to create too big cities - a few houses more or less next to each other may look well enough for a village already.

I agree with everything except the last part. The aim is to eventually be able to create pretty big towns, no matter how laggy that would be. Of course I wish to reduce the lag and calculations as much as possible, so I will do what can be done to keep it as optimal too.

[Sokomine]

Fine! I'm looking forward to it. For my own mod, I'm not going to spawn entire villages for now and instead let the player decide what ought to be built where. I really hope we'll get that voxel-import-function soon.

[sfan5]

Fine! I'm looking forward to it. For my own mod, I'm not going to spawn entire villages for now and instead let the player decide what ought to be built where. I really hope we'll get that voxel-import-function soon.

https://github.com/minetest/minetest/commit/c1b829077a3518f3a129eee11887b2358a53f20b#L0R1290 may help
WorldEdit already has support for the Decoration Schematics.

[MirceaKitsune]

I managed to figure it out. On each column, every building that spawns registers its upper-right corner into a table. When we get to the next column and start filling the rows there, we check which of the registered corners from the previous row intersect the building on the left-right axis. For each corner that does, we register the furthest (rightmost) distance and push the building to it. For more detail on how I used it, see this post.