c# - How do I generalise Bresenham's line algorithm to floating-point endpoints?

I'm trying to combine two things. I'm writing a game and I need to determine the grid squares lying on a line with the floating-point endpoints.

Moreover I need it to include all the grid squares it touches (i.e. not just Bresenham's line but the blue one):

Can someone offer me any insight on how to do it? The obvious solution is to use naive line algorithm, but is there something more optimized (faster)?

Answer

You are looking for a grid traversal algorithm. This paper gives a good implementation;

Here's the basic implementation in 2D found on the paper:

loop {

    if(tMaxX < tMaxY) {
        tMaxX= tMaxX + tDeltaX;
        X= X + stepX;
    } else {
        tMaxY= tMaxY + tDeltaY;
        Y= Y + stepY;
    }
    NextVoxel(X,Y);
}

There's also a 3D ray-casting version on the paper.

In case the link rots, you can find many mirrors with its name: A faster voxel traversal algorithm for raytracing.