Visual tour through kdegames 4.6 Beta 1

Long time no see! I’ve actually been cut off from KDE development lately because the 4.6 Beta 1 update broke KMail temporarily, which is a blessing in disguise because it gives me time to focus on my upcoming exams.

Anyway, the KDE Applications 4.6 Beta 1 release is out (is that correct promo-speak?). Time to take a look at what is hot and new in kdegames 4.6 Beta 1. And the hottest way to do that is a visual tour:

Palapeli has received quite some polish. Johannes Löhnert has contributed a new set of slicers, which is now known as the Palapeli Slicer Collection. The screenshot shows the Cairo slicer which produces pentagonal pieces. Other shapes (both usual and odd) are available, and configurable to your liking.

To honor the addition of this big set of slicers, the puzzle creation dialog has been revamped. Create your own jigsaw puzzles in three easy steps (image file, slicer, parameters)! The screenshot shows step 1 (bottom right) and step 2 (bottom left).

Furthermore, Johannes has sent in a patch that creates a bevel effect on the pieces. As can be seen on the screenshot, they appear three-dimensional now.

As a regular reader of my blog, you probably know that Kolf has received some love lately: I have mostly worked on cleaning up the internals and making the code readable, so the only visible result is the new on-canvas controls in the editor (see top right of the course, where I have selected an elliptic slope below the cup). Saving edited courses is a bit broken in Beta 1 (and probably also Beta 2), I hope to sort that out before the final release.

The other big new feature in Kolf is that balls don’t tunnel through walls anymore, though that’s hard to visualize in a screenshot. But I can tell you that it’s a great feeling to close an eight-year-old bug.

No, the new feature in KDiamond is not an embedded KSysGuard view. I’m using KSysGuard to visualize the important change in here: KDiamond has reduced its memory usage with the new KGameRenderer framework. I’ve written about KGameRenderer before: Long story short, it introduces multiple levels of caching to speed up rendering of vector graphics theme elements. This was previously done in each game by itself; now it’s done once right by the KGameRenderer classes in the libkdegames library.

At this place, I’d like to thank all the volunteers that helped us to port a total of 13 games to KGameRenderer. This also includes:

Yes, it’s Klickety! We lost it in the KDE 4 transition, but now it’s back. As a fun fact, KSame has been removed: It is now “simulated” by Klickety through a “compatibility mode”, much like KSnake lives inside KTron.

Continuing on the track of new applications, Knights has just become the first game to be hosted on Git. It is stable, but has not yet had an official release because we still need to figure out how to release stuff from Git. However, some distros have packaged it already (e.g. openSUSE in the KDE:Unstable:Playground repository).

There are even more changes which I don’t remember now, or which I can’t write about because I don’t know the apps. The latter includes most notably Kajongg: It’s actually sad that Wolfgang Rohdewald, the developer of Kajongg, is not blogging on the planet. I’m regularly seeing dozens of commits from him, he’s active like the whole rest of the kdegames team combined, but no buzz is being generated about Kajongg, which makes me sad.

Also from the “interesting-changes-that-I-cannot-talk-about” dept.: KGoldRunner has gained a new input mode, and can now save the selected input mode (as far as the 4.6 feature plan tells me).

This concludes my visual tour through kdegames 4.6 Beta 1. More changes have happened under the hood, e.g. Granatier uses <a href="http://community.kde.org/User:Majewsky/Project_TagaroTagaroAudio for sound output, thereby replacing an optional dependency on GluonAudio by direct OpenAL+libsndfile usage.

Code from Project Tagaro is also being used by Kolf for its rendering. These uses all copy the relevant source code into their own source trees because libtagaro is nowhere near production-ready. I hope to get libtagaro into the state of a private library inside kdegames for the 4.7 release, to make kdegames even more resource-efficient, to make them fit for mobile form factors, and to make it easier to maintain them. Help is always appreciated.

Kolf update

I’ve just dcommitted another huge patch (+2730/-3371 in 22 commits) as part of my Kolf refactoring. We now know how Kolf will look like in the KDE Applications 4.6 release: Its balls won’t tunnel through walls. Its editor will work again. The GUI will still be ugly, but that’ s on the list for 4.7.

