Version 2.5.0: how editing large maps went from seconds to a fraction of a second

[Filroden]

Version 2.5.0 is mostly a performance release, and this post is the longer account of it: what was slow, what changed, how I checked that the maps still come out the same, and what it costs. The short version is in the changelog. This is for anyone who wants the detail, including the parts that did not work.

The short version

On my own test map (3210 x 2400 pixels, 7,158 brush strokes, 46 custom rivers, Foundry v14), the work that follows an edit went from several seconds to a fraction of a second.

Action	Before	Now
Finish a brush stroke	6.21 s	0.17 s
Undo a brush stroke	4.12 s, then 1.84 s more, 0.8 s later	0.23 s
Redo a brush stroke	4.12 s, then 1.57 s more	0.19 s
Move a custom river node	7.43 s	0.22 s
Undo that move	6.68 s	0.24 s

All of these are times measured in Foundry. They leave out the 2 second pause between finishing a stroke (or moving a node) and the change being applied, which I have left alone on purpose, because it is what lets you keep drawing without being interrupted.

The "before" column is not the true starting point. It was measured after the first change described below, the faster brush loop, was already in. Before that, replaying the brush strokes alone took about four times as long, so the real starting point was several seconds worse than these numbers.

Loading a map, and changing the seed or a slider, still regenerate the whole map. Those are faster too, because the largest part of a whole-map regeneration on a map with many strokes is replaying the strokes, and that is now about four times quicker: 3.6 seconds on my map.

Two changes are worth knowing about before you update. Keeping edits quick uses extra memory (details below). And procedural rivers on existing maps may take a slightly different route, for a reason explained in the last section of the changes.

Why edits were slow

The module builds a map in stages. It generates the base terrain from noise, replays every brush stroke onto it, carves faults and custom rivers, works out moisture and temperature (the climate), traces the procedural rivers, and finally paints the layers you see: base colour, topography, biomes and contours.

That order is right, but every edit paid for all of it. On my map, because it has custom rivers, every terrain stroke ended in a full replay of all 7,158 strokes, a full repaint, a full climate calculation, a river pass, and a second full repaint. Undo and redo did the same. A tiny stroke cost as much as a whole new map, and the cost grew with every stroke added, so a map got slower to edit the more you worked on it.

Two things I had tried or considered earlier shaped how the rest was done:

• Web Workers were tested and dropped. Someone editing a map still has to wait for the result, so moving the work off the main thread did not help. Everything stays synchronous.
• An earlier attempt to limit the climate calculation to the edited area left "ghost" terrain outside the box and a visible box border. The lesson taken from that was not to predict what an edit changes, but to measure what actually changed.

What changed

1. A faster brush loop

Replaying strokes was about three quarters of a full render, and the innermost loop (stamping the brush onto the terrain, once per pixel) was slower than it needed to be. It called Math.hypot for every pixel and looked up the stroke's settings again for every pixel.

The rewrite resolves the stroke's settings once per stamp, skips the pixels outside the brush circle row by row, and specialises the raise and lower tools. The interesting detail is the distance calculation. Plain Math.sqrt(dx * dx + dy * dy) is faster still, but it rounds differently from Math.hypot for about 38% of pixel offsets (up to 2 units in the last place, over 20 million offsets I measured). The terrain is stored as 32-bit floats and I never found a case where that changed the stored value, but that is luck of rounding rather than a guarantee, and it would let replayed terrain drift from what earlier versions produced. So the loop uses exactHypot, an inline copy of V8's own two-argument algorithm (scale both values by the larger, take the square root of the summed squares, scale back). It matched Math.hypot on 60 million random offsets and the edge cases, with no differences.

On a replica of my map's stroke mix, the replay went from 34.1 s to 8.8 s in a two-core sandbox (3.9 times faster), and it takes 3.6 s in Foundry on the real map. Terrain and biome output is identical to before, pixel for pixel.

2. Keeping the brushed terrain, so nothing is replayed

Even at four times faster, replaying thousands of strokes on every edit is wasteful, because all but the last one are the same as last time. The brush engine now keeps a second copy of the terrain, the brushed layer: the base terrain with every stroke applied and nothing else (no faults, no rivers). The working terrain is that layer with the vector features carved on top, so a rebuild copies the layer and carves again instead of replaying.

The layer has to be exactly what a full replay would produce, so it is only ever changed by operations that reproduce a replay's result:

