• The Idiot’s Tale
• Pac-MAS
• Super Beat Bros.
• WHAM Engine
• National Map Viewer
• Knapsack GA
• Navigation GA
• Pascal Compiler Front-End
• Distributed Arduino Orchestra
• CSP Data Visualization

The Idiot’s Tale

The Idiot’s Tale is an old-school point-and-click adventure game with a truly warped sense of humor.

You are Sir Jimothy Quest, a noble-but-ignorant knight-errant in the medieval kingdom of Dodotry. With your trusty sidekick Hoover the Owl, you’ll venture across the land in search of legendary lost treasures. Along the way, you’ll encounter fearsome monsters, classic fairy tale characters, corporate fast food, and more puzzles than you can shake your cursor at.

• Over eighty environments to explore!
• Dozens of brain-twisting puzzles! Guaranteed head-scratchers, hair-pullers, and nail-biters included!
• Built-in hint system to help you beat the game without consulting the Internet!
• Original jazz soundtrack for you to groove to as you cross the lands!

Can you find all three treasures and save the day? Or are you just gonna run away like an idiot?

Available now at Steam or itch.io!

---

Pac-MAS

An adaptive multi-agent system (MAS) version of Pac-Man, developed in Javascript using the Phaser.io HTML5 game engine. Created for the Self-Adaptive Systems course (CS-7863-01) at the University of Tulsa. Because it’s a web app, I’ve embedded it above!

The user can select a map for the Pac-Man MAS to solve, and set the number of agents in the system. After pressing the START button, the system will generate an initial plan to divide up the maze between the agents. While the game is running, the user may click on a Pac-Man to kill it, and the other agents will redistribute the remaining Pac-Dots originally assigned to the disabled agent. Alternatively, agents also have the ability to repair disabled agents, if it appears to be worth their time to do so.

Assets are either taken from the original 1980 Pac-Man (via Spriter’s Resource) or created by me.

---

Super Beat Bros.

A Java-based defense game about avoiding projectiles and dancing to funky beats.

The game is played by moving the Beat Bros’ van around with the WASD keys, and using the mouse to collect musical energy (from falling notes) and draw musical-energy shields. The shields block incoming alien projectiles, which increase in intensity as the game progresses. At times a wyrm will also appear, whose head must be clicked to vanquish him. A .jar file is provided for convenience of execution– all assets are packaged inside.

The bulk of the code base is adapted from Andrew Davison’s “Killer Game Programming in Java” example code. It can be found (as of 7/7/21) at the book’s website. The following classes were modified or created during the development of this game, building on some initial modifications made by Dr. Roger Mailler for his CS-3023 Intro to Game Programming class.

• BeatBrosGame, adapted from Davison’s WormChase class and Mailler’s modifications
• GameFrame, adapted from Davison’s GameFrame class and Mailler’s modifications
• entities.DefenseField
• entities.ExplosionSprite
• entities.MissileSprite
• entities.NoteSprite
• entities.PlayerSprite
• entities.Sprite, adapted from Davison’s Sprite class
• entities.Wyrm, adapted from Davison’s Worm class
• framework.GameMenu
• framework.RibbonsManager, adapted from Davison’s RibbonsManager class
• framework.ScoreTable
• sound.MusicManager

All art assets are original. Midi files are drawn from various sources around the net, which at this point I honestly cannot recall. Most sound effects from freesound.org, with explosion sounds from Andrew Davison’s examples.

---

WHAM Engine

C++ game engine programmed in 2012 for the Advanced Game Programming course (CS-5863-02) at the University of Tulsa. Contains (among other things) OpenGL rendering, memory management, and Bullet physics integration. Cleaned up for GitHub in 2015.

The code should compile on most Windows systems from the included Visual Studio solution.

Also incorporates headers, .lib’s, and .dll’s from multiple open-source libraries:

• OpenGLUT, for window management.
• Bullet 2, for physics.
• Assimp, for asset importing.
• RapidXML, for XML importing.

Assets are all original, except for the Sinbad model and the “BobLampClean” guard model.

---

National Map Viewer

