Rendering Lo-fi Lightning

A few months ago, I was creating some silly special effects for the screens that appear when you win or lose a race in Last Train to Timbuktu. In the losing screen, the sky turns dark, rain pours down, and lightning flashes down on your train as it grinds to a halt. So, I needed a way to render lightning.

Fortunately, Academia came to the rescue! I found a paper by Theodore Kim and Ming Lin at UNC called "Physically Based Animation and Rendering of Lightning" that modified the dielectric breakdown model to simulate electrical arcs. They produced renderings that look like this:

That looks pretty darn nice. Unfortunately, the simulation requires solving many large matrix equations. This is something I wanted to avoid, particularly on mobile devices. So, I adapted the approach to make it more efficient and simpler to implement, while still generating nice results for lo-fi rendering, like this:

The main idea is to discretize the drawing area into square cells, choose two cells to be the source and target of the lightning bolt, and simulate the path of electric charge through the grid. Choosing a target at the outset departs somewhat from the more realistic physical simulation used in the paper, but makes the overall process much more efficient, as I'll describe.

After choosing the bolt's source and target, the simulation proceeds by keeping track of the cells in the bolt. (Initially, this is only the source cell.) Each timestep, one more cell is added to the bolt, extending the lightning. When the target cell gets added, the bolt is complete and the simulation ends.

The trick, obviously, is to choose which cell to add to the lightning bolt so that it ends up looking believable. The key to the dielectric simulation approach is to make the choice probabilistically, based on a work function that estimates how much energy is used to travel from one cell to another. The more work required to expand the bolt to a cell, the less likely that cell will be chosen.

In Kim & Lin's simulation, each cell possesses a value representing an electric charge. Choosing the correct cell to expand to requires solving Laplace's equation - this step is what makes the approach computationally expensive.

By choosing the target cell at the outset, I avoided this time-consuming step. In my approach, the probability of adding a given cell to the lightning bolt is proportional to exp(-d(C,T)), where d(C,T) is the distance between the candidate cell and the target cell. Notice that the larger the distance between the cells, the smaller this exponential is. The simulation thus prefers to expand to cells nearer to the target, but has a random chance to expand in another direction.

Putting this together, the overall algorithm can be expressed in pseudocode as follows:

From the point of view of physical simulation, it is "cheating" to choose the target ahead of time, since lightning doesn't know where it's going to end up. But from my perspective, the lightning has to end up somewhere, so if I just choose the target cell randomly, and still get nice looking bolts like the ones below, while running the simulation quickly enough to render on a phone, then I'm happy.

Let me briefly describe the actual rendering process. The bolt is rendered each timestep, so that you can see it grow across the screen. I rendered each cell in the bolt with two rectangles. the background rectangle is slightly larger than the cell size, and its colour is taken randomly in HSV space between bright blue and bright purple. This gives the bolt its "electric" border. The foreground rectangle is bright and just off-white. You could obviously render this in many more sophisticated ways, but graphical effects are not really a priority with Last Train to Timbuktu, since it's a puzzle game.

I thought this was a nice example of taking a fairly rigourous academic result and choosing when and how to take shortcuts to achieve acceptable performance, while still basing techniques on solid foundations. I hope you found the simulation technique interesting!

(Last Train to Timbuktu is free for Android devices on the Google Play Store!)