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

November 11, 2010

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

October 31, 2010

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

March 4, 2010

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.

Undostack designs: command-based and state-based

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.

Push and Trim commands illustrated

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.)

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!

February 27, 2010

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”.)

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.

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:
kolf2-dependency-graph

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.