Browse the notebook

Category: arrays

2D Map Avoid

[SWF(width=401,height=401,background=0xEFEFEF)]

var w:Number = stage.stageWidth-1;
var h:Number = stage.stageHeight-1;
var tileSize:Number = 20;
var halfTileSize:Number = 20;
var hTiles:Number = w / tileSize;
var vTiles:Number = h / tileSize;
var world:Shape = Shape(addChild(new Shape()));
var map:Array=[];
populateMap();
var gridColor:uint = 0xCCCCCC;
grid(tileSize,  gridColor);

vTiles -= 1;
var movers:Array = [];
for (var i:int = 0; i<100; i++){
	movers.push(makeMover(i % hTiles, int( i / hTiles),0x000000))
	movers.push(makeMover(i % hTiles, vTiles - int( i / hTiles),0xFF0000))
}
var moverNum:int = movers.length;
hTiles -= 1;

addEventListener(Event.ENTER_FRAME, onLoop);
function onLoop(evt:Event):void {
	world.graphics.clear();
    for (var i:int = 0; i<moverNum; i++){
	   movers[i]();
     }
}
function populateMap():void{
	for (var i:int = 0; i<vTiles; i++){
		map[i] = [];
		for (var j:int = 0; j<hTiles; j++){
		    map[i][j] = 0;
		}
	}
}
function grid(size:Number=30, lineColor:uint=0xFFFF00, lineAlpha:Number=1):void {
    with(graphics){
		lineStyle(0, lineColor, lineAlpha);
		drawRect(0,0,w,h);
		for (var i:Number = size; i<w; i+=size) {
			moveTo(i, 0);
			lineTo(i, w);
		}
		for (i = size; i<h; i+=size) {
			moveTo(0, i);
			lineTo(h, i);
		}
	}
}
function makeMover(x:Number, y:Number, col:uint):Function{
	var xp:Number = x;
	var yp:Number = y;
	var prevX:Number = x;
	var prevY:Number = y;
	map[yp][xp] = 1;
	var dx:Number = xp;
	var dy:Number = yp;
	var counter:int = 0;
	return function():void{
		if (counter > 20){
			if (int(Math.random()*30) == 1){
				xp += int(Math.random()*2) - 1 | 1;
				xp = xp < 0 ? 0 : xp;
				xp = xp > hTiles ? hTiles : xp;
				if (map[yp][xp] == 1){
					 xp = prevX;
				}else{
					map[prevY][prevX] = 0;
					map[yp][xp] = 1;
					counter = 0;
				}
				prevX = xp;
			}else
			if (int(Math.random()*30) == 1){
				yp += int(Math.random()*2) - 1 | 1;
				yp = yp < 0 ? 0 : yp;
				yp = yp > vTiles ? vTiles : yp;
				if (map[yp][xp] == 1){
					 yp = prevY;
				}else{
					map[prevY][prevX] = 0;
					map[yp][xp] = 1;
					counter = 0;
				}
				prevY = yp;
			}
		}
		counter++;
		dx += (xp - dx) * 0.5;
		dy += (yp - dy) * 0.5;
		with(world.graphics){
			lineStyle(0, gridColor,1, true)
			beginFill(col);
			drawRect(dx * tileSize, dy * tileSize, tileSize, tileSize);
		}
	}
}

This (somewhat long) snippet moves boxes around on a grid – the boxes avoid one another by reading values in a 2D array. This technique can also be used for collision detection in tile-based games.


Have a look at the swf here…

Read snippet: 2D Map Avoid

x and y Coordinates in 1D Array / Vector

var canvas:BitmapData=new BitmapData(400,400,false,0x000000);
addChild(new Bitmap(canvas));
var pix:Vector.<uint>=canvas.getVector(canvas.rect);

