Game Painter Dev Log 2: Developing the Back End

Hello. This is the second entry in a series documenting the development of my graphical programming environment, Game Painter.

In my first entry, I talked about the front end to various rule forms, and today I wanted to follow it up with a discussion of the back end.

Cellular Automata as look-up tables

The goal of Game Painter was to make a graphical programming interface, so as I was thinking about what made sense for the UI, I happened to stumble on a chapter of Daniel Shiffman’s The Nature of Code about cellular automata. The diagrams in the chapter helped me see that the logic of cellular automata has a strong graphical interpretation. Cellular automata could be defined graphically!

This graphical interface would need to be supported by some sort of back end implementation. The first back-end solution came from that same chapter from the Nature of Code. Here’s the basic idea:

In Stephen Wolfram’s concept of “elementary cellular automata,” cellular automata are encoded as strings of digits. For example, if we take the following rule diagram

We can assign digits to each unique sprite and form two numbers, one on the left-hand side and one on the right-hand side.

That’s 110100000 and 110110000 in binary, or 416 and 432 in decimal. But on the right-hand side, the center cell is the only one we care about because it’s the only one that changes state from left to right. So then we get

We can use the left number as an index to an array and use the right number as the value at that index.

var index = unbinary("110100000"); // index is assigned the value 416
var val = 1;
lookUpTable[index] = val;

We can compose all of our rules into a single table by writing them in sequence to the look-up table. This implies a prioritization of some rules over others because later rules in the sequence can overwrite earlier ones.

This procedure works generally for any number of unique sprites. If we have two unique sprites we can encode rules as binary numbers, if we have three unique sprites we can encode rules as trinary numbers, and so on and so forth. Finally, we can perform this encoding procedure on rules with any number of total sprites. That number becomes the number of digits in the encoding.

The advantage of this approach is that array lookup is instantaneous. But there is a serious limitation here. With N unique sprites and M total sprites, the size of the lookup table becomes M^N. This is fine for small rulesets such as Conway’s Game of Life (2^9 == 512) but quickly becomes problematic as rulesets become larger. This table shows how rapidly the array size grows as N and M grow.

One-to-one rule interpretation

Look-up tables proved not to be a good general solution, and the front-end was evolving in ways that were moving farther away from cellular automata. At this point, it seemed more natural to write a back-end implementation that reflected what was happening on the front-end more directly.

We define a general rule interface:

interface Rule 
{
  evalCell: (lvl: Level, i: number, j: number) => number;
}

Where i and j are the coordinates of the cell to evaluate in the given level.

We can implement a concrete Rule type for every form of rule, and there are many advantages to this approach.

With this solution, we have total flexibility to grow our language to incorporate new rule forms without affecting existing rule forms.

We can compose rules, defining them hierarchically, kind of like an abstract syntax tree. Except our tree is comprised of rules rather than expressions.

This solution is also conceptually simple. It provides a one-to-one relationship between the front-end and the back-end, and it enables a divide-and-conquer approach to implementation.

We can even fold our look-up table solution into this more general solution and use look-up tables in special cases. Look-up tables can be defined as a type of Rule. Something like this:

class LookUpTable implements Rule
{
   private table: number[];

   public evalCell(lvl: Level, i: number, j: number)
   {
       let index = parse(lvl, i, j); // get the neighborhood encoding
       return table[index];
   }
}

Until Next Time

For the next post, I plan on taking a break from these technically-oriented posts to talk about the high-level design ideas behind Game Painter. Stay tuned to this blog or follow me on Twitter @objstothinkwith  to see more. Thanks for reading!

Game Painter Dev Log 1: Rule Types

Hello there. This is the first in a series of posts to document the development of my experimental programming environment, Game Painter.  

Game Painter’s interface is entirely graphical. The way you program is by painting canvases to define rules. With this first post, I’m going to be describing some of the various rule forms in Game Painter and their applications.

We’ll start by looking at rule forms that allow us to program cellular automata, such as Conway’s Game of Life. Later, we will move on to talk about constructs that could help us program puzzle games.

This first post will focus on the front-end, but I’m planning to follow it up with a post about the technical considerations of building the back-end.

One note before starting: the project is very early in development, so terms and even concepts that I use here are subject to revision.

Some Terminology

Let’s get some basic terminology out of the way, so we can move onto the interesting stuff.

Game Painter runs simulations of cells called levels. Levels can be interactive or completely autonomous. This post will mostly focus on autonomous systems.

Programs define the behavior of levels. Programs are composed of rules. Rules have a left-hand side and a right-hand side. Each side of the rule contains some arrangement of cells.

