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

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!

• If you're willing to use floating point, then you can move the start and endpoints of the line to any location you want in their respective cells and trace the ray between them with this Dec 13, 2020 at 2:02
• That did it, thank you Dec 15, 2020 at 1:27 