I'm working on a Sega Genesis homebrew game (it has a 7mhz 68000 CPU). I'm looking for a way to find the intersection between a particle sprite and a background tile. Particles are represented as a point with a movement vector. Background tiles are 8 x 8 pixels, with an (X,Y) position that is always located at a multiple of 8.
So, really, I need to find the intersection point for a ray-box collision; I need to find out where along the edge of the tile the ray/particle hits.
I have these two hard constraints:
I'm working with pixel locations (integers). Floating point is too expensive. It doesn't have to be super exact, just close enough.
Multiplications, divisions, dot products, et cetera, are incredibly expensive and are to be avoided.
So I'm looking for an efficient algorithm that would fit those constraints. Any ideas? I'm writing it in C, so that would work, but assembly should be good as well.