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!
