Sign in to follow this  

Filling collision 2d array

This topic is 4735 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, this is the view of my 2d collision array:
****************************************************************
*###########################*********###########################
*#*************************#*********#*************************#
*#*************************##########**************************#
*#*************************************************************#
*#*************************************************************#
*#*************************************************************#
*#*****############********************************************#
*#*****#**********#********###########*************************#
*#*****#*#########*********#*********#*************************#
*#*****#*#*****************#*********#*************************#
*#*****#*#*****************#*********#*************************#
*#*****#*#*****************#*********#*************************#
*#*****#*#*****************#*********#*************************#
*#*****#*#*****************#*********#*************************#
*#*****#*#*****************#*********#*************************#
*#*****#*#*****************#*********#*************************#
*#*****#*#********#########**********#*************************#
*#*****#*#********#******************#*************************#
*#*****#*#********#******************#*************************#
*#*****#*#********#******************#*************************#
*#*****#*#********#******************#*************************#
*#*****#*#********#******************#*************************#
*######**#########*******************##########################*

The # are the borders, and i want all the * within this border to be filled with # too. Has anyone a clue how to solve this. It like filling a polygon in paint, or so. I tried something like that, but that didn't work corretly everywhere:
	for(i=2; i < 24; i++) {
		prevRestr = 0;
		for(k=0; k < 63; k++) {
			if(moveable[i][k] == true) {
				if(moveable[i][k+1] == true) {
					prevRestr = 0;
					continue;
				}
				prevRestr = (prevRestr + 1) % 2;
			}

			if(prevRestr == 1) {
				moveable[i][k] = true;
				//msg("");
			}
		}
	}

thanks for you help

Share this post


Link to post
Share on other sites
Not tested this, but something like:



bool isinsidepolygon = false;

for(unsigned int row = 0; row < rowsize; ++row)
{
for(unsigned int column = 0; column < columnsize; ++ column)
{
if(isinsidepolygon && array[row][column] != '#')
array[row][column] = '#';
else if(isinsidepolygon && array[row][column] == '#')
isinsidepolygon = false;
else if(!isinsidepolygon && array[row][column] == '#')
isinsidepolygon = true;
}

isinsidepolygon = false;

}





The general idea is to loop through the array of data looking for a #, if it finds one then it sets the bool isinsidepolygon to true to signal that the next block in the array is either inside the polygon or is the ending edge of the polygon. If the next element in the array is not a # then it sets it to be a # to fill in the block, it does this until it encounters another #, which signals the end of the inside of the polygon. It then resets the bool variable to be false when it advances to the next row, just incase the row didnt end in a #.

Share this post


Link to post
Share on other sites
Jingo: There are some special cases where your algorithm doesn't quite work correctly and may limit map designs. Consider:


****#****
***#*#***
***#*#***
****#****

Or

**#####**
**#***#**
**#*#*#**
**#***#**
**#####**


Perhaps the most elegant (though probably not the most efficient) way is to use recursion:


void fill(unsigned int x, unsigned int y)
{
if(x < x_size && y < y_size && map[x][y] == '*')
{
map[x][y] = '#';
fill(x-1,y); fill(x+1,y); fill(x,y-1); fill(x,y+1);
}
}




Call it for some coordinate (x,y) that you know lies inside the walls.

Share this post


Link to post
Share on other sites
Quote:
Original post by Jingo
Yea mine has a few other flaws.

#######
##****#
#######

Would also mess it up.


Yes, that was the problem with mine too.

@Sharlin

I will try it later, thanks

Share this post


Link to post
Share on other sites
Quote:
Original post by Sharlin
Perhaps the most elegant (though probably not the most efficient) way is to use recursion:


I actually believe that it's the most efficient way to fill up a space like that, especially considering the fact that you can optimise it greatly using in-line assembly. The code is so compact and elegant that it will be pipelined nicely and you could use the (very quick) stack to store the x and y values. I don't know whether the C compiler already does this or not, but my guess is that a nicely written in-line assembly code will make this method more than twice as fast! I'm not sure which compiler you are using, but I'll post an example with GCC in-line assembly later.

Bas

Share this post


Link to post
Share on other sites
Quote:
Original post by Ludi83
Quote:
Original post by Jingo
Yea mine has a few other flaws.

#######
##****#
#######

Would also mess it up.


Yes, that was the problem with mine too.

@Sharlin

I will try it later, thanks


Simply because your algo works only with non convex area

ex:


#### ####
# # # #
# ####### #
# #
#############



I concord with Sharlin


// the same code
void fill(unsigned int x, unsigned int y){
if(x < x_size && y < y_size && map[x][y] == '*'){
map[x][y] = '#';
fill(x-1,y); fill(x+1,y); fill(x,y-1); fill(x,y+1);
}
}





Obviously you need a 'seed' (starting point) for every area you want to fill.
Nice, simple and elegant...

Share this post


Link to post
Share on other sites
Jingo:
"The main downside to it is that it requires starting from inside the walls, how do you find a position inside the wall?"

Obviously you have to specify it! There is no a methematic solution because when you create a convex region you create also a non convex region in the same plane.
Where is 'inside'? Where 'outside' ?

