|
Selected Software Projects by Joel Martin
Spacewar game using python and pygame
|
2004-2005
|
|
In order to teach myself python, I decided to re-make the old DEC PDP-1 game
"Spacewar" with a modern look using the pygame library. Most of media files and
some of the menu code is derived from an open source game called Solarwolf. The
game play code (100% mine) is primarily contained in objs.py and ai.py.
In ai.py I also have the start of a genetic algorithm to generate the
heuristic AI player for the game. The GA is functional but it still
needs optimization and tuning work.
|
Fast, Non-deterministic N-Queens Solver
|
2003
|
|
In 2003 the Taylor University Computer Science department held a programming competition
to create the fastest N-queens solver for a 30x30 board. CS alumni were also invited
to submit entries for fun. I created two different versions for this contest. Both are
quite fast and use a non-deterministic algorithm to solve the problem.
The first version uses short variable names but
is well documented. The second version is an obfuscated and shortened version
(also limited to a 30x30 board). It is 473 characters long and must be built on
Linux using the compile string specified in the comment at the beginning
(ignore the warnings). It is presented as the result of an intense problem
solving activity and not of good programming style. The curious reader may notice
that the compile line compiles the program twice and uses the "--omagic" linker
option. Thanks to Aaron Brooks for some obfuscation suggestions.
|
Highly Optimized "Conway's Game of Life"
|
2002
|
|
After reading about cellular automata discussing them with some friends
I decided to write my own optimized implementation of Conway's Game of Life.
The current code is set to play a 10,000 x 10,000 cell board. The comment at
the beginning of the code describes the data representation of the board.
Rather than calculating each cell of the board for every "generation", this
program pre-calculates a lookup table for every possible combination of a 6x4
block of cells. This allows each lookup to "calculate" a 4x2 area of the
board.
The main system limit that this program runs up against is memory caching. The
code also has instrumentation to measure which lookup entries are the most
commonly looked up. I then used this information to sort the order of the bits
for the lookup index (the 6x4 cell block). I found the most optimal layout for
these bits so that the lookup table (which contains 16 million entries) is
sorted to minimize cache misses.
|
|
|
|