Motor Physics: sequential impulses

I have now implemented Erin Catto’s Sequential Impulses solver which he presented in his Box2D mini demo. It’s equivalent to the PGS (Projected Gauss Seidel) algorithm when using SI with clamped accumulated impulses. You find more information in his paper.

The flash runs currently very slow because it’s not optimized at all, but so far I’m happy that it works. I really love SI as it overcomes the jitter of objects which also made stacking nearly impossible in the previous version. But I keep my old solver because it’s very fast and great for non-gravity environments or particle-sized objects where jitter was not an issue.

The last (and probably hardest) step is to rewrite all my collision functions to add contact caching capability, which is quite complicated. The Box2D engine only supports (guess what.. boxes) and the collision and contact generation code is far to slow to be enjoyable in flash, so it’s crucial to find a fast solution for this. Once this is done I can concentrate on the API.

FlashDevelop 3.0.0 Alpha released

Mika from flashdevelop.org: “Here’s a release that lots of people have been waiting for, FlashDevelop 3. This is an alpha release that may contain bugs or may lack some features but we wanted to start the release cycle for our new baby. We hope you like it.”

Hell yes, I love it! I also tried Flex Builder, but I prefer using FlashDevelop because it’s free, fast and has everything I need for Flash development. The only thing I’m missing is a built-in debugger, but as I understood the guys are also working on it.

More information: http://www.flashdevelop.org/community/viewtopic.php?t=1436

Data structures example: the queue class

FIFO - First In, First Out

The queue class is rather basic, which saves me a lot of writing :-). The idea is simple: Think of waiting in a line at a movie theater; you get in line at the end to buy a ticket (enqueue); you reach the head of the line (peek) and finally buy the ticket and leave the line (dequeue). To use the queue class you only need three basic methods. Here are the method signatures:

var success:Boolean = myQueue.enqueue(obj);
var obj:* = myQueue.peek();
var obj:* = myQueue.dequeue();

Enqueue() obviously enqueues an item, peek() returns an instance to the front item and dequeue() removes and returns the front item at the same time. Here is a simple demonstration (first click flash to get focus):

Use key e to enqueue an item and d to dequeue the front item (blue colored circle). The numbers indicate the order of the items inside the queue. Lower numbers leave the queue before higher numbers. Also if the queue is full, all nodes are purple colored.

Size matters

A limitation of the queue class is that it has be to initialized with a fixed size. So in case the queue is full, the enqueue() method does nothing and just returns false:

var success:Boolean = myQueueInstance.enqueue(obj);

Defining a size for a new queue is also a bit different from other classes in the package because it has to be a multiple of two - this is needed for a fast bitwise modulo to speed up the array access. A queue is used so often in game programming that it should run as fast as possible, although it wasts some memory - the array might be bigger than actually needed. Instead of passing the target size directly, you pass the exponent by which 2 is raised:

var myQueueInstance:ArrayedQueue = new ArrayedQueue(4);

The queue above can store 16 items, because 2^4 (eq. 1 << 4) is 16. To be able to store 32 items, pass 5 (2^5) and so on.

Performance

If you now think “Who needs a class for it ? I keep it real and just use the native flash array methods push() and shift() !” then I have a surprise for you. Lets create a really big queue with more than 100,000 elements (131,072 to be exactly, which is 2^17). Now we enqueue items until its full, then empty it with dequeue.

The push/shift version (or unshift/pop, it doesn’t matter) takes 13 seconds(!) on my machine:

var size:int = 1 << 17;
var que:Array = [];
for (var i:int = 0; i < size; i++)
{
    que.push("foo");
}
for (var i:int = 0; i < size; i++)
{
    var result:String = que.shift();
}

Now the queue class, which takes only 40 milliseconds:

var aq:ArrayedQueue = new ArrayedQueue(17);
var success:Boolean;
do
{
    success = aq.enqueue("foo");
}
while (success);

var result:String;
do
{
    result = aq.dequeue();
}
while (result);

Here is a comparison table using a queue with a more realistic size:

As you see, the queue class grows linearly in processing time, while the array methods increases more drastically. This is because the flash player has to move a lot of data around inside the memory every time you add or remove the first element of an array (or any other in between except for the last one).

For very small queues, the class is a little bit slower. On the other hand it manages the size of the queue for you and also provides an iterator and implements the collection interface.

