Blockbuster — Approaches & Algorithms

A guide to the mathematical models and techniques behind Blockbuster's route-planning engine.

1. What Blockbuster Does

Blockbuster is a route-planning tool for traversing landscapes where different regions carry different kinds of danger. Given a terrain map, a set of waypoints, and an analyst's risk tolerances, it solves a variant of the shortest-path problem — except that "shortest" means lowest total risk-adjusted cost, not merely shortest distance.

The system produces three ranked Courses of Action (COAs), each taking a distinct corridor through the terrain. This lets the analyst compare trade-offs quantitatively: one route might minimise heat exposure at the expense of higher bandit risk; another might be physically longer but avoids all elevated-risk cells.

The pipeline has four stages: terrain generation → hex grid overlay → risk assessment → route optimisation. Each stage is deterministic — the same inputs always yield the same outputs. Everything runs client-side in the browser; no data leaves the machine.

2. Procedural Terrain Generation

The landscape is generated procedurally from a single seed integer. The seed initialises a deterministic pseudo-random number generator (mulberry32, a fast 32-bit PRNG), guaranteeing that the same seed always produces an identical map — useful for reproducibility and scenario sharing.

The underlying technique is Perlin noise, a gradient-based noise function that produces smooth, continuous variation across a 2D plane. At each integer lattice point, a pseudo-random gradient vector is assigned (via a deterministic hash — no sine functions, avoiding floating-point artefacts). The noise value at any point (x, y) is computed by interpolating the dot products of these gradients with the offset vectors, using Perlin's smootherstep function:

smootherstep(t) = 6t⁵ − 15t⁴ + 10t³

This gives C² continuity (both the value and its first derivative are smooth), producing natural-looking contours rather than blocky artefacts.

To create terrain with features at multiple scales — large mountain ranges and small rocky outcrops — multiple octaves of Perlin noise are summed in a technique called Fractal Brownian Motion (FBM). Each successive octave doubles the frequency and halves the amplitude:

FBM(x, y) = Σ_i=0ⁿ⁻¹   0.5ⁱ · perlin(2ⁱx,  2ⁱy)

The result is normalised to [0, 1]. Separate FBM fields (with different seed offsets) drive elevation, vegetation density, temperature, and other terrain attributes. The biome at each point — woodland, savannah, mountains, etc. — is classified from these continuous fields.

3. Hex Grid Tessellation

The terrain is discretised into a hexagonal grid using axial coordinates (q, r) — a two-axis system where the implicit third coordinate is always s = −q − r (the "cube constraint"). This is mathematically elegant because hex distance reduces to a simple formula:

d(a, b) = max(|Δq|, |Δr|, |Δs|)   where   Δs = −Δq − Δr

The key advantage over a square grid is isotropy: all six neighbours of a hex cell are equidistant from its centre. In a square grid, the four diagonal neighbours are √2 ≈ 1.41 times further than the four cardinal neighbours, which introduces directional bias into any pathfinding algorithm. Hexagons eliminate this.

The grid uses pointy-top orientation with a configurable circumradius (centre-to-vertex distance). The default of 2.4 km yields approximately 100 cells over the standard 50 km × 30 km map extent — as specified in the project brief.

4. Risk Assessment

At each cell's centre, the terrain field is sampled to obtain continuous attributes — elevation, temperature, vegetation density, water proximity, and bandit activity. These are then mapped to five independent risk channels, each normalised to the range [0, 1]:

• Animals — positively correlated with vegetation density
• Cold — driven by elevation and low temperature
• Heat — driven by high temperature
• Lack of water — inversely correlated with water proximity
• Humans — driven by bandit activity near settlements

Together these form the cell's risk profile — a five-dimensional vector. Analysts can override any channel if they possess better local intelligence; overridden values take precedence during route planning and are visually highlighted in the UI.

5. The Cost Function and Risk Appetite

The cost of traversing a cell is a weighted sum across all five risk channels. The analyst controls a risk appetite per channel — a value in [0, 1] where 0 means "intolerant" and 1 means "fully tolerant." The sensitivity is simply the complement:

sensitivity = 1 − appetite

The per-channel cost contribution is then:

cost_channel = risk_channel × sensitivity_channel × w_risk

where w_risk is a global risk weight (default 10). The total risk cost for the cell is the sum across all five channels. A separate movement cost — proportional to the physical distance in kilometres — is added to prevent routes from taking excessively long detours to avoid minor risks. The total step cost is therefore:

step cost = Σ_channels cost_channel + distance(km) × w_distance

Crucially, this cost function is shared between the routing engine and the UI charts — both call the same code, ensuring that what the analyst sees in the stacked bar charts is exactly what the optimiser minimised.

6. Route Optimisation (A* Search)

Given a set of waypoints, the system finds the lowest-cost path through the hex graph using the A* algorithm. A* is a best-first graph search that maintains a priority queue of candidate cells, ordered by f(n) = g(n) + h(n), where:

• g(n) is the accumulated cost from the start to cell n
• h(n) is a heuristic estimate of the remaining cost to the goal (hex distance × minimum possible cell cost)

Because the heuristic never overestimates, A* is guaranteed to find the optimal path. On a hex grid with ~100 cells and degree 6, this runs in well under 50 ms.

The widget below makes that search visible. A* explores outward from the start, always opening the most promising cell next — the one with the lowest f = g + h. Step through it, or press Play, and watch the two sets grow: the frontier (gold outlines — cells discovered but not yet committed) and the explored set (navy — cells whose best cost is now settled). When the frontier reaches the goal, the path is traced back through the recorded parent links.

The most instructive control is the heuristic weight. Slide it to 0 and A* degenerates into Dijkstra's algorithm — with no sense of direction it explores in an expanding blob, equally in all directions. At weight 1 it is true A*: the same optimal path, but the explored set is visibly pulled toward the goal, so far fewer cells are touched. Push it above 1 and it becomes greedy / weighted — it rushes at the goal and finishes even faster, but may settle for a slightly costlier route. This is the central trade-off in heuristic search, the same one the Red Blob Games tutorials illustrate.

Multi-waypoint routes are computed segment by segment: A* is run independently between each consecutive pair of waypoints, and the resulting sub-paths are concatenated.

Generating three diverse COAs

A single optimal path is rarely sufficient for decision-making. To produce three distinct Courses of Action, the system applies a cumulative penalty strategy:

The three COAs are ranked by total cost. Each records a per-cell breakdown of risk contributions, enabling the detailed visual comparison described in the next section.

7. Comparing Courses of Action

The three COAs are visualised as stacked bar charts. Each bar represents one cell along the route; each coloured segment shows the contribution of one risk channel to that cell's cost. The total cost of each COA is displayed above its chart.

This decomposition is possible because the cost function is additive across channels — the analyst can immediately see which risks dominate each route and make an informed choice. For example, one COA might show tall red (heat) segments while another shows tall purple (human) segments of similar overall height, representing a genuine trade-off.

8. Responsiveness and Concurrency

Route optimisation — three A* searches across a ~100-cell graph — can take tens of milliseconds. To prevent the UI from freezing during computation, the routing engine runs in a Web Worker (a browser-native background thread). The main thread remains responsive to slider adjustments and map interactions throughout.

User actions are debounced with a ~150 ms window: rapid successive changes (e.g., dragging a slider) are coalesced into a single route-planning request. If the analyst modifies the inputs while a plan is in progress, the system applies stale-guarding — it checks whether the returned plan's waypoints still match the current state, and discards outdated results.

9. Glossary