forked from: MCMC on 15puzzle
/**
* Copyright uwi ( http://wonderfl.net/user/uwi )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/yb9J
*/
// forked from uwi's MCMC on 15puzzle
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;
private var _states : Object;
private var _opes : Array;
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;
_gct2 = 0;
_cur = calcVal(_f);
_states = {};
_opes = [];
}
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 _gct2 : Number = 0;
private var _cur : Number; // 現在の評価値
private var _space : uint; // 空きマスのインデックス
private function onEnterFrame(e : Event) : void
{
for(var i : uint = 0;i < 2000;i++){
step();
}
_gct2 += 2000;
_tf.text = "";
tr(_f);
// tr(_cur);
tr("step : " + _gct2);
tr("move : " + _gct);
var u : uint = 0;
for each(var k : String in _states)u++;
tr("unique : " + u);
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;
var fj : String = _f.join(',');
if(_states[fj]){
for(var k : uint = _states[fj] + 1;k < _opes.length;k++){
_states[_opes[k]] = null;
}
_opes.splice(_states[fj] + 1, _opes.length - (_states[fj] + 1) + 1);
}else{
_states[fj] = _opes.length;
_opes.push(fj);
}
_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");
}
}
}