So this should be all you need to know about queues. Besides, the package contains also the LinkedQueue, which is based on a linked list, thus has no size limitations and performs the same no matter how many elements are stored inside it. The class itself is simple - it just defines some wrapper functions for a the linked list to provide queue-like access.

A command queue

Finally a little real-world example of what is called a command queue. I used it to create a very basic waypoint system. Click on the flash to add a waypoint, and the ‘plane’ (the colored circle) follows all waypoints until the queue is empty.

The sources for the flash examples can be downloaded here (Flash CS3 required). Next in the series will be the graph class, so stay tuned :-)

See also:
Linked lists
The tree class
The graph class

Data structures example: the tree class

First, I have updated the data structures source to version 0.7.3, so make sure you have the latest version. The source code for the SWFs in this post can be obtained here (Flash CS3 required).

Using the tree iterator

Before we build a tree its important to understand how the tree iterator works. Normally the iterator is used to iterate over the structure’s data - in this case the iterator additionally acts as a ‘marker’ and points to the node at which we may modify the tree.
Also, the tree iterator is somewhat special, because it allows you to iterate through the tree in two directions: horizontally and vertically. Therefore it has to manage two node references simultaneously, making it more complex than other iterators.

In the figure below, the purple colored node is the vertical iterator and is used to move up and down the tree using the treeNodeInstance.parent property, while the blue node is obviously the horizontal iterator and can only step left and right through the node’s children.

I think a simple demonstration is worth more than thousand words, so you can try it yourself by playing around with the tree using the keys below (first click the flash to get focus):

up/down, left/right: moves the vertical (V) and horizontal (H) iterator
home: deletes the whole tree
a: appends a child node to the (V) node
i: inserts a node after the (H) node
d: recursively removes all child nodes from the (V) node
r: removes the (H) node

Building a simple tree

Now let’s look how to build a tree in ActionScript. First we create the root of the tree and get an iterator pointing to this node:

var tree:TreeNode = new TreeNode("root");
var itr:TreeIterator = tree.getTreeIterator();

The root has three children, so lets add them:

for (var i:int = 0; i < 3; i++)
{
    itr.appendChild("node" + i);
}

Now the root’s second child (’node1′) has children by itself. To insert them, we first have to adjust the vertical iterator so it points to ‘node1′. First one step to the right, then one step down the tree:

itr.nextChild();
itr.down();

Now we can add ‘node3′ and ‘node4′, this time in a reverse order:

itr.prependChild("node" + 3);
itr.prependChild("node" + 4);

The first time we add a child node to an empty node, the horizontal iterator is automatically initialized to point to the first child, which in this case is ‘node4′. So to create ‘node5′ and ‘node6′ we only need to go another step down.

itr.down();
itr.appendChild("node" + 5);
itr.appendChild("node" + 6);

Finally we want to add ‘node7′. Therefore we ‘bubble up’ the tree until we arrive at the root node, go to the rightmost child, one step down and add it:

itr.root();
itr.childEnd();
itr.down();
itr.appendChild("node" + 7);

The dump() method invoked on the root node prints out the complete tree, as you can see it matches the tree above.

[TreeNode > (root) has 3 child nodes, data=root]
+---[TreeNode > (leaf), data=node0]
+---[TreeNode >  has 2 child nodes, data=node1]
|    +---[TreeNode >  has 2 child nodes, data=node4]
|    |    +---[TreeNode > (leaf), data=node5]
|    |    +---[TreeNode > (leaf), data=node6]
|    +---[TreeNode > (leaf), data=node3]
+---[TreeNode >  has 1 child nodes, data=node2]
|    +---[TreeNode > (leaf), data=node7]

Preorder and postorder traversal

Now that you have created a tree structure, you need a way of traversing the nodes so you access the node’s data. There are two common recursive algorithms for doing this. The preorder function first visits the node that is passed to the function and then loops through each child calling the preorder function on each child. The postorder on the other hand does the opposite: It visits the current node after its child nodes.
To see this in action just click a node in the demo below. The numbers indicate the order in which the nodes are visited.

The TreeNode class also supports a regular iterator using hasNext() and next(). This matches the preorder iterator, but is implemented in a non-recursive way.

See also:
Linked lists
The queue class
The graph class

Data Structures released

I’ve just released the first version of my data structures package for AS3.
There is no example code included, but I have started writing some simple demonstrations which I’ll post successively.