Literate Programming 5 - A Javascript Game.

Prev:WEB 4 Top:WEB 0 Next:WEB 6

Prologue

Jon Breuer - September 13, 2024.

I think my implementation of WEB has enough features for some serious use cases and I'm tired of chasing the bootstrapping oroboros with each version of this tool. With this article, I'm going to show how to build a little Javascript game.

This is the source *.WEB file, and this is the generated HTML.

Table of Contents:

Inspiration

I've recently seen some cool Voronoi cell (wiki) games and videos and thought it would be fun to build one.

Here's a picture from Wikipedia:

Getting Started

We're going to need an HTML canvas element and to render some stuff into it.

Starting HTML

    <canvas width="100" height="100" style="border:1px solid black"></canvas>
    <script src="literate_programming_5.js"></script>

We'll be using Javascript to draw into it. Grab the drawable 2d context on the canvas and fill a rect.

Basic drawing on canvas

    let canvas = document.getElementById("canvas1").getContext("2d")
    canvas.fillStyle="blue"
    canvas.rect(10,10,75,57);
    canvas.fill();

Points

Now let's create some points on the canvas. For some purposes I'll treat these as 2D lying in the plane of the canvas/screen and for later uses I'll treat them in 3D extending above and below the screen. [3D makes this all around slower. I needed more points to saturate the cube instead of the plane. There's an interesting effect of some cells appearing and disappearing, but it's not significant.]

Point List Definition

    let VoronoiPoints = []
    for(let i = 0; i < 20; i++) {
        let point = { 
            x: Math.random() * CANVAS_WIDTH, 
            y: Math.random() * CANVAS_HEIGHT,
            //z: Math.random() * CANVAS_HEIGHT, 
            } 
        VoronoiPoints.push( point)
        Future Point Initialization
    }

Store off the size of the screen so I don't have to interrogate the canvas every time I draw. I've also gotten fond of working in TURNS of a circle instead of 2 * PI radians or 1 Taus.

Useful Constants

    let CANVAS_WIDTH = 500
    let CANVAS_HEIGHT = 500
    let ONE_TURN = Math.PI * 2

Fill the background of the canvas

    canvas.fillStyle="#008"
    canvas.rect(0,0,CANVAS_WIDTH,CANVAS_HEIGHT);
    canvas.fill();

Plot each point as a little filled circle

    for(let i in VoronoiPoints) {
        let point = VoronoiPoints[i]
        
        canvas.beginPath();
        canvas.fillStyle = point.color || "#800"
        canvas.moveTo(point.x, point.y);
        canvas.arc(point.x, point.y, 5, 0, ONE_TURN);
        canvas.fill();
    }

And tie it all together.

Draw Points As Basic Circles

    Fill the background of the canvas
    Plot each point as a little filled circle

Animated Points

To create an animation, we'll need to redraw our canvas repeatedly as we move the points. I default to setInterval( ...callback..., 30), but requestAnimationFrame(...callback...) is also popular.

Set up a do_frame function to execute 30 times per second.

setInterval(do_frame,30);
function do_frame()
{
    Move points around
    Draw Points Each Frame
}

For the animation to be visible, our points will need to be moving, so add a random initial velocity to each point.

Future Point Initialization...+

    const POINT_SPEED = 3;
    point.vel = {
        x:Math.random() * POINT_SPEED - POINT_SPEED / 2, 
        y:Math.random() * POINT_SPEED - POINT_SPEED / 2, 
        y:Math.random() * POINT_SPEED - POINT_SPEED / 2, }

And add that velocity to the positions on each frame.

Move points around

    for(let i in VoronoiPoints) {
        let point = VoronoiPoints[i]
        point.x += point.vel.x;
        point.y += point.vel.y;
        
        Keep points on screen
    }

I also want the points to be different colors.

Future Point Initialization...+

    point.color = "#" +
        Math.floor(Math.random()*10) +
        Math.floor(Math.random()*10) +
        Math.floor(Math.random()*10) + ""

If we just let the points move with a given velocity, they'd quickly run off the edges of the canvas. Use the math modulo operation to keep them all between 0 and 500.

Keep points on screen

    point.x = (point.x + CANVAS_WIDTH) % CANVAS_WIDTH;
    point.y = (point.y + CANVAS_HEIGHT) % CANVAS_HEIGHT;

Create a function to draw the points and call that from our callback.

Define Draw Points Function

function draw_points(canvas) {
    Draw Points As Basic Circles
}