canvas.lock();
for (var i:int = 0; i<300; i++) {
	var xp:int=50+i;
	var yp:int=50+i/2;
	// target x and y coords in 1D array
	pix[xp+yp*400]=0xFFFFFF;
}
canvas.setVector(canvas.rect, pix);
canvas.unlock();

This snippet shows how to target x and y coordinates in a 1D Array / Vector. This can be useful sometimes when working with setVector().

This is sort of like re-inventing setPixel()…. and for that reason is kind of pointless – that said, it’s interesting to know. I first learned about this technique from using processing.

Read snippet: x and y Coordinates in 1D Array / Vector

Array.push() Vector.push() Optimization

var tVerts:Vector.<Number> = new Vector.<Number>();
var inc:int = 0;
var t:Number, i:Number, j:Number, k:Number;
 
 // fast way
t = getTimer();
for (i= -2; i<2; i+=.03){
	for (j = -2; j<2; j+=.03){
		for (k = -2; k<2; k+=.03){
			tVerts[inc] = i;
			inc++;
			tVerts[inc] = j;
			inc++;
			tVerts[inc]= k;
			inc++;
		}
	}
}
trace(getTimer() - t);

tVerts  = new Vector.<Number>();

// slow way
t = getTimer();
for (i= -2; i<2; i+=.03){
	for (j = -2; j<2; j+=.03){
		for (k = -2; k<2; k+=.03){

			tVerts.push(i, j, k);
		//	tVerts.push(j);
		//	tVerts.push(k);
		}
	}
}
trace(getTimer() - t);

Today I needed to populate a Vector in the above manner… populating the vector using push() was quite slow in this case because (among other reasons) push() is a method call. I was curious how much faster populating the Vector without push would be… so I wrote this snippet – in this case it was significantly faster – took less than a third of the time. You can run this snippet to see what kind of results you get.

It’s important to note that this nested for loop could be optimized further but I wanted to focus on the push() optimization alone.

Warning

The most HORRIBLE thing about testing the speed of ActionScript code is that you CANNOT rely on the debug player to test optimizations. Always use the release version of the flash player. The debug player will give unusual (usually slower) results…

Read snippet: Array.push() Vector.push() Optimization

Hill Climbing

var target:Array = ("actionsnippet").split("");
var leng:int=target.length;
var iterations:int = 0;

var alphabet:Array = ("abcdefghijklmnopqrstuvwxyz").split("");
var search:Array = randomString();
var indices:Array = new Array();
for (var i:int = 0; i<leng; i++) indices.push(i);

addEventListener(Event.ENTER_FRAME, onLoop);
function onLoop(evt:Event):void {
	for (var i:int = 0; i<10; i++){
		if (indices.length > 0){
		   var ii:int = int(Math.random()*indices.length);
		   var index:int = indices[ii];
		 
		   search[index] = randomChar();
		   
		   if (search[index] == target[index]){
			   indices.splice(ii,1);   
		   }
		   trace(search);
		   iterations++;
		}else{
			trace("found after "+iterations+" iterations");
			removeEventListener(Event.ENTER_FRAME, onLoop);
			break;
		}
	}
}
function randomChar():String { return alphabet[int(Math.random()*alphabet.length)]; };
function randomString():Array {
	var str:Array = new Array();
	for (var i:int = 0; i<leng; i++) {
		str.push(randomChar());
	}
	return str;
}

A little random hill climbing…

Here are the last few iterations… lowest number of iterations I noticed was round 250…

....
j,c,t,i,o,n,s,n,i,p,p,e,t
y,c,t,i,o,n,s,n,i,p,p,e,t
s,c,t,i,o,n,s,n,i,p,p,e,t
w,c,t,i,o,n,s,n,i,p,p,e,t
e,c,t,i,o,n,s,n,i,p,p,e,t
j,c,t,i,o,n,s,n,i,p,p,e,t
z,c,t,i,o,n,s,n,i,p,p,e,t
l,c,t,i,o,n,s,n,i,p,p,e,t
f,c,t,i,o,n,s,n,i,p,p,e,t
a,c,t,i,o,n,s,n,i,p,p,e,t
found after 361 iterations

