Procedural Planet Generation

Recently I have developed a technique to generate random planets, with the plan to use the generated planets in a game I am developing in Unity. The generated planets look like this:

Random Planets

These planets are created by first generating a random  spherical mesh. This is done by choosing a start position, then creating a set number of vertices around this start point at any given radius. To randomize the position of each vertex in a way to avoid overlap with neighboring vertices, the vertices are moved a random amount on the line that represents its direction from the start point. So essentially, they are either moved randomly closer or further from the start point. Once the vertices are in place they can be used to create a mesh. However I found only having one set of vertices from the center point to the radius of the planet created problems later when I was trying to use a shader to fade towards the edge. To create a mesh that I could work with more easily in a shader I repeated the first process many times, creating sub layers within the mesh that connected to each other.

Generated Mesh

UV’s for the mesh could be calculated fairly simply by comparing the vertices position to the start position. To generate the texture used on the planets I came up with a technique that makes use of Cellular Automata. The idea is to generate multiple layers of the texture, that only consisted of two colors on each layer. I devised two different Cellular Automatons rule sets that would be used. The first would try and create small isolated sections of the layer color on the texture, then switch to the second rule set that would try and grow these isolated blobs outwards. To create more diverse layers the rules were randomized in several ways, for example the number of cycles before switching rule sets is randomized, as well as the actual rules that affect how cells die and live. An example of what an individual layer looks like can be seen in the picture below:

Texture Layers

To combine the layers into one texture, each layer is added incrementally, averaging the color of each pixel in its texture with the value of the corresponding pixel already on the combined texture. The result of combining 4 layers (which is the amount used in the picture at the top of this blog) looks like the following:

Combined Texture

To create the fade effect a simple shader is used to blend the texture with the polygons color alpha, which gives the final result.

Final Result

I feel the results so far are pretty good but there is still a bit of work I would like to try and do, for example experimenting with ways to make the edge of the asteroid more apparent and possibly finding a better technique for the fade to edge that is already in place.

Procedural Dungeon Generation

Source code available here

I recently used three different techniques to generate dungeon structures. This was done as part of my final year project. All techniques were implemented with Unity and used a common procedure to produce a 3D representation of the dungeons. The full report I wrote to go with these generators can be found here

Cellular Automaton Generation

 Arguably not the best technique to use for dungeon generation, and much better suited for cavern generation, the results did give interesting shaped domains.

Binary Space Partitioning Generation

A much more common technique used to generate dungeons. Produces very uniformed shaped dungeons.

Delaunay Triangulation Generation

Based off the generation technique created by Phi Dinh for his game Tiny Keep. This techniques creates much less uniformed dungeons than the BSP technique and gives very appealing results. My implementation uses the incremental algorithm for constructing a Delaunay triangulation combined with the edge flipping technique.

Source code available here

Unity Dungeon Generator

Github Repository

This week I decided to take a little break from FlyBy and work on something  fun, so I decided to try and make a BSP Dungeon Generator in Unity.

To begin with I needed to create the Binary Tree that would store the space inside it. I decided to represent the space just using Unity’s primitive cubes. Splitting a BSP Node would take the cube it stored, break it in half randomly, and create two new cubes that would be stored as its left and right children nodes. After 5 splits of the tree it resulted in this:

The level split up into sections

Each color square is a leaf of the BSP Tree

With the level now partitioned it was time to start adding rooms to each section. I decided I would create a room prefab, and make several variations of it for each possible number of exits. Then when it came time to generate the connections between rooms just change the room to the correct prefab. So I created a prefab that looked like this:

A room with 4 exits

A room with 4 exits

Then it was a case of just randomly putting these into leaf nodes on the tree. Randomizing its position and size depending on the size of space that node was holding:

Stretched room prefabs

Stretched room prefabs

And doing this cause the prefabs to get horribly stretched, making the exits a non uniform size, and look like a complete mess. At this points I re-thought my plan and decided to store everything as tiles in a grid. this would mean that each room would be made out of lots of floor and wall tiles. Although significantly more expensive, it is a much more flexible approach. After making these changes I ended up with this:

Rooms now made out of tiles

Rooms now made out of tiles

Ah, that looks much better. Now to start connecting them. I decided to go with the most simple approach possible. To begin with I connect sibling rooms, these being rooms that share the same parent node in the BSP tree. To actually connect the rooms I created a ‘Digger’ class that would move from a start position towards a target position changing the tiles it touches into floor tiles, and surrounding the tiles it creates with walls, if those tiles are empty. The Diggers movement was a very naive ‘while My_x is less than Target_X, My_x ++’ sort of affair. Ideally I would like to go back and make the ‘Digger’ use a form of path-finding to find the shortest path avoiding other rooms and such, but that is a job for another day. The results of connecting siblings looks like this:

sc4

Siblings connected to each other

Not too bad, but we do get the unideal double connecting of rooms. I fix this by checking if nodes are already connected before connecting them. At this point it is just a matter of continuing traversing up the tree connecting the rooms with parents higher up the tree, until we are back at the root of the tree. At this point the dungeon should be fully connected! Lets have a look:

A fully connected dungeon!

A fully connected dungeon!

Top down view

Top down view

