This beautiful essay describes the making of the LS ENGINE and explores its inner workings: how it runs 2D, 3D, and assorted other-D games in a web browser, and how you might make an engine of your own. Assuming, of course, that you have too much free time and an inadequate fear of debugging.
Why would you want to make a game engine? The main reasons are:
For me, it started with Castle Haunt. Just before that, I had made Princess Wants Everything, and the map format, map-to-world routines, and map-display methods were already there, waiting patiently to be reused. Copy and paste worked, of course, but that is for pussies—and for people who enjoy fixing the same bug in seventeen different places.
At that point, it became clear that my real hobby was not making tons of retro games. It was building my own game engine, written predominantly in JavaScript and designed for developing and running web-based retro games. The games, apparently, were merely a side effect.
The first rule of my hobby is to use only my own code; otherwise, what is the point of having a hobby? This rule is, naturally, enforced only as rigidly as remains convenient. Since I am not writing the whole thing in assembly merely to preserve the complete 1980s experience, I have allowed myself a few notable concessions:
id, it offers:
document.getElementById(id);$(`#${id}`);As I hinted earlier, Brendan Eich famously wrote the first version of JavaScript in ten days. He is not a god after all, although ten days remains irritatingly close. Perhaps as a result, JavaScript can occasionally resemble an ugly duckling. We love it nonetheless; we merely subject it to a little corrective surgery.
Accordingly, I committed the unspeakable heresy of adding methods to several native JavaScript objects
and
browser interfaces: Array, Math, String, Set, the
Canvas
API, and several other innocent victims. Respectable software engineering has naturally filed a
complaint.
I add a method only if that name does not already exist, and I use the library solely inside my own
games,
where any resulting catastrophe remains reassuringly proprietary.
My Prototype library also provides a collection of foundational classes—Grid,
Vector, Point, Angle, Area, and assorted
relatives—with either integer-grid or floating-point semantics, in both 2D and 3D variants.
These classes, however, grew out of a 2D worldview in which x and y form the game-world plane, while z represents height. For the 3D engine, I adopted a y-up convention: x runs horizontally, y represents height, and z provides depth. OpenGL itself does not require this particular world-axis arrangement, but it is the convention used by my 3D renderer. Consequently, y and z had to exchange identities. Splendid.
LS_matrix.js acts as an adapter layer between the rest of the 3D engine, my Prototype classes, and glMatrix. An LS matrix object therefore leads a double life: it exposes the familiar Grid- and Vector-style properties used by the engine while also maintaining a flat floating-point array suitable for glMatrix and for upload through WebGL to the shaders. At the boundary, y and z quietly exchange passports. The rest of the engine is spared the paperwork.
ENGINE is the first component to wake up. Its first order of business is to preload
graphics,
audio, GLSL shader source, object definitions, models, and assorted other assets, then prepare
everything for
use by the game. Nothing undermines the majesty of a game engine quite like asking it to draw a sprite
whose
image has not yet arrived.
ENGINE also organises the canvas layers, renders sprites onto them, handles conversions
between
bitmaps and canvases, and provides several flavours of MoveState and Motion
classes,
responsible for—surprise—moving objects.
Then come the various Actor classes, which encapsulate sprite properties and rendering
routines.
Timers live here as well, alongside inventory managers and methods for drawing HTML-like forms onto
canvases.
Once a file grows large enough, apparently, it develops its own gravitational field.
And, naturally, the magnificently global unit vectors used for directions. They are needed everywhere, so everywhere is precisely where they live.
Historically, more specialised functionality was gradually extracted from ENGINE into
separate
modules. This is why it is now a lean, disciplined 5,000 lines.
At that size, ENGINE is less a single-purpose module than the reception desk for the entire
establishment. GAME arrives, announces what it needs and where it needs it, and
ENGINE politely makes the arrangements while pretending that all of this was part of the
original
design.
At a mere 3,000 lines, GRID.js is one of the engine's most essential components. It forms
the next
layer of abstraction above the foundational grid classes, connecting them to motion handlers,
sprite-rendering
routines, and several varieties of collision detection. It also houses pathfinding, including
implementations
of familiar algorithms such as
A*
(A-star)
and
Dijkstra's algorithm.
Apparently, knowing where everything is was not enough; the engine must also know how to get there.
The following method calculates a 2D distance field using the engine's array-backed queue. Because every valid move costs exactly one, this is the unit-weight case of Dijkstra's algorithm and can be solved as breadth-first search. A binary heap is unnecessary here and would mostly contribute paperwork:
calcDistancesBFS_A(start, dungeon, mode = GROUND_MOVE_GRID_EXCLUSION, nodeMap = "nodeMap") {
dungeon.setNodeMap(mode, nodeMap);
let Q = new NodeQ("distance");
dungeon.GA[nodeMap][start.x][start.y].distance = 0;
dungeon.GA[nodeMap][start.x][start.y].goto = new Vector(0, 0);
Q.queueSimple(dungeon.GA[nodeMap][start.x][start.y]);
while (Q.size() > 0) {
let node = Q.dequeue();
for (let D = 0; D < ENGINE.directions.length; D++) {
let x = (node.grid.x + ENGINE.directions[D].x);
let y = (node.grid.y + ENGINE.directions[D].y);
let nextNode = dungeon.GA[nodeMap][x][y];
if (nextNode) {
if (nextNode.distance > node.distance + 1) {
nextNode.distance = node.distance + 1;
nextNode.prev = node.grid;
nextNode.goto = ENGINE.directions[D].mirror();
Q.queueSimple(nextNode);
}
}
}
}
},
One of the central concepts inside GRID.js is the aptly named GridArray. It
wraps a
flat typed array in several helper methods, allowing its contents to be accessed either by linear index
or by
grid coordinates. Each array element represents one cell: a value of zero denotes empty space, while
individual
bits encode properties such as walls, corridors, closed rooms, doors, staircases, flooded terrain, and
whatever
fresh indignity the dungeon invents next.
GridArray, affectionately shortened to GA because three syllables were clearly
excessive, stores the mostly static topology of the dungeon. Mostly static, naturally—a fragile wall can
always
be demolished. Permanence in games is generally just a temporary implementation detail.
Depending on its purpose, a GA can use 8, 16, or 32 bits per cell. This provides
constant-time
access to a cell's flags and suitably cheap occupancy checks for the wall-collision system.
The following method performs A* over a 3D node map, restricting movement to the XY plane unless
fly is enabled. A* does not simply favour whichever node appears closest to the
destination; it
selects the node with the lowest estimated total cost:
f(n) = g(n) + h(n). Here, path supplies g(n),
distance supplies h(n), and setPriority() combines them.
In benchmarks on my own mazes, this array-backed priority queue outperformed my binary-heap implementation. That is not a new theorem of computer science, merely the welcome result of testing the code I actually run.
findPath_AStar_fast(start, finish, path = [0], type = "value", fly = 0, block = []) {
if (GRID.same(start, finish)) return 0;
var Q = new NodeQ("priority");
let NodeMap = this.setNodeMap("AStar", path, type, block);
const DIR = fly > 0.0 ? [...ENGINE.directions3D] : [...ENGINE.directions3D_XY_plane];
NodeMap[start.x][start.y][start.z].distance = start.distance(finish);
NodeMap[start.x][start.y][start.z].path = 0;
NodeMap[start.x][start.y][start.z].setPriority();
Q.queueSimple(NodeMap[start.x][start.y][start.z]);
while (Q.size() > 0) {
let node = Q.dequeue();
for (let D = 0; D < DIR.length; D++) {
let x = (node.grid.x + DIR[D].x);
let y = (node.grid.y + DIR[D].y);
let z = (node.grid.z + DIR[D].z);
let nextNode = NodeMap[x][y][z];
if (nextNode) {
if (nextNode.path > node.path + 1) {
nextNode.path = node.path + 1;
nextNode.prev = node.grid;
nextNode.distance = nextNode.grid.distance(finish);
nextNode.setPriority();
Q.queueSimple(nextNode);
if (nextNode.distance === 0) return NodeMap;
}
}
}
}
return null;
}
What GA is to mostly static cell properties, IndexArray—or IA—is
to
runtime objects. It provides constant-time access to the packed contents of any grid cell, allowing the
engine
to locate moving actors, items, fireplaces, torches, and other objects currently inconveniencing the
dungeon.
A dungeon generally needs only one GA, but it may maintain several IAs. Each
one
covers a related family of object instances that the engine may need to query together. Apparently, even
data
structures eventually form cliques.
Like GA, IA wraps a flat typed array. Each array element corresponds to one
grid cell
and is divided into fixed-width bit banks. Every bank stores a compact object index, with 0
reserved to mean “vacant.” Packing several banks into one element allows a cell to contain references to
multiple objects without allocating a separate array for every coordinate.
Bank width trades index range against maximum occupancy. A 32-bit element can contain four 8-bit banks,
allowing four indices between 1 and 255, or eight 4-bit banks, allowing eight
indices
between 1 and 15. There is no free lunch, merely lunch compressed into bit
fields.
The following method unpacks—or, in the established dialect of the engine, “unrolls”—all non-zero indices from a cell, beginning with the least-significant bank:
unroll(grid) {
const items = [];
if (this.isOutOfBounds(grid)) return items;
const index = this.gridToIndex(grid);
let layerValue = this.map[index];
for (let i = 0; i < this.banks; i++) {
const current = layerValue & this.layerSize;
if (current) items.push(current);
layerValue >>>= this.bankBitWidth;
}
return items;
}
IndexArrays are organised into a higher abstraction: IndexArray Managers, or
IAMs. GAME never deals with an IA directly; that would be beneath
its dignity and, more importantly, far too low-level.
Each IAM combines its spatial index with an iterable collection of object instances,
affectionately called POOL. The POOL is the guest list; the IA is
the seating plan. Together, they answer two valuable questions:
POOL to
update
its position and behaviour, draw it, or otherwise remind it that another frame has begun.
IA identifies the objects occupying a particular
cell.
Which enemy is HERO touching? Which item? Which burning fireplace has become an
immediate
career concern?
If we step back for a moment, where does the responsibility of ENGINE end and that of
GAME begin? ENGINE answers, “What just happened?” GAME answers,
“What are we going to do about it?” A collision is geometry; losing a life is editorial policy.
Sometimes ENGINE can relieve GAME of a common burden. Preventing ordinary
actors
from walking through solid walls is reusable enough to become the engine's default behaviour. Individual
games may still override it, naturally, because ghosts, secret passages, and debugging modes have never
respected architecture.
Jumping can be more game-specific. ENGINE can provide the underlying Motion
machinery, but GAME decides the jump rules: its initial impulse, gravity, permitted states,
animation, and the precise degree to which the player should blame the controls.
Returning to IAM: it moves as much reusable bookkeeping as possible into
ENGINE, allowing GAME to make one pleasantly simple call from its game loop:
ENEMY2D.manage(lapsedTime, HERO.player);One polite call above the waterline; several thousand lines paddling furiously beneath it.
The AI module is accessed only by IAMs. GAME never touches it
directly.
Not with a stick. By then they are fourth-degree architectural relatives: technically family, but no
longer
invited to the same function call.
Remember Pac-Man? Each ghost followed a different targeting rule and consequently displayed a
recognisable
personality. That is the territory of the AI module. It governs the behaviour of movable
entities
and their transitions between active and passive modes. Here, “AI” means authored decision logic, not
machine
learning or an enemy achieving self-awareness five minutes before release.
Depending on its behaviour pattern, an entity may wander blindly through the maze, guard a golden key, find the shortest route to the crossroads you are about to reach, or head towards the one you just left in anticipation of a cowardly reversal. It may quietly shadow your movements from just outside your field of view while steering you into a corner. It may even consider whether to shoot you now or wait for a better opportunity. Restraint has finally entered the engine, regrettably on the enemy's side.
All of this remains properly deterministic: the same state and the same inputs produce the same decisions. Well, except when not ...
And we have not yet mentioned the distance fields calculated by BFS or Dijkstra, nor all the paths found by A*. All of that happens within the same frame. On a 60 Hz display, an entire frame lasts about 16.7 milliseconds, and the game must share that time with browser event handling, rendering, compositing, and assorted invisible bureaucracy. The browser does not mercifully allocate the whole budget to us; it merely schedules the next repaint and waits to see whether we embarrass ourselves.
MAZE is a dungeon generator that uses binary space partitioning (BSP) to divide the map
into
regions and place rooms. Corridors are then carved using a directionally biased recursive-backtracker,
implemented iteratively with an explicit stack. Optional maze braiding removes selected dead ends and
introduces loops. In short, it imposes order with BSP, becomes deliberately lost with depth-first
search,
and then removes some of the evidence.
It first powered my early Rogue-like games: initially the 2D Deep Down Into The Darkness, and later the pseudo-3D raycasting game Crawl Master. Both used fully procedurally generated dungeons, allowing the player and the developer to be equally uncertain about what waited around the next corner.
In later games, MAZE produced an initial dungeon template, which I then refined in
MapEditor to better serve the level design. Algorithms, like writers, benefit from an
editor,
although neither enjoys being told so.
A version of the generator was also ported to MOS 6510 assembly and became part of a half-finished Commodore 64 game. The maze generator completed its work. The rest of the project showed less discipline.
MAZE can generate configurable, self-contained dungeon levels with multiple lock-and-key
pairs
arranged into a dependency chain guaranteed to be solvable: the first key is reachable and unlocks a
room
containing the next key, and so on. It can also designate a temple, a starting room, and an exit room.
The dungeon may be cruel, but it is never fraudulent.
At roughly 8,000 lines, this behemoth took over most of the duties previously handled by
ENGINE.js when I moved from raycasting to polygonal 3D rendering with WebGL and GLSL for
Crawl Master II. Apparently, adding a third dimension also adds
several
thousand lines of code. Who could have foreseen this?
It constructs 3D worlds from GridArray data using pleasantly obedient cubic geometry,
imports
glTF models into LS ENGINE's internal object format, and adapts ENGINE's entity-motion classes to the
needs
of a 3D world. It replaces sprite-rendering classes with model-rendering classes and provides the
machinery
for cameras, dungeon decals, lights, world objects, items, traps, missiles, static dungeon dwellers,
fire,
and explosions. It is less a module than a small government, although marginally better organized.
It also generates GLSL shader source dynamically from the dungeon configuration, then compiles the shaders and links them into WebGL programs before rendering. Merely writing the shaders was apparently not ambitious enough; they also had to assemble themselves.
WebGL.js brings game mechanics and visual representation together under one roof. GLSL
shaders
paint everything visible on the screen, while its buffers and supporting data structures connect the
rendered
world to game-world interaction. This is the soul of LS ENGINE—a rather large, GPU-accelerated soul with
an
alarming number of responsibilities.
LS ENGINE is more than its major modules. Beneath them toil smaller components that rarely receive
applause:
SaveGame, Speech, Terrain, Turn,
Lights, Materials, and many other tiny but indispensable pieces of the puzzle.
They work quietly under the hood, which is fortunate—if they started demanding recognition, the
architecture
diagram would become unbearable.
LS ENGINE does not have a GitHub repository of its own. Anyone interested in the details can visit the main LaughingSkull game page. Each listed game includes a link to its GitHub repository, where the relevant version of ENGINE can be studied in its natural habitat, surrounded by whichever game was abusing it at the time. Some versions have already become pleasantly retro. Software ages faster than programmers—at least according to programmers.
With persistence, small steps, continuous learning, and the masochistic correction of bugs I had thoughtfully created myself, I progressed from the modest Space Invaders-style shooter GalactiX to the fully 3D role-playing adventure Haunting the Hauntessa—a masterpiece, if I may say so myself. I may. This is my website.
But this is not GAME OVER. LS ENGINE is not finished, and neither am I. There are still games to build, ideas to overengineer, and entirely new classes of bugs waiting to be invented.
