Wrote a floodfill visualizer in React

Question

First time using React.

Here is a demo: https://ostralyan.github.io/flood-fill/

Game Component

import React from 'react';
import Board from './Board';
import Options from './Options';
export default class Game extends React.Component {
  constructor(props) {
    super(props);
    this.state = {};
    this.state.widthOfSquare = 10;
    this.state.squaresPerRow = 50;
    this.state.numberOfColors = 3;
    this.state.includeDiagonals = false;

    this.state.colors = this.generateColors(this.state.numberOfColors);
    this.state.squares = this.generateSquares(
      this.state.colors,
      this.state.squaresPerRow,
      this.state.numberOfColors
    );

    this.resetBoard = this.resetBoard.bind(this);
  }

  resetBoard(widthOfSquare, squaresPerRow, numberOfColors, includeDiagonals) {
    const colors = this.generateColors(numberOfColors);

    const state = {
      widthOfSquare,
      squaresPerRow,
      numberOfColors,
      includeDiagonals,
      colors: colors,
      squares: this.generateSquares(colors, squaresPerRow, numberOfColors)
    }

    this.setState(state);
  }

  generateColors(numberOfColors) {
    const colors = [];
    for (let i = 0; i < numberOfColors; i++) {
      colors[i] = '#' + (Math.random() * 0xFFFFFF << 0).toString(16);
    }
    return colors;
  }

  generateSquares(colors, squaresPerRow, numberOfColors) {
    const squares = []
    for(let i = 0; i < squaresPerRow; i++) {
      squares[i] = [];
      for(let j = 0; j < squaresPerRow; j++) {
        squares[i][j] = {
          color: this.getColor(colors, numberOfColors),
          visited: false
        }
      }
    }
    return squares;
  }

  getColor(colors, numberOfColors) {
    const numberBetweenZeroAndFour = Math.floor((Math.random() * numberOfColors));
    return colors[numberBetweenZeroAndFour];
  }

  render() {
    return (
      <div className="game">
        <div className="game-board">
          <Options
            onReset={this.resetBoard}
            widthOfSquare={this.state.widthOfSquare}
            squaresPerRow={this.state.squaresPerRow}
            numberOfColors={this.state.numberOfColors}
            includeDiagonals={this.state.includeDiagonals}
          />
          <Board 
            widthOfSquare={this.state.widthOfSquare}
            squaresPerRow={this.state.squaresPerRow}
            numberOfColors={this.state.numberOfColors}
            includeDiagonals={this.state.includeDiagonals}
            squares={this.state.squares}
            colors={this.state.colors}
          />
        </div>
      </div>
    );
  }
}

Board Component

import React from 'react';
import Square from './Square';

export default class Board extends React.Component {
  constructor(props) {
    super(props);
    this.state = {};
  }

  floodFillRecursive(i, j) {
    const oldColor = this.props.squares[i][j].color;
    const newColor = this.getUniqueRandomColor(oldColor);
    const squares = this.props.squares.slice();

    this.floodFillHelper(squares, i, j, oldColor, newColor);
    this.clearVisisted(squares);
    this.setState({ squares: squares });
  }

  floodFillRecursiveHelper(squares, i, j, oldColor, newColor) {
    // check out of bounds
    if (i < 0 || i > this.props.squaresPerRow - 1) return;
    if (j < 0 || j > this.props.squaresPerRow - 1) return;
    // check if it's visited
    if (squares[i][j].visited) return;
    // Indicate node has been visited
    squares[i][j].visited = true;
    // check if it's same color
    if (squares[i][j].color !== oldColor) return;
    // set the current color to the new color and mark node as visited.
    squares[i][j].color = newColor;
    // recurse through up, down, left, right boxes.
    this.floodFillRecursiveHelper(squares, i + 1, j, oldColor, newColor);
    this.floodFillRecursiveHelper(squares, i - 1, j, oldColor, newColor);
    this.floodFillRecursiveHelper(squares, i, j + 1, oldColor, newColor);
    this.floodFillRecursiveHelper(squares, i, j - 1, oldColor, newColor);

    if (this.props.includeDiagonals) {
      this.floodFillRecursiveHelper(squares, i + 1, j + 1, oldColor, newColor);
      this.floodFillRecursiveHelper(squares, i - 1, j + 1, oldColor, newColor);
      this.floodFillRecursiveHelper(squares, i + 1, j + 1, oldColor, newColor);
      this.floodFillRecursiveHelper(squares, i - 1, j - 1, oldColor, newColor);
    }
  }

