QuickSort

The next algorithm the course required us to implement is QuickSort. QuickSort is quite a well known algorithm and, theoretically speaking, it performs as good as Merge Sort ( O(n log n) time ). In practice however, it usually comes out faster. Choosing the pivot well is essential to a good running time.
Here is my implementation, with the pivot choosing subroutine left out:



In my next post I will show how we can choose a good pivot and how much it matters.

Selection Sort

I decided to throw another sorting algorithm into the mix: Selection Sort.
In theory, this one should be the worst of all.
In practice, it turned out a little bit different:


Create a graph
This was my implementation:

When we analyze these algorithms mathematically, we can conclude that:

• Merge Sort runs in O(n log n) time.
• Both selection and insertion sort run in O(n²) time.

As you can see, this makes a huge difference when amount of data increases.

Insertion Sort

In order to understand just how important a good sorting algorithm is, I quickly whipped up an Insertion Sort:

I applied both of them on a list of 100,000 numbers. This was the result, in seconds:
Graphing

Merge Sort

The first programming challenge the course over at Coursera provided us with was to implement an algortihm for counting the inverions in an array. As it turns out, this can be achieved by applying a minor modification in the Merge Sort algorithm. I implemented it both in C++ and Python.
Python version C++ version I'll leave the method to calculate the inversions as an exercise for the reader, it's really not that difficult.

Coursera

The finals are finally over! I'm so happy I can get back to work on my projects. As I mentioned in my last post I'll be revealing my latest project soon, on this blog. I'm also taking up a free course offered by Stanford University on Coursera. the "Design and Analysis of Algorithms" course will undoubtedly sharpen my skills regarding algorithms and will make me a better programmer in general. You can still sign up now!

Decreased activity

Since exams are coming up, I won't have much time to blog anymore. I'm working on something entirely different than what I usual make (games ^^) in collaboration with a friend who'll take the financial side of things on his shoulders. All will be revealed when the time is right!

Nodes!

The latest revision of SFGE introduces two new classes: Node and CollidableNode.
The idea is that a Node can have child nodes, which on their turn can have even more child nodes an so on.
The interface of the Node class:

 namespace sfge  
 {  
   class Node  
   {  
     public:  
       Node(const std::string& name = "Node");  
       virtual ~Node();  
   
       std::string getName();  
   
       void draw(sf::RenderTarget& target);  
       void update(sf::Time delta);  
   
       void addNode(Node* node);  
       void removeNode(Node* node);  
   
       Node* getParent();  
       void setParent(Node* parentnode);  
   
     protected:  
       virtual void onDraw(sf::RenderTarget& target){}  
       virtual void onUpdate(sf::Time delta){}  
       Node* parent;  
       std::vector<Node*> children;  
       std::string name;  
   };  
 }  

When the draw function is called, the Node draws itself as well as all his children. Same holds for the update function. onDraw and onUpdate draw and update the current node.
ConvexCollidable has been changed to CollidableNode (derives from Node) and the AABB classes have been removed.

Previous projects

Before I started this blog I had already completed quite a few projects. I made them available on this blog through static pages (see top of page). Every project I'll complete will get it's own page next to them.
Here is a small overview of my past projects:

• X-Break
  First game I ever got to finish. It's a breakout clone boasting new graphics and some more features.
   
• Chest Crusher
  This game was the result of me diving into Box2D (a physics library). Due to my outstanding creativity it ended up like an Angry Birds clone. Not a literal clone, but the core gameplay is the same as in Angry Birds.
   
• Damn Asteroids!
  My first game made in a language other than C++: Python! I used  the Cocos2D framework (which is built on top of Pyglet). This allowed for insanely fast development, the game was completed in less than a week.
   

Spatial Hashing for improving performance

The current implementation of my CollisionDetector class in SFGE uses a brute-force algorithm. It simply iterates through all objects it's holding and checks for collision with all other objects (however, no two objects are ever checked twice against each other). At first, I thought this wouldn't give me much trouble because, you know, C++ is fast right? Obviously, I ran into trouble when I used the class for collision detection in my platformer game. The implementation runs in O(n²/2) time. Say, we have a game with 10 cars that can collide with each other. The amount of checks needed in my current implemenation would be 50. Not too much, right?
Now imagine a platformer game with 200 tiles, 10 monsters and one player in one level. The amount of checks would be 2100! This makes the framerate drop quite severely.

