Here’s a handy tool in my tool-belt that I thought would be worth sharing. We’ve all dealt with situations in development where we have to create multiple lists of the same logical things. Here’s a classic example:

1
2
3
4
5
6
7
8
9
10
11

enum Animals {
  DOG,
  CAT,
  MOUSE
};

const char* AnimalNames[] = {
  "DOG",
  "CAT",
  "MOUSE"
};

Here we’ve defined an enumeration and their stringified names so that we can pretty-print them. But, this means we have two lists that must have the same number and order of elements or there is a bug. These are parallel lists and they can be tricky to maintain.

Luckily, the C preprocessor gives us an elegant (but not well known) solution. We can put the list into a macro and then generate the parallel lists in the preprocessor such that they will always be correct. Here’s how it works:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#define ANIMAL_LIST(m)        \
  m(DOG),                     \
  m(CAT),                     \
  m(MOUSE)

#define GENERATE_ENUM(m) m

#define GENERATE_STRING(m) #m

enum Animals {
   ANIMAL_LIST(GENERATE_ENUM)
};

const char* AnimalNames[] = {
   ANIMAL_LIST(GENERATE_STRING)
};

Slick, huh? We’ve only listed our items once but we’ve generated the enum and the stringified names from that single list. Here’s what happened:

We defined a macro named “ANIMAL_LIST” that takes another macro as an argument. The macro then calls that macro with each of the elements of the list. Thus, ANIMAL_LIST is a “higher order macro” because its behavior is partially determined by the macro it accepts as an argument. We then define our enum and within the curly braces we expand the ANIMAL_LIST higher order macro using a macro that just emits each of the elements of the list directly. We then define our stringification array and within those curly braces we expand ANIMAL_LIST using a macro that emits the stringified version of each list element.

For a far more ambitious use of this higher-order macro concept, check out the BrianScheme Virtual Machine. Here, the opcode_table is a higher order macro that is expanded 7 times to produce opcode to string mappings, symbols for each of the opcodes, pointer to opcode mappings, and more. That’s a lot of parallel lists that must be kept consistent!

Update!

The original mac release had a packaging bug that meant it would only work on Mountain Lion. This release should work on any version of OSX version 10.5 or newer. Please leave a comment if you have trouble. Thanks!

=========

We’ve released a demo of Mosaic for the Mac! Mosaic puzzle game created by Stephen Mitchell and me for game making contest promoting the upcoming Ouya game console. Grab the mac demo at let me know what you think. If you like what you see then remember to thumbs up our contest video so the OUYA Create judges can count your vote.

If you’re one of the few folks lucky enough to own an Ouya, you can download the Ouya version too!.

I finished my second Game Jam and my very first team game project! We’re calling this game “Mosaic.” It is designed for the upcoming Ouya game console.

If you like what you see and can spare some social love then thumbs up our video and +1 our page. You see, this jam is also a bit of a popularity contest.

Stephen Mitchell took on most of the art and design responsibilities for this project. The simple and clean aesthetic he brings really made Mosaic shine.

If you’re one of the few lucky people in the world who own an Ouya (I’m loving mine) then you can download the APK. We would love to hear what you think.

I really get a lot out of game jams. Sometimes the deadline they impose is essential for forcing me to focus on the things that matter most in my game. @McFunkypants really helped me understand how to harness the power of a deadline in his book The Game Jam Survival Guide. I highly recommend this book for anyone considering participating in a game jam or who has participated but would like to do better next time.

Making games is hard!

My game engine now runs on the Ouya (a new Android-based device using a Tegra 3 ARM processor!)

One of the big challenges that I encountered during the port was asset loading. Android packages, which are delivered as .apk files, typically load assets at run-time by reaching back into the .apk file. The Android provided API for accomplishing asset loading in Java is appropriate but the Android NDK C API has some shortcomings. Why would I say that when the Java API and the C API are almost identical? C applications that handle streams of data from files are typically designed around the file pointer abstraction (FILE*) and the Android API isn’t compatible. This means, typically, that you would need to alter the code of any third-party libraries that you are using (if they deal with files) in order to port them the Android asset API… until now!