The way Game Painter works is by find and replace. Given a rule, the runtime looks in the level for instances of the left-hand pattern and replaces them with instances of the right-hand pattern. Left-hand cells can be wildcards (indicated by the ‘?’), meaning they will match any cell.

Let’s say that we’ve defined the following two rules.


The first rule says that if a black cell is to the immediate left of a white cell, then they will trade places. The second rule says that if a black cell is to the immediate right of a white cell, then they will also trade places.

If we populate a level with some black, white, and gray cells, then run the level with the two rules we made, we’ll see all the black and white cells oscillate back and forth.

Those are all of the basics we need for now, so let’s move onto the focus of this post, which is to discuss the different types of rules in Game Painter.

Multi-Cell Rules, Single-Cell Rules, and Conway’s Game of Life

The rules we saw in the previous example are what I call multi-cell rules, due to the fact that, in each rule, multiple (two) cells are being changed in the transformation from the left side to the right side.

A restriction on the multi-cell rule is the single-cell rule, where only one cell can be transformed. When I get the chance to write a follow up on the back-end implementation of rules, I’ll spend some time on why this distinction is significant.

Single cell rules are all we need to define Conway’s Game of Life, the most famous example of cellular automata, which gives rise to so many complex and fascinating patterns and is theoretically as powerful as any computer.

Given a 3×3 neighborhood of cells of black and white cells, where black cells are “live” cells and white cells are “dead” cells, four rules define Conway’s Game of Life:

    1. Reproduction: Any dead cell with exactly 3 live neighbors becomes a live cell.
    2. Survival: Any live cell with exactly 2 or 3 live neighbors lives.
    3. Loneliness: any live cell with fewer than 2 live neighbors dies.
    4. Overpopulation: Any live cell with more than 3 live neighbors dies.

All of these are single-cell rules, because for any application of one of these rules, no more than one cell will change from live to dead or dead to live. But when we run these rules on a whole grid of cells in parallel, we get all the interesting emergent behaviors that characterize the Game of Life.

Rendering the Game of Life

A governing idea of Game Painter is that everything is graphical. So how would we graphically express these 4 rules?

Let’s start with reproduction: “Any dead cell with exactly 3 live neighbors becomes a live cell.”

For example, this is one 3×3 grid where the center cell has 3 live neighbors, and thus it becomes alive.

But there are many such grids (where the center cell has 3 black neighbors) :

In other words, way too many to define manually.

What we need is a way to express these combinations succinctly. My solution is to introduce what I call combinatorial masks.

Combinatorial Masks

With combinatorial rules, we can define any subset of cells as a combination, which means any combination of values we write to those cells will be accepted. In the graphic below, the yellow cells are marked as part of a combination.

With this combinatorial mask, the reproduction rule will match any combination of 3 black cells and 5 white cells.

Now we can finally make a one-to-one mapping of the Game of Life, as it’s expressed in plain english, to the graphic “language” of Game Painter.

Given the following mask

The Game of Life is defined as reproduction,

Survival,

Loneliness,

And overpopulation

 

So now we know that we can make “games” like Conway’s Game of Life using Game Painter. But Conway’s Game of Life is really just a game in name only. What about games with players?

Input Switching on Rules

What we have now are the tools to create autonomous simulations. To make interactive simulations, we need some way to respond to input.

In Game Painter, rulesets are mapped to different inputs. Thus, when an input is pressed, the associated ruleset is switched on.

In this dummy example, if the right arrow key is pressed, the “move right” rule is activated and our character moves right.

And if the left arrow key is pressed, the “move left” rule is activated and our character moves left.

We’ve swapped out black and white cells for sprites, but logically this example works exactly the same as previous examples.

In Conclusion

There are more rule variations I’d like to cover, specifically “…” rules and generic rules. The former enables more game-like applications and the latter solves a redundancy problem that occurs when you have many cell types that interact in similar ways, but this post has already gone on too long, so I’ll leave them for another time.

Hopefully, this starts to give you an image of what Game Painter is about. I’m planning to post about the project every week for the next several weeks. So if you’re interested, stay tuned to this blog or follow me @objstothinkwith on Twitter for updates.

 

 

Version Control as Creative Tool

Version control is a good idea, so it’s strange how little it’s reached outside of the world of programming.

For example, the Google Doc in which I’m writing this essay has a version history feature, which is cool. But it’s like the name suggests, a history, a timeline. Not a tree that can branch in several directions like proper version control software.

Part of the reason for this disconnect is the lack of accessibility.

Git is the most popular version control system in the world of open source software, but despite being the de facto standard and the version control system most programmers learn first, Git can be difficult to learn. There are whole books written on how to learn Git.

All this seems a bit odd when the basic ideas of version control are so simple and natural. Something seems wrong here.