• A finished stroke is applied to it by replaying just that stroke's recorded points.
• Before a stroke is applied, the 64 x 64 pixel tiles it is about to touch are copied aside as an undo patch. Undoing pastes them back. Redoing applies the stroke again.
• Anything else that could change what a replay produces (a new base terrain, a different sea level, strokes edited in place, an undo whose patch had to be dropped to stay within its memory budget) marks the layer invalid, and the next rebuild replays the whole history once to make it valid again.
  If the browser refuses to allocate the memory for the layer, the module falls back to replaying the history, which needs no extra memory, and says so in the console.

3. Refreshing only what changed

With the replay gone, what remained was whole-map work: climate, rivers, and repainting all four layers. Most edits change a small part of the map, so the module now works out which part, and limits the rest of the work to it.

The important word is "works out". A river's carved bed follows the terrain along its whole length, so editing terrain near one end can change the carved elevation a long way from the edit. Predicting the changed area from the stroke's footprint is exactly the kind of guess that produced ghost terrain before. So instead:

1. The new terrain is built off to the side in a scratch buffer: the brushed layer, then faults and rivers over the whole map.
2. It is compared with the working terrain, and only the pixels that differ are copied across. The comparison returns the bounding box of what changed.
3. The area painted live by the brush since the last refresh is added to that box. The live brush writes straight into the working terrain, so if a rebuild happens to give one of those pixels the same value, the comparison reports nothing, but the moisture, rivers and canvas pixels derived from it have not been updated.
   The comparison is bit for bit, not numeric. A numeric !== treats -0 and +0 as equal and NaN as different from itself, and a stage that skipped a pixel because of that could leave the map differing from a full rebuild. BufferDiff reads the float rasters through a Uint32Array view of the same memory, so it compares raw bits:

static #asComparable(raster) {
    return raster instanceof Float32Array ? new Uint32Array(raster.buffer, raster.byteOffset, raster.length) : raster;
}

The stages after the comparison are then limited to that area, with three details that matter:

• Climate. Moisture at a pixel reads the elevation a fixed distance upwind on the same row, so a change to elevation alters the moisture of pixels up to the wind distance to its left and right. The climate area is padded by that distance on each side, which is exactly what the calculation can reach. Temperature only reads its own pixel.
• Rivers. The river pass is still run over the whole map, because a change in one place can send a river somewhere quite different a long way downstream. It keeps the previous water mask aside, and afterwards reports where the water changed, so the repaint covers that too.
• Repaint. Land is shaded relative to the map's highest point. If that point has moved, every land pixel's colour has changed, so the module scans for the peak first and repaints the whole map if it moved. Otherwise it repaints only the changed area, plus a one pixel margin that the colour, biome and contour painters write around it (contour lines sit between two pixels).
  On a full-size replica the median repainted area was about 5% of the map.

4. Skipping the base terrain when it cannot have changed

Moving a fault or river node still went through the full pipeline, including regenerating the base noise and replaying the strokes, even though the base terrain cannot have changed: faults and rivers are applied after the strokes, never inside the base terrain. That was the 7.4 seconds in the table.

The module now records a description of everything the base terrain and the settings depend on: the generation engine, seed, map size, sea level, every derived generation parameter, the custom biomes and their colours, and (in Guided mode only) the land masks. It is a JSON string, stored when a full generation finishes and compared when the next one is asked for. If the two are equal, the same refresh described above is used instead of a full generation. If they differ, if the last generation never finished, or if the buffers have been replaced, the full generation runs as before. Any doubt means the full path, which is always correct.

What the description leaves out is what a refresh finds by comparison anyway: brush strokes, faults and manual rivers. It also leaves out the spring pins, which only feed the river pass, and a refresh always reruns that pass. A pin move once left the river map stale in a test until I added that rerun for a refresh that finds no terrain change.

5. Uploading only the changed rows

Each of the five map layers keeps an RGBA pixel buffer the size of the map (31 MB on my map). Foundry v14 uses PIXI 7, and PIXI 7's BufferResource copies the whole buffer into its texture data and uploads all of it to the graphics card on every update. That happens even for a tiny repaint, and on every pointer move while painting.

The map layers now use a RegionUploadResource, a subclass of BufferResource. It copies only the rows that changed into its texture data and uploads only that band of rows with texSubImage2D. A band of full-width rows is the smallest piece that is contiguous in the buffer, which means it needs none of the WebGL 2 only unpack settings (and no cleanup of them afterwards). It uploads the whole texture, as before, whenever it cannot be sure that the graphics card's copy matches: the first upload, a size change, a texture the browser recreated (for example after a lost context), or a pixel buffer that is not the one it last copied from.

This assumes PIXI 7 and one renderer per texture, which is what the map canvas has. It is written against PIXI 7.4's BufferResource.upload, and would need rechecking if Foundry moves to a later PIXI version.

