SFML News – Week 11 (2013)

Although I probably shouldn’t start again with something new and rather try to get more of those computer science articles ready, I still had this funny idea of releasing ‘news’ articles on what has been happening in the SFML community. I’ll try to release weekly articles, but I don’t promise anything and I don’t even know how much I’ll write for each article.

Projects

Kroniax

As promised by AlexAUT, Kroniax 0.4 got published last Sunday and it adds a complete redesign of the GUI and a few additional levels. Although he mentioned that it would take longer before the next version, he managed to get 0.51 (download page) out yesterday.

But who’s AlexAUT and what’s Kroniax? AlexAUT joined the SFML community in October last year and has been most likely busy ever since. Less than a month ago he released his probably first bigger game with SFML. It’s some kind of a side-scroller, where you have to maneuver a white triangle, representing a ship, through a maze of blocks. To make things more interesting the velocity of the triangle as well as the strength of gravity varies from level to level or can change within each level. Next to the described Arcade mode, the latest version 0.51 features now another mode called Speedchallenge, where you can change the velocity on your own, while you still have to beat the level. Since it is called ‘challenge’, AlexAUT added an online highscore, so you’ll get some aim to fight for.

Kroniax is extremely addictive and makes a lot of fun. Since I had so much fun with it, I’ve even made quick Let’s Play:

Open Hexagon

Legendary Vee has done it again and released not only one new version of Open Hexagon but five; starting with 1.8 and ending with 1.84 (download page). The most noticeable change are the online highscores. Everyone who’s playing with the official version in ‘official mode’, will automatically submit their scores to a server and get their current position and the top 8 places. But that’s not the only new thing; you now get a full menu for various options and a nice pseudo 3D effect. As always you can find the full changelog in Vee’s detailed ReadMe. The minor updates were mostly bug fixes, as well as security and performances updates.

I actually wanted to make another video on Open Hexagon, but my microphone on the headset died and I don’t have a replacement yet. The built-in mic of my notebook is not really useable for such things, but you can still checkout one of my older videos on Open Hexagon:

NEAT Visualizer

The NEAT Visualizer is a project, which visualizes an implementation of the Neuro-Evolution of Augmenting Topologies (short NEAT) algorithm. The NEAT algorithm evolves neuronal network structures and weights them simultaneously. Such a network is capable of learning some simple tasks, which the visualizer should make prettier for the eye. The used algorithm doesn’t have anything to do with SFML, since it’s a generic, but the visualization uses SFML underneath. Based on NEAT lolz123 has also written a small but fun game as Ludum Dare.

lolz123 released a new video and a new version of the NEAT visualizer this week. You can look at the video here:

Discussions

New SFML Logo

Nearly two years ago Laurent opened the discussion on the forum for a new logo. Back then we already assumed SFML 2.0 would get released anytime now, but well we are still waiting, more on that in another post though. After the thread died out for a while it’s back again and every week we get a few new suggestions. The ones of this week were in my opinion quite strange and not very well suited as logo. On two of them it’s nearly impossible to see the letters ‘SFML’, especially if you don’t know already that they should be there. The other one is textured which is not useable at all for a logo. But maybe I’m not artsy enough to understand this, so I’ll let you make your own opinions:

Will SFML support OpenGL ES sooner than expected?

OpenGL ES is as specification for a platform and language independed 3D programming. It’s mainly aims embedded systems (thus the ES) such as Raspberry Pi or devices that run Android or iOS.
If SFML were to be ported over to OpenGL ES, it could potentially open the world to a whole new set of platforms and thus new games and applications with SMFL. In general Laurent wants to get SFML to OpenGL ES, but in the past this was not due for anytime soon. What could then change his mind? Well slotdev started a discussion on the forum about having a DirectX backend for SFML, which would involve even a bigger change to SFML, but luckily some guys have created ANGLE, which basically translate OpenGL to DirectX calls and thus enables one to write OpenGL applications for platforms which support only DirectX. The downside to this is though, that ANGLE implements an OpenGL ES specification. Since slotdev and a few more people are commercially working on games for casino machines, Laurent stated that he’d be looking into getting OpenGL ES support sooner than plant, if they require it anytime soon. The discussion was then moved to private chats and we’re kind of left in the dark what they decided on.

What do you guys think about elevating the priorities on OpenGL ES? Should Laurent tackle other more important issues first before rewriting huge junks of SFML’s code? Let me know what you think in the comments below.

Source code changes

