Back to General and Gameplay Programming

Filling collision 2d array

General and Gameplay Programming Programming

Started by Ludi83 December 31, 2004 05:50 AM

11 comments, last by Ludi83 19 years, 4 months ago

Ludi83

300

Author

December 31, 2004 05: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

582

December 31, 2004 06: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

864

December 31, 2004 07: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

582

December 31, 2004 07:30 AM

Yea mine has a few other flaws.

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

Would also mess it up.

Ludi83

300

Author

December 31, 2004 07: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

156

December 31, 2004 08: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

268

December 31, 2004 08: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

582

December 31, 2004 08: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

268

December 31, 2004 08: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

156

December 31, 2004 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) &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 :))

Filling collision 2d array

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Filling collision 2d array

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines