Implement Recursive Flood Fill (Zero-Clear)

[lukeKilpatrick-minitap]

Description
When a user reveals a cell with 0 neighbors, the game must automatically reveal all surrounding cells.

Requirements

• Implement a recursive function (DFS or BFS).
• Trigger: User reveals a cell where neighborCount == 0.
• Action: Reveal all 8 neighbors.
• Recursion: If any of those neighbors are also 0, repeat the process.
• Stop condition: Stop when hitting a cell with neighborCount > 0.

[traycerai]

Plan

Observations

The repository currently contains only documentation files (file:README.md and file:LICENSE). No game logic has been implemented yet. The README describes a mobile-first Minesweeper game with classic rules, including flood fill behavior when digging a cell with 0 adjacent mines. The tech stack is not yet determined, with options including React Native, Flutter, or native Swift/Kotlin.

Approach

The flood fill algorithm will use a recursive approach (DFS preferred for simplicity) to automatically reveal all connected cells when a zero-neighbor cell is revealed. The implementation will traverse the 8-directional neighbors, revealing cells recursively until hitting cells with neighbor counts greater than zero or board boundaries. This approach aligns with classic Minesweeper behavior and provides the best user experience.

Implementation Steps

1. Core Game State Structure

Define the game board data structure to track:

• Cell state: Each cell needs properties for:
  • isMine (boolean)
  • isRevealed (boolean)
  • isFlagged (boolean)
  • neighborCount (integer 0-8)
  • row and column coordinates

2. Neighbor Count Calculation

Before implementing flood fill, ensure a function exists to calculate neighbor counts:

• For each non-mine cell, count adjacent mines in all 8 directions
• Store the count in the cell's neighborCount property
• This should be called after mine placement (post first-dig)

3. Flood Fill Algorithm Implementation

Create a floodFill or revealCell function with the following logic:

Function signature: floodFill(row, column, board)

Algorithm steps:

1. Boundary validation: Check if coordinates are within board bounds
2. Early exit conditions:
   • If cell is already revealed, return
   • If cell is flagged, return (optional: depends on game rules)
   • If cell is a mine, return (should not happen in normal flow)
3. Reveal current cell: Set isRevealed = true for the current cell
4. Check neighbor count:
   • If neighborCount > 0: Stop recursion (this is a numbered cell)
   • If neighborCount == 0: Continue to step 5
5. Recursive expansion: For each of the 8 neighbors:
   • Calculate neighbor coordinates using offsets: [-1,-1], [-1,0], [-1,1], [0,-1], [0,1], [1,-1], [1,0], [1,1]
   • Recursively call floodFill(neighborRow, neighborCol, board)

Direction offsets:

const directions = [
  [-1, -1], [-1, 0], [-1, 1],
  [0, -1],           [0, 1],
  [1, -1],  [1, 0],  [1, 1]
]

4. Integration with Dig Action

Modify the existing dig/reveal cell handler:

• When user taps a cell in Dig mode
• Validate the cell is not flagged (optional protection)
• If it's the first move, place mines (avoiding the clicked cell)
• Calculate neighbor counts for all cells
• Call floodFill(row, column, board) instead of just revealing the single cell
• Update game state and UI
• Check win/loss conditions

5. Performance Considerations

Stack overflow prevention:

• For very large boards, consider iterative BFS using a queue instead of recursive DFS
• BFS approach: Use a queue data structure, add initial cell, then process neighbors iteratively

Optimization:

• Mark cells as "visited" during traversal to avoid redundant checks
• The isRevealed flag serves this purpose naturally
• Batch UI updates if using a reactive framework to avoid excessive re-renders

6. Algorithm Flow Diagram

