My first Android application - 15 Puzzle Game

Did a classic implementation of the 15 Puzzle game as a class project.
Features
- Different background pictures to choose among
- animations
- sound
- highscore list

Requires Android 2.3.3 or above. Enjoy!

 

A* and 15-Puzzle

I have been trying to solve 15-Puzzles by using the A* (A-star) search algorithm. The A* search algorithm use not only the cost to reach the node (usually denoted g(x)) but also an estimated cost (usually denoted h(x)) to get from the node the goal node to determine the order in which the search visits nodes.
The heuristic function h(x) plays a vital role here, with a good heuristic function fewer nodes will be generated and ultimately leads to smaller costs both in time and space.
You can easily solve the 8-Puzzle with the Manhattan distance (MD) as your h(x) function but for the 15-Puzzle MD as your h(x) function is sadly not good enough.

Below are some numbers I got when I run my A* algorithm with a h(x) function consisting of  MD and Linear Conflict (LC). LC improves the heuristic function a little but the search is still painfully slow and not viable for any real usage if the solution length are to "deep".

MD + HVC
solution length                     nodes generated
19                                      497
26                                      2696
34                                      122941
42                                      501595
46                                      979602

There is better heuristic functions out there but then it is not "simple" anymore and will take some time and brain power to implement. You may consider one of these: The Manhattan Pair Distance Heuristic by Bernard Bauer, use pattern databases or Walking Distance by Ken'ichiro Takahashi.


UPDATE 2012-03-07
I did improve the heuristic function by also taking in account the vertical linear conflict (VLC).
Here are the new numbers.

MD + HVC + VLC
solution length                     nodes generated
19                                      342
26                                      1375
34                                      97894
42                                      104267
46                                      508080

Image effects

Coded some pretty straightforward image effects such as bucket fill, blur, chroma key, edge finding and convert to ascii. Bucket fill is still to slow but the others run pretty smoothly.

Original image.

Bucket fill effect.

Blur effect.

Chroma key effect.

Edge finding effect.

Ascii effect.

Returning from the shadows!

I'm back! After a long hiatus from computers and programming I'm ready to dive in again. Keep your eyes wide and ears open. :D

Bombsweeper

I wrote some code to handle logics for Minesweeper a while ago, so I decided to wrap it up and make my own version of this little game. Let me present to you Bombsweeper complete with 3 difficulty levels, highscore lists, and sound effects. Special thanks to Imphenzia for the sound effects!

Start screen.

A game of Bombsweeper on (Expert level).

TRON B - A simplified game of Tron using MINIMAX

I have coded a Tron game clone to further see what the MINIMAX strategy can do. For those who are not familiar with the rules and game mechanics of Tron will here follow a short explanation. Tron is a two-player game where each player controls a square inside a grid. When a player moves her square in a direction (up, down, left or right) the square will move to that location and leave a solid "wall" behind. Do not crash into "walls" or your opponent. If you do, you have lost the game.
The goal is to outlive your opponent.
For the AI of the computer I've implemented a MINIMAX strategy. This time around I'm not going trough the whole game tree (to time consuming for large grids), instead I've limited the search depth. The challenge here is to write a good utility function that evaluate the current game-state "correct". So far i have equipped my utility function to consider the amount of free space and a "trapability" factor when evaluating game-states. It is not the killer I want it to be yet but with a few more "tools" added to the utility function...

The start screen.



A game in action.

Game over!



Tic-Tac-Toe using the MINIMAX strategy

I made a Tic-Tac-Toe game to see the minimax strategy in action and it works quite well, the AI still hasn't lost a game yet. There are fewer than 9! (362 880) games states in Tic-Tac-Toe so I can search trough the whole game tree for the optimal move. The utility function check for either a win, a loss, a draw or if the outcome of the game can't be decided yet and return a value accordingly.
I rank win > uncertain > draw > loss.

Tic-Tac-Toe