Skip to main content
gamedev.net
🔒 Locked

[Algorithm]: Allocating blocks in a 2d array

Started by Ysaneya Aug 17, 2000 at 8:56 AM 33 replies 2.1k views
Original Post
Ysaneya
Ysaneya
Well, it''s a quite simple problem, with a not-so-simple solution. I have a 2d array of bits (0=empty,1=allocated). I''d like to write a function to allocate a block (a rectangle of a given size X,Y) in this 2d array. We give X and Y in argument. The function must return an empty area position in this array. The array is N*N size (with N=2^m) if that helps. And i want this search to be *fast*. Very *fast* Memory isn''t a problem, so.. The first idea is simply to parse each possible position (x,y) in the 2d array, and to check in the block fits or not. This is not fast enough I''ve also been thinking of using a hashtable, a tree of nodes (0=empty,1=some blocks allocated,2=totally filled), etc.. but it''s hardly practical. Any suggestion ? Code ? Links ? Ideas ? Y.
Osc
Osc
Here's an idea...

You can maintain a collection of available blocks identified by their top-left corner and width/height. At initialisation, this collection will contain only one block (as the whole 2D array will be available).

To allocate a block, search the collection for an available block with width and height at least as large as X and Y (search the smallest first). If the search is successful, remove the block from the collection. Allocate the necessary bits, then add 0, 1, or 2 blocks back into the collection (depending on how much was allocated).

For example, say you start with a 16x16 block available, and you want to allocate a 4x3 block. Remove the 16x16, allocate the 4x3, and add a 4x13 and a 12x16 block back into the collection. If you then want to allocate a 6x8, remove the 12x16 and replace with 6x8 and 6x16.

I would suggest using the available block sizes as a key to the collection (perhaps a hash table?). If you're going to be deallocating blocks as well, you might want to build some code to work through the collection and combine two or more blocks into bigger blocks where possible.

Hope this helps,

Osc.


Edited by - Osc on August 17, 2000 10:21:06 AM
Ysaneya
Ysaneya
Nice idea, but it doesn''t seem to be working.. how could i allocate, say, a 16x1 block after i allocated the 4x3 block in your example ?

Y.
TimSmith
TimSmith
Hmmm. This is actually a very interesting problem. One question, are you looking for first-fit, or best-fit?

Tim
Ysaneya
Ysaneya
It does not matter if there are "holes" finally left in the array.. well, unless it is big holes So the answer would be: first-fit.

Y.
TimSmith
TimSmith
Off the top of my head, I wonder if a variant of a scan line based hidden surface algorithm would work well.

Initialize your scan lines to N lines of M blocks long. (for an N by M working surface) To locate an empty spot large enough, you could just loop through each scan line trying to locate a large enough space. If one is found, then you can validate that the higher scan lines have space for the block. One you find an open space, the scan lines would be chopped up into segments.

In my mind, I see exactly how I would do it, but not totally sure how fast it would be.

Tim

Osc
Osc
quote:
Original post by Ysaneya

Nice idea, but it doesn''t seem to be working.. how could i allocate, say, a 16x1 block after i allocated the 4x3 block in your example ?



Okay...

How about using a multiple-pass alogirthm? The first pass could use some process similar to my first suggestion. If this failed to allocate the block, then you can fall back on a slower method.

Depending on the exact type of data involved, it may be best to just have two passes, using your original exhaustive method as the second pass. Alternatively, you could have a second pass that attempts to combine bits from two or more available blocks to fill the request.

Another idea for a second pass would be to keep a second collection of allocated blocks and use this to check if the allocation is impossible. If this pass proved that an allocation was possible, you could then fall back on your original method and know you''re not wasting all those cycles.
Osc
Osc
quote:
Original post by Ysaneya

Nice idea, but it doesn''t seem to be working.. how could i allocate, say, a 16x1 block after i allocated the 4x3 block in your example ?



Here''s a slight variation which may make things much better...

Again using the collection of available blocks , starting with 16x16 available and trying to allocate 4x3. This time, split the block into two overlapping blocks of size 12x16 and 16x13.

When searching the available blocks to allocate a new block, use the same method as before. When a match is found, record the position that the new block will be allocated, then work through the whole list of available blocks again and split any that contain part of the newly allocated block. Remember to create overlapping blocks when splitting into 2 new blocks. For each block created by this splitting, check if it is wholly contained within any existing ''available block'' and only add it to the list if this is not the case.

