rune|vision blog

Rolling Grids for Infinite Worlds

2013-05-02T16:01:00.001+02:00

I want to share how I do the rolling grids I use in EaS that in essence acts as infinite 2D arrays.

Originally, my procedural game EaS (you can read all the posts about EaS here) was divided into "levels". The levels lined up seamlessly so wouldn't be noticed by the player, but in the implementation they were completely separate. Tons of code was used to deal with the boundaries of the levels. Every algorithm that handled some kind of grid, and which looked at neighbor cells in that grid, had to have special boundary case handling for the edges, which was a pain.

In 2012 I completely rewrote this to instead be based on a set of layers of infinite grids. Each layer loads/generates chunks on demand, but exposes an interface where this is abstracted away making the layer in essence "infinite". This approach has removed the need for almost all boundary case handling related to edges of grids.

An infinite grid could be implemented as a dictionary, but dictionaries have a large overhead. I wanted performance that was much closer to a regular 2D array. A rolling grid is just a 2D array with some very lightweight number conversions on top.

You can use rolling grids when you load/generate data (such as chunks of the world) in a grid locally around some position; typically the player's position. As the position moves, you load/generate new chunks in front, and destroy the ones that are now further away in order to keep the loaded chunks centered around the position in focus. You have to make sure yourself that you don't have cells loaded that are too far apart, and you also need to not attempt to read cells that are further out than the currently loaded area.

Usage

When creating the grid you'll need to know the maximum size of the area you may need to have loaded at once. E.g. you can create a 40x40 grid if you know you'll never have chunks loaded simultaneously that cover more than a 40x40 area.

RollingGrid<LevelChunk> myRollingGrid = new RollingGrid (40, 40);

When a new data cell has been loaded/generated you assign it to the grid like this:

myRollingGrid[x, y] = myNewLevelChunk;

When you have destroyed a data cell, you must set it to null in the rolling grid:

myRollingGrid[x, y] = null;

That's it!

RollingGrid class

Note about the code: You'll have to replace Logic.LogError() with your own favorite logging mechanism of choice.

public class RollingGrid<T> where T : class {
 
 private int m_SizeX, m_SizeY;
 private int[] m_ColItems, m_RowItems;
 private int[] m_ColIndices, m_RowIndices;
 private T[,] m_Grid;
 
 public RollingGrid (int sizeX, int sizeY) {
  m_SizeX = sizeX;
  m_SizeY = sizeY;
  m_Grid = new T[sizeX, sizeY];
  m_ColItems = new int[sizeX];
  m_RowItems = new int[sizeY];
  m_ColIndices = new int[sizeX];
  m_RowIndices = new int[sizeY];
 }
 
 public T this[int x, int y] {
  get {
   int modX = Util.Mod (x, m_SizeX);
   int modY = Util.Mod (y, m_SizeY);
   if ((m_ColIndices[modX] != x && m_ColItems[modX] > 0) ||
    (m_RowIndices[modY] != y && m_RowItems[modY] > 0))
    Logic.LogError ("Position ("+x+","+y+") is outside "
     +"of RollingGrid<"+typeof (T).Name+"> current area.");
   return m_Grid[modX, modY];
  }
  set {
   int modX = Util.Mod (x, m_SizeX);
   int modY = Util.Mod (y, m_SizeY);
   
   // Check against book-keeping
   if (m_ColItems[modX] > 0 && m_ColIndices[modX] != x)
    Logic.LogError ("Trying to write to col "+x+" ("+modX+") "
     +"but space already occupied by col "+m_ColIndices[modX]);
   if (m_RowItems[modY] > 0 && m_RowIndices[modY] != y)
    Logic.LogError ("Trying to write to row "+y+" ("+modY+") "
     +"but space already occupied by row "+m_RowIndices[modY]);
   
   T existing = m_Grid[modX, modY];
   
   // Early out if new and existing are the same
   if (existing == value)
    return;
   
   // Don't allow overwriting
   if (existing != null && value != null)
    Logic.LogError ("Trying to write to cell "+x+","+y+" "
     +"but cell is already occupied");
   
   // Set value
   m_Grid[modX, modY] = value;
   
   // Do book-keeping
   m_ColIndices[modX] = x;
   m_RowIndices[modY] = y;
   int delta = (value == null ? -1 : 1);
   m_ColItems[modX] += delta;
   m_RowItems[modY] += delta;
  }
 }
 
 public T this[Point p] {
  get { return this[p.x, p.y]; }
  set { this[p.x, p.y] = value; }
 }
}

You'll also need this Modulus function which return a number between 0 and period no matter of the input x is positive or negative. I use these modified modulus and division functions all over the place in my game, wherever I need to convert between different coordinate systems.

public class Util {
 
 public static int Mod (int x, int period) {
  return ((x % period) + period) % period;
 }
 
 public static int Div (int x, int divisor) {
  return (x - (((x % divisor) + divisor) % divisor)) / divisor;
 }
}

If you're wondering why there's two native modulus (%) operations in there instead of simply only adding period if the number is negative, it's because I measured it to be faster than the cost incurred by a branch - see branch prediction.

Automating it further

A single rolling grid can be nice in itself, but the real beauty in EaS is how the different data layers automatically keep track of which chunks needs to be loaded and unloaded based on dependencies from higher level layers. But that's material for future posts.

Technologies in my Procedural Game EaS

2013-02-17T19:09:00.000+01:00

This post is about EaS, my 2.5D platform game under development with focus on non-linear exploration, set in a big, continuous world. You can read all the posts about EaS here.

In this post I'm creating an overview of the different technical aspects of EaS and listing links to posts I've written in each area. I'm also describing areas I haven't written about (yet).

If there's any of these areas you'd like to hear more about, let me know in the comments. This can help me decide which areas to prioritize in future posts.

Level Design

The level design in EaS is "deliberate", meaning that aspects of a level are created on purpose rather than randomly, like it is the case in games like MineCraft. With gameplay that doesn't allow removing or adding terrain, the levels have to be guaranteed to be traversable from the start.

Maze Generation and Key/Lock Placement

Generating a tree structure from a maze (2012)

Forcing Structure in Procedural Spaces (2011)

Demo of Procedural Environment (2010)

Terrain Generation

The terrain in EaS is based on a 3D grid of blocks (popularly known as "voxels" although they are not really) and mesh geometry is generated based on this. The geometry has smoothed edges and support for textured transitions at edges and between blocks of different materials.

