Parser Combinators are the shit!

The name is daunting, but parser combinators are actually pretty straightforward once you get the hang of it (as is the case with most programming :P). Scala has a parser combinator library built right in; I myself followed the chapter on Parser Combinators in Programming in Scala 2nd Edition (PiS2E). I won’t go into details about how such combinators work or write a tutorial; there are enough of them out there. It is sufficient to say that you can build a basic arithmetic calculator (with +, -, *, /, and parentheses) using THREE LINES (ok, six counting declarations). If that doesn’t whet your appetite, then your stomach is probably made of rubber… There’s probably a better pun in there somewhere, but I’ll leave that as an exercise for the reader :P The following code is taken directly from PiS2E:

import scala.util.parsing.combinator._
class Arith extends JavaTokenParsers {
def expr: Parser[Any] = term~rep("+"~term | ""~term)
def term: Parser[Any] = factor~rep("*"~factor | "/"~factor)
def factor: Parser[Any] = floatingPointNumber | "("~expr~")"
}

All you need aside from that is to actually call the “parseAll” method with input, and then magic happens:

println(parseAll(expr, args(0)))
input: 2 * (3 + 7)
[1.12] parsed: ((2~List((*~(((~((3~List())~List((+
~(7~List())))))~)))))~List())

The formatting isn’t particularly pleasing to look at but it’s apparent that the structure is in there. It’s not much more complicated to adapt the code to actually spit out a number, add in constants, or parse variables. It’s the shit.

I used parser combinators on a sketch about a week ago to let users type in linear transformations. I’ve been on a fractal binge lately, and I was reading about IFSes and decided to implement a simple IFS drawer for a sketch. The algorithm is pretty straightforward:

  /*
  a) you have a set of geometric objects (points, lines, polygons, curves, etc) (named S)
  b) you have a set of transformations (rotate, translate, scale, shear, etc) (named T)
  c) you apply each transformation to each object in that set, which gives you the set of transformed objects S' (giving you num(S)*num(T) new objects)
  d) Use S' as the set S in a)
  */
  def iterated(): Set[Geometry] = {
    var Sprime: Set[Geometry] = Set()
    S.foreach(g => T.foreach(t => Sprime += g.transformed(t)))
    return Sprime;
  }

  def iterate() { //Move the iteration along.
    S = iterated();
  }

Writing a combinator to parse matrix inputs is pretty straightforward: you have basic transformations (translate, scale, rotate, etc.), and then you may combine them, usually with matrix multiplication (although I also implemented by-element summation to see what would happen). After some wiring and judicious ^^ usage (the ^^ method transforms raw combinator output types into types you want), some nice looking figures start popping up:

The shit!

At this point the only shape you start off with is a square; originally I was going to leave it at that but coming back to the sketch yesterday, I decided to add drawing capabilities. You can see the sketch here.

You can draw stuff!

I’m using controlP5 for the GUI, which works great for Processing but doesn’t have a comprehensive focus system so one has to write methods checking whether the user wants to draw things or if they’re just working the controls. controlP5 is also finnicky with regards to Proguard since the font it uses is stored in a couple of gif files within the “controlp5” package, so I decided to skip obfuscation for this jar; the resulting file is ~550kb, which still isn’t bad.

I wanted to create a three-dimensional view that kept track of the “age” of shapes and placed them on the Z axis according to age; that might be a future feature. All in all, I’m very pleased with how easy and quick it was to do what I was looking for in Scala, especially in regards to writing a grammar for linear transformations. It’s one of the reasons why I love Scala as a language; it’s like everything you ever wanted but didn’t have in Java. And so. Much. Less. Boilerplate. I’m not sure if I even USE plates anymore!

Advertisements

Generative Terrain, Proscene, Algebra, Proguard

I love generative content. It would be my dream job to work on procedural generation for content in games. I feel that there is a lot of room for improvement in this field. The idea of generative maps has been around for some time and adds a level of replayability that I really love (think of how boring Nethack would be if every single runthrough had the same map).

I started off by sampling 2D Perlin noise at regular intervals and displaying it as a bunch of 3D rectangular prisms, which worked fine but wasn’t particularly interesting to look at. I added a color gradient from toxiclibs that would match different heights with different colors; the lower levels were made a deep blue to look like water, which then faded into a small of light yellow for sand, which then became green for a grassy look, etc. etc. Adding that really improved the aesthetic quality of the sketch, since I suddenly had hills and valleys and little ponds. In retrospect I probably should’ve taken screenshots of the sketch as it progressed; unfortunately none exist so just imagine it :P.

For a while I wanted to do a first-person (FP) camera where you could move around the terrain and look around you, so I used the Proscene library, since it is by far the best 3D camera library out there right now. I tend to have problems with conceptualizing cameras and 3D orientations; the vocabulary in particular throws me off. I had a mostly working FP camera by setting the Z position to be whatever the height of the block was, but kept running into weird problems related to the definitions of pitch, yaw, and roll and their relation to either the coordinate system that was set up or the “target” I was looking at. I would really appreciate if someone could enlighten me or point me to a nice tutorial on understanding such things, or possibly a library geared towards intuitive FP camera movement. At any rate I decided to scrap the first-person camera idea and move on.

