Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
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. – user744 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

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

share|improve this answer
up vote 0 down vote accepted

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.