Gamasutra - Sponsored Feature: Democratizing Game Distribution: The Next Step

Gamasutra - Sponsored Feature: Democratizing Game Distribution: The Next Step

When we released XNA Game Studio Express 1.0 in December 2006, we had a feeling it would be an important development. After all, we were solving a set of common problems faced by all game developers. By offering a managed code framework and by empowering community members to run code safely on their Xbox 360 consoles, we made it easier for creators to write games.

With the release of XNA Game Studio 2.0, we added multiplayer support over Xbox LIVE and made several other improvements. We enhanced our tools with a steady stream of samples, articles, mini-games, and other types of content that are posted at http://creators.xna.com throughout the year. As the community embraced XNA Game Studio, we saw that we were redefining who could be a game developer.

The response of the creator community to XNA Game Studio has been overwhelmingly positive. At the time of this writing, we have seen over 800,000 downloads of our tools. Over 400 academic institutions incorporated XNA Game Studio and C# into their computer science curriculums.

I've always wanted to produce video games. But the barrier to entry for consoles has always been high. The good news is that that is no longer the case.

I'm going to let the computer figure it out

The problem with code written 16 years ago is that sometimes you can't figure it out - even when you're the one who wrote it. On top of that, most programmers will look at code they wrote so many years ago and gag at how bad it is. I'm having that problem with my Formula Tree code.

I'm sure if I wanted to bother I could reverse engineer my own code and figure out where I was going with it. But I decided that I'm going to take a different approach. I'm going to use Genetic Programming to finish the code. Yes, I'm going to let the computer figure it out.

There are several reasons:

* I'm more interested in working on GP than finishing the Formula Tree code - this way I can combine the two.
* Every thought I've had for resolving the parentheses problem doesn't seem very elegant.
* The application is perfect for Genetic Programming.

Think about it. What does the program need to do? Simple: take a formula as an input along with a variable to solve. Then produce another formula as an output. It's a simple transformation problem where the input and expected output can be listed along side each other in a table.

I will grant that the solution won't be very simple. It will probably require some tree manipulation. But I could help the process along by giving each Genetic Program access to a special library for manipulating trees. I could even make it so that the input to the program is a tree, as well as the expected output. That way the GP can operate at a more abstract level. I don't have to wait for it to evolve tree manipulation primitives to get started.

Advances in Genetic Programming

If you are interested in learning about Genetic Programming, a good place to start is the book Advances in Genetic Programming edited by Kenneth E. Kinnear.


The book contains a compilation of chapters written by several authors. The most prominent is John R. Koza, who provides a very good introduction to GP. Mr. Koza is the author of the definitive book Genetic Programming: On the Programming of Computers by Means of Natural Selection (Complex Adaptive Systems). But before you start with his 800 page explanation, the Kinnear book is a less overwhelming introduction.

You can find more information and the Table of Contents at the MIT Press Web site.

While looking up the Kinnear book on Amazon, I discovered that there were two follow-ups written. I just ordered copies and will review them at a later date.

Formula Trees

I dug out some old code that I originally wrote back in 1992 for solving equations. At the time it was command line based (remember command lines?) and I would dump the output to a text file. The text output would represent the original formula as a tree like this:

Node # 1|     0 : [ D ] <-  [ = ]  -> 3 : [ - ]
Node # 3|     2 : [ A ] <-  [ - ]  -> 5 : [ / ]
Node # 5|     4 : [ B ] <-  [ / ]  -> 6 : [ C ]

I'd then have to grab a pen and sketch things out to visualize it. I've always wanted to combine such programs with Flash and ActionScript. The screenshot is of my very first rudimentary attempt.

The code lets me select a variable from the formula and solve it. The way I do that is by manipulating the tree. Here's the output from the trace window:

solveFormulaFor( C )
moveFormulaTree()
... moving: -
Node # 1|     2 : [ A ] <-  [ = ]  -> 3 : [ + ]
Node # 3|     0 : [ D ] <-  [ + ]  -> 5 : [ / ]
Node # 5|     4 : [ B ] <-  [ / ]  -> 6 : [ C ]
moveFormulaTree()
... moving: +
Node # 1|     5 : [ / ] <-  [ = ]  -> 3 : [ - ]
Node # 3|     2 : [ A ] <-  [ - ]  -> 0 : [ D ]
Node # 5|     4 : [ B ] <-  [ / ]  -> 6 : [ C ]
moveFormulaTree()
... moving: /
Node # 1|     4 : [ B ] <-  [ = ]  -> 5 : [ * ]
Node # 3|     2 : [ A ] <-  [ - ]  -> 0 : [ D ]
Node # 5|     3 : [ - ] <-  [ * ]  -> 6 : [ C ]
moveFormulaTree()
... moving: *
Node # 1|     6 : [ C ] <-  [ = ]  -> 5 : [ / ]
Node # 3|     2 : [ A ] <-  [ - ]  -> 0 : [ D ]
Node # 5|     4 : [ B ] <-  [ / ]  -> 3 : [ - ]

The last set of nodes represents the solution that you can see in the lower part of the screen shot.

I still have a few kinks to work out of the code. It doesn't handle solving formulas with parentheses too well. I didn't realize there was a problem until I started visualizing it through Flash. Whenever I get around to fixing that and have a much cleaner prototype I'll post an interactive version.

I know quite a lot about calc engines. I used to work for Lotus testing 1-2-3 as well as another company testing their calc engine. Before that as a consultant I wrote code to parse and pull out data from spreadsheet files. I've also written calc engines based on an old simulation language called Dynamo. One day, if I can ever find the time, I may write an e-book on spreadsheet mechanics, or just my experiments with formula trees.

This is just the tip of the iceberg. I'm interested in manipulating and visualizing formula trees because the techniques can also be applied to one of my favorite topics - Genetic Programming.

Interactive L-Systems Flash App

I have several books that discuss Turtle Graphics and L-Systems. The book that I used to produce the app above was The Computational Beauty of Nature: Computer Explorations of Fractals, Chaos, Complex Systems, and Adaptation by Gary William Flake (see the review in my previous post).

The book doesn't contain source code (though some pseudo code). But it included a very good explanation of what an L-System parser needs to do. I combined what I learned from the book with a Turtle Graphics library that I wrote in ActionScript. The models used in the app were described in the book.

Be patient. When you click on a button, it may take a few seconds for an image to generate.