In your example of allocating the 16x1 block, you would allocate it from the 16x13 available block . So you remove the 16x13 and create a 16x12. This is not wholly contained in any other block, so is added to the collection. You then split the 12x16 block (because the block you have allocated overlap''s it) into a 12x3 and a 12x12. The 12x3 is not wholly contained in any other block, so is added to the collection. The 12x12 is wholly contained in another block, so is not added.

Okay, this isn''t perfect. In the worst case, you can traverse the whole collection many times. However, the final step ensures that the collection will not grow too large (all be it at quite a computational cost).

Does this make any sense?
Ysaneya
Ysaneya
TimSmith:
I fail to see how your scan-line algorithm is different than the brute-force "parsing each position to check if the block fits" idea i explained in the original post ? Could you provide an example ?

Osc:
Hmm the idea of overlapped available rectangles should be working (at least, if it''s not, it''s not obvious). It should be pretty fast too. I''ll try to implement it quickly tomorrow and i''ll post a comparison with the brute-force algorithm.

I''m also experimenting an algorithm which uses (horizontally only) some "pointers" to the next allocated/free block. It''s working very well. I''ll describe it later, once i''ve tested the speed.

Y.
TimSmith
TimSmith
Ok, I might be breaking a forum rule, but I threw this together real quick. The code isn't tested very well, but hopefully, you will get my idea.

                
// Blocks.cpp : Defines the entry point for the console application.

//


#include "stdafx.h"

#define max(a,b)   (((a) > (b)) ? (a) : (b))

#define min(a,b)   (((a) < (b)) ? (a) : (b))

//

// Structure used to store scan block information

//


struct ScanBlock
{
	int nStart;				// Index of first free entry in block

	int nEnd;				// Index of last free entry in block

	ScanBlock *pNext;		// Pointer to next block in scan line, 
							// NULL terminates

};

//

// Build a scan line table

//


ScanBlock **Build (int nWidth, int nHeight)
{
	ScanBlock **ppTable;

	//

	// Allocate the array

	//


	ppTable = new ScanBlock * [nHeight];

	//

	// Initialize each scan line to contain one block of the whole line

	//


	for (int i = 0; i < nHeight; i++)
	{
		ppTable <i> = new ScanBlock;
		ppTable <i> ->nStart = 0;
		ppTable <i> ->nEnd = nWidth - 1;
		ppTable <i> ->pNext = NULL;
	}
	return ppTable;
}

//

// Given a pointer to the current block and the previous block pointer,
// patch the given block so that indexes x through x + nBWidth - 1 are 

// no longer free

//


void PatchRow (ScanBlock **ppPrevPtr, ScanBlock *pCur, int x, int nBWidth)
{
	//

	// If all used, remove
	//


	if (pCur ->nStart == x && pCur ->nEnd == x + nBWidth - 1)
	{
		*ppPrevPtr = pCur ->pNext;
		delete pCur;
	}

	//

	// If start used, patch start pointer
	//


	else if (pCur ->nStart == x)
	{
		pCur ->nStart += nBWidth;
	}

	//

	// If end used, patch end pointer
	//


	else if (pCur ->nEnd == x + nBWidth - 1)
	{
		pCur ->nEnd -= nBWidth;
	}

	//

	// Otherwise, add a new entry
	//


	else
	{
		ScanBlock *pNew = new ScanBlock;
		pNew ->pNext = pCur ->pNext;
		pNew ->nStart = x + nBWidth;
		pNew ->nEnd = pCur ->nEnd;
		pCur ->nEnd = x - 1;
		pCur ->pNext = pNew;
	}
}

//

// Given a row, try to locate a scan block that is large enough to contain
// the block.  If found, check the higher rows
//


