Doubly linked list and object pooling

AS3, Data Structures, Entity/Component System, Games, Object Pooling, Programming, , , , , , , ,

After holidays, it’s time to get back to work 🙂
I was really busy last month, so this is some news on what I did and what is going on :

– I’ve made some experiments with the Citrus Engine on the Hero adding some functionality. But what appears is the Hero class becomes more and more complex… So I asked its creator if he knows a system/model which has a modular way to add features to the hero. And he gives me some information about the Entity/Component model. Woah, it is awesome! It’s really a new way of thinking about programming. No more OOP. This is 3 useful links/resources if you are interested : Gamasutra the Entity Component Model, Entity Systems are the future of MMOG development, Entity Systems. This links are very interesting, but there isn’t any implementation. You can find implementations with the PushButton Engine (flash), Artemis (java). However it is really complex, so I was not able to create a Component/Entity System for the CE due to my lack of experience… but if its creator has time, he will do!

– I was in holidays at Praha (Czech Republic), amazing city/country! And beer is really cheap 🙂

– I’m currently reading the book of Jesse Schell, The Art of Game Design it’s a masterpiece! Really, really interesting, lots of awesome advices. Approved & Recommended!

– I’m working/designing my next portfolio. It will be nice… 😉

– On Thursday 15 September, I go back to the Gobelins school! And I will make a point with Tiffany about Kinessia. We are thinking to create the game for mobile. I hope we will have enough time (there are already lots of project at school…), so stay tuned!

– Mobile, tablet and game design/programming is interesting me more and even more. This is two good links on mobile game programming : Starting with AIR for Android and iOS – building one app for both platforms, and Building mobile games in Adobe AIR – optimization techniques.

– And finally I’m also waiting FDT5 to invest more time in haXe and WebGL!

I think it’s enough for the news at the moment! Now it’s time to speak about the topic, this week I wanted to make some algorithms, doubly linked list and object pooling are a good exercice. Previously I made an oral in my school to introduce recurisivity and data structures (pdf link in french). Doubly linked list and object pooling are techniques optimizations used in game development and especially on mobile devices.

A Linked List is a data structure consisting of a group of nodes which together represent a sequence. Each node is composed of a data and a reference (a link) to the next node in the sequence. Whereas we use index to access a specific element in an array (myArray[2]), we are blind in a linked list. We know the first and the last element, that’s all. If we want to access to the 3 element, we need to go through our linked list and stop on the element : head.next.next.data
This is simple function to do that :

var count:uint = 1;
var tmpHead:Node = head;
 
while (count < 3) {
	tmpHead = tmpHead.next;
	++count;
}
 
return tmpHead.data;

So what are the interests of the linked list? Why we should use them?
If we have only some elements, we shouldn’t use a linked list. Yet if we have many elements and make many operations (add/remove in head or tail) on them, we should use one. Indeed when we use the unshift method in an array (to add an element to the beginning of the array), each index are moved. If we have an array with 5 000 000 elements and we add/remove first elements in an EnterFrame (so 30 times by second), we imagine easily the performance problem. With a linked list you just add/remove an element without moving all index!
More informations on wikipedia.

Let’s start coding, this is my implementation of a doubly linked list and a node :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

package alamboley.datastructures {
 
	/**
	 * @author Aymeric
	 */
	public class DoublyLinkedListNode {
 
		public var data:*;
		public var next:DoublyLinkedListNode;
		public var prev:DoublyLinkedListNode;
 
		/**
		 * A simple data node used for DoubleLinkedList and Pool
		 * @param obj untyped data stored in the node
		 */
		public function DoublyLinkedListNode(obj:* = null) {
 
			next = prev = null;
			data = obj;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205

package alamboley.datastructures {
 
	/**
	 * @author Aymeric
	 */
	public class DoublyLinkedList {
 
		public var head:DoublyLinkedListNode;
		public var tail:DoublyLinkedListNode;
 
		protected var _count:uint;
 
		public function DoublyLinkedList() {
 
			head = tail = null;
			_count = 0;
		}
 
		/**
		 * Append an object to the list.
		 * @param data an object of any type added at the end of the list.
		 * @return returns the tail.
		 */
		public function append(data:*):DoublyLinkedListNode {
 
			var node:DoublyLinkedListNode = new DoublyLinkedListNode(data);
 
			if (tail != null) {
 
				tail.next = node;
				node.prev = tail;
				tail = node;
 
			} else {
				head = tail = node;
			}
 
			++_count;
 
			return tail;
		}
 
		/**
		 * Append a node to the list.
		 * @param node a DoubleLinkedListNode object of any type added at the end of the list.
		 * @return returns the doubleLinkedList.
		 */
		public function appendNode(node:DoublyLinkedListNode):DoublyLinkedList {
 
			if (head != null) {
 
				tail.next = node;
				node.prev = tail;
				tail = node;
 
			} else {
				head = tail = node;
			}
 
 
			++_count;
 
			return this;
		}
 
		/**
		 * Prepend an object to the list.
		 * @param data an object of any type added at the beginning of the list.
		 * @return returns the head.
		 */
		public function prepend(data:*):DoublyLinkedListNode {
 
			var node:DoublyLinkedListNode = new DoublyLinkedListNode(data);
 
			if (head != null) {
 
				head.prev = node;
				node.next = head;
				head = node;
 
			} else {
				head = tail = node;
			}
 
			++_count;
 
			return head;
		}
 
		/**
		 * Prepend a node to the list.
		 * @param data an object of any type added at the beginning of the list.
		 * @return returns the doubleLinkedList.
		 */
		public function prependNode(node:DoublyLinkedListNode):DoublyLinkedList {
 
			if (head != null) {
 
				head.prev = node;
				node.next = head;
				head = node;
 
			} else {
				head = tail = node;
			}
 
			++_count;
 
			return this;
		}
 
		/**
		 * Remove a node from the list and return its data.
		 * @param node the node to remove from the list.
		 * @return returns the removed node data.
		 */
 
		public function removeNode(node:DoublyLinkedListNode):* {
 
			var data:* = node.data;
 
			if (node == head) {
 
				removeHead();
 
			} else {
				node.prev.next = node.next;
			}
 
			if (node == tail) {
 
				removeTail();
 
			} else {
				node.next.prev = node.prev;
			}
 
			--_count;
 
			return data;
 
		}
 
		public function removeHead():* {
 
			var node:DoublyLinkedListNode = head;
 
			if (head != null) {
 
				var data:* = node.data;
 
				head = head.next;
 
				if (head != null) {
					head.prev = null ;
				}
 
				--_count;
 
				return data;
			}
		}
 
		public function removeTail():* {
 
			var node:DoublyLinkedListNode = tail;
 
			if (tail != null) {
 
				var data:* = node.data;
 
				tail = tail.prev;
 
				if (tail != null) {
					tail.next = null;
				}
 
				--_count;
 
				return data;
			}
		}
 
		/**
		 * Get the lengh of the list.
		 * @return the list length.
		 */
		public function get length():uint {
			return _count;
		}
 
		public function content():String {
 
			var tmpHead:DoublyLinkedListNode = head;
			var text:String = '';
 
			while (tmpHead != null) {
				text += String(tmpHead.data) + " ";
				tmpHead = tmpHead.next;
			}
 
			return text;
		}
	}
}

Now an application usage :

var doublyLinkedList:DoublyLinkedList = new DoublyLinkedList();
var node:DoublyLinkedListNode = new DoublyLinkedListNode(6);
doublyLinkedList.append(2);
doublyLinkedList.prepend(5);
doublyLinkedList.append(7);
doublyLinkedList.appendNode(node);
trace(doublyLinkedList.content());
 
doublyLinkedList.removeNode(node);
doublyLinkedList.append(9);
 
trace(doublyLinkedList.content());

The first output is : 5 2 7 6
And the second : 5 2 7 9
Easy to use, isn’t it ?

Now let’s move on the second part : object pooling.
Object pooling is a datastructure based on a simple observation : the ‘new’ operator is costly, memory allocation necessary for the object creation is a slow process. And Garbage Collection too! So object pooling idea is really simple :
– create lots of object at the beginning of your level, if there is FPS reduction it shouldn’t be a big problem.
– if you need more objects during the game create many of them that can be use later.
– destroy your object if you don’t need it anymore, but keep a link to it! So it will be reassign!
– destroy all your objects and set them to null at the end of your level (garbage collector will work).

That was for theorical advices, now more practical :
– object pooling is often a linked list and objects are in node data.
– never add params to your constructor! Add params to a init function. Indeed when you reassign an element, you don’t use the constructor but your init function.
– create a destroy function to clear your object.

So this is an implementation based on the works of Alkemi (their turoials on blitting is really interesting). I added some functionality. Most of the time, we don’t find object pooling implementation with graphics resources. I offer one at the end 😉
The PooledSprite class :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187

package alamboley.datastructures {
 
	/**
	 * @author Aymeric based on the works of Alkemi (Mickael Mouillé & Alain Puget) www.alkemi-games.com 
	 */
	public class PooledSprite extends DoublyLinkedList {
 
		protected var _poolType:Class;
		protected var _poolSize:uint = 0;
		protected var _poolGrowthRate:uint = 0;
 
		// Start of the list of free objects
		protected var _freeListHead:DoublyLinkedListNode = null;
 
		/**
		 * An implementation of an object Pool to limit instantiation for better performances.
		 * Though you pass the Class as a parameter at the pool creation, there's no way for it to send you back your object correctly typed
		 * If you want that, reimplement the Pool class and the DoublyLinkedListNode for each of your pool or port these files to Haxe with Generics !
		 * WARNING : Be sure to design your pooled objects with NO constructor parameters and an 'init' method of some kind that will reinitialized 
		 * all necessary properties each time your objects are 'recycled'.
		 * WARNING : Remember to cast your objects in the correct type before using them each time you get on from a DoublyLinkedListNode.data !!!
		 * 
		 * @param $pooledType the Class Object of the type you want to store in this pool
		 * @param $poolSize the initial size of your pool. Ideally you should never have to use more than this number.
		 * @param $poolGrowthRate the number of object to instantiate each time a new one is needed and the free list is empty
		 */
		public function PooledSprite($pooledType:Class, $poolSize:uint, $poolGrowthRate:uint):void {
 
			super();
 
			_poolType = $pooledType;
			_poolSize = $poolSize;
			_poolGrowthRate = $poolGrowthRate;
 
			increasePoolSize(_poolSize);
 
		}
 
		/**
		 * Create new objects of the _poolType type and store them in the free list for future needs.
		 * Called once at the pool creation with _poolSize as a parameter, and once with _poolGrowthRate
		 * each time a new Object is needed and the free list is empty.
		 * 
		 * @param	$sizeIncrease the number of objects to instantiate and store in the free list
		 */
		protected function increasePoolSize($sizeIncrease:uint):void {
 
			for (var i:int = 0; i < $sizeIncrease; ++i) {
				var node:DoublyLinkedListNode = new DoublyLinkedListNode();
				node.data = new _poolType();
 
				if (_freeListHead) {
					_freeListHead.prev = node;
					node.next = _freeListHead;
					_freeListHead = node;
				} else {
					_freeListHead = node;
				}
 
			}
 
		}
 
		/** Get an object from the free list and returns the node holding it in its data property
		 * Don't forget to cast and reinitialize it !!!
		 * @return a node holding the newly 'recycled' object
		 */
		public  function create(bigCircleRadius:uint):DoublyLinkedListNode {
			var node:DoublyLinkedListNode;
 
			// if no object is available in the freelist, make some more !
			if (!_freeListHead) increasePoolSize(_poolGrowthRate);
 
			// get the first free object
			node = _freeListHead;
 
			// extract it from the free list
			if (node.next) {
				_freeListHead = node.next;
				_freeListHead.prev = null;
				node.next = null;
			} else
				_freeListHead = null;
 
 
			// append it to the list of the pool
			if (head != null) {
				tail.next = node;
				node.prev = tail;
				tail = node;
			} else
				head = tail = node;
 
			(node.data as _poolType).init(bigCircleRadius);
 
			++_count;
 
			return node;
		}
 
		public function update(...params):void {
 
			var tmpHead:DoublyLinkedListNode = head;
 
			while (tmpHead != null) {
				(tmpHead.data as _poolType).update(params[0]);
				tmpHead = tmpHead.next;
			}
 
		}
 
		/**
		 * Discard a now useless object to be stored in the free list.
		 * @param	$node the node holding the object to discard
		 */
		protected function _dispose($node:DoublyLinkedListNode):void {
			// Extract the node from the list
			if ($node == head) {
				head = $node.next;
				if (head != null) head.prev = null;
			} else {
				$node.prev.next = $node.next;
			}
 
			if ($node == tail) {
				tail = $node.prev;
				if (tail != null) tail.next = null;
			} else {
				$node.next.prev = $node.prev;
			}
 
 
			$node.prev = null;
 
 
			// Store the discarded object in the free list
			if (_freeListHead) {
				_freeListHead.prev = $node;
				$node.next = _freeListHead;
				_freeListHead = $node;
			} else {
				_freeListHead = $node;
				$node.next = null;
			}
 
			--_count;
 
		}
 
		public function disposeGraphicObject(node:DoublyLinkedListNode):DoublyLinkedListNode {
 
			(node.data as _poolType).destroy();
 
			_dispose(node);
 
			return node;
		}
 
		/**
		 * Discard all currently used objects and send them all back to the free list
		 */
		public function disposeAll():void {
			while (head) {
				disposeGraphicObject(head);
			}
		}
 
		/**
		 * Completely destroy all the content of the pool
		 */
		public function clear():void {
			disposeAll();
 
			var node:DoublyLinkedListNode;
 
			while (_freeListHead) {
				node = _freeListHead;
				node.data = null;
				_freeListHead = node.next;
				if (_freeListHead) _freeListHead.prev = null;
				node.next = null;
			}
 
		}
 
	}
}

It is well commented, it shouldn’t be too hard to understand. Now a simple class to add point on a circle. There is some nice mathematical function :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

package {
 
	import flash.display.Shape;
 
	/**
	 * @author Aymeric
	 */
	public class PointCircle extends Shape {
 
		private var _radius:uint;
 
		public function PointCircle() {
		}
 
		public function init(radius:uint = 2):void {
 
			_radius = radius;
		}
 
		public function update(bigCircleRadius:uint):void {
 
			graphics.clear();
			graphics.beginFill(Math.random() * 0xFFFFFF);
			graphics.drawCircle(0, 0, _radius);
			graphics.endFill();
 
			var theta:Number = Math.random() * 360;
			var phi:Number = Math.random() * 90;
 
			x = bigCircleRadius * Math.cos(phi) * Math.cos(theta);
			y = bigCircleRadius * Math.cos(phi) * Math.sin(theta);
			z = bigCircleRadius * Math.sin(phi);
		}
 
		public function destroy():void {
 
			graphics.clear();
		}
 
	}
}

Notice that there is nothing in the constructor method! If we just init this object, it will not be visible. The update method makes it visible. It depends on your need, that’s not a big deal.

And finally my main class :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

package {
 
	import alamboley.datastructures.DoublyLinkedList;
	import alamboley.datastructures.DoublyLinkedListNode;
	import alamboley.datastructures.PooledSprite;
	import alamboley.utils.FPSMemCounter;
 
	import flash.display.Sprite;
	import flash.events.Event;
	import flash.events.MouseEvent;
	import flash.text.TextField;
 
 
	[SWF(backgroundColor="#000000", frameRate="24", width="600", height="500")]
 
	/**
	 * @author Aymeric
	 */
	public class Main extends Sprite {
 
		private const _INIT_OBJECTS:uint = 500;
		private const _BIG_CIRCLE_RADIUS:uint = 200;
		private const _CIRCLE_RADIUS:uint = 2;
 
		private var _container:Sprite;
		private var _pool:PooledSprite;
		private var _tf:TextField;
 
		private var _radius:uint = 200;
		private var _radiusIncrease:Boolean = false;
 
		public function Main() {
 
			FPSMemCounter.init(stage, this, true);
 
			_container = new Sprite();
 
			addChild(_container);
			_container.x = stage.stageWidth * 0.5;
			_container.y = stage.stageHeight * 0.5;
 
			_initButtons();
 
			stage.addEventListener(Event.ENTER_FRAME, _ef);
 
			_pool = new PooledSprite(PointCircle, _INIT_OBJECTS, 50);
 
			var i:uint = 0;
			for (i = 0; i < _INIT_OBJECTS; ++i) {
				trace('Creating Point ', _pool.length);
				_container.addChild(_pool.create(_CIRCLE_RADIUS).data);
			}
 
			_tf.text = String(_pool.length) + " objects";
		}
 
		private function _ef(evt:Event):void {
 
			if (_radiusIncrease == true) {
 
				++_radius;
				if (_radius > _BIG_CIRCLE_RADIUS) {
					_radiusIncrease = false;
				}
 
			} else {
 
				--_radius;
				if (_radius < 25) {
					_radiusIncrease = true;
				}
 
			}
 
			_pool.update(_radius);
		}
 
		private function _removeObjects(mEvt:MouseEvent):void {
 
			if (_pool.length > 50) {
				var i:uint = 0;
				for ( i = 0; i < 50; ++i ) {
					trace('Disposing Point', _pool.length);
					_container.removeChild(_pool.disposeGraphicObject(_pool.tail).data);
				}
				_tf.text = String(_pool.length) + " objects";
			}
		}
 
		private function _addObjects(mEvt:MouseEvent):void {
 
			var i:uint = 0;
			for (i = 0; i < 50; ++i) {
				trace('Creating Point ', _pool.length);
				_container.addChild(_pool.create(_CIRCLE_RADIUS).data);
			}
			_tf.text = String(_pool.length) + " objects";
		}
 
		private function _initButtons():void {
 
			var addObject:Sprite = new Sprite();
			addObject.graphics.beginFill(0x0000FF);
			addObject.graphics.drawRect(0, 0, 75, 30);
			addObject.graphics.endFill();
			addObject.x = 500;
			addObject.y = 380;
			addChild(addObject);
			addObject.buttonMode = true;
			addObject.addEventListener(MouseEvent.CLICK, _addObjects);
 
			var addObjectText:TextField = new TextField();
			addObjectText.selectable = false;
			addObjectText.mouseEnabled = false;
			addObjectText.textColor = 0x00FF00;
			addObject.addChild(addObjectText);
			addObjectText.text = "Add 50 objects";
			addObjectText.y = 10;
 
			var removeObject:Sprite = new Sprite();
			removeObject.graphics.beginFill(0xFF0000);
			removeObject.graphics.drawRect(0, 0, 75, 30);
			removeObject.graphics.endFill();
			removeObject.x = 500;
			removeObject.y = 430;
			addChild(removeObject);
			removeObject.buttonMode = true;
			removeObject.addEventListener(MouseEvent.CLICK, _removeObjects);
 
			var removeObjectText:TextField = new TextField();
			removeObjectText.selectable = false;
			removeObjectText.mouseEnabled = false;
			removeObjectText.textColor = 0x00FF00;
			removeObject.addChild(removeObjectText);
			removeObjectText.text = "Remove 50";
			removeObjectText.y = 10;
 
			_tf = new TextField();
			_tf.selectable = false;
			_tf.mouseEnabled = false;
			_tf.x = 30;
			_tf.y = 450;
			_tf.textColor = 0x00FF00;
			addChild(_tf);
		}
	}
}

If you have read all, congratulations! Now you can see my experiment with doubly linked list and object pooling : a Sphere.
My zip.

4 thoughts on “Doubly linked list and object pooling”

  2. Pingback: Rugby game, AS3 – CE – haXe versions :Aymeric Lamboley
  3. Pingback: CitrusEngine goes Stage3D with Starling :Aymeric Lamboley
  4. Pingback: Aymeric Lamboley » An entity/component system’s attempt using Box2D

Leave a Reply

Your email address will not be published. Required fields are marked *