How to code animations of data structures and algorithms

In this post I am going to explain how the animations on my webpage are coded. They are visual explanations of data structures and algorithms, and to understand this post you better check them out here first.

The list of ingredients for this project is short: Javascript, (animated) SVG and a JS lib called svg.js, which ties JS and SVG together. In case you didn't know, modern browsers not only display SVG content seamlessly as part of an HTML5 document, but can also animate changes in this SVG. Changes can mean changing colors of elements or positions, sizes and more.

Before a data structure can be animated, it has to be draw statically. In the case of e.g. a binary heap, this means laying out nodes, represented as circles with a number, in a complete binary tree. This involves computing positions and issuing commands to draw geometric objects with certain properties at the right locations. svg.js gives fairly low-level access to SVG, but allows enough attributes to be configured. It is up to me as the programmer to keep track of position in a data structure and compute the layout.

An advantage of working with SVG is that it is scalable, which is what the 'S' stands for. This means that you can work with a fixed coordinate frame of known width and height, but later have the graphic scaled seamlessly to fit the HTML document of whatever size. This is done by using a percentage size for the entire SVG document relative to the enclosing div element in the HTML document.

So once the binary heap is drawn, we want to show changes to it visually. This means inserting and removing values or using the heap to sort an array. The easy part is implementing these operations on the basic data structure. The hard part is keeping the changes to the underlying data structure in sync with the changes in the animation representing it graphically. While changes to the underlying heap in our example, could happen very quickly, the representing animations have to be timed right for optimal display. This can be done with svg.js by chaining functions to each be called at the end of the previous animation step, or simply by using a setTimeout() call.

Over the course of coding the eight subpages currently on the project I experimented with different styles to make this work. I started with a functional approach in plain JS, passing configuration as parameters. Later I tried an OO style, creating classes for various display objects and inheriting functionality. This worked better than the first version, but was still not as flexible for changing behaviour as desired.

It turns out that a lot of configuration parameters are needed: colors, sizes and thickness, modes of operation like displaying a heap sort vs. just showing the heap, ranges of numeric values to be used, speed of animation and more. These are kept in a simple Javascript object of key-value entries with defaults overwritten as needed for different panels in a page.

For most pages of the project I implemented speed controls, which allow the reader to change the display speed of animations or to pause animation all together and later resume animation at the same point. These were added a while after launching most pages, and required substantial changes to the source to make them work. The basic operation is to call a function for each next step, which checks whether the state is paused or not and then computes the current animation step time from configuration and user setting.

I don't want to make this post too long, just a starter, but if I get enough ❤️ I will go into more detail 😃