I’m building a game in Elm, and I wanted to illuminate a circle of light around the character, to reveal the visible parts of the game world, like you see in the screenshot.

How can we do this in Elm?

We can use raycasting: emitting lots of photons and seeing how far each goes until it encounters something that absorbs it.
There are a few different strategies for raycasting: continuous and discrete.
In continuous raycasting, we aren’t concerned with illuminating a fixed grid but rather a smooth space with arbitrary obstructions.
(Besides, there is already a great tutorial on this style of raycasting in Elm.)

For our purposes—illuminating a regular grid where obstructions are “whole-cell” blockers—we can use Bresenham’s algorithm for discrete raycasting.

Points

When engineering an Elm application, it is often useful to start by guessing at types.
Consider points in the plane with integer-valued coordinates: What sort of type could these points inhabit?

We will write a Point type alias of a tuple of Ints.
This definition captures the idea of a point as a “pair of integer-valued coordinates”.

type alias Point = (Int, Int)

This permits direct construction of a Point value like this:

pt = (1,2)

-- a point at the origin
origin = (0,0)

-- a point far away from the origin
farAway = (1000000,1000000)

The lines we want to build will be Lists of these Points.

Note that a line can be geometrically defined as a pair of points in the plane (i.e., a starting and an ending point).
However, since we are concerned with discrete space, we must be able to represent the set of points on a fixed grid which approximate an “ideal” geometric line.

While we’re thinking about the Point type, let’s use it!
We write a Euclidean distance calculation.
This computes how far apart two Points are from one another:

distance : Point -> Point -> Float
distance (ax,ay) (bx,by) =
  let
    dx =
      toFloat (ax - bx)

    dy =
      toFloat (ay - by)
  in
    sqrt( (dx*dx) + (dy*dy) )

Simple Lines

Let’s consider the elementary case of horizontal and vertical lines first.

The structure of such axis-aligned lines in the plane can be described as follows:

• The value of one coordinate will be the same for every point making up the line.
• The value of the other coordinate will “move” according to our direction.

So for the case of vertical lines, we are walking along a line parallel to the y-axis. We map over the range of y coordinates, joining each y coordinate with the given x coordinate:

vline : Int -> Int -> Int -> List Point
vline x y0 y1 =
  if y1 < y0 then
    List.reverse (vline x y1 y0)
  else
    List.map (y -> (x,y)) [y0..y1]

Note that for a downward line, we swap y coordinates and reverse the resulting line.

Elm evaluates a range where the end value is less than the start value as [] (the empty list).
To ensure we end up with a non-empty list, we must ensure the start value of the range precedes the end.

Taking this into account we can write a horizontal line function similarly, but reflected for the x-axis:

hline : Int -> Int -> Int -> List Point
hline y x0 x1 =
  if x1 < x0 then
    List.reverse (hline y x1 x0)
  else
    List.map (x -> (x,y)) [x0..x1]

Mr. Bresenham

Bresenham’s algorithm is a strategy for finding the set of pixels which most closely approximate a line.
With a strategy analogous to the simpler cases of the horizontal and vertical lines we have seen already, we can implement a fully general line-drawing method.
We can already construct a straight line by walking along the axis with one coordinate and assigning the specified value to the other coordinate.
In the general case, we will walk an axis, but now we are instead concerned with identifying the grid coordinate closest to the “ideal” geometric line. Our line-drawing strategy will be as follows:

• First, we construct an “ideal” line function f using the slope (dy/dx) to determine which y coordinate to take on given a specific x coordinate
• Next, we map f over the range of values for the x coordinate, thereby computing the y value using our ideal line function
• Finally, we round this value to an integer and assemble our list of points

We can write the core of this idea in Elm like this:

    let
      f = x ->
        slope * toFloat (x - ax)

      slope =
        dy / dx
    in
      [(ax)..(bx)]
      |> List.map (x -> (x, round (f x) + ay))

One wrinkle here is what happens if ax > bx? This case is an issue since Elm will give us an empty array for [ax..bx].
So we will need to handle this condition similarly to the horizontal line cases: invert the source and destination, then reverse the resulting line.

