Another inquiry post. I’m thinking about removing the custom mouse interaction code in Palapeli. The situation is that whereas most applications hardcode what certain mouse buttons do (e.g. left button = click, right button = context menu), Palapeli allows the user to configure which mouse button (or wheel) does what. For reference, this is the default configuration:

Problem is that the code behind these mouse button associations is awkwardly complex.¹ I plan to remove this mess and replace it with a sane default configuration because I feel it’s just adding clutter without providing much added value.

So if you want me to keep this code, please write back. Besides that, I also accept recommendations for a better default configuration.

¹ In numbers: 1127 LOC where the whole application is about 6000 LOC.

Now on Twitter

April 2, 2011

My last post was quite big, so I’ve split out the news part to ensure that it gets some attention. I’m now on Twitter as @stefanmajewsky. Follow me for updates on my KDE development, esp. Palapeli and Tagaro. My blog posts should also be syndicated there automatically; this post is the test balloon.

The Blue Wonder Meeting last week was an excellent opportunity to do some work on Palapeli. One thing that I wanted to do for at least a year was to rewrite the multithreading code around the (fairly central) Palapeli::Puzzle class. The new class has an aspect-oriented design, where single components of the puzzle (like the metadata or the contents) are always made available by worker threads, by casting existing components. For example, a puzzle file can be casted into metadata by reading the latter from the puzzle file. The possible casting paths are actually so convoluted that I documented them in an image inside the source code directory:

Yet there are still areas where Palapeli’s concurrency needs to improve. Much of the puzzle loading is done in the GUI thread, which causes the loading animation to freeze frequently. But that’s for another day. Moving back from what I should do to what I actually did, I noticed that Palapeli’s memory usage is awful. During the sprint, I wanted to demo Palapeli’s performance with big piece counts, and created a puzzle with the maximum of 2000 pieces from a 5000×5000 px image. It actually rendered fluently, but only because I upgraded my notebook’s RAM to 2 GB last year. Palapeli used an enormous 1.6 gigabytes of memory.

I figured that’s a bit much, and looked yesterday evening into how this can be optimized. I was testing with a 30 pieces puzzle from a 4000x4000px image. After having started Palapeli and having loaded the puzzle, the application used about 800 MB memory. The first, and simple, optimization was to remove some intermediary images which are only used while loading the image. That saved something like 100 MB of memory. But wait! Shouldn’t a 4000×4000 pixel image need only 61 MB (four bytes per pixel)? Yes, that’s true, but actually we’re not talking about one big image, but about 30 images, one for each piece. While pieces might have an arbitrary shape, their image must internally be rectangular all the time, even if big parts (e.g. around the plugs) are fully transparent. This means that the memory usage for the 30 pieces is bigger than what one might expect from the complete image.

A randomly chosen piece was 855×1098 pixels big, so by a rough approximation, all 30 pieces take 30*855*1098*4 bytes = 107 MB in memory. That still does not explain why the process still occupies 700 MB. But what’s that?

There’s a shadow around the pieces! This shadow is not added by the slicer when the puzzle is created, but by the engine when the puzzle is loaded. And because we need to control how shadows cover other pieces, we cannot render the shadows into the piece image, but must store them as separate images! And to make matters even worse, we need different shadow images for selected and unselected pieces (note the difference between blue and black shadows). The shadow size for the test image is 0.15 * (width + height) = 300 pixels on each side. Putting everything together, the memory usage of piece images + normal shadows + selected shadows is about 700 MB, i.e. everything can be explained by the pure size of the displayed images. The second optimization therefore was to restrict the shadow size to 50 pixels. This reduces the memory consumption to 380 MB, and allows to play even 5000×5000 px (i.e. 25 megapixel) images with below 1 GB of RAM.

More sophisticated optimizations are certainly possible, but let’s stop at this 50% improvement for now. There’s another thing I want to show: Palapeli’s mainwindow has been cleaned up. I really liked the old tab interface. It had its time and justification, but I want to move forward and need a cleaner, more standard interface for that. So now Palapeli has only a menubar and toolbar, just like all the other apps:

