Field of vision and obstructions

[nevon]

So, I've been teaching myself some linear algebra concepts that I should've learned a long time ago. Right now I would like to put them into practice, by creating a small game that deals with field of vision. I already know how to check if a point is within the field of vision of an entity, but what I don't know is what the best way to deal with obstacles that could obstruct the line of sight.

5ZtVm.png (4.76 KiB) Viewed 125 times

I thought there would be a bazillion resources on this on the interwebs, but all that I have been able to find have been about tile-based engines.

[vrld]

Do you need the vision field? If not, you could test for every "seeable" object in the viewing radius if the line between your actor and the object intersects any objects that are itself intersecting the viewing radius:

Diagram1.png (4.58 KiB) Viewed 1315 times

If you need the viewing volume, you could try to break the circle into subshapes by casting rays to every intersecting corner line-circle-intersection points. Something like this:

Diagram2.png (7.57 KiB) Viewed 1315 times

Maybe the study of binary space partitioning and shadow volumes could provide a solution.

[nevon]

Do you need the vision field? If not, you could test for every "seeable" object in the viewing radius if the line between your actor and the object intersects any objects that are itself intersecting the viewing radius:

Diagram1.png

I don't need the vision field, no. I just need a good way to handle obstacles that limit the line of sight. If I have two points (an enemy and the player), and I know that the player is within the enemy's field of vision (without taking obstacles into account), what would be the best way to check if any obstacles are in the way - obscuring the player? We could assume that all obstacles are rectangular and aligned straight (so no diagonal objects). Each object would have a position, a width and a height.

EDIT: Oh wait, that's just a regular line-rectangle intersection check. xD That was kind of dumb of me.

[nevon]

In the end I went with a slightly different approach. Instead of doing some line-rectangle intersection, I decided to treat it as lines of a polygon - so I had do to line-segment intersection testing instead. That worked out much better, since I can now have odd shapes and weird angles. I also added line-circle intersection.

It's just a proof-of-concept, more or less, but the line-line intersection stuff might be of use to someone else, so I've uploaded a .love file. This is the interesting part:

Code: Select all

function isOnSegment(xi, yi, xj, yj, xk, yk)
    return (xi <= xk or xj <= xk) and (xk <= xi or xk <= xj) and (yi <= yk or yj <= yk) and (yk <= yi or xk <= yj)
end

function computeDirection(xi, yi, xj, yj, xk, yk)
    local a = (xk - xi) * (yj - yi)
    local b = (xj - xi) * (yk - yi)
    if a < b then return -1 elseif a > b then return 1 else return 0 end
end

function doLineSegmentsIntersect(x1, y1, x2, y2, x3, y3, x4, y4)
    local d1 = computeDirection(x3, y3, x4, y4, x1, y1)
    local d2 = computeDirection(x3, y3, x4, y4, x2, y2)
    local d3 = computeDirection(x1, y1, x2, y2, x3, y3)
    local d4 = computeDirection(x1, y1, x2, y2, x4, y4)
    return (((d1 > 0 and d2 < 0) or (d1 < 0 and d2 > 0)) and 
        ((d3 > 0 and d4 < 0) or (d3 < 0 and d4 > 0))) or 
        (d1 == 0 and isOnSegment(x3, y3, x4, y4, x1, y1)) or 
        (d2 == 0 and isOnSegment(x3, y3, x4, y4, x2, y2)) or 
        (d3 == 0 and isOnSegment(x1, y1, x2, y2, x3, y3)) or 
        (d4 == 0 and isOnSegment(x1, y1, x2, y2, x4, y4))
end

EDIT: Changed the line-circle intersection test to be less hackish. It is now:

Code: Select all

function lineCircleIntersect(startx, starty, endx, endy, circlex, circley, circler)
    local dirVector = Vector.new(endx-startx, endy-starty)
    
    local diffVector = Vector.new(circlex-startx,circley-starty)
    
    local t = Vector.Dot(diffVector, dirVector) / Vector.Dot(dirVector, dirVector)
    
    if t < 0 then
        t=0
    elseif t > 1 then
        t=1
    end
    
    local closest = Vector.new(startx+(t*dirVector.x), starty+(t*dirVector.y))
    
    local d = Vector.new(circlex-closest.x, circley-closest.y)
    
    local distSqrt = Vector.Dot(d,d)
    
    if distSqrt <= circler*circler then
        return true
    else
        return false
    end
end

[Robin]

Doesn't work perfectly: somewhere inside the polygon, it is treated as visible as well.

[nevon]

Doesn't work perfectly: somewhere inside the polygon, it is treated as visible as well.

Bah! Then don't go in to the polygon! :@

[Robin]

Doesn't work perfectly: somewhere inside the polygon, it is treated as visible as well.

Bah! Then don't go in to the polygon! :@

But if it is a house, it would mean you could see inside the house (and I'm on linux, so no windows).

[nevon]

Doesn't work perfectly: somewhere inside the polygon, it is treated as visible as well.

Bah! Then don't go in to the polygon! :@

But if it is a house, it would mean you could see inside the house (and I'm on linux, so no windows).

You're invisible in most of the house anyway... :/ I guess it could be that both of the points are further away from the guard than the player - which is a case that I eliminate because that should mean that the wall is behind the player. When I think about it, that's a faulty assumption.