Side Projects: Gnomon

As I'm frantically running around doing stuff, I figured it'd be a good time to dump some of the small projects I've worked on in my spare time.

First up, the little Clojure/Scala interop project tentatively called Gnomon. Nothing to see here graphically, the fun part is just having a little space in which to evaluate Clojure directly. Rendering commands are pushed from the Edit Window thread (using the (render-command ...) and (render-static ...) macros) by simply converting the s-exprs to strings, and then evaluated on the render thread. The bulk of the app is written in Scala, but all the fun stuff happens in Clojure.

The editor itself is amazingly crude, but it was more a proof-of-concept for a joint Scala/Clojure project. There's a little awkwardness due to Scala frequently emitting a variety of name-mangled classes, but it still works surprisingly well - Clojure provides a certain flexibility and ridiculously easy runtime augmentation, while it's easier to generate a (more) efficient statically-typed framework in Scala, and Java interop on both sides provides for easy communication.

I'd love to follow this up at a later date with a proper project.

Wibble!

Mmm, lunchtime blogging.

First off, have a screenshot:

I've been playing with exponential shadow maps, and they're kinda fun. Not sure whether I'll use them over variance shadow maps, but it's tempting. I've also been messing with lit particles, although this has not been superbly successful. The image shows some alpha-tested jobbies that interact nicely with the deferred lighting, cast shadows and generally behave themselves, but the ultimate aim is to have nicely lit smoke effects and they do little to advance that goal.

I've been playing with rendering a lot of small fake-sphere particles to a render target and blurring it as a post process, but it's a bit too crude to work and smacks of megaparticles. I may go for a simple volume rendering approach.

I have moral objections to CPU-driven particles, which precludes the standard sort-and-render which makes such things easy. I'm also avoiding texture fetch in general (I got burned by ATI's render-to-vertex-buffer non-implementation in the past), so simulating particles in a position texture and doing the sorting GPU-side is not tempting either, although I may yet go back to that. In the meantime, the hunt for order-independent transparency continues!


do => for

I can't write much about this because I'm still feeling my way, but using a for expression to perform computation inside a monad is... weird, but quite nice. I'm not sure I prefer it to Haskell's do notation.

It's odd enough that I want to dump my exploratory fiddlings anyway, so here's a stub for the conflict-resolution step for two entities colliding after a movement phase. Note the awesome game logic for deciding the winner:

   private def collidePair( a: Ent, b: Ent ) : (Ent,Ent) = {
      val ab2 = for{
        aPos <- a.get[Int3]("position") if( a("solid",true) )
        bPos <- b.get[Int3]("position") if(aPos == bPos && b("solid",true) )
        aPosHis <- listToOption(a.history[Int3]("position").drop(1))
        bPosHis <- listToOption(b.history[Int3]("position").drop(1))
      } yield {
          val aWins = Math.random < 0.5
          if( aWins )
            (a,b.extend("position",bPosHis))
          else
            (a.extend("position",aPosHis),b)
        }
      ab2.getOrElse(a,b)
    }

Slightly odd exploratory code. Anyway, it crudely rips the current position from both entities, as well as their previous position, and yields an Option containing a tuple of new entities. If any of the extraction steps or predicates in the for chunk fails, it simply returns the original pair of entities.

Errors abound, of course. An entity doesn't always have a 'last' position, and if it does this in no way implies it's a reasonable place to go if it fails the conflict step. The listToOption thing is ugly as well. Bleh. But my original point stands: for is a weird and flexible beast in Scala, which I didn't appreciate before.

Ehm, a monad perhaps?

Disclosure: I know nothing about monads, or category theory in general, to an amazingly good approximation. I apologise in advance for any botched terminology or shoddy thinking.

Also, this kind of thing is a wonderful antidote to days staring at C++. Really. That's why I'm blogging about it, even though progress is pitifully slow.

Anyway, continuing with the code in previous entries, I ended up with these little methods (with minor implementation details in the Empty object to produce errors/None/Nil, resp.):

def apply[B]( w: Var[B] ) : B = w match {
  case _ : v.type => x
  case _ => Env.this.apply(w)
}
def get[B]( w: Var[B] ) : Option[B] = w match {
  case _ : v.type => Some(x)
  case _ => Env.this.get(w)
}
def history[B]( w: Var[B] ) : List[B] = w match {
  case _ : v.type => x :: Env.this.history(w)
  case _ => Env.this.history(w)
}

