I have a map with integer grid points. The map is flat, so all points are on a 2D plane. There are objects scattered here and there on the map. Some objects are concave, and some are convex. I'm looking for a way to map a route between two points. I have come up with an algorithm which is fairly tight, but it hinges on the ability to do one thing:

For a line between any two points, find out whether it intersects any of the objects on the map.

There is one obvious way to handle this, which would be to walk the line from A to B checking each point to see whether it is part of one of the known objects. This seems painfully slow, but there may not be any superior alternative. The first thought I had was this:

1) Find the quadrant that the direction from A to B falls into. With 0 being North, then the quadrants are 315-45, 45-135, 135-225, and 225-315.

Assume that the angle theta falls between 0 and 45, the pseudo code would look something like this:

X as Integer

For each Y from Ya To Yb
X = Y\ (1/Tan(theta))
If check point (X,Y) Then
Exit, cause the line hit an object.
End If
Next

For angles 45-90, swap X and Y.
For angles 90-135 swap X and Y and negate Y.
etc.

What I'm looking for is a better way to do this. Of course, the pseudo code is not optimized, since 1/Tan(theta) is effectively a constant.

If there is also an optimal solution for the whole problem of finding a route from A to B, then I'd like to see it. It appears that route finding algorithms are based on roads. I don't have roads. This is about navigating around within a mostly empty space.