bool LocateFreeInRow (ScanBlock **ppTable, int nRow, int nStart, 
					  int nEnd, int nBWidth, int nBHeight, int *px)
{

	//

	// Initialize the loop.  Loop while we have blocks

	//


	ScanBlock **ppPrevPtr = &ppTable [nRow];
	ScanBlock *pCur = ppTable [nRow];
	while (pCur)
	{

		//

		// Compute the range of this block restricted by the range

		// supplied by the caller

		//


		int nStart2 = max (nStart, pCur ->nStart);
		int nEnd2 = min (nEnd, pCur ->nEnd);

		//

		// If this block is big enough

		//


		if (nBWidth + nStart2 < nEnd2 + 1)
		{

			//

			// If we still have lines to check in this block, then
			// 

			if (nBHeight > 1)
			{

				//

				// Call this routine recusively.  Restrict the range

				// to the range of this block.  If we have found a place,
				// then patch the row.  Exit from routine.

				//


				if (LocateFreeInRow (ppTable, nRow + 1,
					nStart2, nEnd2, nBWidth, nBHeight - 1, px))
				{
					PatchRow (ppPrevPtr, pCur, *px, nBWidth);
					return true;
				}
			}

			//

			// If all rows have been checked, the used the starting
			// position in this row as the starting position of the block.

			// Patch the current scan block.  Exit from routine

			//


			else
			{
				*px = nStart2;
				PatchRow (ppPrevPtr, pCur, *px, nBWidth);
				return true;
			}
		}

		//

		// Move on to next scan line

		//


		ppPrevPtr = &pCur ->pNext;
		pCur = pCur ->pNext;
	}
	return false;
}

//

// This routine loops through all the scan lines trying to

// locate a block

//


bool LocateFree (ScanBlock **ppTable, int nWidth, int nHeight,
				 int nBWidth, int nBHeight, int *px, int *py)
{
	for (int i = 0; i < nHeight - nBHeight; i++)
	{
		if (LocateFreeInRow (ppTable, i, 0, nWidth - 1,
			nBWidth, nBHeight, px))
		{
			*py = i;
			return true;
		}
	}
	return false;
}

//

// the main =)
//


int main(int argc, char* argv[])
{
	int nHeight = 16;
	int nWidth = 16;
	int x, y;

	ScanBlock **ppTable = Build (nWidth, nHeight);

	LocateFree (ppTable, nWidth, nHeight, 2, 4, &x, &y);
	LocateFree (ppTable, nWidth, nHeight, 3, 3, &x, &y);
	return 0;
}


To allocate a block, the min number of tests will be only the hight of the block being allocated. The max will never exceed number of scan blocks times the height of the block being allocated.

Hopefully the code is clear enough to understand.

Tim


Edited by - timsmith on August 17, 2000 4:29:04 PM

Edited by - TimSmith on August 17, 2000 4:30:04 PM

Edited by - TimSmith on August 17, 2000 4:30:31 PM
TimSmith
TimSmith
ACK, that made the message huge...

Tim
Ysaneya
Ysaneya
Hey!

I'm back from testing all these algorithms I've implemented them all and they're working (with a few minor modifications). I'm going to post the results. First, a little description of the 4 algorithms tested:

TimSmith's algorithm: uses scan blocks (linked list of free blocks for each row).
Ysaneya's algorithm: a variant of TimSmith's. Each cell of the map gots a pointer to the next allocated block(if the cell was free), or the next free block(if the cell was allocated).
Brute-force's algorithm: well.. parse each cell, and test the area..
Osc's algorithm: this one was interesting to test; uses overlapping areas, and a single linked list of free areas.

Notes:
1. The tests were done in Python, which is a high-level language. That's why the results (in milliseconds) are quite low. You can expect a *10 to *100 if implemented in C/C++.
2. Different size of maps have been tested. The 400x400 map used so much memory and time that sometimes i didn't test it.
3. Allocated blocks are in the form (X*Y). X is the number of requested blocks, and Y the avertage size of the block.
4. Miss is the % of failed requests. Happens when there is little free space remaining.
5. Holes is the % of the map which is still empty.

Ok, now the results:


Test1: a few big blocks (60*36), by increasing map size:
Map size:		6	10	20	40	80	140	256	400
Miss:		98	95	81	26	0	0	0	0
Holes:		0	2	11	8	65	88	96	98

TimSmith:		14	22	63	141	177	150	150	144
Ysaneya:		12	23	68	212	264	274	211	392
Brute:		39	115	663	2794	2636	2454	1368	1419
Osc:		8	17	82	234	436	461	543	508


Test2: a lot of big blocks(600*36), by increasing map size:
Map size:		6	10	20	40	80	140	256	400
Miss:		99	99	98	92	71	12	0	0
Holes:		0	2	4	3	2	2	66	86

