Archive

Archive for the ‘ActionScript’ Category

Life (Cached)

June 22nd, 2011 2 comments

Sean Cooper recently ran a challenge at Lolapps to create the fastest version of Conway’s game of life in Flash that we could. Of course, he first showed us his version which uses a convolution filter, but that’s not what this challenge was about. The idea was to figure out how to make AS3 both perform and display as fast as possible. Of course I immediately found someone else’s Pixel Bender version but after playing with that I went my own route to see what I could do in pure AS3.

For the impatient, you can view an animation which helps to explain the concept or jump straight to the result.

Pretty quickly, the discussion I was a part of moved towards the possibility of caching. After getting the initial naive version of Life finished, I let the caching idea bounce around in my head and finally came up with an idea. Since (basic) life has only two states per pixel, alive or dead, these map trivially to bits. Taking an arbitrary rectangle of the map and reducing it to a simple integer then is easy. Additionally, operations on this section can be done via bitshifting and bitwise operations, which tend to be extremely fast. Unfortunately, the uint in AS3 is only 32 bits long, so this limits the size of the “chunk” we can put into a single uint, but then again 2^32 would be a lot of states to possibly store and/or calculate. I also found that if I try to make a Vector.<uint> 2^30 long, Flash hangs, then crashes.

Let’s assume for now that we’re going to deal with Life in 3×3 cell chunks. I’ll explain why later on. We’ll start with a 9×9 set of cells:

A 9x9 section of cells

Then break that up into 3×3 chunks of cells.

3x3 chunks

Let’s look at the center chunk:

The center chunk

The simple life rules make each cell depend on its immediate neighbors in every direction.

  • If a cell has less than 2 live neighbors it dies (or stays dead) due to loneliness.
  • If a cell has 2 live neighbors it stays as it is, dead or alive.
  • If a cell has 3 live neighbors it is alive in the next iteration (dead cells come alive, live cells stay alive).
  • If a cell has 4 or more live neighbors it dies of overcrowding.

To run these rules for a single cell we need the ring of cells around it to calculate its next state. In the same way, to calculate the next state of a 3×3 set of cells we need the ring around it, making the chunk we need to look at a 5×5 chunk of cells.

5x5

This is what ultimately limits the size of the chunks we can easily cache. 5×5 cells mean we need 25 bits to make them into a uint. 5×6 would make 30 bits and a simple array that big crashes Flash.

Now that we’ve established the basics of what we need it’s just a matter of figuring out how to efficiently calculate, store, and retrieve the values.

We’ll store the state transitions in a simple vector of uints. The index will be the current state and the value is the next state. For the current state we take the 5×5 chunk, turn the pixels into bits, then put them together to make a uint.

5x5 as bits, the top-left is the least significant bit (2^0)

= 9870129

Now we have the center chunk’s current 5×5 state as a uint. 9870129 will be the index into the state transition map. Now we need the state that this will become after the rules are applied.

The next state

Note that the ring around the 3×3 chunk is all empty. Since what we’re calculating for is the 3×3, that’s all we care about. We needed the 5×5 to be able to say what the 3×3 became and in the result we store the uint with only the 3×3 chunk filled out.

Result bits

= 4194688

Once this is done for all of the 3×3 chunks, you run it all over again. In order to get the 5×5 you can mask out the bits needed in the neighbors, bitshift them, and bitwise-or them together to get the 5×5 uint to index back into the state transition map. To speed things up even more you can store those masked and bitshifted parts separately so all you need to do is bitwise-or them together to find out what the next state is.

If you made it this far, thanks for reading. Here again is a link to the explanatory demo, which is where the screenshots above came from.

And, finally, the result. The fastest Life implementation I’ve made thus far. :-) You can press ‘r’ to switch to another pattern (try resizing to 1440×599) and then again to get a random start state. ‘p’ pauses the animation. Enjoy!

Click to view the completed application

 

Categories: ActionScript, Flash Tags:

Java-style Typesafe Enumerations in AS3: Round 2

December 23rd, 2010 No comments

