Roto-Mortar: A 7-Day Lisp Game March 26th, 2010
Patrick Stein

Roto Mortar was written for the 2010 LISP Game Design Challenge. The challenge was to design and implement a game in seven days using some LISP dialect.

The KPs have been beating on your base all week. Your defenses are just about to collapse. In fact, your mortar cannons are both on the fritz. Billy Bob, the ACME Repair Guy, has just gotten one of your mortar cannons back online. Unfortunately, he had to wire things a little wonky. Your cannon is spinning all on its own. You’ve only got one button to control both the elevation of the cannon and when to fire it. And, you better fire it, because the KPs are still coming at you.

Inspiration

A few years ago, I read the book Game Design Workshop: Designing, Prototyping, and Playtesting Games. One of the exercises in the first chapter is to design a game with a “one-button interface”. At the time, I didn’t come up with anything particularly thrilling.

When I started brainstorming what to do for this Game Challenge, I remembered that exercise. I came up with this concept just under (as in 3.5 hours under) seven days ago. The game is nowhere near as polished as I’d like… but it was a 7-day thing. And, it was fun to take a break from Objective C to get back to some Lisp programming.

Obtaining It

You can find out more about the game, including where to get the source and a Mac OS X binary, on the game’s web page.

XML Parser Generator March 16th, 2010
Patrick Stein

A few years back (for a very generous few), we needed to parse a wide variety of XML strings. It was quite tedious to go from the XML to the native-language representations of the data (even from a DOM version). Furthermore, we needed to parse this XML both in Java and in C++.

I wrote (in Java) an XML parser generator that took an XML description of how you’d like the native-language data structures to look and where in the XML it could find the values for those data structures. The Java code-base for this was ugly, ugly, ugly. I tried several times to clean it up into something publishable. I tried to clean it up several times so that it could actually generate the parser it used to read the XML description file. Alas, the meta-ness, combined with the clunky Java code, kept me from completing the circle.

Fast forward to last week. Suddenly, I have a reason to parse a wide variety of XML strings in Objective C. I certainly didn’t want to pull out the Java parser generator and try to beat it into generating Objective C, too. That’s fortunate, too, because I cannot find any of the copies (in various states of repair) that once lurked in ~/src.

What’s a man to do? Write it in Lisp, of course.

Example

Here’s an example to show how it works. Let’s take some simple XML that lists food items on a menu:

<menu>
        <food name="Belgian Waffles" price="$5.95" calories="650">
                <description>two of our famous Belgian Waffles with plenty of real maple syrup</description>
        </food>
        <!-- ... more food entries, omitted here for brevity ... -->
</menu>

We craft an XML description of how to go from the XML into a native representation:

<parser_generator root="menu" from="/menu">
  <struct name="food item">
    <field type="string" name="name" from="@name" />
    <field type="string" name="price" from="@price" />
    <field type="string" name="description" from="/description/." />
    <field type="integer" name="calories" from="@calories" />
  </struct>

  <struct name="menu">
    <field name="menu items">
      <array>
        <array_element type="food item" from="/food" />
      </array>
    </field>
  </struct>
</parser_generator>

Now, you run the parser generator on the above input file:

% sh parser-generator.sh --language=lisp \
                           --types-package menu \
                           --reader-package menu-reader \
                           --file menu.xml

This generates two files for you: types.lisp and reader.lisp. This is what types.lisp looks like:

(defpackage :menu
  (:use :common-lisp)
  (:export #:food-item
             #:name
             #:price
             #:description
             #:calories
           #:menu
             #:menu-items))

(in-package :menu)

(defclass food-item ()
  ((name :initarg :name :type string)
   (price :initarg :price :type string)
   (description :initarg :description :type string)
   (calories :initarg :calories :type integer)))

(defclass menu ()
  ((menu-items :initarg :menu-items :type list :initform nil)))

I will not bore you with all of reader.lisp as it’s 134 lines of code you never had to write. The only part you need to worry about is the parse function which takes a stream for or pathname to the XML and returns an instance of the menu class. Here is a small snippet though:

;;; =================================================================
;;; food-item struct
;;; =================================================================
(defmethod data progn ((handler sax-handler) (item food-item) path value)
  (with-slots (name price description calories) item
    (case path
      (:|@name| (setf name value))
      (:|@price| (setf price value))
      (:|/description/.| (setf description value))
      (:|@calories| (setf calories (parse-integer value))))))

Where it’s at

I currently have the parser generator generating its own parser (five times fast). I still have a little bit more that I’d like to add to include assertions for things like the minimum number of elements in an array or the minimum value of an integer. I also have a few kinks to work out so that you can return some type other than an instance of a class for cases like this where the menu class just wraps one item.

My next step though is to get it generating Objective C parsers.

Somewhere in there, I’ll post this to a public git repository.

Burnt Paper plugin for GIMP February 16th, 2010
Patrick Stein

Yesterday, I decided to make the images in my article look like they were on old, burnt paper. I did this manually in the GIMP.

I liked the effect, but I didn’t want the tedium of having to do all n steps manually next time I go to use it. So, I wrote a GIMP plugin script to do it.

Here is an example of the plugin script in action. As you can see, I started with a text layer and a selection that was bigger than the text layer. The plugin uses the selection size as original edge of the paper (original, as in before the paper was burned).

And, here is the resulting image:

Here is the Burnt Paper plugin script. Plop this in a directory that’s in your script search path and refresh GIMP’s scripting and then you’ll find it in the Filters > Decor menu. [You can see the script search path by going to Edit > Preferences and selecting Scripts under Folders in the left sidebar. And, you can refresh the scripts by going to Filters > Script-Fu > Refresh Scripts.]

Finding the Perfect Hyperbola February 15th, 2010
Patrick Stein

For an application that I’m working on, I needed a way to scale quantities that range (theoretically) over the real numbers (though practically are probably between plus and minus three) into positive numbers. I wanted the function to be everywhere increasing, I wanted f(0) = 1, and I wanted control of the derivative at x = 0.

The easy choice is: f(x) = e^{\alpha x}. This is monotonically increasing. f(0) = 1 and f^\prime(0) = \alpha.

I needed to scale three such quantities and mush them together. I thought it’d be spiffy then to have three different functions that satisfy my criteria. The next logical choice was f(x) = 1 + \mathrm{tanh} (\alpha x). It is everywhere positive and increasing. And, it has f^\prime(0) = \alpha.

Now, I needed third function that was always positive, always increasing, had f(0) = 1 and f^\prime(0) = \alpha. One choice was: f(x) = e^{e^{\alpha x} - 1}. But, that seemed like overkill. It also meant that I really had to keep my \alpha tiny if I didn’t want to scale things into the stratosphere.

Playing with hyperbolas

So, I thought… why don’t I make a hyperbola, rotate it, and shift it so that the apex of one side of the hyperbola is at (0,1). And, I can adjust the parameters of the hyperbola so that f'(0) = \alpha. After a variety of false starts where I tried to keep the hyperbola general until the very end (\frac{x^2}{a^2} - \frac{y^2}{b^2} = r^2, rotated by \theta degrees, and shifted by \beta), I quickly got bogged down in six or seven incredibly ugly equations in eight or nine variables.

So, it was time to start trying to make it easy from the beginning. I noticed that if was going to rotate it by an angle \theta in the clockwise direction, then I needed \phi = \frac{\pi}{2} - \theta to be such that \tan \phi = \alpha if my slope was going to work out right in the end. So, I’m looking at the basic triangle on the right then to determine all of my sines and cosines and such.

Based on that triangle, it was also obvious that the asymptote for my starting hyperbola had to have \frac{b}{a} = \frac{1}{\alpha}. I played around a bit then with making a = \alpha and b = 1. In the end, I found things simplified sooner if I started with a = 1 and b = \frac{1}{\alpha}.

I also needed r to be such that the point (-r,0) rotate up so that its y-coordinate was 1. This meant that r \sin \theta = 1 or r = \frac{1}{\sin \theta} = \sqrt{1 + \alpha^2}.

So, my starting hyperbola then was: x^2 - \alpha^2 y^2 = 1 + \alpha^2.

From there, I had to rotate the x and y by \theta in the clockwise direction. This gave me:

(x\cos\theta - y\sin\theta)^2 - \alpha^2 (x\sin\theta + y\cos\theta)^2 = 1 + \alpha^2

A little multiplying out leads to:

(x^2\cos^2\theta - 2xy\sin\theta\cos\theta + y^2\sin^2\theta) \\ - \alpha^2(x^2\sin^2\theta + 2xy\sin\theta\cos\theta + y^2\cos^2\theta) = 1 + \alpha^2

From there, using cos^2\theta = \frac{\alpha^2}{1 + \alpha^2}, sin^2\theta = \frac{1}{1 + \alpha^2}, and \sin\theta\cos\theta = \frac{\alpha}{1 + \alpha^2}, we come to:

\frac{-2\alpha(1 + \alpha^2)xy + ( 1 - \alpha^4 )y^2}{1 + \alpha^2} = -2\alpha{}xy + (1 - \alpha^2)y^2 = 1 + \alpha^2

The only step remaining was to shift it all over so that when y = 1, we end up with x = 0. Plugging in y = 1, we see that -2x\alpha + 1 - \alpha^2 = 1 + \alpha. That equation balances when x = -\alpha. We want it to balance when x = 0, so we’re going to substitute (x - \alpha) in place of the x in the above equation to get:

-2\alpha(x - \alpha)y + (1 - \alpha^2)y^2 = 1 + \alpha^2

We can easily verify that the point (0,1) is on the curve. And, we can implicitly differentiate the above to get:

-2\alpha(x - \alpha)\frac{dy}{dx} - 2\alpha{}y + 2(1 - \alpha^2)y\frac{dy}{dx} = 0

Plopping x = 0 and y = 1 in there, we find that \frac{dy}{dx} = \alpha.

This is pretty good as it goes. The only step is to complete the square to find a nicer expression for y in terms of x. We start by adding \left[ \frac{\alpha}{\sqrt{1 - \alpha^2}} (x - \alpha) \right]^2 to both sides to get:

\left[ \sqrt(1 - \alpha^2)y - \frac{\alpha}{\sqrt{1 - \alpha^2}(x - \alpha)} \right]^2 = 1 + \alpha^2 + \frac{\alpha}{1 - \alpha^2} (x-\alpha)^2

This is easy enough to solve for y by taking the square root of both sides and shuffling some things about:

y = \frac{\alpha}{1 - \alpha^2}(x - \alpha) + \frac{1}{\sqrt{1 - \alpha^2}} \sqrt{1 + \alpha^2 + \frac{\alpha^2}{1 - \alpha^2}(x - \alpha)^2}

Here are all three curves with \alpha = \frac{1}{4}. The exponential is in black, the hyperbolic tangent is in red, and the hyperbola is in blue:

The first image on the page here was made with Zach’s Vecto library with some post-processing in the GIMP. (Here is the source file: hyperbola.lisp.) The second image was made entirely within the GIMP. And, the last image was made using Foo Plot and the GIMP.

Submitted small bug-fix to iPhone Spelling Toy February 10th, 2010
Patrick Stein

I just uploaded the first update to my iPhone Spelling Toy. The update includes two minor changes:

  • Corrected spelling of siete (Spanish for seven)
  • Corrected spelling of colores (Spanish for colors)

Today, I am working on adding animal drawings.

Updates In Email

Email:

RSS Feeds

l