My engine uses quite a few third-party libraries, specifically:

1. Box2D for physics

2. lobogg / tremor for sound and music

3. Lua for scripting

4. stb_image for image loading

All of these libraries, except Box2D, provide features that already exist behind some other Android API. The reason I explicitly provide these features again through my own libraries is for portability. I do my quick-turnaround build testing on my Mac but I want the same code to work exactly the same way on the Ouya. The simplest way to achieve this is to provide a lot of my own low-level support. The more “pure” way to achieve this would be to create an abstraction layer that used the Android APIs and the OSX APIs under the hood.

libogg, Lua, and stb_image all use the FILE* API to load files from disk. They call fopen when they want to open a new file and fread to extract data from it. They also occasionally use fseek to jump around.

One amazing and well-hidden fact about the FILE* API is that it is actually polymorphic and extensible! (A surprise from C, right?) We can create a FILE* that uses code we wrote to satisfy fopen, fread, fseek, and fwrite requests. We can use this little-known feature to wrap the Android asset API in a FILE* API instead.

Here’s how:

1
2
3
4
5
6
7
8

FILE* android_fopen(const char* fname, const char* mode) {
  if(mode[0] == 'w') return NULL;

  AAsset* asset = AAssetManager_open(android_asset_manager, fname, 0);
  if(!asset) return NULL;

  return funopen(asset, android_read, android_write, android_seek, android_close);
}

The funopen function creates a new file pointer that will delegate control to the functions that you specify when the user uses fread and friends on that file pointer. The first parameter to funopen is the “cookie” to associate with the FILE*. This is arbitrary data that will be given to your delegate functions whenever they are called. OOP programmers should think of it as the self (or this) pointer.

Let’s write those delegate functions:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

static int android_read(void* cookie, char* buf, int size) {
  return AAsset_read((AAsset*)cookie, buf, size);
}

static int android_write(void* cookie, const char* buf, int size) {
  return EACCES; // can't provide write access to the apk
}

static fpos_t android_seek(void* cookie, fpos_t offset, int whence) {
  return AAsset_seek((AAsset*)cookie, offset, whence);
}

static int android_close(void* cookie) {
  AAsset_close((AAsset*)cookie);
  return 0;
}

Now we can use the FILE* API to access our assets!

1
2
3

FILE* android_file = android_fopen("something.txt");
fread(buffer, size, 1, android_file);
fclose(android_file);

This is great but we still have to call android_fopen to create our special FILE*. If we stopped hacking here then we would still need to open up all those third party libraries to change the fopen calls to android fopen instead. We can do better.

If we’re willing to say that ALL file access should go through the asset API then we can achieve that quickly. We’ll just create a header for our new android fopen library and redefine fopen using a macro:

1
2
3
4
5
6
7
8

#ifndef ANDROID_FOPEN_H
#define ANDROID_FOPEN_H

FILE* android_fopen(const char* fname, const char* mode);

#define fopen(name, mode) android_fopen(name, mode)

#endif

Now we just include this header in our code and we can use fopen as normal! But, again, we’re still adding code to those third party libraries. Thankfully, gcc has the answer.

1

gcc -o foo foo.c -include "android_fopen.h"

The -include argument causes gcc to treat your code as-if you had included the provided file at the very top of your code. Now, to port Lua and libogg and any other big-fancy library that uses FILE* to Android, all we need to do is tweak the build system to include our magic header.

The full source is here and here.

I am now the proud owner of Civilization 4 (for Mac) and I’m really happy to see all of the modding potential that this game has.

For those of you just getting started (like me) the secret to enabling the in-game Python console on the Mac is as follows:

Open your Documents folder and find the “Civilization IV” directory. Then, open the CivilizationIV.ini in the text editor of your choice (TextEdit is fine.) Find the line that looks like

1

CheatCode = 0

and change it to

1

CheatCode = chipotle

Now, start a new game of Civilization IV (or load an existing one) and press Shift + ~ in game to bring up the Python Console.

Try typing these commands to see how the Python console works:

1
2
3

> print "hello world"

