Category Archives: arrays

2D Map Avoid

Actionscript:
  1. [SWF(width=401,height=401,background=0xEFEFEF)]
  2.  
  3. var w:Number = stage.stageWidth-1;
  4. var h:Number = stage.stageHeight-1;
  5. var tileSize:Number = 20;
  6. var halfTileSize:Number = 20;
  7. var hTiles:Number = w / tileSize;
  8. var vTiles:Number = h / tileSize;
  9. var world:Shape = Shape(addChild(new Shape()));
  10. var map:Array=[];
  11. populateMap();
  12. var gridColor:uint = 0xCCCCCC;
  13. grid(tileSize,  gridColor);
  14.  
  15. vTiles -= 1;
  16. var movers:Array = [];
  17. for (var i:int = 0; i<100; i++){
  18.     movers.push(makeMover(i % hTiles, int( i / hTiles),0x000000))
  19.     movers.push(makeMover(i % hTiles, vTiles - int( i / hTiles),0xFF0000))
  20. }
  21. var moverNum:int = movers.length;
  22. hTiles -= 1;
  23.  
  24. addEventListener(Event.ENTER_FRAME, onLoop);
  25. function onLoop(evt:Event):void {
  26.     world.graphics.clear();
  27.     for (var i:int = 0; i<moverNum; i++){
  28.        movers[i]();
  29.      }
  30. }
  31. function populateMap():void{
  32.     for (var i:int = 0; i<vTiles; i++){
  33.         map[i] = [];
  34.         for (var j:int = 0; j<hTiles; j++){
  35.             map[i][j] = 0;
  36.         }
  37.     }
  38. }
  39. function grid(size:Number=30, lineColor:uint=0xFFFF00, lineAlpha:Number=1):void {
  40.     with(graphics){
  41.         lineStyle(0, lineColor, lineAlpha);
  42.         drawRect(0,0,w,h);
  43.         for (var i:Number = size; i<w; i+=size) {
  44.             moveTo(i, 0);
  45.             lineTo(i, w);
  46.         }
  47.         for (i = size; i<h; i+=size) {
  48.             moveTo(0, i);
  49.             lineTo(h, i);
  50.         }
  51.     }
  52. }
  53. function makeMover(x:Number, y:Number, col:uint):Function{
  54.     var xp:Number = x;
  55.     var yp:Number = y;
  56.     var prevX:Number = x;
  57.     var prevY:Number = y;
  58.     map[yp][xp] = 1;
  59.     var dx:Number = xp;
  60.     var dy:Number = yp;
  61.     var counter:int = 0;
  62.     return function():void{
  63.         if (counter> 20){
  64.             if (int(Math.random()*30) == 1){
  65.                 xp += int(Math.random()*2) - 1 | 1;
  66.                 xp = xp <0 ? 0 : xp;
  67.                 xp = xp> hTiles ? hTiles : xp;
  68.                 if (map[yp][xp] == 1){
  69.                      xp = prevX;
  70.                 }else{
  71.                     map[prevY][prevX] = 0;
  72.                     map[yp][xp] = 1;
  73.                     counter = 0;
  74.                 }
  75.                 prevX = xp;
  76.             }else
  77.             if (int(Math.random()*30) == 1){
  78.                 yp += int(Math.random()*2) - 1 | 1;
  79.                 yp = yp <0 ? 0 : yp;
  80.                 yp = yp> vTiles ? vTiles : yp;
  81.                 if (map[yp][xp] == 1){
  82.                      yp = prevY;
  83.                 }else{
  84.                     map[prevY][prevX] = 0;
  85.                     map[yp][xp] = 1;
  86.                     counter = 0;
  87.                 }
  88.                 prevY = yp;
  89.             }
  90.         }
  91.         counter++;
  92.         dx += (xp - dx) * 0.5;
  93.         dy += (yp - dy) * 0.5;
  94.         with(world.graphics){
  95.             lineStyle(0, gridColor,1, true)
  96.             beginFill(col);
  97.             drawRect(dx * tileSize, dy * tileSize, tileSize, tileSize);
  98.         }
  99.     }
  100. }

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...

Also posted in motion, random | Tagged , , | Leave a comment

x and y Coordinates in 1D Array / Vector

Actionscript:
  1. var canvas:BitmapData=new BitmapData(400,400,false,0x000000);
  2. addChild(new Bitmap(canvas));
  3. var pix:Vector.<uint>=canvas.getVector(canvas.rect);
  4.  
  5. canvas.lock();
  6. for (var i:int = 0; i<300; i++) {
  7.     var xp:int=50+i;
  8.     var yp:int=50+i/2;
  9.     // target x and y coords in 1D array
  10.     pix[xp+yp*400]=0xFFFFFF;
  11. }
  12. canvas.setVector(canvas.rect, pix);
  13. 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.