This change was possible after I realized that all toolbar actions for the collection also make sense on the puzzle table: Delete and Export work on the current puzzle. Newly created or imported puzzled will be loaded into the puzzle table afterwards. The “Back to collection” button replaces the “My collection” and “Puzzle table” tabs.

From the 4.7 dept.: The puzzle list in Palapeli 1.3 will have sorting (by title and piece count) and filtering by title.

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=" 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.

I don’t have to tell you how great Akademy was; others on the Planet have already elaborated on this quite extensively. The only bad thing is that I had to depart on Tuesday. (Also, my plane to Helsinki was delayed quite a bit, but that’s another story.)

Those of you who were there probably remember the keynote of Aaron who wants us to put a focus on elegance. Details. The small things that distinguish good and useful programs from great programs. I soaked this message up like a sponge, and started working towards more elegance in our beloved jigsaw puzzle game Palapeli immediately after the keynote.

There are already quite some visual improvements which we are working on for Palapeli 1.2 (KDE SC 4.6): During the next week, the bling-compatible Goldberg slicer will be integrated into Palapeli as the new default slicer (I have just renamed it to “Palapeli Slicer Collection” to reduce confusion over the name). This will give us more natural and random piece shapes, and more grid types such as the Cairo grid with its pentagonal pieces.

The Goldberg slicer makes apparent a problem in a seemingly unrelated point of the program. Because it offers very many configuration options, the puzzle creation dialog turns into a mess:

I have now turned this dialog into an assistant dialog (also known as “wizard”) with multiple pages, which should make it more obvious what to do:

I am well aware that the third page is still quite cluttered. libpala already has support for flagging slicer properties as advanced, and once Palapeli knows to use this information, we will be able to present to the average user only those properties that really matter (most prominently the “piece count”). Another possible strategy could be to use images which describe the slicers and their properties.

