Find contiguous body...

Unity Engine
1

I’m working on a game similar to GO. The winner has the most contiguous number of blocks on a grid. Does anyone have any insight on how to calculate a number of blocks that are touching/contiguous to each other?

I hope this isn’t as hard as the “traveling salesman” :wink:

Thanks for any help,
Ethan

2

I think a modified flood-fill algorithm should work okay.

Hope that helps…
-Jon

3

Yep - use a recursive function to “paint” the matrix from “uncounted” to “counted”, incrementing a variable as you go. I’d go into more detail, but Wikipedia pretty much has it covered.

The hard part will be not screwing up the recursion, since Unity has no infinite-loop-breaking functionality.

4

Thanks Jon, this seems to be the way to go… I just hope I have the smarts to pull it off, probably not :wink:

The thing I’m wondering is how to “fill” the many contiguous spaces of each player and determine which one is the largest “fill” field. Time for me to step up and learn some real programming I guess :wink:

Uugh, I’ve put all my scripting knowledge into this game so far, but the scoring method is obviously the most important part and I’m at a loss. The grid is only 20x20, but I need a fill script that calculates each player’s region that is contiguous and then says who has the largest single region (out of several that they might have). I don’t want anyone to solve this for me, just some pointers would be great.

Ethan

23619--838--$picture_1_178.png

5

We had a program in my HS CS class wherein we face this exact problem. The trick is to have a temporary matrix of “painted” cells. As you step through them recursively, on the way “down” (deeper into the recursion, i.e. before the recursive function call), set the spot in the matrix to “painted”, and increment the count variable. At each step, check all 4/8 spots around you; if the temp matrix is not painted at that spot, and that that spot is not an obstacle. If it’s an open, unpainted spot, recurse in to it. After you’ve checked all 4/8 spots, simply exit the function. At the end of the whole thing, the variable you increment will be the number of spots.

Hope that helps.

P.S. That screenshot looks really slick :smile:

6

i’m a big fan of GO so i’d definitly be interested in this one. there’s alot of academic stuff out there for go - i’d look for algorithms searching for dead-live groups calculating endgame points - there’s gotta be something open source out there or a thesis paper you could read for ideas.

EDIT: i have no idea if this is what you need as its over my head, but check the bottom section of this page (gnugo is open source so you can grab the source code):