At this point I decided to abstract my terrain generator function. One can use any function of two variables to generate height maps, and Scala really shines in dealing with functions. First I wrote a trait called TerrainGenerator (TG) that was nothing more than an alias: trait TerrainGenerator extends ((Int, Int) => Float). Then one can write a PerlinNoiseTG for generating terrain from perlin noise; it’s just as easy to write something like SimplexNoiseTG for simplex noise or FuncTG for a generic function. That’s great, but what’s really awesome is writing operators for terrain generators. I’m kind of obsessed with algebra – not the high school “solve 3x+7=12” bullhonky – but with the idea of having a set of objects and then using operators to combine those objects together. You can create beautiful structure from fairly simple rules. This is probably old news for most mathematically inclined people but I’m still new to the concept and it is very exciting :). My combiner class looks like this:

abstract class TGCombiner(tgs:TerrainGenerator*) 
   extends ((TerrainGenerator*) => TerrainGenerator) 
   with TerrainGenerator {

    override def apply(x:Int, y:Int) = apply(tgs:_*)(x, y)

}

TGCombiner is actually two functions – one takes in a varargs list of TGs and outputs a new TG, and the other is just the TG function (taking in two variables and outputting the height). Probably the most obvious type of combiner is one which performs some sort of operation on each individual height to spit out a new height; the class looks like:

abstract class OperatorCombiner(tgss:TerrainGenerator*) 
   extends TGCombiner(tgss:_*) {

       def op:(Float, Float) => Float

       override def apply(tgs:TerrainGenerator*) = new TerrainGenerator { 
          override def apply(x:Int, y:Int) = tgs.map(_.apply(x, y)).reduceLeft(op) 
       }

}

I’m not too happy with how apply has to instantiate an anonymous class; I considered writing a subclass of TerrainGenerator to handle this case but I think the problem comes down to either a) having apply take parameters, b) having the class take parameters, or c) not having enough framework. Actually, I’m not really certain about what I am even looking for at this point. There is obviously something weird going on but it’s not clear to me yet. But anyways.

I ended up writing three base TGs: one for simplex noise, one for Perlin noise, and one of two superimposed sine waves. On top of that, I built OperatorCombiners for all combinations of the three base TGs. You can see the sketch here.

The final stage in this sketch was to make it presentable for the wide internet. Applets written in Scala are pretty much unviable due to the requirement of packaging the whole Scala library (2.8.0 is ~6 mb), unless you use some sort of code shinker. Proguard is a great tool for shrinking java files, but it requires a lot of configuration. You have to specify the scala library as one of the input jars, and not as a library jar. Proguard looks at library jars as another source to find references to classes, but it won’t shrink library jars. Alternatively (this is what I do), you can extract all your referenced libraries, including Scala, right into the jar file that holds your applet, and then feed that single jar into Proguard. Proguard will also throw warnings and cancel the operation whenever it runs across a class that it can’t find, which happens several times when it tries to process the Scala library. The only solution I’ve found is to specify the -dontwarn option, which just tells Proguard to carry on despite warnings.
Shrinkers can’t account for dynamic access of classes (e.g. through reflection), which Processing and Proscene (and several other Processing libraries) rely on, so you have to keep specific classes. Originally I tried to keep only the methods that might get dynamically called by Processing but I couldn’t figure it out so I just kept all of Proscene (which was the only offender). I can imagine that there will be a lot of classes one will have to keep in order to keep all of the dynamic access happy, but I haven’t really looked into it. My current configuration looks like this:

-injars Daily.jar
-outjars Daily_Out.jar

-libraryjars 'C:\Program Files\Java\jdk1.6.0_23\jre\lib\rt.jar'

-dontoptimize
-dontobfuscate
-dontpreverify
-dontwarn


-keep public class * extends processing.core.PGraphics

# Keep Proscene
-keepclasseswithmembers public class remixlab.proscene.* {
    public ;
}

# Keep all registerXxxx() method callbacks in all classes
# -keep public class * extends java.lang.Object {
# 	public void pre();
# 	public void draw();
# 	public void post();
# 	public void keyEvent(java.awt.event.KeyEvent);
# 	public void mouseEvent(java.awt.event.MouseEvent);
# 	public void size(int, int);
# 	public void stop();
# 	public void dispose();
# }

# Keep Jul08b
-keep public class daily.Jul08b

This shrunk the jar from 8,987 kb to 709 kb, which I’d say is pretty good. Removing -dontoptimize further reduces it to 611 kb, and removing -dontobfuscate even further reduces it to just 439 kb. The size of this blog page is more than that (I checked :P). Quite impressive. As a note, it might be better to hold all of the libraries you might use in one location within the server – that is, putting all of the jars within a single folder somewhere – and then have the applets’ classpath point to those jars. Jar caching would work and the user wouldn’t have to download redundant code when viewing multiple applets; on the downside, new viewers would have to download a large number of libraries right off the bat.

I think there’s a lot of room for exploration in the field of generative content, especially in relation to games. I would LOVE to see randomly generated NPCs, enemies, towns, quests, spells, game mechanics, games, game generating algorithms, algorithms generating game generating… you get the point.