Apart from these concerns, the new page layout makes it easy to cleanly add new options to the wizard (like the cropping interface requested in bko#231407).

One other thing which I’m working on is a bit unrelated to the original elegance theme of this blog post: I’m investigating how to make the puzzle loading more multi-threaded. This should make the puzzle loading faster, and the application should become more responsive and startup faster even with big puzzle collections.

Last but not least, Johannes Löhnert (the developer of the Goldberg slicer) is working on more puzzle pieces bling, namely a bevel effect which is applicable to all kinds of puzzles (also to those which you have generated with earlier Palapeli versions). Compare the current rendering without bevels (on the left) to the rendering with bevels (to the right):

As you see, we know already now that Palapeli 1.2 (KDE SC 4.6) will rock hard when it is released to the masses by early 2011. Bleeding-edge lovers can obtain the updated puzzle creation dialog already now by building kdegames trunk. The Goldberg slicer is in kdereview and will be merged with trunk very soon (just like the bevel patch).

Last night, I completed an extensive update of the Palapeli manual, so the 1.1 release is technically done now. Of course, the KDE SC 4.5 beta phase is still ahead, but one does not need to fear the beta phase if one manages to write good code, and I’m confident I did so this time. 🙂

So on to Palapeli 1.2: While 1.1 focused on improving the puzzling experience, 1.2 will also include changes to other parts of Palapeli. Most prominently, I will work with Johannes Loehnert, who has just recieved has KDE SVN account, on importing his Goldberg slicer as the new default slicer plugin.

As a part of this process, I will be adding some new API to libpala, the library that slicer plugins use to communicate with Palapeli. And this finally brings me to why I am writing this post at all: If you develop slicer plugins or use libpala in some other manner and want to review this new API before it goes live, please send me a mail or drop a comment here. I’m very interested in your feedback.

Generating a Palapeli puzzle requires one to slice the image into jigsaw pieces. I had no clue how to write a good slicing algorithm for Palapeli. Several tries showed that I am not particularly good at this stuff. Because of that (and because I want more puzzles with obscure piece shapes), I made the puzzle generation extensible: You can write your own slicing plugins for Palapeli. (There’s even a tutorial on Techbase, if you are interested.)

My evil plan worked out: Johannes Löhnert has implemented a Goldberg slicer (I’m not quite sure where the name comes from.) with a plethora of tesselation types and eyecandy. What follows is a shameless (though authorized) copy from the project page:


For KDE SC 4.6, we will work on including the Goldberg slicer as the new default in Palapeli. If this is too long time for you, head over to the project page to install the Goldberg slicer.¹ It works with Palapeli 1.0 and higher.

¹ The fine print: There are only source tarballs at the moment. I tried to make RPM packages with kdeobsgenerator, but it failed with weird linking errors which I could not reproduce outside OBS.

Season of KDE (SoK) 2010 is kicking off. SoK is an annual program which makes it easy for students to enter the world of open source development: You pick a project, write a proposal, and if it is good, you will get your personal mentor who will help you on your way to completing your project. Plus, you get a certificate some nice KDE swag.

Unlike its bigger brother, Google’s Summer of Code, the rules are less strict for SoK, which allows me to offer you a chance to do a Palapeli-related project for SoK.

Palapeli is KDE’s jigsaw puzzle game. It has just seen its first stable release three months ago as part of KDE SC 4.4, and as with every new software, it is still lacking some important features. Among the most requested features is what I call “puzzle piles”: a way to organise big puzzles into piles, which can be looked at separately. Implementing puzzle piles requires both work under the hood and in the interface, and is something which should be solvable in two to three months of work.

If you are not interested in puzzle piles, you can also come up with your own ideas how to make Palapeli rock. KDE’s Bugzilla has 21 open feature requests. I’m also perfectly fine with a project proposal that implements ten small features instead of one or two big ones.

If you would like to do a SoK project for Palapeli, do the following:

  • Grab the source code from svn://, and dive into it. (Ask me if you have a hard time with compiling.)
  • Write your proposal. You should include details about
    • how you want to implement the features in code
    • what you imagine how the user interface will look like
    • yourself (your previous experience with C++/Qt/KDE, how much time you will have to work on your project)
    • a timeline (I expect a total project duration of three or four months. Divide these into chunks of a few weeks, with some explicit target, like “read pile association from savegame”.)
  • Send your proposal to until the end of next week (i.e. Sunday, 9 May 2010). We will comment on your proposal, and you are allowed to improve it and resend it within the deadline.
  • The best proposal will be picked, and you can begin to work with your mentor (which would be me most probably).
  • If you complete your project successfully, the results of your work will be merged into trunk at the end of the SoK and released in Palapeli 1.2 as part of KDE SC 4.6.

Now, after having described in detail the application process, what are the requirements? Not much. You should be familiar with C++ and Qt. Experience with Qt’s Graphics View framework will greatly improve your chances, because everything about Palapeli’s puzzle table is based on that. Also, you should have enough time for hacking this summer.

For any further questions, you may ask me personally. You find my mail address in the copyright headers of Palapeli’s source code, or in Palapeli’s About dialog.

The fine print: Even if you are not considering to take on big projects and apply for SoK, the right time to start contributing to KDE in general and especially Palapeli is right now! Write to me or to the mailing list if you are interested in hacking on Palapeli.

Anyone remembers the configuration option “Left mouse button moves viewport” from Palapeli 1.0? It has been removed earlier this month, just to return on steroids in Palapeli 1.1 (which will ship with KDE SC 4.5):

I already spoiled this big change earlier this month: Any mouse interaction with the puzzle table can now be configured to arbitrary mouse buttons and keyboard modifiers. Just click on the button with the mouse icon, hold the right modifiers, and press the right button. And here is your favorite hidden feature: If you press the space key instead of a mouse button, the interaction is assigned to “No-Button”.

For example, the “Select pieces by clicking” interaction is assigned to “Ctrl+Left-Button”. That is, if you hold the Ctrl key and left-click on a piece, it will be selected. (Multiple pieces can be selected at once this way.) If you change the trigger to “Ctrl+No-Button”, the selection will be toggled with the Ctrl key only.

To test the strengths of this new framework, I’ve implemented some new interactors: The “mouse button” page in the first image shows an interactor which allows to toggle the lock state of the puzzle table area. (When I’m not taking screenshots of the default config, I have this configured to “Alt+No-Button” here.) The “mouse wheel” page in the second image shows wheel interactors to move the viewport.