Posts Tagged ‘python’

Towards a Python Based Domain Specific Language for Interactive Fiction

March 1st, 2014

Several years ago I wrote an Interactive Fiction game. (To be clear, I mean the sort of game where you type things like TAKE ROCK, or GO NORTH, and the game obligingly responds by allowing (or not allowing) the player character to do so, and then reports the results in prose.) Since then, I have not written another. There are quite a few reasons for this, but one of them is that there really aren’t any IF authoring systems that I like. In particular, Inform 7, the system that has received the majority of the mind share for IF in recent years, uses syntax that approximates English text as nearly as possible, which makes it very easy for a newbie to understand, but can seem frustratingly verbose and unstructured to an experienced programmer. While there are other systems around, most of them use languages that were built from scratch for the purpose of IF authoring. I personally would prefer to be using a general purpose language; Python is my favorite, and the one I have the most experience with in recent years. A system that used Python could leverage the existing skills of programmers, and allow the use of code libraries that have already been written.

As it happens, there is already at least one IF authoring system that uses Python. In 2011 Nick Montfort released Curveship, an IF development system that was mostly intended as a testbed for some of Montfort’s ideas about dynamic text generation. Unfortunately, reading the code of a sample game written with Curveship reveals what should have been obvious to me: Python, as a general purpose interpreted language, is actually pretty poorly suited for the task of IF authorship. The contortions that it takes to write a game using Curveship are in fact pretty reasonable under the circumstances, but in my opinion they are bad enough to keep it from being a respectable option for writing an IF game of any length.

Nevertheless, reading that sample game code prompted me to consider what syntax I would want to see in a Python based IF development system. I recognized that it might take some tricky hacks to make that syntax achievable, and in some cases there might need to be compromises with what the language “wants”. But I’ve come to the position that we can get to a language syntax that is reasonably concise and readable. In outlining my proposed syntax, I was guided by the constructs present in Inform 6, (which, despite sharing a name and a lead developer with Inform 7, is a very different system, and more like a traditional programming language.) In my opinion, Inform 6 does a lot of things right, in that the sorts of things you want to write as an IF programmer can be done concisely. Unfortunately, many of the actual symbol characters you type in Inform 6 are different from the ones you would use in any language in the whose syntax falls into the same lineage as C, so for a programmer, it can give a feeling of being a “crazy moon language” until you get used to it.

The sample game code that I mentioned previously was an implementation of Roger Firth’s Cloak of Darkness, a short game that has been translated into many IF languages so that prospective authors can judge their features and syntaxes. Here is an excerpt of Cloak of Darkness in my proposed syntax:

class Foyer(Room):
    name = "Foyer of the Opera House"
    desc = "You are standing in a spacious hall, splendidly decorated in red \
            and gold, with glittering chandeliers overhead. The entrance from \
            the street is to the north, and there are doorways south and west."
    dirs = {
        west: cloakroom,
        south: bar
        }

The first thing to notice is that here, as for every unique object or thing in the game, we will be defining a class. One of the unusual things that distinguishes IF programming is that the vast majority of objects that are written are one-offs. We won’t be creating multiple Foyer objects; we can assume that we will only ever need one. Because of this Inform 6 does not require a separate step to instantiate an object. (You can create classes that are not automatically instantiated, but this is not the usual case.) Python, by contrast, does not autoinstantiate. But we can get around that using Python’s metaclass mechanism, which allows us to change how classes work at class definition time.

class Cloakroom(Room):
    desc = "The walls of this small room were clearly once lined with hooks, \
            though now only one remains. The exit is a door to the east."
    dirs = {
        east: foyer
        }

A couple of things to notice here: first, the Foyer class refers to the cloakroom object before we have even defined it. This is not actually possible in Python. But allowing forward references like this is quite desirable! IF games usually contain a web of objects that can interact with each other in various ways, and having to arrange code so that it contains no forward references would be a real hindrance. Can we get around the problem? I’m pretty sure we can, actually. Python’s ast (abstract syntax tree) module allows you to modify parsed Python code before you run it. It should be possible to scan for classes and make dummy objects for each class, so the illegal forward references will actually be perfectly legal backward references, which should, if we can pull this off, turn into forward references again when we define the referenced object. (We may still need to be careful that we don’t access variables and methods of later objects at initialization time, but this should be doable.)