Java software used to visualize USGS terrain survey data. Coded in Fall 2014 for the Fundamentals of Computer Graphics course (CS-6813-01) at the University of Tulsa. It provides a 3D contour plot visualization (TerrainVis.java), as well as a to-scale scene walkthrough (SceneWalkthrough.java). Executable JAR files are also included in nmvJars.zip.

Note that this project is dependent on JOGL for its rendering. I made use of this guide to quickly set up the dependencies in Eclipse.

Compatible terrain data for this project can be acquired from the USGS National Map viewer.

1. Use the map to find an area you’d like to download data for.
2. Click the “Download by Bounding Box” button in the toolbar above the map, and draw a bounding box around the area.
3. A pop-up window should appear with data options for the selected area. Choose “Elevation DEM Products” and press “Next”.
4. Find a GridFloat-format dataset to your liking and check the box. Highlighting different options will highlight the portion of your bounding box that the data pertains to.
5. Press “Next” to exit the pop-up window. The data you’ve selected will appear in the cart on the left-hand side of the menu.
6. Press “Checkout” and enter your email address to have the data sent to you.

Since this data is in the public domain, I’ve taken the liberty of including some data of the area surrounding Mt. Rainier in Washington. The data is compressed to conserve space.

Map services and data available from U.S. Geological Survey, National Geospatial Program. The “flare” and “grass” images included with the project are public domain, courtesy of Wikimedia Commons, while the flag is my own.

Wikimedia Images: Grass | Fire

---

Knapsack GA

This project includes both a genetic algorithm and a simulated annealing approach to solving the 01-Knapsack problem. In this problem, the goal is to take a set of P packages, each with a size S and value V, and select the correct subset of them that maximizes the total value of all selected packages, without allowing the total size of all those selected to surpass the knapsack capacity C. Both programs take command-line user inputs, and are intended to be run on the included datasets, which should be moved to the root directory. When specifying the dataset for the program to solve, the prefix before the underscore should be used.

JAR files encapsulating each program are included in the bin directory, with a group of compatible datasets. Each executable should be run using the associated batch file to provide the necessary command prompt and allow results to be viewed (at least on Windows).

The datasets prefixed “pXX_” were previously hosted at John Burkardt’s website and have since been retired. For these, The ‘c’ suffix indicates capacity, with ‘w’ for weight, ‘p’ for package value, and ‘s’ for optimal solution. A separate program (KnapsackGenerator) is included with this project which allows both toy problems and random problems to be generated in the same format but at a larger scale (though without the optimal solution, which is generally unknown). Some example output of this program is included in the bin directory and prefixed “mXX_”.

The fitness function for the genetic algorithm is a simple expression of the form f = V-(X*(P*(S-C)+O)), where:

• V is the total value of all items selected in the chromosome.
• S is the total size of all items selected.
• C is the knapsack capacity.
• X is 0 when S <= C, and 1 otherwise (to punish infeasible solutions)
• P is a per-unit-size penalty, derived from the highest value per unit-size ratio of any single package in the dataset.
• O is the penalty offset, calculated at about 1/3 of the value of all packages (designed to keep infeasibles from possibly outdoing the best feasibles found so far, without making them totally unfit)

The genetic algorithm allows the user to set:

• The initial population size
• The number of generations to run before termination
• The mutation rate of chromosomes
• The crossover rate of chromosomes

It also provides the following operators to choose from:

• Roulette Selection – Use the fractional fitness of each chromosome to make a biased random selection for crossover.
• Tournament Selection – Compare the fitness of two chromosomes randomly, without bias. Biasedly allow the more fit of the two to be selected K percent of the time.
• N-Slice Crossover – Generate N random, unique integers (between 0 and P-2, and N < chromosome length). Take each integer to represent a random “slice” point at which to swap alternating segments of the two parents.
• Uniform Crossover – Generate uniform-random bit strings which determine which of the two parent chromosomes each bit of the child chromosome is to be taken from.
• N-Point Mutation – Invert N random points in the chromosome.
• Bit-Inversion Mutation – Invert all bits in the chromosome.

The simulated annealing allows the testing parameters to be set at the start of each run. It includes a toggle which allows it to behave as a foolish hill-climber (i.e., no probability of taking poorer solutions), and also provides the following settings:

• The user can choose between an N-Point Perturbation, which inverts N random, unique points in the current solution, and N-Slice Perturbation, which picks N unique, random slice points (as above) and inverts half of the resulting segments.
• The user can set the cooling factor alpha, the time factor beta, the initial temperature T0, and the initial number of iterations I0.
• The user can set the fraction of the initial temperature at which to terminate the annealing process.

---

Navigation GA

C++ implementation of a genetic algorithm to solve a robot pathfinding problem, using an experimental chromosome structure. Coded in Spring 2014 for an Independent Study under Dr. Roger Wainwright at the University of Tulsa.

In this problem, a robot seeks to find a path from a starting position to some goal. We assume that the robot is roughly aware of the obstacles in its way, and structure our tests such that it must always travel from the upper-left corner of a map to the lower-right. This project was based on a master’s thesis written in 2004 by Kamran Sedighi, “Local Path-planning of an Autonomous Mobile Robot Using a Genetic Algorithm.” In that work, Sedighi used a chromosome that detailed a path in either column-wise or row-wise coordinates, and provided two opportunities to switch between coordinate-systems. The focus of my work was on performing experimentation with a new chromosome structure for the genetic algorithm, which allowed switching between coordinate systems at any point. We found that this made the pathfinding much more flexible overall. Finally, I determined that the worst-case scenario which should still be workable for this chromosome structure was a map which required the maximum amount of travel away from the straight line between the starting position and the goal. Some simple test cases can also thwart the algorithm by requiring too much backtracking, as mentioned in the report.

When run, the genetic algorithm allows the user to set:

• The initial population size
• The number of generations to run before termination
• The mutation rate of chromosomes
• The crossover rate of chromosomes

It also provides the following operators to choose from:

• Roulette Selection – Use the fractional fitness of each chromosome to make a biased random selection for crossover.
• Rank Selection – Rank the fitness of each chromosome, and make a biased random selection based on the resulting ordering.
• Tournament Selection – Compare the fitness of two chromosomes randomly, without bias. Biasedly allow the more fit of the two to be selected K percent of the time.
• N-Slice Crossover – Generate N random, unique integers (between 0 and P-2, and N < chromosome length). Take each integer to represent a random “slice” point at which to swap alternating segments of the two parents.
• Local N-Slice Crossover – The same as regular N-Slice, except that all slide points are chosen before the first collision point in the chromosome’s path. The intention was that this might help fix issues with chromosomes expending too many coordinates from their path early on.
• Uniform Crossover – Generate uniform-random bit strings which determine which of the two parent chromosomes each bit of the child chromosome is to be taken from.
• N-Point Mutation – Invert N uniform random points in the chromosome.
• Limited N-Point Mutation – The same as regular N-Point, except that all mutation points are chosen before the first collision point, as before.
• Gaussian N-Point Mutation – Invert N random points, selected from a Gaussian distribution with a mean around the first collision point in the chromosome (standard deviation is one-tenth of the chromosome length).

The simulated annealing allows the testing parameters to be set at the start of each run. It allows the user to choose between an N-Point Perturbation, corresponding to an N-Point Mutation for the GA, and the Limited and Gaussian variations as described above. Note that for the purposes of these tests, the other annealing parameters were hard-coded.

Files included in this project are:

main: Initial program I/O, and the main GA loop, with all GA operators. Also incorporates a simulated-annealing algorithm as a sanity check.

Trail: Represents a single path, as expressed by any given chromosome.

Chromosome: Interface for two chromosome types experimented with.

TurnPointChrom: Chromosome developed for this work.

CoordinateChrom: Sanity-check chromosome which simply specifies a fixed-length list X,Y coordinate pairs.

GANavigation: A Windows executable that allows users to specify parameters to the algorithm and run it on one of the supplied datasets. Test map file names should be specified relative to the executable’s directory.

results: Contains some sample results for the worst-case testing that I focused my work on, and a report for the conclusion of the study.

tests: Contains some test “map” files, in a straightforward ASCII representation, to run the algorithm on. Note that all maps are square, with a size encoded in the initial line of each file.

