Finding Bubbles in a 2D Character Array in Java

Question

I am dealing with a problem in my Go Game project.

I have a board (gobana) represented by a two-dimensional array of characters. Before each next step, I would like to check the "bubbles" in the array. The bubble should be a 4-connected region of identical symbols surrounded in 4 directions by another group of defined identical symbols. If this “bubble” exists, the symbols inside should be replaced by others. But there may be more areas, and not all of them are nested. For example, I have this board:

1 2 3 4 5 6 7 8 9 10 11 12 13 - - - - - - - - - - - - - - - A | + + + + + + + + + + + + + | B | + + + + + + + + + + + + + | C | + + + + + + + + + + + + + | D | + + + + + + + + + + + + + | E | + + + + + + + + + + + + + | F | + + OOOO + + + + + + + | G | + OXXXXO + + + + + + | H | + + OOXXO + + + + + + | I | + + + + OXXO + + + + + | J | + + + + OXO + + + + + + | K | + + + + + O + + + + + + + | L | + + + + + + + + + + + + + | M | + + + + + + + + + + + + + | - - - - - - - - - - - - - - - 

And I would like to find the Xs bubble, count them and replace them with a “Z”.

I searched for it and I think that some labeling algorithms for the Connected component or FloodFill can do the job, but I'm not sure how to implement it. Could this solve or something less complicated? Thanks you

Edit: I tried to find a pattern that could find areas of a certain nature and count their freedoms, but it always failed when the location was layered. Changing the data structure may be a solution, but if possible, I would like to do it the way it is now.

My current solution idea:

 public void solve(){ if (boardContainsEnclosedAreas(goban, onMovePlayerStone, oppositePlayerStone){ onMovePlayerScore += countElementsInAreaAndReplaceThem(onMovePlayerStone, 'Z'); } } public boolean boardContainsEnclosedAreas(char[][] playingBoard, char searchedChar, char surroundingChar){ // this method should find the bubble in the playingBoard array } public int countElementsInAreaAndReplaceThem(char searchedChar, char replacingChar){ // the method should go through the bubble and replace all inner chars // returns amount of replaced chars } 

Answer 1

You can do this with a recursive method using the FloodFill theory.

Basically, go through your grid and each time you find X, replace it with Z, as well as 4 neighboring ones (if applicable). But the trick is this: instead of just replacing them and looping around each time, call the same (calling) method again to do this. Recursiveness does the rest.

Here is his (quick-made) pseudo-code version: (assuming your grid is indexed from 0 to xmax, from 0 to ymax)

 int numberOfBubbles = 0; for (x = 0 to xmax) { for (y = 0 to ymax) { if (getCharAt(x, y) == "X") { // this if is needed because you want to count the bubbles. If not, you could just do handleBubble(x, y); numberOfBubbles++; handleBubble(x, y); } } } // Recursive method void handleBubble(int x, int y) { if (getCharAt(x, y) != "X") { return; // exit condition } getCharAt(x, y) = "Z"; if (x > 0) handleBubble(x-1, y); if (x < xmax) handleBubble(x+1, y); if (y > 0) handleBubble(x, y-1); if (y < ymax) handleBubble(x, y+1); } 

As far as I know, this is a solution only for this problem, which works no matter what strange shape your bubble is. The difficulty is also good.

This can be optimized further since it is currently checking for characters that obviously do not contain X (since they have just been replaced with Z). This remains as an exercise for the reader :)

(Note: the minesweeper game, among other things, is based on this decision)

Answer 2

Here we need an algorithm (in pseudo-code) that I used for similar image analysis:

 regions = Collection<Set<Point>> foreach (Point p : allBoardLocations) if (charAtLocation(p) != 'X') continue foundInRegion = false for (Set<Point> s : regions) if (s.contains(p)) foundInRegion=true break; if (!foundInRegion) newRegion = new Set<Point>() stack = new Stack<Point>() stack.push(p) while (!stack.empty()) foreach (Point n : neighboringPoints(stack.pop())) if (charAtLocation(n) == 'X') if (!newRegion.contains(n)) newRegion.add(n); stack.push(n); 

Basically, you save a set of sets of points, where each set represents a “bubble” of adjacent points on the board. Scan each place on the board, and if it’s “X” and it’s not yet in the region, create a new region and a stack containing this location, and although there is an element in the stack, visit its neighbors who are looking for invisibles ” X ", adding them to a new area and stack as detected.

At the end, you will get a set of sets of points, each of which will be a “bubble”.