Ray casting in 2D game engines

ultimate cheatsheet

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.

Line-segment - ray intersection point

Assume that point \(P\) is the intersection point of line-segment defined by points \(A\) and \(B\), and ray defined by points \(C\) and \(D\). Point \(P\) is then expressed by set of two equations: \[ \left\{\begin{align} P &= s(B - A) + A\text {, where } 0 \leq s \leq 1 \text{, and} \\ P &= r(D - C) + C\text {, where } r \geq 0 \text{.} \end{align}\right. \] \[ r = \tfrac{(B_x - A_x)(C_y - A_y) - (C_x - A_x)(B_y - A_y)}{(D_x - C_x)(B_y - A_y) - (B_x - A_x)(D_y - C_y)} \] \[ s = \tfrac{(A_x - C_x)(D_y - C_y) - (D_x - C_x)(A_y - C_y)}{(D_x - C_x)(B_y - A_y) - (B_x - A_x)(D_y - C_y)} \] Having \(s\) and \(r\) calculated, we can calculate \(P\) using one of the equations from the set.

Illuminating the visible area

  1. Cast rays on all vertices
  2. For every cast ray, cast two additional rays offseted by small angle
  3. Sort intersection points
  4. Draw a visibility polygon by connecting sorted intersection points
Casting slighly offsetted rays

Consider ray \(AB\) starting at \(A = (A_x, A_y)\) going through \(B = (B_x, B_y)\). We want to find such point \(C = (C_x, C_y)\) that ray \(AC\) would be rotated by \(\phi\) with \(A\) being the origin point. \(C\) coordinates would be as follow: \[ \left\{\begin{align} 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{align}\right. \]

Sorting intersection points

\[ P_1 > P_2 \leftrightarrow atan2(P_{1_y} - A_y, P_{1_x} - A_x) > (P_{2_y} - A_y, P_{2_x} - A_x) \]

Circle - ray intersection point

Let \(P\) be an intersection point, \(A\) a ray's anchor point, \(B\) a point on the ray, \(C\) a circle's center point and \(r\) a circle's radius. \[ \left\{\begin{align} a &= (B_x - A_x) ^ 2 + (B_y - A_y) ^ 2 \\ b &= 2((B_x - A_x)(A_x - C_x) + (B_y - A_y)(A_y - C_y)) \\ c &= (A_x - C_x) ^ 2 + (A_y - C_y) ^ 2 - r ^ 2 \\ \Delta &= b ^ 2 - 4ac \end{align}\right. \]

  • \(\Delta < 0\): ray does not intersect the circle,
  • \(\Delta = 0 \): ray intersects the circle in one point (tangent),
  • \(\Delta > 0 \): ray intersects the circle in two points.

Only if \(\Delta = 0\): \[ \begin{align} t = \tfrac{-b}{2a} \end{align} \] Only if \(t \geq 0\): \[ \left\{\begin{align} P_x &= t(B_x - A_x) + A_x \\ P_y &= t(B_y - A_y) + A_y \end{align}\right. \]

Only if \(\Delta > 0\): \[ \left\{\begin{align} t_1 &= \tfrac{-b -\sqrt{\Delta}}{2a} \\ t_2 &= \tfrac{-b +\sqrt{\Delta}}{2a} \\ \end{align}\right. \] Only if \(t_i \geq 0\): \[ \left\{\begin{align} P_{i_x} &= t_i(B_x - A_x) + A_x \\ P_{i_y} &= t_i(B_y - A_y) + A_y \end{align}\right. \]

Spatial hashmaps

Using spatial hashmaps allows 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.

We can use them for things such as implementing viewports, visibility circles and flashlights.

Bresenham-based supercover line algorithm

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.

Casting rays on circles

Let \(P_i\) be tangent points, \(A\) a ray's anchor point, \(C\) a circle's center point and \(r\) a circle's radius.
We will also be moving all points using translation vector \(\overrightarrow{v} = (-C_x, -C_y)\): \(X^\prime = X + \overrightarrow{v}\), so the circle's center is at \((0,0)\).

Applies to all cases below:

  • \(\Delta < 0\): there are no tangent points (ray's anchor point is in the circle),
  • \(\Delta = 0 \): there is only one tangent point (ray's anchor point),
  • \(\Delta > 0 \): there are two tangent points.

Case #1 (\(A_x ^ \prime \neq 0 \land A_y ^ \prime \neq 0\)):
\[ \left\{\begin{align} a &= A_x ^{\prime ^ 2} + A_y ^{\prime ^ 2} \\ b &= - 2r ^ 2 A_y ^ \prime \\ c &= r ^ 4 - r ^ 2 A_x ^ {\prime ^ 2} \\ \Delta &= b ^ 2 - 4ac \end{align}\right. \]

Only if \(\Delta = 0\): \[ \left\{\begin{align} P_y ^ \prime &= \tfrac{-b}{2a} \\ P_x ^ \prime &= \tfrac{r ^ 2 - P_y ^ \prime A_y ^ \prime }{A_x ^ \prime} \end{align}\right. \] \[ \left\{\begin{align} P_x &= P_x ^ \prime + C_x \\ P_y &= P_y ^ \prime + C_y \end{align}\right. \]

Only if \(\Delta > 0\): \[ \left\{\begin{align} P_{1_y} ^ \prime &= \tfrac{-b -\sqrt{\Delta}}{2a} \\ P_{2_y} ^ \prime &= \tfrac{-b +\sqrt{\Delta}}{2a} \\ P_{i_x} ^ \prime &= \tfrac{r ^ 2 - P_{i_y} ^ \prime A_y ^ \prime }{A_x ^ \prime} \end{align}\right. \] \[ \left\{\begin{align} P_{i_x} &= P_{i_x} ^ \prime + C_x \\ P_{i_y} &= P_{i_y} ^ \prime + C_y \end{align}\right. \]

Case #2 (\(A_x ^ \prime = 0 \land A_y ^ \prime \neq 0\)):
\[ \left\{\begin{align} a &= A_y ^ {\prime ^ 2} \\ b &= 0 \\ c &= r ^ 4 - r ^ 2 A_y ^ {\prime ^ 2} \\ \Delta &= b ^ 2 - 4ac \end{align}\right. \]

Only if \(\Delta = 0\): \[ \left\{\begin{align} P_x ^ \prime &= \tfrac{-b}{2a} \\ P_y ^ \prime &= \tfrac{r ^ 2}{A_y ^ \prime} \end{align}\right. \] \[ \left\{\begin{align} P_x &= P_x ^ \prime + C_x \\ P_y &= P_y ^ \prime + C_y \end{align}\right. \]

Only if \(\Delta > 0\): \[ \left\{\begin{align} P_{1_x} ^ \prime &= \tfrac{-b -\sqrt{\Delta}}{2a} \\ P_{2_x} ^ \prime &= \tfrac{-b +\sqrt{\Delta}}{2a} \\ P_{i_y} ^ \prime &= \tfrac{r ^ 2}{A_y ^ \prime} \end{align}\right. \] \[ \left\{\begin{align} P_{i_x} &= P_{i_x} ^ \prime + C_x \\ P_{i_y} &= P_{i_y} ^ \prime + C_y \end{align}\right. \]

Case #3 (\(A_x ^ \prime \neq 0 \land A_y ^ \prime = 0\)):
\[ \left\{\begin{align} a &= A_x ^ {\prime ^ 2} \\ b &= 0 \\ c &= r ^ 4 - r ^ 2 A_x ^ {\prime ^ 2} \\ \Delta &= b ^ 2 - 4ac \end{align}\right. \]

Only if \(\Delta = 0\): \[ \left\{\begin{align} P_y ^ \prime &= \tfrac{-b}{2a} \\ P_x ^ \prime &= \tfrac{r ^ 2}{A_x ^ \prime} \end{align}\right. \] \[ \left\{\begin{align} P_x &= P_x ^ \prime + C_x \\ P_y &= P_y ^ \prime + C_y \end{align}\right. \]

Only if \(\Delta > 0\): \[ \left\{\begin{align} P_{1_y} ^ \prime &= \tfrac{-b -\sqrt{\Delta}}{2a} \\ P_{2_y} ^ \prime &= \tfrac{-b +\sqrt{\Delta}}{2a} \\ P_{i_x} ^ \prime &= \tfrac{r ^ 2}{A_x ^ \prime} \end{align}\right. \] \[ \left\{\begin{align} P_{i_x} &= P_{i_x} ^ \prime + C_x \\ P_{i_y} &= P_{i_y} ^ \prime + C_y \end{align}\right. \]

Case #4 (\(A_x ^ \prime = A_y ^ \prime = 0\)):

No tangent points (\(A = C\)).