2D Visibility

Visibility triangles from 2D occluding segment geometry in GDScript.

– Created: June 12, 2023 UTC

– Edited: July 28, 2024 UTC

– Tags: Programming, Godot, GDScript

Based on Redblobgames' visibility article and Haxe reference implementation

Full usable code is here.

Explanation

First step is determining angles for each segment point as well as denoting which one gets encountered first.

for segment in range(0, _endpoints.size(), 2):
    var p1 := _endpoints[segment] as EndPoint
    var p2 := _endpoints[segment + 1] as EndPoint
    p1.angle = (p1.point - center).angle()
    p2.angle = (p2.point - center).angle()
    var da := p2.angle - p1.angle
    if da <= PI: da += TAU
    if da > PI: da -= TAU
    p1.begin = da > 0.0
    p2.begin = not p1.begin

Then points are sorted by angle and beginning:

static func sort(p_a: EndPoint, p_b: EndPoint) -> bool:
    if p_a.angle > p_b.angle: return true
    elif p_a.angle < p_b.angle: return false
    elif not p_a.begin and p_b.begin: return true
    else: return false

Then in two passes:

• Walk over sorted points.
• When nearest segment end or another more nearest encountered, - remember the starting angle and only emit two points representing the visible portion of segment on second pass.

var start_angle := 0.0

for n_pass in range(2):
    for p_idx in range(_sorted_endpoints.size() - 1, -1, -1):
        var p := _sorted_endpoints[p_idx] as EndPoint
        var old := -1 if _open.empty() else _open[0]

        if p.begin:
            var idx := 0
            while idx < _open.size() and _is_segment_in_front(p.segment, _open[idx]):
                idx += 1
            _open.insert(idx, p.segment)
        else:
            var idx := _open.rfind(p.segment)
            if idx != -1: _open.remove(idx)

        if old != (-1 if _open.empty() else _open[0]):
            if n_pass == 1:
                var p3 := _endpoints[old].point as Vector2 if old != -1 else \
                    center + Vector2(cos(start_angle), sin(start_angle)) * 500.0
                var t2 := Vector2(cos(p.angle), sin(p.angle))
                var p4 := p3.direction_to(_endpoints[old + 1].point) if old != -1 else t2 

                # note: Checks are in case of parallel lines.
                var l = Geometry.line_intersects_line_2d(p3, p4, center,
                    Vector2(cos(start_angle), sin(start_angle)))
                if l != null: output.append(l)
                l = Geometry.line_intersects_line_2d(p3, p4, center, t2)
                if l != null: output.append(l)

            start_angle = p.angle

Where segment front deciding algorithm is as follows, using cross products:

func _is_segment_in_front(p_segment1: int, p_segment2: int) -> bool:
    var s1p1 := _endpoints[p_segment1].point as Vector2
    var s1p2 := _endpoints[p_segment1 + 1].point as Vector2
    var s2p1 := _endpoints[p_segment2].point as Vector2
    var s2p2 := _endpoints[p_segment2 + 1].point as Vector2

    var d := s1p2 - s1p1
    var p := s2p1.linear_interpolate(s2p2, 0.01)
    var a1 := (d.x * (p.y - s1p1.y) \
             - d.y * (p.x - s1p1.x)) < 0.0
    p = s2p2.linear_interpolate(s2p1, 0.01)
    var a2 := (d.x * (p.y - s1p1.y) \
             - d.y * (p.x - s1p1.x)) < 0.0
    var a3 := (d.x * (center.y - s1p1.y) \
             - d.y * (center.x - s1p1.x)) < 0.0

    if a1 == a2 and a2 == a3: return true

    d = s2p2 - s2p1
    p = s1p1.linear_interpolate(s1p2, 0.01)
    var b1 := (d.x * (p.y - s2p1.y) \
             - d.y * (p.x - s2p1.x)) < 0.0
    p = s1p2.linear_interpolate(s1p1, 0.01)
    var b2 := (d.x * (p.y - s2p1.y) \
             - d.y * (p.x - s2p1.x)) < 0.0
    var b3 := (d.x * (center.y - s2p1.y) \
             - d.y * (center.x - s2p1.x)) < 0.0

    return b1 == b2 and b2 != b3

Usage example

Visibility2D.gd class implements builder interface to make it slightly easier to work with.

func _process(_delta):
    $Visibility2D.init_builder() \
        .view_point(get_global_mouse_position()) \
        .bounds(get_viewport_rect()) \
        .occluder($Line2D) \
        .finalize()

    for child in $Cones.get_children():
        child.queue_free()

    var edges = $Visibility2D.sweep()
    for i in range(0, edges.size() - 1, 2):
        var polygon := Polygon2D.new()
        polygon.polygon = PoolVector2Array([$Visibility2D.center, edges[i], edges[i + 1]])
        $Cones.add_child(polygon)