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.
The "front end" of the generator are a set of functions that generate
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
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.
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.
|Start with the leftmost point||
|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||
|Keep taking the next point until you find the first point again||
module ConvexHull = let FromPoints points = let firstpt = List.minBy (fun (v:Vector3) -> v.X) points let nextpt pt = let firstpoint p q = if Matrix2(p.Xz-pt.Xz,q.Xz-pt.Xz).Determinant < 0.0f then q else p List.except [pt] points |> List.reduce firstpoint List.unfold (fun p -> let n = nextpt p in if n = firstpt then None else Some(p, n)) firstpt
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)
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
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.
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
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
fsharp installed. If you're on Windows, you're on your own, but try to open the included fsproj in Visual Studio.