The second important thing to point out here is that the “cloakroom” object was named in lowercase, while the Cloakroom class was upper case. I wanted the autoinstantiator to give a name for the object that does not interfere with the name for the class, so I’m having it take the lowercase of the class name. You might well be wanting to refer to either the object or the class later. (This does mean that lowercase names for game object classes will be illegal.) Moving along:

class Cloakroom(Room):
    desc = "The walls of this small room were clearly once lined with hooks, \
            though now only one remains. The exit is a door to the east."
    dirs = {
        east: foyer
        }

class Hook(Thing):
    name = "small brass hook"
    nouns = ["peg"]
    def desc(self):
        "It's just a small brass hook, "
        if cloak.parent == self:
            "with a cloak hanging on it."
        else:
            "screwed to the wall."

Notice that the hook is meant to be an object in the Cloakroom. Since it is natural for us to list the things in a room after describing the room itself, we will automatically put each Thing into the last Room in the code. Sometimes you won’t want that. For those cases, there will be a location attribute that you can set. In addition to being able to explicitly set the location, I want one to be able to set it to a dummy object called Above that would cause an object to be contained in the last mentioned thing. I’ll probably want some more tricks for placing things in the object containment tree. This is going to take some careful thought.

The other thing that’s going on here is that I’m borrowing the automatic printing of bare string expressions from Inform 6. Bare strings are perfectly legal in Python; they just don’t do anything. I’m actually changing the semantics from how it works in Inform 6. In inform 6, bare strings automatically print a newline, and then return True. I’m not convinced this is a win. It means you have to use print statements instead of bare strings half of the time, and you frequently get burned if you pick the wrong one. The implicit return saves you the effort of typing “else” if you use a bare string in an if clause, but at the cost of making the code more difficult to understand. Since we aren’t outputting newlines in the places where we would usually be implicitly doing so in Inform 6, we’ll have to be careful that the system does it for us. Getting newlines right is actually a more non-trivial problem than you would think, but I think it’s doable. (Turning bare string expressions into calls to a printing function would require another ast hack.)

Finally, I’ll skip a bit ahead to get to another language feature I would want:

class Cloak(Clothing):
    name = "velvet cloak"
    location = player
    containment = worn
    nouns = ["handsome", "dark", "black", "satin"]
    desc = "A handsome cloak, of velvet trimmed with satin, and slightly \
            spattered with raindrops. Its blackness is so deep that it \
            almost seems to suck light from the room."
    used = False
    def enact(self):
        if +cloakroom:
            if +drop or (+put and +on):
                bar.lit = True
                if self.used == False:
                    score += 1
                    self.used = True
        if +take:
            bar.lit = False

Notice the presence of the unary plus operator. This is used as an implicit comparison. For any given built in class of objects, there will be a variable whose value corresponds to the “obvious” instance of that class that one might currently want to check against. The implicit comparison will return True if it is being applied to that object, otherwise False. For rooms, the implicit comparison checks the player’s location. For actions, it checks the current action. For things, it checks the indirect object of the action, (the assumption being that we are most likely in a method belonging to the direct object) and for prepositions, it checks the current preposition object. (Sometimes you will be in a method belonging to the indirect object and you will want to check the direct object. I’m still not sure whether making the implicit comparator work in this case is reasonable, or whether we should fall back to an explicit comparison.)

This feature is based on the implicit switch feature in Inform 6, but it works in any context, and should feel like less of a kludge. Since we used unary plus for the explicit comparison, it seems elegant to use unary minus for the negation of the comparison. In terms of implementation, operator overloading should work in a pretty straightforward manner here.

