Archive for the ‘Independent Project’ Category

RTS Framework

Please look here to browse the state of this project.

rtsframework

Over the winter break of my senior year, I took on a project with two long-time friends of mine, Breck Fresen (CMU CS ‘09) and Erich Wolodzko (Stanford CS ‘09) [citations needed]. After completing the majority of our undergraduate degrees, we challenged ourselves to see what we could accomplish in 3 weeks time. We opted to attempt to create the system framework for a real-time strategy game (i.e. Starcraft, Age Of Empires, Command & Conquer) that is entirely data driven. Ideally, using the framework, one could play any number of style of RTS games that have completely different art, maps, units, etc. just by switching a config file. Our feature list included internet multi-player capability, 3D accelerated graphics, and OS portability.

These goals imposed many difficult design decisions on the structure of the system. In a collaborative effort, we designed the system to work on 3 separate threads: a main control thread, a game logic thread, and a network maintenance thread. The main control thread was in charge of the presentation layer and window/input handling. The network maintenance thread handled our unique strategy of synchronizing multiple players for game actions. The game logic thread took input from the control and network threads to progress the game forward.

To maintain synchronization across multiple computers, we decomposed all game logic into a set of “game commands,” specified by a game-time timestamp and meta-data depending on what the command represented. We turned all user input into a corresponding game command, and, depending on the length of network latency, elegantly broadcast a time-chunk of game commands to all other peers. Once all peers acknowledged receiving all game commands up to a particular game time, those commands were allowed to be executed at their appropriate time by the game logic thread. This strategy guaranteed no 2 peers falling out of sync with game commands, but could become jerky or locked depending on network instability.

I, personally, was a part of every design decision. Furthermore, I was in charge of the majority of the control thread’s responsibilities, wrote a custom GUI framework to work both as a menu-ing and in-game interface system, implemented all graphics work (OpenGL), and implemented my share of game logic.
The project was written entirely in C++. It has only been tested to compile under g++ and uses GLFW for portable windowing.

In 3 weeks we were able to successfully synchronize 3 computers across the nation to create, select, and move multiple units across a complex terrain. Hopefully one of us will breathe life into the project later when we have the time and energy to do so.

Cube Solver

Originally taken from Breck Fresen’s page

Here’s a quick video of the program in action:

Download the source here. To compile for Win32, you’ll need to link in the OpenGL DLL’s.

Background

At the end of freshman year my friend Breck and I teamed up to write an optimal Rubiks Cube Solver that runs in a reasonable amount of time (not days like Richard Korf). The program randomly scrambles the cube and then solves it in the fewest number of turns possible.

Rubik’s Cube presents an interesting search problem because the cube space is so large – 43 quintillion combinations – that even if we could compress our cube representation to the theoretical minimum of 66 bits, we would only be able to store 1 one-hundred-billionth of all possible cube states in RAM at any given time on a 32 bit machine.

Implementation Discussion

With lessons learned from Path Finder, we started simple. Initially we scrambled the cube with just a few turns and used breadth-first search to solve it. On his laptop (1GB of RAM), this could solve cubes scrambled to a depth of 5 turns before the program started paging.

Next we implemented a double-ended breadth first search (where the scrambled cube searches for the solved cube and the solved cube searches for the scrambled cube). Double-ended searches (aka two frontier searches) are more efficient than their one-way counterparts on graphs with any significant branching factors because 2 * O(n) is much smaller than O(2 ^ n). This allowed us to solve cubes that required 10 turns, and we could do it in 2 minutes or less.

Our cube representation also improved. Initially we represented each face by a 3×3 array of 32 bit ints, which wasted a significant amount of space. Ultimately we settled on bit fields, where each cube face was represented by 9, 3 bit numbers (where each 3 bit number represented one of the 6 possible colors). This reduced our cube size from 216 bytes to 24 bytes.

Finally we implemented double ended A*, which required our first bit of serious thinking. Picking a heuristic for the cube space that always underestimates the distance to the goal (a requirement for A* to return an optimal path) was non-trivial. Ultimately we realized that a single turn can correct at most 4 edge-corner pairs and 4 edge-center pairs. This turned out to be an excellent heuristic. It got us another depth out of each end of the A* search, meaning the laptop could solve cubes scrambled to a depth of 12 or less without paging, which is where the program stands now.

I believe it’s been proven that there exists a cube – the superflip – which requires at least 24 quarter turns to solve. So we’re still a long way from being able to solve every cube optimally. But this program is an excellent example of how progress happens when you attempt a problem you’re not entirely sure you can solve. Try, test, improve. Iterate.

Tank Hunter

Download the source here.

Tank Hunter was a personal project amongst friends that turned into a high school independent study project. I worked with my high school friends Erich Wolodzko (Stanford CS ‘09) and Eric Iverson (UIUC EE ‘09) to create a video game engine from scratch.

Looking back on the code after my undergraduate education, I see many spots for improvement, but the lessons learned were invaluable. It was my first real experience designing, developing, and iterating all pieces of a larger code-base structure. To this day, this is the furthest completed independent project I have taken on. After developing the entire system, we spent over a month hashing out bugs, redesigning the game to be more entertaining, and attempted to port it to Mac. I still show the finalized game to peers and interviewers.

Please view in-game footage here.

Path Finder

Originally taken from Breck Fresen’s page

Download the source here.

Path Finder, was developed as a science fair project for the senior division of the Illinois state science fair. We (my friends Breck Fresen, Erich Wolodzko, and I) were awarded Best in Category in Computer Science at both the regional and state levels.

Although college makes the project seem simple in retrospect, at the time it was very challenging and a tremendous learning experience. I’m keeping it here for nostalgia’s sake.