A Platformer Level Generator

A Platformer Level Generator

My second /r/proceduralgeneration contest entry! I spent less effort on this than the previous round, but apparently there was just a lot less participation in general because of the steep hurdle of having to create a game in order for creating a level to be particularly meaningful. Instead of using F#, I decided to go with Typescript for this round, since I wanted an interactive online demo level that people could play around with. This was my first time using Typescript but it turned out to be pretty nice to work with; The platformer/level generator wound up just shy of 300 lines of code, most of which were not involved in actual level generation.

screenshot

Generating Platforms

The core of the generation function is at Github:level.ts. I basically roll a die, randomly chooseing a direction up, up-left, up-right, right, or down. Before going in any given direction, I make sure it doesn't interfere too much with the previous direction (for example, I wouldn't go up, then immediate go down.) To build the level, I start with an initial platform at 0, 0, pick a direction, build a random number of platforms out in that direction, and then repeat. In the following example code, for example, I would start with an initial platform, build right, then right again, then up-left.

    var platform = new Box(0, 0, 1, 1);
    platform = linkRight(platform, 3, 1, 1); // make a 1x1 box 3 units right from the first one
    platform = linkRight(platform, 1, 2, 10); // make a 2x10 box 1 unit away from the second box
    platform = linkUpl(platform); // make a box up and to the left from the third one

Series of Platforms

zoom-out

However, a level that goes in a random direction for every platform would turn out looking pretty .. random. While the random walk pattern looks nice for creating a cavelike network structure, it feels pretty aimless for a platformer level. It helps when you have a stronger direction of flow, both locally at the small scale (platforms form 'set pieces' that go in a particular direction) and at the large scale (the entire level doesn't double back on itself too often). For the first point, if I want to build platforms towards the right, I might as well build 3 or 4 platforms in a series. I encapsulate this in the repeat function, which will update the state of the platform and repeatedly call a link function.

    platform = repeat(3, linkRight);

For the second point, the generator tracks the last direction it was building new platforms in. Certain transitions are forbidden. RIGHT->RIGHT [which results in a long horizontal string of platforms towards the right] is forbidden, as well as "drops of faith" (large downward drops marked by caution blocks) when you've just been ascending up or leftwards (to prevent dropping back onto previously placed platforms).

var new_dir = randarr([RIGHT, RIGHT, RIGHT, UPRIGHT, UPLEFT, UP, DROP, DROP, DROP]);
switch (new_dir) {
    ...
    case DROP:
        if (prev_dir == UPLEFT || prev_dir == UP) continue;
        newbox.navi = "drop";
        yield * repeat(randi(1, 3), drop); break;

Doodads

doodads

The level looks kind of boring when it's just a bunch of platforms, so I scatter little decorations, like rocks, bushes, and grass, randomly throughout the level. Since we want to keep the distribution uniform, the number of doodads on each block is proportional to the width of the block.

function * getDoodads() {
    ...
    for(var box of this.boxes) {
        for(var j = box.w * 2; j --> 0;)
            if (random() < 0.2)
                yield [randarr(["bush", "grass", "rock",
                    "grass", "bush", "grass",
                    "rock", "mushroomBrown", "mushroomRed"]),
                    new Point(box.x + 0.5 + random() * (box.w-1), box.t + 0.5)];
    }
    ...
}

Keeping Track of Completion

Kind of a last-minute feature I threw in: save completed levels to Local Storage. 1) This gives you a sense of progress, and 2) it allows players to share particularly interesting level seeds with each other (or with me, if you want to report a bug).

Try it out!

Creating a Procedural Castle in F#

A Procedural Castle in F#

Introduction

My goals here were to implement, using F# and OpenTK, a procedural castle village generator. The code should be as clean as you should expect from a month-long programming challenge and should be simple, elegant, and powerful.

Notes on the high-level design of this system

The Frontend

The "front end" of the generator are a set of functions that generate Trees, Towers, Columns, etc. As you will see from the tree example below, the front end is concerned purely with construction rules. For example, the three basic rules for producing a tower are:

