🔒 Locked

Filling collision 2d array

Started by Ludi83 Dec 31, 2004 at 5:50 AM 11 replies 1.5k views

Original Post

Dec 31, 2004 at 5:50 AM

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[k] == true) {
				if(moveable[k+1] == true) {
					prevRestr = 0;
					continue;
				}
				prevRestr = (prevRestr + 1) % 2;
			}

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

thanks for you help

Jingo

Dec 31, 2004 at 6:05 AM

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

Sharlin

Dec 31, 2004 at 7:03 AM

Jingo: There are some special cases where your algorithm doesn't quite work correctly and may limit map designs. Consider:

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

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

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.

Jingo

Dec 31, 2004 at 7:30 AM

Yea mine has a few other flaws.

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

Would also mess it up.

Ludi83

Author

Ludi83

Dec 31, 2004 at 7:59 AM

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

basananas

Dec 31, 2004 at 8:20 AM

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

blizzard999

Dec 31, 2004 at 8:38 AM

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...

Jingo

Dec 31, 2004 at 8:38 AM

The main downside to it is that it requires starting from inside the walls, how do you find a position inside the wall?

blizzard999

Dec 31, 2004 at 8:47 AM

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' ?

basananas

Dec 31, 2004 at 10:06 AM

#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....          Ychar * 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) ↦  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 :))

basananas

Dec 31, 2004 at 11:08 AM

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

blizzard999

Dec 31, 2004 at 11:21 AM

That is for a single fill

0.5 ms with the normal method
0.2 ms with asm

:)

Ludi83

Author

Ludi83

Dec 31, 2004 at 11:47 AM

@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.

Topic Locked

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