carrotcake Blog 🍃

official devlog for carrotcake written by Louis Durrant

Thursday Report: A Whole New World

Posted on Mar 28, 2019

I took a break from the Thursday report last week because I was still knee-deep in developing a system that would generate fresh, unique maps for The Garden Path.

This was an area I had been bracing myself for since I began learning to program roughly a year ago now. Alongside AI for the characters, it was an area I had anticipated I may need to outsource for.

I saw a great quote yesterday, “You learn just enough to do, and you try to do more than you learned”. In that spirit, I decided to see how far I could get, and how much I could learn.

I found myself encumbered with a system hundreds of lines long that simply was not working. I would rubber duck debug into oblivion, frustrated when everything in writing seemed to make sense, but wasn’t translating when the code was being run.

I ultimately decided it was time to take everything that I had learned from my first attempt, and rewrite it from scratch with a fresh head. By some stroke of luck, it worked seemingly immediately, and all in less than 100 lines of code.

So, how does it work?

The starting point is the ‘acre’ I mentioned a couple of blog posts ago. An ‘acre’ is made of 9 tiles, and so I divided the acre into 12 effective ‘sides’. Think of it like a jigsaw piece, which usually has 4 ‘sides’, either protruding or concaved. In order to know what pieces can sit next to each other, those sides need to be matched.

Here’s the guide I made that helped me along the way:

Certain environmental features need to be preserved to make a cohesive map. For instance, an acre with a river ending on it’s right side, will need to be connected to an acre that has a river coming in the from the left side.

For each acre, an entry in a JSON(!) file is made. It includes the ID number of the acre, and what can be found on the edge of each of it’s sides. While I’m sure there’s a way to automatic this process, that’s something I can worry about later. I’m happy inputting the information manually for now.

The game see’s all the points where an acre is spawned, and needs rules to know which acre ID it spawns there (rivers next to rivers, etc), with some degree of randomness.

It starts from the top left. This is just because that’s how I laid it out, it might be more interesting if I scatter it, but I’ll be working with it scanning left to right for now.

The very first acre point has absolutely no rules attached to it – it could be anything. So, the game takes a shot in the dark and picks an acre at random.

The tricky part comes next. Before placing the next acre, it must write rules for what can appear around it. The game looks at the acre it just placed, then compares it against all other acres. To use my earlier example, if there’s a river on side 5, it must find all acres with a river coming from side 11. It does this for all acre spawn points adjacent to it, creating a whitelist for each of those points. When the game comes to picking that acre, it must select an ID at random from that whitelist.

Unfortunately, as I quickly found out, certain future tile placements may begin creating contradictory whitelists.

Take this example. Acre point 2 is spawned, and it creates a whitelist for acre point 4 (it’s southern neighbour). It says, “the river in my acre is going from left to right. There’s clear space at the bottom of my tile, so I’m going to whitelist an acre that is completely clear – one that has no river’. That makes perfect sense, so it adds it to the whitelist.

Since we’re scanning from left to right, acre point 3 is next to spawn. It says, “I have a river in my acre coming from the bottom, curving to right. I need an acre next to me that has a river coming from the left”.

The trouble is, acre point 2 has already whitelisted an acre that’s completely clear, which would not match the acre that acre point 3 has selected.

The solution is that I had to have each acre point write both a whitelist and a blacklist – both what it can be and what it can not be. Now, when acre point 3 is writing its whitelist, it writes in it’s blacklist that it can’t have an acre with nothing in it. It sees there’s the same acre in both it’s blacklist and it’s whitelist, so it removes it from the whitelist.

And that’s it, so far. I think it’s quite a neat little solution.

The river paths in the image are deliberately very rigid for the sake of me seeing how they work, but they needn’t be. These generating paths can become very natural – widening, curling, all within the same acre so long as it arrives at the right ‘side’.

This is also exciting because it doesn’t begin and end with rivers. This will allow interesting height-tiers across the map, it will allow an acre of birch trees fade into an acre of fir trees, or maybe even allow the addition waterfalls.

As with anything random, it’s not the ‘making-it-be-random’ part that’s tricky, it’s controlling the chaos within set boundaries. It’s very possible I run into issues that will require me to set harder parameters. Should I allow cyclical rivers? Is the chance of a map generating too many rivers too high? Are certain crucial acre types suddenly less common? All these factors I may eventually have to account for and control.

For now though, it’s a thrill loading up the game and landing in an entirely new map. I can feel a little bit of that urge to explore in my gut.

I’m very keen to see how this all comes into play as I begin creating the final art assets next year.