Also posted in BitmapData, Vector, pixel manipulation, setPixel | Tagged , , | Leave a comment

Array.push() Vector.push() Optimization

Actionscript:
  1. var tVerts:Vector.<Number> = new Vector.<Number>();
  2. var inc:int = 0;
  3. var t:Number, i:Number, j:Number, k:Number;
  4.  
  5.  // fast way
  6. t = getTimer();
  7. for (i= -2; i<2; i+=.03){
  8.     for (j = -2; j<2; j+=.03){
  9.         for (k = -2; k<2; k+=.03){
  10.             tVerts[inc] = i;
  11.             inc++;
  12.             tVerts[inc] = j;
  13.             inc++;
  14.             tVerts[inc]= k;
  15.             inc++;
  16.         }
  17.     }
  18. }
  19. trace(getTimer() - t);
  20.  
  21. tVerts  = new Vector.<Number>();
  22.  
  23. // slow way
  24. t = getTimer();
  25. for (i= -2; i<2; i+=.03){
  26.     for (j = -2; j<2; j+=.03){
  27.         for (k = -2; k<2; k+=.03){
  28.  
  29.             tVerts.push(i, j, k);
  30.         //  tVerts.push(j);
  31.         //  tVerts.push(k);
  32.         }
  33.     }
  34. }
  35. 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...

Also posted in Vector | Tagged , | 1 Comment

Hill Climbing

Actionscript:
  1. var target:Array = ("actionsnippet").split("");
  2. var leng:int=target.length;
  3. var iterations:int = 0;
  4.  
  5. var alphabet:Array = ("abcdefghijklmnopqrstuvwxyz").split("");
  6. var search:Array = randomString();
  7. var indices:Array = new Array();
  8. for (var i:int = 0; i<leng; i++) indices.push(i);
  9.  
  10. addEventListener(Event.ENTER_FRAME, onLoop);
  11. function onLoop(evt:Event):void {
  12.     for (var i:int = 0; i<10; i++){
  13.         if (indices.length> 0){
  14.            var ii:int = int(Math.random()*indices.length);
  15.            var index:int = indices[ii];
  16.          
  17.            search[index] = randomChar();
  18.            
  19.            if (search[index] == target[index]){
  20.                indices.splice(ii,1);  
  21.            }
  22.            trace(search);
  23.            iterations++;
  24.         }else{
  25.             trace("found after "+iterations+" iterations");
  26.             removeEventListener(Event.ENTER_FRAME, onLoop);
  27.             break;
  28.         }
  29.     }
  30. }
  31. function randomChar():String { return alphabet[int(Math.random()*alphabet.length)]; };
  32. function randomString():Array {
  33.     var str:Array = new Array();
  34.     for (var i:int = 0; i<leng; i++) {
  35.         str.push(randomChar());
  36.     }
  37.     return str;
  38. }

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

Also posted in misc, strings | Tagged , | 5 Comments

Vector.sortOn()

Actionscript:
  1. var a:Vector.<Sprite> = new Vector.<Sprite>();
  2.  
  3. trace("unsorted");
  4. for (var i:int = 0; i<10; i++){
  5.     var s:Sprite = new Sprite();
  6.     s.x = int(Math.random()*100);
  7.     a.push(s);
  8.     trace(s.x);
  9. }
  10.  
  11. quickSortOn(a, "x", 0, a.length-1);
  12.  
  13. trace("sorted");
  14. for (i= 0; i<10; i++){
  15.     trace(a[i].x);
  16. }
  17.  
  18. // modified code from kirupa.com
  19. // http://www.kirupa.com/developer/actionscript/quickSort.htm
  20. function quickSortOn(a:Vector.<Sprite>, prop:String, left:int, right:int):void {
  21.     var i:int = 0, j:int = 0, pivot:Sprite, tmp:Sprite;
  22.     i=left;
  23.     j=right;
  24.     pivot = a[Math.round((left+right)*.5)];
  25.     while (i<=j) {
  26.         while (a[i][prop]<pivot[prop]) i++;
  27.         while (a[j][prop]>pivot[prop]) j--;
  28.         if (i<=j) {
  29.             tmp=a[i];
  30.             a[i]=a[j];
  31.             i++;
  32.             a[j]=tmp;
  33.             j--;
  34.         }
  35.     }
  36.     if (left<j)  quickSortOn(a, prop, left, j);
  37.     if (i<right) quickSortOn(a, prop, i, right);
  38. }
  39. /* outputs something like:
  40. unsorted
  41. 26
  42. 33
  43. 20
  44. 63
  45. 7
  46. 68
  47. 75
  48. 39
  49. 67
  50. 53
  51. sorted
  52. 7
  53. 20
  54. 26
  55. 33
  56. 39
  57. 53
  58. 63
  59. 67
  60. 68
  61. 75
  62. */

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...

