Algorithm animations

[Sam Hobbs]

If you know how to use newsgroups, then try asking in the newsgroup:

comp.graphics.animation

For DirectAnimation use the newsgroup:

microsoft.public.multimedia.directx.danimation.controls

While looking for something useful about DirectAnimation, I found something describing SVG. It is a proposed standard for the internet. Look at Scalable Vector Graphics (SVG), but don't ask me for more about it since everything I know is the result of a brief look at that page.

[Homestead]

Thanks a lot but I dont know how to use it,
Thanks for links, advice and ideas,
But as I already mentioned, I will use OpenGL...
And I will also install DirectX, leaning it when I have free time...

Regards,

Homestead

[galathaea]

I've been wanting to reply to this question, but I kinda figured it might take a bit of my time, so I wanted to wait until after the holidays. I hope you are still interested.

This is actually where a lot of my study in linguistics and the foundations of mathematics and science was focused in the work I did on my philosophy major in college, and is still very dear to my heart. In fact, I sincerely believe that it is one of the necessary foundations for future education focused on the multimiedia experience.

But I think that some of the previous concentrations have been focused on the wrong details. Of course you need some kind of programming framework, and openGL is probably the much better choice since it is so easily portable (which would be an important part of educational material or even game-oriented material such as this -- I personally believe there's not much of a difference between games and education conceptually, just most games stop at kindergarten level of ability testing). But the algorithmic expression languages are very much visual.

My belief is that category theory is the best place to start research in this field. Its a field of mathematics that break expressions of algorithmics into point or circular pieces known as objects or identities and arrow looking creatures which point from one object to another known as morphisms / morphs. Categories are defined as collections of points and arrows that obey the basic relationship semantics:

• for any objects A, B, C which have morphs f:A->B, g:B->C, there exists a morph h:A->C called the composition morph of f and g and written left-linearly as h = g o f.
• for every object X, there is an identity morph idX:X->X such that any other morphs y:Y->X or z:X->Z obey y o idX = y and idX o z = z.
• (associativity) (a o b) o c = a o (b o c).

The concept of equality in category theory is expressed in what are known as commutative diagrams which are just pictures of objects and morphs where all paths in the diagram from some object M to some object N are considered to produce objects N in the same state. Also defined by the theory are functors between categories and higher order mappings.

In other words, category theory is inherently a visual language. And it is a complete model theory (in other words, it can be used as an foundations to all of mathematics alternative to set theory), so it can be applied to any mathematical process anywhere. The only problem I found in my research was that the way it is used in the mathematics community is basically descriptive. Commutative diagrams are placed in mathematical texts to highlight interesting relationships between objects and morphs, but there is rarely (or ever?? -- I have yet to see..) full proofs or algorithmic evaluations done completely in the visual language of category theory. And part of this has to do with the lack of a natural abstraction semantics.

So what I developed was an extension to the language of categories. Commutative diagrams were wrapped up in larger circles and given their own object status. In fact, commutative diagrams are used as the definition process for objects. I introduced abstract or generic objects and morphs, which I distinguished from actualised versions by drawing them with dashed or dotted lines and circles. And I introduced a more fundamental notion of negation which are visually displayed by slashes through the circle or arrow being denied.

With just these basics, along with a bit more formalisation on naming of these things, name matching, and some other minutiae, I was able to show how entire proofs can be formulated in this language visually and entire algorithm evaluations can be traced. I was interested at one point in using such technology as well in functional language debuggers and hooking it up to a joystick to control flow evaluations based on user input, as a possible operating systems foundations. Using some creative drawing of the pieces and some cool animation, such a system can be both educational and illustrative as well as interactive and test-oriented.

I would first suggest looking around the net for some info on category theory. There are some sites with pictures (ugly pictures though, the product of stiff mathematicians who never feel comfortable wrapping nice designs around their tools) that can give a good first idea of what I'm talking about. You should also check your local college library for the works of people like Eilenberg, MacLane, Lawvere, Grothendieck, and Steenrod. I first learned category theory through the fascinating book Topoi: the categorial analysis of logic by Goldblatt, but Categories for the working mathematician is the classic starter in the field and the others have written more in depth studies. Lawvere is fascinating in that it seems that he too was quite interested / awe-struck at the potential use of category theory for a foundations of concept science back in the 50s and 60s when the field was really starting to become popular.

Then use your creativity. Make things visually interesting. Animate the arrows. Show the traditional linear language algorithmics along with the diagrams. When you see

2 x = 6

transform into

x = 3

in the linear language, animate the two in a flipping move pivoted from the equals and collapsing under the 6 to divide it into the 3.

Once you have some ideas worked out and a foundational framework built, really there is nothing stopping the animation of the most complex or obtuse proofs or algorithmic evaluations in mathematics...