Rune Skovbo Johansen
Creative Programmer & Designer
runevision
Menu

The Cluster

The Cluster is a 2.5D exploration platformer set in a procedurally generated world. The world is the same every time you play, and the same for everyone, just as if it had been manually designed. However, it's also endless and is generated (deterministically) on the fly as you explore.

The project is currently on hold while I work on other projects. It has been under development on and off between 2005 and 2016, starting with a 2D game Cavex made in Delphi Pascal and reinvented multiple times. As such it's been the longest running project I've worked on.

Development of The Cluster put on hold

Sep 6 2016
The Cluster is an exploration platformer game I've been developing in my spare time for some time. You can see all posts about it here.

As of the time being, I've put development of The Cluster on hold indefinitely.

Burdens

After having worked on the game for more than ten years (!) I finally came to the conclusion that the overall design and constraints in the game is making it very hard for me to finish it, while also holding me back from trying out a lot of otherwise interesting ideas.
  • The game is procedural and the same every time you play, which makes it super important to guarantee you can't get stuck.
  • There is gravity and no ability to fly, which means you will get stuck unless the algorithms are carefully designed to make it impossible. It has to be more or less mathematically provable.
  • The AI enemies can follow you practically everywhere, which means every obstacle needs to be coded to also be usable by AI.
  • The world is constructed from a rather large-scale grid which makes things like large ramps and hills impossible (just a bit boring).
  • The third-person perspective require art and animation resources for avatar and enemies.
  • The side-scrolling format makes it hard to wordlessly attract the player to interesting things in the far distance, because only the immediate environment can be seen. This creates more of a reliance on maps and narratives to explain the reasoning for seeking out those far away things, and that plays against the procedural nature of the game.
Now, none of those things are impossible to overcome, and I did have a playable demo at the end of 2015 that worked under all of those constraints. But the game is not yet nearly varied enough, and every new feature is very tough to pull off under the burden of all those constraints.

Focusing on my strengths

