Order to chaos to order with TSP 3D
TSP 3D
Original work by itatsu
Feb.4.2009
====================================================
Modified Lord_mungo
Feb 9.2009
My first flash code -
Nodes contrained on a sphere.
Each node is repelled by every other node by
inversely proportional to the square of the distance.
Each node has momentum, and a damping factor slows allows
the system to settle down.
Runs algorithm to find shorter route - thanks itatsu
Press 'space' to double the nodes.
// forked from itatsu's TSP 3D
// TSP 3D
// Original work by itatsu
// Feb.4.2009
// ====================================================
// Modified Lord_mungo
// Feb 9.2009
// My first flash code -
//
// Nodes contrained on a sphere.
// Each node is repelled by every other node by
// inversely proportional to the square of the distance.
// Each node has momentum, and a damping factor slows allows
// the system to settle down.
//
// Runs algorithm to find shorter route - thanks itatsu
//
//
// Press 'space' to double the nodes.
package {
import flash.display.*;
import flash.events.*;
import flash.utils.getTimer;
[SWF(width="465", height="465", backgroundColor="30", frameRate="60")]
public class MyBots extends Sprite {
public function MyBots() {
global = this;
global.x = 465 / 2;
global.y = 465 / 2;
stage.quality = StageQuality.HIGH;
Initialize();
global.addEventListener(Event.ENTER_FRAME, Update);
stage.addEventListener(KeyboardEvent.KEY_DOWN, KeyDown);
}
}
}
import flash.display.*;
import flash.events.*;
import flash.geom.*;
import flash.text.*;
import flash.filters.*;
// Global
var global:Sprite;
//**************** Adjust these values ******************
// City amount
const amInit:int = 60;
// City amount
const am_max:int = amInit;
// Cities that can move
const freeToMoveInit:int = amInit;
// Cities that can move at end
const freeToMoveMax:int = 99999;
// Delay between node adding;
const freeToMoveRate:Number = 6;
// Damping
const damping:Number = 0.16;
// Simulation speed
const speed:Number = 1000;
// Delay before net optimisation starts
const optimiseDelay:int = 0;
//*******************************************************
const radius:Number = 150;
// Rotation
var rX:Number = 0;
var rY:Number = -12 * Math.PI / 180;
var rZ:Number = -12 * Math.PI/180;
var changeRotation:Number = 0;
var mat:Matrix3D = new Matrix3D();
var tumbleMat:Matrix3D = new Matrix3D();
var tweakNode :Number = 0;
var tweakNodeTime : Number = 0;
var highlightNode :int;
// Present route
var route:Vector.<Vector3D> = new Vector.<Vector3D>();
var motion:Vector.<Matrix3D> = new Vector.<Matrix3D>();
var motionV:Vector.<Vector3D> = new Vector.<Vector3D>();
// City amount
var am:int;
var freeTimer:int =0;
var mode:int;
var freeToMove:int;
var optimise:int =0;
var lasttick:int=0;
var interval:int;
var framesPerSecond:Number;
var calc:int=0;
var calcPoints:int=0;
var optimisePoints:int=1;
// Textfield
var tField:TextField = new TextField;
var tField2:TextField= new TextField;
var tField3:TextField= new TextField;
var constrain1s:int=-1;
var constrain2s:int=-1;
var constrain1e:int=-1;
var constrain2e:int=-1;
var constrain3s:int=-1;
var constrain3e:int=-1;
function Initialize():void {
tumbleMat=new Matrix3D();
tumbleMat.appendRotation(0, Vector3D.Y_AXIS);
tumbleMat.appendRotation(360/amInit, Vector3D.Z_AXIS);
am = amInit;
freeToMove=freeToMoveInit;
route = new Vector.<Vector3D>();
motionV = new Vector.<Vector3D>();
// Generate cities
var cit:Vector3D = new Vector3D(radius,0,0);
for (var i:int = 0; i < am; i++) {
cit=tumbleMat.transformVector(cit)
route.push(new Vector3D(cit.x, cit.y, cit.z));
motion.push(new Matrix3D());
motionV.push(new Vector3D(0,0,0.0001));
}
route[0].z=10;
var tFormat:TextFormat = new TextFormat;
tFormat.font = "Arial";
tFormat.bold = false;
tFormat.color = 0xffffff;
tFormat.size = 25;
tFormat.align = TextFormatAlign.LEFT;
tField.defaultTextFormat = tFormat;
tField.selectable = false;
tField.x = -220;
tField.y = -200;
tField.width = 460;
tField2.defaultTextFormat = tFormat;
tField2.selectable = false;
tField2.x = -220;
tField2.y = -230;
tField2.width = 250;
tField3.defaultTextFormat = tFormat;
tField3.selectable = false;
tField3.x = 90;
tField3.y = -230;
tField3.width = 200;
// global.filters = [new GlowFilter(0xffffff, 0.7, 6, 6)];
}
function Update(evt:Event):void {
interval=flash.utils.getTimer()-lasttick;
framesPerSecond =1000/interval;
lasttick=flash.utils.getTimer();
global.graphics.clear();
while (global.numChildren > 0) {
global.removeChildAt(0);
}
DrawRoute();
global.addChild(tField);
tField.text = String(Length(route));
global.addChild(tField2);
tField2.text = String(Math.floor(framesPerSecond))+"FPS - "+String(calcPoints)+" - "+String(optimisePoints);
// tField2.text = "Hello";
global.addChild(tField3);
tField3.text =String(freeToMove)+"/"+String(am_max);;
// Rotate
mat.appendRotation(rX, Vector3D.X_AXIS);
mat.appendRotation(rY, Vector3D.Y_AXIS);
mat.appendRotation(changeRotation/2000*rZ, Vector3D.Z_AXIS);
if (++changeRotation>2000)
changeRotation=0;
if (++freeTimer>=freeToMoveRate)
{
if ((freeToMove<freeToMoveMax)&&(freeToMove<am))
freeToMove++;
else
optimise++;
freeTimer=0;
}
if (framesPerSecond>40)
{
if (calcPoints<am)
calcPoints++;
else if (optimisePoints<10000)
optimisePoints=Math.floor(optimisePoints*1.1+1);
}
if (framesPerSecond<30)
{
if (optimisePoints>10)
optimisePoints=Math.floor(optimisePoints*0.9);
else if (calcPoints>1)
calcPoints--;
}
Repel();
if (optimise>=optimiseDelay)
SeekBetterRoute();
}
function SeekBetterRoute():void{
var s:int=0;
var e:int=0;
while(s>=e)
{
s=Math.floor(Math.random() * am);
if (Math.random()>0.9)
e=nodeAfter(s);
else if (Math.random()>0.9)
e=nodeAfter(nodeAfter(s));
else
e=Math.floor(Math.random() * am);
}
var r2:Vector.<Vector3D> = RouteClone(route);
var j:int;
for (j = s; j <= e; j++) // swap chunk from s-e;
r2[s + e - j] = new Vector3D(route[j].x, route[j].y, route[j].z);
if (Length(r2)+0.001 < Length(route))
{
route=RouteClone(r2);
r2 = RouteClone(motionV);
for (j = s; j <= e; j++) // swap motion vectors too
r2[s + e - j] = new Vector3D(motionV[j].x, motionV[j].y, motionV[j].z);
motionV=RouteClone(r2);
}
s=Math.floor(Math.random() * am);
e=Math.floor(Math.random() * am);
var r3:Vector.<Vector3D> = new Vector.<Vector3D>();
var n2:int;
for (n2 = 0; (n2 < am); n2++) // re-route single node;
{
if (n2!=s)
r3.push(new Vector3D(route[n2].x, route[n2].y, route[n2].z));
if (n2==e)
r3.push(new Vector3D(route[s].x, route[s].y, route[s].z));
}
if (Length(r3)+0.001 < Length(route))
{
route=RouteClone(r3);
r3= new Vector.<Vector3D>();
for (n2 = 0; (n2 < am); n2++) // re-route single node;
{
if (n2!=s)
r3.push(new Vector3D(motionV[n2].x, motionV[n2].y, motionV[n2].z));
if (n2==e)
r3.push(new Vector3D(motionV[s].x, motionV[s].y, motionV[s].z));
}
motionV=RouteClone(r3);
}
}
function Repel():void
{
if (interval>100)
interval=100;
var deltaT:Number=interval/1000;
var deltaTM:Number=deltaT*am/calcPoints;
for (var k:int = 0; (k < calcPoints); k++)
{
calc=(calc+1)%am
var totalForce:Vector3D=new Vector3D();
var twist:Vector3D=new Vector3D();
for (var n:int = 0; (n < am); n++)
{
if (calc!=n)
{
var f:Vector3D = new Vector3D();
f=route[calc].subtract(route[n])
var d:Number=f.length;
f.normalize()
f.scaleBy(-1/(d*d*am));
totalForce=totalForce.add(f);
}
}
twist=totalForce.crossProduct(route[calc]);
twist.scaleBy(deltaTM*speed/Math.sqrt(am));
motionV[calc].scaleBy(1-deltaTM*damping);
motionV[calc]=motionV[calc].add(twist);
}
for (var j:int = 0; (j < freeToMove); j++)
{
motion[j]=new Matrix3D();
motion[j].appendRotation(1*deltaT*motionV[j].length,motionV[j]);
route[j]=motion[j].transformVector(route[j]);
route[j].normalize();
route[j].scaleBy(radius);
}
}
function ConstrainLine(c1:int,c1e:int,c2:int,c2e:int,c3:int,c3e:int):void
{
constrain1s=c1;
constrain1e=c1e;
constrain2s=c2;
constrain2e=c2e;
constrain3s=c3;
constrain3e=c3e;
}
function Length(r:Vector.<Vector3D>):Number {
var s:Number = 0;
for (var i:int = 0; i < am; i++)
{
var ii:int = (i + 1) % am;
var side:Number = Math.sqrt((r[i].x - r[ii].x) * (r[i].x - r[ii].x)
+ (r[i].y - r[ii].y) * (r[i].y - r[ii].y)
+ (r[i].z - r[ii].z) * (r[i].z - r[ii].z));
var l:Number = 2*Math.asin(side/1.999/radius); // arc length around sphere
s+=l; // tried s+=Vector3D.angleBetween(r[i],r[ii])*radius; but got occassional unexpected NaN result
}
return s;
}
function RouteClone(r:Vector.<Vector3D>):Vector.<Vector3D> {
var r2:Vector.<Vector3D> = new Vector.<Vector3D>();
for (var i:int = 0; i < am; i++) {
r2.push(new Vector3D(r[i].x, r[i].y, r[i].z));
}
return r2;
}
function DoubleNodes():void {
var r2:Vector.<Vector3D> = new Vector.<Vector3D>();
var m2:Vector.<Vector3D> = new Vector.<Vector3D>();
for (var i:int = 0; i < am; i++) {
r2.push(new Vector3D(route[i].x, route[i].y, route[i].z));
var midpoint:Vector3D=new Vector3D();
midpoint=route[i].add(route[(i+1)%am]);
midpoint.normalize();
midpoint.scaleBy(radius);
r2.push(midpoint);
m2.push(new Vector3D(motionV[i].x,motionV[i].y,motionV[i].z))
midpoint=motionV[i].add(motionV[(i+1)%am])
midpoint.scaleBy(0.5);
m2.push(new Vector3D(motionV[i].x,motionV[i].y,motionV[i].z))
}
am=am*2;
freeToMove=freeToMove*2;
route=RouteClone(r2);
motionV=RouteClone(m2);
}
function AddNode():void {
var r2:Vector.<Vector3D> = new Vector.<Vector3D>();
var m2:Vector.<Vector3D> = new Vector.<Vector3D>();
for (var i:int = 0; i < am; i++) {
r2.push(new Vector3D(route[i].x, route[i].y, route[i].z));
m2.push(new Vector3D(motionV[i].x,motionV[i].y,motionV[i].z))
if (i==0)
{
var midpoint:Vector3D=new Vector3D();
midpoint=route[i].add(route[(i+1)%am]);
midpoint.normalize();
midpoint.scaleBy(radius);
r2.push(midpoint);
midpoint=motionV[i].add(motionV[(i+1)%am])
midpoint.scaleBy(0.5);
m2.push(new Vector3D(motionV[i].x,motionV[i].y,motionV[i].z))
}
}
am++;
freeToMove++;
route=RouteClone(r2);
motionV=RouteClone(m2);
}
function nodeAfter(node:int):int
{
return ((node+1)%am);
}
function nodeBefore(node:int):int
{
return ((node+am-1)%am);
}
function DrawRoute():void {
var st:Vector3D = new Vector3D();
var ed:Vector3D = new Vector3D();
for (var i:int = 0; i < am; i++) {
var ii:int = (i + 1) % am;
st = mat.transformVector(route[i]);
ed = mat.transformVector(route[nodeAfter(i)]);
var depthcue:Number=100/(400-st.z-ed.z); // largest =1060 smallest 460
global.graphics.lineStyle(2, 0x010101*Math.floor(depthcue*254));
global.graphics.moveTo(st.x, st.y);
global.graphics.lineTo(ed.x, ed.y);
if (am<200)
global.graphics.drawCircle(st.x, st.y, 2200 / (380 - st.z));
if(i==highlightNode)
global.graphics.drawCircle(st.x, st.y, 3300 / (380 - st.z));
}
if (constrain1s>=0)
{
st = mat.transformVector(route[constrain1s]);
ed = mat.transformVector(route[constrain1e]);
global.graphics.lineStyle(2, 0xffff00);
global.graphics.moveTo(st.x, st.y);
global.graphics.lineTo(ed.x, ed.y);
}
if (constrain2s>=0)
{
st = mat.transformVector(route[constrain2s]);
ed = mat.transformVector(route[constrain2e]);
global.graphics.lineStyle(2, 0xffff00);
global.graphics.moveTo(st.x, st.y);
global.graphics.lineTo(ed.x, ed.y);
}
if (constrain3s>=0)
{
st = mat.transformVector(route[constrain3s]);
ed = mat.transformVector(route[constrain3e]);
global.graphics.lineStyle(2, 0xff0000);
global.graphics.moveTo(st.x, st.y);
global.graphics.lineTo(ed.x, ed.y);
}
}
function KeyDown(evt:KeyboardEvent):void {
//
if (evt.keyCode==32)
DoubleNodes();// AddCity();
else if (evt.keyCode==27)
Initialize();
else
AddNode();
}