algorithm - How can I generate a lightning bolt effect?

Is there an algorithm to generate a lightning bolt?

I would like an algorithm that generates a list of segment or point objects specifying where the bolt will land. The method would need a start point parameter, along with an endpoint. The bolt should have random branches coming off it, and zig-zag at random intervals. The result will be a random lightning effect that would look somewhat like this

_{(source: wikimedia.org)}

If anyone knows of an algorithm that this may work for, help would be greatly appreciated!

Answer

There's a fairly straightforward algorithm you can use to generate lighting bolts.

Start with a line segment between the bolt's origin (O) and end point (E)

Choose a point on that line (approximately or exactly in the middle), called S and split the segment into two line segments (O->S and S->E). Displace S away from the original line segment (along the segment's normal) by some small random amount. This gives you a single "bend" of lightning.

After you compute the bend, based on a small random chance you'll want to add a third line segment (usually an extension of the O->S segment). This is how you produce the "forks" in the lightning. You'll usually want to track information about the intensity of the bolt during this generation process, because you'll want the forks to be dimmer or have a more subtle blur:

Then, repeat the above process for all of the new line segments you have; you'll need to choose a repetition amount that produces shapes you like:

There's a fairly clear explanation of this technique at my friend's blog here (it's where I shamelessly stole the pictures from); it goes into additional depth about adding the glow effect as well.

Finally, there's also this NVIDIA paper that describes the same basic algorithm (also with more details).