|
<!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> |