I've switched focus to working on projects that I hope both play more to my strengths, and should be possible to pull off in a shorter time frame.
  • First-person perspective without jumping, so no fiddly physics.
  • No humanoid characters, which decreases the demands for art, animation and "behaviors".
  • No ambition of a story (some of my favorite games don't have one anyway).
This frees me up to focus more exclusively on making interesting environments, which is what I'm most passionate about.

The good news is that the time has not been entirely wasted. For one, I've learned a LOT. And for another I've developed several pieces of substantive tech that are fully reusable in my future projects.

Speaking of future projects, I'm working on a few already.

One is The Big Forest, though I'm not actively working on it right now. The focus here is to create nice, interesting and varied environments with very simple gameplay on top. I want it to me my own favorite walking simulator. In its current early stage it's already one of the best virtual forest experiences I've had.

The project I'm actively working on is a VR game for Vive that I've tweeted a little bit about and will soon announce properly here on the blog.
Stay tuned!

The Cluster 2015 Retrospective

Dec 22 2015
The Cluster is an exploration game I've been developing in my spare time for some time. You can see all posts about it here. It looks like I didn't write any posts about it for all of 2015, yet I've been far from idle.

By the end of 2014 I had done some ground work for fleshing out the structure of the world regions, but the game still didn't provide visible purpose and direction for the player.

My goal for 2015 was to get The Cluster in a state where it worked as a real game and I could hand it over to people to play it without needing instructions from me. Did The Cluster reach this goal in 2015? Yes and no.
I made a big to-do list with all the items needed to be done for this to work. (As always, the list was revised continuously.) I did manage to implement all these things so that the game in theory should be meaningfully playable. I consider that in itself a success and big milestone.

However, I performed a few play tests in the fall, and it revealed some issues. This was not really unexpected. I've developed games and play tested them before, and it always reveals issues and shows that things that were designed to be clearly understandable are not necessarily so. I don't consider this a failure as such - when I decided on my goal for 2015 I didn't make room for extensive iteration based on play test findings. I did manage to address some of the issues already - others will need to be addressed in 2016.

On the plus side, several players I had playing the game had a good time with it once they got into it with a little bit of help from me. In two instances they continued playing for much longer than I would have expected, and in one instance a play-tester completed clearing an entire region, which takes several hours. I think only a minority of players can get that engaged with the game in its current state, but it was still highly encouraging to see.

Essentials

Some boring but important stuff just had to be done. A main menu. A pause menu. Fading to black during loading and showing a progress bar. (I found out that estimating progress for procedural generation can be surprisingly tricky and involved. I now have a lot more understanding for unreliable progress bars in general.) Also, upgrading to Unity 5 and fixing some shaders etc.

Enemy combat

I had AI path-finding working long ago, but never wrapped up the AIs into fully functional enemies. In 2015 I implemented enemy bases in the world to give the enemies a place to spawn from and patrol around.
Enemy combat also entailed implementing health systems for player and enemies (with time-based healing for the player), implementing player death and reloading of state, and having the enemies be destroyed when the player enters certain safe zones.

For the combat I decided to return to a combat approach I used long ago where both player and enemies can hold only one piece of ammo at a time (a firestone). Once thrown, player or enemies have to look for a new firestone to pick up before they can attack again. This facilitates a gameplay alternating between attacking and evading. I noticed that the game Feist uses a similar approach (though the old version of my game that used this approach is much older than Feist).
I decided to begin to use behaviour trees for the high-level control of enemies. This included patrolling between points by default, spotting the player on sight, pursuing the player, but look for firestones on the ground to use as ammo if not already carrying one. Then returning to patrolling if having lost sight of the player for too long. Even AI logic as simple as this turned out to have quite some complexities and edge cases to handle.

Conveying the world structure

The other big task on my list after enemy combat was making the world structure comprehensible and functional to the player.

Worlds in The Cluster are divided into large regions. One region has a central village and multiple shrines. All of those function as safe zones that instantly destroys enemies when entered and saves the progress. In addition, a region has multiple artefact locations that are initially unknown and must be found and activated by the player. This basic structure was already in place by the end of 2014, but not yet communicated to the player in any way.

I've done my share of game design but I'm still not super experienced as a game designer. It took a lot of pondering and iteration to figure out how to effectively communicate everything that's needed to the player, and even then it's still far from perfect. In the end I've used several different ways to communicate the world structure that work in conjunction:
  • Supporting it through the game mechanics.
  • In-world as part of how the world looks.
  • In meta communication, such as a map screen.
  • Through text explanations / dialogue.

Supporting world structure through game mechanics

There are a number of game mechanics that are designed to support the world structure.

The artefacts that are hidden around the region can be discovered by chance by exploring randomly, but this can take quite a while and requires self-direction and determination that not all players have. To provide more of a direction, I introduced a mechanic that the shrines can reveal the approximate location of the nearest undiscovered artefact. This gives the player a smaller area to go towards and then search within.
In order to sustain most of the mystery for as long as possible, a new approximate artefact location can't be revealed until the existing one has been found. This also helps giving the player a single clear goal, they are still free to explore elsewhere if desired.

Once an artefact is found, a shortcut in the form of a travel tube can be used to quickly get back to a more central place in the region. Initially the tube exit would be close to a shrine, but the player might subsequently miss the shrine and be aimless about where to go next. Based on early play tests, I changed the tubes to lead directly back to a shrine. This way the player can immediately choose to have a new approximate artefact location revealed.

World structure communicated in-world

I got the idea to create in-world road signs that point towards nearby locations in the region, such as the village and the various shrines. This both concretely provides directions for the player and increases immersion.

Particularly for a procedurally generated world, the signage can also help reinforce the notion that there is structure and reason to the world as opposed to it being entirely random as can be a preconception about procedurally generated worlds.
This entailed generating names for the locations and figuring out which structures to store them in. The signs can point to locations which are far outside the range of the world that is currently loaded at the max planning level. As such, the names of locations need to be generated as part of the overall region planning rather than as part of the more detailed but shorter range planning of individual places.

Next, I needed to make key locations look their part. I'm not a modeller, but I created some simple placeholder models and structures which at least can give the idea of a village and shrines.

Improved map screen

I had created a detailed map for the game long ago, but that didn't effectively communicate the larger overall structure of a region.

To remedy this I created a new map that shows the region structure. I've gone a bit back and forth between how the two maps integrate, but eventually I've concluded that combining them in one view produces too much confusing simultaneous information, so they are now mostly separate, with the map screen transitioning between the two as the player zooms in or out.

Here's examples of the detail-map and the region-map:
Apart from the map itself, I also added icons to the map to indicate the various locations as well as the position of the player. Certain locations in the game can be known but not yet discovered. This mean the approximate location is known but not the exact position. These locations are marked with a question-mark in the icon and a dotted circle around it to indicate the area in which to search for the location.
Part of the work was also to keep track of discovered locations in the save system.

Dialogue system

Communicating structure and purpose through in-world signage and the map screen was not sufficient, so I started implementing a dialogue system in order to let characters in the game be able to explain things.
This too proved to be quite involved. Besides the system to just display text on screen in a nice way, there also needed to be a whole supporting system for controlling which dialogues should be shown where, depending on which kind of world state.

This can be complex enough for a manually designed game. For a procedural game, it's an additional concern how to design the code to place one-off dialogue triggers in among procedural algorithms that are used to generate hundreds of different places, without the code becoming cluttered in undesirable ways.

What's next?

I hope to get The Cluster into a state where it's fully playable without any instructions in the first quarter of 2016.

After that I want to expand on the gameplay to make it more engaging and more varied.

As part of that I anticipate that I may need to revert the graphics in the game to a simpler look for a while. I've had a certain satisfaction from developing the gameplay and graphics of the game in parallel, since having something nice to look at is very satisfying to accomplish. However, now that I'll need to ramp up rapid development of more gameplay elements, having to make new gameplay gizmos match the same level of graphics will slow down the iteration process. For that reason I'll probably make the game have more of a prototype look for a while, where I can develop new gameplay with little or no time spent on graphics and looks.

Nevertheless, even with a much simpler look, I still want to retain some level of atmosphere, since one of the things I want to implement is more variety in moods. This is in extension to the game jam project A Study in Composition I worked on this year.

If you are interested in being a play tester for early builds of The Cluster, let me know. I can't say when I will start the next round of play testing, but I'm building up a list of people I can contact once the time is right. Play testing may involve talking and screen-sharing over e.g. Skype since I'll need to be able to observe the play session.

If you want to follow the development of the Cluster you can follow The Cluster on Twitter or follow myself.

Procedural world potentials: The simulation, functional and planning approaches

Oct 10 2015
Procedural generation has gotten a lot more popular since my interest in it started 10 years ago. Today most game developers and even many gamers know what it means in broad terms.

In this piece I want to highlight fundamental differences between three approaches to procedural world generation: The simulation approach, the functional approach and the planning approach. The approaches are not only algorithmically very different but are also suitable for different types of games and gameplay. Here's a breakdown and analysis, with lovingly hand-drawn - err, mouse-drawn - illustrations.

The three approaches

The simulation approach attempts to create an environment by simulating the processes that creates it. Terrain erosion, vegetation distribution based on plants competing over sunlight and nutrients, fluid dynamics, fire propagation and genetic algorithms all fall under this approach. Simulation approaches are not always based on reality. For example cellular automata simulations can be used to create nice cave patterns even though this is not mimicking how caves are formed in reality. The defining trait of simulations is that it's a process with calculation steps that are repeated many times in order to reach the end result.
The functional approach deals only with the desired end result and attempts to approximate it directly with a mathematical function. For height field based terrain, this could be using a Perlin Noise function, a fractal function, or any combination of many different functions to determine the height for a given coordinate. Similar functions (but for 3D coordinates) can be used for voxel terrain. For vegetation, mathematical functions can be used to determine the probabilities for various types of plants to appear at a given spot.
The planning approach doesn't primarily try to mimic nature at all, but instead plans out an area according to level design principles. For a terrain it might create a mountain range that can only be passed in a specific spot, or it could carve out a cave which contains a key inside that unlocks a vital door elsewhere. For vegetation it might create dense trees that block the player from taking an unwanted shortcut, or it might place plants and flowers in specific spots to try to create a certain emotion or feel related to that spot.
We'll get back to the planning approach in a bit. For now, let's compare the simulation and functional approaches.

Context or no context

An important distinction of the functional approach is that the value at a given coordinate can be evaluated without regard for neighboring points. This is both a strength and a weakness.

The strength is that the generation is simpler and that it can more easily be divided up into smaller parts that don't rely on each other. No arrays need to be used for the generation except to store the end result and this means lower memory requirements.

For games with a pseudo-infinite world, such as Minecraft and No Man's Sky, the lack of dependencies on neighboring points (at least for terrain generation) is important. Since the world is generated in chunks on the fly, a point may need to be evaluated without the neighboring points being available yet, because they are in a different chunk that doesn't exist at this point in time.
The weakness of the functional approach is that certain things can just not be calculated meaningfully without context. For example, consider a river that flows from a source and downwards wherever the terrain goes down the steepest. Given a mathematical function that defines a terrain, it's not generally possible to determine where the river would flow without considering the terrain at many different points at once. Similarly, it's not possible to calculate how light and shadow propagates in a space without having the context of the surrounding geometry available.

There are ways to get around these limitations by mixing functional techniques with simulation techniques. Once a pass of functional calculations have run, a different pass of simulation can run on top, which has does context information. For game worlds that are not generated all at once - and that includes all pseudo-infinite worlds - this has to be handled very carefully to work correctly.

One example is calculation of lighting in Minecraft. The terrain is calculated fully functionally (with user-created modifications on top). After that, the lighting is simulated with proper context information about the terrain. However, the fact that the lighting simulation needs context means that lighting near the edge of a chunk needs terrain data from the neighboring chunk in order to be simulated. How far out can a change in geometry affect the lighting? 2 blocks? 10 blocks? 100 blocks? This, along with the block size of chunks, affects how many neighboring chunks must have been "geometry calculated" before a given chunk can be "lighting simulated".

It just so happens that chunks in Minecraft are 16x16 (vertically they take up the entire world height), while lighting propagates only 15 blocks. This conveniently means that only the 8 neighboring chunks need to be geometry calculated in order for sufficient lighting context to be available for a chunk. This is very likely not to be a coincidence. Having light propagate further than the size of one chunk would have had large negative consequences for the performance.
(Disclaimer: My explanation of lighting in Minecraft is based on a few facts combined with speculation on my part. I can't guarantee it actually works the way I describe but it's entirely conceivable.)

Other types of simulation can not as easily be limited to a specific range. One option here is to just ignore the simulation for chunks or parts of the world that haven't been generated yet, and just simulates the best they can with the information generated so far. Maybe a river only begins flowing once the player gets close enough to its source that the chunk containing the source is generated, and that's okay. But for other games where any rivers present should appear to have always been there and not just suddenly begin flowing based on player location, it can be a tricky or impossible problem to solve.

Topology and traversability

Consider for a moment a game with a player character that can not dig holes or build structures (except maybe at very specific spots). It could be Zelda, Grand Theft Auto, Mario, Half-Life, Metroid or really most other games. What would it mean if there was a hole too deep to jump out of? A gap too wide to jump over? Or a tall wall with a vital objective on the other side but no way to get past it? Basically you would be stuck. It would be game breaking.
Games like Minecraft would have tons of these stuck situations if it wasn't for the ability to dig and build. But in the majority of games - games where the player can generally not modify the environment much - the level design needs to guarantee that you won't get physically stuck with no means to progress.

These games need to guarantee that the topology is such that it can be traversed by the player, so that all locations can be reached that needs to be reached.

Here's the kicker: Neither the simulation nor the functional approach can make such guarantees. (Well except in boring cases; for example if the world is so flat and without obstructions that the player can go in any direction at any time.)

Let's say we uneven terrain with caves. The simulation and functional approaches can easily be used to create interesting terrain of this type, but very little can be guaranteed about it. Maybe it creates some cliffs, but you don't know if you can get to the top, or if it's too steep all the way around. Or maybe it creates a cave underground, but you don't actually know if it's connected to the surface or not.
For the functional approach, this is because it evaluates every point without context - and topology cannot be determined without context. Again, the exception is terrain where it's trivial to get to any point, but that's not useful for directed, non-sandbox gameplay. The point is that it's virtually impossible to create a mathematical function that creates interesting level/world design where it's non-trivial to reach a given goal location, yet still guaranteed to be possible. Maybe it's doable - and if so that would be highly interesting - but I've yet to have seen it pulled off in practice.

For the simulation approach, the context is usually available, but simulation is not concerned with making guarantees about topology or traversability, just like there are no such guarantees in nature. If a simulation algorithm did make such guarantees, it would really at least partially be a planning algorithm instead.

The planning approach then is the one that can make these guarantees. In fact, much of the planning in planning algorithms is typically centered around ensuring such guarantees.

If you have read articles describing procedural generation for rogue-like games, they typically describe how multiple rooms are placed on the map, and an algorithm ensures that they are all connected with passages. Maybe certain rooms are guaranteed to only be reachable via one passage. More advanced ones may have keys for locked doors, and need to ensure that a key for a locked door is not placed behind the locked door, and similar.
Most games with planning algorithms take place in sequences of maps with limited size, which each are generated all at once. It's trickier, though absolutely possible, to use the planning approach on pseudo-infinite worlds generated on the fly in chunks. It typically requires planning at several scopes, with a large-scale planning algorithm handling the overall design of the world. This algorithm can then delegate responsibility of the more fine grained planning to algorithms creating the individual chunks. Often, each chunk is given certain criteria it must meet in order to fit into the overall plan. There can be an arbitrary number of such layers of responsibility.

I'm not aware of any shipped games that are pseudo-infinite and use the planning approach - let me know if you do! My own game in development, The Cluster, uses this approach, and I write about various aspects of the generation and design on my blog.

Generation approaches and effects on gameplay

We have discussed how the simulation and functional generation approaches cannot make guarantees about topology and traversability. What this means is that they are essentially mostly suited for games with sandbox gameplay, for example where the player can dig and/or builds anywhere in order to make non-traversable environments traversable. Often these games also don't have any specific locations that must be reached, with the goals being loosely defined or completely absent.

More traditional "directed" games have carefully constructed level design that can be traversed without freely modifying the environment. For these games certain guarantees must be made. For this to be done procedurally, a planning approach must be used.

We have also discussed the implications for pseudo-infinite games that are generated in chunks on the fly. For these games the functional approach has very advantageous properties in that it doesn't require context. The simulation approach can be used only to a very limited extent, while the planning approach can be used fine, but needs very careful division of responsibility between different generation algorithms at different layers of scope or abstraction.

Mixing and matching

While a procedural game typically has one approach that dominates its generation strategy, there's no problem in mixing and matching the different approaches. For example, a game might use a planning approach for the overall level design, use a bit of simulation to enhance aesthetic properties of the terrain that doesn't affect traversability, and then use a functional approach to place vegetation.
The dominating approach could be said to be the one that affects gameplay the most, and specifically determines how the player can move around in the world and achieve objectives. For anything that doesn't affect gameplay directly, or only in aesthetic ways, the choice of approach is more of an open question.

I hope this article has been helpful in giving insight into various approaches to use for procedural world generation, either for analyzing other games or for use in designing your own. If you have great examples of games using the various approaches to good effect, let me know!

The Cluster 2014 Retrospective

Dec 18 2014
The development of my exploration game The Cluster, that I'm creating in my spare time, marches ever onwards, and 2014 saw some nice improvements to it. Let's have a look back in the form of embedded tweets from throughout the year with added explanations.

Worlds and world structure

During the end of 2013 I had implemented the concept of huge worlds in the game, and I spent a good part of 2014 beginning to add more structure and purpose to these worlds.

Each world is divided into regions with pathways connecting artefacts, connections to neighbor regions, and the region hub. I used a minimum spanning tree algorithm to find a nice way to determine nicely balanced connections, and tweaking the weights used for the connections to change the overall feel of the structure is always fun.

New name

In the early 2D iteration of my game, it was called Cavex, because it had caves and weird spelling was the thing to do to make names unique. Then since 2010 I used the code name EaS after the still undisclosed names of the protagonists, E. and S. This year I decided to name the game The Cluster as a reference to the place where the game takes place.

Spherical atmosphere

The game takes place on large (though not planet-sized) floating worlds. Skyboxes with fixed sky gradients don't fit well with this, but finding a good alternative is tricky. I finally managed to produce shaders that create the effect of spherical fog (and atmosphere is like very thin fog), which elegantly solved the problem.

The atmosphere now looks correct (meaning nice, not physically correct) both when inside and when moving outside of it. The shader was a combination of existing work from the community and some extensive tweaks and changes by myself. I've posted my spherical fog shader here.

Integrating large world structures with terrain

The game world in The Cluster is consists of a large grid of areas, though you wouldn't be able to tell where the cell borders are because it's completely seamless. Still, the background hills used to be controlled by each area individually based solely on whether each of the four corners where inside or outside of the ground. I changed this to be more tightly integrated with the overall shape of the world and some large-scale noise functions. The new overall shapes of the hills have greater variety and also fit the shape of the world better. I also re-enabled features of the terrain I had implemented years ago but which had gotten lost in some refactoring at some point. Namely, I have perturbation functions that take a regular smooth noise function and makes it more blocky. I prefer this embracing of block shapes over the smooth but pixelated look of e.g. Minecraft.

Tubes

As part of creating more structure in the regions, I realized the need to reduce boring backtracking after having reached a remote goal. I implemented tubes that can quickly transport the player back. I may use them for other purposes too. Unlike tubes (pipes) in Mario, these tubes are 100% connected in-world, so are not just magic teleports in tube form. Wheee!

What's next?

It's not a secret that most aspects of The Cluster gameplay are only loosely defined despite all good advise of making sure to "find the fun" as early as possible. Being able to ignore sound advice is one of the benefits of a spare time project!

However, after the ground work for fleshing out the structure of the world regions this year, I've gotten some more concrete ideas for how the core of the game is going to function. I won't reveal more here, but stay tuned!

The Cluster

Sep 13 2014
The game I'm working on has a new name: The Cluster

Screenshot with title.
This replaces the previous working title "EaS". The full final name is likely going to be something along the lines of "Explorers of The Cluster", "Adventurers of The Cluster", "Enigmas of The Cluster" or similar, but I haven't decided on that yet. "The Cluster" is the defining part, and would be the recurring part if there should ever be more than one game in the series.

(For the sake of coherence I've retroactively updated past blog posts to use the new name.)

This post is about The Cluster, 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 The Cluster here.

Debug your procedural world generation much easier with this one simple trick

Sep 6 2014
This post is about The Cluster, 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 The Cluster here.

Okay cheesy title aside, this trick really did make debugging much easier for me, though the trick really is also very basic in retrospect. But it took me years to realize this, so maybe it will help somebody else too.

TLDR; freeze the generation at the exact point you encounter an error, but let the game continue running so you can inspect the frozen generation state with full visual context, turning various in-game debug visualizations on and off, and moving the camera around as needed.

A problem I've had for a long time is that errors in the procedural generation of my game can be hard to debug. The game have many sub-systems dependent on each other. When the player approaches an area that hasn't yet been generated, it will be generated by the various sub-systems on the fly with the various dependencies respected. Terrain info needs to be generated before path-finding info for instance.

The complexity of the dependency relations can make it hard to keep track of exactly how something went wrong, and whether an issue was caused by a bug in generation code itself, or a bug in the dependencies code that meant some needed information wasn't yet available.

Add to that the challenge that many of the generation algorithms modify data in several passes, and just looking at a visualization of the data at the end of the generation may not be sufficient to see how the data was wrong at some step in the middle of the process.

The normal way to inspect data in the middle of a process is by using breakpoints. But breakpoints only let you inspect data in your text/debugging IDE as numbers, and data for procedural generation is often incomprehensible at that low of an abstraction level. The custom-made visual debugging tools are really needed, but they can't be enabled and manipulated while the entire game is paused. And according to StackOverflow, individual threads can't be paused selectively.

Generation breakpoint triggered and visual debugging used to inspect the state.

For the trick to work, your procedural generation needs to fulfill these criteria
  • The generation should not happen on the main thread where the game loop and logic runs. This means you need to perform the procedural generation in one or more threads dedicated to that. This is pretty much needed anyway if your game generates new parts of the world on the fly without pausing the play. In my game I run all the generation in just one thread.
  • Make your life simpler by making it easy to switch various debug visualizations on and off at any point while running the game.
  • Obviously, have places in your code (such as asserts) where you check if what you take for granted is true and print a helpful error otherwise with as much info about the problem as possible. In addition to messages that are just printed in the console, I also have positional logging which shows up in the game world at a specific 3D position if the relevant debug visualization is enabled.
 The trick is to implement your own breakpoints that pause the generation thread. I did it like this:

Whereever I have detected a problem that I want to pause the game, I just call

 Debugging.GenerationBreakpoint();

In the Debugging class I have this code:

 static bool waitForBreakpoints = false;
static bool breakpointPaused = false;

public static void GenerationBreakpoint () {
if (!waitForBreakpoints)
return;

breakpointPaused = true;
while (breakpointPaused)
System.Threading.Thread.Sleep (5);
}

I then have some debugging UI with a setting to turn waitForBreakpoints on and off, and a Resume button that is only shown when BreakpointPaused is true, and which sets it to false again when clicked.

That's it!

Layer-Based Procedural Generation

Sep 22 2013
One of the problems you'll face when creating an infinite procedurally generated world is that your procedural algorithm is not completely context-free: For example, some block might need to know about neighboring blocks.

To use graphics processing as an example, you might have an initial noise function which is completely context-free, but very often an interesting procedural generation algorithm will also involve a blur filter, or something else where the local result depends on the neighboring data. But since you only have a part of the world loaded/generated at a time, what do you do at the boundaries of the loaded area? The neighboring pixels or data isn't available there since it isn't loaded/generated yet. The layer-based approach I describe in this post and video is a way to address this issue.

I hinted at this layer-based approach in the overview post Technologies in my Procedural Game The Cluster. I have also written a post Rolling Grids for Infinite Worlds with the source code for the RollingGrid class I use for achieving practically infinite grids; only bounded by the Int32 min and max values.

I use two different layer-based approaches in The Cluster: Encapsulated layers and internal layers.

Encapsulated layers are the most flexible and what I've been using the most. Encapsulated layers can depend on other encapsulated layers, but don't know about their implementation details, and different encapsulated layers can use completely different sizes for the chunks that are loaded. I might go more in details with this some other time.

Recently I implemented the simpler internal layers. Internal layers are tightly coupled. They share the same grid, but chunks in the grid can be loaded up to different layer levels. I explain this in more detail in this video below.


That's it for now. You can read all the posts about The Cluster here.

Rolling Grids for Infinite Worlds

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

Originally, my procedural game The Cluster (you can read all the posts about The Cluster 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 The Cluster 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 The Cluster

Feb 17 2013
This post is about The Cluster, 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 The Cluster here.

In this post I'm creating an overview of the different technical aspects of The Cluster 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 The Cluster 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.

    Terrain Generation

    The terrain in The Cluster 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.

    AI / Path-finding

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

    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

          The Cluster 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.

          Layers of Infinite Grids

          Originally, The Cluster 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.

          Debug Options

          With a game as complex as The Cluster 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.

            Generating a tree structure from a maze

            May 15 2012
            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 The Cluster 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 Cluster game...

            Apr 23 2012
            Though I haven't posted about it for the good part of a year, I haven't dropped my game The Cluster. 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...

            Forcing Structure in Procedural Spaces

            Aug 21 2011
            The procedural game I'm working on in my spare time, The Cluster, 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 The Cluster, my 2.5D platform game under development with focus on non-linear exploration. (You can read all the posts about The Cluster 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 The Cluster.

            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:
            1. 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.
            2. To give the player a sense of reward when a new part of the world is unlocked.
            3. 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:
            1. Corridors - which act as natural choke points at each end, and cover if you are in them
            2. Convex shapes - spaces where you can see everything in the space from everywhere else
            3. Concave shapes - spaces where some space is hidden from another (more cover)
            4. 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.

            The Cluster: Video of New Environments

            Aug 15 2011
            This post is about The Cluster, 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 The Cluster here.

            In the last post I wrote about how I've improved the edges in the environment generation of The Cluster. 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.

            The Cluster: Sweet Sweet Edges

            May 29 2011
            This post is about The Cluster, 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 The Cluster here.

            Last time I posted an update about The Cluster 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:

            View image

            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.

            View image

            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.

            View image

            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 The Cluster (don't mind those ugly green box stepping platforms and spikes. They're placeholders I haven't yet replaced with something better):

            View image

            View image

            View image

            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!

            View image

            Unity's ScriptableObject and Threading

            May 20 2011
            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. :)

            The Cluster: Demo of Hunting AI and New Models

            Aug 11 2010
            This post is about The Cluster, 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 The Cluster here.

            Like I wrote about a few weeks ago I've been working on pathfinding and AI for the enemies in The Cluster. 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!

            The Cluster: Demo of Procedural Environment

            Aug 8 2010
            This post is about The Cluster, 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 The Cluster here.

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

            The entire world in The Cluster 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 The Cluster in coming blog posts.

            The Cluster: Agile Enemies in a Platform Game?

            Jul 29 2010
            This post is about The Cluster, 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 The Cluster here.

            I've been working on implementing path-finding for The Cluster, 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 The Cluster

            Jun 14 2010
            This post is about The Cluster, 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 The Cluster here.

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

            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.

            View image

            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.

            View image

            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.

            View image

            I'll continue documenting the progress of The Cluster 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.