Fast ray-box intersection algorithm?

djcouchycouch · Post by **djcouchycouch** » Thu Mar 29, 2012 1:54 pm

Hi,

I'm looking for a really efficient ray-box intersection algorithm. The "ray" here is a particle like a bullet, represented by a point and a movement vector. And by "box" I mean an 8 by 8 background tile. I need to know exactly (or close enough) where the particle hits on the edge of the tile. And of course, since it's on the Genesis, it needs to be real fast. Any ideas?

Thanks!
DJCC

mic_ · Post by **mic_** » Sat Mar 31, 2012 11:13 am

I don't know exactly what you're trying to do, but wouldn't something like this work:

Whenever you move the bullets you can check if they hit something solid in the background. I.e. something like:

Code: Select all

if (map[FIX2INT(ry) >> 3][FIX2INT(rx) >> 3].type == SOLID)

And for all other objects (sprites) that are hittable you can begin by checking if the ray's endpoint and the object are located within the same 8x8 cell, and then whether the endpoint is actually within the object's bounding box (a few IFs).

To find out exactly where the ray hit you could do e.g.:

Code: Select all

if (FIX2INT(rx) > obj.x1)
  s = FIX2INT(rx) - obj.x1  // hit from left
else
  s = obj.x2 - FIX2INT(rx)  // hit from right
hitx = rx - s*dx
// ..and likewise for y

Chilly Willy · Post by **Chilly Willy** » Sat Mar 31, 2012 5:14 pm

This is a "classic" raycasting question. Look at any tutorial on basic raycasting (like found in Wolf3D) for the answers. As to fast, that would be a matter of simplifying the problem if possible, and good assembly coding.