> print dir(gc)

There you have it!

If you have the Beyond the Sword expansion then follow the same instructions given above but find the CivilizationIV.ini file in your ”~/Documents/Civilization IV Beyond the Sword/” directory instead.

Happy modding!

Mass convert a folder of Photoshop Files (psd) into png files!

Copy this script into a file named convert2png.jsx and run it from Photoshop (File | Scripts | Browse…). Select the files you want to convert and click open. PNG files with the same name will be created and placed in the same directory as the source files.

1
2
3
4
5
6
7
8
9
10
11

var files = openDialog();

for(var key in files) {
    var inFile = files[key];
    open(inFile);

    var pngOptions = new PNGSaveOptions();
    pngOptions.interlaced = false;
    app.activeDocument.saveAs(inFile, pngOptions, true, Extension.LOWERCASE);
    app.activeDocument.close();
 }

Spriter is an exciting tool for building game animations being developed by BrashMonkey. Like many other interesting little-guy innovations of our time, Spriter started its life on KickStarter. Spriter produces a simple format called SCML that’s designed to be consumed by third-party game engines.

Since I’m a proud sponsor and future user of Spriter I wrote a SCML parser / playback tool as part of a Scheme game engine I’m working on. The SCML code is nicely abstracted from the rest of my engine so it should be very easy to port to other LISPy languages if anyone is interested.

In action:

All of the SCML related code is in the spriter.scm file. The only dependency on the rest my code has to do with turning raw XML into an equally raw (but far nicer) tree of s-expressions.

This implements the final (post beta) SCML spec. Interestingly, this may actually be the FIRST implementation of the post-beta spec. I haven’t found any others yet.

To load an animation:

1
2