sequenceDiagram
    participant User
    participant DigHandler
    participant FloodFill
    participant GameState
    
    User->>DigHandler: Tap cell (row, col)
    DigHandler->>DigHandler: Validate cell (not flagged, not revealed)
    DigHandler->>FloodFill: floodFill(row, col, board)
    
    FloodFill->>FloodFill: Check bounds & early exits
    FloodFill->>GameState: Set cell.isRevealed = true
    
    alt neighborCount > 0
        FloodFill->>DigHandler: Return (stop recursion)
    else neighborCount == 0
        loop For each 8 neighbors
            FloodFill->>FloodFill: floodFill(neighborRow, neighborCol, board)
        end
        FloodFill->>DigHandler: Return (all neighbors processed)
    end
    
    DigHandler->>GameState: Update board state
    DigHandler->>User: Render revealed cells

Loading

7. Edge Cases to Handle

• First move safety: Ensure mines are placed after first dig, so flood fill never hits a mine
• Flagged cells: Decide whether flood fill should skip flagged cells (recommended: yes)
• Board boundaries: Validate coordinates before accessing cells
• Already revealed cells: Skip to prevent infinite loops
• Single zero cell: Should still reveal itself even if no expansion occurs
• Chord interaction: Ensure flood fill works correctly when triggered by chord action

8. Testing Scenarios

Verify the implementation with these test cases:

• Reveal a zero cell surrounded by other zeros (should expand widely)
• Reveal a zero cell adjacent to numbered cells (should stop at numbers)
• Reveal a zero cell in a corner (boundary handling)
• Reveal a zero cell next to flagged cells (should respect flags)
• Reveal a numbered cell (should not trigger flood fill)
• Large board with many connected zeros (performance test)

9. Alternative: BFS Implementation

If stack overflow is a concern for large boards, implement using BFS:

Algorithm:

1. Create a queue and add the initial cell
2. While queue is not empty:
   • Dequeue a cell
   • If already revealed or invalid, skip
   • Reveal the cell
   • If neighborCount == 0, enqueue all 8 neighbors
3. Continue until queue is empty

This iterative approach avoids deep recursion but requires managing a queue data structure.

Import In IDE

🤖 Prompt for AI Agents

## Observations

The repository currently contains only documentation files (`file:README.md` and `file:LICENSE`). No game logic has been implemented yet. The README describes a mobile-first Minesweeper game with classic rules, including flood fill behavior when digging a cell with 0 adjacent mines. The tech stack is not yet determined, with options including React Native, Flutter, or native Swift/Kotlin.

## Approach

The flood fill algorithm will use a recursive approach (DFS preferred for simplicity) to automatically reveal all connected cells when a zero-neighbor cell is revealed. The implementation will traverse the 8-directional neighbors, revealing cells recursively until hitting cells with neighbor counts greater than zero or board boundaries. This approach aligns with classic Minesweeper behavior and provides the best user experience.

## Implementation Steps

### 1. Core Game State Structure

Define the game board data structure to track:
- **Cell state**: Each cell needs properties for:
  - `isMine` (boolean)
  - `isRevealed` (boolean)
  - `isFlagged` (boolean)
  - `neighborCount` (integer 0-8)
  - `row` and `column` coordinates

### 2. Neighbor Count Calculation

Before implementing flood fill, ensure a function exists to calculate neighbor counts:
- For each non-mine cell, count adjacent mines in all 8 directions
- Store the count in the cell's `neighborCount` property
- This should be called after mine placement (post first-dig)

### 3. Flood Fill Algorithm Implementation

Create a `floodFill` or `revealCell` function with the following logic:

**Function signature**: `floodFill(row, column, board)`

**Algorithm steps**:

1. **Boundary validation**: Check if coordinates are within board bounds
2. **Early exit conditions**:
   - If cell is already revealed, return
   - If cell is flagged, return (optional: depends on game rules)
   - If cell is a mine, return (should not happen in normal flow)
3. **Reveal current cell**: Set `isRevealed = true` for the current cell
4. **Check neighbor count**:
   - If `neighborCount > 0`: Stop recursion (this is a numbered cell)
   - If `neighborCount == 0`: Continue to step 5
