Ray casting in 2D Game Engines

last updated Jan 12, 2022
Read other articles
Post cover photo

In my opinion, ray casting is a beautiful concept that is not that hard to grasp, but the quality resources are rare. We will learn the math behind it so you can implement it in your future projects with ease. I will try to make it as comprehensible as possible, explain all the caveats and issues you may stumble upon. We will also talk about optimization and how can spatial hash maps significantly help you. I will also provide some basic live examples for you to try out. Please note that demos were written to be as simple as possible, do not expect enterprise-grade code - we only learn about the concept, not the implementation.

What is ray casting?

Ray casting is the most basic of many computer graphics rendering algorithms that use the geometric algorithm of ray tracing. Ray tracing-based rendering algorithms operate in image order to render three-dimensional scenes to two-dimensional images... The idea behind ray casting is to trace rays from the eye, one per pixel, and find the closest object blocking the path of that ray – think of an image as a screen-door, with each square in the screen being a pixel. This is then the object the eye sees through that pixel.

Wikipedia on Ray casting

Well, it does not tell us much, does it? Let me simplify that. Ray casting is a fundamental and popular technique used to determine the visibility of specific objects (polygons) by tracing rays from the eye (for instance, player’s hero) on every pixel (well, not quite in our case - more on that later) and finding the nearest intersections with objects.

Where might ray casting be used?

Ray casting has many uses, especially in three-dimensional space. I outlined three, in my opinion, the most important, which are commonly used in 2D game engines:

Creating 3D perspective in a 2D map

The most well-known game that used this technique is Wolfenstein 3D. Rays were traced to determine the closest objects, and their distance from the player position was used to appropriately scale them.

Wolfenstein 3D Wolfenstein 3D

Point-in-polygon problem

PIP problem asks whether a given point lies inside, outside, or on the boundary of a polygon. Using the ray casting algorithm, we can count how many times the point intersects the edges of the polygon. If the number of the intersections is even, the point is on the outside of the polygon. If the number of the intersections is odd, the point is on the inside or on the boundary of a polygon.

Point-in-polygon problem Point-in-polygon problem

Object visibility and light casting

This is the problem we will specifically tackle in this article - determining which objects are visible by the player and illuminating the visible area.

Object visibility and light casting Object visibility and light casting

Object visibility and light casting in 2D games

In this section we will go through basics such as calculating intersection points, casting rays, sorting intersection points to illuminate the visible area, and few words about circles. I will provide interactive demos at each stage so you do not get lost and see the results immediately.

Line-segment - ray intersection point

It is all about those intersection points. Let's learn step by step how to find them and how to use them. We will derive a line parametric equation first, calculate intersection points and finally learn how to efficiently determine which one of them is the closest.

Deriving line parametric equation

Let us talk about lines and their parametric equation first.

Line example Line example

We can express vector AP\overrightarrow{AP} by the following equation: AP=tAB\overrightarrow{AP} = t\overrightarrow{AB}, where tt is an equation parameter defining how much do we stretch (t>1|t| > 1) or shrink (t<1|t| < 1), and if we flip the direction (t<0t < 0) of vector AP\overrightarrow{AP} in relation to vector AB\overrightarrow{AB}.

Let me show you few examples:

Vectors examples Vectors examples

As you might have noticed, we can use tt as a scale factor: d(A,P)=td(A,B)d(A, P) = t * d(A, B), where dd denotes the euclidean distance between two points. We will use that fact when determining the closest intersection point.

Now we can easily see, that if we want the point to be contained on:

  • line: tRt \in \mathbb{R},
  • ray: t0t \geq 0,
  • line-segment: 0t10 \leq t \leq 1.

Having all of that sorted out, we can finally derive the parametric equation:

AP=tABPA=t(BA)P=t(BA)+A\begin{align*} \overrightarrow{AP} &= t \overrightarrow{AB} \\ P - A &= t (B - A) \\ P &= t(B - A) + A \\ \end{align*}

If you still do not know what happens here, I can recommend an awesome short lecture by Norm Prokup: Parametrizing a Line Segment - Concept.

Calculating the intersection point

Assume that point PP is the intersection point of line-segment defined by points AA and BB, and ray defined by points CC and DD. Point PP is then expressed by set of two equations:

