AS3 Data Structures For Game Developers (AS3DS)

ds_logo.gif

Development of as3ds is discontinued.

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 be 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.

Trackbacks/Pingbacks

  1. [...] 3 Data Structures for Game Developers Michael Baczynski recently released a library of data structures targeting game development.  I’m already interested in the BST for some work in bone [...]

  2. [...] Development by Polygonal Labs May 15th, 2007 — drawk I have been waiting for this.  Polygonal labs released a pretty sweet package of core game development AS3 data structures (and other rich application development) tools that are common on other languages but not so in [...]

  3. [...] Top Clicks bubblemark.com/3d/wpfe.ht…labs.zeh.com.br/blog/?p=1…lab.polygonal.de/dsalex-uhlmann.de/flash/ani…channel9.msdn.com/playgro…mosessupposes.com/Fuselab.polygonal.de/wp-conte…lab.polygonal.de/2007/04/…codeproject.com/cs/media/…lab.polygonal.de/2007/05/… [...]

  4. [...] case you missed it Michael of Polygonal Labs has released a package of ActionScript 3.0 data structures that are especially dedicated for game development. He’s also writing examples on how some of [...]

  5. [...] Baczynski has published an AS3 framework ‘Data Structures’ especially for game development. This will be obviously also assistant for any performance [...]

  6. [...] AS3 Data Structures For Game Developers [...]

  7. [...] I came up with writing my own MultiMap class, so here it is! The MultiMap is heavily based on Michael Baczynski’s HashTable class but I modified it to my requirements and added a couple of additional methods for luxury. At first [...]

  8. [...] going through APE Physics engine by Alex Cove.  The tools so far by polygonal labs such as the AS3 Data Structures for Game Developers have been excellent and made it into many games and engine tests of mine and his blog is a really [...]

  9. [...] 作者一个月前就release了,呵呵,我总是那么的落后。。 项目页面:Data Structures SVN: http://code.google.com/p/as3ds/source Documentation: [...]

  10. [...] I’ve used Michael Baczynski’s ‘AS3 Data Structures For Game Developers’ to implement the Queue used in the Breadth-first search. Wish I’d run across this earlier. [...]

  11. [...] polygonal gibt es eine kleine Sammlung von AS3 Datenstrukturen, wie Binärer Baum, Vorrangwarteschlange, Hash-Tabelle und Co. Eine Doku gibt es hier. [...]

  12. [...] Yet another developer mentioned using linked lists when we were talking about arrays. He said that since object access in AS3 is faster than array access you can use a linked list like an array when performance is key. He also said there was an open source AS3 game developers library out there that implemented them…I’m thinking it’s “AS3 Data Structures For Game Developers“. [...]

  13. [...] for some month now. But after searching the web for some new algorithms in Flash I stumbled over AS3 Data Structures For Game Developers done by Michael Baczynski. Great piece of work which looks really professional. The package adds [...]

  14. [...] are also people developing games engines who need to perform such profiling sessions.The package “AS3 Data Structures For Game Developers” by Polygonal is an excellent reliable base to start build efficient games engines. As you can guess define and [...]

  15. [...] – open source 3D engines (such as Papervision 3D and Sandy), Physics engines (Fisix), specific data structures and even game creation [...]

  16. [...] che come librerie per la gestione delle strutture dati sto usando queste, sono uno spettacolo! : polygonal labs » Data Structures (ActionScript effettivamente deficita un po’ di librerie per data structure.. ) ho una classe [...]

  17. [...] WOW-Engine use and depend of the Data Structures classes written by polygonal labs. [...]

  18. [...] Jérôme Birembaut, aka Seraf, has released his WOW engine for 3D physics, based on Alec Cove’s APE (2D ActionScript Physics Engine). It apparently works with both Papervision and Sandy – Seraf seems to have been more inspired by Sandy’s architecture – and makes heavy use of polygonal labs’ AS3 data structures for game programming. [...]

  19. [...] engine, uses the Sandy library for all 3D math and incorporates data structures classes written by polygonal labs. It’s a very promising beginning. The future of Flash 3D programming and game development [...]

  20. [...] – open source 3D engines (such as Papervision 3D and Sandy), Physics engines (Fisix), specific data structures and even game creation [...]

  21. [...] AS3 Data Structures ‘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. [...]

  22. [...] Learn about data structures in programming and be a nerd like me. polygonal labs » Data Structures [...]

  23. [...] 昨天索性上網找了一堆Flex Component於是就看到了這個超讚的AS3 Class – AS3 Data Structures其實這個Class之前好像有在白大的部落格看到過不過當時沒有很仔細的去看官網上的一些文章今天大概的看了幾篇文章之後我決定po上來跟大家share一下這個好東西 這個AS3 Class真的非常實用他其實就是把資料結構中的許多演算法都已經實做出來了底層複雜的東西你都不用去管了只需知道怎麼用這些Class就好了對於常需要寫這些演算法的人來說真的很方便特別是開發Flash Gameçš„Programmer看完官網的幾篇文章範例之後發現自己在資料結構部份的基礎真的超弱的阿XD沒辦法~誰叫我自己要亂跨領域@@有時間再來慢慢研究Data Structures吧畢竟這種基礎的東西扎根夠深的話對於之後在寫程式時會很有幫助的像我之前在寫相關詞Map跟分群的東西時就有很深的感觸… [...]

  24. [...] something like a hash map. Actionscript 3 doesn’t have it. But some developers have made different versions. I am leaning towards this MultiMap Class [...]

  25. [...] something like a hash map. Actionscript 3 doesn’t have it. But some developers have made different versions. I am leaning towards this MultiMap Class [...]

  26. [...] of utilities come in handy. Another that comes to mind is Arthur Debert’s BulkLoader and polygonal labs Data Structures for Game Developers that are all great [...]

  27. [...] fiddling around with Mike Baczynski’s Data Structures for Game Developers (what benighted dabbler in Flash game programming hasn’t?), and have found a few things [...]

  28. [...] Librería de Estructuras de Datos que puedes utilizar en el desarrollo de tus juegos. Muy útil!… Lo mejor?… Esta bajo la licencia MIT (y para los que no sepan, eso es algo bueno). Para aquellos que no sepan lo que es una estructura de datos les recomiendo estudiar un poquito más cuestiones de programación: las estructuras de datos pueden salvar tu vida. Son manera de iterar en un arreglo de elementos, de organizar elementos en base a algún parámetro, de ordenarlos… Etc… Cuando estas trabajando en un juego con cientos de elementos en pantalla es bueno tener estructuras de datos que nos ayuden a controlarlos. :-) [...]

  29. [...] MultiMap is heavily based on Michael Baczynski’s HashTable class but I modified it to my requirements and added a couple of additional methods for luxury. At first [...]

  30. [...] whereever we needed datastructures, we’ve been using the great opensource package from Michael Baczynksy at polygonal.de for the use of lists, queues, stacks and trees . While it works great, it has some explicit design [...]

  31. [...] hacks like tellTarget are finally gone. Pixel level manipulation is possible and even faster. Real frameworks, excellent structured animation kits and even 3d engines are being built everyday. And invisible [...]

  32. [...] The BinaryCA class is an independent class to manage 2D CAs. To store the CA cells I based the core on the Array2 class from polygonal labs’ AS3DS data structures library. [...]

  33. [...] WOW-Engine use and depend of the Data Structures classes written by polygonal labs. [...]

  34. [...] here. In the before-engine version of our core base, this was filled with a re-packaged version of Polygonal Labs Data Structures for Game Developers. I decided to restart the work here to keep code standards equal throughout the [...]

  35. [...] I ramble, be sure to check out Data Structures for Game Developers by Polygonal Labs now ported for haXe as hx3ds if you are doing any sort of work in AS3 or haXe for AS3 it will be [...]

  36. [...] ???? AS3????????2007??????? Related PostsNo related posts [...]

  37. [...] AS3 Data Structures For Game Developers The first choice (and best source) when it comes to bare algorithms and speed optimised data structures. Apparently the widest acceptance of all libraries. More a losely coupled set of distinctive implementations than a framework (doesn’t claim do be one). Provided and maintained by the German Michael Baczynski. http://lab.polygonal.de/ds/ [...]

  38. [...] as3ds – AS3 Data Structures: Site no Google Code: http://code.google.com/p/as3ds/ Blog da equipe: http://lab.polygonal.de/ds/ [...]

  39. [...] at this point: I’m using Flex’s Grid control to hold my actual data — in the end I will be using a Multi-Dimensional Array provided by the good folks over at Polygonal Labs. I also need to remove any UI interaction from [...]

  40. [...] case you missed it Michael of Polygonal Labs has released a package of ActionScript 3.0 data structures that are especially dedicated for game development. He’s also writing examples on how some of [...]

  41. [...] UPDATE 3.06.2007 — AS3 Data Structures For Game Developers is a package containing common data structures useful for game programming and application [...]

  42. [...] Data Structures :AS 3 – Datenstruktur Bibliothek [...]

  43. [...] einige interessante Projekte entstanden, wie Z.B. PaperVision3D, Fisix Engine, APE, wiiFlash und AS3 Data Structures in denen einiges an KnowHow, viel Arbeit und vor allem Potenzial für Flash Game Entwickler steckt. [...]

  44. [...] — Nothing like a geek who speak in algorithms.http://lab.polygonal.de/ds/ — A geek with Flash on the brain. Has a nifty little “Data Structures” package for [...]

  45. [...] AS 3 Data Structures für Game-Developer [...]

  46. [...] décidé d’utiliser le MemoryManager du projet hx3ds la version haXe du projet AS3DS API de structure de données fortement [...]

  47. [...] I found: AS3 Data Structures For Game Developers by Michael Baczynski. Thanks Michael! This library includes Hash Maps, Queues, Trees, and Stacks [...]

  48. [...] websites, looks good! as3corelib – encryption, picture formats and some networking classes.. as3 data structures – for game devs as3FlexUnitLib – It’s like JUnit but for flex. FlUint – [...]

  49. [...] AS Data Structures for Game Developers [...]

  50. [...] Struktury danych Collision Detection Spatial hashing [...]

  51. [...] Labs Data Structures – http://lab.polygonal.de/ds/ A great set of utility classes that build extra functionality on top of the existing core [...]

  52. [...] of my favorite data structures that  enables me to avoid conditional logic are linked lists. Michael has some great data objects; however, his implementation is a little overkill for many of the [...]

  53. [...] http://lab.polygonal.de/ds/ (Basic [yet advanced compared to what ships with flash] datastructures like BSTs, Heap, Stack, Queue, etc) http://www.a-z-dictionaries.com/Open_Source_Dictionary_Gutenberg.html (Suprising amount of open source dictionaries) [...]

  54. [...] Data Structures For Game Developers ???Polygonal Labs ???http://lab.polygonal.de/ds/ ???MIT License ???AS3 DATA [...]

  55. [...]    http://lab.polygonal.de/ds/ [...]

  56. [...] WOW-Engine use and depend of the Data Structures classes written by polygonal labs. [...]

  57. [...] dev links In computerz, game dev, link, links, words on September 18, 2007 at 7:03 am as3 data structures for game developers [...]

  58. [...] Polygonal datastructures Version 1.04 The ActionScript version of the polygonal data structures is not further developed and has been ported to the haXe language with the claim to be faster. However, some of the haXe structures did not support primitive values (Heap, BST), so I test here the last ActionScript version. [...]

  59. [...] Experiment source here. Dependencies TweenMax AS3 and Polygonal Labs Data Structures. [...]

  60. Flash ???? says:

    [...] in Flash at Devnet. http://www.adobe.com/devnet/facebook Other Useful ActionScript Libraries AS3 Data Structures For Game Developers (AS3DS) – lot of useful structures for general game development BaseUI Layouting like in Flex, but [...]

  61. [...] AS3 Data Structures For Game Developers (AS3DS) – ?????????? [...]

  62. [...] ?????? ???????????????????? ??????????????????DListNode??????????????polygonal???????????????????????????????????????????????? [...]

  63. [...] z-coordinates. Lets help it a bit with linked lists (double linked lists). I have used merge and insertion sort methods, both are very fast (merge is faster for unsorted lists, insertion for [...]

  64. [...] (bredth-first search) on Trie and we need a Queue data structure for this. I used the queue from AS3DS package from PolygonLabs (“q” [...]

Leave a Comment



Get Adobe Flash player