  floodFillIterative(i, j) {
    const oldColor = this.props.squares[i][j].color;
    const newColor = this.getUniqueRandomColor(oldColor);
    const squares = this.props.squares.slice();

    const stack = [
      [i, j]
    ];
    while (stack.length) {
      const squareCoordinates = stack.pop();
      let newI = squareCoordinates[0];
      let newJ = squareCoordinates[1];

      if (newI < 0 || newI >= this.props.squaresPerRow) continue;
      if (newJ < 0 || newJ >= this.props.squaresPerRow) continue;
      let nextSquare = squares[newI][newJ];

      if (nextSquare.color !== oldColor) continue;
      if (nextSquare.visited) continue;

      Array.prototype.push.apply(stack, [
        [newI - 1, newJ],
        [newI + 1, newJ],
        [newI, newJ - 1],
        [newI, newJ + 1],
      ]);

      if (this.props.includeDiagonals) {
        Array.prototype.push.apply(stack, [
          [newI - 1, newJ - 1],
          [newI + 1, newJ - 1],
          [newI - 1, newJ + 1],
          [newI + 1, newJ + 1],
        ]);
      }

      nextSquare.visited = true;
      nextSquare.color = newColor;
    }
    this.setState({ squares });
    this.clearVisisted(squares);
  }

  getUniqueRandomColor(color) {
    const numberBetweenZeroAndFour = Math.floor((Math.random() * this.props.numberOfColors));
    if (color === this.props.colors[numberBetweenZeroAndFour]) {
      return this.getUniqueRandomColor(color);
    } else {
      return this.props.colors[numberBetweenZeroAndFour];
    }
  }

  clearVisisted(squares) {
    for (let i = 0; i < squares.length; i++) {
      for (let j = 0; j < squares[i].length; j++) {
        squares[i][j].visited = false;
      }
    }
  }

  renderSquare(i, j) {
    return <Square
      color={this.props.squares[i][j].color}
      onClick={() => this.floodFillIterative(i, j)}
      widthOfSquare={this.props.widthOfSquare}
      key={i + "," + j}
    />;
  }

  createTable() {
    let table = []

    for (let i = 0; i < this.props.squaresPerRow; i++) {
      let children = []
      // Inner loop to create children
      for (let j = 0; j < this.props.squaresPerRow; j++) {
        children.push(this.renderSquare(i, j))
      }
      // Create the parent and add the children
      table.push(<div className="board-row" key={i}>{children}</div>)
    }
    return table
  }

  render() {
    return (
      <div>
        {this.createTable()}
      </div>
    );
  }
}

Options Component

import React from 'react';

export default class Options extends React.Component {
  constructor(props) {
    super(props)
    this.state = {};
    this.state.widthOfSquare = this.props.widthOfSquare
    this.state.squaresPerRow = this.props.squaresPerRow
    this.state.numberOfColors = this.props.numberOfColors
    this.state.includeDiagonals = this.props.includeDiagonals

    this.handleChange = this.handleChange.bind(this);
    this.handleSubmit = this.handleSubmit.bind(this);
  }

  handleChange(event) {
    const target = event.target;
    const value = target.type === 'checkbox' ? target.checked : target.value;
    const name = target.name;

    this.setState({
      [name]: value
    });
  }

  handleSubmit(event) {
    this.props.onReset(
      this.state.widthOfSquare,
      this.state.squaresPerRow,
      this.state.numberOfColors,
      this.state.includeDiagonals,
    );

    event.preventDefault();
  }

  render() {
    return (
      <div>
        <p>
          Instructions: Click on any square.<br></br>
          <a href="https://github.com/ostralyan/flood-fill" target="_blank" rel="noopener noreferrer">Written by Luke Xu.</a>
        </p>
        <form onSubmit={this.handleSubmit}>
        <label>
          Width of square:
          <input type="number" name="widthOfSquare" value={this.state.widthOfSquare} onChange={this.handleChange} />
        </label>
        <br></br>
        <label>
          Squares per row:
          <input type="number" name="squaresPerRow" value={this.state.squaresPerRow} onChange={this.handleChange} />
        </label>
        <br></br>
        <label>
          Number of colors:
          <input type="number" name="numberOfColors" value={this.state.numberOfColors} onChange={this.handleChange} />
        </label>
        <br></br>
        <label>
          Include diagonals:
          <input
            name="includeDiagonals"
            type="checkbox"
            checked={this.state.includeDiagonals}
            onChange={this.handleChange} />
        </label>
        <br></br>
        <input type="submit" value="Reset" />
      </form>
      <br></br>
    </div>
    );
  }
}