Spatial Hashing visualised

The solution for this problem is Spatial Hashing. It basically divides the game world in cells which hold game objects. Using this method, objects only need to be checked against the other objects it's cell is holding. Simple, yet very effective.

SAT implemented in SFGE!

The Seperating Axis Theorem is successfully implemented in the engine. It is now able to handle collision detection AND response between convex shapes. All this functionality has been integrated in the form of three classes: ConvexCollisionDetector, ConvexCollidable and ConvexShape. ConvexCollidable objects have a ConvexShape object as member. these can be added to a ConvexCollisionDetector who handles the collision checking & notifies the objects that collided with the necessary information to respond to the collision (it gives the Minimum Translation Vector and the object we collided with).

The documentation has been updated and the latest revision is supposed to be stable.

Seperating Axis Theorem

Since my current CollisionDetector class is rather primitive (AABB only) I searched for alternatives. I found a satisfying algorithm very fast: SAT (Seperating Axis Theorem). The online flash game "N" used this method and wrote a tutorial about the subject. I have the algorithm implemented, now I need to reflect a bit on how I'll redesign my Collidable class.

A quick video of my test application:

Expect the next revision of the engine to have this included!

SFGE Test Project

In order to iron out all the little bugs in SFGE I'm making a game using the engine. I chose for a platformer since my previous attempt somewhat failed (it was too ambitious). I'm aiming for a simple & fun game.
First progress video:

SFGE - Simple & Fast Game Engine

I'm here to present my new project: SFGE.

SFGE is an acronym for Simple & Fast Game Engine. It is built on top of the SFML library with the purpose of   allowing faster development of games in a simple and flexible framework. You can follow active development on the Google Code page. 

Currently, these classes are implemented:

• Director
• State
• CollisionDetector
• Collidable
• EventSystem
• Event
• FileLogger
• AnimatedSprite
• Animation
• ResourceManager

The next major milestone will be a GUI system for the menus.

Box2D and Python!

Last month I set myself some goals (see previous blog post). I'm happy to say I fulfilled all of them!

Box2D

First I wanted to get my hands dirty with Box2D. The start was rough, it's a pretty complicated library. I persevered and after 3 days of playing around, I started a little project. The result is Chest Crusher. Heavily inspired by Angry Birds, the purpose is to shoot catapult balls at castles and open up all the chests. When a big enough force hits a chest, it opens up.Here is a video from when it was still in development:

Python

Second up was learning a new language. I chose Python because of it's beautiful syntax and because is has lots of third-party libraries . The syntax was so easy, I started a learning project on my second day. A game, ofcourse :) . I decided to use Cocos2D over the more popular PyGame alternative because it was based on pyglet and thus supported hardware acceleration. I had little to no inspiration and the best I could come up with was a vertical space shooter. On the third day I had a functional prototype, here is a video:

One particularly easy part of development was writing the menus. In C++ it is the most boring task of game development for me, yet here I had a menu up and running in under 5 minutes. I will probably release this game in the future but it needs some more tweaking right now.

Conclusion

Learning new things is always a fun process, certainly when it involves programming! I'm happy to have a physics library under the belt now as well as a dynamic language. For small games that don't require much processing power, Pyhon is almost always a better choice over C++. 

Box2D & Taking a break

I've hit a wall in the development of my platformer. I feel I'm not up for the task yet to implement all the stuff I want my game to have. I'm going to take a break from programming this game and focus on learning as much as I can, starting with Box2D (and maybe make a little physics-based game). Physics have been quite a pain in the ass with my homemade physics-system so it's no surprise I want to get the hang of a physics library. Afterwards I'll try to broaden my skill set by learning other languages as well as some web design.

If you still haven't seen the latest video of the platformer, here it is:

Quite a lot has changed since this video, however.

Cheers, Xander.

Welcome

From here on out I'll be posting updates about my current projects and give you a sneak peek of what's to come.