There are some kinks to iron out, though: My refactoring has completely broken Z ordering and strutting, so a ball can be reflected from a wall underneath a bridge, floaters will not raise balls, and so on. Also, the editor behaves a bit quirky now because it’s basically two editors in coexistence (just like there were two physics engines in coexistence for some short period in time). Since tomorrow evening is feature freeze, I will be hacking like crazy next evening, but now I need some sleep.

Kolf: The future begins now

While I’m writing this, git-svn is pushing into KDE SVN what I have been working on (with interruptions) for over four months now. After efforts on Kolf 2 have never really lead to something that can be considered a playable game, I’ve now started the harder road, which is to fix Kolf 1. This is so hard because the code of Kolf 1 is structured like a pile of mashed potatoes (read: nearly no structure at all), which even a former maintainer admits.

I started by simplifying awkwardly complicated statements. After some time, code was such that I could actually try to understand what is going on in the big picture. I’m not there, yet; I understand only the graphics stuff and the physics engine at the moment. Another big problem of Kolf is that it has some awkwardly big classes: The central CanvasItem class has no less than 40 virtual methods, and I’m not yet at the point where my refactoring massively reduces this number. The KolfGame class is even worse: By now, it has 39 methods, 30 slots, 17 signals, and 78 private members (of which only some have a “m_” prefix). The central header “game.h” contained over 60 classes when I started the refactoring; I’m now down to about 30 classes by removing an unnecessary parallel object hierarchy.

The biggest problem about Kolf 1, however, is its awkward physics engine. Problems with balls tunneling through walls have been known since KDE 3 times. But no longer! I have ported Kolf 1 to use the Box2D physics engine (which I had previously experimented with in Kolf 2) instead. This kills among other things bug 46532 which has been with us since August 2002.

So, the whole diff weighs in at some +2600/-3000 lines, and has been committed as a series of 55 commits. Great times are coming for Kolf.

How to come undone

Dominik Haumann of Kate is writing about the design of Kate’s text buffer. He also linked to an explanation of Kate’s undo/redo system. An interesting coincidence that this shows up on Planet KDE just now, because I’ve spent the last two days rewriting the undo stack of Kolf.

I’m using this opportunity to share my thoughts and experiences with undo/redo frameworks in general, just in case that this information might be useful to someone.

The basics

When everything goes right, an undo/redo framework remains mostly invisible. At the heart of each such framework is an undo stack. When you make some input in your program, information about this change is pushed onto the stack. One can then go back to previous versions by traversing this stack. Because the stack is linear, there are only two primitive actions which the user needs to invoke:

• Undo: Go back to the previous version.
• Redo: Go forth to the next version.

The words “previous” and “next” imply that the program keeps track of the current position in the stack. There is another bit of information which is saved in the stack: Besides the current index (where index means a position in the stack, I’ll expand on this in a minute), there is also a clean index, which refers to that state which has been saved on the disk. A good undo/redo framework should automagically enable or disable the “Save” button and add the “[Modified]” flag to the window title when the current index changes.

Select a state, or execute a command?

Until now, I’ve tried to keep the terms as abstract as possible, but what objects are actually stored in the undo stack? There are two basic models, each with its distinct advantages, disadvantages and application areas.

Let’s start with the right one, which I will call the state-based undo stack. In this model, the stack stores a list of states of the document. The current index refers to the state which is currently presented to the user. The “undo” action decrements the current index, and loads the new state into the view. Similarly, “redo” will increment the current index.

The state-based stack is very easy to grasp, but does not scale. Consider a text document of e. g. 300 KB which you type into your text editor from scratch. If the state is only the plain text string, we end up with a hilariously big undo stack which eats 44 GB of your memory. Not quite what we want, eh? Of course, we could constrain the size of the undo stack, but there is a much better solution.

The left stack in the picture is the command-based undo stack (at least in my terminology). It does not store complete states, but commands. One command contains the information which is necessary to convert two adjacent states into each other. In the above example, we would not store 300000 complete documents, but only 300000 character insertion commands. If a character insertion command consists of the cursor position (with line and column number) and the character inserted, a single command is 12 KB big. The whole undo stack would then be 3.5 MB in memory. Much better, isn’t it?

For these reasons, the standard QUndoStack provided by Qt 4 is a command-based undo stack. The state-based undo stack has other advantages: For example, it has a much better performance when selecting an arbitrary state. Let N be the absolute difference between current index and the target index which you want to select. This selection is an O(N) process, because N commands need to be executed. The complexity is O(1) for the state-based undo stack.

