MCMC on 15puzzle

by uwi 22 May 2010

• Related works: 1
Embed

/**
 * Copyright uwi ( http://wonderfl.net/user/uwi )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/5SXj
 */

package {
    import flash.display.Loader;
    import flash.display.Sprite;
    import flash.display.Bitmap;
    import flash.display.BitmapData;
    import flash.display.DisplayObject;
    import flash.display.LoaderInfo;
    import flash.geom.Point;
    import flash.geom.Rectangle;
    import flash.text.TextField;
    import flash.events.Event;
    import flash.events.MouseEvent;
    import flash.net.URLRequest;
    import flash.system.LoaderContext;
    import com.bit101.components.*;

    [SWF(backgroundColor="0x000000", frameRate="60")]
    public class MCMC15 extends Sprite {
        private var _tf : TextField;
        private var _f : Vector.<uint>;
        private var _l : Loader;
        private var _bmps : Array; //<Bitmap>
        
        private var _w : Number;
        private var _h : Number;
  
        public function MCMC15() {
        		graphics.beginFill(0);
        		graphics.drawRect(0, 0, stage.stageWidth, stage.stageHeight);
        		graphics.endFill();
        	
            _tf = new TextField();
            _tf.textColor = 0xffffff;
            _tf.width = 200;
            _tf.height = 100;
            addChild(_tf);

            _f = new Vector.<uint>(16);
            init();
            
            var shuffle : PushButton = new PushButton(this, 0, 400, "shuffle", onShuffleClick);
            
            _l = new Loader();
            _l.load(new URLRequest("http://assets.wonderfl.net/images/related_images/d/df/dfae/dfae160f843ceb3408e646413761bafe0b294b46"), new LoaderContext(true));
            _l.contentLoaderInfo.addEventListener(Event.COMPLETE, onLoadComplete);
        }
        
        private function onShuffleClick(e : MouseEvent) : void
        {
        		init();
        		if(!this.hasEventListener(Event.ENTER_FRAME))addEventListener(Event.ENTER_FRAME, onEnterFrame);
        }
        
        private function onLoadComplete(e : Event) : void
        {
        		var li : LoaderInfo = LoaderInfo(e.target);
        		li.removeEventListener(Event.COMPLETE, onLoadComplete);
        		var dobj : DisplayObject = li.content;
        		_w = dobj.width;
        		_w += (4 - (_w % 4));
        		_h = dobj.height;
        		_h += (4 - (_h % 4));
        		var base : BitmapData = new BitmapData(_w, _h, false, 0x000000);
        		base.draw(dobj); 
        		
        		_bmps = [];
        		for(var i : uint = 0;i < 15;i++){
        			var bmd : BitmapData = new BitmapData(_w / 4, _h / 4, false, 0x000000);
        			var y : uint = i / 4;
        			var x : uint = i % 4;
        			bmd.copyPixels(base, 
        				new Rectangle(_w * x / 4, _h * y / 4, _w / 4, _h / 4),
        				new Point(0, 0)
        				);
        			var bmp : Bitmap = new Bitmap(bmd);
        			bmd.lock();
        			_bmps.push(bmp);
        			addChild(bmp);
        		}
        		paint(_f);
        		addEventListener(Event.ENTER_FRAME, onEnterFrame);
        }
              
        // index番目に空きがある時の移動可能なセル
        private const MOV : Array = [
        		[1, 4],
        		[0, 2, 5],
        		[1, 3, 6],
        		[2, 7],
        		[0, 5, 8],
        		[1, 4, 6, 9],
        		[2, 5, 7, 10],
        		[3, 6, 11],
        		[4, 9, 12],
        		[5, 8, 10, 13],
        		[6, 9, 11, 14],
        		[7, 10, 15],
        		[8, 13],
        		[9, 12, 14],
        		[10, 13, 15],
        		[11, 14]
        		];
        
        // 初期化
        private function init() : void
        {
        		var i : uint;
        		for(i = 0;i < 16;i++){
        			_f[i] = i;
        		}
        		_space = 15;
        		
        		// shuffle
        		for(i = 0;i < 1000;i++){
        			var v : uint = MOV[_space][int(Math.random() * MOV[_space].length)];
        			_f[_space] = _f[v];
        			_f[v] = 15;
        			_space = v;
        		}
        		
        		_gct = 0; 
        		_cur = calcVal(_f);
        }
        
        private function paint(f : Vector.<uint>) : void
        {
        		var i : uint;
        		for(i = 0;i < 15;i++){
        			_bmps[i].x = stage.stageWidth / 2 - _w / 2 + _w / 4 * (f[i] % 4);
        			_bmps[i].y = stage.stageHeight / 2 - _h / 2 + _h / 4 * uint(f[i] / 4);
        		}
        }
        
        private var _gct : Number = 0;
        private var _cur : Number; // 現在の評価値
        private var _space : uint; // 空きマスのインデックス
        
        private function onEnterFrame(e : Event) : void
        {
        		for(var i : uint = 0;i < 200;i++){
        			step();
        		}
        		
        		_tf.text = "";
        		tr(_f);
        		tr(_cur);
   			tr("step : " + _gct);
        		if(_cur == 0){
        			removeEventListener(Event.ENTER_FRAME, onEnterFrame);
        		}
        		paint(_f);
        }
        
        // MCMCの1ステップ
        private function step() : Boolean
        {
    			var ind : uint = MOV[_space][int(Math.random() * MOV[_space].length)];
        		_f[_space] = _f[ind];
        		_f[ind] = 15;
        		var v : Number = calcVal(_f);
        		if(Math.random() < Math.exp((_cur - v) * 1.2)){
        			_space = ind;
        			_cur = v;
	        		_gct++;
        			return true;
        		}else{
        			_f[ind] = _f[_space];
        			_f[_space] = 15;
        			return false;
        		}
        }
        
        // 評価値を計算
        private static function calcVal(f : Vector.<uint>) : Number
        {
        		var ret : Number = 0;
        		for(var i : uint = 0;i < 16;i++){
        			var y : uint = i / 4;
        			var x : uint = i % 4;
        			var fy : uint = f[i] / 4;
        			var fx : uint = f[i] % 4;
        			ret += Math.abs(fx - x) + Math.abs(fy - y);
        		}
        		return ret;
        }
        
        private function tr(...o : Array) : void
        {
            _tf.appendText(o + "\n");
        }
    }
}