Jake Warmerdam

Fast Sudoku Solver

Inspired by a programming puzzle book someone got me, I decided to try my hand at a sudoku puzzle solver. The basic implementation is very simple, but I wanted it to go as fast as possible. Initially, my implementation would take a second or so to solve a basic problem, and hang for a long period on certain very difficult cases (including impossible puzzles). After quite a lot of optimization, it now solves pretty much any puzzle I throw at it in a few milliseconds. You can even give it a completely empty board and it will spit out a solved puzzle as quick as solving any other. The only puzzles it will take any time on now are puzzles that are found to be impossible after deep nesting. Those will compute in about half a minute. m sure I could bring that down, but I am satisfied with the current implementation. The nice thing about sudoku is you can represent the entire data set pretty compactly, and also validate guesses extremely quickly. I have a data structure to represent each box on the board, that includes the guessed value, a bit field that stores which numbers have been definitely eliminated (by duplicates in its row or column, etc), and how many values have been eliminated so that, for instance, if there is only one value left we can just use that as the computed value. I also keep a structure that represents each set that is supposed to hold the numbers 1-9 (one for each row, column, and box) and use this to speed up computation. With all that, it pretty much just solves like a human would: look at a box, see if there are any reasons that box could be only one value, if no boxes have only one value, then make a smart guess, continue to solve until an inconsistency is found or the puzzle is completed.I

First Android App Published

My first ever Android app is available in the marketplace: CuteCounter. My wife came up with the idea. It simply replicates a tool that knitters use, but it is convenient because you can track multiple projects, and save/load. Cute Counter

2D Shadows

A year or two ago I wrote up a quick test of rendering soft shadows in a normal mapped 2d scene. It didnt look half bad, but I never really had a project to try it out on.

Race to the Top

My family plays a lot of games over the holidays, and sometimes we like to make up our own rules, or extend the rules of an existing game. A few years ago we got so far as to start creating a whole board game. We had some interesting dice rules, and my dad drew out an initial board mock up. Since then ve been working on a photoshop for a real board off and on.

Game Jams!

I have participated in a couple of game jams, and really had a good time. In my first one, I was a lone wolf, the theme was infection. Since I didnt have any support on the graphics or level creation, I had to keep it really simple. What I made was a zombie game based on physics: you can push a zombie around, but when they start to crowd around you, they become too hard to push. If you are surrounded for too long, you are dead (you start over, and your previous player is now an extra zombie in the maze). My levels were a grid, so I just created them in photoshop. Different colors had different properties, i.e. white was a solid wall, red was a switch, and so on. I also controlled camera zoom this way, so I could have a scary corridor where the camera was zoomed in too far to see much around you. Finally, I recorded a jazzy drum beat with a bunch of moaning zombies over top for the music.

In my next game jam, I had a partner, James Kono, a coworker. The theme was treachery. We settled on a treacherous control scheme: each controller actually controlled two different avatars, one player would hold the left side, the other the right. We supported four players at once, using two controllers. Since all you could do was move, jump, and attack it worked out. (the controller idea didnt work that well, but the game itself was pretty fun) The game centered around jumping from planet to planet, attacking each other, and collecting power ups. The most fun part was playing with momentum using the gravity of the planets.

3D Risk (2007)

I was playing a lot of Risk and wanted to do a related project. I had two ideas: 1) A Risk AI interface, to allow different AIs to battle (challenge your friends to program one!) or 2) a 3D risk game. I started with the 3d game, and pushed it pretty far before realizing that a realistically rendered earth is not fun to play risk on. I had recently purchased a graphics card with decent pixel shader support so it was a good excuse to try it out. I grabbed the color and cloud maps from the NASA blue marble project, which was really convenient, but I did write some conversion scripts to take the super high-res lat/long map from NASA and convert to my own cube map variation that minimized stretching in the corners. I used fully 3d atmosphere model to calculate the shadow of the earth (at first - when you exaggerate the size of the atmosphere it looks great, but at realistic size it wasnt worth the performance hit. In the end I used fin extrusions around the edge of the planet and a hand painted lookup texture for color shift to have more control over the look during sunrise) I also had a separate normal mapped cloud layer that cast shadows on the ground, which looked pretty good in motion.

Final CS Project (2005)

My final project for my computer science degree was for an advanced compilers course. What I did was create a hypothetical game machine, that was to be used to teach basic game programming. I created a full instruction set architecture, andwrote an emulator for the machine. Then I wrote a compiler for the machine (the language was a useful subset of C, and it had a few extensions specific to game programming, such as importing data resources). It had joystick input, graphics output, and a few other education related features, such as ability to change the clock speed and video refresh rate of the machine. I wrote a couple small programs to demonstrate that everything worked correctly.

Raytracer (2004)

For an introductory computer graphics course in 2004 the final project was a basic ray tracer. The min spec was lighting with hard shadows, reflections, and sphere and plane primitives. I added a few additional features such as soft shadows, anti-aliasing, texture mapping, bump mapping, refraction, and simple video support (static scene, camera on a spline)

Minigolf Physics (2003)

This was my attempt at a simple minigolf game. I started by implementing collision and physics for the ball. The unique thing about the implementation was that it would actually solve the motion equations for the exact time of collision so that there would never be interpenetration. The downside was it had some numerical stability issues.

Terrain and Trees (2000)

Here is a project from around the year 2000, featuring terrain and trees. I was really interested in creating trees procedurally. This also had a separate cloud layer that was created by combining multiple scrolling layers of noise texture together.

First 3D Program: "718" (1999)

This was one of the first 3d programs that I ever wrote. My brother and I collaborated on it - it must have been 98 or 99 when I was still in high school. It featured colored lightmapping, and a skybox, and the really great feature that when you take a screenshot, it said screenshot right in the middle of the screen. The name of the engine, 718, stood for the day we started working on it: July 18. We were just having fun during summer vacation.