• Files prefixed corners are maps that exhibit worst-case traits for the chromosome structure we used (i.e., they require a large number of deviations from the “straight line” path to the goal).
• Files prefixed godugu are sample test cases taken from a work by Jagruthi Godugu, “Development of a Benchmark for Robot Path Planning.” These were meant to provide baseline tests for our algorithm.
• Files prefixed manikas are taken from a work by Theodore Manikas, “Genetic Algorithms for Autonomous Robot Navigation.” This work provided additional baseline tests.
• Files prefixed SearchSpace are taken from the dataset used by Thomas Geisler in “Autonomous Robot Navigation System using a Genetic Algorithm with a Novel Value Encoding Technique.”
• Other files were developed by me for specific testing needs.

---

Pascal Compiler Front-End

C implementation of the front-end for a Pascal compiler. Written September-December 2013.

This project is the front-end of a Pascal compiler, designed for a simplified version of the language. It consists of two main components, a lexical analyzer (lexical.c) that breaks up a source file into tokens, and a parser (parser.c) that leverages a decorated parse tree to understand the tokens and assign identifiers memory addresses. These are designed to be compiled as separate executables, and run in sequence. Together, they are able to identify any lexical, syntax, or semantic errors present in the source code. Example source code is included in the /src folder, and a build of the executables with the output for example.pas is included in the /build folder.

Note that reserved.txt is required for the lexical analyzer to run correctly.

The root of the repository includes a makefile for easy compilation, as well as an example source file to compile (example.pas), and the list of reserved words (the hard-coded input, reserved.txt). Once built, the compiler can be run using compile.bat, which simply executes lexical.exe and parser.exe in sequence. In Windows, this is done on the command line with either:

compile example.pas

or

lexical example.pas
parser

Once the compiler is run, the console will contain a trace of the compiler’s progress through the code. Output files are:

Lexical Analyzer:

• listing.txt – The primary output. Numbers each line in the source and adds notes for any lexical errors.
• symbolTable.txt – A listing of the symbols identified in the source and the memory addresses where each is stored.
• tokenFile.txt – A listing of the tokens detected in the source, with 1) the line number, 2) the lexeme, 3) the number of the token type, and 4) the attribute (here, assigned memory addresses, for identifiers only).
• tokenListing.txt – A formatted version of tokenFile.txt.

Parser:

• listing2.txt – The primary output. Adds notes of any syntactical or semantic errors in the source to listing.txt.
• symMemTable.txt – A listing of the symbols identified in the source, and the memory addresses assigned to each (according to the size of the identifier’s type in bytes).

---

Distributed Arduino Orchestra

Arduino program designed for a multi-agent system implemented across several Arduino boards. Created in 2014 for the Cyber-Physical Systems course (CS-7863-05) at the University of Tulsa. The system uses the simple Asynchronous BackTracking (ABT) algorithm to distribute role assignments in a musical ensemble on-the-fly (here, soprano, bass, and percussion). When role assignments are complete, the boards use synth outputs to perform the chord progression from Pachelbel’s canon.

Detailed project documentation is included. The original system was developed on LittleBits hardware (see http://littlebits.cc/). The library “pitches.h” was taken from the official Arduino tutorials hosted at https://www.arduino.cc/en/Tutorial/Tone.

---

CSP Data Visualization

A Python/Java project which leverages VTK to visualize the progress and results of DCSP algorithms. Programmed in 2014 for the Scientific and Information Visualization course (CS-6863-01) at the University of Tulsa.

Traces from individual solution runs are included with the project, as well as the Java code written to convert them to either OBJ or CSV data suitable for use in VTK. Transformed data is also included, with Python code used to visualize either the progress of the algorithms as an animation, or the final result as a fixed 3D mesh. Finally, the original report and presentation slides for the project are included, which provide additional documentation and example output images.

• The Java code may be run by executing CSPtoVTK.java, with the name of the data file to be transformed passed in as a program parameter, as long as the data is copied into the same folder.
• The Python code may be run after installing VTK (found at www.vtk.org), with the data in the same folder. The program was designed around VTK version 6.1.0.

Original CSP traces for the project make use of the format:

• Problem domain size, on one row.
• Total # constraints, on another row.
• Several columns, of which the first gives the number of satisfied constraints at each time step, while the others give the value selected by each variable at each time step.

Processed CSP traces are stored in CSV files and simple Waveform OBJ files.