Search

Nov 21, 2016

# Elm Enlightenment: Raycasting with Bresenham’s Algorithm

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 `List`s of these `Point`s.

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 `Point`s 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 `Point`s 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.

### Juan Pablo Claude

Reviewer Big Nerd Ranch

During his tenure at BNR, Juan Pablo has taught bootcamps on macOS development, iOS development, Python, and Django. He has also participated in consulting projects in those areas. Juan Pablo is currently a Director of Technology focusing mainly on managing engineers and his interests include Machine Learning and Data Science.

Speak with a nerd

Schedule a call today! Our team of nerds are ready to help