Draw Points Each Frame

    canvas = document.getElementById("canvas3").getContext("2d")
    if(canvas.__is_visible != false) {
        draw_points(canvas)
    }

Voronoi Grid

Now that we can see where our initial points are, let's generate a Voronoi grid from our points. A Voronoi grid is generated by coloring all the points on the screen with the color of the nearest control point.

At each pixel, find the control point that's the nearest.

Initialize the nearest control point

    let bestPoint = VoronoiPoints[0];
    let bestDistSq = squared(bestPoint.x-x) + squared(bestPoint.y-y)
//    + squared(bestPoint.z-RENDER_Z);

Loop over all the control points, calculating the new distance

    for(let i in VoronoiPoints) {
        let point = VoronoiPoints[i];
        let distSq = squared(point.x-x) + squared(point.y-y) 
        //+ squared(point.z-RENDER_Z)

If the new control point is closer to our pixel than the previous control point, record the new best match.

        if(distSq < bestDistSq) {
            bestDistSq = distSq;
            bestPoint = point;
        }
    }

The control points are floating through 3D space, but we're rendering a slice at a specific Z level.

Useful Constants...+

const RENDER_Z = 200;

Iterate over every point in the canvas. I already know this process can be slow, so I'm skipping over a grid of 4x4 to simplify the calculations.

Voronoi Grid Iteration

    Start Performance Timing

    const CELL_SIZE = 4;
    for(let x = 0; x < CANVAS_WIDTH; x += CELL_SIZE) {
        for(let y = 0; y < CANVAS_HEIGHT; y += CELL_SIZE) {
           
            Initialize the nearest control point
            Loop over all the control points, calculating the new distance
            If the new control point is closer to our pixel than the previous control point, record the new best match.
            
            Draw the grid cell
        }

    }
    
    End Performance Timing

Draw the grid cell

    canvas.fillStyle=bestPoint.color;
    canvas.fillRect(x, y, CELL_SIZE, CELL_SIZE);

Add our Voronoi Grid draw code to the setInterval do_frame callback.

Draw Points Each Frame...+

{
    canvas = document.getElementById("canvas4").getContext("2d")
    const z = 200;
    if(canvas.__is_visible != false) {
        Voronoi Grid Iteration
    }
}

Utility Functions...+

function squared(value) { return value * value; }

Optimized Voronoi Grid

This didn't work as well as I hoped. The intricacy of the Voronoi grid comes from the fine variation of possible control points against pixels.

The outer loop of the optimized form doesn't really change from the previous form.

Draw Voronoi Grid Optimized

    Start Performance Timing
    
    const CELL_SIZE = 20;
    const SMALL_CELL_SIZE = 2;
    
    distance to point helper function
    
    for(let x = 0; x < CANVAS_WIDTH; x += CELL_SIZE) {
        let cx = x + CELL_SIZE / 2;
        for(let y = 0; y < CANVAS_HEIGHT; y += CELL_SIZE) {
            let cy = y + CELL_SIZE / 2;
           
           Attempt to render a chunky pixel more quickly and more accurately.
        }
    }
    
    End Performance Timing

What I'm going to rely on for optimization is that for any chunky area, the list of closest control points doesn't change much, even if the exact closest control point does change pixel by pixel.

Attempt to render a chunky pixel more quickly and more accurately.

    For a cell, calculate the list of nearish control points
    Within a single cell, calculate the actual best point per pixel.

For a cell, calculate the list of nearish control points

    Convert or map the raw points into pairs with the distances pre-calculated so we do not repeat the distance calculations
    Sort the points based on the pre-calculated distances.
    Limit the control points to only the very nearest points.

The pythagorean therom for distance between two points is the square root of (The sum of (The squares of (the distance between points))). It's a game programming trick that when comparing distances, choosing to compare all the distances or all the distances squared doesn't matter because the relative distances still sort the same. So calculate the distance squared to skip the expensive and unneccessary square root function.

distance to point helper function

function distance_to_point(x, y, point) {
    return squared(point.x-x) + squared(point.y-y)// + squared(point.z-RENDER_Z)
}

Calculate the distance from the current pixel cell to the control point and cache it in a pair

point => [
        distance_to_point(cx, cy, point), 
        point ]

Convert or map the raw points into pairs with the distances pre-calculated so we do not repeat the distance calculations

let pointsWithPrecalculatedDistances = VoronoiPoints.map( 
    Calculate the distance from the current pixel cell to the control point and cache it in a pair
)

Sort the points based on the pre-calculated distances.

