Finding path depending on cells' value on 2D grid array

Question

I have a grid composed with JLabel. Each cell has 3 states: public enum Token{ VIDE, CERCLE_ROUGE, CERCLE_BLEU } An empty cell == Token.VIDE

I have this simple algorithm that find all neighbors of a given cell then I use swing custom painting to draw a polygon following the path having the center of the label as points.

private CellsList getNeighbors(int  row, int col) {
    CellsList neighbors = new CellsList();
    for (int colNum = col - 1 ; colNum <= (col + 1) ; colNum +=1  ) {
        for (int rowNum = row - 1 ; rowNum <= (row + 1) ; rowNum +=1  ) {
            if(!((colNum == col) && (rowNum == row))) {
                if(withinGrid (rowNum, colNum )  ) {
                    neighbors.add( new int[] {rowNum, colNum});
                }
            }
        }
    }

    return neighbors;
}

here is the condition to have a path:

if((size() >= MIN_PATH_LEGTH) && neighbors.contains(origin)  ) {
            add(cell);
            return true;
        }

Now I want to make it more precise by adding conditions such as a path can be valid if only there are at least 4 cells with the same value found in the neighborhood AND at least one opposite value.

Example: Red cells at (11, 10)(10, 11)(11, 12)(12, 11) can form a valid path if only there is at least a Blue cell at (11, 11). (See image below)

And the following can't be a valid path, so no drawing:

For now, the algorith finds a path only with the minimal value (int MIN_PATH_LEGTH = 3) I've defined but I can't find a way to define the second condition (at least one opposite cell value within the neighborhood)

I'll edit with new elements if needed.

Answer 1

My answer is based on the code posted in a previous answer.

Path class
Add isWithinLoop to check if a cell is within path by checking if it has a path-cell to its left, right, top and bottom.
Also add getContainedWithin which returns a collection of all cells that are bounded by the path, and their token is of the opposite color of the path

    //returns a collection of all cells that are bounded by the path 
    //and their token is of the opposite color of the path 
    List<int[]> getContainedWithin() {

        //find path max and min X values, max and min Y values
        minPathRow = grid[0].length; //set min to the largest possible value
        maxPathCol = grid.length;
        maxPathRow = 0;              //set max to the largest possible value
        maxPathCol = 0;

        //find the actual min max x y values of the path
        for (int[] cell : this) {
            minPathRow = Math.min(minPathRow, cell[0]);
            minPathCol = Math.min(minPathCol, cell[1]);
            maxPathRow = Math.max(maxPathRow, cell[0]);
            maxPathCol = Math.max(maxPathCol, cell[1]);
        }

        //todo remove after testing
        System.out.println("x range: "+minPathRow + "-" 
        + maxPathRow + " y range: " + minPathCol + "-" + maxPathCol);

        List<int[]> block = new ArrayList<>(25);
        int[] cell = get(0);//get an arbitrary cell in the path
        Token pathToken = grid[cell[0]][cell[1]]; //keep a reference to its token

        //iterate over all cells within path x, y limits
        for (int col = minPathCol; col < (maxPathCol); col++) {

            for (int row = minPathRow; row < (maxPathRow); row++) {

                //check cell color
                Token token = grid[row][col];
                if ((token == pathToken) || (token == Token.VIDE)) {
                    continue;
                }
                if (isWithinLoop(row,col)) {
                    block.add(new int[] {row, col});
                }
            }
        }

        return block;
    }

    //check if row, col represent a cell with in path by checking if it has a 
    //path-cell to its left, right, top and bottom 
    private boolean isWithinLoop(int row, int col) {

        if(  isPathCellOnLeft(row, col)
             &&
             isPathCellOnRight(row, col)
             &&
             isPathCellOnTop(row, col)
             &&
             isPathCellOnBottom(row, col)
          ) {
            return true;
        }

        return false;
    }

    private boolean isPathCellOnLeft(int cellRow, int cellCol) {

        for ( int col = minPathCol; col < cellCol ; col++) {

            if(getPath().contains(new int[] {cellRow, col})) {
                return true;
            }
        }

        return false;
    }

    private boolean isPathCellOnRight(int cellRow, int cellCol) {

        for ( int col = cellCol; col <= maxPathCol ; col++) {

            if(getPath().contains(new int[] {cellRow, col})) {
                return true;
            }
        }

        return false;
    }

    private boolean isPathCellOnTop(int cellRow, int cellCol) {

        for ( int row =minPathRow; row < cellRow ; row++) {

            if(getPath().contains(new int[] {row, cellCol})) {
                return true;
            }
        }

        return false;
    }

    private boolean isPathCellOnBottom(int cellRow, int cellCol) {

        for ( int row = cellRow; row <= maxPathRow; row++) {

            if(getPath().contains(new int[] {row, cellCol})) {
                return true;
            }
        }

        return false;
    }
}

