SOURCE / PINNED RELEASE
Made of little things.
Drift City
- Release
- 098731aa0f0f…
- Author-recorded commit
- 2822ea0a4f5b…
- License
- LICENSE
- Author’s source reference
- nostr://npub12lm3rxsva8kfempyjkxupt09e02n3fezurkyadyqfejdc5e0r2kscqty6r/wss%3A%2F%2Fgit.napplet.soy%2F/n-a4c0039c855
Archive hash verified: b3323e408235502b…. The source-to-build association is the author’s claim; it has not been independently rebuilt.
import type { RoadGraph } from './traffic.js';
/**
* Race routes: a line along the roads from a start to a finish (or round a circuit),
* passing through the waypoints the player set on the map.
*
* Each waypoint is snapped onto the nearest road; between one and the next the route
* takes the shortest way along the road network, so it follows the streets however the
* points were placed. The result is one smooth polyline, resampled every few metres, with
* how wide the road is at each point (for the rivals to use its width).
*/
/** A waypoint on a road: which edge, how far along it from its first end, and where that is. */
export interface RoutePoint {
x: number;
z: number;
edge: number;
t: number;
}
/** A place on the route, and the way it runs there. */
export interface RouteSample {
x: number;
z: number;
tx: number;
tz: number;
/** Half the road's width there. */
hw: number;
/** The road's height there (up on the highway, or 0 on the ground). */
y?: number;
/** A one-way road there (the whole width is the race's, no oncoming half). */
oneway?: boolean;
}
const SPACING = 4;
/** Where the start line is, along the route: the grid lines up behind it. */
export const START_S = 34;
/** Snap a point on the map to the nearest place on any road. */
export function snapToRoad(graph: RoadGraph, x: number, z: number): RoutePoint {
const { cursor } = graph.nearest(x, z, 0);
const e = graph.edges[cursor.edge]!;
const t = cursor.dir > 0 ? cursor.s : e.len - cursor.s;
const p = pointOnEdge(graph, cursor.edge, t);
return { x: p.x, z: p.z, edge: cursor.edge, t };
}
function pointOnEdge(graph: RoadGraph, edge: number, t: number): { x: number; y: number; z: number } {
const e = graph.edges[edge]!;
const d = Math.max(0, Math.min(e.len, t));
let i = 1;
while (i < e.cum.length - 1 && e.cum[i]! < d) i++;
const a = e.pts[i - 1]!;
const b = e.pts[i]!;
const f = (d - e.cum[i - 1]!) / (e.cum[i]! - e.cum[i - 1]! || 1);
return { x: a.x + (b.x - a.x) * f, y: a.y + (b.y - a.y) * f, z: a.z + (b.z - a.z) * f };
}
/** The points of an edge from distance t0 to t1 along it (either way round), ends included. */
function slice(graph: RoadGraph, edge: number, t0: number, t1: number, out: Raw[]): void {
const e = graph.edges[edge]!;
const push = (p: { x: number; y: number; z: number }) => out.push({ x: p.x, y: p.y, z: p.z, hw: halfWidth(e), oneway: !!e.oneway });
push(pointOnEdge(graph, edge, t0));
if (t1 >= t0) {
for (let i = 0; i < e.pts.length; i++) if (e.cum[i]! > t0 && e.cum[i]! < t1) push(e.pts[i]!);
} else {
for (let i = e.pts.length - 1; i >= 0; i--) if (e.cum[i]! < t0 && e.cum[i]! > t1) push(e.pts[i]!);
}
push(pointOnEdge(graph, edge, t1));
}
/** A point of a route as it's first laid along the roads. */
type Raw = { x: number; y: number; z: number; hw: number; oneway: boolean };
/** May traffic (and a race) go along edge e from its end a (dir 1) or its end b (dir -1)? */
function allowed(graph: RoadGraph, edge: number, dir: 1 | -1): boolean {
const w = graph.edges[edge]!.oneway;
return !w || w === dir;
}
/** Half the width a racer has on an edge: a street or the highway, a one-way curve of it, a ramp, a country road or lane. */
function halfWidth(e: { city: boolean; kind: string; oneway: number }): number {
return e.kind === 'ramp' ? 3.2 : e.oneway ? 4.6 : e.city ? 7.4 : 5;
}
/** Shortest distances (and the way back) from a place on the roads to every junction. */
function dijkstra(graph: RoadGraph, from: RoutePoint): { dist: Float64Array; prevNode: Int32Array; prevEdge: Int32Array } {
const n = graph.nodes.length;
const dist = new Float64Array(n).fill(Infinity);
const prevNode = new Int32Array(n).fill(-1);
const prevEdge = new Int32Array(n).fill(-1);
const done = new Uint8Array(n);
const e0 = graph.edges[from.edge]!;
// Leaving the start edge by either end (-2 marks "straight from the start point").
if (allowed(graph, from.edge, -1)) {
dist[e0.a] = from.t;
prevNode[e0.a] = -2;
prevEdge[e0.a] = from.edge;
}
if (allowed(graph, from.edge, 1) && e0.len - from.t < dist[e0.b]!) {
dist[e0.b] = e0.len - from.t;
prevNode[e0.b] = -2;
prevEdge[e0.b] = from.edge;
}
for (;;) {
let u = -1;
for (let i = 0; i < n; i++) if (!done[i] && dist[i]! < Infinity && (u < 0 || dist[i]! < dist[u]!)) u = i;
if (u < 0) break;
done[u] = 1;
for (const ei of graph.nodes[u]!.edges) {
const e = graph.edges[ei]!;
if (!allowed(graph, ei, e.a === u ? 1 : -1)) continue;
const v = e.a === u ? e.b : e.a;
const d = dist[u]! + e.len;
if (d < dist[v]!) {
dist[v] = d;
prevNode[v] = u;
prevEdge[v] = ei;
}
}
}
return { dist, prevNode, prevEdge };
}
/** The way along the roads from one waypoint to the next, as points (the first included). */
function leg(graph: RoadGraph, p: RoutePoint, q: RoutePoint, out: Raw[]): number {
const eq = graph.edges[q.edge]!;
// Along the same stretch of road, straight there.
let direct = Infinity;
if (p.edge === q.edge && allowed(graph, p.edge, q.t >= p.t ? 1 : -1)) direct = Math.abs(q.t - p.t);
const { dist, prevNode, prevEdge } = dijkstra(graph, p);
const viaA = allowed(graph, q.edge, 1) ? dist[eq.a]! + q.t : Infinity;
const viaB = allowed(graph, q.edge, -1) ? dist[eq.b]! + (eq.len - q.t) : Infinity;
const best = Math.min(direct, viaA, viaB);
if (!isFinite(best)) return Infinity;
if (best === direct) {
slice(graph, p.edge, p.t, q.t, out);
return best;
}
// Walk back from the junction it reaches q's road by, then lay the way out forwards.
const end = viaA <= viaB ? eq.a : eq.b;
const nodes: number[] = [];
const edges: number[] = [];
for (let u = end; u >= 0; u = prevNode[u]!) {
nodes.unshift(u);
edges.unshift(prevEdge[u]!);
if (prevNode[u] === -2) break;
}
// The first edge is p's own, from p out to the first junction.
const e0 = graph.edges[p.edge]!;
slice(graph, p.edge, p.t, nodes[0] === e0.a ? 0 : e0.len, out);
for (let i = 1; i < nodes.length; i++) {
const e = graph.edges[edges[i]!]!;
const fromA = e.a === nodes[i - 1];
slice(graph, edges[i]!, fromA ? 0 : e.len, fromA ? e.len : 0, out);
}
slice(graph, q.edge, end === eq.a ? 0 : eq.len, q.t, out);
return best;
}
/** A sensible first route: from near where the car starts to somewhere about 1.5 km away by road. */
export function defaultRoute(graph: RoadGraph, x: number, z: number): RoutePoint[] {
const start = snapToRoad(graph, x, z);
const { dist } = dijkstra(graph, start);
let best = -1;
for (let i = 0; i < dist.length; i++) if (isFinite(dist[i]!) && (best < 0 || Math.abs(dist[i]! - 1500) < Math.abs(dist[best]! - 1500))) best = i;
const n = graph.nodes[Math.max(0, best)]!;
return [start, snapToRoad(graph, n.x, n.z)];
}
export class RaceRoute {
/** Evenly spaced points along the route, and how far along each one is. */
readonly pts: RouteSample[] = [];
readonly len: number;
/** For each point, which leg (waypoint to waypoint) it's on: for the editor to insert waypoints. */
readonly legOf: number[] = [];
private constructor(
raw: (Raw & { leg: number })[],
readonly loop: boolean,
) {
// Resample to even spacing, dropping repeats.
const cum = [0];
for (let i = 1; i < raw.length; i++) cum.push(cum[i - 1]! + Math.hypot(raw[i]!.x - raw[i - 1]!.x, raw[i]!.z - raw[i - 1]!.z));
const total = cum[cum.length - 1]!;
const n = Math.max(2, Math.round(total / SPACING));
let j = 1;
for (let k = 0; k <= n; k++) {
const d = (k / n) * total;
while (j < raw.length - 1 && cum[j]! < d) j++;
const a = raw[j - 1]!;
const b = raw[j]!;
const f = (d - cum[j - 1]!) / (cum[j]! - cum[j - 1]! || 1);
this.pts.push({ x: a.x + (b.x - a.x) * f, y: a.y + (b.y - a.y) * f, z: a.z + (b.z - a.z) * f, tx: 0, tz: 1, hw: Math.max(a.hw, b.hw), oneway: a.oneway && b.oneway });
this.legOf.push(a.leg);
}
if (loop) {
this.pts.pop();
this.legOf.pop();
}
this.len = loop ? total : total;
// Directions: smoothed over a few points so corners turn gradually.
const m = this.pts.length;
for (let i = 0; i < m; i++) {
const pi = loop ? (i - 3 + m) % m : Math.max(0, i - 3);
const ni = loop ? (i + 3) % m : Math.min(m - 1, i + 3);
const dx = this.pts[ni]!.x - this.pts[pi]!.x;
const dz = this.pts[ni]!.z - this.pts[pi]!.z;
const l = Math.hypot(dx, dz) || 1;
this.pts[i]!.tx = dx / l;
this.pts[i]!.tz = dz / l;
}
}
/** The route through these waypoints (round to the first again if loop), or null if they can't be joined. */
static build(graph: RoadGraph, way: RoutePoint[], loop: boolean): RaceRoute | null {
if (way.length < 2) return null;
const raw: (Raw & { leg: number })[] = [];
const stops = loop ? [...way, way[0]!] : way;
for (let i = 0; i + 1 < stops.length; i++) {
const part: Raw[] = [];
if (!isFinite(leg(graph, stops[i]!, stops[i + 1]!, part))) return null;
for (const p of part) {
const last = raw[raw.length - 1];
if (last && Math.hypot(last.x - p.x, last.z - p.z) < 0.3) continue;
raw.push({ ...p, leg: i });
}
}
if (raw.length < 2) return null;
return new RaceRoute(raw, loop);
}
/** The route at distance s along it (wrapping round a circuit; clamped otherwise). */
at(s: number, out: RouteSample): RouteSample {
const m = this.pts.length;
const step = this.loop ? this.len / m : this.len / (m - 1);
let u = s / step;
if (this.loop) u = ((u % m) + m) % m;
else u = Math.max(0, Math.min(m - 1, u));
const i = Math.floor(u);
const f = u - i;
const a = this.pts[i]!;
const b = this.pts[this.loop ? (i + 1) % m : Math.min(m - 1, i + 1)]!;
out.x = a.x + (b.x - a.x) * f;
out.z = a.z + (b.z - a.z) * f;
out.y = (a.y ?? 0) + ((b.y ?? 0) - (a.y ?? 0)) * f;
const tx = a.tx + (b.tx - a.tx) * f;
const tz = a.tz + (b.tz - a.tz) * f;
const l = Math.hypot(tx, tz) || 1;
out.tx = tx / l;
out.tz = tz / l;
out.hw = Math.min(a.hw, b.hw);
out.oneway = !!(a.oneway && b.oneway);
return out;
}
/**
* Where (x, z) is along the route, searching from s - back to s + ahead (so a racer's
* progress can't jump to a far part of the route that happens to pass close by), and how
* far from the route's line it is. Where the route doubles back on itself (a U-turn at a
* waypoint), both ways lie side by side: stick says how strongly to favour the place
* nearest s, so progress carries on round the turn rather than jumping across.
*/
project(x: number, z: number, s: number, back: number, ahead: number, stick = 0): { s: number; d: number } {
let best = { s, d: Infinity };
let bestScore = Infinity;
const step = 2;
let prev = this.at(s - back, _a);
let px = prev.x;
let pz = prev.z;
for (let u = s - back + step; u <= s + ahead + 1e-6; u += step) {
if (!this.loop && (u < 0 || u - step > this.len)) {
prev = this.at(u, _a);
px = prev.x;
pz = prev.z;
continue;
}
const q = this.at(u, _b);
const vx = q.x - px;
const vz = q.z - pz;
const l2 = vx * vx + vz * vz || 1;
const t = Math.max(0, Math.min(1, ((x - px) * vx + (z - pz) * vz) / l2));
const d = Math.hypot(x - (px + vx * t), z - (pz + vz * t));
const at = u - step + step * t;
const score = d + stick * Math.abs(at - s);
if (score < bestScore) {
bestScore = score;
best = { s: at, d };
}
px = q.x;
pz = q.z;
}
return best;
}
}
const _a: RouteSample = { x: 0, z: 0, tx: 0, tz: 1, hw: 4 };
const _b: RouteSample = { x: 0, z: 0, tx: 0, tz: 1, hw: 4 };
export type RaceEvent =
| { type: 'count'; n: number }
| { type: 'go' }
| { type: 'checkpoint'; n: number; of: number; time: number }
| { type: 'lap'; lap: number; of: number; time: number }
| { type: 'finish'; position: number; of: number; time: number };
/** One line of the standings. */
export interface Standing {
name: string;
player: boolean;
/** Seconds to the line, once over it. */
time: number | null;
out: boolean;
/** Metres still to go (while racing). */
toGo: number;
}
/** The race's state for the HUD. */
export interface RaceInfo {
phase: 'countdown' | 'racing' | 'finished';
countdown: number;
position: number;
of: number;
lap: number;
laps: number;
time: number;
/** Off the route: drive back to it (R puts you back). */
offRoute: boolean;
/** Metres left to the finish. */
toGo: number;
}
const COUNTDOWN = 3.6;
/**
* A race under way: the countdown, the clock, the player's progress along the route
* (found near where they were, so it can't skip ahead by leaving the road), checkpoints,
* laps, everyone's position, and the finish.
*/
export class RaceSession {
phase: RaceInfo['phase'] = 'countdown';
/** Seconds until the start (counting down), then the race clock. */
clock = COUNTDOWN;
time = 0;
/** How far the player has come from the start line (negative on the grid). */
prog: number;
/** How far it is from the start line to the finish, laps and all. */
readonly total: number;
/** Progress at each checkpoint gate, and which is next. */
readonly checkpoints: number[] = [];
private next = 0;
private lapsDone = 0;
private lastCount = 4;
offRoute = false;
finishTime = 0;
finishPosition = 0;
standings: Standing[] = [];
constructor(
readonly route: RaceRoute,
readonly laps: number,
startProg: number,
) {
this.prog = startProg;
const lap = route.loop ? route.len : route.len - 25 - START_S;
this.total = route.loop ? lap * laps : lap;
// A checkpoint about every 350 m of each lap.
const per = Math.max(1, Math.round(lap / 350));
for (let k = 0; k < laps; k++) for (let c = 1; c < per; c++) this.checkpoints.push(k * lap + (lap * c) / per);
if (route.loop) for (let k = 1; k < laps; k++) this.checkpoints.push(k * lap);
this.checkpoints.sort((a, b) => a - b);
}
/** Where the finish line is, along the route. */
get finishS(): number {
return this.route.loop ? START_S : this.route.len - 25;
}
/** The lap length (or the whole route, point to point). */
get lapLen(): number {
return this.route.loop ? this.route.len : this.total;
}
/**
* One step. rivals gives each rival's progress (from the start line) and state; it
* returns what happened, and finished lists rivals who crossed the line this step.
*/
update(dt: number, x: number, z: number, rivals: { name: string; prog: number; out: boolean; finished: number | null }[]): { events: RaceEvent[]; finished: string[] } {
const events: RaceEvent[] = [];
const finished: string[] = [];
if (this.phase === 'countdown') {
this.clock -= dt;
const n = Math.ceil(this.clock);
if (n < this.lastCount && n > 0) events.push({ type: 'count', n });
this.lastCount = n;
if (this.clock <= 0) {
this.phase = 'racing';
this.clock = 0;
events.push({ type: 'go' });
}
} else this.time += dt;
// The player's progress, searched for near where they were.
if (this.phase !== 'finished') {
const pr = this.route.project(x, z, START_S + this.prog, 25, 60, 0.1);
const p = this.route.at(pr.s, _a);
this.offRoute = pr.d > p.hw + 16;
if (!this.offRoute && this.phase === 'racing') this.prog = Math.max(this.prog - 25, pr.s - START_S);
}
if (this.phase === 'racing') {
while (this.next < this.checkpoints.length && this.prog >= this.checkpoints[this.next]!) {
const at = this.checkpoints[this.next]!;
this.next++;
const lapAt = this.route.loop ? Math.round(at / this.lapLen) : 0;
if (this.route.loop && Math.abs(at - lapAt * this.lapLen) < 1) {
this.lapsDone = lapAt;
events.push({ type: 'lap', lap: lapAt + 1, of: this.laps, time: this.time });
} else events.push({ type: 'checkpoint', n: this.next, of: this.checkpoints.length, time: this.time });
}
for (const r of rivals) if (r.finished === null && !r.out && r.prog >= this.total) finished.push(r.name);
if (this.prog >= this.total) {
this.phase = 'finished';
this.finishTime = this.time;
this.rank(rivals, finished);
this.finishPosition = this.standings.findIndex((s) => s.player) + 1;
events.push({ type: 'finish', position: this.finishPosition, of: this.standings.length, time: this.time });
return { events, finished };
}
}
if (this.phase === 'finished')
// The player's done; the rivals race on to the line, timed.
for (const r of rivals) if (r.finished === null && !r.out && r.prog >= this.total) finished.push(r.name);
this.rank(rivals, finished);
return { events, finished };
}
/** Whether everyone's over the line (or out). */
allIn(rivals: { finished: number | null; out?: boolean }[]): boolean {
return this.phase === 'finished' && rivals.every((r) => r.finished !== null || r.out);
}
/** Everyone in order: over the line by time, then by how far along they are; wrecks last. */
private rank(rivals: { name: string; prog: number; out: boolean; finished: number | null }[], justFinished: string[]): void {
const all = [
{ name: 'You', player: true, prog: this.prog, out: false, time: this.phase === 'finished' ? this.finishTime : null },
...rivals.map((r) => ({ name: r.name, player: false, prog: r.prog, out: r.out, time: r.finished ?? (justFinished.includes(r.name) ? this.time : null) })),
];
all.sort((a, b) => {
if (a.out !== b.out) return a.out ? 1 : -1;
if (a.time !== null || b.time !== null) {
if (a.time === null) return 1;
if (b.time === null) return -1;
return a.time - b.time;
}
return b.prog - a.prog;
});
this.standings = all.map((a) => ({ name: a.name, player: a.player, time: a.time, out: a.out, toGo: Math.max(0, this.total - a.prog) }));
}
info(): RaceInfo {
const position = this.standings.findIndex((s) => s.player) + 1 || this.standings.length;
const lap = this.route.loop ? Math.min(this.laps, Math.floor(Math.max(0, this.prog) / this.lapLen) + 1) : 1;
return {
phase: this.phase,
countdown: Math.ceil(this.clock),
position,
of: Math.max(1, this.standings.length),
lap: this.phase === 'finished' ? this.laps : Math.max(lap, this.lapsDone + 1),
laps: this.route.loop ? this.laps : 1,
time: this.phase === 'finished' ? this.finishTime : this.time,
offRoute: this.offRoute && this.phase === 'racing',
toGo: Math.max(0, this.total - this.prog),
};
}
}
/** Race time as m:ss.cc. */
export function raceTime(t: number): string {
const m = Math.floor(t / 60);
const s = t - m * 60;
return `${m}:${s.toFixed(2).padStart(5, '0')}`;
}
/** One stretch of a generated route: along an edge from distance t0 to t1 (t1 < t0 going backwards). */
interface Step {
edge: number;
t0: number;
t1: number;
/** The junction it comes into this edge from (-1 for the first). */
from: number;
}
/**
* A route about `length` metres long along the roads from `start`, using no road twice: a
* finish flag that far along (point to point) or a loop back to the start (a circuit). The
* search prefers carrying on more or less straight, varied by seed. Returns the waypoints
* for the planner (as few as will pin the route to that way round), or null if no such
* route was found.
*/
export function generateRoute(graph: RoadGraph, start: RoutePoint, length: number, loop: boolean, seed: number): RoutePoint[] | null {
// As twisty as it can be while still the length asked for: if a route full of turns
// runs out of roads first, a straighter one.
let best: Step[] | null = null;
let bestErr = Infinity;
for (const twist of [1, 0.6, 0.25]) {
const steps = loop ? searchLoop(graph, start, length, seed, twist) : searchLine(graph, start, length, seed, twist);
if (!steps) continue;
const got = steps.reduce((sum, st) => sum + Math.abs(st.t1 - st.t0), 0);
const err = Math.abs(got - length) / length;
if (err < bestErr) {
best = steps;
bestErr = err;
}
if (err < 0.08) break;
}
return best ? pin(graph, start, best, loop) : null;
}
function seeded(seed: number): () => number {
let a = seed >>> 0 || 1;
return () => {
a = (a + 0x6d2b79f5) >>> 0;
let t = a;
t = Math.imul(t ^ (t >>> 15), t | 1);
t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
};
}
/** How far a route must run on after a turn before it favours turning again (m): corners with straights between, not a staircase. */
const STRAIGHT = 120;
/** The straight run after taking edge ei out of node: on from since if it carries straight on, from nothing if it turns. */
function runOn(graph: RoadGraph, ei: number, node: number, heading: { x: number; z: number }, since: number): number {
const h = leave(graph, ei, node);
const len = graph.edges[ei]!.len;
return h.x * heading.x + h.z * heading.z > 0.75 ? since + len : len;
}
/** Heading leaving a junction along one of its roads (unit vector). */
function leave(graph: RoadGraph, edge: number, node: number): { x: number; z: number } {
const e = graph.edges[edge]!;
const p = pointOnEdge(graph, edge, e.a === node ? 0 : e.len);
const q = pointOnEdge(graph, edge, e.a === node ? Math.min(8, e.len) : Math.max(0, e.len - 8));
const l = Math.hypot(q.x - p.x, q.z - p.z) || 1;
return { x: (q.x - p.x) / l, z: (q.z - p.z) / l };
}
/**
* The ways on from a junction, best first: turning off left or right scores highest (races
* are more fun with corners), carrying straight on less, doubling sharply back lowest, with
* a random shake so different seeds give different routes.
* near (optional) pulls towards a point (home, for a circuit).
*/
function options(graph: RoadGraph, node: number, inHeading: { x: number; z: number }, used: Set<number>, rand: () => number, twist: number, near?: { x: number; z: number; w: number }): number[] {
const n = graph.nodes[node]!;
const scored: [number, number][] = [];
for (const ei of n.edges) {
if (used.has(ei)) continue;
const e = graph.edges[ei]!;
if (e.dead && near) continue;
if (!allowed(graph, ei, e.a === node ? 1 : -1)) continue;
const h = leave(graph, ei, node);
const ahead = h.x * inHeading.x + h.z * inHeading.z;
// twist 1: turns first; less, the more it leans towards carrying straight on.
// (twist below 0: just turned, so carrying straight on comes first.)
let score = (ahead > -0.4 ? (twist >= 0 ? (1 - Math.abs(ahead)) * 2 * twist + ahead * 1.8 * (1 - twist) : ahead * 1.8) : -2) + rand() * 1.2;
if (near) {
const other = graph.nodes[e.a === node ? e.b : e.a]!;
const before = Math.hypot(n.x - near.x, n.z - near.z);
const after = Math.hypot(other.x - near.x, other.z - near.z);
score += ((before - after) / Math.max(40, e.len)) * near.w;
}
scored.push([ei, score]);
}
return scored.sort((a, b) => b[1] - a[1]).map(([ei]) => ei);
}
/** Point to point: a path of edges from the start until `length` is used up, the finish part way along the last. */
function searchLine(graph: RoadGraph, start: RoutePoint, length: number, seed: number, twist: number): Step[] | null {
const rand = seeded(seed);
const e0 = graph.edges[start.edge]!;
let budget = 40000;
const used = new Set<number>([start.edge]);
const steps: Step[] = [];
const go = (node: number, heading: { x: number; z: number }, left: number, since: number): boolean => {
if (--budget < 0) return false;
for (const ei of options(graph, node, heading, used, rand, since < STRAIGHT ? -0.4 : twist)) {
const e = graph.edges[ei]!;
const fromA = e.a === node;
// The finish falls on this stretch: not right at either end of it.
if (left <= e.len - 12 && left >= Math.min(12, e.len / 2)) {
steps.push({ edge: ei, t0: fromA ? 0 : e.len, t1: fromA ? left : e.len - left, from: node });
return true;
}
if (left < e.len) continue;
used.add(ei);
steps.push({ edge: ei, t0: fromA ? 0 : e.len, t1: fromA ? e.len : 0, from: node });
const other = fromA ? e.b : e.a;
const h = leave(graph, ei, other);
if (go(other, { x: -h.x, z: -h.z }, left - e.len, runOn(graph, ei, node, heading, since))) return true;
steps.pop();
used.delete(ei);
}
return false;
};
// Off either way along the start's own road, the longer way first.
const ends = start.t > e0.len - start.t ? [e0.a, e0.b] : [e0.b, e0.a];
for (const end of ends) {
if (!allowed(graph, start.edge, end === e0.a ? -1 : 1)) continue;
const run = end === e0.a ? start.t : e0.len - start.t;
const t1 = end === e0.a ? 0 : e0.len;
if (run >= length) return [{ edge: start.edge, t0: start.t, t1: end === e0.a ? start.t - length : start.t + length, from: -1 }];
steps.length = 0;
steps.push({ edge: start.edge, t0: start.t, t1, from: -1 });
const into = leave(graph, start.edge, end);
if (go(end, { x: -into.x, z: -into.z }, length - run, run)) return steps;
}
return null;
}
/** A circuit: out along the start's road one way, round, and back in along it from the other end. */
function searchLoop(graph: RoadGraph, start: RoutePoint, length: number, seed: number, twist: number): Step[] | null {
const rand = seeded(seed);
const e0 = graph.edges[start.edge]!;
if (e0.a === e0.b || !allowed(graph, start.edge, 1)) return null;
const home = graph.nodes[e0.a]!;
const target = length - e0.len;
const used = new Set<number>([start.edge]);
const steps: Step[] = [];
let best: Step[] | null = null;
let bestErr = Infinity;
let budget = 40000;
const tol = Math.max(80, length * 0.06);
const go = (node: number, heading: { x: number; z: number }, run: number, since: number): boolean => {
if (--budget < 0) return true;
if (node === e0.a) {
const err = Math.abs(run - target);
if (err < bestErr) {
bestErr = err;
best = steps.slice();
}
return err < tol;
}
// Too far out to get home in time.
const nn = graph.nodes[node]!;
if (run + Math.hypot(nn.x - home.x, nn.z - home.z) > target + tol) return false;
const pull = run > target * 0.45 ? { x: home.x, z: home.z, w: 2.5 * (run / target) } : undefined;
for (const ei of options(graph, node, heading, used, rand, since < STRAIGHT ? -0.4 : twist, pull)) {
const e = graph.edges[ei]!;
const fromA = e.a === node;
used.add(ei);
steps.push({ edge: ei, t0: fromA ? 0 : e.len, t1: fromA ? e.len : 0, from: node });
const other = fromA ? e.b : e.a;
const h = leave(graph, ei, other);
if (go(other, { x: -h.x, z: -h.z }, run + e.len, runOn(graph, ei, node, heading, since))) return true;
steps.pop();
used.delete(ei);
}
return false;
};
const into = leave(graph, start.edge, e0.b);
go(e0.b, { x: -into.x, z: -into.z }, 0, e0.len - start.t);
const found = best as Step[] | null;
if (!found || bestErr > length * 0.35) return null;
return [{ edge: start.edge, t0: start.t, t1: e0.len, from: -1 }, ...found, { edge: start.edge, t0: 0, t1: start.t, from: e0.a }];
}
/**
* Waypoints that pin the planner's route (the shortest way between each pair) to the
* steps: from each waypoint, on as far along the steps as the shortest way still follows
* them, then a waypoint there.
*/
function pin(graph: RoadGraph, start: RoutePoint, steps: Step[], loop: boolean): RoutePoint[] {
const way: RoutePoint[] = [start];
const last = steps.length - 1;
// Candidate places: the middle of each whole stretch, and the finish.
const at = (k: number): RoutePoint => {
const st = steps[k]!;
const t = k === last ? st.t1 : (st.t0 + st.t1) / 2;
const p = pointOnEdge(graph, st.edge, t);
return { x: p.x, z: p.z, edge: st.edge, t };
};
// (A circuit's last step ends back at the start, which closes the loop by itself.)
const end = last;
// The way the shortest path from w goes along step k's edge (does it come in by step k's junction, the right way?).
const follows = (i: number, j: number, prevNode: Int32Array, prevEdge: Int32Array, dist: Float64Array): boolean => {
const st = steps[j]!;
const e = graph.edges[st.edge]!;
const q = at(j);
const viaA = dist[e.a]! + q.t;
const viaB = dist[e.b]! + (e.len - q.t);
if ((viaA <= viaB ? e.a : e.b) !== st.from) return false;
// Back from there to the waypoint, edge by edge against the steps.
let node = st.from;
for (let k = j - 1; k > i; k--) {
if (prevNode[node] === -2 || prevEdge[node] !== steps[k]!.edge) return false;
node = prevNode[node]!;
}
return prevNode[node] === -2 && prevEdge[node] === steps[i]!.edge;
};
/** A place on step k, d metres in from where it starts. */
const into = (k: number, d: number): RoutePoint => {
const st = steps[k]!;
const t = st.t0 + Math.sign(st.t1 - st.t0) * Math.min(d, Math.abs(st.t1 - st.t0));
const p = pointOnEdge(graph, st.edge, t);
return { x: p.x, z: p.z, edge: st.edge, t };
};
let i = 0;
let done = false;
while (i < end) {
const { prevNode, prevEdge, dist } = dijkstra(graph, way[way.length - 1]!);
let best = -1;
for (let j = i + 1; j <= end; j++) {
if (!follows(i, j, prevNode, prevEdge, dist)) break;
best = j;
}
if (best < 0) {
// Even the next stretch's middle is quicker reached some other way (a long road whose
// far end is close by another): a waypoint just into it, then on along it.
way.push(into(i + 1, 12));
i++;
continue;
}
if (loop && best === last) {
done = true;
break;
}
way.push(at(best));
i = best;
done = best === last;
}
// Still short of the finish, part way along its stretch: waypoints on along it, close
// enough together that each next one is straight on along the road.
if (!loop && !done) {
const st = steps[last]!;
const from = way[way.length - 1]!.edge === st.edge ? way[way.length - 1]!.t : st.t0;
const run = Math.abs(st.t1 - from);
const n = Math.floor(run / 120);
for (let k = 1; k <= n; k++) {
const t = from + Math.sign(st.t1 - from) * k * 120;
const p = pointOnEdge(graph, st.edge, t);
way.push({ x: p.x, z: p.z, edge: st.edge, t });
}
way.push(at(last));
}
// A circuit wants at least two waypoints after the start to make a loop of.
if (loop && way.length < 3 && steps.length > 3) way.splice(1, 0, at(Math.floor(steps.length / 2)));
return way;
}