let sortedPoints = pointsWithPrecalculatedDistances.sort((a,b) => a[0] - b[0]);

Limit the control points to only the very nearest points.

sortedPoints.length = Math.min(20, sortedPoints.length);

Limiting the points too far didn't help. It made everything very chunky because in three dimensions, there are more active points than I think there are.

Within a single cell, calculate the actual best point per pixel.

for(let xx = 0; xx < CELL_SIZE; xx += SMALL_CELL_SIZE) {
    for(let yy = 0; yy < CELL_SIZE; yy += SMALL_CELL_SIZE) {
        Calculate best control point per pixel
        canvas.fillStyle = bestPoint.color;
        canvas.fillRect(x + xx, y + yy, SMALL_CELL_SIZE, SMALL_CELL_SIZE);
    }
}

This is the same code as for the unoptimized Voronoi grid, but now we're checking fewer adjacent control points.

Calculate best control point per pixel

    let bestPoint = sortedPoints[0][1];
    let bestDistSq = distance_to_point(x + xx, y + yy, bestPoint)
    for(let i in sortedPoints) {
        let point = sortedPoints[i][1];
        let distSq = distance_to_point(x + xx, y + yy, point)
        if(distSq < bestDistSq) {
            bestDistSq = distSq;
            bestPoint = point;
        }
    }

Add our optimized Voronoi grid draw code to the setInterval do_frame callback.

Draw Points Each Frame...+

{
    canvas = document.getElementById("canvas5").getContext("2d")
    if(canvas.__is_visible != false) {
    Draw Voronoi Grid Optimized
    }
}

Performance Improvements

I'm still not happy with the performance, so I'm adding a performance tracker to the displays.

Start Performance Timing

    const startTime = Date.now()

End Performance Timing

    const elapsedTime = Date.now().valueOf() - startTime.valueOf();
    const text = "" + elapsedTime + "ms";
    canvas.strokeStyle="black";
    canvas.fillStyle="white";
    canvas.font = "24px arial";

    canvas.fillText(text, 0,CANVAS_HEIGHT);
    canvas.strokeText(text, 0,CANVAS_HEIGHT);

On my PC, the chunky naive renderer runs 30ms and the optimized more detailed version runs 60-70ms. My phone is running at the "optimized" version at 380ms.

I'm going to start tracking which canvas is actually visible and stop processing the ones which aren't. Even if all this is expensive or inefficient, I don't need to process things that aren't visible.

Set up an Itersection Observer to check which canvas elements are visible

const observer = new IntersectionObserver(entries => {
    entries.forEach(canvas => { canvas.__is_visible = canvas.isVisible; }) } );
const allCanvasElements = document.querySelectorAll('canvas');
allCanvasElements.forEach(canvas => observer.observe(canvas));

Per-Pixel Voronoi Grid

The renderer is still too slow. Let's see if rectFill is slow and pixel rendering is faster.

Utility Functions...+

function putPixel(imageData, x, y, colorRGBA) {
    const pixelStart = (x + y * imageData.width) * 4;
    for(let i = 0; i < 4; i++) {
        imageData.data[pixelStart + i] = colorRGBA[i];
    }
    //imageData.data[ + 0] = (colorRGBA & 0xFF0000) >> 16;
    //imageData.data[(x + y * imageData.width) * 4 + 1] = (colorRGBA & 0x00FF00) >> 8;
    //imageData.data[(x + y * imageData.width) * 4 + 2] = colorRGBA & 0x0000FF;
    //imageData.data[(x + y * imageData.width) * 4 + 3] = 255;;
}

Utility Functions...+

function color_uint_from_string(colorString)
{
    if(colorString.length == 4) {
        // "#FDA"
        // 17 = 16 + 1 :: F => FF , 8 => 88 (in hex)
        let r = parseInt(colorString.slice(1,2), 16) * 17
        let g = parseInt(colorString.slice(2,3), 16) * 17
        let b = parseInt(colorString.slice(3,4), 16) * 17
        return [r, g, b, 255];
        //return r << 16 | g << 8 | b;
    } else if(colorString.length == 7) {
        // "#FFDDAA"
        let r = parseInt(colorString.slice(1,3), 16)
        let g = parseInt(colorString.slice(3,5), 16)
        let b = parseInt(colorString.slice(5,7), 16)
        return [r, g, b, 255];
        //return r << 16 | g << 8 | b ;
    } else {
        // ???
        let r = 255
        let g = 0
        let b = 255
        return [r, g, b, 255];
        //return r << 16 | g << 8 | b ;
    }
}

