Genetic algorithm:Solution of P&D
Genetic Programming
1:init the DNA
2:clone the current DNA
3:mutate the clone
4:find how many combo
5: if the new DNA make more combo than the previous did, overwrite the current DNA with the new DNA
6:goto 2
/**
* Copyright CZQ ( http://wonderfl.net/user/CZQ )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/16dV
*/
package
{
import com.bit101.components.Label;
import com.bit101.components.NumericStepper;
import com.bit101.components.PushButton;
import com.bit101.components.Text;
import flash.display.Sprite;
import flash.events.Event;
import flash.events.MouseEvent;
import flash.geom.Point;
//import genetic.DNA;
import net.hires.debug.Stats;
/**
*
* @author CZQ
* http://weibo.com/chzuqi
*
*
*/
[SWF(width='425', height='425',frameRate=24, backgroundColor='0xFFFFFF')]
public class PADCounter extends Sprite
{
public static var maxLength:int = 10;
private var ballMap:Array =
[
0,0,1,1,2,0,
3,3,2,2,5,4,
4,2,1,2,1,3,
3,4,1,5,5,4,
2,3,3,2,2,1,
];
private var bestDna:DNA;
private var bestCombo:int = 0;
private var count:int = 0;
private var txtCount:Label;
private var txtBestCombo:Label;
private var txtBestSolution:Label;
private var txtDna:Text;
private var numMutateRate:NumericStepper;
private var numSpeed:NumericStepper;
private var numStep:NumericStepper;
private var MutateRate:Number = 0.05;
private var speed:int = 100;
private var SameSolutionRate:Number = 0.1;
public function PADCounter()
{
txtCount = new Label(this, 0, 0);
txtBestCombo = new Label(this, 90, 0);
txtBestSolution = new Label(this, 150, 0);
txtDna = new Text(this,0,20,JSON.stringify(ballMap));
txtDna.setSize(300,20);
var btnChangeMap:PushButton = new PushButton(this, 310, 20, "Change", onChangeArray);
new Label(this, 0, 200, 'MutateRate');
numMutateRate = new NumericStepper(this, 0, 220, onChangeMutateRate);
numMutateRate.maximum = 1;
numMutateRate.minimum = 0;
numMutateRate.step = 0.1;
numMutateRate.value = MutateRate;
new Label(this, 120, 200, "Speed");
numSpeed = new NumericStepper(this, 120, 220, onChangeSpeed);
numSpeed.value = speed;
numSpeed.maximum = 5003;
numSpeed.minimum = 100;
numSpeed.step = 100;
new Label(this, 240, 200, "Step");
numStep = new NumericStepper(this, 240, 220, onChangeStep);
numStep.value = maxLength;
numStep.maximum = 30;
numStep.minimum = 2;
numStep.step = 1;
draw(ballMap, 5, 50, 25);
addEventListener(Event.ENTER_FRAME, onEnterFrame);
var s:Stats = new Stats();
s.y = 300;
addChild(s);
}
private function onChangeStep(e:Event):void
{
maxLength = numStep.value;
bestDna = null;
bestCombo = 0;
count = 0;
}
private function onChangeMutateRate(e:Event):void
{
MutateRate = numMutateRate.value;
}
private function onChangeSpeed(e:Event):void
{
speed = numSpeed.value;
}
private function onChangeArray(e:MouseEvent):void
{
var mapS:String = txtDna.text;
var map:Array = [];
try{
map = JSON.parse(mapS) as Array;
}catch(e:*){
}
if (map.length == PadUtil.COL * PadUtil.ROW){
ballMap = map;
bestDna = null;
bestCombo = 0;
count = 0;
}
}
private function onEnterFrame(e:Event = null):void
{
for (var i:int = 0; i < speed; i++){
countIt();
}
}
private function countIt():void
{
if (!bestDna){
bestDna = new DNA();
GeneticUtil.initDna(bestDna, maxLength);
}
var newDna:DNA;
if (Math.random() > MutateRate){
//copy from best
newDna = GeneticUtil.mutate(bestDna);
}else{
//Big Mutate!
newDna = new DNA();
GeneticUtil.initDna(newDna, maxLength);
}
var newMap:Array = GeneticUtil.useDna(ballMap,newDna)
var newCombo:int = PadUtil.countFunc(newMap);
if (newCombo > bestCombo || (newCombo == bestCombo && Math.random() < SameSolutionRate)){
graphics.clear();
draw(ballMap, 5, 50, 25);
draw(newMap, 200, 50, 25);
drawDNA(newDna, 200, 50, 25);
newDna.dump();
bestDna = newDna;
bestCombo = newCombo;
txtBestCombo.text = "Max Combo" + bestCombo.toString();
txtBestSolution.text = bestDna.dump();
}
count += 1;
txtCount.text = "Mutations:" + count.toString();
}
public function draw(map:Array, dx:Number = 50, dy:Number = 50, size:Number = 50):void
{
//draw board
graphics.lineStyle(0);
for (var i:int = 0; i <= PadUtil.COL; i++){
graphics.moveTo(dx + i * size, dy/* dy */ + 0 * size);
graphics.lineTo(dx + i * size, dy/* dy */ + PadUtil.ROW * size);
}
for (var j:int = 0; j <= PadUtil.ROW; j++){
graphics.moveTo(dx + 0 * size, dy/* dy */ + j * size);
graphics.lineTo(dx + PadUtil.COL * size, dy/* dy */ + j * size);
}
for (i = 0; i < map.length; i++){
var p:Point = GeneticUtil.indexToPoint(i);
switch (map[i]){
case 0://R=>0
graphics.beginFill(0xfe6f39);
break;
case 1://G->1
graphics.beginFill(0x63e874);
break;
case 2://B
graphics.beginFill(0x227ef2);
break;
case 3://L
graphics.beginFill(0xfefe9b);
break;
case 4://D
graphics.beginFill(0x9a67a9);
break;
case 5://H
graphics.beginFill(0xea6dbe);
break;
break;
}
if (map[i] >= 0)
graphics.drawCircle( dx + size / 2 + p.x * size, dy + size / 2 + p.y * size, size / 3);
}
graphics.endFill();
}
public function drawDNA(dna:DNA, dx:Number = 50, dy:Number = 50, size:Number = 50):void
{
var p:Point = dna.dna[0];
graphics.moveTo(dx + size / 2 + p.x * size, dy + size / 2 + p.y * size);
graphics.lineStyle(1);
graphics.beginFill(0xFFFFFF);
graphics.drawCircle(dx + size / 2 + p.x * size, dy + size / 2 + p.y * size, size / 5);
graphics.endFill();
for (var i:int = 1; i < dna.dna.length; i++){
p = dna.dna[i];
graphics.lineTo(dx + size / 2 + p.x * size, dy + size / 2 + p.y * size);
}
graphics.beginFill(0x000000);
graphics.drawCircle(dx + size / 2 + p.x * size, dy + size / 2 + p.y * size, size / 5);
graphics.endFill();
}
}
}
//package
//{
import flash.geom.Point;
//import genetic.DNA;
class GeneticUtil
{
/**
* init the dna
* @param dna
* @param length
*
*/
public static function initDna(dna:DNA, length:int):void
{
dna.dna = new Vector.<Point>;
dna.dna.push(new Point(rnd(PadUtil.COL), rnd(PadUtil.ROW)));
var oe:int = -1;
for (var i:int = 1; i < length; i++)
{
oe *= -1;
if (oe > 0){
//change Col
dna.dna.push(new Point(rnd(PadUtil.COL), dna.dna[i-1].y));
}else{
//change Row
dna.dna.push(new Point(dna.dna[i-1].x, rnd(PadUtil.ROW)));
}
}
}
/**
* Evolution
* @param dnaSource
* @param strength
* @return
*
*/
public static function mutate(dnaSource:DNA):DNA {
var newDna:DNA = dnaSource.clone();
var dnaIndex:int = Math.random() * newDna.dna.length;
var now:Point = newDna.dna[dnaIndex];
var prev:Point = now.clone();
var next:Point = now.clone();
if (dnaIndex != 0){
prev = newDna.dna[dnaIndex - 1];
}
if (dnaIndex != newDna.dna.length - 1) {
next = newDna.dna[dnaIndex + 1];
}
if ((dnaIndex == 0 || oneOrNegativeOne() > 0) && dnaIndex != newDna.dna.length - 1 ){
//change next
if (prev.y == now.y && next.x == now.x){
//change now .x && next.x
// now.x = int(clamp(now.x + oneOrNegativeOne() * Math.random() * strength * 2, 0, PadUtil.COL));
now.x = rnd(PadUtil.COL);
next.x = now.x;
}else{
//change now.y && next.y
// now.y = int(clamp(now.y + oneOrNegativeOne() * Math.random() * strength * 2, 0, PadUtil.ROW));
now.y = rnd(PadUtil.ROW);
next.y = now.y;
}
}else{
//change prev
if (prev.y == now.y && next.x == now.x){
//change now.y && prev.y
// now.y = int(clamp(now.y + oneOrNegativeOne() * Math.random() * strength * 2, 0, PadUtil.ROW));
now.y = rnd(PadUtil.ROW);
prev.y = now.y;
}else{
//change now .x && prev.x
// now.x = int(clamp(now.x + oneOrNegativeOne() * Math.random() * strength * 2, 0, PadUtil.COL));
now.x = rnd(PadUtil.COL);
prev.x = now.x;
}
}
//already wrote it to dna~
return newDna
}
/**
* Use Dna for map
* @param map
* @param dna
* @return
*
*/
public static function useDna(mapSoure:Array, dna:DNA):Array
{
var j:int;
var d:int;
var mapCopy:Array = mapSoure.concat();
var nowPoint:Point = dna.dna[0];
var startColor:int = mapCopy[pointToIndex(nowPoint)];
for (var i:int = 1; i < dna.dna.length; i++)
{
var toPoint:Point = dna.dna[i];
if (nowPoint.y == toPoint.y && nowPoint.x == toPoint.x){
//is already there, do nothing
//special flag,stop here
return mapCopy;
}else if (nowPoint.y == toPoint.y){
//move nowPoint to toPoint.
d = oneOrNegativeOneForNum(toPoint.x - nowPoint.x);
//move right if d >0
for (j = nowPoint.x; j != toPoint.x; j+= d){
mapCopy[xyToIndex(j,nowPoint.y)] = mapCopy[xyToIndex(j + d,nowPoint.y)]
}
//set topoint to c
mapCopy[pointToIndex(toPoint)] = startColor;
}else if (nowPoint.x == toPoint.x){
d = oneOrNegativeOneForNum(toPoint.y - nowPoint.y);
for (j = nowPoint.y; j != toPoint.y; j+= d){
mapCopy[xyToIndex(nowPoint.x, j)] = mapCopy[xyToIndex(nowPoint.x, j + d)]
}
//set topoint to c
mapCopy[pointToIndex(toPoint)] = startColor;
}else{
//wrong move,no solution
return mapSoure.concat();
}
nowPoint = toPoint.clone();
}
return mapCopy;
}
public static function oneOrNegativeOne():int
{
return (Math.random() > 0.5)?1:-1;
}
public static function oneOrNegativeOneForNum(v:Number):int
{
if (v > 0) return 1;
return -1;
}
public static function pointToIndex(p:Point):int
{
return (p.x + p.y * PadUtil.COL);
}
public static function xyToIndex(x:int, y:int):int
{
return (x + y * PadUtil.COL);
}
public static function indexToPoint(index:int):Point
{
return new Point(index % PadUtil.COL, int(index / PadUtil.COL));
}
public static function rnd(n:Number):int
{
return Math.floor(n * Math.random());
}
public static function clamp(val:Number, minval:Number, maxval:Number):Number
{
if(val<minval) return minval;
if(val>maxval) return maxval;
return val;
}
}
//}
//package
//{
class PadUtil
{
public static const ROW:int = 5;
public static const COL:int = 6;
/**
* Count how many combo
* @param map
* @return
*
*/
public static function countFunc(map:Array):int{
var nextMap:Array = map.concat();
var mapCount:int = getThisMapCount(nextMap);
if (mapCount == 0){
//nothing to do
return 0;
}else{
dropMap(nextMap);
return mapCount + countFunc(nextMap);
}
}
public static function getThisMapCount(map:Array):int
{
var count:int = 0;
var combos:Array = [];
//in col,right 2
for (var i:int = 0; i < COL * ROW; i++)
{
if ((i % COL) > (COL - 3)) continue;
if (map[i] == -1) continue;
if (map[i] == map[i+1] && map[i] == map[i+2]){
count += greatePush(combos, i, i+1, i+2);
}
}
for (i = 0; i < COL * (ROW - 2); i++)
{
if (map[i] == -1) continue;
if (map[i] == map[i+COL] && map[i] == map[i+2 * COL]){
count += greatePush(combos, i, i+COL, i+2 * COL);
}
}
for (i = 0; i < combos.length; i++)
{
map[combos[i]] = -1;
}
return count;
}
private static function greatePush(combos:Array, index1:int, index2:int, index3:int):int
{
//push 3 to array
var combo:int = 1;
if (combos.indexOf(index1) == -1)
combos.push(index1);
else
combo = 0;
if (combos.indexOf(index2) == -1)
combos.push(index2);
else
combo = 0;
if (combos.indexOf(index3) == -1)
combos.push(index3);
else
combo = 0;
return combo;
}
public static function dropMap(map:Array):void
{
//冒泡Row次
for (var j:int = 0; j < ROW; j++){
//let all -1 up~
for (var i:int = COL; i < COL*ROW; i++){
if (map[i] == -1 && map[i - COL] != -1){
//up~up
map[i] = map[i - COL];
map[i - COL] = -1;
}
}
}
}
}
//}
//package genetic
//{
import flash.geom.Point;
/**
* Gene Piece
* Use Point
*
* @author CZQ
*
*/
class DNA
{
public var dna:Vector.<Point>;
public function DNA()
{
}
public function clone():DNA
{
var newdna:DNA = new DNA();
newdna.dna = new Vector.<Point>;
for (var i:int = 0; i < dna.length; i++){
newdna.dna.push(dna[i].clone());
}
return newdna;
}
public function dump():String
{
var arr:Array = [];
for (var i:int = 0; i < dna.length; i++){
arr.push("(" + dna[i].x + "," + dna[i].y + ")");
}
return arr.join(',');
}
}
//}