Genetic algorithm bin packing

Pixbae · 4 Dec 2012, 18:24

Hi everyone! I want to develop a plugin, I know nothing of programming but will learn so I can develop this. I'd just like some pointers or advice on how to tackle this problem.

I want to develop a plugin in which I input areas(represented by rectangles) and it organizes them and presents me various possible solutions to a floor plan, probably utilizing a genetic algorithm.

It would group them in the least possible space (not within a container, no boundaries). at the same time, I want some of these rectangles to be closer to others, so there is a hierarchy of proximity between rectangles. For example, if I wanted various possibilites of a house floor plan, I'd input spaces such as kitchen, dinning room, living room, bedrooms, etc., and it would not only group them in little space, but also ubicate them according to desirable proximities (kitchen - dinning room for example).

So basically, it would be some sort of 2d bin packing, but is there a way to control how the objects "pack" so I have the desirable proximities between them?

I´ve played a bit with Rhino Grasshopper, but it isn't able do what I want for two reasons: 1- galapagos, which is a genetic algorithm plugin, just accepts 1 fitness. I need multiple fitnesses to fulfill all conditions of proximity.
2- I haven't figured out how to detect collision in Rhino (I know this is possible in SU)

Is it possible to develop a genetic algorithm with multiple fitnesses? so it searches for various solutions taking into consideration ALL of the desirable conditions.

Is it possible to develop this within SU?, or could I use an external appliaction such as excel, (is it possible to have compatibiltiy between SU and other programs?)

Thanks in advance, open to suggestions,ideas or anything.

Aerilius · 4 Dec 2012, 19:12

It is possible (it is possible to implement the logic in probably any language, only what you want to do with it depends on the available APIs/UI).

To keep it simple, I would create a component of a box (maybe with open top). Then the plugin would insert component instances and scale and move them to the positions calculated by the bin packing.

First you need to know (or think out) an algorithm to solve the problem, because being able to program doesn't help further if you don't know what to program.
If you just need a simple bin packing algorithm without extra conditions, you can take one from the internet: https://encrypted.google.com/search?hl=en&q=texture%20packing%20algorithm (I for example implemented the 2. search result in an unfinished texture baker)

Secondly, to get started with Ruby is not difficult (but it is helpful if you have at least once worked with another scripting/programming language). When you start from zero, do tutorials first (It's possible to become fluent in Ruby within a month)
http://tryruby.org/levels/1/challenges/0
Take a look at all the ressources here:
http://sketchucation.com/forums/viewtopic.php?f=180&t=10142#p269709

Chris Fullmer · 4 Dec 2012, 19:53

Yeah seriously, just get started learning how to make a box in SketchUp.

SketchUp doesn't do collision testing like you might want. But with simple boxes I'm sure you could figure something out using plane intersections.

You would be better off if you had a genetic algorithm or whatever already made that you could just supply coordinates to and it would supply new coordinates. Anyhow, good luck!

pilou · 4 Dec 2012, 22:19

@unknownuser said:

I want to develop a plugin, I know nothing of programming but will learn so I can develop this.

Learning programming is 3 years minimun before make anything you want!
Especially for your subject!
You have better time to use existing programs and use them with tricky some "physics" one

By example with "Sketchyphysics"
make a box a little more bigger of what you want without top
Drop inside a pile of your different pieces
and move in x and y very strongly
At the end all boxes are take place
Just look if it's optimum
If not repeat again

jolran · 4 Dec 2012, 22:37

I would recommend starting with e-book Automatic Sketchup.
http://www.autosketchup.com/
It won't learn you ruby in depth, but at least get you going programming in Sketchup, right away. You will then get a feeling for if it's the right activity for you.
A very timeconsumming one I might add

Pixbae · 5 Dec 2012, 00:36

Thanks everyone for the help, I'll get started right away!

thomthom · 5 Dec 2012, 08:41

Once you get your head wrapped around programming and you start to develop your plugin I recommend you read through this guide on how to ensure your plugin doesn't clash with other plugins: http://www.thomthom.net/thoughts/2012/01/golden-rules-of-sketchup-plugin-development/

There's also many more articles on my blog detailing various topics.