Supercover line algorithm from corners instead of the square's center?

Question

I need to check whether a cell in a 2D grid is visible to the starting cell. I'm currently using amit's supercover line algorithm, this one https://www.redblobgames.com/grids/line-drawing.html#supercover

The algorithm works but I need the cells that are intersected by the top-left corner-to-corner line instead of the center-to-center.

This shows what I mean:

• The green square is the start point and red is the end point
• The white dots represents the cells that are visited by the line drawing algorithm I'm using
• I want to get the cells that are intersected by the blue line. It's drew from the top-left corner of the start cell to the top-left corner of the end cell.

This is my implementation of the amit's algorithm in gdscript

func _line_of_sight(p0, p1):
    var dx = p1.x - p0.x
    var dy = p1.y - p0.y
    
    var sx = 1 if dx > 0 else -1
    var sy = 1 if dy > 0 else -1
    
    var p = Vector2(p0.x, p0.y)
    _points.append(p)
    
    var x = 0
    var y = 0
    var nx = abs(dx)
    var ny = abs(dy)
    
    var result = true
    var blocked_cells = _tilemap.get_used_cells()
    
    while x < nx or y < ny:
        var px = (1+2*x) * ny
        var py = (1+2*y) * nx
        
        if px == py:
            p.x += sx
            p.y += sy
            x += 1
            y += 1
            
        elif px < py:
            p.x += sx
            x += 1
        else:
            p.y += sy
            y += 1
            
        if blocked_cells.has(p):
            result = false
            
        _points.append(p)
        
    return result

I've also tried Bresenham's line algorithm and the Bresenham supercover modification, this and this, as well as this, but none did the trick

Any insight would be appreciated - thanks in advance!

Answer 1

The solution was to use "A Fast Voxel Traversal Algorithm for Ray Tracing", as suggested by DMGregor, to trace a ray from/to "world" position instead of a grid cell's coordinate. I implemented the algorithm based on this site: https://www.flipcode.com/archives/Raytracing_Topics_Techniques-Part_4_Spatial_Subdivisions.shtml

Some of the other links I visited during my research:

• https://theshoemaker.de/2016/02/ray-casting-in-2d-grids/
• http://www.cse.yorku.ca/~amana/research/grid.pdf
• https://github.com/francisengelmann/fast_voxel_traversal
• https://www.shadertoy.com/view/XddcWn
• https://stackoverflow.com/questions/11694886/traverse-a-2-5d-grid