Post news RSS DevBlog 2 - Ray Casting Through a Spatial Hash Grid

The custom collision system (SAT) uses spatial hashing to only do collision tests for objects nearby. This creates a problem for lasers that travel through many cells at once. So a special function was added to only query the cells that intersect a ray segment.

Posted by on



My spatial hash grid has the ability to look up collision shapes within a given spatial hash cell.
But I did not really have the ability to easily query a line of individual cells.
If I wanted to trace a line through the spatial hash, I would need a shape encompassed the entire line.
This was extremely wasteful, as it would include a lot of insignificant cells (imagine a big box around the line trace).
So I wrote code that determines which cells the line passes through.
I can then run a special query only for those cells, which is much faster than a large box overlap.

The goal of this this ray casting system is assist projectiles.
Since projectiles are moving very fast, there is the potential that they may skip space if there is a large delta time.
But I can determine the line representing the projectile's movement since the last frame.
I can use this line to figure out which cells it intersects, and query those cells to see if any ships are within that portion of the grid.
If this line then also intersects any shapes contained within a cell, then it should process that as a collision.

This game is open source and not commercial.

Post a comment
Sign in or join with:

Only registered members can share their thoughts. So come on! Join the community today (totally free - or sign in with your social account on the right) and join in the conversation.