generic image
Processing...
  • Games
  • Catalog
  • Develop
  • Robux
  • Search in Players
  • Search in Games
  • Search in Catalog
  • Search in Groups
  • Search in Library
  • Log In
  • Sign Up
  • Games
  • Catalog
  • Develop
  • Robux
   
ROBLOX Forum » Game Creation and Development » Scripting Helpers
Home Search
 

Filling a given area with n number of squares

Previous Thread :: Next Thread 
MrgamesNwatch is not online. MrgamesNwatch
Joined: 02 Feb 2009
Total Posts: 7729
14 Mar 2014 12:24 PM
So I have a box of a set size and a number of squares. I want to tile these squares inside the box to fill the most area possible while still fitting. Left over space is fine since the squares can't be divided and must be the same size.

Any ideas how to accomplish this? I've tried a few things, but haven't really succeeded. I have found one possible solution, but I don't quite understand it. Perhaps it could help someone? math.stackexchange.com/questions/466198/
Report Abuse
Absurdism is not online. Absurdism
Joined: 18 Jul 2013
Total Posts: 2568
14 Mar 2014 12:57 PM
The guy on StackExchange is right. His "beginner's method" is really easy to understand.

Let us say we have a 5x6 box and we want to fill it with 9 squares. The area of the box is 30 (5*6 = 30). Now, if we do this the non-optimal way, we divide 30/9 to get the area of one square. Though this is not optimal, we know that it is indeed the _maximum_ area for the square. If it is any more, then the box will overflow. Take this visual (to scale of 100):

i imgur com/aE8TZvI.png


Basically, he says we must fill one axis. We can't fill both, but we can fill one. The algorithm we'll employ checks the x-axis first. The area of a square is defined by the square of the side length. That is:

A = x^2
30/9 = x^2

Now we rearrange this equation:

sqrt(30/9) = x

We have now found the maximum side length of the square. So, we divide the length on the x-axis by the side length, or 5/(sqrt(30/9)). We then round this number up to get 3.
I'll post this to show someone is actually replying, then I'll continue in a follow-up post.
Report Abuse
Absurdism is not online. Absurdism
Joined: 18 Jul 2013
Total Posts: 2568
14 Mar 2014 01:08 PM
The 3 we received is now what we're going to call p_x. This means we can try to divide the length 6 into 3 parts (p_x parts). The area of such a square would be (5/3)^2 using that formula up there. If we multiply this by our number of desired squares, we get 25. So we fill 25 of 30 units.
If these squares squeeze together horizontally, then we p_x++ until math.ceil(6/(5/p_x)) >= 9, or the desired number of squares.

If we repeat this substep of the algorithm for the y-axis, and save the number of parts as p_y, then we get that 6/(sqrt(30/9))*9 = 29 units of 30.
We now take the greater number between x/p_y and y/p_x. This is the optimal side length.
Report Abuse
MrgamesNwatch is not online. MrgamesNwatch
Joined: 02 Feb 2009
Total Posts: 7729
14 Mar 2014 01:14 PM
Thanks, I think you covered the parts that weren't 100% clear on stackexchange. I'm still working it out, but I think I've got what I need. I will return if something goes terribly wrong. :p
Report Abuse
Absurdism is not online. Absurdism
Joined: 18 Jul 2013
Total Posts: 2568
14 Mar 2014 01:17 PM
Here is the algorithm in Lua. I've swapped p_x and p_y to make it a bit easier to understand. I'm sure you'll follow the code.

findSLOfSquares = function(x, y, n)
local p_x, p_y = math.ceil((n*x/y)^.5), math.ceil((n*y/x)^.5)
local sideX, sideY = math.floor(p_x*y / x)*p_x < n and y/math.ceil(p_x*y/x) or x/p_x, math.floor(p_y*x / y)*p_y < n and x/math.ceil(x*p_y/y) or y/p_y

return math.max(sideX, sideY)
end

Report Abuse
Previous Thread :: Next Thread 
Page 1 of 1
 
 
ROBLOX Forum » Game Creation and Development » Scripting Helpers
   
 
   
  • About Us
  • Jobs
  • Blog
  • Parents
  • Help
  • Terms
  • Privacy

©2017 Roblox Corporation. Roblox, the Roblox logo, Robux, Bloxy, and Powering Imagination are among our registered and unregistered trademarks in the U.S. and other countries.



Progress
Starting Roblox...
Connecting to Players...
R R

Roblox is now loading. Get ready to play!

R R

You're moments away from getting into the game!

Click here for help

Check Remember my choice and click Launch Application in the dialog box above to join games faster in the future!

Gameplay sponsored by:
Loading 0% - Starting game...
Get more with Builders Club! Join Builders Club
Choose Your Avatar
I have an account
generic image