Archived

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

Lord Hen

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Lord Hen    122
Thanks for your replies =)

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 WW
W W
W W
WWWWWWWW

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

Share this post


Link to post
Share on other sites
hplus0603    11347
Classify square types into "enclosing" and "not enclosing". Water and land are both "not enclosing".

If a flood fill from point X terminates at "enclosing" in all directions, then it''s enclosed.

Note that flood fills over large maps may take lots of CPU. If performance is of concern, then you probably want to flood fill only, say, a bounding box of enclosing/placed boxes, or out to 10 units away from the X and assume that you can''t fill more than 10x10 squares at a time.

Share this post


Link to post
Share on other sites