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.

---