In code, this looks like:

let rec create () =
    let stories = rand.Next(4, 8)
    let segments = generateSegments (Options.sides) stories
    let tower = Capped(segments, Options.topstyle ())
    let tower = match rand.Next(4) with
        | 0 -> Buttress(tower, [Capped(generateSegments 4 3, SpireStyle.ConeNoFlag)])
        | 1 -> Foundation(tower)
        | _ -> tower

The Backend

Ultimately all the high-level types like Tower get converted into a set of primitive types -- cylinders, blocks, vertex-lists, etc, in the backend understands. This provides a uniform representation of objects. Utility classes such as bounding-boxes and spatial hashes only ever need to deal with "boxes" and "lists of vertexes" instead of having separate logic for each object they interact with.

Backend Logic Example: the Convex Hull

One example of backend logic is calculating the convex hull of a given set of points. This is useful because we first generate a bunch of structures, and need to figure out where to build the walls so that they surround all the structures we've built. The algorithm implemented here is the Graham scan, an O(n log n) complexity algorithm. To understand this function, it may be helpful to translate it piece-by-piece into English.

English F#
Start with the leftmost point let firstpt = List.minBy (fun (v:Vector3) -> v.X) points
To find the next point, take all the other points ... let nextpt pt = List.except [pt] points |>
and find the one with the smallest counterclockwise angle List.reduce (fun p q -> if Matrix2(p.Xz-pt.Xz,q.Xz-pt.Xz).Determinant < 0.0f then q else p)
Keep taking the next point until you find the first point again List.unfold (fun p -> let n = nextpt p in if n = firstpt then None else Some(p, n)) firstpt
module ConvexHull =
    let FromPoints points =
        let firstpt = List.minBy (fun (v:Vector3) -> v.X) points
        let nextpt pt =
            List.except [pt] points |> List.reduce (fun p q -> if Matrix2(p.Xz-pt.Xz,q.Xz-pt.Xz).Determinant < 0.0f then q else p)
        List.unfold (fun p -> let n = nextpt p in if n = firstpt then None else Some(p, n)) firstpt

Backend Logic Notes: The placement algorithm

I used a spatial hash to detect collisions when placing objects. When placing a new object, we check for collisions, spiraling outwards from the initial point until we find a location. Not too much to say here, other than if i had more time, I would have preferred using some kind of tree structure instead for more flexibility. Since I wasn't comparing object-object collisions directly, I could only resolve collisions at the size of a spatial hash cell. This led to a tradeoff between hash resolution (lower resolution means larger gaps between objects) and performance (each insertion and collision check is O(V) where V is the volume of the inserted object)

Example Generator: Trees

A tree is one of the most common recursively generated objects out there. There is a fundamental fractal nature about trees that makes it very suitable for generation algorithms.

type Tree =
    | Leaf of Vector3
    | Branch of Vector3 * float32 * Tree list

The body of the generate function is three lines: 1 to create a Leaf node, 1 to create a random point pos, and 1 and create a Branch ending on pos, recursively containing between 2 and 5 sub-branches.

let rec generate = function
    | 0 -> Leaf(Vector3.One)
    | n -> let pos = 0.6f * Vector3.Normalize (r.NextV3(-0.5f, 0.5f, 0.2f, 0.6f, -0.5f, 0.5f))
           Branch(pos, 0.03f * float32 n, [for i in 0..r.Next(2, 6) -> generate (n-1)])

The body of the _toPolygon function is below. Leaves are converted to dark green blocks. The Branch part is slightly more involved. We find the rotation+scale matrix c based on the endpoint of the current branch, and recursively apply it to all child nodes. After the recursive step, I have a list of child nodes, comprising of a combination of rectangular Block objects and Offset matrices representing a nested transformation. Both Blocks and Offsets are primitive types that my rendering function recognizes and can convert to a triangle array for rasterization.

