intersection of line with walls in tile-based game?

I'm making a game that uses an array to keep track of boundaries, like a tile-based game (but the background will be art-based).

I'm trying to figure out how to determine whether or not a line is intersecting some walls. The line can be any length and rotated at any angle.

I could probably get the rows and columns that the ends of the line are on and then check all the rows and columns in between, but that seems like an awful lot of work. Is there a better way?

FWIW, There will be things attached to each end of the line, each doing their own thing, so the line will be moving slightly in a frame loop. Therefore, the solution I use will have to be fast...

The attached image shows an example of what might happen, but in the real game, the line might span many, many more rows and columns.

Thanks for any advice!

Cooper
www.pigdogtoad.com

hey,
here's a paper describing a simple algorithm to do what you want: it will let you start at one end of the line and "walk" along the line, testing only those grid cells (i.e array elements) which touch the line.

http://www.cs.yorku.ca/~amana/research/grid.pdf

raigan

Thanks for the link! That looks like just what I need, but that's some scary stuff! I've been working on my own thing and am getting closer...

I gave up on the method above - too cpu intensive. What I did instead, which isn't entirely accurate, but is accurate enough for me, is to just get the cells every 30 pixels along the line. My tiles are 30 pixels, so it's close enough. For my needs, having it not be perfect is actually better.