Read snippet: Hill Climbing

Vector.sortOn()

var a:Vector.<Sprite> = new Vector.<Sprite>();

trace("unsorted");
for (var i:int = 0; i<10; i++){
	var s:Sprite = new Sprite();
	s.x = int(Math.random()*100);
	a.push(s);
	trace(s.x);
}

quickSortOn(a, "x", 0, a.length-1);

trace("sorted");
for (i= 0; i<10; i++){
	trace(a[i].x);
}

// modified code from kirupa.com
// http://www.kirupa.com/developer/actionscript/quickSort.htm
function quickSortOn(a:Vector.<Sprite>, prop:String, left:int, right:int):void {
    var i:int = 0, j:int = 0, pivot:Sprite, tmp:Sprite;
	i=left;
	j=right;
	pivot = a[Math.round((left+right)*.5)];
	while (i<=j) {
		while (a[i][prop]<pivot[prop]) i++;
		while (a[j][prop]>pivot[prop]) j--;
		if (i<=j) {
			tmp=a[i];
			a[i]=a[j];
			i++;
			a[j]=tmp;
			j--;
		}
	}
	if (left<j)  quickSortOn(a, prop, left, j);
	if (i<right) quickSortOn(a, prop, i, right);
}
/* outputs something like:
unsorted
26
33
20
63
7
68
75
39
67
53
sorted
7
20
26
33
39
53
63
67
68
75
*/

This demo is my first quick stab at using at a sortOn() function for the Vector class. It sorts a Vector of Sprites by their x property.

Recently there were a few times when I was prototyping ideas and suddenly realized that I needed to change my Vector to an Array because I needed to use sortOn().(If you don’t already know, there is no built in sortOn() method for the Vector class). In the past I spent some time with sorting algorithms, bubble, insertion etc… so I knew I could pretty easily write my own sortOn(), but I also realized that a generic implementation wouldn’t be easy/possible without loosing the type of the Vector. What I mean is, if you have a Vector of Sprites, you need a sorting method that takes a Vector.< Sprite > type as an argument (as seen above), if you have a Vector of TextFields you need a Vector.< TextField > type as an argument. You could of course use a generic type, but this kind of defeats the purpose of using a vector in the first place…

I will likely post a revised version of this in the near future with a slightly improved implementation of QuickSort. I haven’t spent that much time with this, but If I recall correctly this is not the ideal implementation. I ported this code from a nice Kirupa tutorial and modified it to sort based on a property…

Read snippet: Vector.sortOn()

Fracture a Number

var target:Number = 1024;
var slices:Array = [target];
var leng:int = 11;

for (var i:int = 0; i<leng-1; i++){
	 var index:int = int(Math.random()*slices.length);
	 var val:Number = slices[index];
	 var rand:Number = Math.random() * val/2;
	 slices[index] = val - rand;
	 slices.push(rand);
}

trace(slices);

// test that they all add up
var sum:Number = 0;
for (i = 0; i<slices.length; i++){
	sum += slices[i];
}
trace("test that they all add up: ", sum);

The above snippet creates an array of a specified length whose elements all add up to the variable target. Here is some example output:


165.31133050055192,322.23456030456015,
257.47582363389245,26.9984893942173,1.96283924962002,
5.466277873168191,21.362282634705164,62.68168197512457,
76.63028224500404,36.27274381401516,12.558309228795265,35.04537914634583
test that they all add up: 1024

Read snippet: Fracture a Number

Random Walk to Target

var target:Number = 360;
var steps:Array = new Array();
for (var step:Number = 0; step < target; step += int(Math.random() * 36 + 36)){
	steps.push(Math.min(target,step));
}
steps.push(target);
trace(steps);
/* outputs something similar to:
0,46,99,144,189,259,330,360
*/

