On Memory Hogs and Compression, Part 1.

A line I picked up from one of my high school Computer Science teachers: “Graphics are memory hogs.” Computers represent pictures as a big grid of colors. Each cell in this grid is called a pixel (short for “picture element”), and usually has an ordered triple of numbers representing what color it should be.  When these pixels are very small and numerous, the picture looks less like a collection of squares, and more like the picture represented.  A similar effect is used to shade and color graphics in newspapers; look closely enough and you’ll notice that the colors are made up of lots of tiny colored dots.  Let’s look at an example…

Done purely for the Hack Value.

Several emulated video games running on the sides of a Compiz desktop cube

Hooray for the PC. Nobody would actually play like this, mind you, but the fact that they all run without conflict is certainly impressive-looking!
I’d say “see if you can name all the games!” but many of them are showing title screens. See if you can name all the consoles being emulated!

Constructing an 8-bit music application for the NDS.

I’ve started to code an 8-bit music tool, inspired by the work of 8-bit artists like Bit Shifter and Bubblyfish, both of whom were brilliant to see live at the concert of Stevens Anime Club’s annual Castle Point Anime Convention earlier this year. The two aforementioned musicians compose and perform their music on the Nintendo Game Boy (as do many other 8-bit musicians), using its PSG to generate the blips and beeps of various frequencies that make up their songs.

The Game Boy Advance is generally used for this, presumably the last of the “Game Boy” series of hardware from Nintendo, because it has hardware backwards-compatibility to all the software of the original Game Boy, and because the older Game Boys are just that–older, harder to come by, and more likely to be broken.

The Nintendo DS isn’t backwards-compatible with the older Game Boy software, but it is backwards-compatible with GBA software. Since the GBA exposed the original Game Boy’s PSG to GBA-specific software, the DS must also provide that functionality, so the same type of PSG was included in the DS hardware. This is fortunate, since the DS is relatively easy to develop for, thanks to devkitPro. An example of the use of the PSG in the DS can be found in the very nifty AXE, written by PinEight.

I have no experience with other existing 8-bit music composition software, but I do have knowledge of music theory (thanks to my brilliant professor Andy Brick, who coincidentally has composed and conducted quite a bit of video game music–check it out!), and I am trying to work both of these facts to my advantage in an effort to make a unique and useful interface for my application. One of my ideas for a user interface involves a selection of chords that would be valid in syntactic progression, where the program takes care of all the voice leading rules after the user has given all the specifics of what he or she wants to be used.

There are some other ideas floating around in my head, too. For now, the interface is very simple: a proof of concept using Zelda 64 “Ocarina-like” controls (the C-buttons map to A, B, X, and Y, and the A button maps to the DS’ R). I’ll post more on this project as I make progress on it. In the meantime, check out some of Bit Shifter’s Information Chase album, available for download for free! (In MP3 format, I know, I’m sorry)

Finding the most efficient way to be a college student during the summer

Throughout the course of my stay at Stevens, I’ve found that, as a college student, one of the most important things to know (if not the most important thing) is where and how I’m going to get my next pizza.

In a normal semester, there are many events run by student organizations, clubs, and the like, where each use part of their budget to get some pizzas to attract more people to their events. This is the most cost-efficient way to obtain pizza (short of someone finding some way to get paid to eat pizza (I’m all ears–if you’ve heard of anything like this, please comment)). It’s also good because the pizzas often come from one of the many fine pizza restaurants in Hoboken.

The second-most efficient method relates to the dreaded meal plan. Any student here living in on-campus housing that doesn’t have a kitchen in his or her room, with certain exceptions, has to be on the meal plan. The meal plan has you pay a constant price up front for an “unlimited” number of times to be let in to the dining hall. The dining hall has an all-you-can-eat buffet, with pizza and various other foods (that rotate day to day). The pizza is okay, I certainly don’t expect to hold it up to proper Hoboken Italian restaurant standards; that would be rather ridiculous to expect of a campus dining hall. But if it’s already been paid for, cashing in on the meal plan is a viable method by which to acquire pizza.

Unfortunately, there’s not always a free-pizza event going on, especially during the summer. Worse yet, the dining hall is closed during the summer. This means the pizza money has to come out of my own pocket. There are many places to choose from here, and I need to determine how I can get the most pizza for the least amount of money. So, I wrote a small, trivial application in C++ (which should be understandable to beginners) that compares an arbitrary number of pizza places based on the amount of pizza you get for the price you pay (per slice).

#include <algorithm> // for sort()
#include <iostream> // for simple i/o
#include <cstdlib> // this is really only here for aesthetic purposes
#include <vector> // nicer to use than arrays, especially with stl algorithm
#include <cmath> // for M_PI

struct pizza_attribs {
	int num;  // index so we know who's the best after sorting
	int slices;  // the number of pieces, not the number of cuts.
	float diameter; // width of the pie
	float slice_cost;  // slice price
	float bang_for_buck;  // = (slice area)/price
};