Level Geometry

Sweet Sweet Edges (2011)
First Peek at Levels (2010)

Level Props

Using Imposters

AI / Path-finding

The enemies in EaS are not simply patrolling back and forth on a platform - they have the ability to follow the player almost anywhere, or flee away.

Game Play Implications

Demo of Hunting AI and New Models (2010)
Agile Enemies in a Platform Game (2010)

Procedurally Created Path-finding Graph

Camera Behaviour

A side-scrolling game is not the hardest to create a basic working camera behavior for, but there is a lot that can be done to elevate the behavior from "good enough" to "great". One thing is having the camera look ahead rather than trailing behind, but without introducing sudden camera moves when changing direction. (The classic Sonic games did this too.) Another is to frame what's important at the position where the player is currently at.

Tips for a Platformer Camera

Level Aware Framing

Use of Threading

EaS originally used a clumsy mix of Unity co-routines and threading for its procedural generation, but it has since been rewritten to do all generation completely in a background thread, except for the actual instantiations, which happen in the main thread, spread out over multiple frames.

Generate in Background Thread, Instantiate in Main Thread

Working With Unity Objects in Threads

Unity's ScriptableObject and Threading (2011)

Layers of Infinite Grids

Originally, EaS was divided into "levels". The levels lined up seamlessly so wouldn't be noticed by the player, but in the implementation they were completely separate. Tons of code was used to deal with the boundaries of the levels. Every algorithm that handled some kind of grid, and which looked at neighbor cells in that grid, had to have special boundary case handling for the edges, which was a pain.

In 2012 I completely rewrote this to instead be based on a set of layers of infinite grids. Each layer loads/generates chunks on demand, but exposes an interface where this is abstracted away making the layer in essence "infinite". Layers can depend on lower layers with a specified amount of "padding". A layer can then freely access a lower layer as long it is doesn't try to access it outside of the contractual bounds. This approach has removed the need for almost all boundary case handling related to edges of grids. At the same time it has enforced a much more well-structured division of information and storage in the generation algorithms.

RollingGrid "Infinite" 2D Array

Layers Upon Layers (or How to Avoid Dealing with Boundary Cases)

Debug Options

With a game as complex as EaS there is a need for tons of different kinds of debug information that can easily be switched on and off while running the game. For a long time, this was a bit tedious to maintain, but I recently found a more or less elegant way to add debug options in-place in the code where it's needed and have the GUI that displays the available debug work pick-up all the options automatically, without any maintenance.

Automatic GUI for Debug Options

I'll update and maintain this post as I write more posts, and as the game evolves.

Automatic Setup of a Humanoid

2013-02-17T16:25:00.000+01:00

I wrote a blog entry on the Unity site called Automatic Setup of a Humanoid detailing the work I did for the Mecanim animation system in Unity 4 on automatically detecting human bones in arbitrary skeleton rigs.

Names of bones, bone directions, bone length ratios, and bone topology all provide hints to which bones should be mapped to what. While none of those sources are very reliable on their own, they can be combined and used in a search algorithm to get rather reliable results.

Generating a tree structure from a maze

2012-05-15T00:27:00.000+02:00

I got a mail from Robert Stehwien asking me how to generate an environment tree (as described on Squidi.net) from a 2D maze - something I wrote previously that I do in my game EaS but didn't go in details with.

An environment tree is basically a tree structure representing connectivity in a spatial space, where inner nodes represent junctions where for example a corridor splits into two or more, and leaf nodes represent dead ends. An environment tree of a 2D maze would have inner nodes where the maze corridors split into two or more and leaf nodes at dead ends.

2D maze with internal and leaf nodes marked.

I wrote the code for doing it more than five years ago. It's rather convoluted but anyway, this is how it works:

I use a "recursive back-tracker" algorithm which is basically the same as a depth-first search. Despite the name of the method, I implemented it as a loop and not as a recursive function. Every time it hits a dead end, it marks the cell as a leaf node and adds it to a list of nodes. While backtracking, every time it hits a junction (3 or 4 passages meeting up) it marks the cell as an internal node and adds it to the list as well if that cell wasn't already added before. While walking the maze it also stores for each cell what the previous cell is. After this process we have a flat list of all nodes in the tree and a way to always go backwards towards the root.

Next, it simply iterate through all the nodes in the list and for each walk backwards towards the root until it hits a cell that's a node too. It marks this node as the parent of the other node and continues the iteration. At the end, all nodes except the root should have a parent, and from this it can also easily find out what the children of any nodes are. And thus the tree structure is complete.

Should I write the code today I'd have done it with an actual recursive function instead. Though I haven't tested it, I think it would take a parent node, the cell of that node, and an initial direction to walk in as parameters. Then it would walk along that path until it either reached a junction or a dead end. At a junction it would create an internal node for that junction, mark it as the child of the node passed as parameter, and call the function recursively for each direction in the junction except the direction it came from. At a dead end it would create a leaf node and mark it as the child node of the node passed as parameter, and return the function with no further recursive calls. At the end the tree structure would be complete.

Still making that EaS game...

2012-04-23T23:12:00.000+02:00

Though I haven't posted about it for the good part of a year, I haven't dropped my game EaS. Google AI Challenge ended up taking up quite some time last fall and after that was a period where I was preoccupied with other things, but I've recently gotten some new ideas and enthusiasm for continuing this long-running spare time project.

Stay tuned...

Google really wants my resume

2012-03-09T03:47:00.003+01:00

I just got this mail from one of the Google AI organizers:

Hello,

Thanks for taking part in the latest AI Challenge. I hope you enjoyed it!

Since you ranked in the top 100, Google really wants to see your resume (curriculum vitae). If you want to be contacted by a Google recruiter, send me a quick reply letting me know.

I will put in a good word for anybody who is interested. With more than 7000 entries in the final tournament, ranking in the top 100 is a serious achievement. I was really impressed by the skill of all the top-ranking bots.

If you are unsure, my advice is to go for it. It's a wonderful opportunity if you love figuring out tough problems and writing awesome code. Your recruiter will be happy to answer any questions you have!

I'm not unsure though. With my 4th place I guess I'd be high on their want list, but I'm happy with my job at Unity. I'll apply my "love for figuring out tough problems and writing awesome code" there instead. :)

