Thursday, May 27, 2010

Push Down! - Update to 1.2

I just released an update for my puzzle game Push Down. After some considerations it now contains a new level selection scheme. I think the old one with a linear progression did not fit very well to the rest of the game structure. So now you can select each level in the game directly from the start but they are still ordered roughly by difficulty. Additionally I introduced a new rating system for each map based on the number of completion steps. So now the less steps you need to complete a level the better your rating gets. The best rating you can get are three stars and the worst a C (but you really have to wander aimlessly in a level to get a C). And finally I decided to exchange the black background to something more colorful. Here a two screenshots of the updated game.

If you have any comments please let me know.

Saturday, May 22, 2010

Gem Square - Procedural Gems

I just released my new free game Gem Square for Android on the Android Market. It is a very simple 'match 3' game with square gems. One of my goals when deciding to develop this game was to start a simple project where I could use my open source texture edtior NeoTextureEdit.
I hoped that using the editor on a real (but small) project helps me to identify parts that can be improved. The result after finishing gem square: it worked :-)

So here is a screenshot of the final NeoTextureEdit project with the gems from the game as procedural images:
It might look a bit confusing, but for such a small project it worked really well. The most important feature that was missing when I started the project was a way to automatically (i.e. via a shell script) export images from the texture project. This is now part of NeoTextureEdit and works really well by adding filename prefixes to individual nodes to mark them for export. More features that came to my mind during the project and that are now on my todo list are automatic graph layout and merging of redundant nodes.
At the end of the project I have to say that using procedural representations for game graphics when possible is really a time saver. The images are resolution independent and you can make small changes to all images with a single click and they get exported automatically. This hugely improves the workflow and shortens iteration time.

Sunday, May 2, 2010

Push Down! is NP-Complete

A friend of mine (nick: diophant) has proven that my android game Push Down! is NP-complete. The proof is surprisingly simple and he did it by showing how the boolean satisfiability problem (SAT) can be mapped onto a level in the game. Instead of a formal proof here is an example:

The equation is:
(A v B v C) (-B v -C) (-A v B) (-B v C)
and the corresponding level is here:

Each literal in the equation is a color in the map (A = green, B = blue, C = yellow). Due to the linked-block property of the game, same colored blocks can only move together. The three blocks on the left are the switches to set each literal to a value of either 0 or 1. Currently they are all set to 0 and moving them up would set them to 1. The four columns on the right are for each term in the equation. If you can find an assignment of A, B and C so that the equation evaluates to TRUE you can find a way to the exit otherwise not.

With this construction it is easy to see that you now can build a map for any given boolean equation but they would quickly grow in size and would be rather confusing to solve. Nevertheless this shows that Push Down! is indeed NP-complete.

If this was a little confusing here is some more detail. The equation above means 
(A or B or C) and (not(B) or not(C)) and (not(A) or B) and (not(B) or C).

The first column is currently blocked completely (A, B, and C are 0) but it is enough to flip one of the literals to make a way and also make the first term in the equation evaluate to TRUE. For example let us flip C (yellow) by moving it up. Now the first term evaluates to true and actually the whole equation evaluates to true as we now can walk the the end of the maps on the right.

If you have any questions or comments write them down below in the comments.

Push Down! Game Page

Saturday, May 1, 2010

Push Down! Update to v1.1.0

A new update for Push Down is released. I added a new challenge mode with 14 new maps. These maps can be played individually and in any order. On successful completion you get some fruit. More information can be found at the official website