Skip to content

Instantly share code, notes, and snippets.

@lyquix-owner

lyquix-owner/js-grid-boxes.html

Last active August 10, 2016 03:58
Show Gist options
  • Save lyquix-owner/fbfbe450980c21646f8a to your computer and use it in GitHub Desktop.
Save lyquix-owner/fbfbe450980c21646f8a to your computer and use it in GitHub Desktop.
Download ZIP
Places an ordered list of box elements of any size in a grid of specific dimensions.
Raw
readme.md

The Problem

We have a list of "stories", each is an html block and its size is either 1x1, 2x1, 2x2 or 4x2. We need to fit them in a grid that is 8x3. We need to respect the order of the list as long as they can fit the grid, otherwise stories are skipped.

The Solution

Our algorithm creates an array of arrays that represents each cell in the grid. Initially all cells as set to false to represent that they are empty.

We create an array of boxes, to represent our list of stores. Each box has a width and height, which can be one of the four sizes: 1x1, 2x1, 2x2 or 4x2

We use a pointer element that has the grid coordinates of the next open space.

The algorithm sweeps the boxes list. On each item it checks if the box fits in the grid at all from the current pointer position. If it does fit, then it checks that all the cells needed by the box are still empty. If yes, then the box is placed, the grid array is updated, and the pointer is moved to the next open spot.

When we are unable to place a box we jump ahead it in the list until we find a box that we can place in the space. Once we are able to place a box, we return to the first box that was not place and try with it again.

Placing on the grid is done by setting the CSS left/top and width/height properties.

This algorithm accounts for edge situations like running out of boxes before filling the grid, and unable to place any boxes while still having space (but all available boxes are larger)

Raw
js-grid-boxes.html
<!DOCTYPE html>
<html lang="en">
<!-- test this at https://jsfiddle.net/lyquix/j3sss39o/ -->
<head>
<meta charset="utf-8">
<style>
.grid {
border: 1px solid #000;
position: relative;
}
.box {
position: absolute;
border: 1px solid #ccc;
box-sizing: border-box;
background-color: #eee;
}
</style>
<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/2.1.4/jquery.min.js"></script>
<script>
// set grid
var gw = 8; // grid width
var gh = 3; // grid height
var pxw = 50; // pixels per grid block width
var pxh = 50; // pixels per grid block height
jQuery('.grid').css({width : gw * pxw, height : gh * pxh});
// create list of 100 boxes of random sizes
var sizes = [{w : 1, h : 1}, {w : 2, h : 1}, {w : 2, h : 2}, {w : 4, h : 2}];
var boxes = new Array();
for ( i = 0; i < 100; i++) {
var rand = Math.floor(Math.random() * sizes.length);
boxes[i] = sizes[rand];
}
// pointer to the next empty spot
var pointer = {x : 0, y : 0};
// setup the grid (all empty)
// saves what spots are empty (false) or filled (true)
var grid = new Array();
for (var y = 0; y < gh; y++) {
grid[y] = new Array();
}
for (var y = 0; y < gh; y++) {
for (var x = 0; x < gw; x++) {
grid[y][x] = false;
}
}
// cycle through boxes
var used = new Array(); // keeps track of used boxes
var b = 0; // current box id
var l = 0; // counts loops
while (b < boxes.length) {
l++; if (l > 1000) break; // avoid infinite loops
console.log(b, boxes[b], pointer, used);
// check if box has been used already
if (used.indexOf(b) == -1) {
if (placeBox(b)) {
// box was placed, add to used and go to next
used.push(b);
b++;
} else {
if (b == boxes.length - 1) {
// we couldn't place the last box, nowhere to jump ahead
b++;
} else {
// box was not placed, jump ahead
console.log('box not placed, jumping ahead');
var j = b + 1; // jump-ahead box id
var l = 0; // counts looks
var added = false;
while (j < boxes.length) {
l++; if (l > 1000) break; // avoid infinite loops
console.log(j, boxes[j], pointer, used);
if (used.indexOf(j) == -1) {
if (placeBox(j)) {
// box was placed, add to used and break the jump ahead cycle
used.push(j);
added = true;
j = boxes.length;
console.log('box placed, going back')
} else {
// box was not placed, try next
j++;
}
} else {
// box already used, try next
j++;
}
}
if (!added) {
// none of the jump ahead boxes was placed, break the main cycle
b = boxes.length;
}
}
}
}
// box has already been used, move to next
else {
console.log('box already used');
b++;
}
}
function placeBox(i) {
var added = false;
// does the box fit the grid?
if (pointer.y + boxes[i].h <= gh && pointer.x + boxes[i].w <= gw) {
// does it fit the empty spaces?
var gridfit = true;
for (var y = pointer.y; y < pointer.y + boxes[i].h; y++) {
for (var x = pointer.x; x < pointer.x + boxes[i].w; x++) {
if (grid[y][x] == true) gridfit = false; // one of the spots is taken
}
if (!gridfit)
break;
}
if (gridfit) {
// append box
jQuery('.grid').append('<div class="box" style="width: ' + (boxes[i].w * pxw) + 'px; height: ' + (boxes[i].h * pxh) + 'px; left: ' + (pointer.x * pxw) + 'px; top: ' + (pointer.y * pxh) + 'px;">' + i + '</div>');
added = true;
// fill the grid space
for (var y = pointer.y; y < pointer.y + boxes[i].h; y++) {
for (var x = pointer.x; x < pointer.x + boxes[i].w; x++) {
grid[y][x] = true;
}
}
// move pointer to next available position
var gridfull = true;
// asumes grid is full unless we find an empty spot
for (var y = 0; y < gh; y++) {
for (var x = 0; x < gw; x++) {
if (grid[y][x] == false) {
// save the empty position in pointer
pointer.x = x;
pointer.y = y;
// grid is not full
gridfull = false;
// break the cycle
y = gh;
x = gw;
}
}
}
// is the grid full?
if (gridfull) {
// place pointer outside grid, break main boxes cycle
pointer = {w : gw, h : gh};
b = boxes.length;
console.log('grid is full');
}
}
}
return added;
}
</script>
</head>
<body>
<div class="grid"></div>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment