So im working with a new physics library, and i want it to run as fast as possible. My game contains a 1D array for the map (but essentially a 2D tile array), and i want to find groups of objects and create rectangles out of them.

Example:


if each tile is using a number, then the map would look like this in the text file:


1111111111
1________1
1_____33_1
1_22__33_1
1_22_____1
1111111111


then the map would be parsed, where each letter represents it's groups id:

1111111111
2________3
2_____44_3
2_55__44_3
2_55_____3
6666666666


But i cant quite seem to figure out the right algorithm.... I have tried numerous ways, but nothing works... What are your ideas?

Just brainstorming (and hopefully I'm understanding your question here )

Are you looking for all solutions, or are there criteria for ruling out multiple ones? If I'm understanding correctly, there are many ways to group your example, such as this alternative:

2222222222
1________3
1_____44_3
1_55__44_3
1_55_____3
7755666663
[/quote]

My intuition tells me that an exact algorithm for finding all solutions may have something to do with the "packing problem" - but I could be wrong, haven't messed with packing algorithms much.

A naive brute force approach could be: find the first filled (valid) cell, then start a rectangle there. Expand the rectangle either right or down or both (weeding out invalid rectangles due to containing an invalid cell), and expanding as far as possible. Add this rectangle to the set of rects. Find the next valid cell that is not contained in the set of rects, and start a new rectangle, repeating the above. Stop when there are no more valid cells not contained in the set of rects.

Example, here is the start of the first rectangle ("S"), it can be expanded either horizontally or vertically successfully ("*"), bot not diagonally because that would include an invalid or empty cell:

S*11111111
*________1
1_____33_1
[/quote]

By whatever convention, we choose to favor horizontal, and created our first recangle thus:

S*********
1________1
1_____33_1
[/quote]

The next valid cell not in the already created rectangle ("x") is found and marked as a new starting point ("S"). Here the horizontal and diagonal expansions are ruled out, so we expand vertically:

xxxxxxxxxx
S_______ 1
*_____33_1
*_22__33_1
*_22_____1
*111111111
[/quote]

Move along to where we've created three rectangles (marked as "x"), and finding the starting point ("S") here.

xxxxxxxxxx
x________x
x_____S3_x
x_22__33_x
x_22_____x
x111111111
[/quote]

In this case, diagonal expansion is valid:

xxxxxxxxxx
x________x
x_____S*_x
x_22__**_x
x_22_____x
x111111111
[/quote]

Depending on which expansion direction you favor (left, down, diagonal), this could lead to different solutions.

Yup. I would prefer horizontal, because the maps are usually longer then their height. Im also doing the steps you listed, but unfortuantly i think im just messing up on 1 part of the algorithm. I have 3 variations of the algorithm that, maybe someone could point out the mistake...


this->Parsed_Map.clear();
char* Temp_Map = new char[this->W_Size_X*this->W_Size_Y];
for(u_int a=0;a<this->W_Size_X*this->W_Size_Y;a++)
Temp_Map[a]=this->Front[a];
for(u_int y=0;y<this->W_Size_Y;y++)
for(u_int x=0;x<this->W_Size_X;x++)
{
if(Temp_Map[y*this->W_Size_X + x])//is collision
{
u_int Width=this->W_Size_X-1,Height=this->W_Size_Y-1;
for(u_int y1=0;y1+y<this->W_Size_Y && Temp_Map[(y1+y)*this->W_Size_X + x];y1++)
{
u_int x1=1;
while(x1<Width && Temp_Map[(y1+y)*this->W_Size_X + x + x1])
x1++;
Width=x1;
}
for(u_int x1=0;x1<Width && Temp_Map[y*this->W_Size_X + x + x1];x1++)
{
u_int y1=1;
while(y1<Height && Temp_Map[(y1+y)*this->W_Size_X + x + x1])
x1++;
Height=y1;
}

/*u_int Width=this->W_Size_X-1,Height=this->W_Size_Y-1;
for(u_int y1=0;y1+y<this->W_Size_Y && Temp_Map[(y1+y)*this->W_Size_X + x]!=0;y1++)//check for smallest width
{
u_int x1=1;
while(x1+x<this->W_Size_X && Temp_Map[(y1+y)*this->W_Size_X + x + x1]!=0)
x1++;
if(x1<Width)
Width=x1;
}
for(u_int x1=0;x1<Width && Temp_Map[y*this->W_Size_X + x + x1]!=0;x1++)//check for smallest height
{
u_int y1=1;
while(y1+y<this->W_Size_Y && Temp_Map[(y1+y)*this->W_Size_X + x + x1]!=0)
y1++;
if(y1<Height)
Height=y1;
}
/*for(u_int x1=0;x1+x<this->W_Size_X && Temp_Map[y*this->W_Size_X + x + x1];x1++)
{
u_int y1=1;
while(y1+y<this->W_Size_Y)// && Temp_Map[(y+y1)*this->W_Size_X + x];y1++)
{
if(Temp_Map[(y+y1)*this->W_Size_X + x + x1])//this is a collision
y1++;
else
{
if(y1<Height || Height==1)//next is air
Height=y1;
break;
}
}
//if(Height==this->W_Size_Y+10)Height=1;
Width++;
}
if(Width==0)
Width=1;
if(Height==0)
Height=1;*/
RECT nRect;
nRect.left=x;
nRect.top=y;
nRect.right=Width+x;
nRect.bottom=Height+y;
this->Parsed_Map.push_back(nRect);
}
}