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!