Square Component

import React from 'react';

export default class Square extends React.Component {
  constructor(props) {
    super(props);
    this.state = {};
  }

  shouldComponentUpdate(nextProps) {
    if (nextProps.color !== this.props.color) {
      return true;
    }

    return false;
  }

  render() {
    const divStyle = {
      backgroundColor: this.props.color,
      height: this.props.widthOfSquare + "px",
      width: this.props.widthOfSquare + "px",
      lineHeight: this.props.widthOfSquare + "px",
    }
    return (
      <button
        className="square"
        style={divStyle}
        onClick={() => this.props.onClick()}>
      </button>
    );
  }
}

Would love to hear any feedback. Things I'm not sure about. How far up should I lift the state? Pretty much all my state lives at the highest component which kind of doesn't make sense to me. Imagine if this was a super large app then literally all my state would just sit in the Game Component. I guess that might be where redux comes in?

Community · Accepted Answer · 2020-06-10 13:24:26Z

FloodFill memory hog

Using a library should reduce your source code size and create a higher performance app. If this is not the case then you should not be using the library.

Using react to hold the pixel state is beyond ludicrous. Just for a 50 by 50 square you create 2500 elements, and the same number of Javascript objects, and more under the hood, plus all the supporting code to hold and render pixels.

A typical image that you would want to fill is in the 1024 by 1024+ size. Most devices would have a hard time creating 1 million unique elements, and thats a low res image.

The fill algorithm

Forget the recursive fill, for anything but a small image there is a high probability that you will overflow the call stack. Also the recursion captures the function state meaning a large memory hit for each pixel you branch at.

The iterative fill is better but you are pushing to the stack the wrong way.

You push all neighboring pixels and check if they are valid when you pop them. This means that the stack grows a lot larger than it should.

Rather you should push only pixels that can be filled to the stack, doing the test before you push to the stack, reducing max stack size and the number of times you loop the fill function.

Holding state

The only state you need to hold are the options, the pixel buffer, and the color set. That is better handled with simple javascript object and a typedArray (in the form of a ImageData object). A canvas can hold the pixels. Two functions to handle the options (read and write), a reset function and a fill function. The state is not at all complex and the UI very simple, I can not imagine why you wanted to use react to implement it?

My opinion

You need to know when to use a high level UI library and when not to. The flood fill is a definite case of not. You could have just done the UI using react but the pixel data load is in the millions and not what react is designed to do.

Example

The example look identical to your demo, but is much much quicker. It uses a canvas to display the pixels, and keeps the pixel state in a ImageData array that uses 4 bytes per pixel (rather than an HTML element and an JS object)

It only implements the iterative flood fill using your method. Rather than push all neighboring pixels to the stack it check if pixels can be pained before pushing to the stack. Also an array of pixels is actually a 1D array so it stores pixel coordinates as a single index rather than an array of coordinates, further saving space.

I did not create a recursive fill as it will crash for large images and its memory growth per pixel is not worth the reduction in code size.

The example starts with a 500*500px bitmap that your app could not handle (well I gave up waiting for it to create the page), By not using react I got a reduction in source code complexity and runtime complexity and memory use.