(define +scml+ (scml-load "monster/Example.SCML"))
(define +idle+ (animation (entity +scml+ "0") "Idle")

The length of the animation (in seconds) is:

1

(animation-length +idle+)

To interpolate the animation to any time between 0 and its animation-length:

1

(interp-anim anim time)

This returns a list of tkey objects which contain the interpolated rotations, positions, and centers for all of the sprite fragments presented in the order they should be drawn.

Here is an example of those tkey objects being rendered using my engine.

Hopefully this saves someone some time!

The Clojurescript benchmark report that cljs-bench generates had been looking a little old fashioned. Today I gave it a facelift.

I’m now using Enlive to create the HTML for the report. Enlive offers very strong separation between business code and HTML. Since the Enlive template is just a normal HTML file, I can edit it using impatient-mode and see the impact of my work immediately.

Here’s a video of me using impatient-mode to sequentially enable chunks of CSS while seeing the browser update instantly.

Updates!

I’ve made significant performance improvements to impatient-mode since I recorded this initial demo. Here is an example of refreshing the CSS on the Clojurescript benchmark site. And this demonstrates live editing with 3 browsers at the same time.

impatient-mode can be installed from MELPA.

impatient-mode

See your HTML rendered as you type it!

My frequent co-conspirator, Chris Wellons, created a HTTP server that runs entirely within Emacs. He made some updates recently that inspired me to create impatient-mode.

impatient-mode uses Chris’s HTTP Server to serve the Emacs buffer of your choice. impatient-mode serves up this buffer along with a thin shim page that makes the browser automatically refresh itself from your buffer as you type.

Here’s a video of it in action!

The adventures continue with Core.Logic!

Since the last post I’ve had some more time to dig into the implementation of Core.Logic. I’ve also been spending more time with Ivan Bratko’s excellent Prolog Programming For Artificial Intelligence. Finally, since Core.Logic is an implementation of miniKanren, I’ve discovered that William Byrd’s miniKanren Dissertation is a very helpful resource for understanding Core.Logic.

Chapter 2 of Prolog Programming For Artificial Intelligence introduces a classic AI problem involving a monkey and a banana.

A monkey is in a room that contains a banana and a box. The banana is in the middle of the room and is out of the monkey’s reach if the monkey is standing on the floor. But, if the monkey positions the box properly and stands on it then the monkey will be able to reach the banana. The monkey is allowed to walk around the room, push the box, climb the box, and reach for the banana. They question is, given a particular starting room configuration, can the monkey reach the banana?

The state of monkey-world can be expressed as a 4-tuple. The terms that make it up are:

1. Where the monkey is in the room
2. If the monkey is on the box
3. Where the box is in the room
4. If the monkey has the banana

In Prolog, we express this using a named structure with 4 parameters. For example:

1

state( middle, onbox, middle, hasnot )

In this configuration, the monkey is in the middle of the room and is standing on the box (also in the middle of the room) and it does not have the banana.

In Core.Logic, we don’t really have a concept that maps directly to Prolog’s named structures but we do have full access to Clojure’s rich data-types. A simple array will do what we need. We could tag the array with a name but that information isn’t needed for this example. We’ll just express the state of the world as an unnamed 4-vector of symbols:

1

[ :middle :onbox :middle :hasnot ]

The monkey can interact with the world by:

1. Grabbing the banana
2. Climbing the box
3. Pushing the box
4. Walking around the room

Not all actions are always possible. The available actions depend on the state of the world and applying an action to a world-state produces a new world-state.

In Prolog, we can encode the “grabbing the banana” action as a relation between the initial world-state, the action, and the resulting world-state:

1
2
3
4

move(
 state( middle, onbox, middle, hasnot ),
 grasp,
 state( middle, onbox, middle, has )).

In English: If the monkey is in the middle of the room and on the box (also in the middle of the room) and it doesn’t have the banana and it uses the grasp action then it will have the banana.

Now, let’s teach the monkey to climb:

1
2
3
4

move(
 state( P, onfloor, P, H),
 climb,
 state( P, onbox, P, H )).

This relation introduces the idea of unbound positions in a relation. In Prolog, if a slot in a relation is filled in with a symbol that begins with capital letter then that slot is unbound. Prolog can often apply rules to figure out what the unbound slots in a relationship should be bound to. If the same capitalized symbol fills multiple slots in a relation then those slots should be bound to the same value once Prolog discovers what the value is.

Now box pushing:

1
2
3
4

move(
 state( P1, onfloor, P1, H),
 push( P1, P2 ),
 state( P2, onfloor P2, H )).

The monkey can push the box from one position to another if the monkey and the box are in the same place. Once the monkey is done pushing then the monkey and the box will be in the new place.

Now walking:

1
2
3
4

move(
 state( P1, onfloor, B, H),
 walk( P1, P2 ),
 state( P2, onfloor, B, H )).

This is like box pushing but only the monkey’s position changes in the new world-state.

That’s quite enough Prolog for the moment. It’s time to introduce a new Core.Logic macro: The Mighty “defne” (which I like to pronounce “Daphne”.)

A defne Interlude

defne combines conde style rules with some powerful sugar that saves us from having to explicitly introduce some of our variables with fresh. It’s difficult to grasp until you’ve used it so let’s try getting there through a few examples.

In the my previous post I defined a relation called parent and added facts to that relation. Here’s that again but with defne:

1
2
3
4
5
6
7

(defne parent [elder child]
  ([:pam :bob])
  ([:tom :bob])
  ([:tom :liz])
  ([:bob :ann])
  ([:bob :pat])
  ([:pat :jim]))

The macro-expansion sheds some light on what’s going on here:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

(macroexpand '(defne parent ....))

;; approximately expands to

(defn parent [elder child]
  (conde
    ((== :pam elder)
     (== :bob child))

    ((== :tom elder)
     (== :bob child))

    ;; and so on...
    ))

We’re defining a new function of two variables. This new function uses conde to provide a series of possible relations. Remember, conde is somewhat like a logical OR. Within each option, defne has bound (actually, unified) each slot of the vector with the corresponding slot in the arguments to the function.

defne isn’t very exciting when you put only constants in the binding slots. Let’s introduce some variables also:

1
2
3
4

(defne appendo [x y z]
  ([ () _ y ])
  ([ [ a . d ] _ [ a . r] ]
   (appendo d y r)))

This is quite a leap forward in complexity. Let’s take it apart by looking at the macro-expansion:

1
2
3
4
5
6
7
8
9

(defn appendo [x y z]
  (conde
    ((== () x)
     (== y z))

    ((fresh [a d r]
       (== (llist a d) x)
       (== (llist a r) z)
       (appendo d y r)))))

This has expanded to a conde with two cases. The first case applies when X is the empty list. This case also unifies its result variable Z with Y. In English, the result of appending the empty list X onto Y is the same as just Y.

The next case has introduced some new variables using fresh. These correspond to the variables we used in the first part of the second case. Here we’re unpacking X into its head A and its tail D. We’re also packing something new into our result variable Z and we’re recursively calling ourselves. In English, the result of appending the non-empty list X onto Y is the result of appending the tail of X onto Y and then sticking the head of X in front of that.

appendo is tricky. The big idea to grasp for this post is that defne pattern matches against its input variables and is useful for unpacking things like lists and doing interesting things with their contents.

Solution to Monkey and Banana

Using defne we can encode our monkey movement rules in even less space than Prolog required:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

(defne moveo [state move new-state]
  ([[:middle :onbox :middle :hasnot]
    :grasp
    [:middle :onbox :middle :has]])

  ([[p :onfloor p h]
    :climb
    [p :onbox p h]])

  ([[p1 :onfloor p1 h]
    [:push p1 p2]
    [p2 :onfloor p2 h]])

  ([[p1 :onfloor b h]
    [:walk p1 p2]
    [p2 :onfloor b h]]))

We can test our move engine by asking for all the moves possible when the monkey and the box are in the middle of the room:

1
2
3
4
5
6
7
8
9

(run* [q]
  (fresh [m s2]
    (moveo [:middle :onfloor :middle :hasnot] m s2)
    (conso m [s2] q)))

;; result
((:climb [:middle :onbox :middle :hasnot])
 ([:push :middle _.0] [_.0 :onfloor _.0 :hasnot])
 ([:walk :middle _.0] [_.0 :onfloor :middle :hasnot]))

Core.Logic answers that the monkey can climb, push the box from the middle to somewhere, or walk from the middle to somewhere. Grasping the banana isn’t possible from this position.

Now that we’ve encoded how moves affect the world-state we just need to find out if there is a sequence of moves that will let the monkey reach its goal. Can the monkey get the banana?

In Prolog:

1
2
3
4
5

canget( state( _, _, _, has ) ).

canget( State1 ) :-
 move( State1, Move, State2 ),
 canget( State2 ).

Or, the monkey can get the banana if it already has the banana or if it makes a move and then can get the banana.

In Core.Logic:

1
2
3
4
5
6

(defne cangeto [state out]
  ([[_ _ _ :has] true])
  ([_ _] (fresh
          [move state2]
          (moveo state move state2)
          (cangeto state2 out))))

Now, finally, we can ask if our monkey can get to its banana:

1
2
3
4

(run 1 [q] (cangeto [:atdoor :onfloor :atwindow :hasnot] q))

;; result
(true)

A happy ending.

Postlude

Ivan Bratko makes the point that the Prolog version of this program is sensitive to the order of its rules. If you re-arrange the final two expressions in canget then the resulting program will never find a solution:

1
2
3

canget( State1 ) :-
 canget( State2 ),
 move( State1, Move, State2 ).

This is because Prolog does a depth-first search of its solution space. The Prolog version of this program gets stuck recursing into the next call to canget before it ever constrains State2 by applying a new Move.

Happily, Core.Logic isn’t sensitive in this way and will execute its similarly altered program to the correct conclusion:

1
2
3
4
5
6
7
8
9
10
11

(defne cangeto [state out]
  ([[_ _ _ :has] true])
  ([_ _] (fresh
          [move state2]
          (cangeto state2 out)))
          (moveo state move state2))

(run 1 [q] (cangeto [:atdoor :onfloor :atwindow :hasnot] q))

;; result
(true)

Credit:

I got stuck in my first attempt to port the monkey and the banana. Happily, David Nolen had already written an example solution to this problem and I was able to study his example. He has implemented other interesting examples as benchmarks for Core.Logic.