I expected this to be the last big saving. It was not, and it is a useful example of why the module now prints timings. The Foundry log showed the copy and upload time dropping to about 7 ms, but the repaint as a whole barely moved, because the time was somewhere else.

6. The real cause of the last big cost: rivers sharing one random stream

After the changes above, moving a river node still took 861 ms, and the log showed the four painters taking 674 ms of it. In a sandbox the same painters take about 2 ms per layer for the changed area, so they had to be repainting something much larger. I had added a note to the timing summary saying how much of the map each repaint covered, and it said 52.2%, in a box spanning most of the map. Looking at those coordinates, the obvious reading was the right one: it was repainting all the rivers, not just the one that moved.

The cause was in the river tracer. Every river was traced from one shared random number stream, in order. The tracer uses it at every step: once for the direction its scan of the eight neighbouring pixels starts in (which decides ties between equally low neighbours) and once per neighbour for the meander jitter. So if an edit changed how many steps one river took, or whether it merged into another, the stream shifted for every river traced after it, and each of those could take a different route wherever a tie went the other way. On a replica of my map, moving one node reshaped between 27 and 34 of 80 rivers.

Now each river draws from a stream of its own, seeded from the map seed and the pixel index of its spring:

static #riverSeed(seedNumber, springIndex) {
    let hash = (seedNumber + 2) ^ Math.imul(springIndex + 1, 0x9e3779b1);
    hash ^= hash >>> 16;
    hash = Math.imul(hash, 0x85ebca6b);
    hash ^= hash >>> 13;
    hash = Math.imul(hash, 0xc2b2ae35);
    hash ^= hash >>> 16;
    return hash >>> 0;
}

The mixing steps (the finaliser from MurmurHash3) make springs a pixel apart get unrelated streams instead of the nearly identical ones that seeds one apart would give. On the replica, moving one node now reshapes 1 to 5 rivers instead of about a third, and the river map differences shrink from a box covering 83 to 86% of the map to one covering 0.2 to 4.2%. On my map the repaint area went from 52.2% to 2.3%, the painters from 674 ms to 61 ms (and from 291 ms to 13 ms on the undo), and the whole refresh from 861 ms to 225 ms.

Two things follow from this that you should know:

• It fixes a small visible oddity as well as a slow one. Before, editing one river could quietly re-route other rivers elsewhere on the map. Now an edit only changes rivers that are connected to it, through a merge or a lake.
• It changes existing maps. Each river now makes different tie-breaking choices from before. On a replica map with 80 procedural rivers, 39 took a slightly different path in detail after the change. The differences are confined to places where the terrain left a river a choice between equally low neighbouring pixels, and in a side by side comparison of existing maps I could not see them by eye. If you do see a difference you dislike, please tell me. It is a deliberate trade, and the alternative was to keep the old behaviour and repaint the scattered changes tile by tile, which I prototyped and left out.

How I checked that the maps come out the same

The rule for all of this is that a refresh must be identical to regenerating the whole map, bit for bit. I did not want a faster map that was slightly wrong, so most of the effort went into testing that.

Foundry itself cannot be driven by an automated test, so the checks are Node harnesses that import the module's real engine code and mirror what the app does around it. They generate a map, apply a random sequence of edits, refresh the way the app would, and then compare every derived layer (base and current elevation, biome overrides, moisture, temperature, river map, water mask and the five painted canvas buffers) with an independent generation of the same map from scratch.

• Brush loop: 1,500 random histories with three seeds (about 25,000 strokes each), covering all tools and guard cases, plus 300 integer boundary cases, plus a full-size replica of my map's stroke mix. No differing pixels.
• Brushed layer and undo patches: thousands of random strokes, undos, redos and every invalidation, compared with a full replay after each step.
• Bounded refresh: about 550 refreshes in randomised runs (strokes, undos, redos, sea level and base changes, faults, rivers, live painted strokes), each compared with a whole-map recompute. About 90% repainted a bounded area, and the rest correctly fell back to a full repaint because the peak moved.
• Skipping the base terrain: randomised runs across all four engine modes with land masks, plus a test that changes each of the 376 settings on its own after a full generation and compares the result with a from-scratch generation. Of those, 208 took the fast path (settings such as grid, brush and tool state that the pipeline does not read), and everything the pipeline reads forced the full path.
• Running out of memory: the same runs with allocation failures injected into the layer, the scratch buffer, both, and at random.
• Partial upload: real PIXI 7.4 in headless Chromium, with WebGL 1 and WebGL 2, comparing the texture read back from the graphics card with a control texture uploaded whole, over random bounded edits, whole writes, lost and restored contexts, and checking that the GL calls were the expected band of rows.
• Rivers: a property test on random terrain quantised into plateaus, so that ties are everywhere. It moves, adds or removes a spring and checks that every river not connected to the edit (through its path, a lake, or the pixel next to a merge) is identical. Nine hundred trials, and none of about 5,400 unconnected rivers changed. With the old shared stream restored, more than half of them did.
  Tests can pass because they are weak, so I also broke the code on purpose (mutation testing) and checked that the harnesses noticed. Across the pieces I tried several dozen deliberate breaks: dropping the wind padding, ignoring the water mask difference, skipping the peak check, off-by-one errors in every bound, leaving out parts of the settings description, and so on. Most were caught. About ten survived, and I checked each one to see why: they were all things that cannot change the output (for example, dropping the map size from the settings description, because the buffers are reallocated whenever the size changes).

