2
\$\begingroup\$

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.

https://i.imgur.com/BZPLKOr.png

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!

\$\endgroup\$
2
  • 2
    \$\begingroup\$ 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 \$\endgroup\$ – DMGregory Dec 13 '20 at 2:02
  • \$\begingroup\$ That did it, thank you \$\endgroup\$ – CrazY D Dec 15 '20 at 1:27
1
\$\begingroup\$

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

enter image description here

Some of the other links I visited during my research:

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.