# What is a technique for 2D ray-box intersection that is suitable for old console hardware?

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:

1. I'm working with pixel locations (integers). Floating point is too expensive. It doesn't have to be super exact, just close enough.

2. 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.

-
 Do you know what box you're testing against? Or are you looking for the intersections of all boxes the vector goes through. Also, do you know the length (or start and end points) of the vector? Is it just the current position + velocity? – Richard Marskell - Drackir Mar 29 '12 at 15:52 Do you need to know it a priori? On some hardware this would've been done by detecting a collision using special hardware when you draw the sprite over the underlying tile (the equivalent of a "modern" occlusion query), but I don't know if this is the case for the Genesis or not. – Joe Wreschnig Mar 29 '12 at 16:45 The genesis has a bit to say if any sprites overlapped, but it can't tell which ones. So that's out. Plus, it's sprite-tile collisions so the bit couldn't be used for that. – DJCouchyCouch Jul 15 '12 at 0:39

## 2 Answers

well if im understanding correctly, what you can do is mod (%) the x and y with the tile size and then check sizes by hand. So if its on the top edge, the X value would be smallest number or if the bottom edge, X would be the largest number, and the same for Y. I hope that answers your question

-

I used a version of the bresenham line algorithm to project a line into the tilemap. Not the most efficient way, but it's fast enough so far and I only have to do it once per frame.

-