Convert the points to RGBA uint values once.

Future Point Initialization...+

    point.colorUint = color_uint_from_string(point.color)

Draw Voronoi Grid Per Pixel

    Start Performance Timing
    
    distance to point helper function
    
    const imageData = canvas.createImageData(canvas.canvas.width, canvas.canvas.height);
    //const imageData = canvas.getImageData(0, 0, canvas.canvas.width, canvas.canvas.height);
  
    for(let x = 0; x < CANVAS_WIDTH; x++) {
        for(let y = 0; y < CANVAS_HEIGHT; y ++) {
            let bestPoint = VoronoiPoints[0];
            let bestDistSq = distance_to_point(x, y, bestPoint)
            for(let i in VoronoiPoints) {
                let point = VoronoiPoints[i];
                let distSq = distance_to_point(x, y, point)
                if(distSq < bestDistSq) {
                    bestDistSq = distSq;
                    bestPoint = point;
                }
            }
            putPixel(imageData, x, y, bestPoint.colorUint);
            
        }
    }
    canvas.putImageData(imageData, 0, 0);
    
    End Performance Timing

Add our optimized Voronoi grid draw code to the setInterval do_frame callback.

Draw Points Once...+

{
    canvas = document.getElementById("canvas6").getContext("2d")
    if(canvas.__is_visible != false) {
        Draw Voronoi Grid Per Pixel
    }
}

O(Width * Height * NumControlPoints) = O(N^2*M) = 12,500,000 checks, which is 480ms on my PC. Let's experiment with the chunking again.

Draw Voronoi Pixel Optimized

    Start Performance Timing
    
    const CELL_SIZE = 10;
    const SMALL_CELL_SIZE = 1;
    function distance_to_point(x, y, point) {
        return squared(point.x-x) + squared(point.y-y)// + squared(point.z-RENDER_Z)
    }
    
    const imageData = canvas.createImageData(canvas.canvas.width, canvas.canvas.height);
    
    for(let x = 0; x < CANVAS_WIDTH; x += CELL_SIZE) {
        let cx = x + CELL_SIZE / 2;
        for(let y = 0; y < CANVAS_HEIGHT; y += CELL_SIZE) {
            let cy = y + CELL_SIZE / 2;
            let pointsWithPrecalculatedDistances = VoronoiPoints.map( point => [
                distance_to_point(cx, cy, point), 
                point ])
            let sortedPoints = pointsWithPrecalculatedDistances.sort((a,b) => a[0] - b[0]);
            sortedPoints.length = Math.min(5, sortedPoints.length);
            for(let xx = 0; xx < CELL_SIZE; xx += SMALL_CELL_SIZE) {
                for(let yy = 0; yy < CELL_SIZE; yy += SMALL_CELL_SIZE) {
                    let bestPoint = sortedPoints[0][1];
                    let bestDistSq = distance_to_point(x + xx, y + yy, bestPoint)
                    for(let i in sortedPoints) {
                        let point = sortedPoints[i][1];
                        let distSq = distance_to_point(x + xx, y + yy, point)
                        if(distSq < bestDistSq) {
                            bestDistSq = distSq;
                            bestPoint = point;
                        }
                    }
                    for(let xxx = 0; xxx < SMALL_CELL_SIZE; xxx++) {
                        for(let yyy = 0; yyy < SMALL_CELL_SIZE; yyy++) {
                            putPixel(imageData, x + xx + xxx, y + yy + yyy, bestPoint.colorUint);
                        }
                    }
                }
            }
        }
    }
    
    canvas.putImageData(imageData, 0, 0);
    
    End Performance Timing

Add our optimized Voronoi grid draw code to the setInterval do_frame callback.

Draw Points Each Frame...+

{
    canvas = document.getElementById("canvas7").getContext("2d")
    if(canvas.__is_visible != false) {
    Draw Voronoi Pixel Optimized
    }
}

This is comparable to the chunky version, but at 4 times the precision. A win, but not an incredible one.

__main__

    Useful Constants
    Utility Functions
    Basic drawing on canvas
   
    Point List Definition
    canvas = document.getElementById("canvas2").getContext("2d")
    Draw Points As Basic Circles
    
    Define Draw Points Function

    Set up a do_frame function to execute 30 times per second.
    
    Set up an Itersection Observer to check which canvas elements are visible
    
    Draw Points Once

TODO

Index:

Prev:WEB 4 Top:WEB 0 Next:WEB 6