They fetch a variable, fetch an optional variable, and get a list of all the values of a variable. They look pretty similar to me. Something niggled at the back of my head, especially combined with the code in Empty which was essentially spitting out _|_ or some zero-like object.

Hey, aren't lists and options (Maybes)... monads? And don't some monads have a sort of addition and zero? Given those, can't I cut out that irritating repetition from my example?

Well, the first few attempts failed to compile, so I threw syntax at it until:

def fetch[A,B]( v: Var[A], unit: A => B, mplus: (B, () => B) => B, mzero: () => B ) : B

def apply[A]( v: Var[A] ) : A = 
  fetch( v, (x:A) => x, (x:A, _: ()=>A) => x, () => error("var not found: "+v) )

def get[A]( v: Var[A] ) : Option[A] = 
  fetch( v, (x:A) => Some(x),  (x:Option[A], _: ()=>Option[A]) => x, () => None )

def history[A]( v: Var[A] ) : List[A] = 
  fetch( v, (x:A) => x :: Nil, (x:List[A], y: ()=>List[A]) => x ::: y(), () => Nil )

Well, that seems to compile, even if its ugly. The implementation inside Env and Empty now looks like this:

//Env
def fetch[A,B]( w: Var[A], unit: A => B, mplus: (B,()=>B) => B, mzero: () => B ) : B = w match {
  case _ : v.type => mplus( unit( x ), () => Env.this.fetch[A,B](w,unit,mplus,mzero) )
  case _ => Env.this.fetch(w,unit,mplus,mzero)
}

//Empty - easy!
def fetch[A,B]( v: Var[A], unit: A => B, mplus: (B,() => B) => B, mzero: () => B ) : B = mzero()

So, the mighty feat of transforming three simple four-line functions into three one-liners! Er, and a four-line definition, plus an extra declaration. Score one for abstraction, or something.

I'd like the syntax to be nicer, though, and I'm pretty sure I don't like the use of ::: (that's the list concatenation operator in Scala, for reference). Eh, anyway, I thought it was neat enough to be interesting, and it extends nicely. Adding a version of apply with a default value is very nice, for example; mzero just returns the default, and the inclusion of the default value means the type parameter is inferred.

Type Frustrations

Warning: this entry is largely a rant about my own ignorance.

I should have remembered this, but there's a big annoying thing that crops up whenever I try to get overly-generic in Scala.

Type erasure.

My understanding of this is that it's a pain in the arse. It has something to do with brutally discarding useful type information at runtime, such that List[Int] has the type List (or possibly List[Object]). Never mind that List is not even a type, it's a type constructor, some combination of the JVM and the writhing tentacles of an entire herd of shoggoths¹ renders it a nigh-useless blob. Dark magic makes it work perfectly when all manipulations are done at compile time, but just try pattern matching or reflection with it...

What this means is that the following code will not compile:

//NB: Will not compile, type of [A] is unchecked due to erasure
def propTest( p: Property ) = p match {
  case li:ListProperty[Int] => println( li.value.toString )
  case lf:ListProperty[Float] => println( lf.value.mkString(":") )
  case _ => println( "unknown property: "+p.toString )
}

Of course, this non-compilation is slightly less annoying than when you only try to pattern-match against a single instance of a parametrised type. In this case the compiler will emit a warning, but still compile to (apparently) working bytecode. If we dispense with the ListProperty[Float] case, the above will compile, li will match any ListProperty, and ClassCastExceptions or similar evil will almost certainly ensue.

Ignoring compilation warnings is (as we all know) incredibly dumb, and re-running compilation with the -unchecked flag will produce more helpful messages about what exactly is completely broken. It's still somewhat vexing that this compiles at all, when the chances of it doing anything useful are effectively zero.

I guess I can't complain overmuch, pattern matching against arbitrary type constructors appears to be something Haskell chokes on too, although with less smelly default behaviour and a different reason. I'm not sure how much of this is down to my downright shoddy understanding of type systems in both languages, so I'll be fiddling with this a lot more. In the interim, without some method for defining simple container properties, including type checking and pattern matching against them, the 'property bag' model appears dead in the water for my chosen implementation language.

