Hash indexes to static array general algorithim help!

help
1

image
image584×937 73.3 KB 

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

2

k is the grid cell index (skipping cells which had no cells in them, I think). This algorithm appears to assume you will be looping over the grid cells in a consistent order, which won't really work with a hash map

3

In the second pass, I got it working now by iterating over all the hasmap keys(the cords) and then finding all rectangles that overlap that same cords, then writing that out to the 1D array.

use hashbrown::HashMap;
#[derive(Copy, Clone, Debug, Default)]
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(3.0, 3.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(2.0, 2.0, 16.0, 16.0), //fits in x: 0, y: 0, an overlapping entity with the first one
        Rect::new(98.0, 0.0, 16.0, 16.0), // fits in grid x: 3, y: 0
        Rect::new(1.0, 1.0, 16.0, 16.0), //fits in x: 0, y: 0, an overlapping entity with the first one
        Rect::new(16.0, 16.0, 16.0, 16.0),  //in 4 grid cells because its in the boundaries
    ];

    // (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();

    //// first pass
    let mut total = 0;
    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), (usize::MAX, 1));
                }
                total += 1;
            }
        }
    }
    
    // (start_index, entities_on_tile)
    let mut indexed_array: Vec<Rect> = Vec::new();
    for _ in 0..total {
        indexed_array.push(Rect::default());
    }


    // second pass
    // we need to adjust the start index to where it would start in the 1d indexed_array and place the overlapping ones sequentailly after
    let mut bsubk = 0;
    let mut asubk = 0;
    for ((x, y), (start_index, num_on_tile)) in &mut hsh {
        let mut found = 0;
        if *start_index == usize::MAX {
            // set  the start index only once!
            *start_index = bsubk + asubk;
            asubk = *num_on_tile;
            bsubk = *start_index;
        }

        // FIND ALL RECTS THAT SHARE THE X & Y OF THE KEYS
        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 fx in top_left_x..=bot_right_x {
                for fy in top_left_y..=bot_right_y {
                    if *x == fx && *y == fy {
                        indexed_array[*start_index + found] = *rect;
                        found += 1;
                        break;
                    } 
                }
            }
            if found == *num_on_tile {
                break;
            }
        }
    }
    for (k, v) in &hsh {
        println!("(x, y): {:?} | (start_index, count): {:?}", k, v);
    }
    println!("the array: ");
    for (index, rect) in indexed_array.iter().enumerate() {
        println!("index: {} | {:?}", index, rect);
    }
}

PRODUCES:
(x, y): (0, 0) | (start_index, count): (0, 4)
(x, y): (0, 1) | (start_index, count): (4, 1)
(x, y): (1, 1) | (start_index, count): (5, 1)
(x, y): (1, 0) | (start_index, count): (6, 1)
(x, y): (3, 0) | (start_index, count): (7, 2)
the array: 
index: 0 | Rect { x: 3.0, y: 3.0, w: 16.0, h: 16.0 }
index: 1 | Rect { x: 2.0, y: 2.0, w: 16.0, h: 16.0 }
index: 2 | Rect { x: 1.0, y: 1.0, w: 16.0, h: 16.0 }
index: 3 | Rect { x: 16.0, y: 16.0, w: 16.0, h: 16.0 }
index: 4 | Rect { x: 16.0, y: 16.0, w: 16.0, h: 16.0 }
index: 5 | Rect { x: 16.0, y: 16.0, w: 16.0, h: 16.0 }
index: 6 | Rect { x: 16.0, y: 16.0, w: 16.0, h: 16.0 }
index: 7 | Rect { x: 96.0, y: 0.0, w: 16.0, h: 16.0 }
index: 8 | Rect { x: 98.0, y: 0.0, w: 16.0, h: 16.0 }

Seems a little inefficent... but I guess if this is only done once during the start of the game it isn't that bad... I hope this is what the paper had in mind.