Frenzy.js - the saga of flood-fill

It may surprise you to know that yes, I am back working on Frenzy.js after a multi-year hiatus. It's a bit surreal working on an "old-skool" (pre-hooks) React app but the end is actually in sight. As of September 2023 I have (by my reckoning) about 80% of the game done;

• Basic geometry (it's all scaled 2x)
• Levels with increasing numbers of Leptons with increasing speed
• Reliable collision detection
• High-score table that persists to a cookie
• Mostly-reliable calculation of the area to be filled
• Accurate emulation of the game state, particularly when the game "pauses"

The big-ticket items I still need to complete are:

• Implement "chasers" on higher levels
• Fine-tune the filled-area calculation (it still gets it wrong sometimes)
• Animated flood-fill
• Player-start, player-death and Lepton-death animations
• (unsure) Sound.

It all comes flooding back

To remind you (if you were an 80s Acorn kid) or (far more likely) educate you on what I mean by "flood-fill", here's Frenzy doing its thing in an emulator; I've just completed drawing the long vertical line, and now the game is flood-filling the smaller area:

I wanted to replicate this distinctive style of flood-fill exactly in my browser-based version, and it's been quite the labour of love. My first attempt (that actually worked there were many iterations that did not) was so comically slow that I almost gave up on the whole idea. Then I took a concrete pill and decided that if I couldn't get a multiple-GHz multi-cored MONSTER of a machine to replicate a single-cored 2MHz (optimistically) 8-bit grot-box from the early 1980s, I may as well just give up...

The basic concept for this is:

Given a polygonal area A that needs to be flood-filled;

Determine bottom-rightmost inner point P within A.
The "frontier pixels" is now the array [P]
On each game update "tick":
  Expand each of the "frontier pixels" to the N,S,E and W; but
    Discard an expansion if it hits a boundary of A
    Also discard it if the pixel has already been filled
  The new "frontier pixels" is all the undiscarded pixels 
Stop when the "frontier pixels" array is empty

I got this to be pretty efficient using a bit-field "sparse array" to quickly check for already-filled pixels. In the browser, I could perform the per-tick operations in less than 0.1 milliseconds for any size of A. Not too surprising given the entire game area is only 240x180 pixels, and the maximum possible polygonal area could only ever be half that big: 21,600 pixels.

The problem now became efficiently shifting the big pile'o'filled-pixels from the algorithm onto the HTML5 canvas that is the main gameplay area. I'm using the excellent React Konva library as a nice abstraction over the canvas, but the principal problem is that a canvas doesn't expose per-pixel operations in its API, and nor does Konva. The Konva team has done an admirable job making their code as performant as possible, but my first cut (instantiating a pile of tiny 1x1 Rects on each tick) simply couldn't cope once the number of pixels got significant:

This has led me down a quite-interesting rabbit-hole at the intersection of HTML5 Canvas, React, React-Konva, and general "performance" stuff which is familiar-yet-different. There's an interesting benchmark set up for this, and the results are all over the shop depending on browser and platform. Mobile results are predictably terrible but I'm deliberately not targeting them. This was a game for a "desktop" (before we called them that) and it needs keyboard input. I contemplated some kind of gestural control but it's just not good enough I think, so I'd rather omit it.

What I need to do, is find a way to automagically go from a big dumb pile of individual filled pixels into a suitable collection of optimally-shaped polygons, implemented as Konva Lines.

The baseline

In code, what I first naïvely had was:

type Point = [number, number]

// get the latest flood fill result as array of points
const filledPixels:Array<Point> = toPointArray(sparseMap);

// Simplified a little - we use some extra options
// on Rect for performance...
return filledPixels.map((fp) => 
  <Rect x={fp[0]} 
        y={fp[1]}
        width={1}
        height={1}
        lineCap="square"
        fillColor="red"
  />
);

With the above code, the worst-case render time while filling the worst-case shape (a box 120x180px) was 123ms. Unacceptable. What I want is:

// Konva just wants a flat list of x1,y1,x2,y2,x3,y3
type Poly = Array<number>;

// get the latest flood fill result as array of polys
const polys:Array<number> = toOptimalPolyArray(sparseMap);

// far-fewer, much-larger polygons
return polys.map((poly) => 
  <Line points={poly} 
        lineCap="square"
        fillColor="red"
        closed
  />
);

So how the hell do I write toOptimalPolyArray()?

Optimisation step 1: RLE FTW

My Googling for "pixel-to-polygon" and "pixel vectorisation" failed me, so I just went from first principles and tried a Run-Length-Encoding on each line of the area to be filled. As a first cut, this should dramatically reduce the number of Konva objects required. Here's the worst-case render time while filling the worst-case shape (a box 120x180px): 4.4ms

Optimisation step 2: Boxy, but good

I'd consider this to be a kind of half-vectorisation. Each row of the area is optimally vectorised into a line with a start and end point. The next step would be to iterate over the lines, and simply merge lines that are "stacked" directly on top of each other. Given the nature of the shapes being filled is typically highly rectilinear, this felt like it would "win" quite often. Worst-case render time now became: 1.9ms

Optimisation step 3: Know your enemy

I felt there was still one more optimisation possible, and that is to exploit the fact that the game always picks the bottom-right-hand corner in which to start filling. Thus there is a very heavy bias towards the fill at any instant looking something like this:

----------------
|              |
|              |
|             P|
|            LL|
|           LLL|
|          LLLL|
|         LLLLL|
|        LLLLLL|
|       LLLLLLL|
|      LLLLLLLL|
|     LLLLLLLLL|
|    LLLLLLLLLL|
|   LLLLLLLLLLL|
|  LLLLLLLLLLLL|
| LLLLLLLLLLLLL|
|SSSSSSSSSSSSSS|
|SSSSSSSSSSSSSS|
|SSSSSSSSSSSSSS|
----------------

where

• P is an unoptimised pixel
• L is a part line, that can be fairly efficiently represented by my "half-vectorisation", and
• S is an optimal block from the "stacked vectorisation" approach

You can see there are still a large number of lines (the Ls and the P) bogging down the canvas. They all share a common right-hand edge, and then form a perfect right-triangle. I started implementing this change but ended up aborting that code. Worst-case render time is already significantly below the "tick" rate, and the code was getting pretty complex. Okay, it's not optimal optimal, but it's Good Enough. Whew.

Building a retro game with React.js. Part 5 - Fill 'er up

By now I had a good portion of the "player's part" of the game complete. Movement around the game area, drawing lines, detecting intersection with existing lines and preventing illegal movement were all done, using the div-based "drawing" that I was familiar with. But now it was time to draw the filled colour block that results when a closed area has been completed. And I was looking at a wall of complexity that I didn't know how to scale.

The answer was to challenge my own comfort zone. Allow myself to quote, myself:
I could do that with an HTML canvas, but I'm (possibly/probably wrongly) not going to use a canvas. I'm drawing divs dammit!
After all, if ever there was a time and place to learn how to do something completely new, isn't it a personal "fun" project? After a quick scan around the canvas-in-React landscape I settled upon React-konva, which has turned out to be completely awesome for my needs, as evidenced by the amount of code changes actually needed to go from my div-based way of drawing a line to the Konva way:
The old way:

const Line = styled('div')`
  position: absolute;
  border: 1px solid ${FrenzyColors.CYAN};
  box-sizing: border-box;
  padding: 0;
`;

renderLine = (line, lineIndex) => {
  const [top, bottom] = minMax(line[2], line[4]);
  const [left, right] = minMax(line[1], line[3]);
  const height = (bottom - top) + 1;
  const width = (right - left) + 1;
  return <Line key={`line-${lineIndex}`}
                  style={{ top: `${top}px`, 
                           left: `${left}px`,
                           width: `${width}px`,
                           height: `${height}px` }} />;
}

The new way:

import { Line } from 'react-konva';

renderLine = (line, lineIndex) => {
  return (
    <Line
      key={`line-${lineIndex}`}
      points={line.slice(1)}
      stroke={FrenzyColors.CYAN}
      strokeWidth={2}
    />
  );
}

... and the jewel in the crown? Here's how simple it is to draw a closed polygon with the correct fill colour; by total fluke, my "model" for lines and polygons is virtually a one-to-one match with the Konva Line object, making this amazingly straightforward:

renderFilledArea = (filledPolygon) => {
  const { polygonLines, color } = filledPolygon;
  const flatPointsList = polygonLines.reduce((acc, l) => {
    const firstPair = l.slice(1, 3);
    return acc.concat(firstPair);
  }, []);

  return (
    <Line
      points={flatPointsList}
      stroke={FrenzyColors.CYAN}
      strokeWidth={2}
      closed
      fill={color}
    />
  );
}

Time Tracking

Probably at around 20 hours of work now.