What is not covered: the parts of the app that need Foundry itself, such as the glue in generateTerrain and the timer that releases the scratch buffer when idle. The harness mirrors that glue, and I used the real thing myself on the real map, but that is a person looking at a result, not a test. My comparison of PNG exports before and after the brush loop change gave identical file sizes, which is reassurance rather than proof. The bit-for-bit evidence is the sandbox harnesses.

What did not work

• Web Workers: tested and dropped, as above.
• Exact bounded replay: limiting the replay to the edited area sounds obvious, but the level, smooth and slope tools read pixels outside their own footprint (an anchor point, the centre of the stamp), and a change under one of those changes the whole footprint elsewhere. Growing the area until it was exact made it 98.3% of my map for nearly every stroke. The brushed layer avoids the question entirely.
• Lower-resolution noise: not bit-identical, so it would have shifted existing maps and re-routed rivers.
• Micro-optimisations of the noise and Guided mode's distance field: the noise change gave nothing (0.84 times, a slowdown), and rewriting the distance field's inner loop gave about 1.2 times.
• A larger texture-upload saving: as described above, the copies were never the bottleneck.
• Repainting scattered changes tile by tile: a prototype cut the repaint area on a river edit from 14.9% to 0.7% on a replica, but once each river had its own random stream the box was already small, and the extra plumbing was not worth it. It is the next step if a real map still shows a large repaint area.

What it costs

• Memory. On my map, about 38 MB for the brushed layer (five bytes per pixel: an elevation float and a biome override byte), a 31 MB scratch buffer that is released after 30 seconds without an edit, and up to 64 MB of undo patches. The patch budget shrinks on very large maps so that the extra memory stays near a 256 MB ceiling. If the browser cannot supply any of it, the module falls back to the slower method instead of failing.
• Existing maps. Procedural rivers may take a slightly different route, as described above.
• PIXI 7. The partial texture upload is written against PIXI 7's BufferResource, which is what Foundry v14 uses. Foundry has deferred moving to PIXI 8 until a much later version, and the upload code will need revisiting then.

What is still slow

• Changing the seed, sea level, a climate slider, the map size, or a Guided mode land mask still regenerates the whole map. That is correct for the sliders (they change everything), but land mask edits could in principle be limited to the area they change, if the land mask pass reported which pixels it touched. In Guided mode the distance field is about 58% of a regeneration, so it is a real piece of work and I have not started it.
• After the changes, what is left in a 225 ms refresh is small and spread out: change detection about 30 to 40 ms, climate about 30 to 40 ms, the river pass about 18 ms, a scan for the map's highest point (14 to 52 ms), and the vector layers about 18 ms. Each of those could be trimmed by tens of milliseconds, at the price of state that has to stay exactly right, so I have left them. The 2 second pause before an edit is applied is now the largest part of the wait, and it is a single value in the module's configuration if I decide to tune it.

Reading the console summary

Full renders, refreshes, undo and redo each finish with one summary in the browser console (F12), which lists every phase's time and share of the total, how many times a phase ran, and, for repaints, how much of the map was repainted. It looks like this:

World Map Builder | Terrain refresh took 224.90ms
    Brush layer reused                        0.0ms   0.0%  (7158 strokes)
    Change detection                         30.9ms  13.7%
    Climate                                  29.9ms  13.3%
    Features (springs and rivers)            17.9ms   8.0%
    Canvas repaint: peak scan                14.0ms   6.2%  (asked to repaint x 575-2861, y 1282-1357, 2.3% of the map)
    Canvas repaint: base painter             27.7ms  12.3%
    ...
    Other (unmeasured)                       43.1ms  19.2%

If a map feels slow after this update, or an edit leaves something out of date on the canvas, please open an issue with that summary attached and a note of the map size and roughly how many strokes it has. The summary is what found the river problem above, and it is the quickest way for me to see where the time is going on a map that is not mine.