Motor Physics: 50 dancing boxes

This is a follow up to the post about the SI-Solver from the Box2D engine. The revised demo shows a worst case scenario with 50 stacked boxes. It took great effort to max out performance, but I think it’s fast enough now, especially when realizing that the engine does a lot of computations each frame to make things stable (for example 50 sequential impulse computations per box). Performance is top priority, because a physics system which sucks up all processing time doesn’t leave room for rendering, AI and other game engine elements and hence is useless for more complex games.

I still see a lot potential to make it faster, probably in the range of 30-70%, but I won’t go into that for now. Instead I’m concentrating on putting the engine pieces together and adding forces, constraints and user interactivity. Enough with just bouncing stuff!

As a side note, I also decoupled the simulation from the frame rate (which I should have done a long time ago), so the physics attempts to run at a constant rate, which is very important for games. The example above is limited to 60fps so it tries to update the simulation every ~16ms. When the fps counter shows more than 60fps, there is still processing time available.

Method overloading using namespaces

It’s too bad that AS3 can’t handle method overloading natively, but there is a way to add at least similar functionality using namespaces. True overloading capability means that the compiler figures out which function to use based on the given arguments. Here you have to help the compiler by giving the appropriate namespace tag:

package
{
    import flash.display.Sprite;

    public class MethodOverloadingExample extends Sprite
    {
        //three methods: three namespaces
        public namespace m1;
        public namespace m2;
        public namespace m3;

        public function MethodOverloadingExample():void
        {
            m1::overloadedMethod(1);
        }

     m1 function overloadedMethod(arg0:int):void
        {
            trace("method 1, args=" + arguments.join("|"));

            var out:Boolean = m2::overloadedMethod(1, 2);
        }

     m2 function overloadedMethod(arg0:int, arg1:int):Boolean
        {
            trace("method 2, args=" + arguments.join("|"));

            var out:Number = m3::overloadedMethod(1, 2, 3);
            return true;
        }

     m3 function overloadedMethod(arg0:int, arg1:int, arg2:int):Number
        {
            trace("method 3, args=" + arguments.join("|"));
            return 3;
        }
    }
}

After instantiating the class the various trace calls print out this:

overloaded method 1, args=1
overloaded method 2, args=1|2
overloaded method 3, args=1|2|3

All methods can have different signatures (number of arguments and return type). Nested ‘overloaded’ method calls are allowed, too. I ran a lot of benchmarks and it turned out that namespaces don’t affect performance at all, so you can use this technique for time-critical situations as well.

If you want to access the methods from outside the class you first have to retrieve the namespace and make the call through it. Somehow you can’t access a namespace directly without getting complains from the compiler, so create a get function first.

//inside the class
public function getNameSpace1():Namespace
{
    return m1;
}
...

//outside the class
var m1:Namespace = obj.getNameSpace1();
obj.m1::overloadedMethod(0);

Data structures example: the graph class

In the last data structures post I talked about the tree structure, now let’s head towards graphs. As usual I’m also providing the source files for all included examples, which you can download here.
The code is a bit rough and there is plenty room for optimizations, but nevertheless I hope you understand what’s going on. Also make sure you have the latest release, because I have modified almost all graph-related classes.

What’s a graph?

Graphs (also known as Networks) are very powerful structures and find their applications in path-finding, visibility determination, soft-bodies using mass-spring systems and probably a lot more. A graph is similar to a tree, but it imposes no restrictions on how nodes are connected to each other. In fact each node can point to another node or even multiple nodes at once.

A node is represented by the GraphNode class, and the connections between GraphNode objects are modeled by the GraphArc class. The arc has only one direction (uni-directional) and points from one node to another so you are only allowed to go from A to B and not in the opposite direction. Bi-directional connections can be simulated by creating an arc from node A to B and vice-versa from B to A. Also, each arc has a weight value associated with it, which describes how costly it is to move along the arc. This is optional though, so the default value is 1.

Putting it together, the graph is implemented as an uni-directional weighted graph. The Graph manages everything: it stores the nodes and the arcs in separate lists, makes sure you don’t add a node twice, or mess up the arcs (for example if you remove a node from the graph, it also scans the arc list and removes all arcs pointing to that node) and provides you with tools to traverse the graph.

Building the graph structure

In figure 1, you see a simple graph containing 8 nodes. You can add additional nodes, which will be placed at the position of the cursor by pressing ‘a’ or start with a fresh graph by pressing ‘r’. To create an arc point from node A to Node B, simply click both nodes successively. Traversal is also possible: First press ‘t’ to switch to ‘traverse’ mode, then click a node to find all nodes which are connected to the this node.

Graph traversal

If you have tried out the traversal in the example above, you may wonder how it’s done. The answer lies in two common algorithms to accomplish this: Breadth-first search (BFS) and depth-first search (DFS). (The demonstration above used the breadth-first search.)

The BFS algorithm visits all nodes that are closest to the starting node first, so it gradually expands outward in all directions equally. This looks like a virus infecting the direct neighborhood at each search iteration. BFS utilizes a queue and proceeds as follows:

1. Mark the starting node and enqueue it.
2. Process the node by calling a user-defined function on it.
3. Mark all connected nodes and also put them into the queue.
4. Remove the node at the front of the queue.
5. Repeat steps 2-5 with the node that is now at the front of the queue.
6. Stop if the queue is empty.

