Naive City Generation

Last week I played with an idea for city generation, I didn’t want to do my regular old 2D view, I actually wanted to challenge myself a little, so I looked towards 3D. I’ve known of a JavaScript library for a while called THREE.js, and I’ve tried to use it before but I never really had an end goal in mind, so I only went through the examples, but this time, there was an end goal, and I feel like the result wasn’t all that bad.

It’s fairly commonly known that to generate a city there’s a lot of ideas and algorithms that can be used, L-Systems and Space Colonisation for roads, Binary Space Partitions for building interiors, every element that you build needs to be generated somehow, and that’s what these algorithms are for. For this little project, I just wanted to get a quick prototype up and running, a proof of concept, if you like.

I decided that to keep it basic, I’d have only three types of ’tiles’, a building tile, a road tile and a grass tile. I also decided that I was only going to render a general city outline, you’d see the roads and the shape/size of the buildings, but you wouldn’t be able to go inside any of the buildings (although this could potentially come later).

Once I had decided on this, it was time to decide how to lay them all out. I essentially generated a 2D array of values, which could be ‘road’, ‘building’ or ‘grass’.

Here’s the code for the grid generation:

var grid = [];
for(var x = 0; x <= 12; x++) {
  grid[x] = [];
  for(var y = 0; y <= 12; y++) {
    if(x % 4 == 0 || y % 4 == 0) {
      grid[x][y] = new Road(x, y);
    } else {
      if(Math.random() > 0.5) {
        grid[x][y] = new Building(x, y, Math.ceil(Math.random() * 3))
      } else { 
        grid[x][y] = new Grass(x, y);
      }
    }
  }
}
return grid;

So, we’re generating 12 arrays with 12 values, this gives us a grid that is 12 blocks by 12 blocks. The logic follows that if x is divisible by 4 or y is divisible by 4, then that block will be a road block. This gives us a nice grid pattern for the roads, with a border around the edge of our ‘city’, and leaves 3 x 3 plots of land for buildings or grass to be placed in between. Whilst this doesn’t necessarily match up to how cities look in real life, it emulates the grid pattern that we see in major cities to a good enough extent for our prototype. The buildings/grass part of the logic is essentially a coin flip, there’s a (roughly) 50/50 chance of the remaining blocks in our city being buildings/grass.

The next step is to actually draw this to the screen. As you can see in the code snippet above, I’ve actually called constructors when assigning elements of the array. I had written a data structure for each type of block. Each block had coordinates in its constructor parameters to decide where the block should be placed, the only difference was the building block. I gave the building a height as well, this would ensure that we would have some different sized buildings, and make it look more realistic. The buildings generated would all be between one and four ‘stories’ high. Having identified the dimensions/position of each block, it was time to create the mesh.

A mesh is something that THREE.js can take and render to the screen. To create a mesh, you need a couple of things, a material and a ‘geometry’. The geometry dictates the shape of the object and the material dictates the way the object looks, what colour it is, or if it has a texture. For all of the blocks, creating these was very straightforward.

Building:

this.geometry = new THREE.BoxGeometry(1, height, 1);
//Coloured a mid-grey
this.material = new THREE.MeshLambertMaterial({ color: 0x888888 });

Road:

this.geometry = new THREE.BoxGeometry(1, 1, 1);
//Coloured a dark-grey
this.material = new THREE.MeshLambertMaterial({ color: 0x333333 });

Grass:

this.geometry = new THREE.BoxGeometry(1, 1, 1);
//Coloured a bright green
this.material = new THREE.MeshLambertMaterial({ color: 0x22FF32 });

Then for each block all that was left to do was create the mesh:

this.mesh = new THREE.Mesh(this.geometry, this.material);

Finally, on the mesh object, I just had to set the position:

this.mesh.position.x = x;
this.mesh.position.y = 0;
this.mesh.position.z = y;

This is somewhat confusing to you probably, and that’s because it’s just straight up bad code. What I’ve done is transferred from a 2D array into a 3D space, meaning that our grid has now been flattened, z becomes y, and now we have to fill y with something. If you imagine that we’re looking at a board that’s standing up straight, with our y axis running up/down the board, and our x axis running horizontally along the board. Imagine now, the board falling over. When the board hits the floor, the y axis no longer runs up/down the board, it’s now the z-axis doing so, the y-axis will now be extending out from the board.

Now that we’ve established all of this, it’s time to actually draw it to the screen. I set up THREE.js by creating a scene and a camera:

var scene = new THREE.Scene();
var camera = new THREE.PerspectiveCamera( 75, window.innerWidth / window.innerHeight, 1, 1000 );
var renderer = new THREE.WebGLRenderer();

Having created these, I needed to set up a renderer. Finally, we just need to set up the position/rotation of the camera, and the renderer size and background colour, and attach it to our document, so that we’ll actually see it.

Camera:

camera.position.x = 4.5;
camera.position.y = 10;
camera.position.z = 20;
camera.rotation.x = -0.5;

Renderer:

renderer.setSize(window.innerWidth, window.innerHeight);
renderer.setClearColor( 0xeaeaff, 1 );
document.body.appendChild(renderer.domElement);

I also set up a light:

var light = new THREE.HemisphereLight(0xafafaf, 1);
scene.add(light);

Now all that was left to do was to add the meshes to the scene:

for(var x = 0; x < grid.length; x++) {
  for(var y = 0; y < grid[x].length; y++) {
    var mesh = grid[x][y].mesh;
    scene.add(mesh);
  }
}