Personally I feel like we got a much more involved community in the past few weeks, but I’m not sure whether this is just because I’m looking more closely at the commits and what’s going on, or if it’s really because more people are submitting pull requests and Laurent actually accepts them. It also kind of feels like, Laurent got a bit more open about contributions after the forum thread with the title: “More Commuity-driven Development”

  • We received a fix from one guy, who had problems with some events on Arch Linux with Awesome WM. – 560b741
  • As noticed by our great Nexus in a forum post, the explicit for the sf::Text constructor wasn’t needed anymore. – 5c46daa

 

I hope you’ve enjoyed reading my news post and actually got some news out of this. If you feel, that I’ve missed some parts or just got any kind of feedback, please leave a comment down below or contact me by means of PM, Mail, Twitter, IRC, etc. I’d really to hear some opinions.

Recursive Algorithm

Now that we’ve looked at what an algorithm is, we can go a bit deeper and take on one of the most common section of algorithms: Recursion

Recursive algorithms are actually quite easy to understand and we often use it intuitively in our daily life. Recursion only means, that a function calls itself. To illustrate things, we’ll be taking the calculation of the Fibbonaci numbers as an example. The following image shows the first few numbers and a mathematical definition:

So as you see the function f has one initial values for n = 0 and n = 1. For every other n, we call the function f recursively.
Since we as programmers are not that interested in the mathematical terms, here goes a very easy and straight forward implementation:

unsigned int f(unsigned int n)
{
    if(n == 0 || n == 1)
        return 1;
    else
        return f(n-1)+f(n-2);
}

As you see it nearly matches the mathematical definition after all. If we now were to test this function, we’d soon notice how long it takes to figure out for example n = 50. So how do we make it faster? To answer that question, we’ll first have to take a look at why the algorithm is so slow and for that we need to take a closer look at how applications work in general.

Every application gets a memory area with fixed size, aka as stack, on which it does all its local operations. For every recursion we’re making, all the currently active variables, states, etc. have to be saved onto the stack and only then the “content” for the new function will be loaded. Doing this a few thousand times will crush your performance and can essentially even lead to stack overflows, which means your application will crash.

One way to fix this, is to trade some memory for performance. The main problem of the recursive algorithm is, that it will calculate the same number over and over again. You’ll end up with a tree which is built with the same sub-trees all over again:

With the acquired knowledge we can turn the whole algorithm around and instead of starting at the top, we start at the bottom, save every result in between and then apply the formula for n+1. Now we can immediately look up what the result for any n-i is, we only had to calculate it once and we don’t need to recursively call the function.

#include <vector>

unsigned int f(unsigned int n)
{
    std::vector<unsigned int> mem(n+1, 0);

    mem[0] = 1;
    mem[1] = 1;

    for(unsigned int i = 2; i < n+1; ++i)
        mem[i] = mem[i-1] + mem[i-2];

    return mem[n];
}

You can obviously also use an array if you’d like, but I prefer to use modern containers, which should also assert for out of bound mistakes. The pre-allocation of the vector will give us a bit a better performance due to the fact that, vector won’t have to resize itself while inserting new numbers, but in comparison to the recursive algorithm this won’t be noticeable anyways.

Although this might seem to have worked just for this specific case, the used principles can be applied to quite a few recursive algorithms and is called memoization (no it’s not memorization). Here are the steps again:

  1. Find the recursive formula.
  2. Implement a straight forward algorithm.
  3. Bottom-Up the algorithm and ‘memo(r)ize’ all the steps.

Keep in mind though, that this method is just one way to optimize algorithms and that it might work for other problems, but not be the best way to do it.

I hope my article wasn’t too unstructured and confusing, but gave you some insight or refreshment on that topic.
A complete example with benchmarking can be found on GitHub.

What are Algorithms?

Although I guess most of you know exactly what an algorithm is, I felt anyways that I needed to give a small definition, before I’ll be able to cover specific (types) of algorithms.

When dealing with problems in computer science one generally looks at the ‘theory’ behind solving the problem and the actual implementation separately. Thus an algorithm can informally be defined as the way/idea on how to solve a certain problem, but it often won’t contain an actual implementation to keep a very general layer.

A formal definition of what an algorithm is, can be quite philosophical and complex and is only needed, if you for example have to prove that there doesn’t exist an algorithm for a given problem. Anyways I won’t be going any deeper on that topic and I often won’t stay very general and will give C++ implementations to most of the algorithms.

The course at the university is in fact called “Algorithm and Datastructures”, thus you can imagine that I’ll be also looking at different datastructures. In essence are datastructures also algorithm; they solve the problem of efficiently storing and retrieving data and make use of various other algorithms for their implementation (i.e. a heap sorts its node in a certain way, as describe by an algorithm).

All in all not a very interesting or in-depth article, but it seemed important anyways. Of course if you’re all about knowledge go read the Wikipedia article and start click your way from there into the wildness of the internet.

Stay tuned for further updates! 🙂