After creating my first Enum class for AS3 I found out that Flash was behaving unexpectedly when running the static initializations. Unfortunately, the order of the static declarations isn’t always the order in which Flash runs them. In a simple example with just a few classes I found that the initialization order was the same as the order of the declarations in the file, hence causing the generated ordinal values to be in the defined order, just like in Java. However, in a more complicated application the order became somewhat random, causing the ordinal values to not match what they might be in Java. In the case where you don’t care what the ordinal values are, (i.e. you use the names for storage or network communication or are only using the static vars directly in code) you don’t need to worry about this. However, if you want to use the ordinal values then you’ll have to go back to specifying the ordinal values manually. However, this Enum class still gets you a lot more than just static ints. The type safety alone is worth it in my opinion. Without further ado, the updated class:

package com.reversefold.util {
	import flash.errors.IllegalOperationError;
	import flash.utils.Dictionary;
	import flash.utils.describeType;
	import flash.utils.getQualifiedClassName;
 
	/**
	 * An abstract class to emulate Enum type.
	 * 
	 * Subclasses should follow this pattern:
	 * 
	 * package com.example {
	 * 	public class TestEnum extends Enum {
	 * 		public static const ONE : TestEnum = new TestEnum(1);
	 * 		public static const TWO : TestEnum = new TestEnum(2);
	 * 		public static const THREE : TestEnum = new TestEnum(3);
	 * 		
	 * 		public static function get values() : Vector.<testenum> {
	 * 			return Vector.</testenum><testenum>(Enum.getValues(TestEnum));
	 * 		}
	 * 		
	 * 		{
	 * 			initEnumConstant(TestEnum);
	 * 		}
	 * 	}
	 * }
	 */
	public class Enum {
		protected static var sequence : Dictionary = new Dictionary();
 
		/**
		 * To protect from instantiation after static initializing.
		 */
		private static var values : Dictionary = new Dictionary();//.<vector .<Enum>>
 
		private static var valuesByName : Dictionary = new Dictionary();//.<object>
 
		/**
		 * Function to call for each enum type declared and in static init.
		 */
		protected static function initEnumConstant(inType : Class) : void {
			var className : String = getQualifiedClassName(inType);
			var typeXML : XML = describeType(inType);
			var newValues : Vector.<enum> = new Vector.</enum><enum>();
			var newValuesByName : Object = {};
			for each (var constantXML : XML in typeXML.constant) {
				var name : String = constantXML.@name;
				var constant : Enum = inType[name];
				constant._label = name;
				newValues.push(constant);
				newValuesByName[name.toUpperCase()] = constant;
			}
			//sort by ordinal
			values[className] = newValues.sort(
				function(lhs : Enum, rhs : Enum) : Number {
					return lhs._ordinal > rhs._ordinal ? 1 : (lhs._ordinal < rhs._ordinal ? -1 : 0);
				}
			);
			valuesByName[className] = newValuesByName;
		}
 
		protected static function getValues(inType : Class) : Vector.<Enum> {
			return Vector.</enum><enum>(values[getQualifiedClassName(inType)]);
		}
 
		protected static function getByName(inType : Class, inName : String) : Enum {
			return Enum(valuesByName[getQualifiedClassName(inType)][inName.toUpperCase()]);
		}
 
		protected static function getByOrdinal(inType : Class, inOrdinal : int) : Enum {
			var values : Vector.</enum><enum> = getValues(inType);
			if (inOrdinal >= values.length) {
				throw new Error("There is no enum value for ordinal " + inOrdinal + " in class " + getQualifiedClassName(inType));
			}
			return values[inOrdinal];
		}
 
		/**
		 * Enum label.
		 */
		private var _label : String;
		public function get label() : String {
			return _label;
		}
 
		private var _ordinal : uint;
		public function get ordinal() : uint {
			return _ordinal;
		}
 
		public function Enum(inOrdinal : int = -1) {
			var className : String = getQualifiedClassName(this);
			if (values[className]) {
				throw new IllegalOperationError("Cannot instantiate anymore: " + className);
			}
			if (inOrdinal == -1) {
				var seq : uint;
				if (!sequence[className]) {
					seq = 0;
				} else {
					seq = sequence[className] + 1;
				}
				_ordinal = seq;
				sequence[className] = seq;
			} else {
				_ordinal = inOrdinal;
			}
		}
 
		public function toString() : String {
			return ordinal + " " + label;
		} 
	}
}
</enum></object></vector></testenum>

