- AV Catalog
- Field Reports
- For Developers
- OpenDSA Project
- Getting Started
- Newsletter #1
Submitted by ajalon on 29 March 2010 - 11:35am
A major concern in AV implementation is the interaction between the algorithm itself, and the interface that allows users to control pacing through and interaction with the algorithm.
Designing interaction into your AV
Perhaps the single most important difference between a successful AV and an unsuccessful one is the level of user interaction provided. Passively watching an animation is only marginally better than reading a textbook, and all studies on AV use show that there is no pedagogical advantage to passive viewing of an AV. There are many ways to add interaction to an AV. One conceptually simple (though pedagogically meaningful) change is to break the action into a series of meaningful states, and have progress through the states be driven by the user clicking on a "next" button. For example, if you are implementing Quicksort, have the user direct the AV when to advance to the next state. More meaningful interaction can be had by requiring the user to provide feedback about what has happened or what is about to happen. The user can predict where the next swap will take place, or answer a question in a pop-up box.
However, adding in such control can be difﬁcult. The reason is that there needs to be appropriate interaction between the user interface controls (written as call-back functions under control of the runtime environment) and the algorithm action. The nice thing about an animation is that the algorithm can simply direct the action as it does its work, with no need to relinquish control to the user. But real interaction demands that the algorithm's action be broken up into appropriate pieces. How can this be implemented? Here are some suggestions.
1. As mentioned above, progression through the action can be viewed as a series of state changes. The trick is to execute one state change, then return control to the user interface. When the user clicks the "next" button, control is returned to the algorithm. But how can this be done? One possibility is to completely encapsulate the current state of the algorithm in a data object of some sort. When the "next" button is clicked, it calls a method that implements the action of the algorithm. That method will read the current state object, reconstitute the current state of the algorithm, and progress the algorithm to the next state. It will then save the state and return control to the UI. This is a truly general purpose approach that should work in pretty well any circumstance. Unfortunately, it can be quite complicated to deﬁne and store the state of the algorithm. Consider a recursive algorithm for insertion into a BST that wishes to make a state as each node of the tree is visited. Since the algorithm is recursive, it will be necessary to save the complete recursion stack as part of the state description. When the "next" button is clicked, the algorithm method will recover the recursion stack, get to the right place in the tree, and proceed from there.
2. Since the algorithm needs to stop periodically to allow the UI to act, another approach is to use separate threads for each. That is, the algorithm runs in a separate thread that simply puts itself on hold when it reaches the next state. The "next" button's call-back function needs only to restart the algorithm thread. This can be a nicely implemented in Java.
3. One deﬁciency of the dual-thread method is that there is no way to back up. It can be helpful to the user to be able to "rewind" the action by backing up one or more states. A third alternative to state control is to go re-examine the idea of using animation. However, instead of actually doing the animation while the algorithm is progressing, the algorithm instead writes a state descriptor at each state to some list that captures the entire set of states for the algorithm. Fortunately, in this case a "state" can be much simpler than in approach (1). It merely needs to encode whatever is necessary to drive the display, such as the positions of nodes or the dividing point in an array for the quicksort partition. Most AVs will need only a few 10s of bytes per state and a few 10s of states on each run of the algorithm, so the total amount of storage is low. Once the list of states has been created, the list is given to the UI controller to process. Each click of the "next" button merely moves from one state descriptor to the next. Hitting the "back" button simply moves backwards in the state array.