hanyeah

做了个汉诺塔小游戏。

加上了自动求解。

大多数讲汉诺塔，都是作为递归算法的经典案例来讲。

自动求解，也都是从最初状态到目标状态。

对于任意初始状态的汉诺塔，如何求解，很少有人讲。

知乎上发现一个大神，写的很详细。有兴趣可以拜读一下。

汉诺塔杂谈（二）——汉诺塔图 - 知乎 (zhihu.com)

为了防止上面的链接不能用，下载了一个pdf版的：pdf版 。

效果如下：

代码：

package  {
 
 import flash.display.MovieClip;
 import flash.display.SimpleButton;
 import flash.display.Sprite;
 import flash.events.Event;
 import flash.events.MouseEvent;
 import flash.geom.Point;
 
 
 public class Hanoi extends MovieClip {
  
  public var mc1: MovieClip;
  public var mc2: MovieClip;
  public var mc3: MovieClip;
  public var mc4: MovieClip;
  public var mc5: MovieClip;
  public var mc6: MovieClip;
  public var overMc: MovieClip;
  public var btn1: SimpleButton;
  public var btn2: SimpleButton;
  private var stack1: Array = [];
  private var stack2: Array = [];
  private var stack3: Array = [];
  private var poles: Array = [];
  private var tweenMc: Object = null;
  private var stacks: Array = [];
  private var mcs: Array = [];
  public function Hanoi() {
   // constructor code
   stage?initStage(null): addEventListener(Event.ADDED_TO_STAGE, initStage);
   overMc.visible = false;
   overMc.btn.addEventListener(MouseEvent.CLICK, onRestart);
   btn1.addEventListener(MouseEvent.CLICK, onRestart);
   btn2.addEventListener(MouseEvent.CLICK, onAutoPlay);
  }
  
  private function initStage(e:Event):void 
  {
   removeEventListener(Event.ADDED_TO_STAGE, initStage);
   drag(mc1);
   drag(mc2);
   drag(mc3);
   mc1.id = 1;
   mc2.id = 2;
   mc3.id = 3;
   onRestart(null);
   addEventListener(Event.ENTER_FRAME, onEnterFrame);
  }
  
  private function onEnterFrame(e:Event):void 
  {
   if (tweenMc) {
    tweenMc.t += 1 / stage.frameRate;
    var per: Number = Math.min(1.0, tweenMc.t / tweenMc.duration);
    tweenMc.x = tweenMc.ox + Math.min(per * 5, 1.0) * (tweenMc.tx - tweenMc.ox);
    tweenMc.y = tweenMc.oy + per * (tweenMc.ty - tweenMc.oy);
    if (per == 1) {
     var cb: Function = tweenMc.complete;
     tweenMc = null;
     cb();
    }
   }
  }
  
  private function onRestart(e:MouseEvent):void 
  {
   if (tweenMc || curSp) {
    return;
   }
   overMc.visible = false;
   stack1 = [mc1, mc2, mc3];
   stack2 = [];
   stack3 = [];
   poles = [mc4, mc5, mc6];
   mc1.stack = stack1;
   mc2.stack = stack1;
   mc3.stack = stack1;
   mc1.pole = mc4;
   mc2.pole = mc4;
   mc3.pole = mc4;
   mc4.stack = stack1;
   mc5.stack = stack2;
   mc6.stack = stack3;
   stacks = [stack1, stack2, stack3];
   mcs = [mc1, mc2, mc3];
   for (var i: int = 0; i < stack1.length; i++) {
    stack1[i].x = mc4.x;
    stack1[i].y = getPosY(i);
   }
  }
  
  private function onAutoPlay(e:MouseEvent): void {
   if (!tweenMc && !curSp && !overMc.visible) {
    autoPlay();
   }
  }
  
  private function getPosY(i: int): Number {
   return 290 - i * 20;
  }
  
  private function canDrag(mc: MovieClip): Boolean {
   return !tweenMc && !curSp && (onTop(stack1, mc) || onTop(stack2, mc) || onTop(stack3, mc));
  }
  
  private function onTop(stack: Array, mc: MovieClip): Boolean {
   return mc == getTop(stack);
  }
  
  private function getTop(stack: Array): MovieClip {
   return stack[stack.length - 1];
  }
  
  private function dragEnd(mc: MovieClip): void {
   for (var i: int = 0; i < poles.length; i++ ) {
    var pole: MovieClip = poles[i];
    if (canPut(mc, pole)) {
     put(mc, pole);
     return;
    }
   }
   put(mc, mc.pole);
  }
  
  private function canPut(mc: MovieClip, pole: MovieClip): Boolean {
   if (checkHit(mc, pole)) {
    var tp: MovieClip = getTop(pole.stack);
    return !tp || tp == mc || tp.id < mc.id;
   }
   return false;
  }
  
  private function checkHit(mc: MovieClip, pole: MovieClip): Boolean {
   return mc.hitTestObject(pole);
  }
  
  private function put(mc: MovieClip, pole: MovieClip): void {
   mc.stack.pop();
   mc.stack = pole.stack;
   mc.stack.push(mc);
   mc.pole = pole;
   tweenTo(mc, pole.x, getPosY(mc.stack.length - 1), 0.3, checkWin);
  }
  
  private function tweenTo(mc: MovieClip, x: Number, y: Number, duration: Number,  cb: Function): void {
   // mc.x = x;
   tweenMc = mc;
   tweenMc.ox = mc.x;
   tweenMc.oy = mc.y;
   tweenMc.tx = x;
   tweenMc.ty = y;
   tweenMc.t = 0;
   tweenMc.duration = duration;
   tweenMc.complete = cb;
  }
  
  private function checkWin(): void {
   if (isWin()) {
    overMc.visible = true;
   }
  }
  
  private function isWin(): Boolean {
   return stack3.length == 3;
  }
  
  //-----------------------------
  private var curSp:MovieClip;
  private var draged:Boolean = false;
  
  private function drag(sp:Sprite):void
  {
   sp.buttonMode = true;
   sp.addEventListener(MouseEvent.MOUSE_DOWN, mouseDownHandler);
  }
  
  private function mouseDownHandler(e:MouseEvent):void
  {
   if (!canDrag(e.currentTarget as MovieClip)) {
    return;
   }
   curSp = e.currentTarget as MovieClip;
   curSp.startDrag();
   addEventListener(MouseEvent.MOUSE_MOVE, mouseMoveHandler);
   stage.addEventListener(MouseEvent.MOUSE_UP, mouseUpHandler);
   stage.addEventListener(Event.MOUSE_LEAVE, mouseUpHandler);
  }
  
  private function mouseUpHandler(e:MouseEvent):void
  {
   dragEnd(curSp);
   curSp.stopDrag();
   curSp = null;
   removeEventListener(MouseEvent.MOUSE_MOVE, mouseMoveHandler);
   stage.removeEventListener(MouseEvent.MOUSE_UP, mouseUpHandler);
   stage.removeEventListener(Event.MOUSE_LEAVE, mouseUpHandler);
  }
  
  private function mouseMoveHandler(e:MouseEvent):void
  {
   //
   draged = true;
  }
  
  //----------------------------------
  
  private function autoPlay(): void {
   var s: String = getCurState();
   var p: Array = findPath(s);
   trace('-------------auto play-----------------');
   trace('current state:', s);
   trace('path:', p.join('->'));
   step(p, 0);
  }
  
  
  private function step(p: Array, n: int): void {
   if (n == p.length - 1) {
    overMc.visible = true;
    return;
   }
   var st: Array = getStep(p[n], p[n + 1]);
   doStep(st[0], st[1], function() {
    step(p, n + 1);
   });
  }
  
  private function getStep(s1: String, s2: String): Array {
   trace(s1, s2);
   for (var i: int = 0; i < s1.length; i++) {
    var c1: String = s1.charAt(i);
    var c2: String = s2.charAt(i);
    if (c1 != c2) {
     return ['ABC'.indexOf(c1), 'ABC'.indexOf(c2)];
    }
   }
   return null;
  }
  
  private function doStep(a: int, b: int, cb: Function): void {
   var mc: MovieClip = stacks[a].pop();
   stacks[b].push(mc);
   var pole: MovieClip = poles[b];
   tweenTo2(mc, pole.x, getPosY(stacks[b].length - 1), 3, cb);
  }
  
  private function tweenTo2(mc: MovieClip, x: Number, y: Number, duration: Number, cb: Function): void {
   tweenTo(mc, mc.x, 30, duration / 3, function(){
    tweenTo(mc, x, 30, duration / 3, function(){
     tweenTo(mc, x, y, duration / 3, cb);
    });
   });
  }
  
  private function findPath(s: String): Array {
   for (var i: int = 0; i < paths.length; i++) {
    var p: Array = paths[i];
    for (var j: int = 0; j < p.length; j++) {
     if (s == p[j]) {
      return p.slice(j);
     }
    }
   }
   return null;
  }
  private var paths: Array = [
   ['BBB', 'BBC', 'BAC', 'BAA', 'CAA', 'CAB', 'CCB', 'CCC'],
   ['AAA', 'AAC', 'ABC', 'ABB', 'CBB', 'CBA', 'CCA', 'CCC'],
   ['BCC', 'BCB', 'BAB', 'BAA', 'CAA', 'CAB', 'CCB', 'CCC'],
   ['ACC', 'ACA', 'ABA', 'ABB', 'CBB', 'CBA', 'CCA', 'CCC'],
   ['CAC', 'CAB', 'CCB', 'CCC'],
   ['CBC', 'CBA', 'CCA', 'CCC'],
   ['BBA', 'BBC', 'BAC', 'BAA', 'CAA', 'CAB', 'CCB', 'CCC'],
   ['BCA', 'BCB', 'BAB', 'BAA', 'CAA', 'CAB', 'CCB', 'CCC'],
   ['ACB', 'ACA', 'ABA', 'ABB', 'CBB', 'CBA', 'CCA', 'CCC'],
   ['AAB', 'AAC', 'ABC', 'ABB', 'CBB', 'CBA', 'CCA', 'CCC']
  ];
  
  private var tree: Array = [
   'CCC', [
    'CCB', [
     'CAB', [
      'CAC', null, 
      'CAA', [
       'BAA', [
        'BAB', [
         'BCB', [
          'BCA', null,
          'BCC', null
          ]
         ],
        'BAC', [
         'BBC', [
          'BBB', null,
          'BBA', null
          ]
         ]
        ]
       ]
      ]
     ], 
    'CCA', [
     'CBA', [
      'CBC', null,
      'CBB', [
       'ABB', [
        'ABA', [
         'ACA', [
          'ACC', null,
          'ACB', null
          ]
         ],
        'ABC', [
         'AAC', [
          'AAB', null,
          'AAA', null
          ]
         ]
        ]
       ]
      ]
     ]
    ]
   ];
  private function getCurState(): String {
   var a: Array = [];
   for (var i: int = 0; i < mcs.length; i++) {
    for (var j: int = 0; j < stacks.length; j++){
     if (stacks[j].indexOf(mcs[i]) != -1){
      a[i] = 'ABC'.charAt(j);
      break;
     }
    }
   }
   return a.join('');
  }
  
 }
 
}

源码打包下载