A second wrinkle lies in handling the case where the difference in the y-axis is greater than the difference in the x-axis (i.e., dy > dx), in which case we will need to walk the other axis instead.
Choosing the correct axis to walk is important to ensure we are making a fully-connected line.

Accounting for these nuances, we can now write a fairly general line-drawing helper function line', which takes the two points and returns the “pixellated” line joining them:

line' : Point -> Point -> List Point
line' (ax,ay) (bx,by) =
  let
    dy =
      toFloat (by - ay)
    dx =
      toFloat (bx - ax)
  in
    if abs dx > abs dy then
      let
        f = x ->
          slope * toFloat (x - ax)

        slope =
          dy / dx
      in
        if ax > bx then
          List.reverse (line' (bx,by) (ax,ay))
        else
          [ax..bx]
          |> List.map (x -> (x, round (f x) + ay))
    else
      let
        f = y ->
          slope * toFloat (y - ay)

        slope =
          dx / dy
      in
        if ay > by then
          List.reverse (line' (bx,by) (ax,ay)))
        else
          [(ay)..(by)]
          |> List.map (y -> (round (f y) + ax, y))

There is one final wrinkle to handle, which are the horizontal and vertical lines.

Why are these not handled well in the method above? Consider the definition of slope: it tends to infinity as the denominator dy goes to zero. But luckily, the cases where this difference is zero are precisely the same horizontal and vertical line cases we worked out initially. Integrating those cases we can write a high-level line drawing method.

line : Point -> Point -> List Point
line (ax,ay) (bx,by) =
  if ax == bx then
    vline ax ay by
  else if ay == by then
    hline ay ax bx
  else
    line' (ax,ay) (bx,by)

We now have ready a generalized line-drawing method suitable for use in raycasting!

Optics

The idea is this: we want to emit lots of photons and see how far each goes until it encounters something that absorbs it.

Let’s first write a method which casts a single photon towards a given destination.

Our method castRay will take a max illumination depth (power), a set of points which block the ray (blockers), and finally source and target points (src and dst). We will report back the list of Points the photon traversed until it was absorbed.

castRay : Int -> Set Point -> Point -> Point -> List Point
castRay power blockers src dst =
  let
    pts =
      line src dst
      |> List.tail
      |> Maybe.withDefault []

    notAbsorbed = pt ->
      not (Set.member pt blockers)
      && not ((Point.distance src pt) > toFloat power)

  in
    pts
    |> takeWhile' notAbsorbed

takeWhile' : (a -> Bool) -> List a -> List a
takeWhile' predicate list =
  case list of
    []      -> []
    x::xs   -> if (predicate x) then x :: takeWhile' predicate xs
               else [x]

Let’s use castRay to write a general illumination function!
The idea is to emit photons from a source towards each point along a perimeter.

Once we have the set of illuminated lines, we can fold them together to provide a list of illuminated points.

The method we write will again take a maximum illumination depth (power) and a set of points which should block photons (blockers).
We also accept a list of points to cast rays towards (perimeter), and finally a point source.
We return a list of illuminated points.

illuminate : Int -> List Point -> Set Point -> Point -> List Point
illuminate power perimeter blockers source =
  let
    rays =
      castRay power blockers source
  in
    perimeter
    |> List.concatMap rays

Demonstration

This is precisely the lighting algorithm used in mandos, a tiny Rogue clone I built while learning Elm. Here it is in action.

Closing Thoughts

The way to functional programming enlightenment can seem long, if not interminable. But you don’t need abstract algebra to get started!

Implementing algorithms in a functional language offers significant advantages not just in performance but also in clarity and concision. You will find Elm offers a particularly focused and expressive set of tools for describing and solving problems.

In short: try Elm for yourself! You may be surprised at how much fun it is.

And please consider giving us some feedback! We’d love to hear about your own path to functional illumination.

The post Elm Enlightenment: Raycasting with Bresenham’s Algorithm appeared first on Big Nerd Ranch.