The other primitive actions

In the context of the undo stack, I have already identified the primitive actions Undo and Redo, but when the program is launched, the undo stack contains only one state (or no commands). Undo and Redo do not change the size of the stack, so there must be more primitive operations. It turns out there is one further primitive operation on an undo stack: Push adds a new state (or command) just after the current state. If there are states after the current state, these states are deleted before adding the new state. This is necessary to retain the linear shape of the stack. If we would not cut off, there would be two following states after the old current state.

When a new state is pushed onto the stack, the commands following the current index are removed. Imagine correcting a wrong word in a text editor: You press Ctrl+Z to undo this insertion, then type the correct word. The correct word will be pushed on the undo stack, and the incorrect word is removed. After having typed the correct word, there is no way for you to return to the incorrect word.

What I’m doing in Kolf

I already told you that Qt provides a command-based undo stack. And by now, you should have figured out that I won’t be writing about all this if the QUndoStack would suit my needs. In Kolf, I have chosen to use state-based undo stacks for two reasons:

• The states are rather small. The memory footprint is nearly identical for both types of undo stacks.
• The QUndoStack is, due to its design, missing some functionality which I need.

I have to admit that my usecase is rather exotic: I want to split the undo stacks to improve the modularization of my code. In Kolf’s editor, there are several objects which allow editing. Each hole has an editable par score and quite a number of objects on the green. All objects have separate undo stacks, which are (per hole) combined into one undo group. The undo group itself is an undo stack, again; its states are composed of the states of all contained substacks. The grouping can therefore be continued recursively.

Small disclaimer: The relevant code has not yet been committed because it has some severe regressions. (I previously used a command-based stack, which proved not to scale.)

Kolf: Progress, build instructions

I have made good progress on Kolf 2 over the last days. It’s now in a state where one can actually try it out (even if one has to recompile main.cpp to switch between editor and game, or to select another course). To make this as easy as possible, I’ve created Box2D packages and assembled instructions how to build Kolf 2.

Unfortunately, the Box2D packages provided by Ubuntu and Debian (and possibly also by some other distros) do not work with Kolf 2. Because of the changed build system, I chose to have Kolf 2 depend on an unreleased Box2D version, which only works with a patch of mine applied. See the compilation instructions for more information.

Box2D packages for everyone!

I have worked on Box2D’s build system today. My 14KB patch is now waiting to be merged upstream, and in the meantime, I’ve created packages of my patched Box2D version. Here are the repositories: (The package you’ll need is called “libBox2D2_1_0-devel”.)

• openSUSE 11.2
• openSUSE 11.1
• openSUSE 11.0
• Mandriva 2010
• Fedora 12
• Fedora 11
• Fedora 10

All this is brought to you by the openSUSE Build Service. My thanks go to the friendly folks at the #opensuse-buildservice IRC channel for their help to get the specfiles right.

If you have another distribution and want Box2D packages, please let me know: The Build Service offers some more target distributions. I did not add all dists at once to reduce the server load.

The fine print: It seems like the i586 build servers are either down or very busy at the moment, so there are only 64-bit packages by now. Update: i586 packages are available now.

The other fine print: I have tried to build packages for Debian/Ubuntu, but the build servers are giving me weird errors, and I am giving up now.

Kolf: Observations on code quality and the engine design

The third blog entry in 24 hours. That’s a new record for me, though not the foremost reason for this post.

Kolf 2 has, after about 4 days of intense coding, reached a size of 3000 lines of code. (I admit that much code has been ported from kolf-ng, so you cannot really conclude that I can write 750 LOC a day.) With the base engine nearly finished (the terrain, some object types and general bling will be added later), this is a good moment to stop and take a look at code quality.

On the heuristic side, I’m quite happy with the overall stability. Box2D has turned out to be a good choice: Its documentation is not very extensive, but I could get started with it much quicker than with ODE. The simulation code is simpler and at the same time more flexible than in Kolf-NG, and the simulation feels very natural (even with missing terrain friction). Kolf 2 does now offer some nice convenience classes around Box2D, which hide the non-Qt data types and make the API feel more Qt-ish. If you would like to add some new object types to Kolf 2 (e.g. the black hole is missing currently), drop me a mail or a comment here and I’ll get you started on Kolf 2 hacking (some C++/Qt experience required).

