Detecting gaps in grid of divs

Question

EDIT The solution has been found!

Here's a blog post about it, and here is the Github repo!

I am working on creating a grid of divs that is composed of multiple sized boxes, these sizes are set height's and widths - but are generated dynamically so each time the page is loaded there is a different grid.

My problem - I tried using Masonry, but it winds up leaving gaps, also tried isotope. I am currently floating the elements left which is causing for the breaks in the layout.

How it's built - I calculate the screen dimensions and determine the best column count for the page ranging from 1 to 6, then based on that column width I calculate a "block" this block is essentially the perfect grid. Then I loop through my elements and give them either 1x1, 1x2, 2x2 dimensions.

For reference here is another randomly generated grid

My Question - Is there a good way to detect the missing spaces - currently I am placing my red and black boxes over another grid of my "blocks", which are green, for me to see where I am missing space. I've read about the knapsack packing problem, as well as bin packing problems - and I am having a hard time making sense of either of them.

What I've tried - I have attempted to calculate as I place the blocks to determine the best size but this still results in strange behavior. I have also tried using masonry and Isotope.

I am fine with a ragged bottom edge but the actual grid cannot contain any gaps.

NOTE - The grid is composed of a potentially endless number of elements - I have been thinking if I was to take and copy an element from the bottom area and place it into the missing areas I could avoid having to "shift" elements - I just need to know how to find that missing space.

Any help or pointing in the right direction would be great!

Here is a jsfiddle

here is the base code for the js...

    (function() {
    GRID = function(el, sel) {
        var self = this,
            ran, ranSize, h, w;

        self.options = {
            el: $(el),
            sel: $(sel),
            cols: 1,
            block: {
                height: 0,
                width: 0
            },
            matrix: {
                w: [],
                h: [],
                t: [],
                l: []
            },
            row: {
                height: 0,
                width: 0
            },
            col: {
                height: 0,
                width: 0
            }
        };

/*
         * Size array
        */
        self.sizes = [];
        self.sizes[0] = [2, 2];
        self.sizes[1] = [1, 2];
        self.sizes[2] = [1, 1];



        self.setup = function() {

/*
             * Setup all options 
            */
            // block size
            self.options.block.height = (window.innerWidth / self.cols()) / 1.5;
            self.options.block.width = (window.innerWidth / self.cols());

            // row
            self.options.row.width = window.innerWidth;


            for (var i = 0; i < 60; i++) {
                $(".grid").append('<div class="box"></div>');
            }

            self.size_boxes();


        }
        self.size_boxes = function() {

            if (self.cols() == 1) {
                self.options.sel.height(self.options.block.height);
                self.options.sel.width(self.options.block.width);
            }
            else {
                self.options.sel.each(function() {

                    $this = $(this);

                    ran = Math.floor(Math.random() * self.sizes.length);
                    ranSize = self.sizes[ran];

                    if ($this.hasClass('promoted')) {
                        ran = 0;
                    }
                    if ($this.hasClass('post')) {
                        ran = 2;
                    }
                    h = self.options.block.height * self.sizes[ran][6];
                    w = self.options.block.width * self.sizes[ran][0];

                    // box sizes
                    $this.height(h);
                    $this.width(w);
                });
            }
            $(".grid .box").height(self.options.block.height);
            $(".grid .box").width(self.options.block.width);
        }
        self.cols = function() {
/*
             * Determine cols
            */
            var w = Math.floor(window.innerWidth);
            var cols = 0;

            if (w < 480) {
                cols = 1;
            }
            else if (w > 480 && w < 780) {
                cols = 2;
            }
            else if (w > 780 && w < 1080) {
                cols = 3;
            }
            else if (w > 1080 && w < 1320) {
                cols = 4;
            }
            else if (w > 1320 && w < 1680) {
                cols = 5
            }
            else {
                cols = 6;
            }
            return cols;
        }
        self.resize = function() {
            $(".grid").height(window.innerHeight);
            self.options.block.height = (window.innerWidth / self.cols()) / 1.5;
            self.options.block.width = (window.innerWidth / self.cols());

            self.options.row.width = window.innerWidth;

            self.size_boxes();
        }

        self.setup();
        return self;

    };
})();
var _GRID = new GRID('.gallery', '.box');​

Answer 1

I would keep track of your "perfect grid" with an in-memory matrix of boolean values. This matrix stores whether spaces are filled or not. Whenever you place one of your boxes, you calculate which squares get occupied and update your matrix.

Answer 2

If you're placing them in columns, simply place the divs in columns. For instance, if you've determined that there should be 4 columns:

<div>
    <div>Column 1, Div 1</div>
    <div>Column 1, Div 2</div>
    <div>Column 1, Div 3</div>
    <div>Column 1, Div 4</div>
</div>
<div>
    <div>Column 2, Div 1</div>
    <div>Column 2, Div 2</div>
    <div>Column 2, Div 3</div>
    <div>Column 2, Div 4</div>
</div>
<div>
    <div>Column 3, Div 1</div>
    <div>Column 3, Div 2</div>
    <div>Column 3, Div 3</div>
    <div>Column 3, Div 4</div>
</div>
<div>
    <div>Column 4, Div 1</div>
    <div>Column 4, Div 2</div>
    <div>Column 4, Div 3</div>
    <div>Column 4, Div 4</div>
</div>

Of course, this will only work if the divs in each column are of equal height.