FireApplet - Project Description

FireApplet - Project Description
Overview
This is a very simple applet that uses a diffusion-type cellular automata to simulate a burning flame. In order to minimize its computational impact on the host machine, the applet cuts a few corners. These areas are discussed below. Because this applet was originally an exercise in optimization, I believe the main loop is fairly compact (from a code point of view - I haven't yet evaluated how high-level Java code gets translated to Java byte-code).

The Algorithm

This algorithm is a specific instance of a more general matrix overlay method commonly used in image processing. This method works by superimposing a pattern over each pixel of the original image, performing some math on the pixels under the pattern, and storing the result in a new image. The pattern for this algorithm is shown at the right (where "C" indicates the current pixel). All pixels marked with a "*" are summed, the result divided by 4 (a mathematical average), a constant value is subtracted (to dim the flame), and the result stored in the original pixel location. A benefit of this method is that everything can be done in-place in the original image (this is not true in general since other pixels may depend on the original value of the current pixel). To compute the next generation, this pattern is applied to the current generation from left-to-right, top-to-bottom, and the new image drawn.

+---+---+---+
|   | C |   |
+---+---+---+
| * | * | * |
+---+---+---+
|   | * |   |
+---+---+---+

Areas of Interest

Double-Sized Pixels - A simple speed-up that gives 4x the area for "free" by plotting every pixel as a 2x2 block.
Incorrect Edge Behavior - Another speed-up. Technically, the behavior at the left and right edges should "wrap around" to the other side. However, to avoid the necessary if statements in the inner loop, the applet treats these cases the same as the general case. Since the top-left and bottom-right pixels are not subject to the pattern overlay (because of their position), this does not cause the array access violation that would otherwise be expected.
Double-Image - As long as one image has been computed, why not duplicate it alongside the original and double the area for "free?" This would produce a seamless result if the edge behavior were correct (due to the way the flame is calculated), but does not in this case. Despite this, as long as the duplication is moderate (as opposed to ten identical images next to each other), it is usually difficult to detect.

Conclusion
As this was originally an optimization problem, it taught me a lot about the way Java handles graphics and how to code faster Java routines. However, TANSTATFC (There Ain't No Such Thing As The Fastest Code - Michael Abrash, Zen of Code Optimization), so I'm sure there's plenty of room for improvement. That's what's neat about optimization - as good as you make it, there's always a way to make it even better. As time and interest permit, I may return to this applet in the future to see what else I can learn from it.

The applet is available.
The source code is available for educational purposes.