Categories: ActionScript, Flash Tags:

Java-style Typesafe Enumerations in AS3

July 22nd, 2010 No comments

UPDATE: There is a new version of the Enum class in the next post.

Enumerations are one of the major language features that I miss in AS3, especially when writing client-side versions of Java code which use Java’s robust enumerations. This has been discussed elsewhere quite a bit so I’ll just do a quick recap and then give my new updated version.

The simplest version of an enumeration you can do in AS3, of course (and the one most people use) are static const String values that are set in a class which is meant not to be instantiated.

package com.example {
	public class SimpleEnum {
		public static const ONE : String = "One";
		public static const TWO : String = "Two";
		public static const THREE : String = "Three";
	}
}

This works for the simplest cases but doesn’t come near to having the features of Java’s enumerations. One alternate version uses int values to make the conversion from Java to AS3 easier (Java uses int values to identify each enumeration value which is called an ordinal).

package com.example {
	public class SimpleEnum {
		public static const ONE : uint = 1;
		public static const TWO : uint = 2;
		public static const THREE : uint = 3;
	}
}

The main problem with both of the above is that any time you use one of your SimpleEnum values, you are using a simple type (String or uint) which allows any random value to be passed in, not just those that you have defined.

The next step is to use instances of the Enum class for each one of the constants. This makes your enumerations typesafe and allows you to have your enum values be real objects with member functions and variables.

package com.example {
	public class SimpleEnum {
		public static const ONE : SimpleEnum = new SimpleEnum("One");
		public static const TWO : SimpleEnum = new SimpleEnum("One");
		public static const THREE : SimpleEnum = new SimpleEnum("One");
 
		private var _name : String;
		public function get name() : String {
			return _name;
		}
 
		public SimpleEnum(inName : String) {
			_name = inName;
		}
	}
}

This is great as it enforces that any time you want to use a value from SimpleEnum you can ensure that it’s the right type, but this has a different form of the same issue above. Other code can happily create new versions of SimpleEnum and use them wherever.

It is at this point that some of the more esoteric bits of AS3 coding can be helpful. Private constructors would fix this problem right away but AS3 also lacks this language feature. For Singletons, most developers use a private class which is appended to the same file, after the package block ends. Unfortunately, this doesn’t work as the “private” class is not yet loaded when the static const variables are being created. Luckily, static initializers fix this problem.

package com.example {
	public class SimpleEnum {
		public static const ONE : SimpleEnum = new SimpleEnum("One");
		public static const TWO : SimpleEnum = new SimpleEnum("One");
		public static const THREE : SimpleEnum = new SimpleEnum("One");
 
		private var _name : String;
		public function get name() : String {
			return _name;
		}
 
		private static var _created : Boolean = false;
 
		//This code is run statically after the const vars above are created, closing off the constructor
		{
			_created = true;
		}
 
		public SimpleEnum(inName : String) {
			if (_created) {
				throw new Error("SimpleEnum is an enumeration, use the class constants instead.");
			}
			_name = inName;
		}
	}
}

I can see only two downsides to this pattern. Any function parameter or variable which is of the SimpleEnum type could be set to null. This is a common issue with Object Oriented programming, though, and can happen with Java’s enum type as well, so this is minimal. The larger possible issue is that the error for trying to use new SimpleEnum() happens at run-time and not compile-time. This could bite users who mistakenly try to instantiate the SimpleEnum class in their code and could potentially not be found right away, since a specific set of run-time conditions may have to be satisfied to call the offending code. However, with a helpful enough error message and documentation I think that this is a small issue.

This is essentially the pattern that I have adopted but I’ve added a few more features. Specifically, I’ve implemented an ordinal value which can be used for interaction with Java enum values or for advanced serialization or hashing and have added a function to get all of the possible values for use in iteration (or enumeration of the values….;-) ). The creation checking is also done in the base class so that a minimum of extra work needs to be done in the concrete enum classes.