TimSmith:		81	165	400	972	3440	6223	7867	10661
Ysaneya:		77	236	805	2966	10059	20507	20484	20854
Brute:		374	1412	9021	44564	-	-	-	-
Osc:		26	88	215	1097	5133	19265	30528	31453


Test3: a few little blocks (60*3), by increasing map size:
Map size:		6	10	20	40	80	140	256	400
Miss:		83	54	0	0	0	0	0	0
Holes:		0	0	45	86	96	98	99	99

TimSmith:		20	30	43	40	42	47	50	58
Ysaneya:		27	62	90	84	72	68	69	231
Brute:		95	244	347	345	247	236	236	257
Osc:		14	49	200	196	198	197	196	250


Test4: a lot of little blocks (600*3), by increasing map size:
Map size:		6	10	20	40	80	140	256	-
Miss:		98	95	81	27	0	0	0	-
Holes:		0	0	0	0	65	88	96	-

TimSmith:		127	197	375	676	597	665	809	-
Ysaneya:		37	639	2370	6800	7398	7401	6917	-
Brute:		1021	3079	12390	35598	39782	38182	36871	-
Osc:		32	70	493	6068	12450	12072	12034	-


Test5: we're trying to keep miss>0 and holes>0, map size:40x40	
Miss:		10	8	7	28
Holes:		3	3	0	0
Blocks:		132*13	240*7	690*2	900*2

TimSmith:		337	405	674	911
Ysaneya:		600	1970	8118	12619
Brute:		5389	10664	34872	57876
Osc:		935	2482	8947	9203


Test6: we got a huge map (140x140), little blocks. See how speed veries with the
number of blocks (size 2):
Miss:		0	0	0	0	0	0
Holes:		99	98	96	93	87	75
Blocks:		60	120	240	480	960	1920

TimSmith:		37	90	183	374	859	2197
Ysaneya:		67	215	911	3874	15852	64589
Brute:		211	913	3730	16376	67397	-
Osc:		216	686	2213	7394	26461	94056


Comments: well.. the results are sometimes quite hard to interpret, and sometimes..surprising. But they seem to be exact. A reference test was used each time. When results seemed strange (like when the speed increases, then decreases and increases again later), the tests have been done more than once to be sure it wasn't a "benchmark" problem.

The brute-force algorithm is always slower (no surprise there). My algorithm is also slower than TimSmith's, but varies the same way (it's just implemented slower).
TimSmith's algorithm is almost always the fastest with big maps and a high number of blocks.
Osc's algorithm is better on little maps.

Though the results of TimSmith's algorithm are not.. bad.. i'm wondering if there wouldn't be even better algorithms.. any ideas ?

Y.

Ps.: a little addition.. it's not shown in the results, but it looks like Osc's algorithm tends to generate maps with higher miss/more holes than the others. All the others got the same results..

Pps.: if people are interested i can post a link to the Python code of the 4 algorithms ? I do not post it now, it's too long.


Edited by - Ysaneya on August 18, 2000 11:10:37 AM

Edited by - Ysaneya on August 18, 2000 11:12:09 AM

Edited by - Ysaneya on August 18, 2000 11:16:16 AM
Osc
Osc
quote:
Original post by Ysaneya

Pps.: if people are interested i can post a link to the Python code of the 4 algorithms ? I do not post it now, it's too long.



Look's like you've been busy. I'm very impressed by the performance of TimSmith s algorithm, and also slightly dissapointed by how quickly the performance of my algorithm degrades

I'd like to take a look at your code. I don't know any Python, but people say it's fairly intuitive so it won't hurt to have a go. Can you get your code posted on another web site and link to it from here?


Edited by - Osc on August 21, 2000 4:35:47 AM
Ysaneya
Ysaneya
> Look's like you've been busy. I'm very impressed by the performance of TimSmith s algorithm, and also slightly dissapointed by how quickly the performance of my algorithm degrades

