aboutsummaryrefslogtreecommitdiffstats
path: root/source/game/collide.odin
blob: 6f5a3ff6f589839d3ba5e5f93075421e181b1c0d (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
package game

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

// Building collision for free flight in the street view (Lars, 2026-11-21: "tussen huizen vliegen"). The car
// hits the same walls the street view draws: the real OSM buildings of BUILDINGS_DATA (buildings.odin) at their
// real height, lowered at the edge of the baked circle like the mesh, and the generated town buildings, which
// are not stored but made again from the City triangles around the query point (town_lot). Simulation code: no
// raylib, no camera state. Built on first use from the perm arena, the same for every run.
COLLIDE_CELL_KM :: 0.1
// Cells per side of a city's grid: 2.4 km around the city point holds the 1 km circle and its largest buildings.
COLLIDE_CITY_CELLS :: 24
COLLIDE_TRI_CELL_KM :: 1.0
COLLIDE_TRI_W :: int(MAP_W_KM / COLLIDE_TRI_CELL_KM) + 1
COLLIDE_TRI_H :: int(MAP_H_KM / COLLIDE_TRI_CELL_KM) + 1
// The most buildings one query looks at (a dense city centre has ~20 within 30 m).
COLLIDE_MAX_SEEN :: 96

// Zero = not built yet.
Collide :: struct {
	built:      bool,
	points:     [][2]f32, // building rings, km
	b_start:    []u32, // first point of building b
	b_count:    []u32,
	b_height:   []f32, // m above the ground
	cities:     [BUILDINGS_MAX_CITIES][2]f32, // city points of the real buildings, km
	city_count: int,
	// Building indices per 100 m cell of each city: city_items[city_cells[c] : city_cells[c + 1]] for cell
	// c = city * COLLIDE_CITY_CELLS^2 + y * COLLIDE_CITY_CELLS + x.
	city_cells: []u32,
	city_items: []u32,
	// City triangles per 1 km cell of the map: area index and first point index in w.m.area_points.
	tri_cells:  []u32,
	tri_items:  [][2]u32,
}

// What a circle of radius_m around pos (km) touches with its underside at hag m above the ground. push (m, x east,
// y south) moves it out of the walls it overlaps; roof is the highest roof right under it that it is above
// (m above the ground, 0 = none), so the car can land on a roof.
collide_car :: proc(w: ^World, pos: [2]f32, hag, radius_m: f32) -> (push: [2]f32, roof: f32) {
	co := &w.collide
	if !co.built do collide_build(w)

	// One footprint against the circle: pts in metres relative to pos.
	test :: proc(pts: [][2]f32, height, hag, radius_m: f32, push: ^[2]f32, roof: ^f32) {
		inside := false
		best := max(f32)
		closest: [2]f32
		n := len(pts)
		for k in 0 ..< n {
			a, b := pts[k], pts[(k + 1) % n]
			if (a.y > 0) != (b.y > 0) && a.x + (b.x - a.x) * (0 - a.y) / (b.y - a.y) > 0 do inside = !inside
			ab := b - a
			l2 := linalg.dot(ab, ab)
			t := l2 > 0 ? clamp(-linalg.dot(a, ab) / l2, 0, 1) : 0
			q := a + ab * t
			if d := linalg.dot(q, q); d < best {
				best = d
				closest = q
			}
		}
		dist := math.sqrt(best)
		if hag >= height - 0.3 {
			// Above the roof: it carries the car while the middle of the car is over it.
			if inside || dist < radius_m * 0.4 do roof^ = max(roof^, height)
			return
		}
		if inside {
			// Out through the nearest wall, then a radius further.
			push^ += dist > 1e-4 ? closest * (1 + radius_m / dist) : {radius_m, 0}
		} else if dist < radius_m {
			push^ -= closest / dist * (radius_m - dist)
		}
	}

	seen: [COLLIDE_MAX_SEEN]u32
	seen_n := 0
	ring := make([dynamic][2]f32, 0, 32, context.temp_allocator)
	r_km := radius_m / 1000

	// Real buildings: the 3 x 3 cells around pos in each city near it.
	half := f32(COLLIDE_CITY_CELLS) * COLLIDE_CELL_KM / 2
	for ci in 0 ..< co.city_count {
		rel := pos - co.cities[ci] + half
		if rel.x < -r_km || rel.y < -r_km || rel.x > 2 * half + r_km || rel.y > 2 * half + r_km do continue
		cx, cy := int(math.floor(rel.x / COLLIDE_CELL_KM)), int(math.floor(rel.y / COLLIDE_CELL_KM))
		for y in max(cy - 1, 0) ..= min(cy + 1, COLLIDE_CITY_CELLS - 1) {
			for x in max(cx - 1, 0) ..= min(cx + 1, COLLIDE_CITY_CELLS - 1) {
				c := ci * COLLIDE_CITY_CELLS * COLLIDE_CITY_CELLS + y * COLLIDE_CITY_CELLS + x
				items: for b in co.city_items[co.city_cells[c]:co.city_cells[c + 1]] {
					for s in seen[:seen_n] do if s == b do continue items
					if seen_n < COLLIDE_MAX_SEEN {
						seen[seen_n] = b
						seen_n += 1
					}
					clear(&ring)
					for p in co.points[co.b_start[b]:][:co.b_count[b]] do append(&ring, (p - pos) * 1000)
					test(ring[:], co.b_height[b], hag, radius_m, &push, &roof)
				}
			}
		}
	}

	// Generated town buildings: the lots around pos in every City triangle of the cells it touches.
	lot := f32(TOWN_LOT_M) / 1000
	reach := lot + r_km
	x0 := clamp(int(math.floor((pos.x - reach) / COLLIDE_TRI_CELL_KM)), 0, COLLIDE_TRI_W - 1)
	x1 := clamp(int(math.floor((pos.x + reach) / COLLIDE_TRI_CELL_KM)), 0, COLLIDE_TRI_W - 1)
	y0 := clamp(int(math.floor((pos.y - reach) / COLLIDE_TRI_CELL_KM)), 0, COLLIDE_TRI_H - 1)
	y1 := clamp(int(math.floor((pos.y + reach) / COLLIDE_TRI_CELL_KM)), 0, COLLIDE_TRI_H - 1)
	Lot :: struct {
		seed: u32,
		i, j: i32,
	}
	lots: [COLLIDE_MAX_SEEN]Lot
	lots_n := 0
	for cy in y0 ..= y1 {
		for cx in x0 ..= x1 {
			c := cy * COLLIDE_TRI_W + cx
			for item in co.tri_items[co.tri_cells[c]:co.tri_cells[c + 1]] {
				p0, p1, p2 :=
					w.m.area_points[item[1]], w.m.area_points[item[1] + 1], w.m.area_points[item[1] + 2]
				seed, ax, ay := town_lattice(int(item[0]))
				u := i32(math.floor(linalg.dot(pos, ax) / lot))
				v := i32(math.floor(linalg.dot(pos, ay) / lot))
				for j in v - 1 ..= v + 1 {
					lots_loop: for i in u - 1 ..= u + 1 {
						centre := (ax * (f32(i) + 0.5) + ay * (f32(j) + 0.5)) * lot
						if !in_triangle(centre, p0, p1, p2) do continue
						for l in lots[:lots_n] do if l == {seed, i, j} do continue lots_loop
						if lots_n < COLLIDE_MAX_SEEN {
							lots[lots_n] = {seed, i, j}
							lots_n += 1
						}
						corners, height, ok := town_lot(co.cities[:co.city_count], seed, ax, ay, i, j)
						if !ok do continue
						clear(&ring)
						for p in corners do append(&ring, (p - pos) * 1000)
						test(ring[:], height * 1000, hag, radius_m, &push, &roof)
					}
				}
			}
		}
	}
	return
}

// Unpacks the footprints of BUILDINGS_DATA (format in tools/bake_buildings, read as in buildings_build) and
// files them and the City triangles into their cells. Staging memory is a local arena, freed at the end.
collide_build :: proc(w: ^World) {
	co := &w.collide
	co^ = {}
	co.built = true
	perm := virtual.arena_allocator(&w.perm)

	// City triangles of the land use map, for the generated buildings. Two passes: count per cell, then fill.
	{
		counts := make([]u32, COLLIDE_TRI_W * COLLIDE_TRI_H + 1, perm)
		for pass in 0 ..< 2 {
			for a, ai in w.m.areas {
				if Area_Kind(a.kind) != .City do continue
				for k := a.start; k + 2 < a.start + a.count; k += 3 {
					p := w.m.area_points[k:][:3]
					lo := linalg.min(p[0], linalg.min(p[1], p[2]))
					hi := linalg.max(p[0], linalg.max(p[1], p[2]))
					x0 := clamp(int(lo.x / COLLIDE_TRI_CELL_KM), 0, COLLIDE_TRI_W - 1)
					x1 := clamp(int(hi.x / COLLIDE_TRI_CELL_KM), 0, COLLIDE_TRI_W - 1)
					y0 := clamp(int(lo.y / COLLIDE_TRI_CELL_KM), 0, COLLIDE_TRI_H - 1)
					y1 := clamp(int(hi.y / COLLIDE_TRI_CELL_KM), 0, COLLIDE_TRI_H - 1)
					for y in y0 ..= y1 {
						for x in x0 ..= x1 {
							c := y * COLLIDE_TRI_W + x
							if pass == 0 {
								counts[c + 1] += 1
							} else {
								co.tri_items[co.tri_cells[c] + counts[c]] = {u32(ai), k}
								counts[c] += 1
							}
						}
					}
				}
			}
			if pass == 0 {
				for c in 1 ..< len(counts) do counts[c] += counts[c - 1]
				co.tri_cells = counts
				co.tri_items = make([][2]u32, counts[len(counts) - 1], perm)
				counts = make([]u32, COLLIDE_TRI_W * COLLIDE_TRI_H + 1, context.temp_allocator)
			}
		}
	}

	scratch: virtual.Arena
	if virtual.arena_init_growing(&scratch) != nil do return
	defer virtual.arena_destroy(&scratch)
	tmp := virtual.arena_allocator(&scratch)
	unzipped := make([dynamic]u8, 0, 4 << 20, tmp)
	if err := deflate.inflate_gzip(&unzipped, BUILDINGS_DATA, allocator = tmp); err != nil {
		logf(w, "collide", "buildings.bin.gz does not unpack: %v, no building collision", err)
		return
	}
	data := unzipped[:]
	Header :: struct {
		magic, version, city_count, _: u32le,
	}
	City :: struct {
		origin:                       [2]f32le,
		building_count, vertex_count: u32le,
	}
	if len(data) < size_of(Header) do return
	h := (^Header)(raw_data(data))^
	if h.magic != 0x44425244 || h.version != 1 || int(h.city_count) > BUILDINGS_MAX_CITIES {
		logf(w, "collide", "buildings.bin: wrong magic, version or city count %d", h.city_count)
		return
	}
	cities := ([^]City)(raw_data(data[size_of(Header):]))[:h.city_count]
	off := size_of(Header) + int(h.city_count) * size_of(City)
	total_b, total_v := 0, 0
	for c in cities {
		total_b += int(c.building_count)
		total_v += int(c.vertex_count)
	}
	if len(data) != off + total_b * 2 + total_v * 4 {
		logf(
			w,
			"collide",
			"buildings.bin: %d bytes, the header says %d",
			len(data),
			off + total_b * 2 + total_v * 4,
		)
		return
	}
	counts_b := data[off:][:total_b]
	heights := data[off + total_b:][:total_b]
	planes := data[off + total_b * 2:]

	co.points = make([][2]f32, total_v, perm)
	co.b_start = make([]u32, total_b, perm)
	co.b_count = make([]u32, total_b, perm)
	co.b_height = make([]f32, total_b, perm)
	b_city := make([]u32, total_b, tmp)
	bi, vi := 0, 0
	for c, ci in cities {
		origin := [2]f32{f32(c.origin.x), f32(c.origin.y)}
		co.cities[ci] = origin
		for _ in 0 ..< c.building_count {
			n := int(counts_b[bi])
			q: [2]i32
			mid: [2]f32
			for k in 0 ..< n {
				i := vi + k
				q.x += i32(i16(u16(planes[i]) | u16(planes[total_v + i]) << 8))
				q.y += i32(i16(u16(planes[2 * total_v + i]) | u16(planes[3 * total_v + i]) << 8))
				co.points[i] = origin + [2]f32{f32(q.x), f32(q.y)} * BUILDINGS_POS_UNIT_M / 1000
				mid += co.points[i]
			}
			// The same height as the mesh at real scale: lowered towards the edge of the baked circle.
			height := f32(heights[bi])
			if n > 0 {
				edge := linalg.length(mid / f32(n) - origin) / BUILDINGS_RADIUS_KM
				height *= 1 - 0.75 * math.smoothstep(f32(0.6), 1, edge)
			}
			co.b_start[bi] = u32(vi)
			co.b_count[bi] = n >= 3 ? u32(n) : 0
			co.b_height[bi] = height
			b_city[bi] = u32(ci)
			vi += n
			bi += 1
		}
	}
	co.city_count = len(cities)

	// Each building into every 100 m cell its box touches. Two passes again.
	cells := len(cities) * COLLIDE_CITY_CELLS * COLLIDE_CITY_CELLS
	counts := make([]u32, cells + 1, perm)
	half := f32(COLLIDE_CITY_CELLS) * COLLIDE_CELL_KM / 2
	for pass in 0 ..< 2 {
		for b in 0 ..< total_b {
			if co.b_count[b] == 0 do continue
			ci := int(b_city[b])
			pts := co.points[co.b_start[b]:][:co.b_count[b]]
			lo, hi := pts[0], pts[0]
			for p in pts {
				lo = linalg.min(lo, p)
				hi = linalg.max(hi, p)
			}
			lo = lo - co.cities[ci] + half
			hi = hi - co.cities[ci] + half
			x0 := clamp(int(lo.x / COLLIDE_CELL_KM), 0, COLLIDE_CITY_CELLS - 1)
			x1 := clamp(int(hi.x / COLLIDE_CELL_KM), 0, COLLIDE_CITY_CELLS - 1)
			y0 := clamp(int(lo.y / COLLIDE_CELL_KM), 0, COLLIDE_CITY_CELLS - 1)
			y1 := clamp(int(hi.y / COLLIDE_CELL_KM), 0, COLLIDE_CITY_CELLS - 1)
			for y in y0 ..= y1 {
				for x in x0 ..= x1 {
					c := ci * COLLIDE_CITY_CELLS * COLLIDE_CITY_CELLS + y * COLLIDE_CITY_CELLS + x
					if pass == 0 {
						counts[c + 1] += 1
					} else {
						co.city_items[co.city_cells[c] + counts[c]] = u32(b)
						counts[c] += 1
					}
				}
			}
		}
		if pass == 0 {
			for c in 1 ..< len(counts) do counts[c] += counts[c - 1]
			co.city_cells = counts
			co.city_items = make([]u32, counts[len(counts) - 1], perm)
			counts = make([]u32, cells + 1, tmp)
		}
	}
	logf(
		w,
		"collide",
		"%d buildings in %d cities, %d cell entries, %d town triangle entries",
		total_b,
		co.city_count,
		len(co.city_items),
		len(co.tri_items),
	)
}