Monday, January 23, 2006
Algorithm: fire simulation
Back in the mid 90's I worked on a project that required to graphically simulate a roaring fire.
At the time I wrote the algorithm in assembly. The algorithm was rendering the flames as fast as possible writing straight into the memory of the VGA.
The algorithm to create this animation is very simple, but the effect is suprisingly good.
A few days ago I stumbled across this old code and decided to port it in UJML. The port was very easy and took no more than 30 minutes.
A demo can be seen from your Java enabled web browser simply clicking here: flames demo
Now, let's talk about the algorithm. It is very simple.
Let's assume that we want to have a fire defined by an image composed by 40x70 pixels. This particular dimension is the one used in the demo, but any other dimension could be used (in my original assembly code, for example, the fire size was 640x480).
The algorithm uses a fixed 256 color predefined palette that defines the various colors of a fire. At index 0 we find black, or the darkest color of the fire, and at index 255 we find white, or the brighter color of the fire.
The colors are picked carefully to go smoothly from black, to blue, to red, to yellow all the way to white. These are the colors of a realistic wood fire, but any other color could be picked to simulate different types of fires. For example a gas fire could be made out of shades of blue. I'll leave this as an exercise for the reader :)
An array of 40x70 elements is used to represent the fire image.
Each element of the array represents the index of a color in the palette.
The array is initially set to all zeros. This is done to simulate the fact that the first frame represents the image of no fire, or fire off. It's all black.
Then the algorithm starts by randomly generating a raw of pixels at the bottom of the fire. This raw of pixels is the "burning area", were all the flames are generated. These pixels can be either white or black. White is a "hot" spot, and black is a "cold" spot.
With each iteration (or frame) the algorithm calculates the new values of the colors of each pixel of the image. The calculation of each pixel is based on some of the neighbour pixels below the current pixels being calculated. This simulates the fire roaring upward. The basic idea is to darken the various pixels as the fire raises. This simulates the fire getting colder further from the burning material (bottom raw).
Some adjustment is done to shorten the length of the fire (different adjustments could be done to make it longer, depending on the desired effect).
The code is pretty self explanatory and I invite you to take a look. The UJML source code is public domain. Do whatever you like with it.
The UJML source can be viewed here.
If you want to download the pure source just right click here, select "Save Target As..." and save it on your hard drive with name "flames.ujml".
Note that this algorithm has some very interesting properties. It allows, for example, to simulate fire balls, burning objects , fires going in any direction, fires moved by wind etc...
If anybody is interested in these variations let me know and stay tuned. I'll publish them in some future posts on this blog.