let rec private _toPolygon (mat:Matrix4) = function
    | Leaf(dim) -> [ Offset(mat, [Block(Color4.DarkGreen, Vector3.Zero, dim) ])]
    | Branch(vec, width, children) ->
        let b = Vector3.Cross(Vector3.UnitY, vec)
        let rot = Matrix4.CreateFromAxisAngle(b, Vector3.CalculateAngle(Vector3.UnitY, vec))
        let c = if b.Length > 0.001f then rot * Matrix4.CreateScale (vec.Length) else Matrix4.Identity
        let cc = List.collect (fun (b, a) -> _toPolygon (Matrix4.CreateTranslation (4.0f * b * Vector3.UnitY)) a) children
        [ Offset(c * mat, Block(Color4.Bisque.Mult(0.2), Vector3.Zero,  Vector3(width, 4.0f, width)) :: cc)]
let toPolygon t = match _toPolygon Matrix4.Identity t with | [ Offset(c, f) ] -> f | n -> n

Finally: A note on (un)randomness

Procedural Generation is about controlled chaos. Instead of manually designing individual elements, we have to specify a design space of what kinds of structure the program randomly generates. This theme came up multiple times during the course of this project. A couple examples:

  1. I put off implementing the spatial hash until halfway through the project. Randomly placed Points (https://lucyuki.files.wordpress.com/2015/03/screen-shot-2015-02-16-at-4-56-34-pm.png) aren't really interesting in the long run. All the interesting details about placement happen around questions like "what is the minimum gap between two adjacent objects?" "Do nearby objects influence each other's orientation?" "do objects of similar size cluster together?" In the end, I found a pretty dumb generation strategy (generate large flat areas first, then add a few small objects to break up the space, then add large castle structures, then fill in the gaps with a final set of smaller objects" that yielded the results I wanted -- busy, but not too crowded. Since each new object had to align with at least one previously place object, the smaller units tended to clump and arrange themselves slightly on a grid.

  2. My initial stab at random towers was terrible -- when you choose a rule that says "pick 5 random tower levels and stack them on top of each other", you get what you'd expect -- a tower of barely related objects stacked on top of each other. In the final iteration, I redid the tower grammar to simply generate an N-sided cylinder and simply varied the style of the top and large-scale decorations. While this was more coherent, there should be even better rules available for generating structures closer to what you'd see in real life.

All in all, This was quite a fun project. Feel free to play with and extend the code - Even if you aren't familiar with F#, the overall structure of the code should make sense. If you're on OSX or Linux, the included Makefile should work assuming you have mono and fsharp installed. If you're on Windows, you're on your own, but try to open the included fsproj in Visual Studio.

FizzBuzz, Syntax Abuse, and the Pursuit of Perfect Code

FizzBuzz, Syntax Abuse, and the Pursuit of Perfect Code

If you're a programmer, you have likely seen the "FizzBuzz" problem at some point.

Write a program that prints the numbers from 1 to 100. But for multiples of three print "Fizz" instead of the number and for the multiples of five print "Buzz". For numbers which are multiples of both three and five print "FizzBuzz".

The nice thing about "FizzBuzz" as an interview question is that it is on the lower threshold of triviality, yet it manages to cover I/O, looping, conditionals, and arithmetic. With that said, here is how I'd write out FizzBuzz:

static void FizzBuzz() { 
	for(int i=0; i<100; i++) { 
		Console.WriteLine(
			i % 15 == 0 ? "FizzBuzz" :
			i % 3 == 0 ? "Fizz" :
			i % 5 == 0 ? "Buzz" : 
			(i.ToString()));
	}
}

Hmmm. For some reason, this small bit of code is already going to cause discussion. You could easily find a zillion different ways of writing FizzBuzz, the classic almost-trivial program, and everyone will have differing opinions on how to write it. As it stands, I've heard feedback such as "ugh, ternary operator is obfuscation" or "you need to comment that modulus operation since your maintainer won't understand it."

Ultimately, I can't say that these differing opinions are wrong. Everyone is a Blub Programmer, me included, So things we don't use look goddamn cryptic and things we've decided not to use look childlike in their simplicity. However, it seems to me that you'd be most productive in a team with other programmers of the same Blub-index, or at least in a team where everyone's index falls into the tolerance level for everyone else. Perhaps programmers get righteous in defending their favorite programming language or coding style in hopes that they convert others to their Blub level?

My most proficient languages are C#, F#, Javacript, Python, and Java. Perhaps it's just because it's what I write at work every day, but my Blub-level is somewhere between C# and F#. For every language that I write in, some parts feel really pleasant, like the ease of manipulating the shape of data in LINQ, or refining a DOM selection in jQuery (which Microsoft should totally have paid jresig to call Linq2DOM), or mocking an interface in Java with an anonymous instance. And other parts feel kind of awkward. But how much of that is the implicit tradeoffs we as programmers make every day versus the habits that I've built up, I'm not really sure.

[Code Bits] [Code Musing] [Language Rants]

Double Dispatch and Game logic and Message Handling

Double Dispatch and Game logic and Message Handling.

My previous survey of opinionated elf logic wasn't purely an academic exercise. I originally wrote the argument for dynamic multimethods in C# using Steve's Opinionated Elf example because I was explaining to someone how to handle Message routing between client and server in a multiplayer game. Namely, I have a set of Message types that all subclass a base Message:

class Message { }
class ChatMessage { }
class MoveMessage { }
class ActionEventMessage { }
class LoginMessage { }

and I was trying to explain how to divide up the logic between client-side and server-side components. you could write different client/server logic for individual message types.

class ClientsideMessageHandler { 
	void Route(Message m) { Handle((dynamic)m); } 
	void Handle(Message m) { /* unhandled message type ? */ }
	void Handle(ChatMessage m) { ChatWindow.Show(m.MessageSource, m.MessageText); }
	void Handle(MoveMessave m) { Entities.Find(m.EntityID).Move(m.newLocation); }
	// etc
}
class ServerMessageHandler { 
	void Route(Message m) { Handle((dynamic) m); }
	void Handle(Message m) { /* unhandled message type ? */ }
	void Handle(ChatMessage m) { /* route chat message to listening clients */ }
	void Handle(MoveMessage m) { /* validate then update nearby clients */ }
}

In my opinion this approach is better than explicit type-checking, both in terms of DRY and in terms of maintaining type heirarchies.

void Route(Message m) { 
	var c = m as ChatMessage; 
	if (c != null) { Handle(c); return; }
	.. etc..
}

Is DYNAMIC slow?!?!!

So after that example, lets examine the performance. With the caveat the benchmarks can be misleading, here are some numbers from running a simple MessageHandler that counts the number of different types of messages it's getting. I implemented a basic no-runtime-typing handler that maintains separate typed queues for each message type.

1 Million Message Calls:

So, a basic method dispatch takes a couple nanoseconds, adding in some basic type checking adds 10 nanoseconds, but with a caveat: this takes time proportional the number of types you're checking. for 20 or 30 types, the time would be 10 times as large. The Visitor Pattern manages to be the fastest double-dispatch mechanism, taking 17 nanoseconds regardless of how many types are used. Finally, dynamic turns out to be the slowest method, taking a full 235 nanoseconds per invocation. A quick sanity check in CPython:

>> timeit('for m in items: handler.handle(m)')
0.201900066844

Shows that this is about the same as the cost of a dynamic method invocation in Python. So, how many messages are you going to be routing per second? 100? A 23 microsecond routing cost is fairly easy to swallow in exchange for the simple code. Routing a 100,000 messages per second? If you only have 10 microseconds to respond to each message, it might be better not to waste 200+ nanoseconds per message on the routing dispatch.

Visiting Some Opinionated Elves

Visiting Some Opinionated Elves

Dear reader, have you experienced the treat that is Steve Yegge's writing? If not, I suggest that you go read some of his best writings now instead of wasting time here. Partly because his writings are charmingly entertaining, and partly because I want to discuss a topic that he's already written a bit about.

Now let's say one of your users wants to come in and write a little OpinionatedElf monster. ... Let's say the OpinionatedElf's sole purpose in life is to proclaim whether it likes other monsters or not. It sits on your shoulder, and whenever you run into, say, an Orc, it screams bloodthirstily: "I hate Orcs!!! Aaaaaargh!!!"

Steve's elf is a fairly harmless creature; it sits on your shoulder and simply judges everyone it meets. Some creatures it likes, some creatures it hates. Let's example some different ways to tackle this problem. Note that Steve covers a lot of ground, such as extensibility. I'm going to focus on the slightly narrower problem of code ugliness and maintenance hassle, but ultimately adhering to strong principles of encapsulation helps us out with extensibility as well.

Idea #1: Polymorphic method: Standard OOP logic. If you have a behavior that all creatures share but differ on implementation, it should be a virtual method. Make Creature define a virtual bool doesTheElfLikeMe() method, and creatures have to extend. The good thing about this is that with a proper type heirarchy, you can defer to base implementations. The bad thing is that a very abstract class, Creature now has a very specific concern, doesTheElfLikeMe, in its definition.

Creature::doesTheElfLikeMe () { return true; }

Orc::doesTheElfLikeMe() { return false; }

Spider::doesTheElfLikeMe() { return false; }

HarmlessPetSpider::doesTheElfLikeMe() { return true; }

class Elf { 
	void Greet(Creature c) { 
		say(c.doesTheElfLikeMe() ? "hi, friend" : "DIE FIEND");
	}
}

In this example, The elf can be perfectly happy about a HarmLessPetSpider, which subclasses Spider, while still hating Shelob the EvilGiantSpider, and EvilGiantSpider doesn't even need its own implementation of doesTheElfLikeMe because it defaults to the generic Spider behavior. However, adding a new Elf, or an OpinionatedGoose, involves goine to each individual Creature source file (possibly ones you don't have source access to), and adding a new method. This seems like a maintenance nightmare.