Moving back to the original intention of this post, there are of course some metrics for code quality. Take for example the length of the Krazy report. Recent problems with EBN got me to installing Krazy on my local machine, which went really smooth. (I did not notice at that time that openSUSE has a perl-krazy2 package.) After some smaller changes and two justified “krazy:exclude” lines, krazy did not find any issues.

So if code quality is good, can we at least reduce the code length? Yes, we can! Checking 29 header and source files each, I could remove 26 unused #include directives. I unfortunately forgot to check the compile time before this cleanup (and I’m too tired to rollback my git), but now “make -j3” is running in 19 seconds on my machine. (I’m speaking of real-life seconds, user time is 27 seconds.) That is approx. 6,2 seconds per KLOC. If only I had numbers from other software to compare this to. (Quick check: kolf-ng is 6,9 seconds per KLOC. About 11% worse.)

Hm, what else could we check? Perhaps a class dependency graph could highlight some design flaws:

In this image, dashed lines indicate very weak relations, which are only used for transfering change notifications, and bold lines indicate parent-child relations. Yes, both the ManagedObject and the Scene are in a certain sense parents of each Object. This works without any problems, because both will notice if the other one does for some reason kill an Object. While creating this graph, I have confirmed that every single edge in this graph is justified. Two main observations can be made:

1. That does absolutely not look like a mess. There are cyclic dependencies, but these cannot be prevented on the intra-module level.
2. Nearly everything has a direct connection to Object.

The second point is intentional: Shape and Overlay are two nearly self-contained parts of Object’s behavior (the physical shape and the editing interface), which have been split off to increase code reusability. The whole game engine consists of interactions between different objects, and all properties of the world are modeled as properties for objects. For example, there is an invisible course, which is used to spawn balls and record the course size. In Kolf-NG, there were also light objects for 3D rendering.

This generic design of a world as a bunch of objects makes Kolf 2 feel more like a generic game engine than an actual minigolf game, at least from the developer POV. I try not to change this trend very much when designing the interface. What is a course with holes in a minigolf game, could also be a level in a levelset, and so on. The Object class is designed such that new subclasses can be added through plugins, even if there is no sign of a plugin infrastructure in Kolf 2 currently.

The fine print: All of this does not mean that I am actively planning to turn Kolf into a generic game engine. There are more advanced and sophisticated projects like Gluon. What I am doing is not using the opportunity to design a game engine, I am reducing the probability to miss this opportunity when I might need it in the later run.

The other fine print: Writing this blog article took me two hours (to be attributed mainly to over one hour of reading Stack Overflow discussions on code metrics), so it’s actually not the third blog entry in 24 hours. Damn, no new record.

Tales from the debugging land

Here’s a funny bug I wanted to share with you (where “you” means all audience with bare minimum C++ understanding). I’ve been working today to add a putter interface to Kolf 2. (Attention: There are three Kolfs at the moment. I did previously explain why.) After fixing one or two crashes and fighting against Qt’s partly abstruse event forwarding (why do I have to setAcceptHoverEvents() in order to get mouseMoveEvent()s?!?), everything worked as it should, though there was one problem left: A mouse move event needed around 1 second to be processed. Callgrind to the rescue!

Okay, I admit that I had not expected the result to be so very clear. Let’s have a look at that method then:


void Kolf::SimplePutter::updateAppearance()
{
  if (!m_activeView)
    m_lineItem->hide();
  else
  {
    m_lineItem->show();
    //calculate line
    QPointF lineEnd = m_cursorPosition;
    for (int i = 0; i < m_direction; ++i)
      rotateBy90Degrees(lineEnd);
    //update line
    m_lineItem->setLine(QLineF(QPointF(), lineEnd));
  }
}

Looks quite compact, doesn’t it? Hm, rotateBy90Degrees is called multiple times, perhaps that’s the bottleneck:

void rotateBy90Degrees(QPointF& p)
{
  qreal x = p.x();
  p.rx() = p.y();
  p.ry() = -x;
}

Doesn’t look like it could be any more efficient. But even if it was unefficient, m_direction always has a value smaller than four, because everything else is nonsense. Anyway, let’s have a look at what value is in m_direction:

qDebug() << m_direction; //just before the for loop
//output:
135552768
135552768
135552768
135552768
135552768
135552768
135552768

A quick look in the constructor… Bah, I hate you, C++! Not only do you initialize int member variables with random values, but you also initialize them with random values that are always dividable by four so I don’t notice!