And finally, animate it:

function animate() {
  controls.update();
  requestAnimationFrame(animate);
  renderer.render(scene, camera);
}

animate();

Which gives us a nice little result:

city-2

If you’re following along with the code in this article, you won’t be able to rotate/zoom on the result. To add this functionality, take a look at this orbit controls example.

You can find an interactive example and the full code over here, this should give you another example of the orbit controls in the context of the application.

This is a very naive and quick way of generating something that looks a bit like a city. It’s not very advanced at all. I’ll be expanding upon this topic in my book, being released next year using p5.js, where you’ll be able to find better ways of generating the roads and the buildings. Hopefully, you’ve been able to take something away from this article, at the very least, you’ve got a cool new toy to play with, somewhere to go and play with random cities.

There’s plenty of things that this could be expanded into, maybe you want to generate bigger cities, or potentially you might want to play with the density of the buildings, making more/larger buildings spawn in the middle, and less/smaller buildings spawn on the edges. Alternatively, you could make it so that the city grows, buildings get bigger, or the city gets wider over time, I’d be interested to see what people come up with 🙂

Advertisements
Standard

Maze Generation – Depth-First Search (Part 1)

 

Depth-First Search

Introduction

The maze generation algorithm that I’ll cover in this article is the depth-first search algorithm. This algorithm is described as one of the simplest ways to generate a maze with a computer on the wikipedia page for maze generation algorithms. It’s implemented with a stack, which facilitates ‘backtracking’, it’s much the same as the recursive backtracker algorithm, so I won’t go into details on that particular algorithm because I’ll cover a lot of it with this discussion.

The algorithm itself is very simple:

  1. Generate a grid of cells, each cell has four walls
  2. Pick a random cell
  3. Select a random neighbouring cell that has not been visited yet
  4. Remove the wall separating the two cells
  5. Push the neighbouring cell to the stack
  6. Make the neighbouring cell the current cell and mark it as visited
  7. If there are no unvisited neighbouring cells
    1. Pop a cell off the stack and mark it as the current cell
    2. If there are neighbouring unvisited cells
      1. Go back to step 3
    3. Go back to step 7
  8. Else go back to step 3

In the list of steps above, I specified that each cell will have four walls, assuming that all four walls are the same length, this implies that I’ll be using a square grid. It’s important to note that there are other types of grids, and I’ll be covering two other types of grids in this series of articles about the depth-first search algorithm, I’m going to be discussing hexagonal grids and 3D grids. Although you could construct mazes out of just about any type of geometry, for example, you could generate a Voronoi diagram and use the same algorithm to generate a maze.

Here’s an example gif of the maze being generated on a grid composed of squares using my implementation. The green dots are an indication of a cell being marked as visited, and you can see the walls disappear as the algorithm moves through the maze. The orange dots that you see are indications of the maze reaching a dead end and backtracking until it finds another branch to take, as in the subroutine that is executed in step 7 of the algorithm. The red dot indicates the starting cell:

depth-first-quad

This shows that the algorithm works well, and, as you can see, I’ve put it onto a square grid. I essentially followed the exact steps listed above, first, generating a grid made up of cells with four walls each. Here’s how I specified it to start in JavaScript.

function DepthFirstSquareCell() {
  this.walls = ['up', 'down', 'left', 'right'];
}

Now I needed to write a draw function. My logic was that I could use the walls array to check if it included a wall, and if it did, I’d draw the wall. So, using this logic, I began to write the basics of the function.

