Figuring out if a point on a grid is surrounded by points of a certain kind

Question

In my game, the player can activate objects (tiles here) in a grid. In the example picture, imagine all the red tiles have been "activated". when the player touches any red tile (for instance the tile with the purple arrow), I'd like to send a message to all confluent adjacent red tiles and also any tile that is bound by red tiles (the green tiles).

I wouldn't mind being able to send messages to tiles also bound by EITHER red tiles OR the wall of the grid (if only 1 wall, not corners or the whole empty space would be included). I show this as blue tiles here. I also wouldn't mind trying to get this to work when the red tiles are diaganal, rather than adjacent (the yellow shape), but I'm not sure either of those would make it into the gameplay.

This is a simplification but I just need some advice on where to go here. I just need to know the type of math I need to do.

Not sure if it matters for help, but the game is in Objective-C and Cocos2D and each tile is Subclassed object and has a property to tell which state it is and is in an array of arrays.

This post doesn't seem to be related: surrounding objects algorithm

enter image description here

actually, this might be what i need, gonna think about it: http://www.techuser.net/minecascade.html — kidnim, Aug 10 '13 at 21:02
you're essentially looking for (a variation of) a contour tracing algorithm, like Moore's: http://www.imageprocessingplace.com/downloads_V3/root_downloads/tutorials/contour_tracing_Abeer_George_Ghuneim/moore.html Trace the contour, then you know the tiles that are inside and can check their status. — CodeSmile, Aug 10 '13 at 21:03
Steffen - once again to the rescue! i sort of just started a similar process that i guess is a mix between the minesweeper cascade algorithim and the moore contour thing. i basically take the Starting Tile and build an array of tiles that are tiles connected to it. then i go through each tile in the whole map and check if it is surrounded on all sides by marked tiles. — kidnim, Aug 10 '13 at 21:20
oh wait, this'll miss them in clusters. well, i think i'll still figure it out — kidnim, Aug 10 '13 at 21:23
This sounds to me like a [flood fill](http://en.wikipedia.org/wiki/Flood_fill), if I'm reading it right. Given one red tile, you want a list of all the red tiles that can be reached by passing only through other red tiles, right? — jscs, Aug 10 '13 at 23:29
Using Steffen's/LearnCocos2d's suggestion, i've been able to trace the contour and come up with an array representing tiles within the shape. still dont have an efficient way to reliably check if a tile is "inside" the shape. maybe gonna build a data array with "on" and "off" markers — kidnim, Aug 11 '13 at 19:11

kidnim · Answer 1 · 2013-08-11T21:52:58.510

so, this isn't perfect but it works. i'm not going into too much detail, but i used learncocos2d / steffen's method and then my own version of a border detector to try to detect holes. it only does this in horizontal scans. obviously, the code includes calls to an array of boxes which i'm not changing for this but as is stated in the question, the arrayofboxes is an array of arrasy where each entry is a row of tiles called Box:

i'm posting this in case its helpful to anyone and i'm not 100% certain there arent errors yet

-(NSMutableDictionary*) returnMooreNeighborDictFromBox:(Box*)enteredBox {

NSMutableDictionary * mooreDictToReturn = [NSMutableDictionary dictionaryWithCapacity:8];

//define moore-neighbor as the 8 boxes around any given box. p1 is upper left

/*
 P1 P2 P3
 P8 XX P4
 P7 P6 P5
 */

int depth = enteredBox.trueDepth;
int depthRelativeXCoord = enteredBox.gridAbsoluteXCoord/((pow(2,depth)));
int depthRelativeYCoord = enteredBox.gridAbsoluteYCoord/((pow(2,depth)));
int xPosInArray = depthRelativeXCoord;
int yPosInArray = depthRelativeYCoord;

int maxCoord = (self.numberOfBoxesOfAcross/(pow(2,depth))-1);

NSMutableArray *boxArray = [arrayOfBoxArrays objectAtIndex:depth];

NSMutableArray *boxRowOfArray = [boxArray objectAtIndex:yPosInArray];
    if ((xPosInArray-1)>=0){
        Box * p8Box = [boxRowOfArray objectAtIndex:xPosInArray-1];
        [mooreDictToReturn setObject:p8Box forKey:@"p8"];
        }
    else {
        [mooreDictToReturn setObject:[NSNull new] forKey:@"p8"];
        }
    if ((xPosInArray+1)<=maxCoord){
        Box * p4Box = [boxRowOfArray objectAtIndex:xPosInArray+1];
        [mooreDictToReturn setObject:p4Box forKey:@"p4"];
        }
    else {
        [mooreDictToReturn setObject:[NSNull new] forKey:@"p4"];
        }

if ((yPosInArray-1)>=0){
    NSMutableArray *boxRowBelowArray = [boxArray objectAtIndex:yPosInArray-1];
    Box * p6Box = [boxRowBelowArray objectAtIndex:xPosInArray];
    [mooreDictToReturn setObject:p6Box forKey:@"p6"];
    if ((xPosInArray-1)>=0){
        Box * p7Box = [boxRowBelowArray objectAtIndex:xPosInArray-1];
        [mooreDictToReturn setObject:p7Box forKey:@"p7"];
        }
    else {
        [mooreDictToReturn setObject:[NSNull new] forKey:@"p7"];
        }
    if ((xPosInArray+1)<=maxCoord){
        Box * p5Box = [boxRowBelowArray objectAtIndex:xPosInArray+1];
        [mooreDictToReturn setObject:p5Box forKey:@"p5"];
        }
    else {
        [mooreDictToReturn setObject:[NSNull new] forKey:@"p5"];
        }
    }
else {
    [mooreDictToReturn setObject:[NSNull new] forKey:@"p5"];
    [mooreDictToReturn setObject:[NSNull new] forKey:@"p6"];
    [mooreDictToReturn setObject:[NSNull new] forKey:@"p7"];        
    }


if ((yPosInArray+1)<=maxCoord){
    NSMutableArray *boxRowAboveArray = [boxArray objectAtIndex:yPosInArray+1];
    Box * p2Box = [boxRowAboveArray objectAtIndex:xPosInArray];
    [mooreDictToReturn setObject:p2Box forKey:@"p2"];
    if ((xPosInArray-1)>=0){
        Box * p1Box = [boxRowAboveArray objectAtIndex:xPosInArray-1];
        [mooreDictToReturn setObject:p1Box forKey:@"p1"];
        }
    else {
        [mooreDictToReturn setObject:[NSNull new] forKey:@"p1"];
        }
    if ((xPosInArray+1)<=maxCoord){
        Box * p3Box = [boxRowAboveArray objectAtIndex:xPosInArray+1];
        [mooreDictToReturn setObject:p3Box forKey:@"p3"];
        }
    else {
        [mooreDictToReturn setObject:[NSNull new] forKey:@"p3"];
        }
    }
else {
    [mooreDictToReturn setObject:[NSNull new] forKey:@"p1"];
    [mooreDictToReturn setObject:[NSNull new] forKey:@"p2"];
    [mooreDictToReturn setObject:[NSNull new] forKey:@"p3"];
    }

return mooreDictToReturn;

}

-(NSString*) stepClockwiseMooreItem:(NSString*) currentMooreItem {

CCLOG(@"STEPCLOC");

//go through the 8-moore clockwise starting at P6 until hit. add hit to array. mark "entry box" as last box that was inactive before hit
//go to hit box and go through 8 starting with last hit box (if p3 was prior hit then p2 was empty so go to p8 of new box. these are the pairs: if X hit then prior empty was Y: p1>p8 P2>p1, P3>p2, P4>p3 etc.

NSString *returnString;

if ([currentMooreItem isEqualToString:@"p1"]){returnString= [NSString stringWithFormat:@"p2"];}
else if ([currentMooreItem isEqualToString:@"p2"]){returnString= [NSString stringWithFormat:@"p3"];}
else if ([currentMooreItem isEqualToString:@"p3"]){returnString= [NSString stringWithFormat:@"p4"];}
else if ([currentMooreItem isEqualToString:@"p4"]){returnString= [NSString stringWithFormat:@"p5"];}
else if ([currentMooreItem isEqualToString:@"p5"]){returnString= [NSString stringWithFormat:@"p6"];}
else if ([currentMooreItem isEqualToString:@"p6"]){returnString= [NSString stringWithFormat:@"p7"];}
else if ([currentMooreItem isEqualToString:@"p7"]){returnString= [NSString stringWithFormat:@"p8"];}
else if ([currentMooreItem isEqualToString:@"p8"]){returnString= [NSString stringWithFormat:@"p1"];}

return returnString;

}

-(NSString*) stepCounterClockMooreItem:(NSString*) currentMooreItem {

//go through the 8-moore clockwise starting at P6 until hit. add hit to array. mark "entry box" as last box that was inactive before hit
//go to hit box and go through 8 starting with last hit box (if p3 was prior hit then p2 was empty so go to p8 of new box. these are the pairs: if X hit then prior empty was Y: p1>p8 P2>p1, P3>p2, P4>p3 etc.

NSString *returnString;

if ([currentMooreItem isEqualToString:@"p1"]){returnString= [NSString stringWithFormat:@"p8"];}
else if ([currentMooreItem isEqualToString:@"p2"]){returnString= [NSString stringWithFormat:@"p1"];}
else if ([currentMooreItem isEqualToString:@"p3"]){returnString= [NSString stringWithFormat:@"p2"];}
else if ([currentMooreItem isEqualToString:@"p4"]){returnString= [NSString stringWithFormat:@"p3"];}
else if ([currentMooreItem isEqualToString:@"p5"]){returnString= [NSString stringWithFormat:@"p4"];}
else if ([currentMooreItem isEqualToString:@"p6"]){returnString= [NSString stringWithFormat:@"p5"];}
else if ([currentMooreItem isEqualToString:@"p7"]){returnString= [NSString stringWithFormat:@"p6"];}
else if ([currentMooreItem isEqualToString:@"p8"]){returnString= [NSString stringWithFormat:@"p7"];}

return returnString;
}

-(NSString*) stepMooreBacktrackAfterHitAt:(NSString*) currentMooreItem {

// with the moore, you can only back track adjacenetly, not diagnally, so its not straightforward counterclockwise walk

NSString *returnString;

if ([currentMooreItem isEqualToString:@"p1"]){returnString= [NSString stringWithFormat:@"p6"];}
else if ([currentMooreItem isEqualToString:@"p2"]){returnString= [NSString stringWithFormat:@"p8"];}
else if ([currentMooreItem isEqualToString:@"p3"]){returnString= [NSString stringWithFormat:@"p8"];}
else if ([currentMooreItem isEqualToString:@"p4"]){returnString= [NSString stringWithFormat:@"p2"];}
else if ([currentMooreItem isEqualToString:@"p5"]){returnString= [NSString stringWithFormat:@"p2"];}
else if ([currentMooreItem isEqualToString:@"p6"]){returnString= [NSString stringWithFormat:@"p4"];}
else if ([currentMooreItem isEqualToString:@"p7"]){returnString= [NSString stringWithFormat:@"p4"];}
else if ([currentMooreItem isEqualToString:@"p8"]){returnString= [NSString stringWithFormat:@"p6"];}

return returnString;

}

-(void) boxAreaCollapse:(float)boxCenterGridCoordX andY:(float)boxCenterGridCoordY atDepth:(int)depth{

//ok, to do this, we'll use moore neighbor tracing
//might be able to capture edges by add a row above and below and to either side of grid. each of these has a unique identity so if end wall included or something but this is later

//set array of boxes to empty
NSMutableArray * boxesOnEdgeOfShapeContainingTouchedBox = [NSMutableArray arrayWithCapacity:( (self.numberOfBoxesOfAcross/(pow(2,depth)))*(self.numberOfBoxesOfAcross/(pow(2,depth))) )];

//get array of array for this "depth"
NSMutableArray *boxArray = [arrayOfBoxArrays objectAtIndex:depth];

//get the box that was touched
NSMutableArray * boxRowSameAsTouchedBox = [boxArray objectAtIndex:boxCenterGridCoordY];
Box * boxTouched = [boxRowSameAsTouchedBox objectAtIndex:boxCenterGridCoordX];

CCLOG(@"boxTouched %i,%i",boxTouched.gridAbsoluteXCoord,boxTouched.gridAbsoluteYCoord);

//define boundaries > dont need to do this
//bottom left coord is (0,0), top right is (maxCoord,maxCoord)
//float maxCoord = (self.numberOfBoxesOfAcross/(pow(2,depth))-1); // the -1 because the first is "coord" is 0

//must start on bottom left so move all the way left until hit inactive then down
//move to the left through adjacenet boxes from touched best to find the furthest left connected directly to touch box
int numberOfBoxesLeft = boxCenterGridCoordX;
Box * furthestLeftBox = boxTouched;
for (int i = 1; i <= numberOfBoxesLeft; i++){
    Box * box = [boxRowSameAsTouchedBox objectAtIndex:boxCenterGridCoordX-i];
    if (box.boxState == kBoxActivated || box.boxState == kBoxClicked || box.boxState == kBoxLastDepthCompleted){
        furthestLeftBox = box;
        }
    else {
        break;
        }
    }

//move down from there to connected boxes below
int furthestLeftXCoord = (furthestLeftBox.gridAbsoluteXCoord / ((pow(2,depth))));
int furthestLeftYCoord = (furthestLeftBox.gridAbsoluteYCoord / ((pow(2,depth))));
int numberOfBoxesBelow = furthestLeftYCoord;

Box * furthestDownBox = furthestLeftBox;
for (int i = 1; i <= numberOfBoxesBelow; i++){
    NSMutableArray * boxRowBelow = [boxArray objectAtIndex:furthestLeftYCoord-i];
    Box * box = [boxRowBelow objectAtIndex:furthestLeftXCoord];
    if (box.boxState == kBoxActivated || box.boxState == kBoxClicked || box.boxState == kBoxLastDepthCompleted){
        furthestDownBox = box;
        }
    else {
        break;
        }
    }


//define starting Box and "entry box" for defining when to STOP this algorithim. we know p6 from the starting box should be empty and when we reenter the starting box from p6 we will define the "end"
Box * startingBoxFilled = furthestDownBox;
NSString * startingEnterPoint = @"p6";

//add start box to shape array > dont need to do this, it'll happen in first load of loop
//[boxesOnEdgeOfShapeContainingTouchedBox addObject:furthestDownBox];

//go through the 8-moore clockwise starting at P6 until hit. add hit to array. mark "entry box" as last box that was inactive before hit
//go to hit box and go through 8 starting with last hit box (if p3 was prior hit then p2 was empty so go to p8 of new box. these are the pairs: if X hit then prior empty was Y: p1>p8 P2>p1, P3>p2, P4>p3 etc.


//define first hitBox and entry point for backtrack
Box * hitBox =furthestDownBox;
NSString * hitBoxEnteredFrom = @"p6";

//CCLOG(@"fursthest down box %i,%i: %@, ",hitBox.gridAbsoluteXCoord, hitBox.gridAbsoluteYCoord,hitBox);

BOOL algorithimRunning = YES;
BOOL singleCircleRunning;

while (algorithimRunning == YES) {
    //CCLOG(@"starting loop for box relX %i, relY%i", hitBox.gridAbsoluteXCoord, hitBox.gridAbsoluteYCoord);

    NSMutableDictionary * mooreDictForBox = [self returnMooreNeighborDictFromBox:hitBox];
    singleCircleRunning = YES;

    NSString * circleStartingChecker = hitBoxEnteredFrom;

    while (singleCircleRunning == YES){

        //CCLOG(@"inner circle loop from box relX %i, relY%i checking  %@ ", hitBox.gridAbsoluteXCoord, hitBox.gridAbsoluteYCoord,hitBoxEnteredFrom);

        if ([hitBoxEnteredFrom isEqualToString:circleStartingChecker]){
            singleCircleRunning = NO;
            //CCLOG(@"loop circled around, ending inner loop");
            }

        if ([[mooreDictForBox objectForKey:hitBoxEnteredFrom] isKindOfClass:[Box class]]){
            Box * box = [mooreDictForBox objectForKey:hitBoxEnteredFrom];
            //CCLOG(@"moore object is box: state %i, depth %i, gridX %i, y %i", box.boxState, box.trueDepth, box.gridAbsoluteXCoord, box.gridAbsoluteYCoord);
            if (box.boxState == kBoxActivated || box.boxState == kBoxClicked || box.boxState == kBoxLastDepthCompleted){
                hitBox = box;
                [boxesOnEdgeOfShapeContainingTouchedBox addObject:box];
                NSString * newmooreChecker = [self stepMooreBacktrackAfterHitAt:hitBoxEnteredFrom];
                hitBoxEnteredFrom = newmooreChecker;
                singleCircleRunning = NO;
                //CCLOG(@"box is activated, etc, adjusting to %@ for backtrack ", hitBoxEnteredFrom);
                }
            else {
                NSString * newmooreChecker = [self stepClockwiseMooreItem:hitBoxEnteredFrom];
                hitBoxEnteredFrom = newmooreChecker;
                //CCLOG(@"box is not activated, etc, check next moore");
                }
            }
        else {
            //CCLOG(@"moore object is nil, check next moore object");
            NSString * newmooreChecker = [self stepClockwiseMooreItem:hitBoxEnteredFrom];
            hitBoxEnteredFrom = newmooreChecker;
            }
        }

    //repeat until you reach "starting down". if entered starting down from "entry" stop.
    if ([hitBox isEqual:startingBoxFilled] && [hitBoxEnteredFrom isEqualToString:startingEnterPoint]) {
        algorithimRunning = NO;
        //CCLOG(@"hitbox is starting box and entered from is same as start");
        }
    }


//create an array of dictionaries to represent "on" and "off" for the rows.
//first initialize the array of row arrays with NO in each pixel slot
int numberOfRows = (self.numberOfBoxesOfAcross/(pow(2,depth)));
NSMutableArray * arrayOfRowsForShape = [NSMutableArray arrayWithCapacity:numberOfRows];
for (int i= 0; i< numberOfRows; i++){
    NSMutableDictionary * rowDict = [NSMutableDictionary dictionaryWithCapacity:numberOfRows];
    for (int p = 0; p< numberOfRows; p++){
        [rowDict setObject:[NSString stringWithFormat:@"OUTSIDE"] forKey:[NSNumber numberWithInt:p]];
        }
    [arrayOfRowsForShape addObject:rowDict];
    }

//go through boxes in shape and change to YES if box located at that spot
for (Box * box in boxesOnEdgeOfShapeContainingTouchedBox) {
    NSMutableDictionary * rowDict = [arrayOfRowsForShape objectAtIndex:box.gridAbsoluteYCoord/(pow(2,depth))];
    [rowDict setObject:[NSString stringWithFormat:@"EDGE"] forKey:[NSNumber numberWithInt:box.gridAbsoluteXCoord/(pow(2,depth))]];
    }

//go through array of dict and for each one, go left to right and mark anything bound on both sides as "inside"
for (int locationY = 0; locationY<(self.numberOfBoxesOfAcross/(pow(2,depth))); locationY++ ){
    NSMutableDictionary * rowDict = [arrayOfRowsForShape objectAtIndex:locationY];
    BOOL possiblyInsideContour = NO;
    BOOL edgeFound = NO;
    int holesFound = 0;
    for (int locationXin = 0; locationXin<(self.numberOfBoxesOfAcross/(pow(2,depth))); locationXin++ ){

        NSNumber * locationX = [NSNumber numberWithInt:locationXin];
        NSMutableArray * markForChanging = [NSMutableArray arrayWithCapacity:(self.numberOfBoxesOfAcross/(pow(2,depth)))];
        NSString * thisLocation = [rowDict objectForKey:locationX];
        if ([thisLocation isEqualToString:@"EDGE"] && edgeFound==NO  && possiblyInsideContour==NO ){
            edgeFound=YES;
            }
        else if ([thisLocation isEqualToString:@"OUTSIDE"] && edgeFound==YES && possiblyInsideContour==NO){
            possiblyInsideContour=YES;
            [rowDict setObject:@"MAYBEINSIDE" forKey:locationX];
            [markForChanging addObject:[rowDict objectForKey:locationX]];
            }
        else if ([thisLocation isEqualToString:@"OUTSIDE"] && possiblyInsideContour==YES ){
            [rowDict setObject:@"MAYBEINSIDE" forKey:locationX];
            edgeFound=NO;
            }
        else if ([thisLocation isEqualToString:@"EDGE"] && possiblyInsideContour==YES ){
            possiblyInsideContour=NO;
            holesFound++;
            edgeFound=YES;
            }

        }

    int holesPatched = 0;
    BOOL patchingHole=NO;
    while (holesPatched < holesFound){
        for (int locationXin = 0; locationXin<(self.numberOfBoxesOfAcross/(pow(2,depth))); locationXin++ ){
            NSNumber * locationX = [NSNumber numberWithInt:locationXin];
            NSString * thisLocation = [rowDict objectForKey:locationX];
            if ([thisLocation isEqualToString:@"MAYBEINSIDE"]){
                patchingHole = YES;
                 [rowDict setObject:@"INSIDE" forKey:locationX];
                }
            else if ([thisLocation isEqualToString:@"EDGE"] &&  patchingHole == YES){
                holesPatched++;
                patchingHole=NO;
                }
            }
        }

    }


int locationY=0;
for (NSMutableDictionary *rowDict in arrayOfRowsForShape){

    for (int locationXin = 0; locationXin<(self.numberOfBoxesOfAcross/(pow(2,depth))); locationXin++ ){

        NSNumber * locationX = [NSNumber numberWithInt:locationXin];

        NSString * thisLocation = [rowDict objectForKey:locationX];
        if ([thisLocation isEqualToString:@"INSIDE"]){
            CCLOG(@"inside at %i,%i", [locationX intValue], locationY);
            }
        }
    locationY++;
    }










}

Figuring out if a point on a grid is surrounded by points of a certain kind

1 Answers1