Kolf: 1. Box2D, 2. ???, 3. Profit!!!

The semester is nearly finished; Tuesday is the last exam (on quantum field theory). So finally I have some time for hacking. In the last few months, aside from some personal stuff, hacking almost exclusively meant Palapeli for me. I’m currently working on the design of the next version of Palapeli (with GHNS and puzzle piles, if everything works out), but that’s not what I’m hacking on right now.

In Kolf 2, I’ve decided some time ago to abandon the third spatial dimension and completely return to the classic Kolf feeling. This big change means exchanging the Open Dynamics Engine by a 2D physics engine. There seems to be only one good 2D physics engine around, Box2D. Incidentally, Box2D switched to CMake just two weeks ago.

After only some hours, I had some first prototypes of how I could implement the current Kolf-NG on top of Box2D. In order to get a clean design, I chose not to rewrite Kolf-NG from ODE to Box2D, but to create a complete new Kolf, with big parts of code being adapted from Kolf-NG. Now there are three Kolfs in KDE’s SVN:

• trunk/KDE/kdegames/kolf: quite stable and shipping, home-grown 2D physics engine
• trunk/playground/games/kolf-ng quite unstable, external 3D physics engine
• trunk/playground/games/kolf2 mostly just a testcase at the moment, external 2D physics engine

Now probably you want to build and try Kolf 2 (read: the testcase which will become Kolf 2 at some point). This is quite tricky, because the CMake-based Box2D has not yet had a stable release, so you’ll have to checkout the development version from this SVN url. Even worse, you have to apply this patch against the SVN checkout to have Kolf 2 find the installed Box2D library. Even worse, you’ll need to apply the following patch against the Kolf 2 checkout to have the test-case work properly. (I did not commit this because I usually forget to remove such stuff again.)

diff --git a/kolf2/base/scene.cpp b/kolf2/base/scene.cpp
index db7fa83..c68ce8d 100644
--- a/kolf2/base/scene.cpp
+++ b/kolf2/base/scene.cpp
@@ -30,7 +30,7 @@ static const int MillisecondsPerStep = 1000.0 * SecondsPerStep;

 Kolf::Scene::Scene(QObject* parent)
        : QGraphicsScene(parent)
-       , m_world(new b2World(b2Vec2(0, 0), true)) //parameters: no gravity, objects are allowed to sleep
+       , m_world(new b2World(b2Vec2(0, -100), true)) //parameters: no gravity, objects are allowed to sleep
        , m_objectFactory(new Kolf::ObjectFactory(this, m_world))
        , m_simulationTimerId(startTimer(MillisecondsPerStep))
 {

And even then, you will only see two colliding rectangles. I hope to get the gameplay and course loading working as in Kolf-NG by the end of next week (modulo the terrain). Still, the door is open to great features such as Kolf 1 compatibility.

Kolf: Call for help

The other day, Aaron wrote about the quest of "identifying projects in need". This reminded me that I have one project that it is in need: Kolf 2. About one year ago, I’ve put on myself the burden to rewrite KDE SC’s only sports game. I had big aims, 3D support (besides the classical 2D mode) being the most prominent one.

Over the course of the last year, quite some progress has been made on physics simulation, the implementation of 3D terrain, and a course editor interface. Some nice structures are in place, but big parts are still missing. Also, a weak spot in the design have been identified: It is not possible to allow 2D and 3D views at once. Period. For example, a 2D view does not represent any notion of height, which is important to determine the reachability of certain points of a map.

With real-life workload on one side and Palapeli’s feature request list on the other side, not much time is left for Kolf. This is a call for help: Are you a Qt/KDE developer, and would you like to help Kolf reach the next level of pure awesomeness? The following problems are waiting for fresh minds to be solved:

• Remove the 3D stuff (this should get you familiar with the codebase), and exchange the 3D physics engine by a 2D one.
• Finish the terrain drawing tool.
• Finish the other parts of the course editor (like: adding/removing objects, creating new courses).
• Write new object types.
• Find a better solution for the user interface building. (The current Kolf::GameUI has been written at a time when my knowledge of how to properly use the XMLGUI framework was quite limited.)

If you’re interested, find the source code here. My mail address can be found in there, do not hesitate to approach me with any questions you have. I can comment on any design choices and review new designs you might come up with (using my experiences from previous Kolf development).