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.
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
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
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) )
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]
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
fusing the slope (
dy/dx) to determine which y coordinate to take on given a specific x coordinate
- Next, we map
fover 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
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!
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.
castRay will take a max illumination depth (
power), a set of points which block the ray (
blockers), and finally source and target points (
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]
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 (
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
This is precisely the lighting algorithm used in mandos, a tiny Rogue clone I built while learning Elm. Here it is in action.
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.