As I said before: arse.

¹What the hell is the plural of 'shoggoth'? For that matter, what's the collective noun for 'em?

Functional Update Musings

Recently I've been focussing a lot on the rendering part of this project. Quite fruitfully at times, but it certainly wasn't my intention.

The reason for this is simply when I sat down to work on some gameplay stuff, I found a hard problem, and the solutions I've arrived at so far have not been... nice.

As fair warning, this is a brain dump, and a long, boring one at that. It contains much partly-functional waffle because my brain is full of partially functional waffle.

Background: Mostly for my own illumination, I've been trying to use more functional idioms in this game than is strictly sensible. I've mentioned before that I wish to have a (mostly) immutable world, for example. The world update step therefore creates a new world state every 'turn'. The current world state is stored in a mutable variable at the end of each update, but other than that the entire update should be immutable and cuddly from a gameplay viewpoint.

Problem: Creating a suitable update step for my basic case is very easy. The only entities that can affect the world are Agents. Each agent has a (poorly named) 'energy' integer value. When an agent has zero energy, it can act. Actions themselves are the things that change the world state, they are essentially partial functions of type Action :: WorldState -> WorldState, and almost all have the secondary effect of reducing the current agent's energy value when they're executed. After the current agent has acted, the agent list is sorted, some simple transformations are applied to the entity list (dead creature agents are replaced with corpse entities, for example) and time is advanced to bring another agent into relevancy.

This works after a fashion, but certain things are more sensibly represented as continuous functions of time than as agents that act with some (possibly inconsistent) frequency. A better way might be to allow these functions of time to run after the current agent acts, as conveniently we implicitly have the delta time before the next agent is ready to act. This will allow us to damage creatures in lava/acid, or heal creatures that are regenerating, for example. Easy enough, we can make something like TimeFunction :: Int -> WorldState -> WorldState. This is very ugly in practise, especially if there is no ordering defined over the set of active TimeFunctions (consider the joyous difference in observed state if a timefunction spawns a monster and then another damages/kills it, versus damaging monsters then spawning them). There are also potentially huge problems if the list of active TimeFunctions is part of the world state, subject to being updated by TimeFunctions as they run. Blurgh!

There's another big source of ugly too: edge detection. In general, we're quite interested in observing certain changes in world state. An example which Andrew Doull writes about here is a quest to scare seven goblins, which I think can be done by detecting changes in the afraid state of goblin entities. If we perform a comparison of world state before and after the player-controlled agent acts, we can in theory unambiguously attribute any newly-scared goblins to the player and update quest progress. Again we can create something like: EdgeDetector :: WorldState -> WorldState -> WorldState, but it's even nastier now than the case for TimeFunctions. We also have three transitions that may be of interest and could have associated detectors: comparing the original world state to that after the current agent acts; post-agent-action world state to post-timefunction world state; and original state to post-timefunction world state. This would allow us to differentiate between the player killing a goblin with a mace and the goblin burning to death because it stupidly fell into some lava, even in the absence of creatures storing their last attacker or whatever.

It may help to constrain these ugly bits somewhat. For example mandating that TimeFunctions must define a strict ordering and only affect the list of entities and their own internal state, whilst EdgeDetectors can only update their internal state. This in turn means that some other object has to dig through the EdgeDetectors to extract useful data, but I suppose that's not too evil. Both edge detectors and time functions are created and destroyed only by agents, which is closer to the simplicity of the initial design.

But even with these slightly draconian measures in place, a single update is a far nastier affair than I feel it has any right to be, with multiple intermediate world states, and I'm unwilling to set this down in code outside my messy prototype framework.

I've been wrestling with the few papers I've found talking extensively about reactive/game programming in functional languages (by which I mean Haskell) but it's dense, dry, nearly unintelligible stuff as far as I'm concerned. Admittedly they're generally solving the far harder problem of realtime games, whereas I currently go the cheatsy route of using a great deal of mutable state for all realtime code paths such as rendering.

Anyway, brain dump complete. I hope I'll find a better solution and can come back and mock my doubtless shocking ignorance in this post, but right now it just makes me uneasy. The net result of which is my experimented with deferred rendering pipelines and funky post process effects, so its not all bad.