2D Raycasting without a grid system

Game Mechanics
#1

Okay, so I’ve been learning about raycasting for 1 or 2 days now and I feel like that I have most of it down.
I’ve already gone through most of the online resources that I could find, so please avoid linking Google’s top results for the subject, those won’t help.
Raycasting is a great thing with many uses, and luckily it’s easy to implement in systems where you have something like a tilemap to make sure where you objects begin and end.
However, when you don’t have such a system but objects are dynamically positioned on your map (e.g. they can be anywhere), and they’re not guaranteed to be quad shaped we have to check against line segments (polygons).
Such a system is demonstrated in tutorials like on Red Blob Games’ 2D visibility tutorial, or in Sight & Light’s tutorial.

As far as I understand, implementing such a solution is not hard: Cast a ray for every line segment’s every point with 2 additional rays biased with a minimal value like 0.00001 radians, so the ray will not stop at the wall’s corner but goes through until it hits the next wall behind it (<- this by the way isn’t even discussed in Red Blob Games’ tutorial, but it’s definitely there in the source code), keep track of the hit points and then build a mesh from the point list using triangles.

My question is however, about how to decide if a wall occludes another?
Since my English is not the best when it comes to technical explanations I will use a picture to demonstrate my issue:

How does the demo on Red Blob Games’ site know that the points marked with red are being occluded by other line segments?
I image that I would have to check every of my rays against every line segment in the game, but how would I know if a ray is going through a line segment?
I’m sure there are many mathematical approaches for this kind of problem, but none of them are discussed in the online tutorials (all Red Blob’s site says is that it’s too complex to be discussed in the tutorial which is kind of ironic, seeing that that’s the reason why a tutorial would be needed in the first place). ??? I downloaded the source code, but honestly it’s kind of a mess and I couldn’t get much out of it.

Any help would be greatly appreciated. :smiley:

#2

You would draw a ray from the source of light to each vertex you want to effect the light. Then, if the ray intersects with any of the lines of the shapes, that ray does not exist.

Diagram:

#3

Thank you for your answer but I know that. My question is how to implement exactly that (that is, how to check if a ray passes through a line segment). :slight_smile:

#4

Ah, okay. Sorry about that.

Funny enough, I just finished working on quite a small geometry library of sorts. Here is how I did it after a bit of googling for ‘line-line intersection’:

    /**
     * @param l1_1
     *            Point 1 of line 1.
     * @param l1_2
     *            Point 2 of line 1.
     * @param l2_1
     *            Point 1 of line 2.
     * @param l2_2
     *            Point 2 of line 2.
     * @return If the given lines intersect.
     */
    private boolean linesIntersect(Vec2 l1_1, Vec2 l1_2, Vec2 l2_1, Vec2 l2_2) {
        float UA = ((l2_2.x - l2_1.x) * (l1_1.y - l2_1.y) - (l2_2.y - l2_1.y) * (l1_1.x - l2_1.x)) / ((l2_2.y - l2_1.y) * (l1_2.x - l1_1.x) - (l2_2.x - l2_1.x) * (l1_2.y - l1_1.y));
        float UB = ((l1_2.x - l1_1.x) * (l1_1.y - l2_1.y) - (l1_2.y - l1_1.y) * (l1_1.x - l2_1.x)) / ((l2_2.y - l2_1.y) * (l1_2.x - l1_1.x) - (l2_2.x - l2_1.x) * (l1_2.y - l1_1.y));
        
        if (UA >= 0 && UA <= 1 && UB >= 0 && UB <= 1)
            return true;
        
        return false;
    }

Location

In truth, it is quite a bit messy, but this is the formula that I used. I am sure with a bit more research you could find one that is less messy, but this works for me I guess.

-wes

#5



Here are 3 different methods. But seriously, google is your friend.

#6

Thank you very much guys, I’ve got the line intersection algorithm working.
So happy right now, even though I don’t really understand how it works, the implementation is correct.
Tomorrow when I’ll have the time I’ll take a look at it again and try to write it out on paper to see how it really works.
When that’s done I’ll get working on the visibility algorithm, hopefully I’ll get it by tomorrow night. ;D :smiley:

Edit: Oh, and by the way, I’ve used this explanation for implementing the algorithm. Can recommend it for anyone who’s looking for a similar solution. :slight_smile:

#7

I’ve made a prototype using HTML5 canvas and Javascript (that’s what I use for all my prototyping and learning purposes, so easy to render with… <3), if somebody is interested in trying the system out or just want to take a look at the JS source code here’s the link: JS 2D Visibility Prototype
Once the page has loaded you can move your mouse in the bottom right cell to test out the application.
If you want to play around with it you can add your own walls in the window.onload function’s “// Add additional walls” section.
Have fun! :wink:

As I said this is only a prototype and all it does is the raycasting itself (and the rendering of the walls and the rays), it does not build a visibility mesh from the hit points just yet but I’ll implement that later too. For now I’m pretty happy with this. :smiley: