How to animate Tower of Hanoi?

Question

So I'm trying to animate the common puzzle Tower of Hanoi. I already wrote the algorithm to do this in the console, but I want to make a JApplet that pops up and animates the puzzle being solved after I ask for the number of disks. Here is my code for the algorithm if that helps. Just looking for some instruction, no need to write out the entire code. Thanks.

This is my code for the algorithm.

public class TowerofHanoi extends JFrame{

 static int count= 0;

public void move(int n, String start, String auxiliary, String end) {

       if (n == 1) {
           count++;
           System.out.println(start + " -> " + end);
       } else {
           count++;
           move(n - 1, start, end, auxiliary);
           System.out.println(start + " -> " + end);
           move(n - 1, auxiliary, start, end);
       }
   }

public static void main(String[] args) {
    // TODO Auto-generated method stub
       TowerofHanoi towersOfHanoi = new TowerofHanoi();
       System.out.print("Enter number of discs: ");
       Scanner scanner = new Scanner(System.in);
       int discs = scanner.nextInt();
       towersOfHanoi.move(discs, "A", "B", "C");
       System.out.println("This puzzle took "+count+" moves.");
   }

 public void paint(Graphics g) {
        g.drawRect (10, 10, 200, 200);  

      }
 public TowerofHanoi(){
     setPreferredSize(new Dimension(WIDTH, HEIGHT));
 }
    }

This is my code for the JApplet.

public class Graphics_TOH {

public static void main(String[] args) {
    // TODO Auto-generated method stub
    JFrame frame = new JFrame ("Draw Person");
       frame.setDefaultCloseOperation (JFrame.EXIT_ON_CLOSE);
       TowerofHanoi panel = new TowerofHanoi ();
       frame.getContentPane().add(panel);
       frame.pack();
       frame.setVisible(true);
}

Answer 1

This question is actually a little interesting to me, because it relates to a pet peeve of mine -- the way most programming languages rely on the call stack makes it way too difficult to reuse that nice little move() function of yours.

To do this kind of animation, you need to:

1. Set up a timer to cause a refresh of the panel several times (say 20) per second;
2. Remember the current time when the animation starts; and
3. Every time the panel refreshes itself, get the current time and draw what it is supposed to look like at that time.

The tricky part for you, of course, is step 3.

Lets say you want to draw one move per second. A refresh happens, you get the current time and find that it's been 4.234 seconds since the start of the animation. You calculate that you are 0.234 seconds into move 4, so you want to draw what it should look like 23.4% of the way through move 4.

In order to do this, you need to know: What discs are static on which pegs during move 4, and which disc is moving, its source peg, and its destination peg.

It would be pretty easy to fix your recursive move function to keep track of all that, BUT since it's going to generate ALL the moves at once, there is no way to have it tell you about move 4 specifically.

To fix this, you basically have 3 choices:

a) You could call your move function at the beginning, and have it record all the moves. Then when you have to draw, you could advance through the recorded moves to the correct one. This is easy, and probably practical. Of course it takes a lot of memory to record all the moves for a big puzzle (1M entries for 20 discs), but it also takes a lot of time to animate that (1 week at one move/sec), so you're not going to animate big puzzles anyway.

b) You could execute your recursive move function in a separate thread that exchanges information with the rendering thread on each redraw. This is actually a pretty common wait to do it in multiplayer games where the game state has to be tracked in "real time" anyway. For you, it is more trouble than it's worth.

c) You could rewrite your hanoi solution in a non-recursive way. Then you could implement an Iterator. This would work a lot like solution (a), but you would advance the iterator to generate new moves when necessary instead of iterating through prerecorded moves. The benefit is that you don't need to generate and store all the moves in advance.

If it were me, I would do solution (c), because I'm pretty comfortable with converting the recursive solution to an iterative one with a separate stack. If you are not comfortable with that sort of thing, then you probably want do do (a) and stuff all the moves into an ArrayList.

Answer 2

As a preparatory measure, create Objects of "Disk" type that'll hold the information to what numbered disks they are, then their "x" and "y" will be decided according to what tower they're on and on what number they're there.

To animate the whole process, you'll need to crate a stack of all the moves and keep pushing it as and when you reach the sysout between recursive calls.

When the stack is done, extract it out later, popping it and reading which disk was moved when, to what tower. In the Disk, you'll have a function for changing it's tower no.

The array of disks will show itself, where for each Disk you include a show() function wherein you draw rectangles at specified tower multiplied by a constant and at a certain height, here for leaving out complexity,leave out alteration of heights.

This is all you need. Literally,just convert the above lines into code and you're done. If you want proper height, you'll have to create 3 stacks which hold disks and pop and push while extracting info from the main Stack where you stored all moves. Show function will now include parameters about tower and its stacked position , and that is where you'll draw the rectangle.

I have written highly understandable JavaScript code (running on p5.js framework) inspired by your question and it'll completely teach you how well you can handle the disks in a simple program for Towers of Hanoi.

Visit this link: My Sketch

var amount =22; 
Stack = [];
disks = [];
Sos= [];
A = [];
B = [];
C = [];

var frR =5;

var slider;

function Disk(n){
  this.n=n;
  this.tower=1;
  this.x=10+this.tower*200;
  this.y=100+n*12;

  this.show = function(i,j){
    rectMode(CENTER);
    fill(map(n,0,amount,1,350),260,260);
    rect(-100+(j+1)*350,300-i*12,10 +n*20,10);
  }
}

function setup() { 
  createCanvas(1200, 600);
  slider=createSlider(1,80,frR);
  slider.position(20,400);
    Hanoi(amount,1,2,3);
  frameRate(frR);
  colorMode(HSB);

  Sos.push(A);
  Sos.push(B);
  Sos.push(C);



  for(var i =0 ; i < amount; i++){
    disks.push(new Disk(i));


  }
  for(var i =amount-1 ; i >=0; i--){
    Sos[0].push(disks[i]);
  }

}

function draw(){
  if(frameCount < Stack.length)
    drawIt();
}

function drawIt() { 
  background(0);
    frR=slider.value();
  frameRate(frR);
  push();
  fill(255);
  noStroke();
   text("Select Speed :",20,380);

  textSize(20);
  text("Steps taken  :  " + frameCount+ " / " + Stack.length + " ." ,450,450);
  text("[ " + amount + "  disks  ]", 520,490);
  rect(500,308,1800,2);
  for(var j =0 ; j< 3; j++)
  rect(-100+(j+1)*350, 188,2,240);
  pop();


  for(var j =0 ; j< 3; j++){
    for(var i =0 ; i < Sos[j].length; i++){
      Sos[j][i].show(i,j);

    }
  }

  var current = Stack[frameCount-1];
  Sos[current[1]-1].pop();
  Sos[current[2]-1].push(disks[current[0]]);
}


function Hanoi(n, from, to , via)
{
  if (n==0) return;

  Hanoi(n-1, from, via , to);
//createP(n + " from" + from + " to " + to);
  Stack.push([n,from,to]);
  Hanoi(n-1, via, to , from);
}