By the way; sorry for never getting around to writing part 2 and 3 of the explanation of my bot. After seeing how the announcement of the winners got practically no attention anywhere I got a bit demotivated. You can still download the source though and see how it's done, and if you have any questions, just ask.

4th Place

2011-12-24T14:28:00.002+01:00

What do you know, it looks like I got 4th place in the AI Challenge!

Final Rankings

I began writing an explanation of my bot and you can read Part I here as well as downloading the source code. Right now is holiday time with the family; I'll write up the remainder afterwards. :)

AI Challenge - My Bot Explained, Part I

2011-12-23T01:12:00.005+01:00

So my ant colony bot is doing rather well in the final AI Challenge tournament. It's ranked around between 4 and 11 depending on when you look.

Reading about some of the strategies used by other bots, I'm surprised mine has performed so well, since it's not really that sophisticated. Well, I'm releasing the source code here. This is in the same state as when I submitted it without further cleanup, so not the most tidy code but not a complete mess either.

runevision bot C# source code

Note that the bot behaves completely different depending on whether it's compiled as a DEBUG or a RELEASE build. As a debug build it will look for a file called parameters.txt describing parameters to use for various constants in the code and when executed multiple times it will run with those parameters having different values and keep track of statistics of which parameter values work best. More about that later. As a release build the constants are hard-coded in the code and that's what is used in the actual competition.

The bot have these primary functions:

Combat logic to evaluate each of 5 possible moves (4 directions plus staying) for each ant. Afterwards each ant has a score for each move.

Path-finding done using "flood-filling" / breadth-first search from the goal locations. Afterwards each ant has an assigned goal and know which direction to move in to get there.

Goal handling. This basically adds extra points to one or more of the 5 move scores based on the direction obtained from the path-finding.

Moves resolution. This resolves which ant has the right to move into which position based roughly on "who needs it the most".

Path-Finding

The first thing I implemented was path-finding. This was originally done using a flood-fill / breadth-first search from the goal locations. The default path-finding algorithm choice for computer games is A* but it's not useful for being reused by many agents which is why I used the flood-fill instead. It might also be the same or similar to what is called collaborative diffusion - not entirely sure about that; I only heard about that term after I had implemented my solution.

Initially I simply used a queue for the search. I later switched to a priority queue so I could us various cost functions for the path-finding. For example, by giving positions occupied by my own ants a higher cost, ant behind them will prefer to go around them instead of just being stuck.

I also implemented support for specifying for a goal the maximum number of ants assigned to it, the maximum distance to search out from the goal, and an initial cost (which gives the goal lower overall priority).

The goals I ended up using are:

Defense positions around my own hills (1 ant each, no cost, max dist 30)

Enemy hills (a third of all my ants divided by number of known enemy hills, no cost, no max dist)

Food (1 ant each, cost equal to 4 dist, no max dist)

Explore (1 ant for each explore position, cost equal to 25 dist, no max dist)

Enemy ants (20 ants each, cost equal to 42 dist, max dist 13)

The defense positions are positions immediately around my own hills. 12% of my ants are assigned to defense, divided between my hills if more than one.

Any unassigned ants are assigned to enemy hills as well.

This post is ending up much longer than I thought so I'm splitting it up. Read on in part II about goal handling and moves resolution.

Epic Ant Battle Videos

2011-12-20T23:00:00.003+01:00

The final tournament has begun. Here's some interesting battles my bot has been in that I've captured on video.

My 5th game where my bot annihilates 8 opponents in an epic battle!

My 6th game where my opponent just won't die (or my massive army is not quite aggressive enough). Also: Dancing!

Google AI Challenge Update

2011-12-18T19:09:00.003+01:00

For the past - hmm, almost 2 months now - I've taken a break from my other hobbies and let myself become distracted by Google's AI Challenge - an Artificial Intelligence (AI) programming contest.

Not for much longer though since the final submission deadline is in 10 hours at the time of writing.

When I wrote about it a months ago I'd only been at it for a few weeks but my bot was already ranked 39th in the world out of 10000+.

Since then I've made a lot of improvements - but so have the other contestants, so the overall level has continuously risen.

Whenever a new version of a bot is uploaded to the content servers, the skill and rank is completely reset, so the bot will have to fight its way all the way back up from the bottom. That can take a few days to a week depending on how high a ranking it can get before it's stabilized.

I last uploaded a bot four days ago. It has gotten up to rank 22 in the world; my highest ranking yet. It's also the top ranked bot in Denmark by a large margin and the 3rd ranked bot written in C#.

When working on improving the bot, it's usually hard to know if some new idea will actually improve the bot or just make it worse without having tested it first. I usually test by running a game with the new version against the old version. However, most changes only make a small difference that will only slightly increase the bot's chances of winning, so it has to be in many games before it's clear if it's better or not. Did it win 4 out of 6 games? Might just be a coincidence due to random luck.

You can see it quickly becomes tiresome to test these things manually. That's why I programmed a simple framework to automatically run many games in a row between the various version of the bot and gather statistics on which versions win the most times. I've often let this run overnight so I have statistics from hundreds of games the next day.

Sometimes, however - sometimes an idea turns out to be a significant improvement. By significant I mean that the new version consistently beat the previous version - as in 10 out of 10 times. Those times when I've managed to make such an improvement have been the most satisfying moments of this competition.

The most interesting improvements have all been related to how the ants handle combat. The way battle resolution works in the game follows simple rules but has complex consequences and my understanding of it has increased in stages.

The combat is basically about ants being in majority winning over ants that are in minority. If one red ant is within combat range of one white ant, they both die. But if one red ant is within combat range of two white ants, only the red ant die and both of the white ants survive.

Initially I thought combat was a matter of being cautious. Only move into combat range if you have more ants you can move within range than the opponent has. But it's not that simple. There's various potential outcomes to consider and also an element of gamble. I might write some more about it after the competition has ended if not somebody higher ranking does it first. Not that I'm an expert by any count - I feel like I've only scratched the surface.

Anyway, since I uploaded that last bot four days ago I've made several significant improvements in the combat skillz of my bot, meaning that the newest version I have here totally and consistently kicks the ass of that version I uploaded four days ago. Now I've just uploaded this new version. It will probably be the last unless I get some last-minute epiphany which is not likely by now.

We'll see how it performs in the final tournament.

Ant Colony - Google AI Challenge