package com.reversefold.util {
	import flash.errors.IllegalOperationError;
	import flash.utils.Dictionary;
	import flash.utils.describeType;
	import flash.utils.getQualifiedClassName;
 
	/**
	 * An abstract class to emulate Enum type.
	 * 
	 * Subclasses should follow this pattern:
	 * 
	 * package com.example {
	 * 	public class TestEnum extends Enum {
	 * 		public static const ONE : TestEnum = new TestEnum();
	 * 		public static const TWO : TestEnum = new TestEnum();
	 * 		public static const THREE : TestEnum = new TestEnum();
	 * 		
	 * 		public static function get values() : Vector.<testenum> {
	 * 			return Vector.</testenum><testenum>(Enum.getValues(TestEnum));
	 * 		}
	 * 		
	 * 		{
	 * 			initEnumConstant(TestEnum);
	 * 		}
	 * 	}
	 * }
	 */
	public class Enum {
		protected static var sequence : Dictionary = new Dictionary();
 
		/**
		 * To protect from instantiation after static initializing.
		 */
		protected static var values : Dictionary = new Dictionary();//.<vector .<Enum>>
 
		/**
		 * Function to call for each enum type declared and in static init.
		 */
		protected static function initEnumConstant(inType : Class) : void {
			var className : String = getQualifiedClassName(inType);
			var typeXML : XML = describeType(inType);
			var newValues : Vector.<enum> = new Vector.</enum><enum>();
			for each (var constantXML : XML in typeXML.constant) {
				var name : String = constantXML.@name;
				var constant : Enum = inType[name];
				constant._label = name;
				newValues.push(constant);
			}
			//sort by ordinal (instantiation order)
			values[className] = newValues.sort(
				function(lhs : Enum, rhs : Enum) : Number {
					return lhs._ordinal > rhs._ordinal ? 1 : (lhs._ordinal < rhs._ordinal ? -1 : 0);
				}
			);
		}
 
		protected static function getValues(inType : Class) : Vector.<Enum> {
			return Vector.</enum><enum>(values[getQualifiedClassName(inType)]);
		}
 
		/**
		 * Enum label.
		 */
		private var _label : String;
		public function get label() : String {
			return _label;
		}
 
		private var _ordinal : uint;
		public function get ordinal() : uint {
			return _ordinal;
		}
 
		public function Enum() {
			var className : String = getQualifiedClassName(this);
			if (values[className]) {
				throw new IllegalOperationError("Cannot instantiate anymore: " + className);
			}
			var seq : uint;
			if (sequence[className] == null) {
				seq = 0;
			} else {
				seq = sequence[className] + 1;
			}
			_ordinal = seq;
			sequence[className] = seq;
		}
 
		public function toString() : String {
			return ordinal + " " + label;
		} 
	}
}
</enum></vector></testenum>

And here is an example use:

package com.reversefold.shop.model {
	public class TestEnum extends Enum {
		public static const ONE : TestEnum = new TestEnum("One");
		public static const TWO : TestEnum = new TestEnum("Two");
		public static const THREE : TestEnum = new TestEnum("Three");
 
		//This function gives typesafe access to the list of constants that Enum.getValue() gives
		public static function get values() : Vector.<testenum> {
			return Vector.</testenum><testenum>(Enum.getValues(TestEnum));
		}
 
		//static initializer, make sure to pass in the current class as a parameter
		{
			initEnumConstant(TestEnum);
		}
 
		//read-only getter of the name value
		private var _name : String;
		public function get name() : String {
			return _name;
		}
 
		public function TestEnum(inName : String) : void {
			super();
			_name = inName;
		}
 
		override public function toString() : String {
			return super.toString() + " " + _name;
		}
	}
}
</testenum>

Thanks to all of the linked blog postings for their ideas. I only found Scott Bilas’ post after I’d finished writing my own extension of Peter Moelgaard’s version. Scott’s does nearly the same things mine does, but in a more C#-like way.

Categories: ActionScript Tags: