Tag Archives: optimization

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.

Continue reading Doubly linked list and object pooling →

Greedy algorithm

Programming, ,

According to Wikipedia, a greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding the global optimum. In general, greedy algorithms are used for optimization problems.

An example of a Greedy algorithm is a charging machine. Assume that it give you your change with € currency, you will have coin of : 200, 100, 50, 20, 10, 5, 2, 1. Your change will be really easy to calculate with a greedy algorithm :

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

var moneySystem:Array = [200, 100, 50, 20, 10, 5, 2, 1];
var giveBack:uint = 263;
var solution:Array = [];
 
trace(greedyMethod(moneySystem, giveBack, solution));
 
function greedyMethod($moneySystem:Array, $giveBack:uint, $solution:Array):Array {
 
	if ($giveBack == 0) {
		return $solution;
	}
 
	while ($giveBack >= $moneySystem[0]) {
		$giveBack -= $moneySystem[0];
		$solution.push($moneySystem[0]);
	}
 
	$moneySystem.shift();
 
	return greedyMethod($moneySystem, $giveBack, $solution);
}

For 263, the algorithm will output : 200,50,10,2,1. It is the best solution. Thanks to the € currency, greedy algorithm will always give the best results.
However if we have an other money with only 4, 3, 1 coins and the change is 6 the greedy algorithm outputs 4, 1, 1 instead of 3, 3. That’s a fail !

Another typical example is the knapsack problem : given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
According that our values are sorted in decreasing order we have :

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

var objects:Array = [["A", 12, 10], ["B", 10, 7], ["C", 8, 5], ["D", 7, 4], 
		 ["E", 7, 4],  ["F", 6, 4], ["G", 5, 2], ["H", 4, 2],
		 ["I", 4, 1], ["J", 3, 2], ["K", 3, 2], ["L", 3, 1],
		 ["M", 2, 2], ["N", 1, 1]];
var totalWeight:uint = 25;
 
trace(knapSack(totalWeight, objects));
 
function knapSack($totalWeight:uint, $objects:Array):Array {
 
	var currentWeight:uint = 0;
	var subSet:Array = [];
 
	for (var counter:uint;counter< $objects.length; ++counter) {
 
		if (currentWeight + $objects[counter][2] <= $totalWeight) {
			currentWeight += $objects[counter][2];
			subSet.push($objects[counter]);
		}
	}
 
    return subSet;
}

The output is [A,12,10],[B,10,7],[C,8,5],[G,5,2],[I,4,1]. It’s ok, but we aren’t sure that it is the best result. The problem with a greedy algorith : it will always try to select the first parameter even if it is not the better.
For instance, our max weight is 40, our objects are [“A”, 30, 39], [“B”, 12, 10], [“C”, 12, 10], [“D”, 12, 10], [“E”, 12, 10],[“F”, 4, 1]. The greedy algorithm choose A and F for a value of 34 whereas B, C, D, E is obviously the best value : 48. That’s an other example where it fails.

So to conclude greedy algorithms depends of datas if they are balanced or not. More data are balanced, more it will be powerful. For a perfect result, you can use dynamic programming method. It is more complex and requires more resources. So it’s up to us to find the best solution for our problem.