KlickKlacker 2 Solver
KlickKlacker 2 Solver
The general idea of this game is that areas that are connected by having the same color are removable, and the objective is to remove areas in a strategic way until no further moves are possible. Cells will fall down if there is empty space below them and will be pushed together if there are empty columns. The game ends if there are no possible moves or if all the cells are gone.
My idea was to write a solver that builds a game tree where each leaf contains the final score from making a particular sequence of moves. As one quickly realizes there is a huge number of possible solutions. In order to speed things up, pruning of the game tree can be deployed. However, it is very likely (although unproven for this particular problem, but proven for similar but simpler problems) that the problem of optimally solving this game is NP-complete. This means that pruning won’t really help, because all leaves have to be visited in order to guarantee an optimal solution. However, a few obviously strategically flawed paths can be skipped. As with most pruning, evaluation functions must trade greediness and speed for optimal solutions.
A more failsafe optimization would be to implement a transposition table, because it is likely that by following different sequences of moves (in some cases simply changing the order of the moves) we arrive at the same game position, albeit with a different score. However, this involves checking for existens of a game position before solving at each node. This requires a fast hash-function for computing unique ID’s for game positions, which is non-trivial to design. In these cases we can terminate the paths where the same position was achieved with a lower score.
Currently, I can solve small grids (5×5) using a brute force approach. I also have a playable version of the game, for verifying the suggested moves (and for fun). The solver and the game are built on the same core-library developed by me.
Images
Hough/Radon Transform
Hough/Radon Transform
The Hough transform is a feature extraction technique used to detect objects or shapes in images. Features are represented in a suitable parameter space. The transform then casts votes into this space based on processing of the pixels in the input image. Local maxima in parameter space then correspond to the parameterised features.
The Hough transform operates on binary images, and as such often requires a thresholding of the original image. For greyscale images an alternative is to use the Radon transform. The Radon transform is roughly equivalent to a continuous formulation of the Hough transform.
The images to the right show the respective parameter spaces of a Hough and Radon transform applied to an image (not shown here). At first glance we seem to get better contrast in the Hough image. This is often desirable because it makes the task of finding robust local maxima easier. However, the price we pay for this is the constraint of having to input a binary image. Although it is more difficult to find robust local maxima in the Radon image, this method may sometimes be preferrable. One such case would be when the task of finding robust local maxima is easier than finding a suitable threshold for the original image.
Images
Obamafication
Obamafication
First, please note that this project does not express any political views whatsoever. Posterization is an art-form with the power to transform images into aesthetic renderings geared towards a particular message, often using few colors for printing purposes. I have taken the impressive style used in the 2008 Obama-campaign and applied it to a picture of myself. The procedure is well described in this tutorial. A lot of manual work is required and it is non-trivial to achieve the professional look produced for the presidential campaign. Also, some of the procedures described in the abovementioned tutorial are needlessly complicated. For instance, I have found that using a combination of blurring and median-filtering on the different threshold levels, followed by manual tweaking, is an intuitive way of shaping the final product. Also, this allows much more efficient use of the live-tracing capabilities of Adobe Illustrator, which eliminates the most time-consuming part of the process, namely the path-tracing. Adobe Photoshop and Illustrator were used to create the different image levels and the following path tracing.
Documents
Download vectorized version [.pdf]
Images
Level Set Ray Tracer
Level Set Ray Tracer
This application ray traces level sets by using the signed distance function to determine safe distances for rays to “leap” into the data grid. Snow is applied by letting particles fall downward in a 4D simplex noise field and applying a union operation where particles collide with the level set. The build-up of snow is rather slow for small particles, but smaller particles yield a finer grained build-up where individual unions are not visible after a while.
Images
Room Acoustics
Room Acoustics
A pressure source in a room will cause pressure changes to propagate. Our method of solution uses the Transmission Line Matrix (TLM) approach. Pressure is scattered in four directions at each node (i.e. each pixel in the visualization) and is partially absorbed by walls.
Documents
Images
PLY Reader
PLY Reader
Together with a friend I developed this application for an assignment at school. The application reads PLY-files and is capable of displaying normals, rendering {polygons | wireframe | points}, smooth or flat shading, and cel shading with edge detection (including interior edges). For efficient geometric queries a partial adjacency list was used.
Images
RenderMan Shader
RenderMan Shader
This shader was written for RenderMan. The initial geometry is a simple sphere. The sphere is displaced along the up-axis and further displacement is done to the surface to achieve the crinkles. Crinkles are produced by a noise function with appropriate frequency and amplitude. Green is mixed with brown on the surface for a more organic appearance.
Images
MojoWorld Landscape
MojoWorld Landscape
MojoWorld is an application that makes heavy use of fractals for landscape modeling. It is rather simple to create a decent-looking landscape, but mastering the parameters of this application could take a life-time! This is an image I made for a school assignment. Note the blue line across the mountains and the psychedelic clouds.
Images
Moonlander 3D
Moonlander 3D
User input controls the moon lander’s five thrusters, visualized by simple particle systems. An inertial system determines rotation and translation of the lander. The moon lander was modeled in 3DS MAX. The main remaining problem here is how to divide thrustor forces between rotation and translation, or to be precise, how to determine the ratio between translation and rotation given a force at a certain point having with a known centre of mass. This factor has been estimated to “feel” good. The simulation was turned into a game, where the user tries to land at a given location within fuel constraints, which is more difficult than it might seem.
Images
Procedural Smoke
Procedural Smoke
Smoke is an extremely complicated phenomenon to simulate. Flow equations (Navier-Stokes) must be solved in order to accurately animate smoke. Here, I simply use a kind of 4D vertex noise to displace particles in a vertex shader. This approach is simple, and produces visually pleasing snapshots of smoke. However, the motion of the smoke suffers from the lack of physical simulation. The noise I use has very small look-up tables since these have to be stored in vertex processor registers, as texture memory access was not available from within vertex shaders on my graphics hardware. Particles are rendered using GL_POINT_SPRITE_ARB, which are simply textured billboards that are automatically calculated on hardware.
Documents
Images
Tommy Hinks 