The depth-first search (DFS) on the other hand takes the starting node, follows the next arc it finds to get to the next node, and continues this until the complete path has been discovered, then goes back to the starting node and follows the next path until it reaches a dead end and so on. It’s currently implemented as a recursive function, that means that it probably can fail for very large graphs when the call-stack exceeds the maximum size (I don’t know how big it is in AS3 though).

Both algorithms have in common that they mark a node when it’s added to the queue, otherwise the node would be enqueued and unnecessarily processed multiple times, because different nodes can all point to a common node. So before you start a BFS or DFS it’s very important to reset all markers by calling the clearMarks() function on the graph.

The two algorithms are visualized in figure 2 below. I’ve created a rectangular grid of nodes (similar to a tilemap) by connecting each node with the top, bottom, left and right neighbors (I left out the arcs because it would be a total mess). I have also deleted some nodes to show you that both algorithms don’t rely on a regular structure and can look like anything. Just click a node to start the traversal. You can toggle between both algorithms by pressing ‘b’ BFS and ‘d’ (guess what ;-)).

BFS is much more useful than DFS in most situations. But DFS is likely to be faster, for example when you only want to modify all connected nodes in some way.

A graph-based A* pathfinder

Now for the cool part. I have created a pathfinder to demonstrate the power of the BFS algorithm. When building the graph it’s important that all arcs are bi-directional, so the pathfinder can figure out the shortest path between two locations.

I can’t explain how a pathfinder works in detail, because it’s a vast subject, but actually it’s not that different from the tile-based version, which you probably realized when looking at figure2: in a tilemap, you have 8 directions (N, S, W, E, NW, NE, SW, SE) and you go from one tile to another by adjusting the x and y tile index, in a graph you just follow all arcs of the current node. The implementation is a little chaotic, because I have to render and compute the path simultaneously, so it needs definitely some refactoring to make it clean and reusable, but for demonstration purposes it should hopefully do the work.

After finding a path through the A* algorithm, I store the nodes in a queue. You could then use a command queue so a character can follow the path. In contrast to tile-based path finding, the graph based version is lightning fast and there is still plenty room for optimizations: for example you could run a breath-first search on the graph to precompute all distances between the nodes. That’s all I have to say about graphs, next time I take an closer look at my favorite structure – linked lists!

See also:
Linked lists
The queue class
The tree class

Data structures now at Google Code

I created a Google Code project to host my data structures package. Now you can use the SVN repository to easily get updated with the newest revision.

Besides some bug fixes I added two things:

1. For all structures that have to be initialized with a fixed size and are not resizeable I’ve included a ‘maxSize’ property. This applies to ArrayedQueue, ArrayedStack, Graph, HashTable, Heap and PriorityQueue.
2. The Queue class has a new method, dispose(). For performance reasons, when dequeuing an item it is not removed but may be overwritten later (this is a circular array). For very large queues this can lead to memory waste. To overcome this call the dispose() function directly after (and only after!) the dequeue() function to clear the dequeued item so the garbage collector can take care of it.

AS3 Data Structures For Game Developers (as3ds)
http://code.google.com/p/as3ds/

Int, uint and number data type conversion

There has been a discussion in the past which data type is the fastest in AS3, or how to improve performance by using certain data types in different situations. The answer is actually very simple: performance loss occurs only when converting between data types. This is demonstrated in the loop body below, where a variable of one type is assigned to the other:

var a:uint = 0;
var b:uint = 1 << 28;

var t:Number = getTimer();
for (var i:int = 0; i < 1e+7; i++)
{
	a = b;
}
trace(getTimer() - t);

The loop above computes in 56ms on my machine. The same loop using only signed integers or numbers for a and b takes exactly the same time:

//int only
var a:int = 0;
var b:int = 1 << 28;
...

//number only
var a:Number = 0;
var b:Number = 1 << 28;
...

Now, when var a and b is of mixed type one type has to be promoted or demoted to the other type:

//number -> uint is ~1.8x slower
var a:uint;
var b:Number;
a = b;

//uint -> number is ~2.3x slower
var a:Number;
var b:uint;
a = b;

//number -> int is ~1.8x slower
var a:int;
var b:Number;
a = b;

//no work has to be done here
var a:Number;
var b:int;
a = b;

This also holds true when performing arithmetics, but not for the uint type. According to the documentation, the sum of two integers is an integer, the sum of two numbers is a number. Adding two unsigned integers needs a data type conversion first:

//~1.2x slower
var a:uint;
var b:uint;
var c:uint = a + b;

//no difference with:
var a:int;
var b:int;
var c:int = a + b;

//or:
var a:Number;
var b:Number;
var c:Number = a + b;

I have chosen the value 1 << 28 because André Michelle posted that getQualifiedClassName() outputs different results depending on the number of bits. So in the very first code snippet with the loop body variable b seems to be of number data type:

var b:uint = 1 << 28;
trace(getQualifiedClassName(b)) //outputs Number

But because the first loop performs exactly the same as the 'int to int' or 'number to number' version, a reasonable answer would be that there is something wrong with getQualifiedClassName() instead of variable b being suddenly a number.

As a rule of thumb: Avoid mixing data types, always use signed integers for everything possible (e.g. counting variables, array access..), numbers if you need precision and unsigned integers only for ARGB color values. Avoid using uints for counting variables or arithmetic expressions.