1use super::super::{Aabb, Aabb3, Hit};
2
3#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
4#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
5pub struct Span<const N: usize> {
6 #[cfg_attr(feature = "serde", serde(with = "super::arr"))]
7 pub min: [i32; N],
8 #[cfg_attr(feature = "serde", serde(with = "super::arr"))]
9 pub max: [i32; N],
10}
11
12impl<const N: usize> Span<N> {
13 pub const fn new(min: [i32; N], max: [i32; N]) -> Self {
14 Self { min, max }
15 }
16
17 pub fn around(centre: [i32; N], half: [i32; N]) -> Self {
18 Self {
19 min: std::array::from_fn(|i| centre[i].saturating_sub(half[i])),
20 max: std::array::from_fn(|i| centre[i].saturating_add(half[i])),
21 }
22 }
23
24 pub fn swept(from: [i32; N], to: [i32; N], half: [i32; N]) -> Self {
25 Self {
26 min: std::array::from_fn(|i| from[i].min(to[i]).saturating_sub(half[i])),
27 max: std::array::from_fn(|i| from[i].max(to[i]).saturating_add(half[i])),
28 }
29 }
30
31 pub fn is_empty(&self) -> bool {
32 (0..N).any(|i| self.max[i] <= self.min[i])
33 }
34
35 pub fn overlaps(&self, other: &Span<N>) -> bool {
36 !self.is_empty()
37 && !other.is_empty()
38 && (0..N).all(|i| self.min[i] < other.max[i] && other.min[i] < self.max[i])
39 }
40}
41
42impl From<Span<2>> for Aabb {
43 fn from(span: Span<2>) -> Self {
44 Aabb::new(span.min, span.max)
45 }
46}
47
48impl From<Span<3>> for Aabb3 {
49 fn from(span: Span<3>) -> Self {
50 Aabb3::new(span.min, span.max)
51 }
52}
53
54impl From<Aabb> for Span<2> {
55 fn from(aabb: Aabb) -> Self {
56 Span::new(aabb.min, aabb.max)
57 }
58}
59
60impl From<Aabb3> for Span<3> {
61 fn from(aabb: Aabb3) -> Self {
62 Span::new(aabb.min, aabb.max)
63 }
64}
65
66#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
67#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
68pub struct Shot<const N: usize> {
69 #[cfg_attr(feature = "serde", serde(with = "super::arr"))]
70 pub pos: [i32; N],
71 #[cfg_attr(feature = "serde", serde(with = "super::arr"))]
72 pub vel: [i32; N],
73 #[cfg_attr(feature = "serde", serde(with = "super::arr"))]
74 pub half: [i32; N],
75 pub life: Option<u32>,
76 pub pierce: u32,
77 pub tag: u32,
78}
79
80#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
81#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
82pub struct ShotId {
83 pub index: u32,
84 pub generation: u32,
85}
86
87#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
88#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
89pub enum End {
90 Expired,
91 Left,
92}
93
94#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
95#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
96pub struct Strike<const N: usize> {
97 pub shot: ShotId,
98 pub target: u32,
99 pub gone: bool,
100 #[cfg_attr(feature = "serde", serde(with = "super::arr"))]
101 pub pos: [i32; N],
102}
103
104#[derive(Clone, Copy, Debug, PartialEq, Eq)]
105pub(super) struct Slot<const N: usize> {
106 pub(super) shot: Shot<N>,
107 pub(super) prev: [i32; N],
108 pub(super) generation: u32,
109 pub(super) alive: bool,
110}
111
112impl<const N: usize> Slot<N> {
113 pub(super) const IDLE: Self = Self {
114 shot: Shot {
115 pos: [0; N],
116 vel: [0; N],
117 half: [0; N],
118 life: None,
119 pierce: 0,
120 tag: 0,
121 },
122 prev: [0; N],
123 generation: 0,
124 alive: false,
125 };
126
127 fn same(&self, other: &Self) -> bool {
128 self.generation == other.generation
129 && self.alive == other.alive
130 && (!self.alive || (self.shot == other.shot && self.prev == other.prev))
131 }
132}
133
134#[derive(Clone, Debug)]
135pub struct Shots<const N: usize> {
136 pub(super) slots: Vec<Slot<N>>,
137 pub(super) free: Vec<u32>,
138 pub(super) len: usize,
139 pub(super) high: usize,
140 ended: Vec<(ShotId, End)>,
141 order: Vec<(f64, u32)>,
142 strikes: Vec<Strike<N>>,
143}
144
145impl<const N: usize> PartialEq for Shots<N> {
146 fn eq(&self, other: &Self) -> bool {
147 self.free == other.free
148 && self.len == other.len
149 && self.high == other.high
150 && self.slots.len() == other.slots.len()
151 && self.slots.iter().zip(&other.slots).all(|(a, b)| a.same(b))
152 }
153}
154
155impl<const N: usize> Eq for Shots<N> {}
156
157impl<const N: usize> Shots<N> {
158 pub fn new(capacity: usize) -> Self {
159 let capacity = u32::try_from(capacity).expect("at most u32::MAX shots");
160 Self::from_parts(
161 vec![Slot::IDLE; capacity as usize],
162 (0..capacity).rev().collect(),
163 0,
164 0,
165 )
166 }
167
168 pub(super) fn from_parts(slots: Vec<Slot<N>>, free: Vec<u32>, len: usize, high: usize) -> Self {
169 Self {
170 slots,
171 free,
172 len,
173 high,
174 ended: Vec::new(),
175 order: Vec::new(),
176 strikes: Vec::new(),
177 }
178 }
179
180 pub fn capacity(&self) -> usize {
181 self.slots.len()
182 }
183
184 pub fn len(&self) -> usize {
185 self.len
186 }
187
188 pub fn is_empty(&self) -> bool {
189 self.len == 0
190 }
191
192 pub fn is_full(&self) -> bool {
193 self.free.is_empty()
194 }
195
196 pub fn spawn(&mut self, shot: Shot<N>) -> Option<ShotId> {
197 let index = self.free.pop()?;
198 let slot = &mut self.slots[index as usize];
199 slot.shot = shot;
200 slot.prev = shot.pos;
201 slot.alive = true;
202 self.len += 1;
203 self.high = self.high.max(index as usize + 1);
204 Some(ShotId {
205 index,
206 generation: slot.generation,
207 })
208 }
209
210 pub fn despawn(&mut self, id: ShotId) -> Option<Shot<N>> {
211 let slot = self.slot(id)?;
212 let shot = slot.shot;
213 self.release(id.index);
214 Some(shot)
215 }
216
217 pub fn contains(&self, id: ShotId) -> bool {
218 self.slot(id).is_some()
219 }
220
221 pub fn get(&self, id: ShotId) -> Option<&Shot<N>> {
222 self.slot(id).map(|slot| &slot.shot)
223 }
224
225 pub fn get_mut(&mut self, id: ShotId) -> Option<&mut Shot<N>> {
226 let slot = self.slots.get_mut(id.index as usize)?;
227 (slot.alive && slot.generation == id.generation).then_some(&mut slot.shot)
228 }
229
230 pub fn swept(&self, id: ShotId) -> Option<Span<N>> {
231 self.slot(id)
232 .map(|slot| Span::swept(slot.prev, slot.shot.pos, slot.shot.half))
233 }
234
235 pub fn iter(&self) -> impl Iterator<Item = (ShotId, &Shot<N>)> {
236 self.slots[..self.high]
237 .iter()
238 .enumerate()
239 .filter(|(_, slot)| slot.alive)
240 .map(|(index, slot)| {
241 (
242 ShotId {
243 index: index as u32,
244 generation: slot.generation,
245 },
246 &slot.shot,
247 )
248 })
249 }
250
251 pub fn step(&mut self, bounds: Span<N>) -> &[(ShotId, End)] {
252 self.ended.clear();
253 for index in 0..self.high {
254 let slot = &mut self.slots[index];
255 if !slot.alive {
256 continue;
257 }
258 let id = ShotId {
259 index: index as u32,
260 generation: slot.generation,
261 };
262 if slot.shot.life == Some(0) {
263 self.ended.push((id, End::Expired));
264 self.release(id.index);
265 continue;
266 }
267 slot.prev = slot.shot.pos;
268 for axis in 0..N {
269 slot.shot.pos[axis] = slot.shot.pos[axis].saturating_add(slot.shot.vel[axis]);
270 }
271 if let Some(life) = &mut slot.shot.life {
272 *life -= 1;
273 }
274 if !Span::swept(slot.prev, slot.shot.pos, slot.shot.half).overlaps(&bounds) {
275 self.ended.push((id, End::Left));
276 self.release(id.index);
277 }
278 }
279 &self.ended
280 }
281
282 pub fn ended(&self) -> &[(ShotId, End)] {
283 &self.ended
284 }
285
286 pub fn boxes<B: From<Span<N>>>(&self, ids: &mut Vec<ShotId>, boxes: &mut Vec<B>) {
287 ids.clear();
288 boxes.clear();
289 for (index, slot) in self.slots[..self.high].iter().enumerate() {
290 if slot.alive {
291 ids.push(ShotId {
292 index: index as u32,
293 generation: slot.generation,
294 });
295 boxes.push(B::from(Span::swept(
296 slot.prev,
297 slot.shot.pos,
298 slot.shot.half,
299 )));
300 }
301 }
302 }
303
304 pub fn resolve<B: Copy + Into<Span<N>>>(
305 &mut self,
306 ids: &[ShotId],
307 hits: &[Hit],
308 targets: &[B],
309 mut accept: impl FnMut(ShotId, u32) -> bool,
310 ) -> &[Strike<N>] {
311 self.strikes.clear();
312 let mut at = 0;
313 while at < hits.len() {
314 let a = hits[at].a;
315 let mut end = at;
316 while end < hits.len() && hits[end].a == a {
317 end += 1;
318 }
319 let group = &hits[at..end];
320 at = end;
321 let Some(&id) = ids.get(a as usize) else {
322 continue;
323 };
324 let Some(slot) = self.slot(id).copied() else {
325 continue;
326 };
327 self.order.clear();
328 if let [hit] = group {
329 if (hit.b as usize) < targets.len() {
330 self.order.push((0.0, hit.b));
331 }
332 } else {
333 for hit in group {
334 if let Some(target) = targets.get(hit.b as usize) {
335 self.order.push((entry(&slot, &(*target).into()), hit.b));
336 }
337 }
338 self.order
339 .sort_by(|x, y| x.0.total_cmp(&y.0).then(x.1.cmp(&y.1)));
340 }
341 let mut pierce = slot.shot.pierce;
342 for index in 0..self.order.len() {
343 let target = self.order[index].1;
344 if !accept(id, target) {
345 continue;
346 }
347 let gone = pierce == 0;
348 self.strikes.push(Strike {
349 shot: id,
350 target,
351 gone,
352 pos: slot.shot.pos,
353 });
354 if gone {
355 self.release(id.index);
356 break;
357 }
358 pierce -= 1;
359 }
360 if let Some(shot) = self.get_mut(id) {
361 shot.pierce = pierce;
362 }
363 }
364 &self.strikes
365 }
366
367 pub fn clear(&mut self) {
368 for index in (0..self.high).rev() {
369 if self.slots[index].alive {
370 self.release(index as u32);
371 }
372 }
373 self.free.clear();
374 self.free.extend((0..self.slots.len() as u32).rev());
375 self.high = 0;
376 self.ended.clear();
377 }
378
379 fn slot(&self, id: ShotId) -> Option<&Slot<N>> {
380 let slot = self.slots.get(id.index as usize)?;
381 (slot.alive && slot.generation == id.generation).then_some(slot)
382 }
383
384 fn release(&mut self, index: u32) {
385 let slot = &mut self.slots[index as usize];
386 slot.alive = false;
387 slot.generation = slot.generation.wrapping_add(1);
388 self.free.push(index);
389 self.len -= 1;
390 while self.high > 0 && !self.slots[self.high - 1].alive {
391 self.high -= 1;
392 }
393 }
394}
395
396fn entry<const N: usize>(slot: &Slot<N>, target: &Span<N>) -> f64 {
397 let mut first = 0.0_f64;
398 for axis in 0..N {
399 let from = i64::from(slot.prev[axis]);
400 let half = i64::from(slot.shot.half[axis]);
401 let moved = i64::from(slot.shot.pos[axis]) - from;
402 let gap = if moved > 0 {
403 i64::from(target.min[axis]) - (from + half)
404 } else if moved < 0 {
405 i64::from(target.max[axis]) - (from - half)
406 } else {
407 continue;
408 };
409 let at = gap as f64 / moved as f64;
410 if at > first {
411 first = at;
412 }
413 }
414 if first > 1.0 { 1.0 } else { first }
415}