Model class
Add a getter method to access getContainedWithin:

List<int[]> getContainedWithin() {

    return (path == null ) ? null : path.getContainedWithin();
} 

Control class
Update ModelListener to ignore a path if getContainedWithin is empty:

private class ModelListener implements PropertyChangeListener {
        @Override
        public void propertyChange(PropertyChangeEvent evt) {
            IndexedPropertyChangeEvent iEvt = (IndexedPropertyChangeEvent)evt;
            int index = iEvt.getIndex();
            int row = index / Model.COLS;
            int col = index % Model.COLS;
            Token token = (Token) evt.getNewValue();

            SwingUtilities.invokeLater(new Runnable() {

                @Override
                public void run() {

                    view.setCell(token, row, col);
                    CellsList path = model.getPath();
                    //ignore path if null, empty or encloses no cell
                    if((path == null) || path.isEmpty()
                                        || model.getContainedWithin().isEmpty()) {
                        return;
                    }
                    view.addPath(path);
                    view.refresh();
                }
            });
        }
    }

The complete code can be downloaded for this repo.

Answer 2

test before calling this method if the redCell's path OK:

public boolean isThereABlueCellWithinMyRedPath() {
    // height = height of your map
    // width = width of yout map
    // this array is suppose to be in an other place...
    Cell[][] cellArray = new Cell[height][width];
    // ... so are those two lists
    List<Cell> blueCellsList = new ArrayList<>();
    List<Cell> redCellsList = new ArrayList<>();

    //foreach blueCell on the map ...
    for (Cell blueCell : blueCellsList) {
        boolean north = false;
        boolean east = false;
        boolean south = false;
        boolean west = false;
        int originX = blueCell.getX();
        int originY = blueCell.getY();

        // ... if there is a redCell at north...
        for (int i = originY; i >= 0; i--) {
            if (redCellsList.contains(cellArray[originX][i])) {
                north = true;
                break;
            }
        }
        // ... East ...
        for (int i = originX; i < cellArray[originX].length; i++) {
            if (redCellsList.contains(cellArray[i][originY])) {
                east = true;
                break;
            }
        }
        // ... South ...
        for (int i = originY; i < cellArray.length; i++) {
            if (redCellsList.contains(cellArray[originX][i])) {
                south = true;
                break;
            }
        }
        // ... West ...
        for (int i = originX; i >= 0; i--) {
            if (redCellsList.contains(cellArray[i][originY])) {
                west = true;
                break;
            }
        }
        // ... I am surrended by redCell
        if (south && east && north && west)
            return true;
    }
    return false;
}

I did not try the code but it seems to work.

Answer 3

Maybe you can make a list of blue cells and redcells and if you want to test if a there's a blue cell within the red cell's path you:

go to NORTH until you meet a redCell or a map limit : if it 's a map limit you test with the next blueCell, else you go back to your position and do the same for EAST, SOUTH, WEST. If on the 4 sides you find a redCell first, you return true else you return false.

It can be enough if you want to test in a quite small map. But if the shape made by the red cell can be free I don't find a better way.