2011-11-23T21:23:00.002+01:00

For the past few weeks I've taken a break from my other hobbies and let myself become distracted by Google's AI Challenge.

It's an Artificial Intelligence (AI) programming contest about programming the smartest virtual colony of ants which fight against other colonies for domination.

The matches are played entirely by the submitted programs on online servers and replays of them can be seen online at the website. My matches can be followed here, such as this one.

As mentioned, I've been at it for a few weeks, and my colony is now the 39th highest ranked world-wide out of several thousands, and the highest ranked in Denmark out of 138. :)

It's quite good fun, so I'll try to make a few more improvements, although I'm beginning to run out of ideas. It's tough competition for sure!

If you know a bit of programming, it's easy to get started, and starter packages are provided for all kinds of different programming languages including Java, C#, Python, C++ and more.

Let me know if you're participating as well!

Forcing Structure in Procedural Spaces

2011-08-21T17:33:00.011+02:00

The procedural game I'm working on in my spare time, EaS, has a focus on non-linear exploration and is set in a big, continuous world. When I've let people play it in its current state they've been happy to roam around at first, but quickly become bewildered from a lack of sense of direction and purpose because they could go so many places but had little idea of what they're supposed to do other than running around aimlessly. That got me thinking about ways to direct the experience better.

In Part Six of his series on Proceduralism, Andrew Doull recently wrote:

Populous, Dwarf Fortress, Minecraft and Terraria all cheat procedural generation in two important ways: they allow you to modify the topology of the space and they encourage you to make interesting content in that space to which you become attached. An uninteresting dead end can be transformed into a useful corridor, or lit by a torch to mark that you've 'already been here' or mined for valuable ore. The procedural generation systems they use may make beautiful places, but it is the player's job to change them into interesting spaces.

This sums up the situation pretty well - and if we ignore the building aspect, other games like Spelunky can be added to the list as well. The choice of wording "cheating" can be discussed, but it's certainly a way to circumvent one of the biggest challenges of procedural generation: To make the environment interesting and challenging while still ensuring that it's never impossible to traverse.

Non-Modifiable Environments that Direct the Player
In traditional games it's in general not possible to add or remove from the environment (i.e. Mario, Sonic, Zelda, Metroid, you name it; almost all games are like that). If the player could just dig or blow up a hole anywhere he wanted, it would ruin the carefully constructed challenge. So these games ensure traversability not by allowing the player to change the environment, but by ensuring that it's traversable from the beginning. And that's not hard to do in manually designed levels. If it's not possible to traverse a location, the designers will find out when testing it and then just change it.

For games that are procedurally generated at runtime, it's not always possible to test any level or environment prior to release because there may be an infinite number of them. The above mentioned games circumvent this problem by simply not giving any guarantee that the environments are traversable, because the player in those games can always dig or explode a hole almost anywhere to create a passage where there wouldn't otherwise be one.

Non-Modifiable Environments in Procedural Games
So modifiable environment lifts a big burden from the procedural generation problem in those games. However, some people - like me - still like more traditional games a lot where you have to deal with the given environment rather than just being able to dig a hole through it. Games where the experience is a bit more structured and directed instead of relying entirely on the player creating challenges for himself.

Creating procedural environments that do have a traversability guarantee imposes a lot more restrictions on the generation algorithms, and I find it to be an interesting and worthy challenge. My efforts in that direction can be seen in EaS, my 2.5D platform game under development with focus on non-linear exploration. (You can read all the posts about EaS here.)

Spatial Algorithms that Create Structure
So what kinds of algorithms can be used to create environments that structure the game experience and guides the player?

Before talking algorithms, it's useful to look at what structure and guidance techniques are used in games in general, including non-procedural games.

Linear progression is the simplest way to structure and guide the player. Simply move on forward; it's the only way to go!
Keys and locks is a way to break up linear progression, whether it's literal keys and locks like in Commander Keen and Doom, or other variants like switches that causes a door elsewhere to open, a bridge to extend, or a hazard blocking the way to disappear.
Non-linear games often have features of unlocking new regions when some threshold is met, whether it's experience points in RPGs or number of collected stars in Super Mario 64.
Non-linear games may also grant the player new abilities that are required for certain parts of the world. This effectively is also used for unlocking new regions, but at the same time the ability is also used as a normal part of gameplay within those unlocked regions. This is especially popular in games in the Metroidvania genre.

There's many other techniques, but these are sufficient for this discussion.

For linear games, there's no need for algorithms to structure the experience and guide the player, since the structure and guiding is inherit in the linearity itself. Making the game interesting is still a challenge though, so algorithms are needed for that. This comes down to the moment to moment gameplay, and is very dependent on which type of game it is.

Importantly, making the moment to moment gameplay interesting is needed in any case, no matter if the game is linear or not.

Simple key and lock puzzles can easily be implemented procedurally. I wrote a bit about it here where there's also a playable demo of it, but it's also described well on Squidi.net.

A key and locked door in EaS.

Unlocking parts of the world, whether it's based on collectibles or on gained abilities, should also be more or less simple to implement. I know others have done it already and I'm currently experimenting with algorithms for it myself.

Now, in his article, Andrew Doull also wrote:

My procedural spider senses tingle as soon as I see a procedural generation system that uses one of the following two approaches: 1. Mazes (and by extension BSP-trees) 2. Height maps - because I've yet to play a game where I've exclaimed 'Wow, what a great height map' (...) and the pleasure of solving a maze isn't the same as the pain of having to play through one. I've also seen a rise in recent suggestions and several implementations of Metroid-style procedural generation featuring gated lock-and-key puzzles to partition a map, on the assumption that being forced to traverse through a non-linear space looking for a key is some how interesting. This is putting the cart before the horse: Metroid (and Zelda) use this technique to force the player to explore an already interesting (and hand-designed) location, not because looking for a key is itself challenging.

This is missing the point, I think. Of course the locations and the moment to moment gameplay in them needs to be interesting. Just like a linear game with no challenges (say, just walking from left to right) would bore you to death, so would a game with a different guiding structure, such as keys and locks, or progressively unlocked regions. But that doesn't mean that those guiding structures have no merit or importance. Indeed, just like they were important in Metroid and Zelda, so they can be in a non-linear procedurally generated game.

They have more merit too than just to "force the player to explore an already interesting location". They serve at least three additional purposes:

To prevent player confusion and bewilderment at having too many open possibilities, especially in the beginning. An open world where there's access to everything from the start can give a sense of lack of direction or purpose which can be very off-putting - more so for some people than others. This is why most open and "sand-box" games still have clearly defined "main missions" that can be pursued, and certain options, areas, or missions that are not accessible until further into the game.
To give the player a sense of reward when a new part of the world is unlocked.
To keep things fresh and interesting by saving some things in the game for later.

To dismiss an interest in such guiding structures as "putting the cart before the horse" only makes sense if some people think that a game can consist of these guding structures alone with no gameplay beyond that. But I'm not sure who ever claimed something like that.

Room and Corridors versus Mazes
In his article, Andrew also writes:

The most successful (and perhaps only successful) procedurally generated game spaces so far are all based on Rogue, with its simple room and corridor design. With a room and corridor design we get four important features:
Corridors - which act as natural choke points at each end, and cover if you are in them
Convex shapes - spaces where you can see everything in the space from everywhere else
Concave shapes - spaces where some space is hidden from another (more cover)
Loops - which allow you a safe haven by traversing the loop to recover when chased by enemies of the same speed or slower

But it's obvious that these success criteria are coupled tightly with Rogue-like gameplay and have little relevance to many other types of games.

In any case, I have a hard time seeing how this room and corridor design is superior over a design based initially on a maze. The room and corridor design connects rooms in a web that gives very little control over the progression of the player through the area, as far as I can see, since there's an undefined number of ways to get from one point to another.

In contrast, a design based initially on a perfect maze (a maze with no loops) has only one way to get from any point to any other. This means that obstacles or challenges can be strategically placed at positions that the player cannot avoid - in other words it gives actual control over choke points at a global scale if so desired, whereas the room and corridor design may create local choke points, but won't guarantee the player has to pass through them.

The important point here is that mazes can still provide all those other features as well.

Rooms? Just place rooms in the beginning before the maze algorithm has run. Rooms could define locations with potential entrances or required entrances, and the maze algorithms will make sure to connect them up (but without forming any loops). I have that feature in my own maze algorithms and use it to place predefined rooms where artifacts are located.
Loops? After the maze algorithm has run and after required global choke points like locked doors have been chosen and placed, just carve some additional corridors/tunnels, maybe starting from some of the dead ends left by the maze algorithm. When doing so, prevent connecting parts of the maze that are on opposing sides of a global choke point (like a locked door).
Avoiding dead ends? Dead ends can easily be made non-pointless by placing rewards there (or keys to locked doors), but they can also just be removed in a pass that runs after the maze algorithm that removes any dead ends that haven't been assigned any purpose. The algorithm can also be made to leave a certain number of dead ends in, or give preference to removing long dead ends or short dead ends, depending on what is wanted.

Maze generation with rooms and loops.

The important part here is that using a maze algorithm does not imply that the result will look and feel like a maze. It's just an algorithm to get things done, and the useful part is that at one point during the generation there's exactly one way to get from any point to another, although this doesn't have to be the case when the whole generation is completed.

EaS: Video of New Environments

2011-08-15T00:18:00.006+02:00

This post is about EaS, my 2.5D platform game under development with focus on non-linear exploration, set in a big, continuous world. You can read all the posts about EaS here.

In the last post I wrote about how I've improved the edges in the environment generation of EaS. But the background scenery was basically just parts of the foreground extended far into the distance which was not terribly interesting to look at.

Since then I've implemented generation of more interesting backgrounds with hills and cliffs and forests. The background scenery can be seen in the first half of the video here.

The video shows a green hilly environment and an underground dungeon style environment. There's no enemies in this demo and many objects are still placeholders - the focus is on the terrain itself.

The background is somewhat faint (due to aerial perspective) and blurry and isn't meant to steal the attention away from what's happening in the foreground, but having interesting detail in it can nevertheless add a lot to the overall feel.

Another thing to note in the video is the dynamic camera framing. It zooms the view in and out and places the player nearer the top or bottom of the screen as necessary based on the surroundings. It's something I may go into more detail with in a future post.

Firefox 5 breaks my blog?

2011-08-10T19:48:00.004+02:00

I just upgraded from Firefox 3 to 5 and find that my blog is shown without a stylesheet at all. It still works fine in Firefox 3, and latest Chrome and Safari and I assume other browsers too. And the rest of my site still works fine in Firefox 5 too; it's only the blog part that's broken.

Update: It appears it was the stylesheet that was not recognized. I had my stylesheet inside an .asp file to be able to execute server-side code in it. That has always worked just fine but it appears to break when the browser is Firefox 5 AND the site linking to the stylesheet is on Google's Blogger service. When the same stylesheet is linked to from the part of my website that's hosted on my own server, it works fine. The stylesheet is hosted on my own server in both cases, so how it can make any difference where the html page is hosted I do not understand. In either case, baking the stylesheet into a static .css file and linking to that instead seems to have fixed the problem.

EaS: Sweet Sweet Edges

2011-05-29T19:22:00.004+02:00

This post is about EaS, my 2.5D platform game under development with focus on non-linear exploration, set in a big, continuous world. You can read all the posts about EaS here.

Last time I posted an update about EaS was - 10 months ago!? Well, development hasn't been idle though - far from it! - it's just that I've been working on some refactoring and changes that ended up being rather time-consuming. Some big hurdles are now over and blog updates should hopefully be more regular going forward.

One of the most recent features I've implemented is handling of smoothing and texturing of edges. This has been on my todo-list since forever but I had to switch to a better way of generating meshes before this became feasible.

Consider a generated environment with surfaces that meet each other in sharp edges:

The surfaces look weightless like they're made out of cardboard. No offense to MineCraft, but it's not the look I'm going for. Let's smooth those edges a bit.

