Skip to content

hhow09/minesweeper

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

50 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Minesweeper

Implement the classic Windows game Minesweeper with React.

Live Demo

Rules

  1. Clicking a mine ends the game.
  2. Clicking a square with an adjacent mine clears that square and shows the number of mines touching it.
  3. Clicking a square with no adjacent mine clears that square and clicks all adjacent squares.
  4. The first click will never be a mine.
  5. It will clear the map and place numbers on the grid.
  6. The numbers reflect the number of mines touching a square.

How to Play

  1. Open Live Demo
  2. Adjust Board Config
  3. Click Start
  4. Left Click to open a cell
  5. Right Click to flag a cell (suspicious mine)

Documentation

Basic Structure

Config

  • Board Width: how many columns of a board
  • Board Height: how many rows of a board
  • Bomb Probability: the probability of whether a cell is a mine
  • Show Log: show the log of function execution in Devtool console panel

Board

  • Purpose: a component maintaining the state of game.
  • Lifecycle: uncontrolled component, remount on each round.
  • State
    • boardState: 2D Array of cellState, recording the current board status.
      • cellState: Object type, basic unit of boardState, recording the cell status
      DEFAULT_CELL_STATE = {
        opened: false,
        isBomb: false,
        adjBombNum: 0,
        flagged: false,
      };
    • bombCount: number type, recording the mine(bomb) number.
    • openedCount: number type, recording the opened cell number.

Cell

  • Purpose: a direct visual representation of boardState.
  • Lifecycle: controlled component, re-render on props change
  • State: stateless component

Process

1. Start a game

2. Prepare Board

prepare Board

2-1. Create Board Matrix

  • Generate 2D array of board state based on Board Width and Board Height.
  • Each element contains a least basic properties of a cell: opened, isBomb, adjBombNum and flagged.

2-2. Place Bombs

iterate through every cell of board state and performs following actions respectively.

  1. randomly set isBomb to true based on Bomb Probability.
  2. if set bomb, update adjBombNum of adjacent cells.

3. Click A Cell

Click A Cell

Right Click

Flag / Unflag a cell

Left Click

  • Performs setState only once.
  • The corresponding new state is generated by pipeline of pure function: handleFirstBomb, openCell, openAdjacentSafeCells, openBomb, doSideEffect, getState in helper.js.
    • handleFirstBomb: Given a boardState and cell location, modify the cell to normal cell and update adjBombNum of adjacent cells.
    • openAdjacentSafeCells: Given a boardState and cell location, Using Depth-First-Search get all adjacent cells of adjBombNum===0, then set these cell state opened=true.
    • openCell: Given a boardState and cell location, set the given cell state opened=true
    • openBomb: Given a boardState and cell location, set the given cell state opened=true & background="red"
    • doSideEffect: Use the information of previous function, do something then return as input. Here use to get count of openAdjacentSafeCells.
    • getState: return boardState
Condition: First Click && is mine && adjacentMines==0

First Click && is mine && adjacentMines==0

Condition: First Click && is mine && adjacentMines>0

First Click && is mine && adjacentMines>0

Condition: Normal cell && adjacentMines==0

Normal cell && adjacentMines==0

Condition: Normal cell && adjacentMines>0

Normal cell && adjacentMines>0

Condition: Not first Click && is mine

Not first Click && is mine

4. Check Board Status

check board status

  • Win condition

    board width * board height - bombCount === opened count
    
  • Lose condition:

    clicked a bomb && not first step
    

Refactor Log

I have tried several ways of handleClickCell for updating boardState (list in chronological order)

  1. Multiple steps of setState (not work)

    Since I maintain the boardState with useState, the first and naive implementation of handleClickCell is performing multiple steps of setState (ex. handleFirstBomb, openAdjacentSafeCells...). It did not worked because each step relies on the result of previous step and setState of React does not work synchronously.

  2. Single setState with pipeline of pure functions (commits after: refactor: functions into pure function)

    Instead of multiple setState, I refactored handleClickCell into single setState function with pipeline of pure functions executed inside updater function of setState. It is the first working version.

  3. Performance Optimization: State management with useReducer (commits after refactor: useReducer)

    Since render time increase as board size grows. I thought about the native characteristics of React functional component, the Re-render of each Cell happens whenever boardState change, even for the unchanged cells. Unnecessary re-render can slow down the re-render process. React provide useCallback hook and memo HOC for performance optimization. I expected performance optimization by reducing the unnecessary re-render.

    To utilize memo HOC, the goal here is to distinguish and compare if the props of Cell unchanged.

    The primitive type of props (ex. isBomb: boolean, adjBombNum: number) can be directly compared using equal operator. The trickiest of the part is handleClickCell because function recreate whenever state update and it use boardState directly, which means it must be recreate to get the latest boardState on each re-render.

    dispatch won't change between re-renders (reference)

    In order to remove the dependency of boardState inside handleClickCell. I replaced the useState with useReducer and perform state change inside reducer. In that way the handleClickCell only depends on static dispatch and actions, which means all the onClick of Cell props is essentially same and does not change on re-render. Then I can easily memoize the same reference of it with useCallback hook and wrap Cell with memo HOC for preventing unnecessary re-render of Cell.

    Result

    After the refactoring, I inspected the performance with Chrome devtools. I found out that performance was not improved and the bottleneck actually lies in unstable_runWithPriority of React scheduler, not the render process of Cell. The Cell itself maybe too simple to affect the performance. I should have noticed that before refactoring!

    It would be interesting to compare React project with other examples made with pure javascript (without framework). For example: Hedronium/minesweeper, it directly manipulate DOM tree. Only with rough comparison, under the same Board configuration, performance does not have significant difference compared to this project.

Limitation When scaling up Board

Recursion and Maximum call stack exceed

When bombProbability is low (ex.0.01) , e.g. lots of safe cells, the recursive method of findAdjacentSafeCells is prone to Maximum call stack size exceeded error. Common technique to prevent recursion from call stack size exceed is to push recursion into macro task using setTimeout. Since it is called inside setState, which should be synchronous and pure, setTimeout does not work here.

Solution

To solve the Maximum call stack exceed error encountered above, I refactored the recursion method into iterative BFS.

About

No description, website, or topics provided.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published