Determining If Tiles Are Surrounded


Orkie

Super Duper Mega GP Mania
Joined
Mar 22, 2006
Messages
2,373
Location
UK
Website
www.gp2x.dev
Hi.

In a game I'm currently working on, I have a 20 x 7 grid of square tiles, each of different colours. One player starts on the left and the other on the right. The aim of the game is (clearly) to capture more tiles than your opponent. However, I want tiles to automatically become captured when they are completely separated from the other side of the grid (i.e. there is some kind a line, not necessarily a straight one, cutting a tile or group of tiles off from the opponent's side).
I'm having trouble thinking of a way of determining if tiles match this requirement and should be captured, or not and was wondering if anybody can think of a way of doing this (it doesn't really matter how efficient the method is, so long as it works that's fine).

Thanks
 
Orkie posted on Dec 8 2006 at 12:03 AM said:
Hi.

In a game I'm currently working on, I have a 20 x 7 grid of square tiles, each of different colours. One player starts on the left and the other on the right. The aim of the game is (clearly) to capture more tiles than your opponent. However, I want tiles to automatically become captured when they are completely separated from the other side of the grid (i.e. there is some kind a line, not necessarily a straight one, cutting a tile or group of tiles off from the opponent's side).
I'm having trouble thinking of a way of determining if tiles match this requirement and should be captured, or not and was wondering if anybody can think of a way of doing this (it doesn't really matter how efficient the method is, so long as it works that's fine).

Thanks

Is this line also made up of tiles? Having problems visualising what you mean
 
Last edited by a moderator:
sounds kind like an othello type of game?
maybe a picture would help:

start:
ZZZZYYYY
ZZZZYYYY
ZZZZYYYY
ZZZZYYYY

later:
ZZZZZZYY
ZZZZAZYY
ZZZZZZYY
ZZZZYYYY

Is this what you mean? 'A' is surrounded by 'Z', so it should be 'Z' now?

If this is the case, I would have each tile as an object with the paraneters of x,y,h,w,state. x,y,h,w will give the perimeter/location of the each tile and the state tells you who has control. Then all you need is a loop to compare. Very simpified ut maybe it will give you an idea.
 
hmmm, but what if you have a group of tiles surrounded. I'm not a coder, but this does sound like a tricky problem. :unsure:
 
1 | 1 | 1 | 0 | 0 | 0 | 0
1 | 1 | 1 | 0 | 0 | 0 | 0
1 | 1 | 1 | 0 | 0 | 0 | 0
1 | 1 | 1 | 0 | 0 | 0 | 0
1 | 1 | 1 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 2 | 2 | 2
0 | 0 | 0 | 0 | 2 | 2 | 2
0 | 0 | 0 | 0 | 2 | 2 | 2
0 | 0 | 0 | 0 | 2 | 2 | 2
0 | 0 | 0 | 0 | 0 | 0 | 0

1 | 1 | 1 | 0 | 0 | 0 | 0
1 | 1 | 1 | 0 | 0 | 0 | 0
1 | 1 | 1 | 0 | 0 | 0 | 0
1 | 1 | 1 | 0 | 0 | 0 | 0
1 | 2 | 2 | 2 | 0 | 0 | 0
1 | 2 | 1 | 0 | 0 | 0 | 0
0 | 2 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 2 | 2 | 2
0 | 0 | 0 | 0 | 2 | 2 | 2
0 | 0 | 0 | 0 | 0 | 0 | 0


you could run a check on every element in your array
and if the array element around your select tile are equal to 1 of 0
then the tile has not been captured else it been isolated.

this at what you mean : )
 
Look up flood fill

Find an empty square that has not been checked this round.
Using the flood fill algorithm make sure that the square is not contiguous with any two squares of a different colour.
If it is contiguous with squares of a more than one colour (not including empty) then it is not surrounded and neither are any of the squares you checked using the flood fill.
If it is only contiguous with empty squares and squares of a single colour it is surrounded and so are all the squares you checked with the flood fill.

The cases where this will fail are when there is only one coloured square on the board in which case the entire board will be considered surrounded.

If your board has coloured boarders (i.e. red starts on the left and blue on the right) then they should just be pre-coloured squares and this approach will still work.

Code:
. = empty square
o = team1
x = team2
* = checked square
1 = starting square

1..o.....		  ***o....		 oooo....
...o.....  becomes ***o.... becomes oooo....
...o.....		  ***o....		 oooo....
oooo.....		  oooo....		 oooo....
.........		  ........		 ........  


1..o.....		  ***o****		 ...o....
...o.....  becomes ***o****		 ...o....
.......x.		  ******x* becomes ...o....
oooo.....		  oooo****		 ......x.
.........		  ********		 oooo....

I hope this helps.
Charlie
 
I'm already using a flood fill elsewhere, I hadn't thought of using it like that though - good idea.

Thanks for all the suggestions.
 
Back
Top