lyquix-owner/js-grid-boxes.html

## readme.md

      
    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)

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