Literate Programming 5 - A Javascript Game.
Prev: WEB 4 Top: WEB 0 Next: WEB 6 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:
=
=
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.]
@=
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)
@
}
@ 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.
@=
let CANVAS_WIDTH = 500
let CANVAS_HEIGHT = 500
let ONE_TURN = Math.PI * 2
@=
canvas.fillStyle="#008"
canvas.rect(0,0,CANVAS_WIDTH,CANVAS_HEIGHT);
canvas.fill();
@=
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.
@=
@
@
@
@*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.
@=
setInterval(do_frame,30);
function do_frame()
{
@
@
}
@ For the animation to be visible, our points will need to be moving, so add a random initial velocity to each point.
@=
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.
@=
for(let i in VoronoiPoints) {
let point = VoronoiPoints[i]
point.x += point.vel.x;
point.y += point.vel.y;
@
}
@ I also want the points to be different colors.
@=
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.
@=
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.
@=
function draw_points(canvas) {
@
}
@=
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.
@=
let bestPoint = VoronoiPoints[0];
let bestDistSq = squared(bestPoint.x-x) + squared(bestPoint.y-y)
// + squared(bestPoint.z-RENDER_Z);
@=
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(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.
@=
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.
@=
@
const CELL_SIZE = 4;
for(let x = 0; x < CANVAS_WIDTH; x += CELL_SIZE) {
for(let y = 0; y < CANVAS_HEIGHT; y += CELL_SIZE) {
@
@
@
@
}
}
@
@=
canvas.fillStyle=bestPoint.color;
canvas.fillRect(x, y, CELL_SIZE, CELL_SIZE);
@ Add our Voronoi Grid draw code to the setInterval do_frame callback.
@=
{
canvas = document.getElementById("canvas4").getContext("2d")
const z = 200;
if(canvas.__is_visible != false) {
@
}
}
@=
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.
@=
@
const CELL_SIZE = 20;
const SMALL_CELL_SIZE = 2;
@
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;
@
}
}
@
@ 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.
@=
@
@
@=
@
@
@
@ 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.
@=
function distance_to_point(x, y, point) {
return squared(point.x-x) + squared(point.y-y)// + squared(point.z-RENDER_Z)
}
@=
point => [
distance_to_point(cx, cy, point),
point ]
@=
let pointsWithPrecalculatedDistances = VoronoiPoints.map(
@
)
@=
let sortedPoints = pointsWithPrecalculatedDistances.sort((a,b) => a[0] - b[0]);
@=
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.
=
for(let xx = 0; xx < CELL_SIZE; xx += SMALL_CELL_SIZE) {
for(let yy = 0; yy < CELL_SIZE; yy += SMALL_CELL_SIZE) {
@
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.
@=
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.
@=
{
canvas = document.getElementById("canvas5").getContext("2d")
if(canvas.__is_visible != false) {
@
}
}
@
@*Performance Improvements. I'm still not happy with the performance, so I'm adding a performance tracker to the displays.
@=
const startTime = Date.now()
@=
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.
@=
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.
@=
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;;
}
@=
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.
@=
point.colorUint = color_uint_from_string(point.color)
@=
@
@
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);
@
@ Add our optimized Voronoi grid draw code to the |setInterval| |do_frame| callback.
@=
{
canvas = document.getElementById("canvas6").getContext("2d")
if(canvas.__is_visible != false) {
@
}
}
@ 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.
@
@=
@
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);
@
@ Add our optimized Voronoi grid draw code to the |setInterval| |do_frame| callback.
@=
{
canvas = document.getElementById("canvas7").getContext("2d")
if(canvas.__is_visible != false) {
@
}
}
@
@ This is comparable to the chunky version, but at 4 times the precision. A win, but not an incredible one.
@p
@
@
@
@
canvas = document.getElementById("canvas2").getContext("2d")
@
@
@
@
@
@>
@*__index__.
@
Prev: WEB 4 Top: WEB 0 Next: WEB 6
@*Getting Started. We're going to need an HTML |canvas| element and to render some stuff into it.
@