AS3 Data Structures For Game Developers

source : http://lab.polygonal.de/ds/

svn: http://as3ds.googlecode.com/svn/trunk/ as3ds

Description

‘AS3 Data Structures For Game Developers’ is a package containing common data structures useful for flash game programming and application development. The project was started because I wanted a unified library which I could reuse in my games.
Design Decisions

I have tried to provide just the bare algorithms, coupled with a minimum set of methods I think are most useful to work with. Simplicity and performance were the key guidelines for the whole package. Therefore,

- all structures are untyped and can be fed with any kind of data. This makes usage more flexible and simple, since you don’t have to create special container classes which extend base classes and/or implement interfaces.

- I’m often not following strict design patterns and OOP-practices. For example, to access a classes’ property, I just define it as public instead of writing functions to read/write the property (which is also faster).

- all classes reside in a single package, simply because its hard to separate them - e.g. a linked list can bee seen as a tree, and a tree on the other side is a loose linked list.

- many structures use custom code rather that utilizing the data structure classes themselves - for example the graph structure could be implemented by using the linked list and queue classes, but a plain array works faster behind the scenes.
Collections

Almost all classes implement the Collection interface, which defines the following methods:

contains(obj:*), for checking if an item exists
clear(), for removing all items
getIterator(), for creating an iterator object to step through all items
size, the total number of items and
toArray(), which simply converts the structure into an array.
Using Iterators

Every class that implements the Collection interface is also able to create an iterator object using the getIterator() method. Once you have an iterator, you can walk through the data and read/write the values like so:

var myItr:Iterator = getIterator();
var value:*;

//read all values
while (myItr.hasNext())
{
value = myItr.next();
}

//write new value
myItr.start();
while (myItr.hasNext())
{
myItr.data = "newValue";
next();
}

//the same with a for loop
for (myItr.start(); myItr.hasNext(); myItr.next())
{
value = myItr.data;
}

Keep in mind that an iterator implies no order in which the items are processed. Some classes also support a more complex iterator like the linked list or the tree. This is necessary because you can iterate in more directions (forth, back, up, down..). You get those iterators by performing a downcast or simply calling a special method:

var listItr:ListIterator = myLinkedList.getIterator() as ListIterator;
var listItr:ListIterator = myLinkedList.getListIterator();

The Structures
Multi-Dimensional Arrays

The library contains a two-dimensional and three-dimensional array. They are both implemented by a single linear array rather than nested arrays. This is the fastest method in flash to simulate multi-dimensional arrays and outperforms the nested array method because multiple array lookups are slower compared to one lookup combined with a simple arithmetic expression (which you can also often precompute in the outer loop). The most obvious application would be a tilemap in 2d or a layered tilemap in 3d.
Queue

This is also called a FIFO structure (First In - First Out). The queue comes in two variations, which have the same methods, but differ in their implementations: There is the arrayed queue, which obviously uses an array internally, and the linked queue, which is build upon a linked list. They are both very similar, except that the arrayed version has a fixed size and is faster.
A common application would be a command queue - imagine you have a unit in a strategy game and apply many commands which the unit should follow. All commands are enqueued and afterwards dequeued and processed in order.
Stack

Also commonly know as a FILO structure (First In - Last Out). Like the queue, this comes in two flavors: arrayed and linked. A stack is often not used directly, but a very important concept in programming. Please note, that a queue and a stack are not real structures, because they just define how data is accessed rather then stored.
Tree

A node-based structure. Every tree starts from a single node, called the root node. The root node can contain any number of child nodes, and every child node can again contain children. A tree node with no children is called a leaf node. In fact if you draw the nodes of a tree it looking like a real tree with branches. The AS3 display architecture is also a tree structure, so you could use this to manage your display objects and update them by traversing through the tree. Also, this is useful for decision trees, BVHs, storing a plot line or storing data recursively by applying the composite pattern.
Binary Tree

This is just a specialized kind of tree where each node is only allowed to have up to two children, called the left and right node. Binary trees are very often used for parsing input data, for example arithmetic expressions or when building a scripting system.
Binary Search Tree (BST) and Hash Table

Both structures store data that can be retrieved quickly by using a key. The method however differers greatly: The BST uses a recursive approach to split up large amounts of data into smaller sets. A hash table stores sparse key-based data using a hash-key in a small amount of space.
Linked Lists

A linked list is similar to an array. The main difference is that in an array, each cell contains just the data and is accessed by an index. A linked list consists of several node objects, which in addition to storing the data, manage a reference to the next node (singly linked) or to the next and previous node (doubly linked) in the list. Think of it as a more natural approach to work with sequential data.
Other benefits are that you can insert and remove data quickly by just calling the appropriate method on the node itself - you don’t have to manage array indexes. Also in AS3 object access is faster than array access, so it competes very well in terms of performance when iterating over the list.
Heap and Priority Queue

A Heap is a special kind of binary tree in which every node is bigger than its child nodes. Whatever you throw into a heap, it’s automatically sorted so the item with the ‘most significant’ value (depending on the comparison function) is always the front item. A priority queue is build upon the heap structure, and can manage prioritized data - which can be used in limitless ways.
Graph

A graph is a loose node-based structure. Nodes are connected with arcs, and every node can point to any other node. They can also point to each other creating a bi-directional connection. It is essential for path finding, AI, soft-body dynamics with mass-springs systems and a lot more.
Bit Vector

A bit vector is some kind of array in which you can store boolean values (true/false - 1/0) as close as possible without wasting memory. I currently can’t think of a reasonable application, because usually you should have enough memory - but it’s nice to have because it shows basic bit masking operations.