This is something I’ve had to do a few times recently…. it randomly steps a number toward a given target…

Read snippet: Random Walk to Target

Unique Array Comparison

function uniqueCompare(arr:Array, compare:Function):void {
	var leng:int = arr.length;
	for (var i:int = 0; i<leng; i++){
		for (var j:int = i + 1; j<leng; j++){
			compare(arr[i], arr[j]);
		}
	}
}

var numbers:Array = [1, 2, 3, 4, 5];

uniqueCompare(numbers, compareCallback);

function compareCallback(a:*, b:*):void {
	trace("compare " + a + " to " + b);
}

/*
outputs:
compare 1 to 2
compare 1 to 3
compare 1 to 4
compare 1 to 5
compare 2 to 3
compare 2 to 4
compare 2 to 5
compare 3 to 4
compare 3 to 5
compare 4 to 5
*/

This snippet shows a function called uniqueCompare() that compares all elements in an array to all other elements in an array without repeating a comparison.

Read snippet: Unique Array Comparison

Random Sort

function randomize(a:*, b:*):int{
       return Math.round(Math.random()*8) - 4;
}

var i:int;
var fruits:Array;

trace("Math.random()");
for (i = 0; i<4; i++){
  // reset fruits array:
  fruits = ["apple", "grape","pear","cherry"];
  fruits.sort(randomize);
  trace(fruits);
}


// seeds
var s1:Number= 0xFF00FF;
var s2:Number = 0xCCCCCC;
var s3:Number= 0xFF00F0;

function tRandomize(a:*, b:*):int{
       return Math.round(rand()*8) - 4;
}

trace("nTausworthe rand()");
for (i= 0; i<4; i++){
  fruits = ["apple", "grape","pear","cherry"];
  fruits.sort(tRandomize);
  trace(fruits);
}
// from www.ams.org/mcom/1996-65-213/S0025-5718-96-00696-5/S0025-5718-96-00696-5.pdf
function rand():Number {
	s1=((s1&4294967294)<<12)^(((s1<<13)^s1)>>19);
	s2=((s2&4294967288)<<4)^(((s2<<2)^s2)>>25);
	s3=((s3&4294967280)<<17)^(((s3<<3)^s3)>>11);
	var r:Number = (s1^s2^s3) * 2.3283064365e-10;
	r = (r<0) ? r+=1 : r;
	return r;
}

/*
outputs:
Math.random()
grape,apple,pear,cherry
pear,cherry,apple,grape
grape,apple,pear,cherry
grape,apple,cherry,pear

Tausworthe rand()
apple,grape,pear,cherry
cherry,grape,pear,apple
grape,apple,cherry,pear
grape,pear,apple,cherry
*/

The above shows how to randomly sort or shuffle an array. This is useful in games. To achieve this I made use of the compareFunction argument of Array.sort(). Most sorting algorithms go through the array and compare values until the desired sort order is achieved. The compareFunction argument is a function that takes two values a and b and returns an integer that is negative positive or zero… see this info from the docs:
* A negative return value specifies that A appears before B in the sorted sequence.
* A return value of 0 specifies that A and B have the same sort order.
* A positive return value specifies that A appears after B in the sorted sequence.

So in the case of a randomizing an array you simply need to return a random int -1, 0 or 1. This is what I’ve done in the past (Math.round()*2) -1) … but when I was writing this snippet it seemed like 0 caused less variation in the output of the array so I made the range from -4 to 4 instead. This could have just been my imagination, but it seems like having less chance of a zero caused the arrays to be a bit more shuffled.

The reason I also included a version that uses Tausworthe is because of the easy seeding. In some cases you may want to use seeded randomness to sort an array.

UPDATE:
Was digging around about this and found a much faster method for randomizing arrays… not a big deal if you have small arrays, but if you need to randomize 1000’s of values this method is much faster than using Array.sort()