{P=s(BA)+A, where 0s1P=r(DC)+C, where r0\begin{cases} P = s(B - A) + A\text {, where } 0 \leq s \leq 1 \\ P = r(D - C) + C\text {, where } r \geq 0 \end{cases}
Solve for and
Substitute into the second equation
Substitute into the first equation

Having ss and rr calculated, we can calculate PP using one of the equations from the set.

Intersection points

Finding the closest intersection point

We only need the closest intersection point to properly draw the visible area. The naive solution would be to calculate distances between the ray starting point and intersection points using the Pythagorean Theorem: (CxPx)2+(CyPy)2\sqrt{(C_x - P_x) ^ 2 + (C_y - P_y) ^ 2}. Remember the line equation parameter, though? I have already mentioned that we can use it as a scale factor. As we want to compare distances on ray, we can check for the smallest rr parameter value: CP1<CP2r1<r2|\overrightarrow{CP_1}| < |\overrightarrow{CP_2}| \Leftrightarrow |r_1| < |r_2|.

Closest intersection points

Casting rays

In the following section we will go through two different ways rays might be cast. We will compare them and mention their pros and cons.

Casting rays by offset angle

First way is to cast rays in all directions by specified offset angle. For instance, we could cast 30 rays in total offseted by 1212^\circ. Let's see how to generate all those rays first.

Let P1=(x1,y1)P_1 = (x_1, y_1) be an anchor point of our rays, and let P2=(x2,y2)P_2 = (x_2, y_2) be a some point on a line going through P1P_1 at angle ϕ\phi:

Angle offset Angle offset

We can define x2x_2 as x1+dxx_1 + dx and y2y_2 as y1dyy_1 - dy (our y-axis is inverted hence why the minus sign). Now we need to derive formulas for dxdx and dydy:

{sin(ϕ)=dydistdy=distsin(ϕ)cos(ϕ)=dxdistdx=distcos(ϕ)\begin{cases} \sin(\phi) = \tfrac{dy}{\mathit{dist}} \Rightarrow dy = \mathit{dist} * \sin(\phi) \\ \cos(\phi) = \tfrac{dx}{\mathit{dist}} \Rightarrow dx = \mathit{dist} * \cos(\phi) \end{cases}

dist\mathit{dist} in our case has an arbitrary (greater than 0) value (we are looking for any point on the line), so we are safe to assume dist=1\mathit{dist} = 1 to simplify the calculations. Having it all considered, P2=(x1+sin(ϕ),y1cos(ϕ))P_2 = (x_1 + \sin(\phi), y_1 - \cos(\phi)), where ϕ\phi is our angle offset.

Casting rays by offset angle

Casting rays on vertices

Casting rays on vertices is most likely your go-to solution. Instead of casting rays in all directions, we can simply cast them on our polygons' vertices. Depending on the number of vertices, we can save computing power by not casting useless rays. In the next sections you will see how does it impact animation smoothness and also learn how to further optimize the whole process.

Casting rays on vertices

Illuminating the visible area

This is where the real fun begins. We will illuminate the visible area by filling a giant polygon.

Sorting intersection points

To correctly order vertices to build a proper polygon, we need to sort them by angle first. We will use atan2(y,x)atan2(y, x) function for that. You can read more about it here.

Let's compare both ray casting methods:

Casting rays by offset angle
Casting rays on vertices

Both of them look glitchy, jumpy and inaccurate. Let's take a closer look why.

Casting slightly offseted rays

Notice what happens when rays are cast directly on vertices - they should go beyond that vertex but we are getting only the closest intersection point. The most common solution is casting two extra rays offseted by small angle (in both directions) for every cast ray. Consider ray ABAB starting at A=(Ax,Ay)A = (A_x, A_y) going through B=(Bx,By)B = (B_x, B_y). We want to find such point C=(Cx,Cy)C = (C_x, C_y) that ray ACAC would be rotated by ϕ\phi with AA being the origin point. CC coordinates would be as follow:

{Cx=(BxAx)cos(ϕ)(ByAy)sin(ϕ)+AxCy=(ByAy)cos(ϕ)+(BxAx)sin(ϕ)+Ay\begin{cases} C_x = (B_x - A_x)\cos(\phi) - (B_y - A_y)\sin(\phi) + A_x \\ C_y = (B_y - A_y)\cos(\phi) + (B_x - A_x)\sin(\phi) + A_y \end{cases}
Offseted rays Offseted rays

Note that we do not need to do it for the first method - simply add or substract the offset from the angle we are calculating from. For further explanation you can check this article.

Let's see how the illumination behaves after changes:

Casting rays by offset angle
Casting rays on vertices

It did not help much for the first method. We could decrease angle offset (hence increase number of rays) but the result will still be poor. On the other hand, the second method looks very smooth and accurate. From now on, we will not be talking about the first method anymore.

Visibility circle and flashlight

We may want to somehow limit player's visibility. We can achieve that by creating a clipping region of desired shape. In the demos below, I used a CanvasRenderingContext2D.clip() method.

Visibility circle
Flashlight

As you might have noticed, there is no optimization whatsoever - we are still calculating all the intersection points. We will get back to it once we learn about spatial hashmaps.

What about circles?

I have rarely seen a real use-case scenario for ray casting on circles. Please treat this section as an extra where I only briefly talk about it. I will provide you with equations and basic demos, the rest is up to you.

Circle - ray intersection point

Let PP be an intersection point, AA a ray's anchor point, BB a point on the ray, CC a circle's center point and rr a circle's radius.

Equation set
Solve for
Solve the quadratic equation
  • : ray does not intersect the circle,
  • : ray intersects the circle in one point (tangent),
  • : ray intersects the circle in two points.
Only if and
Only if and
Circle intersection points

Casting rays on circles

We need to find two tangent lines to a given circle passing through a ray anchor point.

Let PiP_i be tangent points, AA a ray's anchor point, CC a circle's center point and rr a circle's radius.

We will also be moving all points using translation vector v=Cx,Cy\overrightarrow{v} = \langle-C_x, -C_y\rangle: X=X+vX^\prime = X + \overrightarrow{v}, so the circle's center is at (0,0)(0,0).

From the circle equation
From the perpendicular line to the circle's radius
Solve the equation system
Substitute into the first equation
Solve the quadratic equation
  • : there are no tangent points (ray's anchor point is in the circle),
  • : there is only one tangent point (ray's anchor point),
  • : there are two tangent points.
Only if
Only if

There is still one issue - it will not work if Ax=0A_x ^ \prime = 0.

Take a closer look at the following equation: r2=PxAx+PyAyr ^ 2 = P_x ^ \prime A_x ^ \prime + P_y ^ \prime A_y ^ \prime. If Ax=0A_x ^ \prime = 0, the equation becomes: r2=PyAyr ^ 2 = P_y ^ \prime A_y ^ \prime - we cannot substitute PxP_x ^ \prime anymore.

Here are the steps for solving the equation system once that happens:

Solve the equation system
Substitute into the first equation
Solve the quadratic equation
  • : there are no tangent points (ray's anchor point is in the circle),
  • : there is only one tangent point (ray's anchor point),
  • : there are two tangent points.
Only if
Only if

Note that we can do the same for Ay=0A_y ^ \prime = 0, however, it is optional.

If Ax=Ay=0A_x ^ \prime = A_y ^ \prime = 0, there are no solutions.

Rays on circles

Few optimization techniques

In this section, we will discuss the usage of spatial hashmaps and modified Bresenham's line algorithm. I will not go into implementation details as they are commonly available on the Internet. I will, however, provide you with some demos to try these out and come up with your own ideas on where to use them.

Spatial hashmaps

Currently, we are drawing all polygons and calculating all intersection points, but it is pretty much useless. In most cases, our play area will be much bigger than the viewport. By using spatial hashmaps, we can quickly determine which polygons are visible to the player and perform adequate calculations.

Basically, we want to divide the play area into smaller cells (of predefined size). Each cell consists of a list containing our shapes (most likely line-segments). If a single shape spans across multiple cells, it will be included in all of them.

The name of this technique suggests using hashmaps (eg. cells would be named something like X+":"+Y), but in our case, using a simple 2D array might be more desired.

Here is a simple demo showing how it might work:

We can use them for viewports as mentioned previously, and also visibility circles and flashlights.

Spatial hashmaps

Bresenham-based supercover line algorithm

Well, it is high time we did something with finding the closest intersection points. Using spatial hashmaps and modified Bresenham's line algorithm, we can traverse the grid in an efficient manner making as few checks as required. The algorithm should stop when the first cell with an intersection point is found.

You can read more about Bresenham's line algorithm here, and its modified version here.
Brasenham-based supercover line algorithm

Everything has an end

Sorry, unfortunately, I mean this article and not rays. haha, very funny

I think I have covered everything to help you get started. I will try my best to expand it in the future if I spot something needing an additional explanation.

If you enjoyed the read be sure to follow me for more content like that in the future. Also do not forget to message me if one of the topics seems to be poorly explained or you have other suggestions.

Stay tuned for more!