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
|
package game
import "core:math"
import "core:slice"
import "core:strings"
MAP_MAGIC :: 0x54465244
MAP_VERSION :: 4
MAX_HUBS :: 32
// Docking towers, top = ground + HUB_TOWER_M (spec).
HUB_TOWER_M :: 58
// Every point in belgium.bin lies inside 0..MAP_W_KM x 0..MAP_H_KM (same extent as the routing grid).
// The bake clips lines to it (tools/bake_map has a copy of both).
MAP_W_KM :: 286
MAP_H_KM :: 237
// map_nearest_name looks only at the cells of this grid that its radius touches (tools/bake_map has a copy).
NAME_CELL_KM :: 10
NAME_GRID_W :: (MAP_W_KM + NAME_CELL_KM - 1) / NAME_CELL_KM
NAME_GRID_H :: (MAP_H_KM + NAME_CELL_KM - 1) / NAME_CELL_KM
// Heightmap and hillshade: one sample per HEIGHT_CELL_KM cell, at the cell centre ((x + 0.5) * 0.25 km,
// (y + 0.5) * 0.25 km), row-major, y down. tools/bake_map has a copy.
HEIGHT_CELL_KM :: 0.25
HEIGHT_W :: MAP_W_KM * 4
HEIGHT_H :: MAP_H_KM * 4
#assert(HEIGHT_W * HEIGHT_CELL_KM == MAP_W_KM && HEIGHT_H * HEIGHT_CELL_KM == MAP_H_KM)
Map_Header :: struct {
magic, version: u32,
line_count, point_count, city_count: u32,
hub_count, names_size: u32,
name_cell_count, name_run_count: u32,
area_count, area_point_count: u32,
height_w, height_h: u32,
road_node_count, road_edge_count: u32,
road_point_count: u32,
}
// name, ref: offsets into Map.names (map_name), 0 = none. ref is the OSM road number, e.g. "E40;A10".
Map_Line :: struct {
start, count, kind: u32,
name, ref: u32,
}
// Segments start ..< start + count of line (index of each segment's first point in Map.points), all touching
// one cell of the name index.
Map_Name_Run :: struct {
line, start, count: u32,
}
// One land use polygon as triangles: area_points[start:][:count], 3 points per triangle.
Map_Area :: struct {
start, count, kind: u32,
}
// belgium.bin lists the areas in this order, so water is drawn over the land kinds.
Area_Kind :: enum u32 {
City,
Park,
Farmland,
Marsh,
Beach,
Water,
}
// Road graph (motorway, trunk, primary, secondary and their ramps) for driving on the ground. A node is a
// junction or a dead end; road_edges[first:][:count] are the edges leaving it.
Road_Node :: struct {
pos: [2]f32,
first, count: u32,
}
// road_points[start:][:count] runs from -> to, the first and last point are the nodes. A two-way road has one
// edge per direction; oneway = 1 marks a road that can only be driven this way. kind is a Map_Kind.
// length_km is measured on the unsimplified OSM way.
Road_Edge :: struct {
from, to: u32,
start, count: u32,
length_km: f32,
kind: u32,
oneway: u32,
}
Map_City :: struct {
pos: [2]f32,
name: [32]u8,
}
Map_Hub :: struct {
pos: [2]f32,
name: [32]u8,
}
// belgium.bin lists the lines in this order, so a bigger road is drawn on top of a smaller one.
Map_Kind :: enum u32 {
Border,
River,
Tertiary,
Secondary,
Primary,
Trunk,
Motorway,
}
Map :: struct {
lines: []Map_Line,
points: [][2]f32,
cities: []Map_City,
// Copied, not sliced: a hub id is an index into this fixed array.
hubs: [MAX_HUBS]Map_Hub,
hub_count: int,
// 0-terminated UTF-8 strings, offset 0 is the empty string, the last byte is always 0.
names: []u8,
// Name index: the runs of cell c are name_runs[name_cells[c]:name_cells[c + 1]], c = y * NAME_GRID_W + x.
// Lists every labelled line: a road or river with a name, or a motorway with a ref.
name_cells: []u32,
name_runs: []Map_Name_Run,
// Land use polygons sorted by kind (Area_Kind order), holes dropped (see tools/bake_map).
areas: []Map_Area,
area_points: [][2]f32,
// Ground height in m (Copernicus GLO-90, cell average, sea 0), HEIGHT_W x HEIGHT_H. Read with height_at.
heights: []i16,
// Hillshade of heights, light from the north-west at 45 degrees, 4x vertical exaggeration:
// 128 = flat, 255 = facing the light, 0 = facing away. Same grid as heights.
hillshade: []u8,
road_nodes: []Road_Node,
road_edges: []Road_Edge,
road_points: [][2]f32,
}
// map_nearest_name ranks a line by distance x weight, so a bigger road wins over a smaller one that is a little
// closer: a motorway at 1.6 km beats a tertiary road at 1 km. Rivers rank like primary roads.
NAME_KIND_WEIGHT :: [Map_Kind]f32 {
.Border = 1,
.River = 0.8,
.Tertiary = 1,
.Secondary = 0.9,
.Primary = 0.8,
.Trunk = 0.7,
.Motorway = 0.6,
}
MAP_DATA :: #load("../../assets/belgium.bin")
// Slices belgium.bin, no copies except the hubs. The file is ours but still checked like outside data: every
// block must fit, every index must point inside its block, every coordinate must be finite. A bad file gives
// ok = false and an empty map, never a crash later.
load_map :: proc() -> (m: Map, ok: bool) {
data := MAP_DATA
if len(data) < size_of(Map_Header) do return {}, false
h := (^Map_Header)(raw_data(data))
if h.magic != MAP_MAGIC || h.version != MAP_VERSION || h.hub_count > MAX_HUBS do return {}, false
// The next count elements of T, or nil and bad = true when they run past the end. u64 so a huge count
// cannot wrap.
off := size_of(Map_Header)
bad := false
take :: proc(data: []u8, off: ^int, count: u32, $T: typeid, bad: ^bool) -> []T {
size := u64(count) * size_of(T)
if u64(off^) + size > u64(len(data)) {
bad^ = true
return nil
}
s := ([^]T)(raw_data(data[off^:]))[:count]
off^ += int(size)
return s
}
// x - x is NaN for NaN and +-Inf, 0 otherwise. One compare per point: this runs over ~800k points at
// startup and after every reload.
finite :: proc(p: [2]f32) -> bool {
d := p - p
return d.x == 0 && d.y == 0
}
m.lines = take(data, &off, h.line_count, Map_Line, &bad)
m.points = take(data, &off, h.point_count, [2]f32, &bad)
m.cities = take(data, &off, h.city_count, Map_City, &bad)
hubs := take(data, &off, h.hub_count, Map_Hub, &bad)
m.names = take(data, &off, h.names_size, u8, &bad)
m.name_cells = take(data, &off, h.name_cell_count, u32, &bad)
m.name_runs = take(data, &off, h.name_run_count, Map_Name_Run, &bad)
m.areas = take(data, &off, h.area_count, Map_Area, &bad)
m.area_points = take(data, &off, h.area_point_count, [2]f32, &bad)
if h.height_w != HEIGHT_W || h.height_h != HEIGHT_H do return {}, false
m.heights = take(data, &off, HEIGHT_W * HEIGHT_H, i16, &bad)
m.hillshade = take(data, &off, HEIGHT_W * HEIGHT_H, u8, &bad)
m.road_nodes = take(data, &off, h.road_node_count, Road_Node, &bad)
m.road_edges = take(data, &off, h.road_edge_count, Road_Edge, &bad)
m.road_points = take(data, &off, h.road_point_count, [2]f32, &bad)
if bad || off != len(data) do return {}, false
if len(m.names) == 0 || m.names[0] != 0 || m.names[len(m.names) - 1] != 0 do return {}, false
for l in m.lines {
if u64(l.start) + u64(l.count) > u64(len(m.points)) || l.kind > u32(max(Map_Kind)) do return {}, false
if int(l.name) >= len(m.names) || int(l.ref) >= len(m.names) do return {}, false
}
if len(m.name_cells) != NAME_GRID_W * NAME_GRID_H + 1 || m.name_cells[0] != 0 do return {}, false
if int(m.name_cells[len(m.name_cells) - 1]) != len(m.name_runs) do return {}, false
for i in 1 ..< len(m.name_cells) do if m.name_cells[i] < m.name_cells[i - 1] do return {}, false
for r in m.name_runs {
if int(r.line) >= len(m.lines) do return {}, false
l := m.lines[r.line]
// A segment k uses points k and k + 1, both inside the line.
if r.start < l.start || u64(r.start) + u64(r.count) >= u64(l.start) + u64(l.count) do return {}, false
}
for a in m.areas {
if u64(a.start) + u64(a.count) > u64(len(m.area_points)) || a.count % 3 != 0 do return {}, false
if a.kind > u32(max(Area_Kind)) do return {}, false
}
for p in m.area_points do if !finite(p) do return {}, false
for n, i in m.road_nodes {
if !finite(n.pos) || u64(n.first) + u64(n.count) > u64(len(m.road_edges)) do return {}, false
for e in m.road_edges[n.first:][:n.count] do if int(e.from) != i do return {}, false
}
for e in m.road_edges {
if int(e.to) >= len(m.road_nodes) || int(e.from) >= len(m.road_nodes) || e.count < 2 do return {}, false
if u64(e.start) + u64(e.count) > u64(len(m.road_points)) do return {}, false
if !(e.length_km >= 0 && e.length_km < 1e4) || e.kind > u32(max(Map_Kind)) || e.oneway > 1 do return {}, false
}
for p in m.road_points do if !finite(p) do return {}, false
for p in m.points do if !finite(p) do return {}, false
for c in m.cities do if !finite(c.pos) do return {}, false
for hub in hubs do if !finite(hub.pos) do return {}, false
m.hub_count = len(hubs)
copy(m.hubs[:], hubs)
return m, true
}
// The string at offset in m.names, "" for 0 or a bad offset. It points into the #load data: valid until the
// next hot reload, so copy it before keeping it in World.
map_name :: proc(m: ^Map, offset: u32) -> string {
if int(offset) >= len(m.names) do return ""
return strings.truncate_to_byte(string(m.names[offset:]), 0)
}
// The label of the line nearest to pos within radius_km (see NAME_KIND_WEIGHT): its name, or for a motorway
// without one the first part of its ref ("E40" of "E40;A10"). Rivers and roads from tertiary up, never the
// border. The string points into the #load data like map_name. ok = false when nothing is in range.
// Visits the index cells the radius touches, so the cost grows with radius^2: ~10 km is what it is made for.
map_nearest_name :: proc(
w: ^World,
pos: [2]f32,
radius_km: f32,
) -> (
name: string,
kind: Map_Kind,
ok: bool,
) {
m := &w.m
if len(m.name_cells) != NAME_GRID_W * NAME_GRID_H + 1 do return
// Also false for NaN, so the cell range below is never built from NaN.
if !(radius_km > 0) || !(abs(pos.x) < 1e6) || !(abs(pos.y) < 1e6) do return
x0 := max(int(math.floor((pos.x - radius_km) / NAME_CELL_KM)), 0)
x1 := min(int(math.floor((pos.x + radius_km) / NAME_CELL_KM)), NAME_GRID_W - 1)
y0 := max(int(math.floor((pos.y - radius_km) / NAME_CELL_KM)), 0)
y1 := min(int(math.floor((pos.y + radius_km) / NAME_CELL_KM)), NAME_GRID_H - 1)
// Cells nearest first: once the best score is below what any line in the next cell could reach (its
// distance x the smallest weight), the rest is skipped. A city cell holds thousands of segments, so in a
// city usually only the cell under pos is read.
Cell :: struct {
d2: f32,
c: int,
}
cells: [NAME_GRID_W * NAME_GRID_H]Cell
n := 0
for y in y0 ..= y1 {
for x in x0 ..= x1 {
dx := max(f32(x) * NAME_CELL_KM - pos.x, 0, pos.x - f32(x + 1) * NAME_CELL_KM)
dy := max(f32(y) * NAME_CELL_KM - pos.y, 0, pos.y - f32(y + 1) * NAME_CELL_KM)
cells[n] = {dx * dx + dy * dy, y * NAME_GRID_W + x}
n += 1
}
}
slice.sort_by(cells[:n], proc(a, b: Cell) -> bool {return a.d2 < b.d2})
// Scores are squared (distance^2 x weight^2), no square root per line.
weights := NAME_KIND_WEIGHT
min_w2 := max(f32)
for k in Map_Kind.River ..= Map_Kind.Motorway do min_w2 = min(min_w2, weights[k] * weights[k])
best_line := -1
best_score := max(f32)
r2 := radius_km * radius_km
for cell in cells[:n] {
if cell.d2 > r2 || cell.d2 * min_w2 >= best_score do break
for run in m.name_runs[m.name_cells[cell.c]:m.name_cells[cell.c + 1]] {
d2 := max(f32)
for k in run.start ..< run.start + run.count {
a, b := m.points[k], m.points[k + 1]
ab, ap := b - a, pos - a
len2 := ab.x * ab.x + ab.y * ab.y
t := len2 > 0 ? clamp((ap.x * ab.x + ap.y * ab.y) / len2, 0, 1) : 0
e := ap - ab * t
d2 = min(d2, e.x * e.x + e.y * e.y)
}
if d2 > r2 do continue
wk := weights[Map_Kind(m.lines[run.line].kind)]
if score := d2 * wk * wk; score < best_score do best_line, best_score = int(run.line), score
}
}
if best_line < 0 do return
l := m.lines[best_line]
kind = Map_Kind(l.kind)
name = map_name(m, l.name)
if name == "" {
name = map_name(m, l.ref)
if i := strings.index_byte(name, ';'); i >= 0 do name = name[:i]
}
return name, kind, name != ""
}
|