function DepthFirstSquareCell() {
  this.walls = ['up', 'down', 'left', 'right'];
  this.draw = function() {
    if(this.walls.includes('up')) {  //draw top wall }
    if(this.walls.includes('down')) { //draw bottom wall }
    if(this.walls.includes('left')) { //draw left wall }
    if(this.walls.includes('right')) {  //draw right wall }
  }
}

The next thing that I needed to know was how I was going to draw the wall, and more importantly where I was going to draw the wall. For this I needed to add a couple more variables to my cell, an x and a y coordinate. I figured that I could pass these in as parameters when it came to generating the grid.

function DepthFirstSquareCell(x, y) {
  this.x = x;
  this.y = y;
  ...
}

And now, for each conditional, I could use the p5 library to draw each wall.

I decided that each cell should be 20px in width and height, meaning that they were quite small, but not too small to see. I used the ‘line’ function provided by p5, which made it a very easy task to draw the lines, I just needed to do a bit of math around the coordinates.

If each cell was 20px by 20px, that would mean that the x and y coordinates would need to be multiplied by 20 to be put into the right place, then I’d need to stretch each edge 20 pixels in the right direction to make it look correct. Let’s look at this on a smaller scale.

Screen Shot 2017-08-17 at 13.28.14

The origin of the cell starts in the top-left corner at 0, 0. To draw the top line, we start at the origin and stretch 20 pixels along the x axis. So, assuming that x = 0 and y = 0, we can say that the top line can be draw from (x, y) to (x + 20, y) and the y coordinate stays the same. If we repeat this for each other line:

top: (x, y) -> (x + 20, y)
left: (x, y) -> (x, y + 20)
right: (x + 20, y) -> (x + 20, y + 20)
bottom: (x, y + 20) -> (x + 20, y + 20)

Drawing four lines using these values will give us a square with each edge measuring 20 pixels. I also mentioned earlier that the x and y coordinates should be multiplied by 20 to place the cells correctly, if we were to place all of the cells without multiplying the coordinates they would overlap. So, now that we’ve figured out our spacing, we can finish the implementation of our draw function.

if(this.walls.includes('up')) {  
  //draw top wall 
  line(x * 20, y * 20, (x * 20) + 20, y);
}
if(this.walls.includes('down')) { 
  //draw bottom wall 
  line(x * 20, (y * 20) + 20, (x * 20) + 20, (y * 20) + 20);
}
if(this.walls.includes('left')) { 
  //draw left wall 
  line(x * 20, y * 20, x * 20, (y * 20) + 20);
}
if(this.walls.includes('right')) {  
  //draw right wall 
  line((x * 20) + 20, y * 20, (x * 20) + 20, (y * 20) + 20);
}

The final thing that we need to know to implement the algorithm is whether the cell has been visited or not. I simply added a boolean value into the cell’s properties so that we could set it as needed and query it when searching for unvisited neighbours.

this.visited = false;

Now that we’ve got everything to do with our cell implemented, we need to look at what to do next. We’ll need a grid to operate on, so let’s look at that. I decided to implement a pretty basic data structure that held a two dimensional array, and a function to find unvisited neighbours for any given cell in that array.

function DepthFirstGrid(width, height) {
  this.data = [];
  for(var x = 0; x < width; x++) {
    data[x] = [];
    for(var y = 0; y < height; y++) {
      data[x][y] = new DepthFirstSquareCell(x, y);
    }
  }

  this.findUnvisitedNeighbours = function(cell) {
    return [
      cell.x > 0 ? this.data[cell.x - 1][cell.y] : continue,
      cell.y > 0 ? this.data[cell.x][cell.y - 1] : null,
      cell.x < this.data.length - 1 ? this.data[cell.x + 1][cell.y] : null,
      cell.y < this.data[0].length - 1 ? this.data[cell.x][cell.y + 1] : null
    ].filter(
      function(item) { 
        return item != null && !item.visited; 
      }
    );
  }
}

The first part of the code in there is very straightforward, we simply specify a two dimensional array and then populate it with our cells. The findUnvisitedNeighbours function may look scary, but let’s just break it down, because I’ve used a lot of syntactic sugar in there to make the code a bit more concise.

Essentially, we need to look at what we want to put into the function and what we want to get out. The input is an arbitrary cell, and the output that we want is an array of the cells that are adjacent to it with the condition that they are not visited. We need to take into account a few things here.

First, we need to check if a cell is on an edge, if it is, we can’t return neighbours for that side of the cell. Let’s say, for example, we’re looking for neighbours of the top left cell. The value would be 0, and the value would be 0. If we tried to get the neighbour to the left we would have to access index -1 of the grid, however, no such index exists, and the code would throw up an error telling us that we can’t get any data from there because firstly, no such index exists, and secondly, even if it did, there wouldn’t be any data to return. The same would happen on the coordinate. So, we need to put conditionals in to make sure that we don’t attempt to access any indices of the array that don’t exist. Now that we know what our checks will be, we can plug that into the array that we return with the neighbours, and we simply say, if the cell is not on an edge, give us the neighbour, but if it is on an edge, just put a null value into it’s place so we know that there is no neighbour there.

Now we have an array with neighbours in it, and we simply want to filter the array down so that we can get rid of the null values left in the array, and in the same line, also specify a conditional that removes any neighbours that have been visited from the array. The final result will be an array that has a list of neighbours for a given cell that have not been visited.

I’ve written some more simplified and self-explanatory code below that does the same thing.

this.findUnvisitedNeighbours(cell) {
  var neighbours = [];
  //is the cell on the left-hand edge of the grid?
  if(cell.x > 0) {
    neighbours.push(this.data[cell.x - 1][cell.y]);
  }
  if(cell.y > 0) {
    neighbours.push(this.data[cell.x][cell.y - 1]);
  }
  if(cell.x < this.data.length - 1) {
    neighbours.push(this.data[cell.x + 1][cell.y]);
  }
  if(cell.y < this.data[0].length - 1) {
    neighbours.push(this.data[cell.x][cell.y + 1]);
  }
  for(var x = 0; x < neighbours.length; x++) {
    var unvisitedNeighbours = [];
    if(!neighbours[x].visited) {
      unvisitedNeighbours.push(neighbours[x]);
    }
    return unvisitedNeighbours;
  }
}

Both sets of code do virtually the same thing (although the second one doesn’t put null values into the array, which means that you might see a slight optimisation on the second method in terms of speed, although it’d be negligible in small examples like the one I’m showing you, although with scale it might shave a bit of time off).

Now that I’ve implemented the code to find unvisited neighbours, I’ve only got one thing left to do that isn’t absolutely necessary before diving into the meat of the algorithm, but I’d like to do just to make things a bit neater, and that’s implementing a function to remove a wall from a cell. It’s a one-liner but it saves a lot of typing later.

this.removeWall = function(wall) {
  this.walls.splice(this.walls.indexOf(wall), 1);
}

Now we can really focus on using all of these data structures and functions that we’ve built out to implement the algorithm.

Here’s the final commented version of the code:

var grid;
var currentCell;
//this is used for backtracking
var stack;

//helper to get a random value between limits
function randRange(min, max) {
  return Math.floor(Math.random() * (max - min)) + min;
}

//p5 setup function, get things ready
function setup() {
  createCanvas(400, 400);
  grid = new DepthFirstGrid(20, 20);
  
  //get random starting cell
  var startX = randRange(0, grid.data.length - 1);
  var startY = randRange(0, grid.data.length - 1);
  currentCell = grid.data[startX][startY];
  currentCell.visited = true;
}

function draw() {
  background(85);
  //Draw the grid
  for(var x = 0; x < grid.data.length; x++) {
    for(var y = 0; y < grid.data[x].length; y++) {
      grid.data[x][y].draw();
    }
  }
  
  //check that we've got a cell
  //if we haven't the maze is complete
  if(currentCell) {
    var unvisitedNeighbours = grid.findUnvisitedNeighbours(currentCell);
    //if there are any unvisited neighbours
    if(unvisitedNeighbours.length > 0) {
      var neighbourCell = unvisitedNeighbours[randRange(0, unvisitedNeighbours.length)]; 
      //if the neighbour cell is to the left of the current cell
      if(currentCell.x > neighbourCell.x) {
        currentCell.removeWall('left');
        neighbourCell.removeWall('right');
      }
      //if the neighbour cell is to the right of the current cell
      if(currentCell.x < neighbourCell.x) {
        currentCell.removeWall('right');
        neighbourCell.removeWall('left');
      }
      //if the neighbour cell is above the current cell
      if(currentCell.y > neighbourCell.y) {
        currentCell.removeWall('up');
        neighbourCell.removeWall('down');
      }
      //if the neighbour cell is below the current cell
      if(currentCell.y < neighbourCell.y) {
         currentCell.removeWall('down');
         neighbourCell.removeWall('up')
      }
      //push the neighbourCell to the stack
      stack.push(neighbourCell)
      neighbourCell = currentCell;
      currentCell.visited = true;
    //otherwise, backtrack
    } else {
      /* grab the top cell on the stack ready for the next loop
         if the top cell on the stack doesn't have any other neighbours
         it'll just call this line again on the next loop */
      currentCell = stack.pop();
    }
  } else {
    //erase all the data and start again
    //if you want to keep your maze you can omit this part of the conditional
    setup();
  }
}

That’s pretty much it for square grids, in the next part of the article I’ll be discussing the implementation on a hexagonal grid and the things that I had to do differently, and in part 3 where I’ll be discussing my 3D implementation. Here’s another gif of a much bigger example of the maze being generated.

big-gen

I have also got a page where you can check out the working examples (and full code) for each algorithm as and when I complete their implementations.

Standard

Paper Prototyping

Background

I am building a stealth puzzler based on Sokoban. The underlying theme being that you play as a robber, pulling off heists in banks, museums, offices, trains, you name a famous heist, there’s going to be a flavour of it in the game, granted, it won’t be historically accurate, but it’ll be fun and challenging, at least that’s what I’m hoping for.

This is my first real crack at game design, I’ve been reading up a lot and watching a lot of talks from industry experts (GDC Vaults are pretty good for this, among other things), but I think I’m starting to pick things up a little and I’m applying my new knowledge with this game.

The importance of paper prototyping is not lost on me, at least now it isn’t. When it came to thinking about designing my levels, I had heard a lot about people using paper prototyping in their games, and I decided to try it out. I had done paper prototyping before, just not for a game. I’ve used UX concepts before, but only to design GUIs, websites, etc., never for a game.

There’s a few things that I knew starting out. My initial levels should provide some amount of problem solving, at least, the problems should be only slightly obvious, these levels are more about introducing the mechanics of the game to the player. I had learned this watching GDC talks (I don’t remember which one specifically taught me this, but I do remember it making a lot of sense, looking at games like Portal, where the mechanics are introduced slowly over a few quick levels, and then the puzzles kick in.)

The other thing I knew was which mechanics I wanted to include. I knew that I wanted the game to be a Sokoban clone with a twist. I wanted to include the stealth element, since that was always a game mechanic that I had enjoyed in other games. I love puzzle games as well, and I vividly remember the Sokoban-like challenges where you had to roll boulders around in Pokemon Sapphire, one of my favourite games of all time, I was always slightly frustrated by these challenges, but the feeling of triumph upon completing them was unmatched by anything (except maybe beating the Elite Four for the first time).

Based on this I picked out a few ideas:

  • Sokoban elements
  • Sweeping cameras
  • Patrolling security guards

I also wanted to include a mini-game of sorts, the first thing that came to my mind was a lock-picking mini game. In true hacker fashion, I’ve played a little bit with lock picking (as a hobby only, not to actually pick locks with malicious intent). In the games that I have seen with this mechanic, I’m looking at you, specifically, TES, the lock picking mechanic just isn’t what I thought it was going to be. In my game I wanted to give the player a side on view of all the pins in the lock and let them pull contortions with their hands to complete the lock picking process, a bit more like the real thing, I guess.

The lock picking mechanic isn’t so pertinent, although I felt I should include it since I added a mini-game trigger into my paper prototypes. Anyway, let’s get to the actual process, my final result, and the things I learned.

The Process

So for the first, introductory level, I wanted to teach the player a few things about the game:

  1. How to move
  2. How to push blocks
  3. How to avoid cameras
  4. How to use blocks to block the camera line of sight and ‘hide’ from the camera
  5. How to move the block to the target

I wanted to illustrate this in the most simple way possible, so I decided to go with the most simple puzzle I could think of. The block should be in the middle of a 3×3 space, giving the player enough room to manoeuvre around it and push it out of the 3×3 space, through a tunnel, and onto the target square, which would then ‘unlock’ the door for them to proceed into the next level.

The next puzzle was fairly similar, a block in a 3×3 space, but this time it was guarded by a security guard and a camera. The player would have to avoid the security guard and the camera, (using the block to stop the camera’s vision from seeing the player).

This taught the player about security guards, whilst having them practice the skills they learned in the previous level.

Finally, the last level would ramp up the difficulty a little, with two security guards and a camera. The player would need to sneak into a room, and play the lockpicking mini game to open a safe and get the ‘golden block’.

This tests the player’s skills and adds in the mini-game, making sure that the player knows how to beat that mechanic.

Mechanics Evolve, Issues Solved

Whilst running through my level designs I looked at a few sticking points. Firstly, I had drawn the walls too tightly on the first level. This would be an issue, so I had to do something to fix this. Essentially, if the player pushed the block onto the target block it would mean that they would not be able to proceed.

I had a couple of ideas, I could have easily opened the corridor up a bit, but that would mean drawing the level out again, I decided that there was a better way. We’d make a hole in the floor that the player couldn’t walk over, this way they only have one way to go – towards the block. It’s a nice subtle way of directing the player. They would then have to push the block into the hole, and that would then allow them to traverse the rest of the level.

The next decision to make was what to do with the door that the block supposedly unlocked. I decided to throw in another lock picking mini game here. This meant that the player was introduced to the idea of it early on, and it meant that they would be able to play it in ‘easy mode’ first, and then at the end of the level, have a chance to play it in ‘hard’ mode.

With this, I had not only solved the issue of the level being too tight and pretty badly designed, I had also found some cool new mechanics and ended up with a nicer level.

The next issue that I found was that in the second level there was no way for the player to move the block into the right place because the camera would always see the player. I decided that the best thing to do would be to change the level so that the target wouldn’t unlock a door, instead, the block would need to be pushed right in front of the camera, completely blocking it’s line of sight, rendering the camera useless.

The final level was very simple to implement, but again, I had drawn the level too tight. I realised that the best thing to do would be to inset the ‘safe’ into the wall, and add a block into the middle of the level. I’d give the security guards a longer range of vision, which would require the player to use the block to protect themselves from line of sight of the guards so that they could pick the lock. The player could then use the block to block off the camera guarding the exit door so that they could make a safe escape.

Whilst thinking about all of this I realised that I could be implementing something else here. The player could steal a valuable ‘dossier’ which would contain blueprints of a museum and correspondence between the curator of the museum and two high powered people about some artefacts that would be transferred to the museum the next day. This would nicely segue into the next level, where the player would be able to make a choice on which artefact they should steal, allowing for story branching.

Summary

In my opinion, paper prototyping has really helped me to figure out the kinks in my game before I’ve implemented anything, and it’s been fun to find new opportunities to make the game look good and fun to play. It’s also nice to see how my levels are going to fit together visually before I actually get around to implementing the game.

My next steps are to implement the levels. I’ll be using Puzzlescript to rapidly prototype the levels, this is a really awesome tool that I’ve learned about from watching a GDC talk by the guy who made Sokobond and A Good Snowman Is Hard To Build, and there’s so much that can be done with it in terms of prototyping levels.

Results

Here’s the final design – after I made all my fixes:

Screen Shot 2017-06-06 at 10.46.15.png

This is a really important document to me, because it illustrates clearly (at least to me, maybe not to anyone else), how my levels are going to play out for the first mission. I’ve got a clear idea of where I’m going with each level and I know exactly where everything will go.

Once my mechanics have actually been implemented, it’ll just be a matter of placing each item in the right place and I’ll have a nicely working demo that I can show off. I’ll be posting later about the demo, and the challenges I faced during implementation.

Standard

Procedurally Generating Trees

When I first decided that I was going to procedurally generate some trees I had no idea what I was about to step into. I had a rough idea of how I was going to do things, but little did I know, there were some pre-existing algorithms out there. I had a very rough idea of where I wanted to go with my algorithm, here’s what I decided on:

  1. Draw a line of arbitrary length to represent a trunk
  2. Draw a line parallel, if the line is to the left hand side of the trunk, split it off to the left for a random distance before making it grow up again
  3. Continue this until the tree has reached a certain number of lines in width
  4. Draw leaves randomly from the trunk to the outermost branches

Screen Shot 2017-05-17 at 13.37.23

This wasn’t working, whilst the premise was good I was having a tough time actually implementing it, so I took to the internet in search of a better approach. I found out about something called L-systems, these were built to model plants, if you haven’t heard of L-systems before you should do a quick google search on them, they’ve got a pretty interesting history, but I won’t go into that in this post.

L-systems are pretty simple. You start with an ‘axiom’, which we can view as the ‘seed’ of our tree. The axiom is then fed into a set of rules, to produce a product. You can then feed the product back into this set of rules a number of times, and this will produce a value that can be used to determine how to model your tree.

So, if, for example we had the following values:

var axiom = 'a';
rules = {
    a: 'bc',
    b: 'ac',
    c: 'ad',
    d: 'ea',
    e: 'a'
};

And we ran our axiom through the rules once, we would have a product:

1: bc

Continuing to run the product through our rules for another five iterations:

2: acad
3: bcadbcea
4: acadbceaacadabc
5: bcadbceaacadabcbcadbceabcacad
6: acadbceaacadabcbcadbceabcacadacadbceaacadabcacadbcadbcea
7: bcadbceaacadabcbcadbceabcacadacadbceaacadabcacadbcadbceabcadbceaacadabcbcadbceabcacadbcadbceaacadbceaacadabc

As you can see, for each character in the string, the rules are applied (replacing the character with those specified in the rules) to produce another product, which grows in length with each iteration.

You can see a working JSFiddle here if you want to play with the rules yourself and mess with the axiom.

OK, so now that we’ve got that out the way we have something to work from. Now, we can decide what each of these characters mean in a string. We’ll take a look at how we can translate our string into a drawing. The easiest way of turning an L-system into a drawing is to use what’s called a ‘turtle’ engine.

A turtle engine will essentially act like a robot that carries out directional commands like move forward, turn left, turn right, etc.

For our purposes, we’ll use the following rules:

a: Draw Forward,

: Rotate Right,

[: Save our current location

]: Return to the saved location

Now we need to start drawing. We’ll start much the same as we did in the first instance, by drawing a ‘stump’, we can use the axiom for this.

We’ll start off by specifying a starting location and a direction, and then follow our axiom’s command.

Let’s start again in the middle of the screen at the bottom, we’ll say that we should always draw a number of pixels ahead, for this example, I’m using 80 pixels as my length; here’s where we’re at:

Screen Shot 2017-05-17 at 12.05.01

So now we have our trunk, we can start to build out the rest of the tree, but to do this, we have to come up with a good set of rules for our L-System.

For our purposes, I’ve just decided that I’m going to specify one rule:

a -> a[>a][<a]

So whenever we encounter an ‘a’ in our string, we’ll replace it with the string shown above.

This produces a tree that looks like this:

Screen Shot 2017-05-17 at 12.13.49

Now I’ve managed to gloss over the code here, so we’ll take a second to talk about that.

I cleaned up my code for the L-System a bit for use in this project.

var axiom = 'a';
var iterations = 5;

var rules = {
 a: 'a[>a][<a]'
};

function evaluate(product) {
  var production = '';
  for(var char of product) {
    var p = rules[char];
    if(p != undefined) {
      production += p;
    } else {
      production += char;
    }
  }
  return production;
}

The code is fairly self-explanatory and similar to the code in the fiddle linked above, the only major difference is that because we don’t have definitions of rules for every character in the alphabet, we have to check whether our rule lookup returns anything or not. If it does, we’ll add that on to the new product, if not, we just add the current character on.

Now to talk about the drawing code, as discussed before, I implemented a turtle system, using p5, this was quite simple.

for(var x = 0; x < iterations; x++) {
  product = evaluate(product);
  len *= 0.65;
  for(var y = 0; y < product.length; y++) {
    if(product[y] == 'a') {
      line(0, 0, 0, -len);
      translate(0, -len);
    }
    if(product[y] == '<') {       rotate(-Math.PI/6);     }     if(product[y] == '>') {
      rotate(Math.PI/6);
    }
    if(product[y] == '[') {
      push();
    }
    if(product[y] == ']') {
      pop();
    }
  }
}

Again, this code is fairly self-explanatory, it basically follows the rules that we set out.

It was quite fun to play with the values, for example, if I changed the amount that I rotated the cursor to

Math.PI / 3

I would end up with some cool looking hexagonal trees like this:

Screen Shot 2017-05-17 at 12.15.15

Changing the ‘len’ adjustment gave me some cool results as well:Screen Shot 2017-05-17 at 12.36.33

Using random values for this would probably give you some really cool results. You could also try to draw multiple trees instead of just one.

Here’s a working so you can have a play with it, some of the lines are commented where changing the values gives more interesting results.

Now whilst this looks good, and I could definitely generate a bunch of trees like this and put them side by side and create my own little forest, I still think it’s just going to look a bit too uniform. It doesn’t quite represent nature. This could be fixed in a number of ways, like changing my rules, or playing with the values, but there’s a better way.

Whilst reading up on algorithms for generating trees, I stumbled across something called a space colonisation algorithm, and apparently they’re really good at generating trees. In fact, if you search ‘Space Colonisation Algorithm’, there’ll be a lot of results that link to creating trees.

A space colonisation algorithm is based on a simple premise. We essentially take an area and plot random points within that area. We then start building out a tree trunk from it’s source towards the area that is filled with random points. When the trunk is tall enough, we can finally get to the meat of the algorithm. We know the trunk is tall enough because it is within a certain distance of one of our points, which we can consider ‘leaves’.

The algorithm then switches it’s focus and begins to look at our ‘leaves’. We then find the nearest branch for each leaf that is within range of the branch, and begin to ‘pull’ that branch towards this leaf. When the branch gets too close to the leaf, the leaf disappears. This is continued until no more leaves are left and we’ll have a nice winding natural looking tree.

We’ll explore the implementation details of that algorithm now.

So, to start, I want to generate a set of random points in a range.

Screen Shot 2017-05-17 at 14.12.55

In a 640 x 480 window, we’ve generated 100 points randomly in a range.

The next step is to start adding branches. This bit was really difficult for me to wrap my head around, but I got there eventually with the help of this video. Essentially, the process is to add a branch node, and then for each of our leaves we need to check if the newest branch node is within range of the leaf. If it isn’t we add another one, but if it is, we can stop there and move on to the next part of the algorithm.

Screen Shot 2017-05-17 at 15.46.44

We now have a tree trunk, and we can almost see a very rough tree shape coming from it. There’s plenty of ways to render the ‘branches’ and the ‘leaves’, although we’ll just stick to a yellow line for the branches and green dots for the leaves.

The next step is to start pulling the branches in the direction of the leaves. So, for each leaf, we can find the closest branch that’s in range.

If a branch is in range, then let’s check if it’s closest. If it is the closest, we need to add a pulling force onto the branch in the direction of that leaf. We continue to do this until all of our leaves have been ‘found’ by branches.

Here’s the final product:

Screen Shot 2017-05-17 at 17.25.06

There’s a lot more that can be done with this but I’m on the right track now. Here’s a working codepen to play with:

Interestingly enough, these algorithms aren’t only useful for generating plants, they’re also very useful for generating road networks, or trade networks, which means that you could, for example, specify a bunch of points on a map that would represent cities and link them up using a space colonisation implementation or an L-system implementation (or a hybrid if you’re brave enough).

 

Standard

Procedurally Generating Islands

My first shot at generating an island didn’t go well. Here’s what it looked like:

Screen Shot 2017-05-03 at 11.27.44

I was happy with it, nonetheless, but over the next 24 hours I would go on to learn a whole host of new techniques that would turn my poor excuse for an island into something that actually looked like an island. This post will follow my journey from nothing to something.

My first island used a very simple technique:

  1. Fill a 2D array with a radial gradient
  2. Apply perlin noise to the gradient
  3. Paint the square based on the value in the cell of the array

This is how we got here.

To fill the 2D array I had kind of figured out my own little algorithm but I was really going about it the wrong way, we’ll see the right way later, but my mistakes turned into lessons and we’ll have to look at the mistake first to learn the lesson later.

My method was to draw concentric circles around the center of the grid. So to start I needed to find out how one finds a point on a circle, it turns out it’s quite simple:

x = centerX + radius * Math.cos(angle);
y = centerY + radius * Math.sin(angle);

Where centerX and Y are the center coordinates of the circle.

We then loop this to fill in each point of the circle. So, logically, with 360 degrees in a circle, we want to loop 360 times, with the angle starting at 0 and increasing by 1 each time.

while(angle < 360) {
    x = centerX + radius * Math.cos(angle);
    y = centerY + radius * Math.sin(angle);
    angle++;
}

This will draw 360 points that will join up into a circle. The next step is to figure out how to draw a slightly smaller circle. Simple answer: reduce the radius.

radius = 200;
maxRadius = 200;
while(radius > 0) {
    while(angle < 360) {
        x = centerX + radius * Math.cos(angle);
        y = centerY + radius * Math.sin(angle);
        array[x][y] = maxRadius - radius;
        angle++;
    }
    angle = 0;
    radius--;
}

This will now draw circles, slowly decreasing inside, towards the center of the array.

The only issue with this algorithm, is that it leaves gaps. When I use the points that I’ve calculated on I get a gradient that looks like this:

Screen Shot 2017-05-03 at 13.10.17

We can see the gaps in here, and when we draw our island it’s going to end up leaving gaps.

So when I did draw the island using these values, I was left with lots of little gaps, I then decided that to fix these gaps I would just make the squares that I drew bigger and they’d merge together, but all I got was the original image I tried a few other things like playing with the noise algorithm, thinking maybe that had something to do with it and reducing the increment of my angle based on how large the outer circle was, but didn’t have much luck with either. So, I took to the internet and I found a very helpful person, and they taught me the following things.

The first step was to figure out how to generate a gradient without gaps. I was informed that by going pixel by pixel over the array and calculating the distance to the middle, I would get a nice smooth radial gradient without gaps. I had already tried this approach before and I had only received a weird, square shape, that’s not what I wanted, but I then read that I had been calculating the manhattan distance to the center with this algorithm:

xDistance = Math.abs(centerX - x);
yDistance = Math.abs(centerY - y);
distance = xDistance + yDistance;

What I actually needed was the euclidean distance to the center. I was having flashbacks to high school, I had to use Pythagoras, for an actual real life application. I couldn’t believe it.

xDistance = Math.pow(Math.abs(centerX - x), 2);
yDistance = Math.pow(Math.abs(centerY - y), 2);
distance = Math.sqrt(xDistance + yDistance);

This produced a beautifully smooth radial gradient, I was so happy. I had actually spent a good few hours trying to implement a radial gradient and the maths just broke my head for some reason. I just needed to sit down and break the problem down, explain what I was doing to someone and then figure out a track from there.

Screen Shot 2017-05-03 at 14.50.47

My nice smooth gradient felt like a huge win, even if it looks like nothing, I was so happy with it.

Now it was time to go back to what we were doing before, we wanted to apply the noise and then draw an island.

First I applied the noise and got this:

Screen Shot 2017-05-03 at 15.12.29

Then I culled the edges, basically only drawing cells with values over a certain threshold:

Screen Shot 2017-05-03 at 15.13.15

And then finally I added a bit of colour, using the values in the array to decide which colour should be drawn

Screen Shot 2017-05-03 at 15.18.33

I finally had something that almost resembled an island. It wasn’t quite there but we were getting somewhere finally.

The next few hours were spent playing with my noise algorithm, figuring out how the hell to make it less sharp, and make my island actually look like one contiguous landmass.Screen Shot 2017-05-03 at 15.46.37

All I could do was make the edges more or less noisy. I still just had a flat set of circles, it didn’t look much like an island at all. Back to playing with noise.

Screen Shot 2017-05-03 at 17.03.18

I finally stumbled on something, this was all a bit of a blur, I was using a perlin noise library and I eventually figured out that if I combined two levels of noise I could make something like this.

It was at this point that someone who had seen my code pointed out that it looked like I was getting my noise pixels incorrectly. Since the noise was in a 1D array and my map was a 2D array, I had to translate that, and I was doing it wrong.

terrain[x][y] -= noise[x * 800 + y]

I was referencing the noise horizontally rather than vertically.

I needed to access it like this:

terrain[x][y] -= noise[y * 600 + x]

It was a simple fix, although I didn’t actually implement it as I was far more concerned with something else. Even if I did manage to place it, my island was going to look like a circle still. I needed to distort it somehow.

I continued playing with different layers of noise, and eventually I got this:

lLdabg2

That was cool, but I still had a few issues with it:

  1. It was still a circle
  2. It still had weird horizontal lines
  3. Someone pointed out that it looked really flat

So, since it looked flat I needed to do something about it. The very nice person on the internet who was guiding me this entire time explained that I could implement some shading, so that was the next step.

At this point, I was using a library called PIXI to do my drawing, it took hex values for colour, which was all very well and good, until shading came into the equation. I spent a good few hours struggling with shading, trying to convert between string, ints and hex values and calculate differences between them. It was horrendous, but I finally got somewhere.

F2So25q

I managed to implement a basic shading algorithm, if the cell closer to the light source is ‘higher’ up, then the current cell needed to be shaded, and would simply be slightly darker than the normal shade for it’s height.

I had also changed my noise algorithm further at this point, so we had a different shape of island.

I then went on to multiply the shade, so the lower it was, the darker it got.

3ov82gu.png

This looked cool, but the lighting on the bright side of the hills looked really flat, so I went a step further and attempted to shade both sides of the hills.

nEiwg0N.png

This really didn’t look that good at all, it almost looked like plastic. I needed to take a different approach, and dealing with hex values wasn’t helping. It had been suggested to me earlier that I ditch the library and just draw with raw JS, and that’s exactly what I did.

The next few hours was turmoil, why wouldn’t it just work, I didn’t understand what was going on, my code was broken, it just wouldn’t draw and I didn’t even get the slightest hint at an error from my dev console.

for(var x = 0; x < 800; x++) {
    for(var y = 0; y < 600; y++) {
        var colour = getColour(terrain[x][y]);
        imageData[(y * 800 + x) * 4] = colour.r;
        imageData[(y * 800 + x) * 4 + 1] = colour.g;
        imageData[(y * 800 + x) * 4 + 2] = colour.b;
        imageData[(y * 800 + x) * 4 + 3] = colour.a;
    }
}
context.putImageData(imageData, 0, 0);

I had virtually copied the code right from the Mozilla docs, but my canvas was not drawing, and I didn’t have any errors. I thought I had lost my island. I was so sad, then, suddenly, I noticed something.

I had a line printing into my JS console in Chrome. I had just told my drawing script to print my imageData object. It hit me like a speeding truck:

Screen Shot 2017-05-04 at 14.22.36

ImageData object, with data as one of it’s members. I needed to access the damn data array, not the object, the simplest change to my code and hours of frustration were suddenly solved:

for(var x = 0; x < 800; x++) {
    for(var y = 0; y < 600; y++) {
        var colour = getColour(terrain[x][y]);
        imageData.data[(y * 800 + x) * 4] = colour.r;
        imageData.data[(y * 800 + x) * 4 + 1] = colour.g;
        imageData.data[(y * 800 + x) * 4 + 2] = colour.b;
        imageData.data[(y * 800 + x) * 4 + 3] = colour.a;
    }
}
context.putImageData(imageData, 0, 0);

I finally had values that could be measured on a scale of 0-255 for my colours, and it drew a whole lot faster than before. I was waiting up to 30 seconds for PIXI to draw my islands before, now I was waiting 10 at most.

Time to add shading:

for(var x = 0; x < 800; x++) {
    for(var y = 0; y < 600; y++) {
            hillshade = terrain[x][y] - terrain[x - 1][y];
            hillshade = 1 + hillshade * 10000;
        }
        var colour = getColour(terrain[x][y]);
        imageData.data[(y * 800 + x) * 4] = colour.r + hillshade;
        imageData.data[(y * 800 + x) * 4 + 1] = colour.g + hillshade;
        imageData.data[(y * 800 + x) * 4 + 2] = colour.b + hillshade;
        imageData.data[(y * 800 + x) * 4 + 3] = colour.a;
    }
}
context.putImageData(imageData, 0, 0);

My other issue was that it still had those weird horizontal lines on it, they were nasty, I needed to fix it. Time to re-think. I ended up finding a new library using a different noise algorithm. I moved over to something called OpenSimplex noise that I had read was quite good and that I should be using over Perlin, so I moved over to that.

Finally, I managed to draw something, with shading, that didn’t have horizontal lines and actually looked like it might be an island.

Screen Shot 2017-05-04 at 12.51.43.png

The only thing left annoying me was that the damn thing still looked like a circle.

After fiddling around for a bit I finally figured out that I could change my initial radial gradient into a differently shaped gradient by changing the distance calculations. Instead of figuring out the squared distance of each point I calculated the distance of each point by 2, minus a random number in the range 0 and 2.

That gave me this:

Screen Shot 2017-05-04 at 13.19.23

It was an actual island looking thing, and it randomly generated, and it looked awesome. We have reached the end of the journey, I’m going to take this knowledge forward and build out things on top of these islands, and I’m really looking forward to learning more about procedural generation.

This has been a wonderful adventure, and the difference between what I had 24 hours ago and what I have now is astounding.

Screen Shot 2017-05-03 at 11.27.44Screen Shot 2017-05-04 at 13.19.23

Standard