Filling collision 2d array

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

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

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 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 on other sites
Yea mine has a few other flaws.

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

Would also mess it up.

Share on other sites
Quote:
 Original post by JingoYea 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 on other sites
Quote:
 Original post by SharlinPerhaps 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 on other sites
Quote:
Original post by Ludi83
Quote:
 Original post by JingoYea 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 on other sites
The main downside to it is that it requires starting from inside the walls, how do you find a position inside the wall?

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

1. 1
2. 2
Rutin
24
3. 3
4. 4
JoeJ
18
5. 5

• 14
• 28
• 11
• 11
• 9
• Forum Statistics

• Total Topics
631772
• Total Posts
3002260
×