Fixing My Processing.js Data Structure Animations

Over the holidays, I spent some time fixing some code for a processing.js data structures and algorithms animation project that I had been working on.  Check out the results here:

Now, a bit of a story about the code.  About 2 years ago, I wrote some code to do some animations of sorting algorithms while I was learning Processing.js.  The idea was to build a library of these animations that my students can use as reference. I wanted to add animations for all the data structures and algorithms we covered in my data structures class. Although I was able to implement two simple sorts using my previous code, I had quite quickly realized that there were two big flaws in the way I had designed my code.  The first is that the animations were frame based.  I basically went and changed the frame rate in my sketch to get the animation to play at the speed I wanted… not a good idea but it was something that was easy to code with pjs so I had done it that way. The bigger problem however was that I had written a state transitioning mess of a program.

The way that Processing works is that there is a single draw() function that is repeatedly called to produce an animation.  The way that I have coded my animation was to have different states for each of my objects and depending on what I wanted to show, I would modify the state of that object.  So if the array was swapping the values of two elements, the array object would be in a swapping state. The drawing and animation was pretty simple.  Change the state, change what animation to play. However, when it came time to code the actual sort animations though, I realized I had a problem.  Translating the procedural sorts into a series of state transitions of the various animation objects was difficult to do.  When completed the animation code was a big mess and does not in any way resemble the sorting algorithm. For example here is the original mess that drew the bubble sort animation (don’t cringe too much… it was a first attempt :P)

  void draw(){
    if(!sorted_){
      if(array_.state()==array_.STABLE){
        if(array_.atIdx(currJ_)>array_.atIdx(currJ_+1)){
          src_.setHighLighter(7);
          array_.setLetterColour(currJ_,#ff0000);
          array_.setLetterColour(currJ_+1,#ff0000);
          array_.swap(currJ_,currJ_+1);
        }
        if(array_.state()==array_.STABLE){
          src_.setHighLighter(6);
          array_.setLetterColour(currJ_+1,#000000);
          array_.setLetterColour(currJ_,#000000);
          currJ_++;

          array_.changeIndicator(0,currJ_);
          array_.changeIndicator(1,currJ_+1);
          if(currJ_ >= sortLength_){
            src_.setHighLighter(4);
            currJ_=0;
            array_.changeIndicator(0,currJ_);
            array_.changeIndicator(1,currJ_+1);
            sortLength_--;
            if(sortLength_==0){
              sorted_=true;
              src_.setHighLighter(11);
            }
          }
          array_.setSplitterPosition(sortLength_+1);
        }
      }
    }
    else{
      array_.setSplitterPosition(0);
    }
    array_.draw();
    src_.draw();
  }

As you can see it does not in any way resemble a bubble sort… no loops, just a nasty series of state transitions. After completing the animation for bubble and insertion I posted my code to github and just left it as is… I always wanting to go back to add more but the thought of translating something more complicated into that mess made my head hurt.

Sometime in the fall I was talking with my friend Phil about the mess I made with my code and trying to think of a way to fix it or possibly even rewriting it. He pointed out that what I needed was really an animation system… something that you can record and play back. Essentially the idea is that you would run through a standard algorithm as is on some given piece of data. During the process of running through the algorithm, the system would “record” the states the animation objects should go through. Displaying the animation was simply playing back the recorded steps. My new design involves 3 new objects (they are not yet complete .. but complete enough for sorting algorithms).

  • Animation step – one discrete step in an animation. I wanted a way to allow for the ability to step through an algorithm. Each step may involve modifying multiple objects or even modifying one object in more than one way but it is taken as one whole step.
  • Animation Instruction – an instruction sent to an object that changes the object’s state in some way… The way it is currently implemented is a series of instructions represented by a constant, and parameters to the instructions which are all done as integers. Its not the best way to do this… but for now it works.
  • Animation – contains a list of animation objects (things that are drawn), and a list of animation steps.

In any case… this method works. Here is the function that creates the bubble sort animation:

void bubble(int array[],int sz){
    int i,j;
    int tmp;
    for(i=0;i<sz-1;i++){
        bubbleSort.addStep();
        bubbleSort.addInstruction(0,SET,4);
        for(j=0;j array[j+1]){
                bubbleSort.addStep();
                bubbleSort.addInstruction(1,SETFONTCOLOUR,j,255,0,0);
                bubbleSort.addInstruction(1,SETFONTCOLOUR,j+1,255,0,0);
                bubbleSort.addStep();
                bubbleSort.addInstruction(0,SET,7);
                bubbleSort.addInstruction(1,SWAP,j,j+1);
                tmp=array[j];
                array[j]=array[j+1];
                array[j+1]=tmp;
                bubbleSort.addStep();
                bubbleSort.addInstruction(1,SETFONTCOLOUR,j,0,0,0);
                bubbleSort.addInstruction(1,SETFONTCOLOUR,j+1,0,0,0);
            }
        }
        bubbleSort.addStep();
        bubbleSort.addInstruction(2,SET,15-(i+1));
    }
    bubbleSort.addStep();
    bubbleSort.addInstruction(2,SET,0);
    bubbleSort.addInstruction(0,SET,0);
}

You can actually see the bubble sort algorithm in here… the animation steps and animation instructions are simply like “print” functions except that they state what should be drawn instead. Each of the addInstruction() calls passes in the index of the animation object to modify and the instruction (SET, SETFONTCOLOUR, etc.) and parameters of the instructions. its not perfect but its way better than the original.  The animation has also been fixed to be time based.  Furthermore, while it is not currently implemented,  it will be possible to allow a step through of the animation also.

I have updated both animations for insertion and bubble sort using this new animation system.  I have also implemented the animation of selection sort and quicksort.  Both were not really hard to do (though I admit that I would want to tweak the quick sort a bit as it isn’t quite as accurate as I would like). Hopefully others will find these animations useful.  Let me know if there is an error or something that is unclear with how the animation is done.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s