Life Pattern - Gunstar

In the last post, we built a simulator for Conway’s Life in Haskell using repa and OpenGL. The initial life pattern in that implementation was hard coded. In this post, I’ll build a framework for parsing patterns from files.

Broadly, a pattern parser needs to read a set of live cell positions from a file and make those available for the grid initialization. It should also support reading some metadata that is common between different file formats. The common file formats are documented on LifeWiki. They all have similar metadata that we can easily support: pattern name, comments or description, and a pattern offset position. The file formats can also define alternate rules for how the cells evolve, but this version won’t support any rules other than the standard Life.

The grid initializer needs a function that determines if each position in the grid is alive or dead, given a pattern. The type of that function should look something like this:

I chose to use a Set that holds the positions of the live cells, so the implementation of this function is just a thin wrapper around Set.member that takes the pattern offset into account. The LifePattern type holds the set and other metadata read from the file. Look at LifePattern.hs for the full definition.

The next abstraction we can make is converting a file into a LifePattern. All of the formats, except small object, only have one pattern per file, and each format can be distinguished by the file extension. LifeWiki doesn’t have many small object format files, so we can ignore those for now and assume one pattern per file. The client of the parsing framework shouldn’t have to care about file formats, so the API should expose one function which accepts a file path and returns either a pattern or an error. The framework will detect the format automatically and apply the correct parser. Let’s break that down into a working design.

Given a file name, we need to check if the extension matches each parser. If one of the parsers matches, run it on the file and return the result. The result of applying this process to each parser is encoded in the type PatternParseResult.

P.ParseError is from Text.Parsec, the parsing library I chose to use.

With a function FilePath -> IO PatternParseResult for each parser, we can easily try each of them and select the first one that evaluates to something other than IncorrectFormat. This is exactly the implementation of the top level file parsing function.

UnknownFormat is the end value in the foldr call, which indicates that no parser could recognize the file.

The function tryParser is mapped over parsers, which is a list generated from each parser along with its name and file extension. Those are passed to a wrapper function that checks the extension, opens the file, runs the parser, and then prints any warnings generated by the parser.

T.readFile is from the Text library, which is generally more efficient than the String version. The function parsePatternFile is a thin wrapper around Parsec’s runPT which hides how the parsers report warnings.

That’s enough for this post. The next installment will look at the parsers for the RLE and plain text formats. Remember, all the code for this post is available on Bitbucket. Fork it, show me how awesome you can make this.

The final state after starting with the acorn pattern

Repa is a new library in Haskell for handling arrays. It has flexible indexing like the old array library, but supports parallel computation, stream fusion, and has a rich API like the vector library.

To learn how to use repa, I implemented Conway’s Life using repa for the simulation and OpenGL for the display. The complete code is available on BitBucket and builds on my GLFW-b boilterplate, so I’ll only discuss the interesting parts here. Don Stewart wrote a good introductory tutorial to repa that will fill in any gaps I leave in this post.

Evolution

We’ll start with the Life evolution step, because that’s actually the simplest function in this implementation. I decided to represent the Life grid as a repa array of Word8 elements. Boolean elements might seem like a more natural choice, and that’s what I used in my first version, but you’ll see that using bytes makes the evolution step simpler.¹ The evolution step uses repa’s stencil convolution support, which can turn small, static convolution kernels into fast code.

Here is how the evolution step works. In the Life grid, a dead cell is 0 and a live cell is 1, so the convolution counts the adjacent live cells and adds 16 if the current cell was alive in the previous generation. Then we map over the results of the convolution and apply Conway’s rules in the step function: 3 live neighbors brings the cell to life, 2 live neighbors makes no change, any other number kills the cell.

The convolution and map generate a “delayed” array. A delayed array is just a function that maps from an index to a value. This is good if we’re only accessing a few elements, but if the elements are accessed several times they have to be recalculated. Instead, we can calculate the whole thing to generate a “manifest” array with either the computeS or computeP functions. The suffix describes the calculation strategy: S means serial and P means parallel. You might notice that computeP is monadic. Repa doesn’t support nested parallel computations, so to make sure each parallel calculation is complete before the next one starts, the parallel versions of repa’s calculation functions are monadic.

The stencil code is a little strange, so let’s take a closer look at it.

The last construction there between the brackets is actually template Haskell that is evaluated at compile time to generate Haskell code. This requires the language pragma QuasiQuotes (if you don’t understand that, look at the top of the source file), and we have to make sure that the names in the package Data.Array.Repa.Stencil.Dim2 are visible. That means that package can’t be imported qualified. The repa index constructor also has to be visible; since we import Data.Array.Repa qualified we need this import line