That doesn’t look too bad. At this point I decided to do a few iterations of a cellular automaton to ‘clean up’ the dungeon a little. This mainly removes corner pieces to make the dungeon feel more open and remove wall pieces that are sticking out awkwardly by themselves. I am pretty pleased with these results but there are plenty of improvements that could be made. If you are interested in the code for this project check out the Github Repository.

Github Repository

LibGDX Mobile Game

So for the last few months I have been working on a small mobile game. I had to stop using Marmalade because I was unable to get a student licence and my trial expired. Because of this I have decided to moved back to LibGDX which actually supports iOS now. The process of getting a LibGDX game onto iOS seems a little daunting but I will give it a try anyways when the game is more complete. Anyways, here are some screen shots of what I’m working on:

Inside a cave

Inside a cave

Some spinning obstacles

Some spinning obstacles

A mine field

A mine field

The graphics are being created by Liam Bower. The game is basically a helicopter style game with extra features such as different areas, power ups and a shop. We hope to have it finished pretty soon, although it has already taken much longer than originally anticipated.

One interesting problem I had to work on recently was generating caves with smooth walls like in the first and second screen shot. Before smoothing the wall generation, the walls were generated in square blocks, and actually still are. What I do is convert the top and bottom blocks on the walls into two triangles.One triangle using the center point on the top edge of the block, the center point on the top edge of the next block, and its x and y position to draw a triangle. Then the other triangle just draws to fill in the rest of the block. This picture should help illustrate whats happening:

Debug drawing of triangles

Debug drawing of triangles

The results of this method are good, however it is probably more process intensive than it needs to be, and finding ways to optimize it will be something I will need to look into. One solution could be generating ‘height map’ like structures, and then using the triangles to draw from the edge of the screen to the tip point of the map. This will remove the drawing of all the boxes under the triangles as the triangles would create the entire terrain. Generating the terrain in wider sections will lower the number of triangles being drawn at once too.

The progress of the game is going good, with almost all the main features already programmed into the game, but there is still quite a lot of work to do before we can call it finished and release it…

Procedural Generation

This week I’ve done some procedural generation using cellular automata. This was for generating coral reef inside levels. The coral reef acts as another obstacle that the player must avoid touching. Here is a look at some of the outputs of the generation:

Both the foreground and background coral are procedurally generated

The background coral uses a different tile set and tile size

The generation can create interesting loops such at this some times

To begin I had to write a grid structure as I found out LibGDX didn’t have one included. After a little research on different ways to implement a grid, I choose to represent mine as an Array of Arrays, which although might not be that efficient, is pretty easy to implement and understand, so heres the grid class I came up with:

package com.me.mygdxgame;

import com.badlogic.gdx.utils.Array;

public class Grid {

private Array<Array<Boolean>> grid = new Array<Array<Boolean>>();
private int rows;
private int collums;

public Grid(int rows, int collums)
{
this.rows = rows;
this.collums = collums;

//populate the grid with false values
for (int i= 0; i < rows; i ++)
{
Array<Boolean> tempArray = new Array<Boolean>();
for (int j = 0; j < collums; j++)
{
tempArray.add(false);
}
grid.add(tempArray);
}
}

/**
* Used to get the value of a cell from the grid
* @param row the row of the cell
* @param collum the columns of the cell
* @return the value of the cell
*/
public boolean getTile(int row, int collum)
{
return grid.get(row).get(collum);
}

/**
* Used to set the value of a cell in the grid
* @param row the row of the cell
* @param collum the columns of the cell
* @param aBool the value of the cell
*/
public void setTile(int row, int collum, boolean aBool)
{
grid.get(row).set(collum, aBool);
}

/**
*
* @return the number of horizontal rows in the grid
*/
public int Rows()
{
return rows;
}

/**
*
* @return the number of vertical columns in the grid
*/
public int Columns()
{
return collums;
}

public void printGrid()
{
for (int i= 0; i < rows; i ++)
{
String aString = new String();
for (int j = 0; j < collums; j++)
{
if (getTile(i,j) == true)
{
aString = aString + "1";
}
else
{
aString = aString + "0";
}
}
System.out.println(aString);
}
}
}

Once I had the grid, I ported the code from a flash demo I made that created cave/caverns using cellular automata. From there I just spent some time playing around with the rules. The main rules are cells with less than 3 neighbour cells that are ‘alive’ will die that pass, and cells surrounded by 5 or more living cells become ‘alive’ if they aren’t already alive. I do 5 iterations of these rules before doing a few special rule sets at the end to help clean up situations such as 1*1 single living cells and to shape the coral a little better.

Once created each cell auto tiles by working out how many cells it is surrounded by and in what positions to determine which tile to use for itself. I use two layers of coral, one for the foreground that when touched ‘hurts’ the player, and the other is a background layer just for aesthetics. The background layer uses bigger size cells, so has less cells in its grid. As such I fill the gird with more noise to start, but besides that it generates using the same rules as the foreground cells, and just auto tiles using a different tile set.

I am pretty pleased with the results of the generation, and have additional rules in place to make levels generate with more coral in later levels to make them harder as you progress, which I feel works pretty well.

This week I am planning to think about the design of the game more, as I feel it is more tedious to play than it is fun to play, so I will try and think of ways to make the game more fun!