July 12th, 2020

🐮 "Is it my cow?" Elm game Postmortem - Part 1 - The idea and core problem

Article cover photo

On May 9th 2020 Elm Game Jam #4 started. It was an opportunity for me to test my gamedev skills after years of break from it, but in different (Functional Programming) paradigm this time. Also, it's not a secret that Elm is my favourite programming language that still inspires me a lot.

You can play the final version of my game here.

💡 The idea

Because the topic of the game jam was Animals/Nature, I had to come up with the idea of the game that intersects with it. There were 3 main thoughts in my mind map on the beginning:

  • Animal - because of the game jam topic
  • SVG - because I am not an artist but personally I find it easier to design vector graphics and there is elm/svg package
  • Randomness - because it is something that looks trickier in Elm than in JS

Combining all of these resulted one idea - cow patches. They look random, SVG curved shapes can be used to represent them on the screen and they can be spread on a cow's body.

Next thing was to gamify that concept. I thought it would be nice to generate multiple cows that have different patterns, and make player find specific one among them.

🎲 Core problem - random patch

I like to create proof of concept of the core problems. Also, as far as I remember from a "Eat that frog" book (that I read a long time ago) that it is a good thing to start with the hardest and most important task first - random patch generator in my case.

Naive approach

First and naive approach was to spread some random 2D points in specific rectangular region and connect these points with lines as they are. We need some random generator with signature like follows:

randomPoints : Random.Generator (List (Int, Int))

From the SVG documentation, there is a path element that should have d attribute which takes specific string with imperative-like instructions for the browser how to draw the path as value. At the beginning I've focused on the simplest path instructions:

  • Mx,y - moves to specific (x, y) point
  • Lx,y - draws a line from the last point to (x, y)
  • Z - closes the path

I knew it from the start that just randomly spreading the 2D points and converting them just into a SVG path won't work but I wanted to see that my predictions are in line with reality:

Naive cow patch generating algorithm result sample

There are at least 3 problems with this algorithm:

  1. generated shape contour lines go in completely random directions so it results with a shape that consists of a triangles and spikes more likely.
  2. when some parts of the path interferes with each other it may create white/inverted holes like that on the center of the above's sample.
  3. we have straight lines instead of smooth contours

I've decided to fix issue 1 and 2 first. I wanted to adjust randomized path so it has some more stable direction. My idea was to generate points in clockwise direction. First what came to my mind was to sort points generated from the naive algorithm somehow but I guess it would require some trigonometric functions to achieve that.

Approach #2 - trigonometry?

The second idea was to generate random points that go clockwise out-of-the-box without any sorting. For instance, given specific center point of our shape, we can generate some points with some random distance relative to that center point. Then, given the distance we would need some angle that advances on each generated points (clockwise):

Clockwise compliant points spread algorithm visual result representation diagram

It is not that I am afraid of the trigonometry or something, however, I felt that there must be some other way to approach this problem. Also, I wanted to create an algorithm that does not limit points to circle or ellipsis-like area, but make one that makes use of full rectangular area.

Approach #3 - without trigonometric functions

Another algorithm that came into my mind written in pseudocode:

  1. Given rectangle (A x B) which sets up random patch boundaries, calculate it's circumference (2A + 2B)
  2. Generate some random numbers from 0 to circumference
  3. Sort these numbers in ascending order
  4. Project these numbers into 2D points placed on rectangle circumference, starting from up side (smallest numbers), then right side, then bottom side and finally on left side (biggest numbers)
  5. Calculate center point of the rectangle (0.5A, 0.5B)
  6. For each 2D point from step 4, move center point to projected 2D point but by random relative distance from 0 to 1 where:
    • 0 means points stays in the center point
    • 0.5 means that point should be placed halfway between center point and projected point
    • 1 means that point should be the same as projected point from the step 4

Here is a function that makes use of that algorithm copied straight from the game source code:

randomBlobPoints : Float -> Float -> Int -> Random.Generator (List Point)
randomBlobPoints width height nodeCount =
        boundaryPerimeter =
            width * 2 + height * 2

        cx =
            width * 0.5

        cy =
            height * 0.5

        nodeLocationToPoint : Float -> Point
        nodeLocationToPoint location =
                p =
                    location * boundaryPerimeter
            if p > width + height + width then
                ( 0, height - (p - width * 2 - height) )

            else if p > width + height then
                ( width - (p - width - height), height )

            else if p > width then
                ( width, p - width )

                ( p, 0 )
    Random.list nodeCount (Random.pair (Random.float 0 1) (Random.float 0.65 1))
        |> Random.map (List.sortBy Tuple.first)
        |> Random.map
                (\( progress, relativeDistance ) ->
                    followPoint ( cx, cy ) (nodeLocationToPoint progress) relativeDistance
                        |> Tuple.mapFirst ((+) cx)
                        |> Tuple.mapSecond ((+) cy)

and some helper function that makes last (6th) step of the algorithm easier:

followPoint : Point -> Point -> Float -> Point
followPoint ( startX, startY ) ( targetX, targetY ) relativeDistance =
    ( (targetX - startX) * relativeDistance, (targetY - startY) * relativeDistance )

Such generated points are already sorted clockwise so connecting them in order will result a shape that is closer to our goal:

Although you may notice that in practice code differs a bit from the presented pseudocode due to the two reasons:

  1. Elm is closer to be declarative than imperative programming paradigm language, so for instance I had to tie random values from the step 2 with random distances from the step 6 together (Random.pair with two random floating point numbers).
  2. In practice, I've experimented a bit with each point distance (from the center of the rectangle) minimum limit and found out that 0.65 makes the shapes look a lot better than values closer to the zero.

Smoothing the lines

Now, we just have to turn our randomly generated shapes into smoother ones. Switching from straight lines into Bézier curves were first that came into my mind. Although, when more than two coordinates describes the part of the path, calculations gets complicated. I've experimented with some custom math formulas but with miserable effects. After that, I've decided to Google a bit but didn't know how to name my problem yet. I came across this article first: "Smooth a Svg path with cubic bezier curves". I've tried to adapt JS code from it into Elm, but something went wrong during that process and effect was still miserable. Then, I came across this: "Smooth Polygon Convex Hull". I didn't tried to adapt JS code into Elm this time, however thanks to this article I believe it was my first time I came across some mathematical concept called "Catmull-Rom curve".

Then, when I knew what I am searching for, somehow I came across this Elm package: folkertdev/one-true-path-experiment which has really nice documentation with pictures. This was exactly what I needed! Shame on me that I haven't asked for help on Elm Slack... Also I couldn't believe that I would find such specific problem solution in the form of an Elm package. I was so focused to find a ready to use solution in largest and most popular programming community which JavaScript currently probably is, that I didn't realize that Elm community was able to solve this already with beautiful API in a Elmsh pure functional manner. Big kudos to @folkertdev!

So, here's the final code of the module for random patch generation that I extracted with more generic name SvgBlob as it can be contender for Elm package perhaps?: SvgBlob.elm

⏩ To be continued...

This is the first post that opens the series of the blog posts where I tell a story with some details how I developed my game. Next time we'll focus on creating a some graphics of a cow and placing it multiple times among some green scenery.

Stay tuned!

19.07.2020 update! the part 2 is already available:

"Is it my cow?" Elm game postmortem series:

  1. The idea and core problem (currently reading)
  2. The cow without legs
  3. Animation
  4. coming soon...