;(()=>{
    function setupUI(opts) {
        function updateUI() {
            widthOfSquareEl.value = opts.pixelSize;
            squaresPerRowEl.value = opts.width;
            numberOfColorsEl.value = opts.numColors;
            includeDiagonalsEl.checked = opts.diagonals;
        }
        
        function getOptionsFromUI() {
            opts.pixelSize = Number(widthOfSquareEl.value);
            opts.width = Number(squaresPerRowEl.value);
            opts.numColors = Number(numberOfColorsEl.value);
            opts.diagonals = includeDiagonalsEl.checked;
        }
        
        resetEl.addEventListener("click", opts.reset); 
        widthOfSquareEl.addEventListener("change", getOptionsFromUI); 
        squaresPerRowEl.addEventListener("change", getOptionsFromUI); 
        numberOfColorsEl.addEventListener("change", getOptionsFromUI); 
        includeDiagonalsEl.addEventListener("change", getOptionsFromUI); 
        
        canvas.addEventListener("click", event => {
            opts.fill(
                event.offsetX / opts.pixelSize | 0, 
                event.offsetY / opts.pixelSize | 0
            );
        });
        
        updateUI();
        opts.reset();
    }
    
    const options = {
        pixelSize: 1,
        width: 500,
        numColors: 3,
        diagonals: false,
        colors : [],
        ctx : canvas.getContext("2d"),
        randomColor(color) {
            var rand = Math.random() * options.colors.length | 0;
            if((options.colors[rand] | 0) === (color | 0)) { 
                rand = (rand + 1) % options.colors.length;
            }
            return options.colors[rand];
        },
        reset,
        fill,
    };
    
    setupUI(options);
    
    function reset(){
        options.colors.length = 0;
        for (let i = 0; i < options.numColors; i++) { 
            options.colors[i] = (Math.random() * 0xFFFFFF | 0) | 0xFF000000;
        }
        options.ctx.imageSmoothingEnabled = false
        const width = canvas.height = canvas.width = options.width;
        canvas.style.height = canvas.style.width = width * options.pixelSize + "px";   
        options.imgData = options.ctx.getImageData(0, 0, width, width);
        const dat32 = new Uint32Array(options.imgData.data.buffer);
        var i = dat32.length;
        while (i--) { dat32[i] = options.colors[Math.random() * options.numColors | 0] }
        options.ctx.putImageData(options.imgData,0,0);
    }
    
    function fill(x, y) {
        const w = options.ctx.canvas.width;
        const imgData = options.imgData;
        const dat32 = new Uint32Array(imgData.data.buffer);
        const fillColor = dat32[x + y * w];
        const color = options.randomColor(fillColor);
        const canPaint = (idx, x) => {
            if (idx < 0 || idx >= dat32.length || x < 0 || x >= w) { return false }
            return dat32[idx] === fillColor;
        }    
        const stack = [x + y * w];
        while (stack.length) {
            const idx = stack.pop();
            dat32[idx] = color;
            x = idx % w;
            canPaint(idx - 1, x - 1) && (stack.push(idx - 1));
            canPaint(idx + 1, x + 1) && (stack.push(idx + 1));
            canPaint(idx - w, x) && (stack.push(idx - w));
            canPaint(idx + w, x) && (stack.push(idx + w));
            if (options.diagonals) {
                canPaint(idx - w - 1, x - 1) && (stack.push(idx - w - 1));
                canPaint(idx - w + 1, x + 1) && (stack.push(idx - w + 1));
                canPaint(idx + w - 1, x - 1) && (stack.push(idx + w - 1));
                canPaint(idx + w + 1, x + 1) && (stack.push(idx + w + 1));
            }
        }
        options.ctx.putImageData(imgData, 0, 0);
    }
})();

#canvas {
  image-rendering: pixelated;
}

<div>
  <p> Instructions: Click on any square. </p>

  <label>
    Width of square:
    <input type="number" id="widthOfSquareEl" />
  </label>
  <br>
  <label>
    Squares per row:
    <input type="number" id="squaresPerRowEl" />
  </label>
  <br>
  <label>
    Number of colors:
    <input type="number" id="numberOfColorsEl" />
  </label>
  <br>
  <label>
    Include diagonals:
    <input id="includeDiagonalsEl" type="checkbox" />
  </label>
  <br>
  <input id="resetEl" type="button" value="Reset" />

  <br>
</div>
<canvas id="canvas"></canvas>

Yeah you're totally right. I tried to do 500x500 and it was soo slow. That's like a quarter of a million components being rendered lol — Luke Xu
– Luke Xu, Commented Oct 31, 2018 at 13:57
Didn't see you update with a demo.... that looks so awesome. Thanks! — Luke Xu
– Luke Xu, Commented Nov 14, 2018 at 4:39

Stack Exchange Network

Wrote a floodfill visualizer in React

1 Answer 1

FloodFill memory hog

The fill algorithm

Holding state

My opinion

Example

You must log in to answer this question.

Hot Network Questions

Wrote a floodfill visualizer in React

1 Answer 1

FloodFill memory hog

The fill algorithm

Holding state

My opinion

Example

You must log in to answer this question.

Related

Hot Network Questions