Also posted in Object, Vector, associative arrays, sortOn | Tagged , | 3 Comments

Fracture a Number

Actionscript:
  1. var target:Number = 1024;
  2. var slices:Array = [target];
  3. var leng:int = 11;
  4.  
  5. for (var i:int = 0; i<leng-1; i++){
  6.      var index:int = int(Math.random()*slices.length);
  7.      var val:Number = slices[index];
  8.      var rand:Number = Math.random() * val/2;
  9.      slices[index] = val - rand;
  10.      slices.push(rand);
  11. }
  12.  
  13. trace(slices);
  14.  
  15. // test that they all add up
  16. var sum:Number = 0;
  17. for (i = 0; i<slices.length; i++){
  18.     sum += slices[i];
  19. }
  20. 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

Also posted in misc | Tagged , | Leave a comment

Random Walk to Target

Actionscript:
  1. var target:Number = 360;
  2. var steps:Array = new Array();
  3. for (var step:Number = 0; step <target; step += int(Math.random() * 36 + 36)){
  4.     steps.push(Math.min(target,step));
  5. }
  6. steps.push(target);
  7. trace(steps);
  8. /* outputs something similar to:
  9. 0,46,99,144,189,259,330,360
  10. */

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

Also posted in misc | Tagged , | Leave a comment

Unique Array Comparison

Actionscript:
  1. function uniqueCompare(arr:Array, compare:Function):void {
  2.     var leng:int = arr.length;
  3.     for (var i:int = 0; i<leng; i++){
  4.         for (var j:int = i + 1; j<leng; j++){
  5.             compare(arr[i], arr[j]);
  6.         }
  7.     }
  8. }
  9.  
  10. var numbers:Array = [1, 2, 3, 4, 5];
  11.  
  12. uniqueCompare(numbers, compareCallback);
  13.  
  14. function compareCallback(a:*, b:*):void {
  15.     trace("compare " + a + " to " + b);
  16. }
  17.  
  18. /*
  19. outputs:
  20. compare 1 to 2
  21. compare 1 to 3
  22. compare 1 to 4
  23. compare 1 to 5
  24. compare 2 to 3
  25. compare 2 to 4
  26. compare 2 to 5
  27. compare 3 to 4
  28. compare 3 to 5
  29. compare 4 to 5
  30. */

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.

Also posted in misc | Tagged , | Leave a comment

Random Sort

Actionscript:
  1. function randomize(a:*, b:*):int{
  2.        return Math.round(Math.random()*8) - 4;
  3. }
  4.  
  5. var i:int;
  6. var fruits:Array;
  7.  
  8. trace("Math.random()");
  9. for (i = 0; i<4; i++){
  10.   // reset fruits array:
  11.   fruits = ["apple", "grape","pear","cherry"];
  12.   fruits.sort(randomize);
  13.   trace(fruits);
  14. }
  15.  
  16.  
  17. // seeds
  18. var s1:Number= 0xFF00FF;
  19. var s2:Number = 0xCCCCCC;
  20. var s3:Number= 0xFF00F0;
  21.  
  22. function tRandomize(a:*, b:*):int{
  23.        return Math.round(rand()*8) - 4;
  24. }
  25.  
  26. trace("\nTausworthe rand()");
  27. for (i= 0; i<4; i++){
  28.   fruits = ["apple", "grape","pear","cherry"];
  29.   fruits.sort(tRandomize);
  30.   trace(fruits);
  31. }
  32. // from www.ams.org/mcom/1996-65-213/S0025-5718-96-00696-5/S0025-5718-96-00696-5.pdf
  33. function rand():Number {
  34.     s1=((s1&4294967294)<<12)^(((s1<<13)^s1)>>19);
  35.     s2=((s2&4294967288)<<4)^(((s2<<2)^s2)>>25);
  36.     s3=((s3&4294967280)<<17)^(((s3<<3)^s3)>>11);
  37.     var r:Number = (s1^s2^s3) * 2.3283064365e-10;
  38.     r = (r<0) ? r+=1 : r;
  39.     return r;
  40. }
  41.  
  42. /*
  43. outputs:
  44. Math.random()
  45. grape,apple,pear,cherry
  46. pear,cherry,apple,grape
  47. grape,apple,pear,cherry
  48. grape,apple,cherry,pear
  49.  
  50. Tausworthe rand()
  51. apple,grape,pear,cherry
  52. cherry,grape,pear,apple
  53. grape,apple,cherry,pear
  54. grape,pear,apple,cherry
  55. */

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()