It’s strange because it looks like an operator but it’s actually a data constructor.

The other argument to the mapStencil2 function is how to treat boundary values. There are three options here.

BoundFixed a

This option will make the entire border area a constant value. The border area is half the size of the convolution kernel.

BoundConst a

This option uses the constant value for all locations outside the array.

BoundClamp

This basically repeats the edge values as far as necessary.

I used BoundConst here to use a special value for locations outside the grid. This way, cells will always die when they get to the edge. It would be better to expand the grid one cell in each direction outside the view so that it appears infinite. That will be easier to do after I switch to shaders for the rendering, so I’ll address that in a later post.

Grid Initialization

Here is the function that creates a new grid when the program starts.

First it creates a delayed array with A.fromFunction, then calculates it into a manifest array with A.computeS. The function is a mapping from array index to value. Repa indices are created with the special constructors Z and :.. I’m using Ints for the index types, but repa supports indices of any type.

The initialization function is implemented using guards to poke some live cells into an initial pattern. This one is a blinker, and there is code for an acorn in the full source. A much better solution would be to accept a file containing the initial pattern. Supporting one or all of the formats on the Conway Life Wiki would open a vast catalog to us. Another option would be allowing the user to draw a pattern in the screen before starting the simulation. I’ll cover both of these in later posts. [Update: There is now a series of posts about the life pattern file parsers]

Rendering

The view is pretty straightforward. In each frame, I write the grid to a grayscale texture and draw it on a quad. Unboxed repa arrays use unboxed vectors underneath, so the grid is easily converted to a storable vector which can be dumped to texture memory. The only trick here is padding the array to a power of two width. Modern graphics cards are supposed to handle textures with off dimensions, but I have a cheap mobile Intel GPU that freaks out when I give it an off-size texture. Look at the source for all the details, but this is the important bit that uses traverse to copy the array into a bigger array.

Performance

At first I thought this would have pretty terrible performance. Each frame is allocating several new arrays for the evolution and the conversion steps to the texture buffer. I thought I would need to rewrite this using mutable vectors to avoid allocations. However, when I ran it with the stats on (+RTS -s) the garbage collector hardly ever runs (only once in several thousand generations) and the program runs in constant space. Thanks to repa, the code is already parallelized and takes advantage of multiple cores (run it with +RTS -NX where X is the number of cores to use).

In the future I want to convert the rendering to use shaders. This will simplify the texturing step since the grayscale conversion can be done in the fragment shader. It will also fix the boundary issue, since I’ll be able to expand the grid to a power of two and only render a section.

Take a look at the full source, fork it and improve it! What would you like to see next in my Haskell experiments? Let me know in the comments or on twitter.

First, to use OpenGL we need a way to open a window, get a context, and respond to user input. There are several different cross-platform libraries to do this, but for simple projects I prefer GLFW. The Haskell package GLFW-b has bindings for GLFW and exposes a more Haskellish API than the regular GLFW package.

This is some boilerplate code for setting up GLFW-b and running a main loop. It will open a window and draw a rotating square. There are inline comments explaining what is going on, but here is a summary of the main points.

• GLFW-b lets us run our own main loop instead of requiring us to use callbacks like GLUT. However, there are still callbacks available for some things. The only one we’ll use is the window resize callback. We’ll use this to set the projection matrix and viewport when the window changes size.
• The rough procedure for using GLFW-b is
  1. Call initialize
  2. Call openWindow with our window options. Start with defaultDisplayOptions and set what we care about. Remember to set num*Bits if you want color.
  3. Set the window size callback with setWindowSizeCallback
  4. Run our loop, calling swapBuffers after every frame
  5. Call closeWindow
  6. Call terminate
• We can use finally to make sure that GLFW-b is terminated properly no matter how our main loop exits.
• Calling swapBuffers polls for input, so inside our main loop we can use the GLFW-b input functions like keyIsPressed. We’ll also check windowIsOpen to exit the main loop when the window closes.

None of this is readily apparent in GAP. Each frame is a separate Gimp file, and GAP sees that they’re part of the same animation because the file names end with successive numbers. There is an onion skinning item in the GAP menu (cleverly disguised as Video), but it doesn’t seem to do anything until you configure it correctly.

To configure onion skinning in GAP, go to Video » Onionskin » Configuration…. The onionskin configuration in GAP is exquisitely flexible and confusing. Here is how to configure onion skinning in GAP for a couple of common scenarios. Note that I’m using Gimp 2.8.2.

Overlay the previous frame

GAP onionskin configuration for seeing one frame through the previous frame