Idea #2: Monkey-patching Steve gives an example of a Ruby definition where when the Elf file gets loaded, it opens up all the classes it cares about and patches in a doesTheElfLikeMe function. This avoids the design issue of having the Elf's preferences scattered around a large number of different code files. This works in most dynamic languages. Here's an example of Ruby and Javascript.

// in the Elf.rb:
class HarmlessPetSpider
def doesElfLikeMe; return true; end
end

// in Elf.js
Spider.prototype.doesElfLikeMe = function() { return false; };

The main issue that remains with monkeypatching (aside from incompatibility with static type systems) is that the data is still not encapsulated in the Elf module. Now, this may be simply my preference and experience with statically typed languages, but I don't like the idea of a system design where modules and types are giving each other functions all willy-nilly. Where is the separation of concerns? the encapsulation?

Idea #3: Runtime type checks Why does Creature need to define doesTheElfLikeMe in the polymorphic example? Shouldn't the Elf figure out whether he likes a creature or not? The code does seem to be very backwards. If we added an OpinionatedGoose we shouldn't have to open up every single creature file again to add a doesTheGooseLikeMe method as well. If we simply put the logic in the Elf or Goose class, maintenance of the feature becomes simpler.

class Elf { 
	bool DoesElfLike(Creature c) { 
		if (c instanceof Orc) return false;
		if (c instanceof HarmlessPetSpider) return true;
		if (c instanceof Spider) return false;
		return true;
	}
}