Share this post


Link to post
Share on other sites

#include <iostream>
#include <stdlib.h>

#define MAP_WIDTH 20
#define MAP_HEIGHT 20

//ASM needs strings
#define ASM_MAP_WIDTH "$20"
#define ASM_MAP_HEIGHT "$20"

void fill(int x, int y);

//char * map;
char map[MAP_WIDTH * MAP_HEIGHT];

int main() {

//X 0123456789.... Y
char * map2= "####################" //0
"#******************#" //1
"#******************#" //2
"#******************#" //3
"#*******#######****#" //4
"#*******#*****#****#" //5
"#*******#*#####****#" //6
"#*******#*#********#" //..
"#*******#*#####****#" //..
"#*******#******#***#"
"#*******#*###*#****#"
"#*******#*#*#**#***#"
"#***#####*#**##****#"
"#***#*****#********#"
"#***#######********#"
"#******************#"
"#******************#"
"#******************#"
"#******************#"
"####################";

memcpy (map,map2,strlen(map2));

fill(9,9);

for (int i = 0; i < MAP_HEIGHT; i++) {
char * line = (char *) malloc(MAP_WIDTH + 2);
line[MAP_WIDTH] = '\n';
line[MAP_WIDTH + 1] = '\0';
memcpy(line, map + i * MAP_WIDTH, MAP_WIDTH);
printf(line);
}

return 0;
}

int asm_start; //you can only use global variables in in-line assembly...

//Pre: the area is limited (else expect some nast crap to happen with stack pointers etc.)
void fill(int x, int y) {
//Basic idea: start at point (x,y) and fill up the map from there

//Calculate starting position in map-array
asm_start = x + y * MAP_WIDTH + (unsigned int) &map;
asm ("movl _asm_start, %eax");
asm ("pushl %eax"); //Push value onto stack
asm ("movl $1, %edx"); //Number of to-be-checked positions in the stack (stack counter)

asm ("movb $35, %cl"); //'#' = ASCII 35
//Starting point inserted into the stack, now start the recursive function:
asm ("fillNext:");
asm ("popl %eax"); //Get the position out of the stack
asm ("movb (%eax), %bl"); //Get the value of the position ('#'=ASCII 35 or '*'=ASCII 42
asm ("cmpb %cl, %bl"); //Compare map[position] to '#'
asm ("je next"); //If that position is already '#', then don't do anything
//Set map to '#'
asm ("movb %cl, (%eax)");

//Check adjacent fields
asm ("decl %eax"); //1:fill(x-1,y)
asm ("pushl %eax");

asm ("addl $2, %eax"); //2:fill(x+2,y)
asm ("pushl %eax");

asm ("decl %eax");
asm ("subl " ASM_MAP_WIDTH ", %eax");
asm ("pushl %eax"); //3:fill(x,y-1)

asm ("addl " ASM_MAP_WIDTH ", %eax");
asm ("addl " ASM_MAP_WIDTH ", %eax");
asm ("pushl %eax"); //4:fill(x,y+1)

asm ("addl $4, %edx");
asm ("next:");
asm ("decl %edx"); //Decrement the stack counter
asm ("cmpl $0, %edx");
asm ("jne fillNext"); //If there are more map positions to be done, then go on

//At this point, everything has been filled up
}



Note that, because of using the stack, the area is restricted to some size. Not sure what that size is though... I've tried a space up to 20000 and it still didn't give problems (probably because it only has to hold values for the edges :))

Share this post


Link to post
Share on other sites
Just to give you an example of the power of ASM:
Filling up the following map for 30'000 times:

"****************************************************************"
"*###########################*********###########################"
"*#*************************#*********#*************************#"
"*#*************************##########**************************#"
"*#*************************************************************#"
"*#*************************************************************#"
"*#*************************************************************#"
"*#*****############********************************************#"
"*#*****#**********#********###########*************************#"
"*#*****#*#########*********#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#*****************#*********#*************************#"
"*#*****#*#********#########**********#*************************#"
"*#*****#*#********#******************#*************************#"
"*#*****#*#********#******************#*************************#"
"*#*****#*#********#******************#*************************#"
"*#*****#*#********#******************#*************************#"
"*#*****#*#********#******************#*************************#"
"*######**#########*******************##########################*";



Takes almost fifteen seconds with the 'normal' method:

//Pre: the area is limited (else expect some nast crap to happen with stack pointers etc.)
void fill(int x, int y) {
//Basic idea: start at point (x,y) and fill up the map from there

if (map[x+y*MAP_WIDTH]!='#') {
map[x+y*MAP_WIDTH] = '#';
fill(x-1,y);
fill(x+1,y);
fill(x,y-1);
fill(x,y+1);
}
}


And only 5 seconds with the in-line assembly code I posted :D

Bas

Share this post


Link to post
Share on other sites
@Sharlin and @basananas

I can't hold back my feelings anymore. I love you :D
Great, thanks a lot.


And I wish you both and all the others here a happy new year.

Share this post


Link to post
Share on other sites

This topic is 4735 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this