With onion skinning configured this way GAP will put the previous frame on top of the current frame, but with lowered opacity, and it will wrap around at the first frame. This can be useful to draw keyframes as you’re building an animation cycle.

• Reference Mode Tells GAP how to select frames for the onion skin. This parameter doesn’t matter when we’re only using one frame. With more than one frame, it works with the Frame Reference parameter to make the list of frames that become onionskin layers.
• Onionskin Layers How many frames to use in the onionskin stack. Here we want to use one.
• Ascending Opacity If this is checked, the frame that is farthest from the current frame will be most opaque.
• Frame Reference This number multiplied by the sequence in Reference Mode gives the offsets to the frames in the onionskin layers. For example, using bidirectional double mode with a frame reference of -1, the first onionskin layer is the previous frame, the second onionskin layer would be the next frame, the third would be -2 (the second previous frame, etc.).
• Cyclic If this is checked the onionskin layers wrap around at the ends of the frame stack.
• Stackposition This is where to put the onionskin layers. We’re telling GAP to put the onionskin layers at the very top. Changing this might be useful if you’re animating a layer in the middle of your stack.
• Opacity The first number is the opacity of the first onionskin layer. The second number is multiplied into the opacity for each successive onionskin layer. So with our settings the second onionskin layer would have opacity 0.70 * 0.50 = 0.35, the third would have opacity 0.70 * 0.50 * 0.50 = 0.175, and so on.
• Layer Selection This can be used to only use certain layers in each frame for onion skinning. The settings shown will use the entire frame.
• Auto create/delete Check these so that the onionskin layers don’t show up in thumbnails. This is useful when using the GAP animation preview tools, but remember that you still have to delete the onion skin layers before exporting the animation or saving a frame.

Overlay the previous and following frames

GAP onionskin configuration for in-between drawing

This onion skinning configuration will let you see the current frame through the two surrounding frames. This is useful for drawing in-between frames to make a smooth animation. You can see that the only change required from the previous settings are to use two onionskin layers. This gets the previous frame and the next frame. If you need more frames to draw your tween, just use more onionskin layers.

When I’m drawing tween frames, I often need to adjust the opacity on the onionskin layers. You can directly change the opacity on these layers as you would with normal Gimp layers. The next time you change frames, the new onionskin layers will be created with the opacity from the onionskin configuration.

I hope this helps explain how to configure onion skinning in GAP, and makes some of these options less confusing. I’d love to see some of the animations you make with this, so share in the comments or hit me on twitter!

Source: Flickr user Ex-Smith

So you’re trying to make money blogging? Want to be a pro blogger? Here are five great reasons why you should write all of your blog posts as lists.

1. Laziness

Let’s assume that you’ve done your research and you know a lot about your topic. My high school English teacher wanted us to write research papers by writing each fact we learned an a 3×5 card. Then, we could experiment with arranging the facts in different ways. The hardest part, of course, was writing the transitions and synthesizing all those facts into an interesting, cohesive narrative.

Let’s face it, organizing information into a coherent 500 word essay is hard work, and most of us couldn’t even do it in high school. Now you’re competing with every literate person in the developed world, and the five paragraph form you learned never really worked in the first place. So why bother with synthesis and transitions? Just dump all the facts you’ve learned into a numbered list and let your readers put it together!

2. Nobody Reads Anyway

The average American reads at an 8th grade level, so all your fancy prose is lost on the proles anyway. Readers are so distracted and overloaded with information these days, no one wants to commit to even the most beautifully written wall of text. I’ve checked twitter three times already while I was writing this.

Most people will scan through the bold headings in your article, pick out a few words from the body, and decide whether or not to share it. Using the list format gives your article a natural set of headings that should stand on their own. For bonus link-bait, follow the lead of major news organizations: write misleading headlines that grab attention but don’t accurately describe the content.

3. Numbers Conveniently Label Content for Sharing

Paragraphs aren’t clear on websites, especially when the text is flowed around images or pull quotes. Counting paragraphs manually is a pain, and you look like an elitist prick pointing out a paragraph by number. Dave Winer uses custom blog software that creates a hyperlink for each paragraph, but, since no one has stolen the idea, I don’t think anyone understands or uses them.

By writing list items, you’re giving your readers clear labels to point out different sections of text. When they share your blog post, your readers will be able to point out exactly what they liked by saying, “OMG #4 is LOLZ!!1!” Classy.

4. Mix N’ Match