Finally, I want to point out what’s going on with the name and nouns attributes. The name attribute is what the system would print out, when listing an item in your inventory, or when outputting the result of an action, e.g., “You take the velvet cloak.” The nouns attribute contains the words that the parser will accept as referring to an object. Notice that the words in the name are not present in the nouns; we’ll automatically put them there at load time, since you will pretty much always want them there. Inform 7 goes a step farther, making the identifier in the code the same as the printed name and the list of words accepted by the parser. If you’re a programmer, you’re probably shrieking in horror at the notion of identifiers containing spaces. So we won’t go there.

I should stress that none of this actually exists. The tricks required to get Python to accept my syntax modifications would be fairly trivial compared to the work of writing, from scratch, an IF library capable of parsing commands, manipulating a world model, and being extensible by game authors in ways that they will need. A front end that displays the game being played in an attractive fashion would also need to be written, although for that purpose, the existing code base of libraries written in Python would be very helpful. I don’t know that I will actually follow through with this. But whether I do or not, I hope some people will find this a useful thought experiment in the realm of what an IF language syntax could look like.

After the cut, for the curious, is the complete code for Cloak of Darkness in my proposed syntax:
» Read more: Towards a Python Based Domain Specific Language for Interactive Fiction

Children of Julia Sets

August 23rd, 2011

Here’s a pretty specimen I found while playing with a bit of code I wrote to produce quadratic Julia sets:

If you know your Julia sets, you might be thinking something odd is going on here.

If you don’t, here’s a quick primer.

Pick a complex constant c. Then for every point z in the complex plane, create a sequence with the following recursive definition:

z
0 = z
zn+1 = zn2 + c

This sequence will do one of two things. Either it will zip away from 0 and eventually go indefinitely far away, or it won’t. (It could converge to a single point, or alternate between a few points, or bounce around chaotically. It doesn’t matter.) The points where the sequence sticks around near zero form a quadratic Julia set. There are other kinds of Julia sets, defined using different formulas. But the kind of Julia set you will most commonly encounter is this one, and henceforward I will use the term Julia set to refer to this kind of Julia set.

Julia sets are fun to play with because they are fractals, with infinite levels of detail and self-similarity. Some Julia sets form a single connected blob:


Julia set for c = .3 + .2i

Other Julia sets form dusts, where any region that appears to be in the set is actually divided into separate disconnected regions, and these regions are themselves divided, ad infinitum:


Julia set for c = .7 + .33i

I should note that I’m cheating here slightly. A dust isn’t actually much to look at. Although it contains an infinite number of points, the probability of an individual point being in a dust-like Julia set is 0, so if I were plotting it properly, there would be nothing to see. What I’m actually plotting for each point is a level of grey on a scale from 0 to 255 (the latter being black) corresponding to the number of iterations it took for the sequence to escape beyond a given bound. The use of a grayscale gives dusts a more organic look, which I rather like.

Every Julia set is either a dust or a blob. The famous Mandelbrot set effectively catalogs this aspect of Julia sets. For every possible constant c, one checks only the behavior of 0 in the Julia set for that constant. If 0 escapes to infinity, we have a dust, otherwise we have a blob.  Near the boundary, the blob thins into increasingly narrow filaments, but it remains in a single connected piece until the boundary is crossed, and the blob shatters into a dust. The Mandelbrot set contains all of the constants that give “blob-like” Julia sets.


The Mandelbrot Set

Getting back to my first image in this post, you can now see why I said there was something odd about it. That fractal is not a single blob; there are many disconnected parts. But it also isn’t a dust; there are filled solid regions. So it can’t be a proper Julia set. But it does have a Julia set “feel” to its self-similarity. So what’s going on?

The answer is that instead of using a single constant at every step of iterating the sequences for each point, as one would for a proper Julia set, I alternated between two constants. In fact, the two constants I alternated between were precisely the constants for the blob and dust I showed above. Thus it is perhaps unsurprising that the “child” of a blob and a dust would show characteristics of each: those characteristics were in its “genes”.

Alternating between the two constants in the opposite order gives the following:

Looks like the same basic pattern as before, but with two big connected bits instead of one. Notice that in this one the center point (z=0) is outside the set, while for the other one it was inside the set. Since this is the point that would tell us if we had a blob or a dust in a normal Julia set, it feels appropriate that it can go either way depending on the order here.

Here’s the Python code that produced the last image:

from PIL import Image
size = 400
im = Image.new("RGB", (size, size))
c = [.3 + .2j, -.70 + .33j] #j is i in python
for x in xrange(size):
    for y in xrange(size):
        z = x * (4.0 / size) - 2 + (y * (4.0 / size) - 2) * 1j 
        i = 0
        while abs(z) < 4 and i < 256:  
            z = z ** 2 + c[i % 2]
            i += 1
        im.putpixel((x,size-y-1), (255-i,255-i,255-i))

im.save("julia6.png")

A Semimagic Magic 45-omino

March 1st, 2011

Bryce Herdt has found a solution to problem #21:

The shape of the darker region is “magic” because the number of cells in each 3×3 block corresponds to a number in a magic square, while the number of cells in each row, column, and main diagonal is 5. The sum of the numbers in each row and column is 115.

There’s still room for improvement here: note that the diagonals do not add up to the magic sum. (A mostly magic square with this property is called semimagic.)

Problem #21.1 Find a magic magic 45-omino, as above, but with diagonals adding to the magic sum.

It’s interesting that this solution was found by manually tweaking the output of a program that I wrote to solve the problem. I was never able to get the program to find an actual solution, so I had it give up after a certain number of trials and output the best near solution. There may well be a large number of solutions, but the search space is enormous.

It’s pretty simple to get fairly close by picking a random permutation of numbers and repeatedly swapping them around to get sums closer to the magic sum. But getting from this local minimum to a real solution is the hard part. The problem would seem to call for something like simulated annealing, and indeed I found a reference to a magic square finder algorithm using something similar. (It should be noted that if all you want is a magic square of a given size, there are deterministic methods that will get you one very quickly.) I added a hack to my code to make it do a crude version of this, but it doesn’t seem to have helped much. (The near solution that Herdt fixed up was made with the old version of the code.)

Feel free to look at my solver code (in Python). I do wonder if there is some way it can be fixed up to be better at getting from near solutions to real solutions.

Polyiamond Minimal Succinct Covers

February 2nd, 2011

My first particularly interesting and novel discovery in the field of polyforms was what I call the minimal succinct cover problem. The basic minimal cover problem, which I introduced in a previous post, is to find the smallest shape into which a each of the polyforms in a set (e. g. the 12 pentominoes) could fit. A succinct cover is a shape or set of shapes into which each of the polyforms in a set can fit in exactly one way. Several years ago I wrote a program in Python to find minimal succinct polyomino covers, and shortly thereafter I extended it to handle polyhexes. But at the time I left off handling polyiamonds, because of the three regular planar tessellations, (square, hexagonal, and triangular) the triangular one is the trickiest to program.

Still, it was about the lowest hanging fruit around as far as results of mine to extend go, and since I recently blogged the minimal hexiamond cover problem, it seemed only natural to look at minimal succinct polyiamond covers now, so I hacked on my code to add them.

Here’s a minimal succinct cover of the hexiamonds:

Notice that the hexagon must appear as a separate piece in a succinct cover. As a result of its symmetry, whenever you add a cell to it, the resulting heptiamond will fit a couple of hexiamonds in two different ways. (The X pentomino has an analogous position in a succinct pentomino cover.)

And here’s an MSC of the heptiamonds:

(No animation here; my process for making them has a couple of manual steps, which would get tedious for larger sets.)

Notice that there are three hexiamonds in the minimal hexiamond cover, and two heptiamonds in the minimal heptiamond cover, and that all of these have some kind of symmetry. This should not be terribly unexpected; symmetrical polyforms are, in a sense, less flexible to work with because the number of distinct ways you can append a neighboring cell is reduced.

Here’s my updated Python code for solving minimal succinct polyform cover problems.

See also my extended writeup on polyform covers. (This was written before I started the blog, and I haven’t yet integrated some of my newer material.)