use hashbrown::HashMap;
#[derive(Copy, Clone, Debug)]
struct Rect {
x: f32,
y: f32,
w: f32,
h: f32,
}
impl Rect {
pub fn new(x: f32, y: f32, w: f32, h: f32) -> Self {
Self {
x,
y,
w,
h
}
}
}
fn main() {
// grid size is 32x32
let static_objects =
[Rect::new(0.0, 0.0, 16.0, 16.0), //fits in x: 0, y: 0
Rect::new(96.0, 0.0, 16.0, 16.0), // fits in grid x: 3, y: 0
Rect::new(0.0, 0.0, 16.0, 16.0), //fits in x: 0, y: 0, an overlapping entity with the first one
];
// (gridx, gridy),(start_index, num_on_cel)
// this will index into the indexed_array below.
let mut hsh: HashMap<(usize, usize), (usize, usize)> = HashMap::new();
// (start_index, entities_on_tile)
let indexed_array: Vec<Rect> = static_objects.to_vec();
//// first pass
for rect in static_objects.iter() {
let (top_left_x, top_left_y) = ((rect.x / 32.0) as usize, (rect.y / 32.0) as usize);
let (bot_right_x, bot_right_y) = (((rect.x + rect.w) / 32.0) as usize, ((rect.y + rect.h) / 32.0) as usize);
for x in top_left_x..=bot_right_x {
for y in top_left_y..=bot_right_y {
if let Some((_, count)) = hsh.get_mut(&(x, y)) {
*count += 1;
} else {
hsh.insert((x, y), (0, 1));
}
}
}
}
// second pass is the main one im struggling with.
// we need to adjust the start index to where it would start in the 1d indexed_array and place the overlapping ones sequentailly after
for rect in static_objects.iter() {
let (top_left_x, top_left_y) = ((rect.x / 32.0) as usize, (rect.y / 32.0) as usize);
let (bot_right_x, bot_right_y) = (((rect.x + rect.w) / 32.0) as usize, ((rect.y + rect.h) / 32.0) as usize);
for x in top_left_x..=bot_right_x {
for y in top_left_y..=bot_right_y {
if let Some((start_index, count)) = hsh.get_mut(&(x, y)) {
// HELP: a bit stuck on setting the starting index
} else {
// HELP: a bit stuck on how to sort them
//indexed_array[index] = rect;
}
}
}
}
for (k, v) in &hsh {
println!("(x, y): {:?} | (start_index, count): {:?}", k, v);
}
}
I'm trying to implement the algorithim above in the book "Real Time Collision Detection" where for static objects, we can store the objects in a 1d array and have a hashmap store grid cell coordinates, and the start to index into that array along with how many items it has thereafter.
So part of the problem is the objects aren't sorted by x & y, one overlapped cell is coming way later. I'm stuck on how to place them into the correct spots, along with determining the starting index. I don't understand what k
is and why bk = bk - 1 + ak - 1
and where to integrate this.. One idea I had is to iterate over the keys first, then look for rects that share the same overlap in the second pass.
Thanks