aboutsummaryrefslogtreecommitdiffstats
path: root/source/game/route.odin
blob: 17e04a6f5f54ebf02c84728d6a6871df2121e38d (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
package game

import "core:math"
import "core:math/linalg"
import "core:mem"
import "core:mem/virtual"

Route_Mode :: enum u8 {
	Fastest,
	Greenest,
	Calmest,
}

// Cruise airspeed per mode in m/s (spec).
MODE_AIRSPEED :: [Route_Mode]f32 {
	.Fastest  = 18,
	.Greenest = 11,
	.Calmest  = 13,
}

// Energy model (spec). The battery holds BATTERY_KWH, a ship leaves with BATTERY_START of it.
BATTERY_KWH :: 180
BATTERY_START :: 0.86

// Ground speed rules in m/s (spec): below GROUND_RETRY the ship throttles up by GROUND_RETRY_BOOST, below
// GROUND_MIN even then the edge is blocked.
GROUND_RETRY :: 2.5
GROUND_RETRY_BOOST :: 6
GROUND_MIN :: 1.5

// Path cleanup (spec). String pulling looks at most PULL_WINDOW nodes ahead and accepts a straight line that
// costs at most PULL_TOLERANCE more than the A* path it replaces.
PULL_WINDOW :: 14
PULL_TOLERANCE :: 0.004
// Routes start and end this far above the tower top (docking is at the top + 3 m).
TOWER_ABOVE_M :: 6
CHAIKIN_ITERATIONS :: 3
// Spacing of the final path points, horizontal. The spec's 20 m was for a 5 km map; on Belgium it is the
// heightmap spacing, so the terrain clearance still sees every height cell (#46).
RESAMPLE_KM :: 0.25
// Highest climb or descent per metre flown horizontally.
SLOPE_MAX :: 0.24
TERRAIN_CLEARANCE_M :: 40

// 1 km cells over every point in belgium.bin (x 0.6..285.2 km, y 1.0..236.5 km), one layer per wind layer.
GRID_CELL_KM :: 1
GRID_W :: 286
GRID_H :: 237
GRID_LAYERS :: WIND_LAYERS
GRID_LAYER_CELLS :: GRID_W * GRID_H
GRID_NODES :: GRID_LAYERS * GRID_LAYER_CELLS

// node = layer * GRID_LAYER_CELLS + y * GRID_W + x. Each layer is one contiguous row-major plane,
// so per-layer data (blocked cells, scan animation) can be read as a flat slice.
Node :: distinct u32

// Offsets in cells and layers (x, y, layer): the 8 horizontal directions, then up and down one layer.
GRID_DIRS :: [10][3]int {
	{1, 0, 0},
	{1, 1, 0},
	{0, 1, 0},
	{-1, 1, 0},
	{-1, 0, 0},
	{-1, -1, 0},
	{0, -1, 0},
	{1, -1, 0},
	{0, 0, 1},
	{0, 0, -1},
}

// A cell is blocked in a layer when its highest ground + this margin is above the layer altitude (spec).
TERRAIN_MARGIN_M :: 75
// Ground samples per cell side, 250 m apart including both edges: the spacing of the heightmap, so the
// highest sample is the highest point of the bilinear terrain inside the cell.
TERRAIN_SAMPLES :: 5
MAX_NO_FLY :: 8
MAX_GUST_ZONES :: 4
// Route end points snap to the closest free node at most this many cells away from the hub.
FREE_NODE_CELLS :: 5

GRID_BLOCKED_WORDS :: (GRID_NODES + 63) / 64

// A circle on the map, closed from the ground up to ceiling. radius 0 marks an unused slot,
// so a zeroed array holds no zones.
No_Fly_Zone :: struct {
	center:  [2]f32, // km
	radius:  f32, // km
	ceiling: f32, // m, every layer below it is blocked
}

// A gust cell reported in flight. Closed at every altitude: the spec gives a reported zone only a
// centre and a radius, no ceiling. radius 0 marks an unused slot.
Gust_Zone :: struct {
	center: [2]f32, // km
	radius: f32, // km
}

// Search state per node, fixed size inside World: allocated once with it, reused by every route.
// cost, parent and slot of a node only count when visit[node] == search, so a new route bumps search
// instead of clearing 4.9 MB. Zero is valid: no node has been visited yet, the open heap is empty,
// the blocked set is not built.
Grid :: struct {
	search:        u32,
	heap_len:      u32,
	visit:         [GRID_NODES]u32,
	cost:          [GRID_NODES]f32, // from the start along the best path so far, unit of the mode
	parent:        [GRID_NODES]Node,
	slot:          [GRID_NODES]u32, // index in heap while open, HEAP_CLOSED once expanded
	heap:          [GRID_NODES]Heap_Item, // binary min-heap on f, the open set of A*
	// Nodes in the order the last route expanded them, for the scan animation: expanded[:expanded_len].
	// An expanded node is never reopened (see grid_estimate), so every node fits at most once.
	expanded:      [GRID_NODES]Node,
	expanded_len:  u32,
	// Bit n set: node n can not be entered. terrain is the edge ring and the cells too close to the ground,
	// blocked is terrain plus blocked_zones and blocked_gusts. Two sets because terrain costs 1.7M height_at
	// calls and only changes with the library (game_hot_reloaded clears terrain_built), the zones change
	// at runtime.
	terrain:       [GRID_BLOCKED_WORDS]u64,
	blocked:       [GRID_BLOCKED_WORDS]u64,
	blocked_zones: [MAX_NO_FLY]No_Fly_Zone,
	blocked_gusts: [MAX_GUST_ZONES]Gust_Zone,
	// Connected free region of each node (A* steps), 0 for a blocked node. Built with blocked.
	region:        [GRID_NODES]u32,
	// wind_at and gust_at at every node centre and cloud_at at every cell centre (cloud cover has no layers)
	// for weather_hour, shared by the three modes and by every route in that hour. Rebuilt when the hour or
	// its forecast differs from the copy it was built from. Zero is a valid cache: a calm, clear hour 0.
	wind:          [GRID_NODES][2]f32,
	gust:          [GRID_NODES]f32,
	cloud:         [GRID_LAYER_CELLS]f32,
	weather_hour:  int,
	weather_wind:  [WIND_LAYERS][WEATHER_CELLS][2]f32,
	weather_gust:  [WIND_LAYERS][WEATHER_CELLS]f32,
	weather_cloud: [WEATHER_CELLS]f32,
	terrain_built: bool,
	blocked_built: bool,
	// Other cars near each node (traffic_build): a node with TRAFFIC_MIN_CARS or more is a traffic jam and
	// costs more to cross. traffic_any = some node has a jam, so the cost needs a look at all.
	traffic:       [GRID_NODES]u8,
	traffic_any:   bool,
}

// Traffic jams (Lars, 2026-11-21: many cars close together is a jam). Each other flying car (w.others) counts
// for the nodes within TRAFFIC_RADIUS_KM in its own layer; cars on the road below do not block the sky. From TRAFFIC_MIN_CARS on, crossing a node costs
// 1 + TRAFFIC_COST_PER_CAR per car over the minimum, at most TRAFFIC_MAX_FACTOR times as much. Never cheaper,
// so the A* estimate stays a lower bound. Our values, not from the spec.
TRAFFIC_RADIUS_KM :: 1.0
TRAFFIC_MIN_CARS :: 4
TRAFFIC_COST_PER_CAR :: 0.5
TRAFFIC_MAX_FACTOR :: 4.0

traffic_factor :: proc(cars: u8) -> f32 {
	if cars < TRAFFIC_MIN_CARS do return 1
	return min(1 + TRAFFIC_COST_PER_CAR * f32(cars - TRAFFIC_MIN_CARS + 1), TRAFFIC_MAX_FACTOR)
}

// Counts the other cars around every node. Cleared and rebuilt per route: a few hundred cars at most.
traffic_build :: proc(w: ^World, g: ^Grid) {
	if g.traffic_any || w.other_count > 0 do g.traffic = {}
	g.traffic_any = false
	R := int(math.ceil(f32(TRAFFIC_RADIUS_KM) / GRID_CELL_KM))
	for o in w.others[:w.other_count] {
		if o.on_road do continue
		layer := layer_at(o.alt)
		cx, cy := int(o.pos.x / GRID_CELL_KM), int(o.pos.y / GRID_CELL_KM)
		for y in max(cy - R, 0) ..= min(cy + R, GRID_H - 1) {
			for x in max(cx - R, 0) ..= min(cx + R, GRID_W - 1) {
				centre := ([2]f32{f32(x), f32(y)} + 0.5) * GRID_CELL_KM
				if linalg.length(centre - o.pos) > TRAFFIC_RADIUS_KM do continue
				n := grid_node({x, y, layer})
				if g.traffic[n] < 255 do g.traffic[n] += 1
				if g.traffic[n] >= TRAFFIC_MIN_CARS do g.traffic_any = true
			}
		}
	}
}

// Cars within radius_km of pos that share the way: on the road too, or flying in the same layer. For the
// ship's own speed in a jam and the jam warning.
traffic_near :: proc(w: ^World, pos: [2]f32, alt: f32, on_road: bool, radius_km: f32) -> int {
	count := 0
	layer := layer_at(alt)
	for o in w.others[:w.other_count] {
		if o.on_road != on_road || (!on_road && layer_at(o.alt) != layer) do continue
		if linalg.length(o.pos - pos) <= radius_km do count += 1
	}
	return count
}

// f = cost + estimate to the goal, the key of the open heap.
Heap_Item :: struct {
	f: f32,
	n: Node,
}

HEAP_CLOSED :: max(u32)

// On an open 8-direction grid thousands of nodes have (almost) the same f, so plain A* expands a wide
// band around the line: 35k nodes corner to corner. Weighting the estimate a little prefers nodes
// closer to the goal: 286 nodes, at most 0.1 % longer than the cheapest path.
ESTIMATE_TIE_BREAK :: 1.001

grid_node :: proc(c: [3]int) -> Node {
	return Node(c.z * GRID_LAYER_CELLS + c.y * GRID_W + c.x)
}

// Inverse of grid_node: x, y, layer.
grid_cell :: proc(n: Node) -> [3]int {
	i := int(n)
	return {i % GRID_W, i / GRID_W % GRID_H, i / GRID_LAYER_CELLS}
}

// pos: x km, y km, altitude m. Snaps to the cell under (x, y) and the layer closest to the altitude.
// ok = false outside the grid or for NaN.
grid_node_at :: proc(pos: [3]f32) -> (n: Node, ok: bool) {
	cx := pos.x / GRID_CELL_KM
	cy := pos.y / GRID_CELL_KM
	// Written as !(inside) so a NaN coordinate fails the test.
	if !(cx >= 0 && cx < GRID_W && cy >= 0 && cy < GRID_H) || math.is_nan(pos.z) do return 0, false

	alt := LAYER_ALT
	layer := 0
	for a, i in alt {
		if abs(pos.z - a) < abs(pos.z - alt[layer]) do layer = i
	}
	return grid_node({int(cx), int(cy), layer}), true
}

// Centre of the node's cell in km and its layer altitude in m.
grid_node_pos :: proc(n: Node) -> [3]f32 {
	c := grid_cell(n)
	alt := LAYER_ALT
	return {(f32(c.x) + 0.5) * GRID_CELL_KM, (f32(c.y) + 0.5) * GRID_CELL_KM, alt[c.z]}
}

// The node one step d (an entry of GRID_DIRS) away from n. ok = false past the edge of the grid.
grid_neighbor :: proc(n: Node, d: [3]int) -> (next: Node, ok: bool) {
	c := grid_cell(n) + d
	if c.x < 0 || c.x >= GRID_W || c.y < 0 || c.y >= GRID_H || c.z < 0 || c.z >= GRID_LAYERS do return 0, false
	return grid_node(c), true
}

grid_blocked :: proc(g: ^Grid, n: Node) -> bool {
	return g.blocked[n >> 6] & (1 << (u32(n) & 63)) != 0
}

// The free node closest to pos (x km, y km) within FREE_NODE_CELLS cells, lowest free layer of that cell
// (spec: start and goal are the closest free node to the hub, lowest layer first). The altitude in pos
// is not used. ok = false when pos lies outside the grid or every node around it is blocked.
grid_free_node_near :: proc(g: ^Grid, pos: [3]f32) -> (n: Node, ok: bool) {
	hub := grid_cell(grid_node_at(pos) or_return)
	best := math.inf_f32(1)
	for y in max(hub.y - FREE_NODE_CELLS, 0) ..= min(hub.y + FREE_NODE_CELLS, GRID_H - 1) {
		for x in max(hub.x - FREE_NODE_CELLS, 0) ..= min(hub.x + FREE_NODE_CELLS, GRID_W - 1) {
			for layer in 0 ..< GRID_LAYERS {
				c := grid_node({x, y, layer})
				if grid_blocked(g, c) do continue
				if d := linalg.length2(grid_node_pos(c).xy - pos.xy); d < best {
					best, n, ok = d, c, true
				}
				break
			}
		}
	}
	return
}

// from, to: x km, y km, altitude m. Hub i is at w.m.hubs[i].pos, its tower top at HUB_TOWER_M.
// Returns the path in the same units, or ok = false when no safe route exists with this wind
// or an end point has no free node near it (outside the grid, in a no-fly or gust zone).
// The path lives in the route arena until the next route call.
route :: proc(w: ^World, from, to: [3]f32, mode: Route_Mode, hour: int) -> (path: [][3]f32, ok: bool) {
	virtual.arena_free_all(&w.route_mem)

	g := &w.grid
	g.search += 1
	if g.search == 0 {
		// Wrapped after 2^32 routes: stale stamps could match the new search, so clear them once.
		g.visit = {}
		g.search = 1
	}
	g.heap_len = 0
	g.expanded_len = 0
	traffic_build(w, g)

	alt := LAYER_ALT
	if !g.terrain_built {
		g.terrain = {}
		count: [GRID_LAYERS]int
		for y in 0 ..< GRID_H {
			for x in 0 ..< GRID_W {
				ground := math.inf_f32(-1)
				for sy in 0 ..< TERRAIN_SAMPLES {
					for sx in 0 ..< TERRAIN_SAMPLES {
						step :: f32(GRID_CELL_KM) / (TERRAIN_SAMPLES - 1)
						sample := [2]f32{f32(x), f32(y)} * GRID_CELL_KM + [2]f32{f32(sx), f32(sy)} * step
						ground = max(ground, height_at(w, sample.x, sample.y))
					}
				}
				// The spec closes the outer ring of cells, so no path runs along the edge of the data. Routes stay
				// over Belgium too (nasr, 2026-11-21): a cell whose centre is abroad is closed on every layer.
				centre := ([2]f32{f32(x), f32(y)} + 0.5) * GRID_CELL_KM
				closed := x == 0 || y == 0 || x == GRID_W - 1 || y == GRID_H - 1
				closed ||= !belgium_inside(w, centre.x, centre.y)
				for layer in 0 ..< GRID_LAYERS {
					// Written as !(free) so a NaN height blocks the cell.
					if closed || !(ground + TERRAIN_MARGIN_M <= alt[layer]) {
						n := grid_node({x, y, layer})
						g.terrain[n >> 6] |= 1 << (u32(n) & 63)
						count[layer] += 1
					}
				}
			}
		}
		g.terrain_built = true
		g.blocked_built = false
		logf(w, "route", "terrain set built: %v of %d nodes per layer blocked", count, GRID_LAYER_CELLS)
	}

	if !g.blocked_built || g.blocked_zones != w.no_fly || g.blocked_gusts != w.gust_zones {
		// Not rebuilt per forecast hour: neither terrain nor the zones depend on it.
		g.blocked = g.terrain
		g.blocked_zones = w.no_fly
		g.blocked_gusts = w.gust_zones
		g.blocked_built = true
		// A gust zone blocks like a no-fly zone without a ceiling.
		zones: [MAX_NO_FLY + MAX_GUST_ZONES]No_Fly_Zone
		copy(zones[:], g.blocked_zones[:])
		for z, i in g.blocked_gusts do zones[MAX_NO_FLY + i] = {z.center, z.radius, math.inf_f32(1)}
		no_fly, gusts, added := 0, 0, 0
		for z, i in zones {
			// Written as !(valid) so NaN and Inf skip the zone, radius 0 is an unused slot.
			if !(z.radius > 0 && z.radius < 1e6 && abs(z.center.x) < 1e6 && abs(z.center.y) < 1e6) do continue
			if i < MAX_NO_FLY {
				no_fly += 1
			} else {
				gusts += 1
			}
			lo := linalg.floor((z.center - z.radius) / GRID_CELL_KM)
			hi := linalg.floor((z.center + z.radius) / GRID_CELL_KM)
			for y in max(int(lo.y), 0) ..= min(int(hi.y), GRID_H - 1) {
				for x in max(int(lo.x), 0) ..= min(int(hi.x), GRID_W - 1) {
					// Overlap, not the cell centre: a zone smaller than a cell must still block it.
					cell := [2]f32{f32(x), f32(y)} * GRID_CELL_KM
					closest := linalg.clamp(z.center, cell, cell + GRID_CELL_KM)
					if linalg.length2(closest - z.center) >= z.radius * z.radius do continue
					for layer in 0 ..< GRID_LAYERS {
						if !(alt[layer] < z.ceiling) do continue
						n := grid_node({x, y, layer})
						bit := u64(1) << (u32(n) & 63)
						if g.blocked[n >> 6] & bit == 0 do added += 1
						g.blocked[n >> 6] |= bit
					}
				}
			}
		}

		// Label the connected free regions: a route between two regions fails at once, instead of
		// expanding every node reachable from the start (a walled-in hub took 33 ms with -o:speed).
		// The open heap is free between routes, so it serves as the flood fill stack.
		g.region = {}
		regions: u32 = 0
		dirs := GRID_DIRS
		for i in 0 ..< GRID_NODES {
			first := Node(i)
			if g.region[first] != 0 || grid_blocked(g, first) do continue
			regions += 1
			g.region[first] = regions
			g.heap[0].n = first
			top := 1
			for top > 0 {
				top -= 1
				c := grid_cell(g.heap[top].n)
				for d in dirs {
					nc := c + d
					if nc.x < 0 || nc.x >= GRID_W || nc.y < 0 || nc.y >= GRID_H do continue
					if nc.z < 0 || nc.z >= GRID_LAYERS do continue
					next := grid_node(nc)
					if g.region[next] != 0 || grid_blocked(g, next) do continue
					g.region[next] = regions
					g.heap[top].n = next
					top += 1
				}
			}
		}
		logf(
			w,
			"route",
			"%d no-fly and %d gust zones block %d nodes beyond the terrain set, %d free regions",
			no_fly,
			gusts,
			added,
			regions,
		)
	}

	start, start_ok := grid_free_node_near(g, from)
	goal, goal_ok := grid_free_node_near(g, to)
	if !start_ok {
		logf(
			w,
			"route",
			"start %v: outside the grid or no free node within %d cells",
			from.xy,
			FREE_NODE_CELLS,
		)
	}
	if !goal_ok {
		logf(w, "route", "goal %v: outside the grid or no free node within %d cells", to.xy, FREE_NODE_CELLS)
	}
	if !start_ok || !goal_ok do return nil, false
	if g.region[start] != g.region[goal] {
		logf(w, "route", "no path from %v to %v: blocked nodes separate them", from.xy, to.xy)
		return nil, false
	}

	h := clamp(hour, 0, FORECAST_HOURS - 1)
	if g.weather_hour != h ||
	   g.weather_wind != w.weather.wind[h] ||
	   g.weather_gust != w.weather.gust[h] ||
	   g.weather_cloud != w.weather.cloud[h] {
		g.weather_hour = h
		g.weather_wind = w.weather.wind[h]
		g.weather_gust = w.weather.gust[h]
		g.weather_cloud = w.weather.cloud[h]
		for y in 0 ..< GRID_H {
			for x in 0 ..< GRID_W {
				p := grid_node_pos(grid_node({x, y, 0}))
				g.cloud[y * GRID_W + x] = cloud_at(w, p.x, p.y, h)
			}
		}
		for layer in 0 ..< GRID_LAYERS {
			for y in 0 ..< GRID_H {
				for x in 0 ..< GRID_W {
					n := grid_node({x, y, layer})
					p := grid_node_pos(n)
					g.wind[n] = wind_at(w, p.x, p.y, layer, h)
					g.gust[n] = gust_at(w, p.x, p.y, layer, h)
				}
			}
		}
	}

	// The A* estimate. Flying l km in grid direction k costs at least l x rate[k]: rate[k] is the mode's
	// cost per km with the strongest tailwind along k anywhere in this hour (the +6 m/s retry included),
	// its calmest gust and its most sun
	// (bilinear sampling never leaves the range of the grid points). The cheapest way to cover a
	// displacement with such moves is a small linear program; any y with y . dir[k] <= rate[k] for every
	// k gives a lower bound y . displacement (LP duality). est holds one such y per 45 degree sector,
	// the edge of the cost polygon over that sector, and the estimate is the largest y . displacement.
	// Each y alone never overestimates an edge, so the estimate stays consistent.
	est: Estimate
	{
		dirs := GRID_DIRS
		airspeeds := MODE_AIRSPEED
		v := airspeeds[mode]
		wind_max, gust_min, cloud_min: f32 = 0, 1, 1
		for &layer in g.weather_wind do for wv in layer do wind_max = max(wind_max, linalg.length(wv))
		for &layer in g.weather_gust do for gv in layer do gust_min = min(gust_min, gv)
		for c in g.weather_cloud do cloud_min = min(cloud_min, c)
		// Bilinear sampling stays between the grid values, so no edge gets more sun than solar_max.
		solar_max := solar_kw(cloud_min)
		unit: [8][2]f32
		rate: [8]f32
		for k in 0 ..< 8 {
			unit[k] = linalg.normalize([2]f32{f32(dirs[k].x), f32(dirs[k].y)})
			tail := math.inf_f32(-1)
			for &layer in g.weather_wind do for wv in layer do tail = max(tail, linalg.dot(wv, unit[k]))
			// Ground speed along k is at most the airspeed plus the best tailwind along k. Written as
			// !(headway) so NaN gives an infinite rate: no move that way, no constraint.
			rate[k] =
				v + tail > 0 ? mode_flight_cost(mode, v, v + tail, gust_min, solar_max, 1) : math.inf_f32(1)
			// The +6 m/s retry only happens where the ground speed at v, at least v - wind_max, is below
			// GROUND_RETRY; sqrt(x + k) <= sqrt(x) + sqrt(k) bounds what it adds (see ground_speed).
			if wind_max > v - GROUND_RETRY {
				boost := v + GROUND_RETRY_BOOST
				boost_ground := min(boost + tail, GROUND_RETRY + math.sqrt(boost * boost - v * v))
				if boost_ground > 0 {
					rate[k] = min(
						rate[k],
						mode_flight_cost(mode, boost, boost_ground, gust_min, solar_max, 1),
					)
				}
			}
		}
		for sector in 0 ..< 8 {
			// The bisector of the sector, the y that bounds it best among the valid ones.
			mid := unit[sector] + unit[(sector + 1) % 8]
			best: f32 = 0
			for a in 0 ..< 8 {
				for b in a + 1 ..< 8 {
					// y . unit[a] = rate[a] and y . unit[b] = rate[b], solved by Cramer's rule.
					det := unit[a].x * unit[b].y - unit[a].y * unit[b].x
					if abs(det) < 1e-3 || math.is_inf(rate[a]) || math.is_inf(rate[b]) do continue
					y := [2]f32 {
						(rate[a] * unit[b].y - rate[b] * unit[a].y) / det,
						(unit[a].x * rate[b] - unit[b].x * rate[a]) / det,
					}
					valid := true
					for k in 0 ..< 8 do if linalg.dot(y, unit[k]) > rate[k] * 1.0001 do valid = false
					if valid && linalg.dot(y, mid) > best {
						best = linalg.dot(y, mid)
						est.y[sector] = y / 1.0001
					}
				}
			}
		}
		est.per_layer = math.inf_f32(1)
		for l in 1 ..< GRID_LAYERS {
			climb := alt[l] - alt[l - 1]
			est.per_layer = min(est.per_layer, mode_climb_cost(mode, climb), mode_climb_cost(mode, -climb))
		}
	}
	g.visit[start] = g.search
	g.cost[start] = 0
	g.parent[start] = start
	g.slot[start] = 0
	g.heap_len = 1
	grid_heap_up(g, start, grid_estimate(start, goal, &est) * ESTIMATE_TIE_BREAK)

	dirs := GRID_DIRS
	// Per direction: the node index step, the unit vector and the length of a horizontal step, so the
	// loop does no division per neighbour.
	steps: [len(GRID_DIRS)]int
	unit: [len(GRID_DIRS)][2]f32
	km: [len(GRID_DIRS)]f32
	for d, k in dirs {
		steps[k] = d.z * GRID_LAYER_CELLS + d.y * GRID_W + d.x
		track := [2]f32{f32(d.x), f32(d.y)} * GRID_CELL_KM
		km[k] = linalg.length(track)
		if km[k] > 0 do unit[k] = track / km[k]
	}
	for g.heap_len > 0 {
		n := g.heap[0].n
		g.slot[n] = HEAP_CLOSED
		g.expanded[g.expanded_len] = n
		g.expanded_len += 1
		g.heap_len -= 1
		if g.heap_len > 0 {
			last := g.heap[g.heap_len]
			i: u32 = 0
			for {
				c := 2 * i + 1
				if c >= g.heap_len do break
				if c + 1 < g.heap_len && g.heap[c + 1].f < g.heap[c].f do c += 1
				if g.heap[c].f >= last.f do break
				g.heap[i] = g.heap[c]
				g.slot[g.heap[i].n] = i
				i = c
			}
			g.heap[i] = last
			g.slot[last.n] = i
		}

		if n == goal {
			route_alloc := virtual.arena_allocator(&w.route_mem)
			err: mem.Allocator_Error

			// The A* nodes from start to goal.
			count := 1
			for p := goal; p != start; p = g.parent[p] do count += 1
			nodes: []Node
			nodes, err = make([]Node, count, route_alloc)
			if err != nil do return nil, false
			{
				i := count - 1
				for p := goal;; p = g.parent[p] {
					nodes[i] = p
					if p == start do break
					i -= 1
				}
			}

			// Cost-aware string pulling (spec): from each kept node jump to the farthest node at most
			// PULL_WINDOW nodes ahead whose straight line stays in free cells of the same layer and costs at
			// most PULL_TOLERANCE more than the A* path between them. Kept nodes are compacted in place.
			kept := 1
			for i := 0; i < len(nodes) - 1; {
				best := i + 1
				a := grid_node_pos(nodes[i])
				layer := grid_cell(nodes[i]).z
				for j in i + 1 ..= min(i + PULL_WINDOW, len(nodes) - 1) {
					if grid_cell(nodes[j]).z != layer do break
					if j == i + 1 do continue
					limit := (g.cost[nodes[j]] - g.cost[nodes[i]]) * (1 + PULL_TOLERANCE)
					straight, free := line_cost(g, a, grid_node_pos(nodes[j]), mode)
					if free && straight <= limit do best = j
				}
				nodes[kept] = nodes[best]
				kept += 1
				i = best
			}

			// Start and end above the tower tops (spec). from.z and to.z are the tops. The ramp point between
			// tower and path lies halfway to the first (last) node, at that node's altitude (#45).
			points: [][3]f32
			points, err = make([][3]f32, kept + 4, route_alloc)
			if err != nil do return nil, false
			first := grid_node_pos(nodes[0])
			last := grid_node_pos(nodes[kept - 1])
			points[0] = {from.x, from.y, from.z + TOWER_ABOVE_M}
			points[1] = {(from.x + first.x) * 0.5, (from.y + first.y) * 0.5, first.z}
			for node, i in nodes[:kept] do points[i + 2] = grid_node_pos(node)
			points[kept + 2] = {(to.x + last.x) * 0.5, (to.y + last.y) * 0.5, last.z}
			points[kept + 3] = {to.x, to.y, to.z + TOWER_ABOVE_M}

			// Chaikin smoothing (spec): every segment becomes its points at 1/4 and 3/4, the end points stay
			// on the towers. Linear in each coordinate, so km and m can share a point.
			for _ in 0 ..< CHAIKIN_ITERATIONS {
				smooth: [][3]f32
				smooth, err = make([][3]f32, 2 * len(points), route_alloc)
				if err != nil do return nil, false
				smooth[0] = points[0]
				for i in 0 ..< len(points) - 1 {
					smooth[2 * i + 1] = points[i] * 0.75 + points[i + 1] * 0.25
					smooth[2 * i + 2] = points[i] * 0.25 + points[i + 1] * 0.75
				}
				smooth[len(smooth) - 1] = points[len(points) - 1]
				points = smooth
			}

			// Resample every RESAMPLE_KM of horizontal distance (spec), the last point is the end tower.
			total: f32
			for i in 1 ..< len(points) do total += linalg.length(points[i].xy - points[i - 1].xy)
			path, err = make([][3]f32, max(int(math.ceil(total / RESAMPLE_KM)), 1) + 1, route_alloc)
			if err != nil do return nil, false
			{
				seg := 0
				seg_start: f32 = 0 // horizontal distance from the start to points[seg]
				for &p, k in path[:len(path) - 1] {
					s := f32(k) * RESAMPLE_KM
					for seg < len(points) - 2 {
						seg_km := linalg.length(points[seg + 1].xy - points[seg].xy)
						if seg_start + seg_km > s do break
						seg_start += seg_km
						seg += 1
					}
					seg_km := linalg.length(points[seg + 1].xy - points[seg].xy)
					t := seg_km > 0 ? clamp((s - seg_start) / seg_km, 0, 1) : 0
					p = linalg.lerp(points[seg], points[seg + 1], t)
				}
				path[len(path) - 1] = points[len(points) - 1]
			}

			// Slope limit (spec): a forward pass caps the climb, a backward pass the descent, both only
			// lower points, the towers stay. Then keep TERRAIN_CLEARANCE_M above the ground.
			for i in 1 ..< len(path) - 1 {
				m := linalg.length(path[i].xy - path[i - 1].xy) * 1000
				path[i].z = min(path[i].z, path[i - 1].z + SLOPE_MAX * m)
			}
			for i := len(path) - 2; i > 0; i -= 1 {
				m := linalg.length(path[i + 1].xy - path[i].xy) * 1000
				path[i].z = min(path[i].z, path[i + 1].z + SLOPE_MAX * m)
			}
			for &p in path do p.z = max(p.z, height_at(w, p.x, p.y) + TERRAIN_CLEARANCE_M)
			return path, true
		}

		c := grid_cell(n)
		for d, k in dirs {
			nc := c + d
			if nc.z < 0 || nc.z >= GRID_LAYERS do continue
			// The outer ring of cells is always blocked, so a free node never steps past the edge.
			next := Node(int(n) + steps[k])
			if grid_blocked(g, next) do continue
			// Edge cost in the unit of the mode: seconds for Fastest and Calmest, kWh for Greenest.
			// Wind, gust and cloud cover are the mean of the two node centres, the weather grid is 40 km
			// so that is the value halfway.
			step: f32
			if d.z != 0 {
				step = mode_climb_cost(mode, alt[nc.z] - alt[c.z])
			} else {
				wind := (g.wind[n] + g.wind[next]) * 0.5
				gust := (g.gust[n] + g.gust[next]) * 0.5
				cloud := (g.cloud[u32(n) % GRID_LAYER_CELLS] + g.cloud[u32(next) % GRID_LAYER_CELLS]) * 0.5
				// ok = false: blocked by the ground speed rules.
				step = flight_cost(mode, wind, unit[k], gust, cloud, km[k]) or_continue
			}
			if g.traffic_any do step *= traffic_factor(g.traffic[next])
			cost := g.cost[n] + step
			if g.visit[next] == g.search {
				if g.slot[next] == HEAP_CLOSED || cost >= g.cost[next] do continue
			} else {
				g.visit[next] = g.search
				g.slot[next] = g.heap_len
				g.heap_len += 1
			}
			g.cost[next] = cost
			g.parent[next] = n
			grid_heap_up(g, next, cost + grid_estimate(next, goal, &est) * ESTIMATE_TIE_BREAK)
		}
	}
	logf(
		w,
		"route",
		"no path from %v to %v, every free node reachable from the start was searched",
		from.xy,
		to.xy,
	)
	return nil, false
}

// Lower bound on the cost from a to b per mode and hour, built at the start of route().
Estimate :: struct {
	y:         [8][2]f32, // cost per km of displacement, one bounding vector per 45 degree sector
	per_layer: f32, // cheapest layer change
}

// Lower bound on the cost from a to b: the largest y . displacement (km) plus the layer changes
// times the cheapest one. Never above the real cost and consistent, so an expanded node is never
// reopened.
grid_estimate :: proc(a, b: Node, est: ^Estimate) -> f32 {
	ca := grid_cell(a)
	cb := grid_cell(b)
	d := [2]f32{f32(cb.x - ca.x), f32(cb.y - ca.y)} * GRID_CELL_KM
	flat: f32 = 0
	for y in est.y do flat = max(flat, linalg.dot(y, d))
	return flat + f32(abs(ca.z - cb.z)) * est.per_layer
}

// Cost of the straight line from a to b (x km, y km, a layer altitude in m) in that layer, in the unit of the
// mode. Walks the cells the line crosses (Amanatides-Woo): each piece costs as an edge with the weather of
// its cell. free = false when a crossed cell is blocked or a piece is blocked by the ground speed rules.
// A line through a cell corner does not enter the two cells beside it, the same as a diagonal A* step.
line_cost :: proc(g: ^Grid, a, b: [3]f32, mode: Route_Mode) -> (cost: f32, free: bool) {
	start := grid_node_at(a) or_return
	layer := grid_cell(start).z
	cell := grid_cell(start).xy
	track := b.xy - a.xy
	total := linalg.length(track)
	if total == 0 do return 0, !grid_blocked(g, start)
	dir := track / total

	// Distance along the line to the next cell boundary in x and y, and between two boundaries.
	step, next, delta: [2]f32
	for axis in 0 ..< 2 {
		step[axis] = dir[axis] > 0 ? 1 : -1
		next[axis] = math.inf_f32(1)
		delta[axis] = math.inf_f32(1)
		if dir[axis] != 0 {
			edge := (f32(cell[axis]) + (dir[axis] > 0 ? 1 : 0)) * GRID_CELL_KM
			next[axis] = (edge - a[axis]) / dir[axis]
			delta[axis] = GRID_CELL_KM / abs(dir[axis])
		}
	}

	// Two boundaries closer than this along the line are one corner.
	CORNER_KM :: 1e-4
	done: f32 = 0
	for {
		if cell.x < 0 || cell.x >= GRID_W || cell.y < 0 || cell.y >= GRID_H do return 0, false
		n := grid_node({cell.x, cell.y, layer})
		if grid_blocked(g, n) do return 0, false
		reach := min(next.x, next.y, total)
		cloud := g.cloud[u32(n) % GRID_LAYER_CELLS]
		piece := flight_cost(mode, g.wind[n], dir, g.gust[n], cloud, reach - done) or_return
		cost += g.traffic_any ? piece * traffic_factor(g.traffic[n]) : piece
		if reach >= total do return cost, true
		done = reach
		if abs(next.x - next.y) < CORNER_KM {
			cell += {int(step.x), int(step.y)}
			next += delta
		} else if next.x < next.y {
			cell.x += int(step.x)
			next.x += delta.x
		} else {
			cell.y += int(step.y)
			next.y += delta.y
		}
	}
}

// Cost of km flown along the unit track dir through wind (m/s), gust index gust and cloud cover cloud at the
// mode's airspeed, after the ground speed rules (spec). ok = false when they block the flight.
flight_cost :: proc(mode: Route_Mode, wind, dir: [2]f32, gust, cloud, km: f32) -> (cost: f32, ok: bool) {
	airspeed := MODE_AIRSPEED
	v := airspeed[mode]
	ground := ground_speed(v, wind, dir) or_return
	if ground < GROUND_RETRY {
		v += GROUND_RETRY_BOOST
		ground = ground_speed(v, wind, dir) or_return
		if ground < GROUND_MIN do return 0, false
	}
	return mode_flight_cost(mode, v, ground, gust, solar_kw(cloud), km), true
}

// Ground speed in m/s along the unit track dir at airspeed v in wind (spec): the tailwind plus what is left
// of v once it cancels the crosswind. ok = false when the crosswind is stronger than v, also for NaN wind.
ground_speed :: proc(v: f32, wind, dir: [2]f32) -> (ground: f32, ok: bool) {
	cross := wind.x * dir.y - wind.y * dir.x
	rest := v * v - cross * cross
	if !(rest >= 0) do return 0, false
	return linalg.dot(wind, dir) + math.sqrt(rest), true
}

// Cost of km flown at airspeed v and ground speed ground (m/s) through gust index gust under solar kW of
// sun (spec, per mode). Rises with gust and v, falls with solar (Greenest) and with ground speed, which the
// A* estimate relies on. power_kw is above the strongest sun at every airspeed, so a cost is never negative.
mode_flight_cost :: proc(mode: Route_Mode, v, ground, gust, solar, km: f32) -> f32 {
	dt := km * 1000 / ground
	switch mode {
	case .Fastest:
		return dt
	case .Calmest:
		return dt * (1 + 7 * gust * gust)
	case .Greenest:
		return (power_kw(v, gust) - solar) * dt / 3600 + 0.25 * gust * gust * km
	}
	return 0
}

// Cost of a vertical edge that climbs climb_m metres, negative for a descent (spec).
mode_climb_cost :: proc(mode: Route_Mode, climb_m: f32) -> f32 {
	if mode == .Greenest do return climb_kwh(climb_m) + 0.02
	return 0.2 * abs(climb_m) / 3
}

// Power drawn in kW at airspeed v m/s through gust index gust 0..1 (spec P(v, g)).
power_kw :: proc(v, gust: f32) -> f32 {
	return 3 + 0.0085 * v * v * v + 6 * gust
}

// Solar yield in kW under cloud cover 0..1 (spec S(c)): 9 kW of film at 75 %, overcast takes 78 % of it.
solar_kw :: proc(cloud: f32) -> f32 {
	return 9 * 0.75 * (1 - 0.78 * cloud)
}

// Ballonet energy in kWh to change altitude by climb_m metres, negative for a descent (spec):
// 0.12 kWh per 100 m up, 0.04 kWh per 100 m down.
climb_kwh :: proc(climb_m: f32) -> f32 {
	return climb_m > 0 ? 0.0012 * climb_m : -0.0004 * climb_m
}

// Gives n priority f and moves it up from its slot to its place in the open heap.
// Used both for a newly opened node (slot = the end of the heap) and for a cheaper path to an open one.
grid_heap_up :: proc(g: ^Grid, n: Node, f: f32) {
	i := g.slot[n]
	for i > 0 {
		p := (i - 1) / 2
		if g.heap[p].f <= f do break
		g.heap[i] = g.heap[p]
		g.slot[g.heap[i].n] = i
		i = p
	}
	g.heap[i] = {f, n}
	g.slot[n] = i
}