using namespace std;

bool pa_compare(pizza_attribs a, pizza_attribs b) {
	return a.bang_for_buck > b.bang_for_buck;
}

int main() {
	vector<pizza_attribs> pa_list;
	int count;

	cout << "Be consistent with your units!" << endl << endl;
	cout << "How many places to compare? ";
	cin >> count;
	for(int i = 0; i < count; ++i) {
		pizza_attribs pie;

		pie.num = i;
		cout << "[pizza place #"<<i<<"] Price of a slice of pizza? ";
		do { cin >> pie.slice_cost; } while(pie.slice_cost <= 0);
		cout << "[pizza place #"<<i<<"] Number of slices in a pie? ";
		do { cin >> pie.slices; } while(pie.slices <= 0);
		cout << "[pizza place #"<<i<<"] Diameter of the pie? ";
		do { cin >> pie.diameter; } while(pie.diameter <= 0);

		pie.bang_for_buck = ((M_PI*pow(pie.diameter/2, 2))
		                     / pie.slices) / pie.slice_cost;

		pa_list.push_back(pie);
		cout << endl;
	}

	sort(pa_list.begin(), pa_list.end(), pa_compare);

	cout << "The results are in!" << endl;
	for(int i = 0; i < pa_list.size(); ++i) {
		cout << "[pizza place #"<<pa_list[i].num<<"] bang for buck: "
		  << pa_list[i].bang_for_buck/pa_list[0].bang_for_buck << endl;
	}

	return 0;
}

For example, the two closest pizza places to me right now are Benny Tudino’s and H&S Giovanni’s. Benny’s slices are taken from a 28-inch pie, sliced into 8 pieces, and cost $3.00 apiece. Gio’s slices are taken from a 22-inch pie, sliced into 8 pieces and cost $3.00 apiece (one can already intuitively figure out that you’d get more pizza from Benny’s). According to this program, you get an estimated 61.7% of the pizza at Gio’s that you would at Benny’s.

Now, this program makes some unreasonable assumptions: Namely, it assumes that all pizzas are of the same thickness, and it doesn’t factor in how good the pizza tastes. However, it makes objectively comparing pizza slices by area versus price a little bit easier.

TODO: Factor in distance to restaurant?

The Obsolescence of Tool-Assisted Speed-running

(And later, its adaptation into an exercise in human computing and cooperative single-player gaming)

Some time ago, navaburo and I were hanging out in my dorm room, and we ended up thinking about the concept of writing an AI to find the best (shortest) path through a video game. A couple days later, we went down to the Linux Lab and fleshed out the idea on paper.

For those unfamiliar with the concept of “Tool-Assisted Speed-running,” it is a process done by some video game enthusiasts in which they play a game on a an emulated (or “virtual”) machine, using special features of the emulator to let them more easily make an almost “perfect run” of the game, where they complete the primary objective as quickly as possible. This usually involves slowing down the game to give them the opportunity to take shortcuts and pull off maneuvers that wouldn’t have been possible with the limitations of human reaction time and reflexes. Sometimes, they also use “luck manipulation,” which involves taking a snapshot of the machine’s state (also known as a “savestate”) before an event that relies on a “random” number, and restoring the machine to that state again and again, until a desired number is generated. Similarly, they often use this functionality to rewind the gameplay in case they make a mistake. When a speed-runner completes a game this way, he or she might post a replay of the “run” on the internet to share with others; there are communities on the web in which speed-runners will compete to complete classic video games with the fastest times they can manage.

navaburo and I theorized that, using an emulator for a given video game console, we could calculate the fastest possible path through the game by using a search on all of the possible inputs starting from the machine’s initial state. This is most likely very impractical to compute, even for the relatively sophisticated computer hardware we have today. Nevertheless, we decided that as long as we could provably calculate the optimal path to do some trivial task, we could also calculate the optimal path to the very end of the game. For proof of concept, we decided on Super Mario Bros. for the NES, and we’d call the program “OptiMario.” We spent some time looking into ways to bootstrap our search into the input functions of various open-source NES emulators, including the popular FCE Ultra and Nestopia, before deciding that for our purposes, the simpler (and lesser-known) NEStra would suffice. So far, we’ve hacked the beginnings of a foundation for this project into NEStra.

I won’t go too much into our methods just yet, mostly because we still haven’t implemented it and the exact method we end up using might change. However, in theory, it seems we might be able to create an artificial “ultimate speed-runner” that is able to complete a game in the fastest possible time, perhaps even using glitches and shortcuts previously unknown (if it can be done with a valid input string, and it shaves seconds off the final elapsed time, such a program (properly implemented) will find it).

Hello World!

++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.

So good of you to join me. I’ll be posting here about my various projects and whatever else I think is interesting enough to post.