Plotting a line through a grid

[cloke]

This should be easy, but I think I am experiencing a tad bit of math block. Lets say I have a grid of tiles 8 x 8 wide, each tile being 16x16 pixels in size. I want to plot an imaginary line from point A to point B and mark each tile that line touch's. I was trying to approach this as a simple rise over run type of thing, but I'm having no luck. Below illustrates what I am trying to achieve. Could anybody make any suggestions on where to start or some sample code that might be out there?


X X X X X X X X
X X X X X X X X
X X X X X X X B Tile @ 128,80
X X X X X X T X Tile @ 96,64
X X X X T T X X Tile @ 64,48 & 80,48
X X T T X X X X Tile @ 32,32 & 48,32
X T T X X X X X Tile @ 16,16 & 32,16
A X X X X X X X Tile @ 0,0


Thanks

[VenerablVampire]

There are a lot of line-drawing algorithms, the most common of which has a name I can't recall (or pronounce). I figured out my own thingy with floating point stuff real quick and I can explain that to get you started. Keep in mind this is by no means a fast method or even good coding.

Basically step one unit at a time from the first point to the second on one axis, and then by some step value on the other. The step value is related to the difference in that axis over the difference in the other axis. At each step, convert the relevant axis to an integer value, do some bounds checking, and plot it.

[ThemsAllTook]

...the most common of which has a name I can't recall (or pronounce).

That's be Bresenham. Google for it and you'll get pretty much everything you need...

Alex Diener

[cloke]

Thanks for the info. I found a good example of a modified Bresenham algorithm. It's exactly what I was looking for. I had no idea that it was such an involved thing to find the line of sight of an object.