Better. The environment now has a certain weight to it; it feels more solid. But the abrupt edges between surfaces with different textures still makes it seem artificial and less believable (believable not in the sense of realism as I'm not going for that, but in the sense of suspension of disbelief). Let's cover up those abrupt changes in texture.

Ahh! With the edges of the textures covered up with natural-looking transitions, the world has finally come alive and is more inviting than ever.

A few more examples of the current look of EaS (don't mind those ugly green box stepping platforms and spikes. They're placeholders I haven't yet replaced with something better):

Most of the textures are made with good old POV-Ray by the way; the raytracer I used to work a lot with back in the days.

The environment is controlled by a neat system of specifying block types, face types, and edge types. Each "cell" in the world (think big voxel) is of a specific block type, for example "Bricks" or "Empty". The procedural generation algorithm fills in the block types of all cells in a generated area prior to constructing the mesh.

A block types specifies the face types it has. For example, this is the data for the Bricks block type (here called EnvironmentData but I should rename that):

All faces here uses the BrickWall face type, except the Up face which uses the Grass face type. Here's the data for the Grass face type:

The face type specifies the material to use for the face surface, as well as edge data for convex, flat, and concave edges. The edge data is used to specify rounding size for an edge as well as the material, width, and UV data for the textured strip that is generated over the edge.

This is an example of an edge texture (diffuse channel):

This one is of course extremely wasteful, but the system is already set up so multiple edges can be contained in one material; I just need to change my texture so they actually make use of that.

Currently it's not possible to differentiate the different edges of a face but I'll need to add support for that so different edge data can be used for edges that are "along U" and "along V".

When generating geometry an edge is of course shared between two faces. The priority value of an edge is used to settle which of the two faces get to use their edge data for the edge.

When I had to set up the relationships between block types, face types and edge types, that was the first time the data got too unwieldy for me to hard-code directly in the code. Instead I turned to Unity's ScriptableObject, as I wrote a short post about here. Using the ScriptableObject means that Unity's Inspector can be used to specify the data, and Unity's serialization system automatically takes care of everything related to storing and loading the data. At some point I'll probably write some custom editor GUI for the data too so it becomes easier to comprehend and get an overview over.

And that's all I have to say about edges!

Unity's ScriptableObject and Threading

2011-05-20T19:02:00.004+02:00

I found a pleasant solution to a problem I had in Unity that I thought I'd share. This post is technical in nature and won't be of interest to people who don't use Unity.

In my procedural game I'm doing a lot of lengthy calculations and I've been looking into doing them in a separate thread in order to easily spread out the calculations over multiple frames. Using co-routines for this was getting overly convoluted, with yield statements and StartCoroutine() calls sprinkled all over the code-base.

Threading is supported in Unity using the normal .Net (or more specifically Mono) APIs for threading. However, the Unity API can't be touched in anything else than the main thread, or errors will occur. Luckily the lengthy calculations are mostly self-contained and are not touching the Unity API.

However, the calculations do use some data structures that are stored in the form of ScriptableObject. Using ScriptableObject is the simplest way to store some data in Unity with automatically handled serialization. Also see Bas' explanation here.

The problem?

Querying the name of a ScriptableObject can't be done outside of the main thread.
Doing equality comparisons between ScriptableObjects can't be done outside of the main thread. This includes checking if a ScriptableObject is null.

These are things I can't avoid in my code. So instead I came up with this derived class that I now use for all my ScriptableObject needs:


using UnityEngine;

public class ThreadFriendlyScriptableObject : ScriptableObject {
    
    // Hide the name property with a public variable of the same name.
    // (Also hide this in the Inspector.)
    [HideInInspector]
    public new string name;
    
    // Set it to be the same as the property was.
    // (OnEnable will be called from the main thread so it's ok here.)
    void OnEnable () {
        name = base.name;
    }
    
    // Override equality operators to avoid calls into
    // the Unity API when doing comparisons.
    
    public static bool operator == (
        ThreadFriendlyScriptableObject a,
        ThreadFriendlyScriptableObject b
    ) {
        return object.ReferenceEquals (a, b);
    }
    
    public static bool operator != (
        ThreadFriendlyScriptableObject a,
        ThreadFriendlyScriptableObject b
    ) {
        return !object.ReferenceEquals (a, b);
    }
    
    public override bool Equals (System.Object other) {
        return object.ReferenceEquals (this, other);
    }
    
    // We get a compile warning if we don't override this one too
    public override int GetHashCode () {
        return base.GetHashCode ();
    }
    
}

Everything works great for me using this class. There's a few limitations of course:

You won't be able to access or modify the actual name of the ScriptableObject. This is not a problem unless you need the name to change.
You won't get Unity's nice behavior of making a reference to an Object look like it's null if the Object was destroyed. This is only a problem if you plan on destroying the ScriptableObjects at runtime. Since the main function of ScriptableObjects is to be persistent assets, you're not likely to want or need this.

Use at your own risk. :)

My 3rd Person Shooter on Kongregate

2010-12-22T20:55:00.011+01:00

OMG the 3rd Person Shooter demo I made in the beginning of the year has ended up on popular web games portal Kongregate. The game has had 20,000 plays so far and counting and has a rating of over 4.1 out of 5. I'm totally flattered. :D

UPDATE: Kongregate took down the demo after enough other Unity games had been submitted that the demo was not needed to demonstrate Unity anymore.

I made the demo at work at Unity back in the beginning of 2010 to demonstrate various animation techniques, and I ended up making it into an actual game (albeit a small one). Since then it has been possible to play it on the Unity website. The demo was based on a tech demo that Paulius Liekis and I did for a presentation about animation techniques at Unite '09.

So the reason it ended up on Kongregate: Kongregate, which used to host only Flash games, has just announced that they have opened up for Unity games too (and they're having a grand Unity Game Content to kick it off!). They wanted to show their users a simple demonstration of just how great things can be made with Unity, and they picked this Unity demo for that purpose.

So - a little known fact is that I did the voice work for this demo; totally unprofessionally too, but it brings a lot of humor to the game. Reading the comments from users on Kongregate, it seems that it's appreciated. :D

A lot of the comments a very positive or out right hilarious. A few examples:

"Takes long to load, but definately worth it. 5/5"

"Wait... This is an actual 3-D game, without lag... And it's not one of those ones with just 3D sprites and whatnot... YES!... YES!... THIS IS DELICIOUS!"

"Cant wait for the sequel Unity demo 2: Better run! and the spin-off game "how do I get behind it?" and don't forget the T.V gameshow "YEAH, Ha Ha, Take THAT!""

"ZOMG!!! love the voice"

"should i pull out my second gun to shoot it with? nooo! why would i do that?"

"lol i love the voice acting :)"

"WOOT! I lost in no fail mode! Robot sploded on my head +)"

"i like the ragdoll physics unity 3d has (this and dead frontier) its fun i killed it on medium ran towards it and BOOM i went flying"

"This. Is. So. Mother. Freaking. Awesome."

"AMAZING Graphics! I Have To Say 5/5 I'm Gonna Devo For This ;)"

"This is actually real?!?! Oh my God the graphics..."

"This game could change the history of kongregate. 3D games Zero lag."

"best graphics on kongregate ever"

"R.I.P. Flash 'Nuff said?"

"BOOOM!sorry that was just my BRAIN exploding from awesome!!!!!!"

I'm famous! Well, except the thing was not posted in my name so nobody will know. Oh well. :P

Procedural Animation Increses Engagement

2010-09-15T21:15:00.005+02:00

A new study confirms that procedural animation in a game, such as the Locomotion System I developed for my Master's Thesis, can improve not only the visual impression of the game, but also increase the overall player engagement significantly.

I was contacted some some ago by Chelsea Hash, a digital media student from the Polytechnic Institute of New York University. She had just finished her own Master's Thesis Reactive Animation and the Play Experience which included a social psychology experiment on the affect of dynamic animation systems on the user experience. The semi-procedural animation system used as part of the experiment is based on the Locomotion System I developed. She told me:

The study found that given four versions of a game with the only variation being the avatar visualization and animation system, the semi-procedural animation system consistently had a positive impact on the game experience. Users consistently ranked the procedurally animated version higher and played it for longer. This effect was found to be subtle and often beneath the user's ability to consciously identify the difference.

I find this highly interesting! My Master's Thesis and many other technical papers about animation techniques simply take for granted that animation techniques that makes characters more physically situated in the game environment increases player immersion - but this study actually tests this hypothesis, and finds that players become more engaged at a general level as well.

Her Master's Thesis is part of her studies at the Social Game Lab where research is conducted that addresses the subconscious qualities in design that make quality interactions. You can read more about Chelsea's work at her website, livelydisposition.com.

For anyone interested in using this form of dynamic animation in their own games (to enhance player engagement!), the Locomotion System can be used for free in any game authored using Unity - get the Locomotion System project folder to get started.

EaS: Demo of Hunting AI and New Models

2010-08-11T21:26:00.009+02:00

This post is about EaS, my 2.5D platform game under development with focus on non-linear exploration, set in a big, continuous world. You can read all the posts about EaS here.

Like I wrote about a few weeks ago I've been working on pathfinding and AI for the enemies in EaS. The AI pathfinding is now reasonably stable and there's a working demo below where you can fight against simple hunting enemies. Right now the enemies always know where the player is; later the knowledge of most enemies will be made less global and more based on local memory.

I've also been working on some new character models and animations. The new animations in particular bring the player avatar and enemies a lot more alive! Even though I'm a complete amateur as an animator, the crude animations I've made still make the character a lot more fun to watch, I think. :)

Here is a simple playable demo of the current state of the game (requires Unity plug-in):

Controls: Arrows to run, Ctrl to jump, Alt to shoot fireballs.

Again, this demo is just a "tech demo" and features no way to win. It extends infinitely to the right. Enemies should be able to chase the player almost everywhere, but they can't pass the checkpoints (the white monuments).

Like I wrote about before, I'm still not sure what gameplay elements would be best at making agile enemies like these the most fun in a platform game. Have a go at the demo above and then let me know if you have some ideas for how to make this gameplay more fun!

EaS: Demo of Procedural Environment

2010-08-08T14:08:00.011+02:00

This post is about EaS, my 2.5D platform game under development with focus on non-linear exploration, set in a big, continuous world. You can read all the posts about EaS here.

I'm taking a break from pathfinding and AI to go back and talk about the raw level design in EaS; More specifically the procedural generation.

The entire world in EaS is procedurally generated at runtime, though it is consistent, meaning that the world will be the same every time you play. However, this is strictly a design choice, not a technical limitation, and I'm considering including some kind of bonus areas or similar that will be different every time.

To give you an idea of the current state of the game, here is a simple playable demo (requires Unity plug-in):

Controls: Arrows to run, Ctrl to jump.

This demo is just a "tech demo" and features no enemies and no way to win. It extends infinitely to the right.

Back in 2007 I explained the procedural level generation of the game. The game has changed a lot since then - among other things it has turned from a tile based 2D game into a 2.5D game with 3D graphics - but the basic method of generation is still the same.

You can actually see the maze map in-game in the demo above by pressing 2. Press 1 to hide the world to only see the map. You can zoom a bit out by pressing Z, X zooms back in, and you can pan around using WASD. Press Esc to reset the camera.

A map of the maze that the area is based on.
The map overlayed onto the actual generated area.
The generated area by itself.

One feature not explained in depth on the page linked to above is the placement of locked doors and keys in the game. The game places locked doors and keys in a "perfect way" such that it is always necessary to find all keys and unlock all doors to be able to proceed, and a "deadlock" will never occur, where the key for a door is placed behind that door. The placements are calculated using a simple algorithm I came up with which is based on dividing the area up into a binary tree and then placing keys in leaf nodes and locks in inner nodes in a specific way. Several years after implementing it, I found this article about "Environment Tree" at Squidi.net. It's basically the same algorithm, so rather than explaining it myself here, I'll refer to that.

A nice aspect about the algorithm is that it supports placing keys both sequentially and nested. In the screenshots above, the red door is sequential in the sense that all the following keys and doors are on the far side of the red door, so once you've gone through it, you don't have to go back. The green door, however, is nested. You go through the green door, pick up the blue key, and then go back out the green door in order to proceed. The algorithm doesn't have separate handling of sequential versus nested key and door placements; these are just emergent properties so to speak.

If there's any interest I can cover other aspects of the procedural generation in EaS in coming blog posts.

Maze Raiders: Good Old Two-Player Fun

2010-08-04T16:06:00.016+02:00

Maze Raiders is a two-player game I made together with three other people back in 2004. You need to sit two persons by the same computer to play the game.

The objective of the game is to run around in a maze and collect more gold coins than your opponent, and to shoot him and steal his coins. The game sports randomly generated mazes each time you play to keep it fresh. There's two different scenarios - jungle and pyramid. It's classic local two-player fun!

Though we were all game design novices, we managed to balance the rules to make for a frantic game that just keeps being fun to go back to. When all coins in a maze are collected you have one minute to try to steal coins from your opponent. During this time the player with fewer coins moves faster than the other player. It's just enough that it's not too late to change the tides, and it makes for a panicked final chase before the time runs out, sometimes with the roles switching multiple times.

Play Maze Raiders
(Requires Shockwave Player plug-in)
In 2004 when the game was made there was no indie game movement to speak of so we had nowhere to announce the game - particularly a game of such a small scope. All we could do was submit it to software distribution services like Tucows and FilePlanet. Ha, things sure have changed since then! I thought I'd take this opportunity to put the game online and let others know about it. Enjoy!

EaS: Agile Enemies in a Platform Game?

2010-07-29T00:04:00.010+02:00

This post is about EaS, my 2.5D platform game under development with focus on non-linear exploration, set in a big, continuous world. You can read all the posts about EaS here.

I've been working on implementing path-finding for EaS, the 2.5D platform game I'm developing. Path-finding will let NPCs (enemies, companions, or other characters in the game) be able to find their way around in the world. For example, this will let them be able to chase/follow the player, or flee away from her.

So far I have a simple proof of concept with multiple red NPCs following the player (but not being quite perfect at it yet):

As mentioned before, some aspects of the game have come a long way already, while other are not even touched yet. I have yet to figure out and decide something as basic as what kind of game mechanics I want the game to focus on. I want game mechanics that create a focus on using the environment to one's advantage, and which makes use of the maneuverability of the enemies in an interesting way. But which mechanics can create that form of gameplay? I'm still a novice at game design.

In practically all platform games I've seen, enemies have exceedingly simple movement patterns and a very limited ability to move around in the level. Most often an enemy simply patrols a small path going back and forth or similar. My aim is to develop more engaging enemies that are almost as agile as the player. If anyone knows of existing games that have tackled this problem, I'd like to know!

I want the focus to stay on platforming though and not make it into a combat game. I don't care for twitch or combo based combat, but would prefer a small tactical element instead, using the local environment to one's advantage somehow.

I've thought about the 3 most dominant fighting mechanics in platform games:

Jumping on enemies' heads
Like in Mario or Sonic
Shooting (typically horizontally and vertically only)
Like in Commander Keen or Cave Story
Melee
(I haven't played a lot of those - Jak and Daxter maybe? But that's 3D)

Early tests quickly revealed that jumping on enemies' heads don't work at all with agile enemies that move fast and unpredictably. All games with this mechanic have enemies that move rather slow or at least in a very predictable pattern.

Melee - I'm not sure how that would work well, as you'd have to always approach the enemies closely, which I think will make it harder to use the environment in an advantageous way.

Shooting from a distance seems like the best candidate to support the kind of gameplay i want, but I'm still not sure how to model the details of the game mechanics to encourage a play style based more on simple tactics than on head-on confrontation.

First Peek at the Levels in EaS

2010-06-14T22:06:00.007+02:00

This post is about EaS, my 2.5D platform game under development with focus on non-linear exploration, set in a big, continuous world. You can read all the posts about EaS here.

I've been working on a platform game on and off in my spare time for a looong time. Working title: EaS.

It's a 2.5D platform game with focus on non-linear exploration, set in a big, continuous world. I'm using Unity to develop it.

In some respects it has already come a long way (advanced algorithms used to control the world in the game) and in other respects the fundamentals haven't even been decided on yet (the exact gameplay mechanics, story, graphical style...) so it's very much a work in progress.

I just finished some code that rounds all the corners in the world geometry and it makes it looks way better than it did before! In the image below an area is seen at some distance, and you can see some coins, some springs, some spikes and some enemies. The models are all simple placeholders for now.

I'll continue documenting the progress of EaS here, so stay tuned. For some info on the very early development when the game was still sprite-based and developed in Delphi Pascal, see this page on my website.

Field Report from GDC 2010

2010-03-14T01:13:00.003+01:00

I've been spending the last week in San Francisco attending the Game Developers Conference and showing off Unity at our awesome (and very busy) booth.

Booth Experiences

The people I've met have been very excited about Unity; both our product in general and about the new features we'll be releasing in upcoming Unity 3 this summer and which we previewed at the booth. Unlike last year, there were practically no people this year who hadn't heard about Unity some way or another.

IGF Impressions

The Independent Games Festival awards show was great. I was especially excited about Danish guys Playdead winning no less than two awards for their game Limbo and other Danish guys Press Play winning an award for their Unity game Max & the Magic Marker for Wii, PC, and Mac. I've had a chance to play both, and they're both excellent games. Coincidentally they're both side-scrolling platform games with a strong puzzle focus, but besides that they're completely different.

Animation Insights

I only got to see one session this year - Player Movement and Animation in Drake's Fortune 1 and 2. It was very well presented. Everything was sensible and easy to understand; there was nothing ground-breaking but a lot of useful tips and tricks. With the exception of one thing that was purely done to save memory (flipping animations on the left-right axis), everything they did could be done in Unity without problems. They basically rely on lots of animation blending, some of the animations applying to only part of the skeleton, and some animations being additive; all things that are supported in Unity. They also do some IK fixes, which of course can be done in Unity with scripting.

Their method for making characters standing and moving correctly on uneven surfaces is a little similar to how my Locomotion System does it, just a bit simpler: They too use raycasts to find the ground height for the feet, then adjust the hip/root height, and then use IK to adjust the legs.

The most interesting thing they did was having a few long animations with random wiggling of the character. By applying this on top of a 1-frame idle animation they get a nice long, varied idle animation, but it means they can have lots of different idle animations that are all just 1 frame long which turn into nice animations when the wiggly-animation is applied on top. They do similar things with walking and running to add variation that can span over a long time but doesn't require much space because it can be reused for many different animations. Perhaps we can add something like that for our new Unity 3 launch demo that we're working on.

Going Home

It's been a long and hard, awesome week, and I've met lots of great people, but now I also look forward to going home again. I'll be arriving back in Copenhagen on Monday, and once I've recharged a little I'll be continuing working on getting Unity 3 out.

3rd Person Shooter Unity Demo

2010-02-11T21:47:00.003+01:00

At work I've been working on a Unity demo to demonstrate various animation techniques, and I ended up making it into an actual game (albeit a small one). You can read more about it - and play it! - here:

New Character Animation / 3rd Person Shooter Demo

It's based on a tech demo that Paulius Liekis and I did for a presentation at Unite '09. You can see a video of the presentation here:

Character Animation Tips & Tricks