Read snippet: Random Sort

Not a Snippet (wandering robots)

package {
	import flash.display.Sprite;
    
    [SWF(width=500, height=500, backgroundColor=0xEFEFEF, frameRate=30)]
	public class Main extends Sprite{
		private var _robotManager:RobotManager;
		public function Main(){
		  _robotManager = new RobotManager(this, 12);
		}
	}
}

class RobotManager{
	
	private var _robots:Array;
	private var _top:Sprite;
	private var _robotNum:int;
	
    public function RobotManager(top:Sprite, robotNum:int){
    	_top = top;
    	_robotNum = robotNum;
    	_robots = new Array();
    	setupRobots();
    	top.addEventListener(Event.ENTER_FRAME, onRun);
    }
    
    private function setupRobots():void{
    	for (var i:int = 0; i<_robotNum; i++){
    		_robots[i] = new Robot();
    		_robots[i].x = 100+(i % 3) * 150;
    		_robots[i].y = 100+int(i / 3) * 100;
    		_robots[i].addEventListener("death", onRobotDie);
    		_top.addChild(_robots[i]);
    	}
    }
    private function onRobotDie(evt:Event):void{
    	for (var i:int = 0; i<_robotNum; i++){
    		if (_robots[i] == evt.currentTarget){
    			_robots.splice(i, 1);
    		}
    	}
    	_robotNum--;
    }
    
    private function onRun(evt:Event):void{
    	collisions();
    }
    
    private function collisions():void{
    	var currBot:Robot;
    	for (var i:int = 0; i<_robotNum; i++){
    		currBot = _robots[i];
    		for (var j:int = 0; j<_robotNum; j++){
    			if (currBot != _robots[j]){
    				var dx:Number = currBot.x - _robots[j].x;
    				var dy:Number = currBot.y - _robots[j].y;
    				if (Math.sqrt((dx * dx) + (dy * dy)) < 40){
    					currBot.die();
    				}
    			}
    		}
    	}
    }
}

import flash.display.*
import flash.events.*;

class Robot extends Sprite{
	private var _inc:Number
	private var _td:Number;
	private var _theta:Number;
	private var _rad:Number;
	
	public function Robot(){
		_theta = Math.random() * (Math.PI * 2);
		_td = _theta;
		_inc = Math.random() * .2 + .05;
		_rad = _inc * 10;
		with(graphics){
			beginFill(0x666666);
			drawRect(-10,-10,20,20);
			endFill();
			beginFill(0x333333);
			drawRect(-5, -5, 20, 10);
			lineStyle(0,0xAAAAAA);
			endFill();
			drawCircle(0,0,20);
		}
		addEventListener(Event.ENTER_FRAME, onRun);
	}
	
	private function onRun(evt:Event):void{
		_td  += _inc;
		_theta += _inc * Math.cos(_td);
		if (x < 0 || y < 0 || x > 500 || y > 500){
			_theta += Math.PI;
		}
		x += _rad * Math.cos(_theta);
		y += _rad * Math.sin(_theta);
		rotation = _theta / Math.PI * 180;
	}
	
	public function die():void{
		removeEventListener(Event.ENTER_FRAME, onRun);
		addEventListener(Event.ENTER_FRAME, onDie);
	}
	
	private function onDie(evt:Event):void{
		scaleX = scaleY += .1;
		alpha -= .1;
		if (scaleX > 2){
			removeEventListener(Event.ENTER_FRAME, onDie);
			if (parent){
				parent.removeChild(this);
				dispatchEvent(new Event("death"));
			}
		}
	}
}

This code should be placed in a document class… not the timeline (hopefully you already know that)

The above creates 12 wandering robots that die when they collide with one another.

This is not a snippet really… but it’s only slightly over 100 lines and it contains a few tricks I find myself using from time to time.

You can view the swf here.

Read snippet: Not a Snippet (wandering robots)