What's the best way to make an animated GIF using an algorithm?

Question

I have an algorithm for knight's tours on chessboards of various sizes (large sizes, like 100x100) and I'd like to animate the result. Each time the knight moves to a new square, a corresponding pixel in the (square) canvas will change colours, until eventually the whole canvas is coloured in. The resulting movies will be available for viewing on a web page about the algorithm.

Animated GIFs seem like the best method if I want broad browser support (though other suggestions are welcome). What is the best tool or library to do this with? I'm happy to use anything that's freely available on a Linux or Mac computer.

The actual algorithm is too long to make a useful example here (see this paper if you're really curious) but here's pseudocode for a (boring) king's tour on an 8x8 board:

movie = new Movie()
frame = new Frame()
frame.fillRectangle((1,1), 8, 8, BLUE)
for row in [1..8] {
    if (row.isOdd()) { colrange = [1..8] } else { colrange = [8..1] }
    for col in colrange {
        frame.colourPixel(row, col, RED)
        movie.addFrame(frame)
    }
}
movie.saveAsGIF("tour.gif")

Extra-credit question: can we take advantage of the special features of this movie to reduce the file size? The Wikipedia article suggests that we might be able to do this, if we are only changing some of the pixels - in fact we are only changing one per frame!

Ornelas

Don't use animated gifs. Convert it to a movie format instead, the compression will be much higher – Smalto

What format do you suggest, and what tool to create it with? – Ornelas

Compression levels depend on a lot of things. For simple images gifs will do just fine. Besides, size might not be as much of a concern as simplicity. Animated gifs aren't wonderful technology, but they are well supported. – Interpellate

Answer 1

You can use giflib to accomplish this. Documentation is in the download.

As an example, this page contains animated gifs created using giflib and source code to the program used to generate the animations. Might be helpful to see how to use giflib for animations.

Edit: Another alternative, if you don't mind some post-processing, is to simply output your frames using a simple format (such as PPM) and then make the animated gif using ImageMagick.

As for your extra credit question: ImageMagick can even do frame comparisons for you to reduce the size of the output.

Interpellate

Thanks for this. I'm thinking of taking your second option: using Python Image Library to draw a collection of .gifs, and then ImageMagick to put them together into an (optimized) animation. – Ornelas

Answer 2

In response to your extra credit question, you could do this improvement yourself by only drawing the changed part of the image on the new frames and setting the rest to be transparent.

Deegan

Got it. Seems like ImageMagick will do the comparison and optimisation for me, but I can do it manually if that doesn't seem to work. – Ornelas