Space in grid algorithm

madwormer2

I need to make an algorithm that looks at a grid of 100x100 currently stored in a multidimensional array (Array ( [0] = Array( 1, 0, 0, 1, 0, 1...), [1] = Array(0,1,1,1,0,0 etc...))) and each array item is either true or false (on or off, black or white, you get the idea.)

This is to be a grid of items of random dimensions, ranging from just a 1x1 to maybe a 10x5 item.

I have been puzzling over a way to search for the next available "space" in the grid, given a specific dimension you need to fit in the grid. I am able to do any one-row items with ease using a simple loop, but I'm having trouble extending it.

I don't necessarily need someone to write it for me (where's the fun in that?) but I'd just like your view on how you'd go about tackling this problem.

I'll provide some code when I get my laptop back from my girlfriend.

examancer

I encountered a similar problem. I designed a javascript-aided window GUI with all windows making use of absolute positioning. For each window I had upper left position values (x/y) and dimension values (width/height). When the user added the window I needed my PHP script to find the first open spot without overlapping any other windows.

I'm not at home right now so I can't show you the LayoutManager class I wrote to handle this problem, but the solution I ended up using does range checking to determine if window overlaps another. It it does overlap, the new window is moved to the next possible spot. My script increments the new window vertically downwards by a fixed number of pixels, then once a max is reached it starts a new column, repeating the process until an open spot is found.

To do range checking you first gather the maximum and minimum width and height positions for each "window". To test if two windows overlap you need to actually need to do a total of 8 conditionals (4 tests for the width range, and four for the height range). The logic would look something like this:

if (
  (
    ($firstWindowMinX >= $secondWindowMinX && $firstWindowMinX <= $secondWindowMaxX) ||
    ($firstWindowMaxX >= $secondWindowMinX && $firstWindowMaxX <= $secondWindowMaxX)
  ) && (
    ($firstWindowMinY >= $secondWindowMinY && $firstWindowMinY <= $secondWindowMaxY) ||
    ($firstWindowMaxY >= $secondWindowMinY && $firstWindowMaxY <= $secondWindowMaxY)
  )
) { echo "Windows overlap!! ... I would increment the position (vertically, horizontally, or both) here."; }

There may be a syntax error or some problem with my logic somewhere in there, because I wrote it free-hand, but that should give you an idea of how it works.

There may be an easier/faster way to do range checking, but if so I haven't found it. If you find one let me know!

Weedpacket

Just playing with the idea idea to see what I can get starting from scratch, here.

First of all, don't maintain every single point, just maintain a list of rectangular regions in which boxes can be inserted. When you start out the list will contain only one region - the entire space. Call it [0,0,fullwidth,widthheight]; the zeros are x and y coordinates. Keep the list sorted by x and y coordinate.

Now consider adding a box [w,h]. You will take two passes through the list.

On the first pass you are looking for a region [x,y,width,height] that is large enough to contain the box (i.e., width>=w and height>=h). Assuming you find one, its x and y coordinates give you the box's position, and you can go on to the second pass.

In the second pass you look at each region in the list and determine if it intersects with your box (there will be at least one such). If it does, remove it from the list and add up to three more new regions (since you're traversing the list it may be easier to build a new list, copying nonintersecting regions over).

Since the box will touch or overlap at least one edge of each region, the situation will look something like (assuming we're talking about the top edge)

a----e====f----b
|    |****|    |
|    |****|    |
|    |****|    |
i    g----h    j
|              |
c----k----l----d

Where the region is marked out by a,b,c,d; the part of the box intersecting the region is e,f,g,h; and i, j, k and l show where the edges of the box would meet the sides of the region if they were extended.

The region marked out by a,b,c,d is thrown away, and replaced by three new regions: those marked out by a,e,c,k; f,b,l,d; and i,j,c,d (yes, they overlap each other). If the box meets more than one edge, then fewer regions will be produced; for example, if the box meets both the top and bottom edges then i,j,c,d disappears.

madwormer2

After reading your input, I have decided to go with the following method.

I make a list of coordinates and put them as array keys (one for each coordinate on the grid.) Then I loop through the existing data, if it comes across an occupied cell, it deletes the items in a box x to the left and y upwards. After it's passed through once, we should be left with a single array with a list of places we can put the box (which I can parse with explode later.)

<?php
$a = Array();
$clear = Array();
for($i=0;$i<20;$i++){
	$a[$i] = Array();
	for($j=0;$j<20;$j++){
		$a[$i][$j] = rand(0,1);
		$clear[$i.';'.$j] = 1;
	}
}
?>
<style type="text/css">
	.a { background-color: #FFF; }
	.b { background-color: #000; }
	.c { background-color:green;}
	td{line-height:10px; height:10px; width:10px;}
</style>
<?php
function search($x,$y,$size){
global $a,$clear;
$size = $size;
	foreach($a as $row => $val){
		foreach($val as $col => $cell){
			if($cell == 1){
				for($i1=($y-1);$i1>=0;$i1--){
					for($i2=($x-1);$i2>=0;$i2--){
						unset($clear[($row-$i1).';'.($col-$i2)]);
					}
				}
			}elseif(($row+$y) > $size || ($col+$x) > $size){
				//echo ($row+$y).';'.($col+$x).'<br>';
				unset($clear[($row).';'.($col)]);
			}
		}
	}
}
search(4,2,20);
print_r($clear);
?>
<table border="1" cellspacing="0" cellpadding="0">
<?php
foreach($a as $i => $b){
	echo '<tr>';
	foreach($b as $j => $c){
		if(isset($clear[($i).';'.($j)])){ $c = 'c'; }
		else $c = ($c?'b':'a');
		echo '<td class="'.$c.'">&nbsp;</td>';
	}
	echo '</tr>';
}
?></table>

This is what I have, it finds the top left corner of the spaces that can be filled with our new item. Although, I can't seem to stop the right hand cells from telling me they can fit in a 10x2 starting at column 18, which clearly isn't right.

Edit: Had me rows and me columns mixed up 😃