5. **Recursive expansion**: For each of the 8 neighbors:
   - Calculate neighbor coordinates using offsets: `[-1,-1], [-1,0], [-1,1], [0,-1], [0,1], [1,-1], [1,0], [1,1]`
   - Recursively call `floodFill(neighborRow, neighborCol, board)`

**Direction offsets**:
```
const directions = [
  [-1, -1], [-1, 0], [-1, 1],
  [0, -1],           [0, 1],
  [1, -1],  [1, 0],  [1, 1]
]
```

### 4. Integration with Dig Action

Modify the existing dig/reveal cell handler:
- When user taps a cell in Dig mode
- Validate the cell is not flagged (optional protection)
- If it's the first move, place mines (avoiding the clicked cell)
- Calculate neighbor counts for all cells
- Call `floodFill(row, column, board)` instead of just revealing the single cell
- Update game state and UI
- Check win/loss conditions

### 5. Performance Considerations

**Stack overflow prevention**:
- For very large boards, consider iterative BFS using a queue instead of recursive DFS
- BFS approach: Use a queue data structure, add initial cell, then process neighbors iteratively

**Optimization**:
- Mark cells as "visited" during traversal to avoid redundant checks
- The `isRevealed` flag serves this purpose naturally
- Batch UI updates if using a reactive framework to avoid excessive re-renders

### 6. Algorithm Flow Diagram

```mermaid
sequenceDiagram
    participant User
    participant DigHandler
    participant FloodFill
    participant GameState
    
    User->>DigHandler: Tap cell (row, col)
    DigHandler->>DigHandler: Validate cell (not flagged, not revealed)
    DigHandler->>FloodFill: floodFill(row, col, board)
    
    FloodFill->>FloodFill: Check bounds & early exits
    FloodFill->>GameState: Set cell.isRevealed = true
    
    alt neighborCount > 0
        FloodFill->>DigHandler: Return (stop recursion)
    else neighborCount == 0
        loop For each 8 neighbors
            FloodFill->>FloodFill: floodFill(neighborRow, neighborCol, board)
        end
        FloodFill->>DigHandler: Return (all neighbors processed)
    end
    
    DigHandler->>GameState: Update board state
    DigHandler->>User: Render revealed cells
```

### 7. Edge Cases to Handle

- **First move safety**: Ensure mines are placed after first dig, so flood fill never hits a mine
- **Flagged cells**: Decide whether flood fill should skip flagged cells (recommended: yes)
- **Board boundaries**: Validate coordinates before accessing cells
- **Already revealed cells**: Skip to prevent infinite loops
- **Single zero cell**: Should still reveal itself even if no expansion occurs
- **Chord interaction**: Ensure flood fill works correctly when triggered by chord action

### 8. Testing Scenarios

Verify the implementation with these test cases:
- Reveal a zero cell surrounded by other zeros (should expand widely)
- Reveal a zero cell adjacent to numbered cells (should stop at numbers)
- Reveal a zero cell in a corner (boundary handling)
- Reveal a zero cell next to flagged cells (should respect flags)
- Reveal a numbered cell (should not trigger flood fill)
- Large board with many connected zeros (performance test)

### 9. Alternative: BFS Implementation

If stack overflow is a concern for large boards, implement using BFS:

**Algorithm**:
1. Create a queue and add the initial cell
2. While queue is not empty:
   - Dequeue a cell
   - If already revealed or invalid, skip
   - Reveal the cell
   - If `neighborCount == 0`, enqueue all 8 neighbors
3. Continue until queue is empty

This iterative approach avoids deep recursion but requires managing a queue data structure.

---

Execution Information

Branch: main
Commit: 8a8f15a

---

💡 Tips

Supported Commands (Inside Comments)

• Use @traycerai generate to iterate on the previous version of the implementation plan.

Supported Commands (Inside Description)

• Add @traycerai ignore anywhere in the ticket description to prevent this ticket from being processed.
• Add @traycerai branch:<branch-name> anywhere in the ticket description to specify the target branch for the implementation plan.

Community

• Join our Discord Community to get help, request features, and share feedback.
• Follow us on X/Twitter for updates and announcements.