Category Archives: arrays

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

Script List Pattern

Actionscript:
  1. var currentState:String = "";
  2.  
  3. var functionList:Vector.<Function> = new Vector.<Function>();
  4.  
  5. function clearFunctions():void{
  6.     functionList = new Vector.<Function>();
  7. }
  8. function addFunction(f:Function):Function {
  9.     functionList.push(f);
  10.     return addFunction;
  11. }
  12.  
  13. function removeFunction(f:Function):void {
  14.     for (var i:int = 0 ; i<functionList.length; i++){
  15.         if (f == functionList[i]){
  16.             functionList.splice(i, 1);
  17.         }
  18.     }
  19. }
  20.  
  21. function runProgram():void {
  22.    
  23.     currentState = "current: ";
  24.    
  25.     for (var i:int = 0; i<functionList.length; i++){
  26.         functionList[i]();
  27.     }
  28.    
  29.     trace(currentState);
  30. }
  31.  
  32. function one():void{
  33.     currentState += " one";
  34. }
  35.  
  36. function two():void {
  37.     currentState += " two";
  38. }
  39.  
  40. function three():void {
  41.     currentState += " three";
  42. }
  43.  
  44. function dot():void{
  45.     currentState += ".";
  46.    
  47. }
  48.  
  49. // test it:
  50. addFunction(one);
  51. addFunction(two);
  52. addFunction(three);
  53.  
  54. runProgram();
  55.  
  56. removeFunction(one);
  57.  
  58. runProgram();
  59.  
  60. addFunction(dot)(dot)(dot);
  61.  
  62. runProgram();
  63.  
  64. clearFunctions();
  65.  
  66. addFunction(dot)(dot)(dot);
  67.  
  68. addFunction(three)(two)(one)(dot)(dot)(dot);
  69.  
  70. runProgram();
  71.  
  72. /* outputs:
  73. current:  one two three
  74. current:  two three
  75. current:  two three...
  76. current: ... three two one...
  77. */

This is a very quick implementation of a pattern that I use sometimes. The idea of this pattern is very simple and can easily be implemented in OOP or procedural style programming. The idea is to have a Vector/Array of functions or Class instances. Loop through this Vector/Array and run each function (or a given method of each Class instance). During runtime your client code can alter this list to change what the program does.

I use this technique for games quite often. All enemies get added to an enemy list - this list is looped through and each enemies run() method is called. If an enemy dies it dispatches an event that tells the enemy manager to remove it from the list. Some pseudo code:

Actionscript:
  1. function onMainLoop():void{
  2.     if (!paused){
  3.        
  4.         runWorld();
  5.         runKeys();
  6.         runChar();
  7.        
  8.         enemyManager.runEnemies();
  9.        
  10.         runPickups();
  11.        
  12.     }else{
  13.         // show pause screen
  14.     }
  15. }
  16.  
  17. //... inside EnemyManager class
  18. function onRunEnemies():void{
  19.     for (var i:int = 0; i<enemyList.length; i++){
  20.             enemyList[i].run(i);
  21.     }
  22. }

I use the same technique for pickups (coins, lives etc....).

I first used this technique in Director with a list of parent scripts.

I'm aware of other more refined patterns that are meant to do similar things, but for small to medium sized apps this has worked very nicely for me.

Also posted in Vector, misc | Tagged , | 2 Comments

Dynamic Vars Dictionary

Actionscript:
  1. var vars:Dictionary = new Dictionary();
  2.  
  3. var sp:Sprite = new Sprite();
  4.  
  5. // associate variables with a sprite (or any non-dynamic class)
  6. vars[sp] = {posX:100, posY:100, velX:1, velY:1};
  7.  
  8. // read
  9. trace(vars[sp].posX);

I've heard people mention that they wish the sprite class were dynamic... meaning they wish they could add methods and properties to a Sprite instance at runtime. There's no way I know of to do this, however... the dictionary class can be used to associate variables with any non-dynamic class instance... as it does in this the above example.

The dictionary class is similar to an associative array except that instead of using strings for keys, dictionaries use object instances.

Also posted in Dictionary, dynamic | Tagged , | 1 Comment

2D Vector

Actionscript:
  1. var map:Vector.<Vector.<int>> = new Vector.<Vector.<int>>();
  2. map[0] = new Vector.<int>();
  3. map[0].push(1);
  4. map[0].push(0);
  5. map[0].push(0);
  6.  
  7. map[1] = new Vector.<int>();
  8. map[1].push(0);
  9. map[1].push(1);
  10. map[1].push(0);
  11.  
  12. map[2] = new Vector.<int>();
  13. map[2].push(0);
  14. map[2].push(0);
  15. map[2].push(1);
  16.  
  17. /*
  18. map:
  19. 1,0,0
  20. 0,1,0
  21. 0,0,1
  22. */

This creates a two dimensional Vector of ints (flash 10 player only). The first line is the real snippet... took me a few minutes to get the syntax right the first time I needed a 2D Vector.

Also posted in Vector | Tagged , | Leave a comment