Spatial Hashing with Hash Maps and Sets for Fast 2D Collision Detection Quiz

Test your understanding of hash maps and sets in spatial hashing for efficient 2D collision detection using a uniform grid. Assess your knowledge of concepts, implementation, and common pitfalls in grid-based partitioning techniques for collision checks.

1. Hash Map Basics in Spatial Hashing

   Why are hash maps commonly used for storing objects in spatial hashing for 2D collision detection?

   1. They store only one object type at a time.
   2. They allow fast lookups and insertions by cell key.
   3. They guarantee objects never collide.
   4. They require objects to be sorted by size.

   Explanation: Hash maps provide efficient key-based access, making it quick to insert or find objects in grid cells by their computed cell keys. This property speeds up checking for possible collisions. Hash maps do not guarantee absolute prevention of collisions—they just facilitate efficient detection. They are not restricted to one object type, and sorting by size is not a requirement for spatial hashing.

2. Uniform Grid Partitioning

   In a 2D uniform grid spatial hashing, how is the grid cell that an object belongs to typically determined?

   1. By randomly choosing a cell each frame.
   2. By dividing the object's coordinates by the grid cell size and rounding down.
   3. By assigning a unique color to each object.
   4. By storing objects alphabetically.

   Explanation: The common method is to divide an object's X and Y coordinates by the size of the cell, rounding down to get integer grid indices. This ensures every object's position maps to its corresponding grid cell. Assigning unique colors or sorting alphabetically does not provide spatial partitioning, and randomly picking cells would not relate to the object's position.

3. Reducing Collision Checks

   How does using a uniform grid with sets or hash maps reduce the number of collision checks between objects?

   1. It sorts all objects globally at every frame.
   2. It guarantees no runtime overhead.
   3. It limits collision checks to objects in the same or neighboring cells.
   4. It removes the need to check for object movements.

   Explanation: Spatial hashing partitions the space so only objects in the same or adjacent cells are checked against each other, minimizing unnecessary comparisons. It does not remove runtime overhead entirely and does not eliminate the need to track moving objects. Global sorting is not relevant to this acceleration technique.

4. Handling Multiple Objects per Cell

   Why are sets commonly used for storing objects in each grid cell when implementing spatial hashing?

   1. They store object colors efficiently.
   2. They require less memory than arrays.
   3. They sort objects automatically by position.
   4. They prevent duplicate entries of the same object in a cell.

   Explanation: Sets inherently avoid duplicates, so the same object cannot be added to the same cell multiple times if it overlaps cell boundaries during updates. Sets do not impact how colors are stored, and while their memory usage can be optimized, that is not their primary advantage in this context. Sets do not automatically sort items by position.

5. Grid Cell Key Construction

   When using a hash map for grid cells, which is a common method to construct a unique cell key for lookup?

   1. Using only the object's mass.
   2. Combining the cell’s X and Y indices into a string or tuple.
   3. Assigning random numbers as cell keys.
   4. Counting the number of objects in the cell.

   Explanation: A pair of indices, often combined as a tuple or concatenated string, uniquely identifies each grid cell in a hash map, enabling precise lookups and insertion. Using mass or random numbers would not correspond to spatial location, and counting objects is not used for addressing cells.

6. Choice of Grid Cell Size

   What is an important consideration when choosing the cell size for a uniform grid in spatial hashing?

   1. The cell size must be random for each cell.
   2. The cell size should be similar to the average object size to balance efficiency.
   3. The cell size should be ten times smaller than any object.
   4. The cell size must always match the window size.

   Explanation: Choosing a cell size close to the average object size ensures that each cell contains a manageable number of objects, balancing collision accuracy and performance. Making cells too small or random can lead to inefficiency, and matching the cell size to the entire window defeats the grid’s purpose.

7. Collisions Across Cell Boundaries

   When an object overlaps multiple grid cells, which approach should be taken to ensure all potential collisions are detected?

   1. Insert the object into every cell it overlaps.
   2. Delete the object from all other cells.
   3. Ignore collisions in partially covered cells.
   4. Only insert it into the cell containing its center point.

   Explanation: Every overlapped cell should register the object so potential collisions in neighboring regions are not missed. Just using the center point misses side collisions, and ignoring partially covered cells results in undetected contacts. Deleting from other cells is counterproductive.

8. Key Advantage over Brute Force

   Compared to checking every pair of objects (brute force), what is the main advantage of uniform grid spatial hashing?

   1. It prevents objects from leaving the defined space.
   2. It reduces the average number of collision checks per object.
   3. It avoids storing object positions.
   4. It ensures absolutely no collisions happen.

   Explanation: Spatial hashing groups potentially colliding objects, so fewer checks are needed per object compared to testing every possible pair. It does not offer perfect collision prevention, nor does it restrict object movement or negate the need to track positions.

9. Removing Stale Entries

   Why is it important to remove objects from their previous grid cells when objects move in spatial hashing?

   1. To ensure all cells have equal object counts.
   2. To prevent false collision checks in outdated cell locations.
   3. To avoid detecting color changes.
   4. To free up video memory.

   Explanation: If objects are not removed from their previous cells after moving, they may be falsely considered for collisions in places they no longer occupy. Memory issues and color changes are unrelated to the spatial hashing structure. Equal cell counts are unnecessary and would defeat efficient partitioning.

10. Handling Edge Cases in Spatial Hashing

    Which is a correct strategy to handle objects that partially overlap the edge or boundary of the grid in spatial hashing?

    1. Move such objects randomly inside the grid.
    2. Allow negative cell indices to wrap around automatically.
    3. Check if their coordinates are within valid cell indices and handle edge conditions accordingly.
    4. Ignore objects near the edge of the grid.

    Explanation: Ensuring that coordinates are within valid grid bounds helps avoid errors and edge-case bugs; appropriate checks or boundary handling is needed. Wrapping indices or ignoring objects near the edge may lead to errors or missed collisions, and moving objects arbitrarily disrupts the simulation.