Another reason for the lack of reach is Git’s design choices, which prioritize team collaboration over creative flow.

I want to propose a different version control interface that’s well-suited for design and creative work in general. But first I should talk about why version control is a good idea for design work in the first place.

Why version control can be good for design

Design can be defined as the purposeful exploration of a possibility space. Version control, with its ability to maintain different branching versions of a document, is well-suited to this task.  It gives the user the ability to extend feelers into a design space.

I like to think of the design process as a tree. In completing a design project, decision points arise, where you can choose to branch off in a number of ways.

When a designer makes choices, they commit to a certain path down the design tree. Sometimes the designer hits a dead end and must retrace their steps. They have to recall some previous state of the project and then recreate it. This kind of thinking is difficult and error-prone for humans, but software does it effortlessly. Thus version control software can help a designer move up and down a design tree, as it can remember exactly the state of the project at every decision point.

In this sense, where we imagine design as a process of tracing a decision tree, the basic vocabulary of version control–branch, fork, merge–translates naturally to the world of design.

Now that we’ve established an abstract connection between design and version control, I want to talk about what this might look like in practice.

An idea of what version control software could do for creative work

Imagine that you are working on a musical composition.

You start with just a melodic idea. You record it.

Now you start to make some changes, while keeping the original intact. You wonder how it would sound if you reversed the melody, or inverted the tonality, or transposed it into a new key.

You save the changed melody, and then return to the original melody. Making new changes, again, you branch off of the original idea.

Now that you have two ideas branching off a derivative idea, you wonder what they would sound like if played concurrently, in a kind of counterpoint, or one after the other, as in different sections of a song. These ideas point to ways in which you could merge branches of your project.

You can continue endlessly this way, growing a family tree of musical ideas and combining ideas by merging them. Some ideas will not work. But some ideas will be interesting and suggest further development. As long as you commit your changes, you don’t have fear that you’ll lose your work, which means you can feel more free to try things.

You can also prune branches that don’t lead to anything interesting, what would be called removing branches in Git. This allows you to keep your work space decluttered.

Pruning branches isn’t the only option for the designer, however. In some cases, the function of the design tree may be to embody a family of ideas, variations on a theme. If the goal of a creative work is to create variations on a theme, then divergent branches don’t have to be simply abandoned in favor of a main branch.

The many forms of merge

I also want to take the time to look a little more closely at merging, an idea we introduced in the last section.

How merge is defined is application specific. In other words, merge is a polymorphic operation, it does something different depending on the context.

Even within a single application, I can imagine merge being used in multiple ways. In short, I can imagine it as being several words as opposed to one.

In my musical example, merge had two uses. The first use had the two merged phrases play simultaneously in a kind of counterpoint. The second use had the merged phrases play one after the other in a sequence. Because we have two separate uses of the word “merge” within the same application, we might want to separate “merge” into two words. For example, we could call the first type of merge “stack”, and the second type of merge could be called “sequence”. Better yet, we could allow the user to define their own custom merges and call them whatever they want. Much of the vocabulary of version control could be context-specific.

Criteria for version control software suitable for creative work

Using the software should be frictionless and easy. Nothing should impede creative flow.

With that in mind, common operations should only cost a single input. If we assume the UI language of conventional operating systems, the user should be able to branch a document with the click of a mouse, commit with a press of a button, and merge by dragging one idea onto another (the one it is to merge with).

The metaphors of version control must be communicated clearly, and we should prefer visual communication to verbal communication.

Uses

I’ve given a small example of how version control could be used for music composition, but I think this is only the tip of the iceberg. With a little bit of thought and planning, I suspect that version control could be well-integrated into all kinds of creative applications.

We could even apply the idea of version control as creative tool back to programming, because programming is itself a creative application. The software we might make for versioning code might look very different from existing software if our main goal was the guidance and maintenance of creative flow.

Of course, these ideas are in no way intended to replace existing version control software. I only want to extend the reach of the basic concepts. The main goal of most existing version control software has been on allowing multiple people on separate machines to work on the same codebase at the same time without breaking code. This is a very valid aim, but it’s not all that the technology can do.

Version control can also encourage a kind of free associative creative process. Yet, by keeping a record, it also reifies the creative process, making it subject to reflection and interrogation afterwards. The creative process is rarely linear, and version control software is uniquely equipped to give a non-linear account of the creative process.

In sum, version control can encourage exploration, creative flow, and it can reify the creative process, making it subject to interrogation and reflection.

Next

Next I want to look at user interfaces for version control software. What should the look and feel of the UI be given some set of design goals such as accessibility and encouraging creative flow? I’ll start to explore my thoughts on this subject in the next post.