Yes, quite busy. That's a shame i didn't have more algorithms to test
As for your algorithm, Test6 shows that your algorithm is very dependant of the number of blocks allocated. It is faster with very little blocks, and far slower (ratio of 1:42 with TimSmith's). Yet, it is faster than the "brute-force" method.

> I'd like to take a look at your code. I don't know any Python, but people say it's fairly intuitive so it won't hurt to have a go. Can you get your code posted on another web site and link to it from here?

You won't have too much troubles to understand the code, even if you haven't seen the language before. Unfortunately i don't have it right now, so you'll have to wait tonight so i can upload it on a site. It is not very good quality code too, i'm afraid. I spent time to make it work and test, not to make it nice

Y.

Ps.: i'm also working on another method. It is quite hard to implement, so if you have ideas..

Here is how i see it: do you know what a quadtree is ? Maybe we could use a similar approach. We have a tree where the root node is the whole array (like 128x128). Then, each node is recursively divided in 4 sons of half size. A node also has a type:

0=node is completely empty (no cells allocated)
1=mixed (some cells are allocated, some aren't)
2=filled (all the cells are allocated)

When a node is of type 0 or 2, we do not subdivide it. Initially, the array, which is empty, is a single node of type 0.



Ex.:
.***
****
..*.
...*


<=> (sons are going from top-left to bottom-right)



1
--> 1
-------> 0
-------> 2
-------> 2
-------> 2
--> 2
--> 0
--> 1
-------> 2
-------> 0
-------> 0
-------> 2


When we allocate a rectangle of size N*M at position (x,y), we update the tree.

I succeeded to implement this update. I thought it was the hardest part, but finally.. i do not see how, with a such updated tree structure, i can do the search of a free rectangle itself. Any ideas ?


Edited by - Ysaneya on August 22, 2000 4:46:52 AM
Osc
Osc
quote:
Original post by Ysaneya

I succeeded to implement this update. I thought it was the hardest part, but finally.. i do not see how, with a such updated tree structure, i can do the search of a free rectangle itself. Any ideas ?



I see how your quadtree works, but finding a free rectangle is going to be a problem. I have tried a few methods, but they all devolve into modifiactions of the brute-force method. Sorry, can''t help on this one.

On a brighter note, here''s another algorithm which could be faster. You said memory wasn''t a problem, but speed is what you''re after, so here''s goes...

We start by dividing the grid into a 2D array of cells (there will be WIDTH * HEIGHT cells). For each cell, we have an array of bool for each line length that can be started at that cell and allocated horizontally. Sound complicated?

Say we have a 10x10 grid and want to allocate a 4x3 block. We check cell[0][0] to see if it can hold a line of length 4:

if (line[0][0][3]) {....}

Note that I''m using index 3 for length 4, etc.

If we get a true, we then check:

if (line[0][1][3] AND line[0][2][3]) {...}

If we get true again, we have a free block. Otherwise, we move onto the next cell...

if (line[1][0][3]) {...}

and so on.

Note that we need only check cells (0...WIDTH - block_width) and (0...HEIGHT - block_height).

When we allocate a block, we set a whole load of values to false. In the above example, we would set line[0..3][0..2][0..9] to false. Actually, some array entries are not needed and can be ignored - there''s no need to check if a cell half way across the grid can hold a line as wide as the whole grid

It''s actually a lot like TimSmith s algorithm, but swaps size for ease of access in terms of data storage. And if you try to visualise the data structure, you end up with a traingular 3D thing - looks a bit like a door wedge.

I''ll put together some code for this and see how it works out (sorry, can''t use Python - it''ll have to be C++).
Ysaneya
Ysaneya
Hmm yes i see how it could be working.. but well, i don''t know, it also makes the allocation/area updates slower too. Whereas in TimSmith''s algorithm you just have to link a node, with yours you''d have to update the 3rd dimension of the array.
I''ll test it in Python, but i guess it won''t be faster than TimSmith''s, for a huge memory difference. We''ll see...

Y.
Ysaneya
Ysaneya
Many news.. first i've uploaded the Python source for the first 4 algorithms. Here is the link.

I also tested your last idea (3d array of booleans), and as i thought, it's.. slow. I haven't made accurate tests, but compared to TimSmith's algo, it seems it can easily be 10 times slower. Looks like this algo is the slowest of the new 4 (excepting the brute-force algo).

Finally, i'm working on my idea of a quadtree. There's still a bug, but i've found a method to search quickly where a block can fit. I haven't tested it yet (fix the bug first!), but i don't think it will beat TimSmith's algo. Allocation needs to update some big parts of the tree. Anyway i'll tell you the results later, once everything is working..

Y.


Edited by - Ysaneya on August 23, 2000 1:44:57 PM
Osc
Osc
Thanks for posting your code. I''d already written my own versions in C++, and come up with pretty much the same things. However, it looks like Python and C++ are strong in different areas....

I found that my original algorithm beat TimSmith''s in lots of cases. TimSmith''s came out on top for grids smaller than 100x100 where the miss rate was 0%. Larger grids with 0% miss, and any grid with >0% miss, did better on my algorithm. Here''s some stats:

NB:
BruteForce is just what is says
Osc(1) is the overlapping block algorithm
Osc(2) is the 3D array algorithm - not too good
TimSmith is the scan line algorithm
timings are in milliseconds



100x100 grid, 250 blocks of up to 20x20
                   time   miss%  holes%
BruteForce          302   47.20    4.22
Osc(1)                7   48.40    3.08
Osc(2)              466   47.20    4.22
TimSmith             14   47.60    3.96

200x200 grid, 1000 blocks of up to 20x20
                   time   miss%  holes%
BruteForce         4725   53.70    1.65
Osc(1)               42   53.20    0.92
Osc(2)             8295   53.70    1.65
TimSmith            192   53.70    1.54

300x300 grid, 2000 blocks of up to 20x20
                   time   miss%  holes%
BruteForce        21465   49.40    1.42
Osc(1)              151   51.40    0.71
Osc(2)            62166   49.40    1.42
TimSmith            714   50.30    1.37


As you can see, Osc(2) was a disaster. I did a whole load of tests, and it always came out worse than BruteForce. TimSmith did very well, and also got a lower holes% in most tests (search uses a different ordering that the first two). Osc(1) did the best in nearly all tests (except small grid''s with 0% miss) and also had the best holes% in each test (uses a Best Fit approach, while others all use First Fit).

Both TimSmith and Osc(1) were dramatically better than the brute force method, so I''d recommend using one of these two, depending on your grid size and likely miss%.

How''s the QuadTree method coming along?
Ysaneya
Ysaneya
Interesting results.. but i think your algorithm (1) is more dependant on the number of blocks, hence the average size of the blocks. If you use 20x20 blocks, i'm not really surprised of the results. Try to increase the number of blocks and decrease their size (to an average of like 3, ie lots of little 3x1, 2x2,1x1, 1x3,etc.. blocks) and see what the results are.
Unfortunately, for my use, i will need a map of around 128x128 and blocks of *any* size.. 1x1 as well as 20x20. I don't think their number will be higher than 1000.

I finished my quadtree method. Finally, it is working The algorithm has come more simple than what i thought, but unfortunately it's not very fast. As expected, the tree updates consume a lot of CPU. Again, i haven't tested it accurately, but it looks like it's close to your second algo. So one of the worst The only interesting thing is that when the map starts to be completely filled, there is a single node into the quadtree and the allocation test, which fails, returns immediately. In that case it's working at light speed

By the way, i've found an interesting thing in Quake's source. It does exactly what we want, but i didn't fully understand the algo. It uses a 1-dimension table and simple loops. I guess it's *extremely* fast, probably 10x TimSmith's algo, but to achieve a such speed i think it has some important drawbacks (i think the ratio of holes is very high). I'll test it later..

Y.


Edited by - Ysaneya on August 24, 2000 5:02:21 PM
Osc
Osc
quote:
Original post by Ysaneya

Unfortunately, for my use, i will need a map of around 128x128 and blocks of *any* size.. 1x1 as well as 20x20. I don''t think their number will be higher than 1000.



Hiya,

Sorry I''ve not been around for a while. I ran the tests on these parameters, and found that Osc(1) and TimSmith gave identical performance - both much better than the brute force approach. I''m sure that there are some simple optimisations that would make them even quicker (tracking the largest width*height in Osc(1), or the longest block in each row for TimSmith, for example). I''m also using dynamic memory allocation in these two algo''s, so they would probably benefit from using a static pool of objects. Both clocked in 14ms to allocate 1000 blocks in the 128x128 grid, while the brute force method took 316ms.

Don''t know how the Quake source licence works... can you post the relevant code here? Either way, let me know how you get on.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.