Also posted in misc | Tagged , | Leave a comment

Not a Snippet (wandering robots)

Actionscript:
  1. package {
  2.     import flash.display.Sprite;
  3.    
  4.     [SWF(width=500, height=500, backgroundColor=0xEFEFEF, frameRate=30)]
  5.     public class Main extends Sprite{
  6.         private var _robotManager:RobotManager;
  7.         public function Main(){
  8.           _robotManager = new RobotManager(this, 12);
  9.         }
  10.     }
  11. }
  12.  
  13. class RobotManager{
  14.    
  15.     private var _robots:Array;
  16.     private var _top:Sprite;
  17.     private var _robotNum:int;
  18.    
  19.     public function RobotManager(top:Sprite, robotNum:int){
  20.         _top = top;
  21.         _robotNum = robotNum;
  22.         _robots = new Array();
  23.         setupRobots();
  24.         top.addEventListener(Event.ENTER_FRAME, onRun);
  25.     }
  26.    
  27.     private function setupRobots():void{
  28.         for (var i:int = 0; i<_robotNum; i++){
  29.             _robots[i] = new Robot();
  30.             _robots[i].x = 100+(i % 3) * 150;
  31.             _robots[i].y = 100+int(i / 3) * 100;
  32.             _robots[i].addEventListener("death", onRobotDie);
  33.             _top.addChild(_robots[i]);
  34.         }
  35.     }
  36.     private function onRobotDie(evt:Event):void{
  37.         for (var i:int = 0; i<_robotNum; i++){
  38.             if (_robots[i] == evt.currentTarget){
  39.                 _robots.splice(i, 1);
  40.             }
  41.         }
  42.         _robotNum--;
  43.     }
  44.    
  45.     private function onRun(evt:Event):void{
  46.         collisions();
  47.     }
  48.    
  49.     private function collisions():void{
  50.         var currBot:Robot;
  51.         for (var i:int = 0; i<_robotNum; i++){
  52.             currBot = _robots[i];
  53.             for (var j:int = 0; j<_robotNum; j++){
  54.                 if (currBot != _robots[j]){
  55.                     var dx:Number = currBot.x - _robots[j].x;
  56.                     var dy:Number = currBot.y - _robots[j].y;
  57.                     if (Math.sqrt((dx * dx) + (dy * dy)) <40){
  58.                         currBot.die();
  59.                     }
  60.                 }
  61.             }
  62.         }
  63.     }
  64. }
  65.  
  66. import flash.display.*
  67. import flash.events.*;
  68.  
  69. class Robot extends Sprite{
  70.     private var _inc:Number
  71.     private var _td:Number;
  72.     private var _theta:Number;
  73.     private var _rad:Number;
  74.    
  75.     public function Robot(){
  76.         _theta = Math.random() * (Math.PI * 2);
  77.         _td = _theta;
  78.         _inc = Math.random() * .2 + .05;
  79.         _rad = _inc * 10;
  80.         with(graphics){
  81.             beginFill(0x666666);
  82.             drawRect(-10,-10,20,20);
  83.             endFill();
  84.             beginFill(0x333333);
  85.             drawRect(-5, -5, 20, 10);
  86.             lineStyle(0,0xAAAAAA);
  87.             endFill();
  88.             drawCircle(0,0,20);
  89.         }
  90.         addEventListener(Event.ENTER_FRAME, onRun);
  91.     }
  92.    
  93.     private function onRun(evt:Event):void{
  94.         _td  += _inc;
  95.         _theta += _inc * Math.cos(_td);
  96.         if (x <0 || y <0 || x> 500 || y> 500){
  97.             _theta += Math.PI;
  98.         }
  99.         x += _rad * Math.cos(_theta);
  100.         y += _rad * Math.sin(_theta);
  101.         rotation = _theta / Math.PI * 180;
  102.     }
  103.    
  104.     public function die():void{
  105.         removeEventListener(Event.ENTER_FRAME, onRun);
  106.         addEventListener(Event.ENTER_FRAME, onDie);
  107.     }
  108.    
  109.     private function onDie(evt:Event):void{
  110.         scaleX = scaleY += .1;
  111.         alpha -= .1;
  112.         if (scaleX> 2){
  113.             removeEventListener(Event.ENTER_FRAME, onDie);
  114.             if (parent){
  115.                 parent.removeChild(this);
  116.                 dispatchEvent(new Event("death"));
  117.             }
  118.         }
  119.     }
  120. }

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.

Also posted in Events, OOP, motion | Tagged , , | 3 Comments