Of course, this has its own drawbacks. Now we've lost the type-heirachy. meaning, if I accidentally put the instanceof Spider check before the instanceof HarmlessPetSpider check, our type system is not going to tell me that I made a logic error, I've simply introduced a bug into the code.

Idea #4 -- Visitor Pattern Ah, The good old Gang of Four has not deserted us in our time of need. As it turns out, runtime multiple-dispatch is a fairly common pattern, common enough that quite programmers frequently independently come up with a pattern on their own that has come to be known as the Visitor pattern.

interface CreatureVisitor { 
	void DoesElfLike(Creature c);
	void DoesElfLike(Orc c);
	void DoesElfLike(Spider c);
	void DoesElfLike(HarmlessPetSpider c);
}
class Orc : Creature { 
	void accept(CreatureVisitor v) { v.Visit(this); } 
}
class Spider : Creature { 
	void accept(CreatureVisitor v) { v.Visit(this); } 
}
.. etc ..

class Elf : CreatureVisitor { 
	void DoesElfLike(Creature c) { c.accept(this); }
	void Visit(Creature c) { Greet(true); }
	void Visit(Spider s) { Greet(false); } 
	void Visit(HarmlessPetSpider s) { Greet(true); }
	void Visit(Orc o) { Greet(false); }
}

