• ### Announcements

#### Archived

This topic is now archived and is closed to further replies.

# Checking if a spot in a 2d array is enclosed

## Recommended Posts

Lord Hen    122
Ok, Im thinking of making a clone of a fun game called Rampart. You have to build walls around a castle to get more territory...and im having trouble thinking of an algorithm for checking if any given spot on the board (represented in a 2d array) is surrounded by walls in all directions... So, for example, in the following grid, check if point X is surrounded by walls(W)....0 is nothing
00WWWWW0
00W000W0
00WX00W0
00WWWWW0
00000000

but this would not be enclosed by walls:
00WWWWW0
00W000W0
00WX00W0
000WWWW0
00000000

Agh, I just cant think of a way to check it.. If anyone can come up with some pseudocode or just a general idea of how to do it it would really help. Thanks, Lord Hen

##### Share on other sites
Wavarian    850
Seems like you need a recursive algorithm for this. You start with the 'X', and check the tiles around it. If it's a wall tile, then you can continue through the algorithm, if it's not a wall, then use the algorithm to check for walls around that tile.

Something like this:

'X' is enclosed if it is surrounded by wall tiles, N,S,E,W,NE,SE,SW,NW.

so you go into the algorithm:
bool Enclosed(tile){   bool N,S,E,W,NE,SE,SW,NW;         // Check to see if north tile is a wall   if(tile.N == wall)       N = true;      // If it isn't, check to make sure north tile is Enclosed   else N = Enclosed(tile.N);      // Check to see if south tile is a wall   if(tile.S == wall)       S = true;      // If it isn't, check to make sure south tile is Enclosed   else S = Enclosed(tile.S);      ...etc      // Return true only if tile is enclosed by walls   return (N && S && E && W && NE && SE && SW && NW);}

I didn't bother checking the above, I just hope that it gave you a possible idea since noone else has posted yet.

Have fun =\

[edited by - wavarian on October 10, 2003 12:11:50 AM]

##### Share on other sites
Wavarian    850
Bah, looking at that again I see you might get a continuous loop happening using the method I suggested.

##### Share on other sites
Real    122
Try to search it like a tree.

Think of the connecting wall as a tree. Scroll down the list and pick up the 1st wall block you see.

Once you pick up the 1st wall block, mark it "A" then you start a depth 1st search. Break out of the depth 1st search when you find a wall block down the tree that is marked "A." Well it just so happens that wall block you found marked "A" is the top of the tree.

Thats right! You just made a loop all the way around. And you are sure if you search down one path and comes back where you were then you are enclosing an area.

Of course you have to check if the alls are simply placed like this.

WW
WW

Which it does circle around but doesn''t enclose any area.

##### Share on other sites
oliii    2196
a simple flood-fill algorithm should detect holes in walls. You flood-fill the map everytime a wall is constructed, starting from somewhere you know is outside any closed area. This will paint everything that is not fully closed. Then you are left with unpainted enclosed areas, where you can paint each of them left into a different color, to differenciate them, or merge them into one single closed area.

##### Share on other sites
Lord Hen    122

A while after I posted, I had thought I could pick a point in the last wall constructed, and trace around the wall until that point is reached again...

After a closed wall is found, I could use my floodfill algo to fill in the enclosed areas.

Before I had posted, I was already trying to think of a way my floodfill could be applied to it, but I overlooked painting everything thats not in walls.
But I see one problem with oliii''s idea...
~ = Water
W = Wall
~~~~~~~~WWWWW WWW      WW      WWWWWWWWW

Although water is right next to the wall, that is still counted as not closed, and should be...but oliii''s idea doesnt take that into consideration... Any ideas? Count water AS land during the check?

Thanks,
Lord Hen