Since you’re not wasting time analyzing and synthesizing your ideas, each list item can probably stand on its own without much context. This is your opportunity to work smarter (not harder!) by reusing items from old lists to create new ones. So you wrote the barn burner, “7 Killer Trout Flies,” and you crushed it with, “5 Secret Fly Fishing Techniques.” Now just pick out the ten best items, and bam! You’ve got, “10 Tips for Trout Fly Fishing!”

Reusing content is a classic trick of pro bloggers, but you have to be careful about overdoing it. Search engines have developed algorithms to punish content that is copied to too many pages, so pros have come up with techniques to create syntactically distinct articles while retaining the semantic meaning. There is even a whole market of tools they use to “spin” articles, which mainly consists of replacing common adjectives with synonyms.

5. Brainstorm to Blog in One Easy Step!

To make money writing a blog you have to post a lot, and each post has to be long enough and have the right keywords to rank well. Coming up with all those ideas and writing all that content is hard work, even with a template.

Using lists can cut down some of that work. If you have an idea for a topic you want to write about, start by making a list of everything that comes to mind about the topic. Pick out the most compelling, punchiest items in your list and expand on them. Add an introduction, some links and images, and you’re done!

To help you get started, here is a sampler of some representative psychobilly music. I included Reverend Horton Heat, Mad Sin, Tiger Army, Nekromantix, Mano Negra, Mad Marge And The Stonecutters, Horrorpops, The Goddamn Gallows, and Hillbilly Hellcats. I wrote comments on each track, hover your mouse on them to see.

If you like what you hear, be sure to buy the albums. (this is an affiliate link)

The theme hook suggestions are lists of increasingly specific keys separated by a double underscore, for example node__mymodule__block5. The first entry, node here, is a top level hook defined by a hook_theme function. When the theme function is called, the theme system will try the most specific hook first, in this example node__mymodule__block5. If that doesn’t exist, it will try the next hook, node__mymodule, and so on until it gets to the top level hook. Themes that implement these specific hooks with template files will replace the underscores with hyphens, so node__mymodule__block5 would be rendered by node--mymodule--block5.tpl.php.

Module developers can set a theme hook suggestion for an element by using the #theme key of a render array. The keys of the render array will have to include any parameters that the top level hook requires. These parameters are defined when the hook is declared. Hooks in Drupal core have their parameters in the Drupal API, and hooks from custom Drupal modules should be documented in the module. Here is a nice list of default theme hooks in Drupal core

Here is an example that creates a list using a theme suggestion derived from the Drupal core hook item_list, getting the elements from some function get_items.

This post shows how to typeset a LaTeX vector with an arrow, a hat, or bold.

LaTeX Vector With an Arrow

The arrow vector notation is the standard in LaTeX, just use the \vec command in math mode.

This:

Generates this:

LaTeX Vectors With Hats

Using the \hat command in LaTeX generates a caret commonly used for unit vectors.

This:

Generates this:

Note that I used \jmath in the last statement. This gets rid of the dot over the j which screws up the placement of the caret. A similar command, \imath is also available for i.

Bold LaTeX Vector

This command will make \vec typeset LaTeX vectors using bold instead of an arrow:

Put that in the header of the LaTeX file, then $\vec{v} = 5\hat{k}$ generates:

If you like bold unit vectors, these commands will also modify the \hat command:

Now $\vec{v} = 5\hat{k}$ generates:

My other post about bold LaTeX vectors has some great tips in the comments about using this with Greek letters.

Bold is my favorite style for vectors in LaTeX articles, but the decorated styles can look good in a well-printed book. Leave your favorite styles and tips in the comments!

Are you surprised at how you sound when you listen to a recording of your voice? I always thought that we sound different to ourselves because your voice vibrates through your skull to your own eardrums, which gives you a unique experience of your voice. It’s kind of nice to think that every time you speak you’re giving yourself a private concert, but for effective communication you need to know how others hear you.

Vocal Coach Chris Beatty’s video shows one way to hear how you sound to others. He explains that part of the effect is due to sound travelling around your face to your ears. Blocking this sound lets you hear how your voice changes as it travels through the room. I gave it a try, and I was surprised at how well it works.

I have a deep voice, and people often have trouble understanding me. I’ve always wondered if I sound louder to myself than others, and if the distinct frequencies of my voice get muddled as they bounce around a room. When I used this technique and blocked my voice with some magazines, it sounded like my volume dropped to about 30%. I couldn’t believe it! I used to do theatre,¹ so I know I can speak loudly enough to be clearly heard across an auditorium. Because of this, I try to keep my volume down so that people don’t think I’m shouting, but I think I went too far. Now, using this technique to hear how I sound to others for feedback I’ll be able to adjust how I speak to be more clearly understood.

via LifeHacker