hmmm. Well, now we've added a bunch of boilerplate on every single Creature type, since every single one of them has to define its accept method. And now, your "list of all subclasses of creature" is hard-wired into your CreatureVisitor. When you need to add a new Creature, you'll have to add it to the list of all your visitors and your base CreatureVisitor interface. This could really be a big issue. Shelob herself is not going to bother us a whole lot, since her GiantEvilSpider can still inherit Spider.accept behavior, but actually adding a new type that the Elf has an opinion on involves changing CreatureVisitor and all its implementors, including any OpinionatedGeese, even if their opinion hasn't changed. Is this much boilerplate really worth the hassle?

Well, maybe. In "enterprise"-land, You'd expect the CreatureVisitor bits to be downstream of the Creature bits. So you could manage change by first adding a new Creature, then updating your Visitors in one go. Incidentally, this suggests that writing general-use visitor types actually leads to more brittle code, since you'd want them packaged as close to the implemetation of the visitors as possible to void breakage. Your Creature taxonomy becomes aggravating to modify, but your Visitor taxonomy becomes easier to modify. The benefit becomes noticeble when you get more Visitor-like things. When your OpinionatedGoose and his pal OpinionatedToaster, or even other functions based on Creatures, such as Serializers or Renderers or what-have-you, come around and they have their own ideas about what they want to do to a Creature, then your machinery is already there; the accepts and Visit slots are ready for implementation. Incidentally, this Creature-axis rigidity behavior comes up in functional programming languages fairly often, since in one of my random musings I realized the visitor pattern is an OOP analogue of functional pattern matching. But that is another story and shall be told another time.

But there will always be a little nagging voice in the back of your head. Your sense of DRY is tingling a bit because of the duplicated accept on all Creature types, and especially the list of types on the CreatureVisitor interface. Why do we have to add this boilerplate to implement something as fundamental as double dispatch?

Idea #5 -- polymorphic dynamic dispatch in C# C++/Java/C# resolve virtual functions via runtime-dispatch the type of the bound object but not on the types of the arguments. Our dynamic language friends such as Python/Ruby/ do not support a polymorphic dispatch; although they do route method calls at run-time, they do not discriminate method signatures based on type arguments. Some typed languages, such as Lisp, support dispatching based on the runtime types of the argument. While neither naive dynamic binding nor naive static binding can implement multimethods, the introduction of scoped dynamic dispatch in C# gives us a new way of implementing our OpinionatedElf:

class Elf { 
	bool DoesElfLike(Creature c) { return doesElfLikeType((dynamic)c); }
    bool DoesElfLikeType(Creature c) { return true; }
	bool DoesElfLikeType(Spider s) { return false; }
	bool DoesElfLikeType(HarmlessPetSpider s) { return true; }
	bool DoesElfLikeType(Orc o) { return false; }
}

And there we go. We avoid touching external files like Idea #1 (adding methods to all Creatures for each opinion). We have all the logic encapsulated in our class without monkey patching anything like in Idea #2. We are about as succinct as explicit type-checking in Idea #3 without losing the type heirarchy information and being subject to ordering errors. And, we avoid the boilerplate required for Idea #4, the Visitor pattern.