• entries
19
27
• views
11716

It's not the 'Journal' that's big - but the game  This blog is for detailing my slow progress towards making a Big Procedural Game.

## Planet Generation Plans

Hey all! This time I'm going to write a little about my plans for generating planets. This entry won’t go into any specific details of the terrain generation but will be just a very high level overview of the basic framework. I don't think any of the ideas in here are new.. the procedural generation community are a very clever bunch indeed! I'm always amazed how when an idea pops into my head I'm able to find an existing article about it that goes into fine detail on the subject. Anyway let's crack on! Heightmaps & Voxels When it comes to generating terrain an easy first choice is to generate height maps and build the terrain mesh from that. You can get some good looking results quickly by overlaying some noise generation and tweaking things here and there. Though these can give some nice results they have limitations. For example tunnels and overhanging terrain can’t be represented in a simple height map. You also have to choose a projection scheme to map a 2D height map onto a sphere. There’s another approach to terrain generation using voxels and that’s what I’m aiming to use. With voxels you can define all sorts of complex terrain and you can define what’s hiding under the ground too - whether it's seams of coal, ore or underground rivers. Many games use voxel terrains to great effect such as the infamous Minecraft. Sign me up! In Minecraft the voxels are arranged in a grid, keeping everything nice and simple.. until you want to model a whole planet. Then you’d get something like this: Though that does look really cool, I don’t want my worlds to be great big cubes floating in space, so what do I do? There are all sorts of solutions to building a spherical world from a voxel grid, but they seem to be full of difficult space warping, caveats and rendering complications. I’d rather not deal with these kinds of complications, so I’m going to try a different approach. Instead of arranging the voxels in a grid I’m planning to arrange them as points on a geodesic sphere like this (imagine the vertices are voxel points): It’s like taking the space warping issues you’d need to do at the cubes edges and spreading it evenly across the entire surface of the sphere. Instead of it becoming a difficult edge case it becomes a constant low level annoyance and keeps things consistent at all times. It will make the mesh generation a little more fun later too Voxel Planet Generation The plan is to use an icosahedron as a starting point. Each vertex here is a voxel. This can be considered the lowest possible Level Of Detail (LOD) of a planet.
The space is chopped up into tetrahedrons from the planet surface into its core. There is an extra vertex at the centre of the planet for this. These tetrahedrons can be subdivided through to the core of the planet as required. These illustrations are somewhat misleading though as this isn’t just generating a spherical mesh, but a bunch of voxels that could be empty space. The voxel points (vertices) hold information about what's actually in the space they occupy, whether it’s atmosphere, rock, magma etc. It is the job of the terrain generator to define what a voxel contains. I'm going to keep a clear divide between the planet voxel generation code and the terrain generation code this way. I have some uncertainties on how to best manage the subdivisions of the planets voxels as required, but I’ll bash it out in a prototype. Dynamic Changes The game also needs to be able to make permanent changes to the terrain during play. Large explosions should create craters and I want them to persist. To do this I will need to be address the voxels and save state changes about them. I'm not 100% sure on the approach for this yet either. One train of thought is to basically create an algorithm for the voxel generation that that is able to assign each possibly generated vertex a unique 64bit number. That would have no waste and allow the maximum number of voxels, and some napkin math makes me believe it would have good detail on earth sized planets. Another approach could be some kind of hash of their XYZ or polar coordinates, though that will be more wasteful so it’d bring the total addressable voxels way below what a 64bit unique id could theoretically hold. Ok that’s enough for now!

## Random Progress - May 2018

I've being progressing a few random things. Generators That Don't Make Models  First up I added a JSON visualiser so I can browse the output of generators that don't create 3D models. There will be plenty of these kicking about. I'm using JSONViewer by Roman Makudera to do this for now. In the future I may roll my own version though that can have knowledge about unit types. For example, in the image above "age" is in years, and the height values would be in metres. That kind of information is lost with the current viewer. Height Map I've also started playing with generating a height map. I'm not planning on doing any terrain work with height maps but I just wanted to see how easy it was to do in ThreeJS. Below is a totally random terrain with random vertex colouring. It was quite straight forward to setup - nice one ThreeJS Voxels I want to build my actual terrain using voxels so I can get more realistic results. It's a lot more complicated but it'll be worth it. Above is simply a cube space filled randomly with voxels. I'm not doing anything clever in the rendering yet for generating the mesh. Each voxel is it's own ThreeJS cube. Ultimately the terrain is going to be more like no mans sky than minecraft - that is it's represented with voxel data but the mesh generation won't render it all with just cubes. Next I'm going to continue playing with the terrain generation using voxels, so I'll likely implemented some 3D noise generators. I have a bunch of terrain generation articles bookmarked from over the years so it'll be loads of fun to finally play with making some of my own

## Debug Text

Having decent tools to debug the generators is crucial. One of the tools I always like to have is lots of debug rendering features. Putting debug text in the world is a big part of that, so I need ThreeJS to do that for me. ThreeJS has some nice stuff built in but I don't want to add dependencies on font files. My typical workflow right now is loading my generator test bed HTML file from explorer straight into Chrome. Chrome isn't a big fan of loading stuff like fonts from local file storage unless you load chrome with a particular command line argument which is not suited to how I'm working. So to keep it simple no fonts please. So I decided to just make a simple 'font' defined as line segments and put together a helper to add debug text to the world using ThreeJS LineSegments geometry. And I kinda like the way it looks Bonus: Note that the £ is missing here. That's because of an awkward HTML character encoding issue. I need to tell Chrome about the encoding of my JS files. I'll get around to that soon!

## Generator Testbed V6 Video

This video is showing early work on my procedural generation test bed. Everything is in javascript using ThreeJS and ThreeCSG. 0:00 - Starts with a cube generator and overriding its input parameters to change it's size. 0:12 - Showing a geometry subtraction test. This uses ThreeCSG. 0:20 - A tiled floor generator. 0:27 - A 'modular' room generator. These would be simple rooms that are made from a standard tile shape - think board games. 0:39 - A stone wall generator that follows a path to build the wall.   I'll try to record progress with these every so often. It's always fun seeing how things progress

## Prototyping In Javascript

I've shifted the project from C++ to JavaScript during this prototyping phase.  I've done this for a few reasons: This makes the project incredibly portable, allowing me to work on it on different devices easily. Prototyping in JavaScript is easy. Threejs is cool and easy to use. I'm a C++ coder at heart and my ultimate goal is for this to be a C++ project. Pragmatically it hasn't been working for me using C++ for my home projects for the last few years. I find myself needing to upgrade projects and libraries, worry about build processes, ensure Visual Studio is installed on the device etc. Now I can now edit generation scripts almost anywhere, anytime, event on my smart phone. Those little moments of downtime can be much more productive I'll take the project to C++ once it has matured - though it will continue to support JavaScript generation scripts so hopefully with a little work I won't have to throw anything away.

## Expanding Earth Theory

A good while ago I stumbled across this video on youtube about a theory that the earth grew in size and the tectonic plates 'float' on top of this expanding sphere.

[media] [/media]

Now despite this being somewhat scientifically questionable it did get me thinking that it might be fun to model a procedurally generated world using this technique. Typical procedural generation techniques using perlin noise or similar often lead to quite random looking continents:

(Apologies if these are your images and you don't like me referencing them!)

This approach can get good results, but it's easy to just get noisy terrains.

Leveraging the 'expanding' earth idea I'm going to build a model for fun where a verlet cloth sits on an expanding sphere. The cloth will become the terrain of the planet and I'll see if I can get it to 'rip' in nice ways as the sphere expands.

One approach I'll try is to randomly assign each of the points on the cloth parameters such as mass or friction, and randomly assign the strength the links have to adjacent points. When the stress on the links reaches a critical point they can 'rip' free. The remaining cloth can be considered land and the rest sea.

Another approach could be to 'inject' cloth into the stress points as the sphere grows, and allow the cloth to exist with a height on top of the sphere, allowing wrinkles as material builds up. Then a sea level can be chosen and the coast lines would be a result of that.

I think it's an interesting idea, I'll post pictures of any results I may come up with. If nothing else perhaps it will give others a new idea to play with too

## Code Status & Geodesic Spheres

This time I'm giving an update on the status of the code itself. It's still early days but at the moment I've been working on mesh generation helper code. The first mesh generation function I have working is for geodesic spheres, a cool piece of geometry!

It's built from an icosahedron as the base which then has each triangle tessellated to the level of required detail. Each new vertex is then projected back on to the surface of the sphere to complete the job. I'm not generating UV coordinates yet, just normals. There are lots of uses for these guys and they have the cool property of evenly distributing surface area across the faces.

[sharedmedia=gallery:images:5534]

The process of creating and rendering this mesh is proving out the renderer and scenegraph behind the scenes which is cool. It's also using my framework for generating and storing meshes. I want this process to be asynchronous in the near future. I'll go into more detail on future posts, but I don't think it's anything particularly new or exciting.

## Scripting Languages

Scripting languages can be a can of worms. I want to make sure I open that can for the right reasons!

I want the code that does any heavy lifting of the generation to be in C++ for performance reasons (and debugging!). I also want the generation steps of objects to have rapid iteration in a forgiving environment, as in without hitting asserts or crashes. My game framework allows this to potentially be in C++ as it supports reloading DLLs on the fly so generation logic could be in DLLs, but it's not what I'd call 'rapid' iteration. Other approaches are runtime CPP compilation, JIT (C#) or byte code scripting language. I'm going to try to not tie myself down to one particular approach if I can help it. Easier said than done though.

I'll probably start with a simple game targeted scripting language such as GameMonkey or Angel Script.

Also aside from scripting the generation having a scripting language hooked up to your engine makes auto testing easier. Having good tests is going to be a life saver in the long run.

I'll put down some sketches of how I imagine the generation process for objects will work and how scripting will help in the near future, with some examples.

## Changing the universe

To make a universe more than just a static diorama things have to change. Time should have an effect, so planets spin and the sun can rise, but more importantly the players actions should have an effect.

If the player gets their hands on a planet destroying super weapon it would be very unsatisfying if they destroy a world to find it magically reappear when they reload, or even just visit the next solar system and come back. These changes need to be saved permanently to the players save data.

I'm planning for save data to be like a patch that is applied over the top of the procedurally generated data. So if you kill someone when it comes to generate their info when it's finished it will stamp 'dead' over the top of their status. It will maybe go on to generate different things off the back of this, maybe give them a grave or something. A planet will be patched with 'exploded' and perhaps an asteroid field will get generated.

This approach will require that the generation algorithms be exactly the same as when the patch data was created. So save games will not survive updates to the game that change these. They will need to be bound to a release version and people should complete their adventures before upgrading, if they want. Not sure if there's an elegant way around that.

## Coordinates & Compressed Space

Having a big universe to play in is going to require some thought into how to locate things.

The Milky Way is 120kly (ish) according to Wikipedia. That's kilo-light years. That sounds big! Ok lets say I want to positiom things with millimetre accuracy. A light year is 9.4605284 x 10^18 millimetres (thanks Google!) So the milky way is approx 1.13526341 x 10^24 millimetres across. 1135263410000000000000000 mm. How many bytes are needed to store a number that big? My calculations put this at 10 bytes. That's a nice chunky number. If we want multiple galaxies or more accuracy we need more bytes too. I'd probably round this up to a lovely 12 bytes.

So I have a super number which can store galaxies to mm precision, except its too big to fit in CPU registers and so all math is horribly complicated and slow. No thanks!

For a game to have a chance of managing this I need to keep the coordinates in a useful form.

There are a few solutions to this problem and I'll outline the one I'm going to try first. I'm going to keep rendering and physics working in lovely floating point numbers. The main reason is that everything is simple when using these, though they lose accuracy pretty quickly. To deal with this I'm going to have reference points evenly distributed across the universe, creating a classic nested coordinate system. All floating point numbers will be local to one of these reference points.

These reference points will have a volume of space defined around them so they overlap the next reference point by 50%. When you move far enough from your ref point the game will switch which point you're anchored too. I need to be careful that these switches dont introduce too much error or performance penalty.

An objects coordinates will be split into a local space floating point position and a reference point ID. The reference points may also need to be put within a nested coordinate space to get extra space, and that can be repeated as many times as necessary.

I'm considering only allowing interactions between objects living in the same reference point, as it will simplify things. We'll see how that plays out.

Finally from a gameplay point of view I'm planning to allow the scale of the generated universe be controllable. I doubt very much that a real size scale for most things will be the default setting. I don't want people dying of old age travelling. I'll aim to reduce how much boring space there is between interesting things without breaking the illusion. This applies to many things, not just the distance between planets. The distance between cities or continents or any feature of interest. Sure people can have 1:1 if they want though! I suspect that space travel will still need FTL drives, stasis pods or wormholes to get around and not die of boredom!

## Narrative Generation Overview

The narrative generation will work within high level constraints placed by the player. Or the Plyer can leave it to be entirely random.

The UI for this will be a page of simple sliders for the highest level of story control, but clicking through into the advanced settings will reveal many ways the player can customise the experience.

Example settings: (not including standard world generation options)
- Approximate narrative duration.. 30mins, 4 hours, 1 month, ongoing etc.
- Force include characters - with character designer.
- Force include species.
- Force include locations.
- Force include plot arc.
- Difficulty preference.
- Action level.
- Mystery level.
- Comedy level.
- Drama level.
- Narrative scope.. Right word? Whether its one town or whole universe.

The system will work on several layers.
On the top is the Narrative Director. It's the only thing that knows the whole story and the intended ending. It's job is to try to keep the story on track and provide the desired levels of suspense or action etc.

Ideally it will do this without affecting a character directly.. It would be easy to let it dabble in the mind of a character but I want it to affect them indirectly. This is because I want to keep the integrity of the characters actions intact. If it wants a character to attack the player they should have a reason provided rather than do it mindlessly. A mercenary is paid, for example, while in a more elaborate scenario the Director could arrange a situation to make a character hate the player. Perhaps the character is lied to or sees the player doing something that incites hate. The director arranges these scenarios.

The characters have their own AI brains. They have their own knowledge of the world and other characters (which may be wrong). They have their own goals to achieve.

Different characters require different kinds of brains. Animals are simple compared to people. To keep things sane a random person in the crowd may run a very simple crowd brain until they interact with the player in a way that requires them to 'upgrade'.Also different characters will run at different speeds.

The story plan is built up by searching a state graph. Nodes are states of the story and edges are actions that can be taken. This is an expensive approach, but I think conceptually simple. It should give me a system that works well, if slowly, and I can improve and optimise it in time.

Heuristics will be employed to trim down the possible actions needing to be searched. Exactly how these will work will be fun figuring out :)

The human player will also get a character. This will try to guess the players mental state and relationship to other characters through their actions. It will then use this proxy in the system like any other character. In theory the plater could let their proxy take over and they will continue to play the game in the same way.

These AI approaches are very expensive. I'll be using level of detail in the system and running things asynchronously to keep things going.

OK that's all for now. This post has mostly been me writing down my thoughts. I'll go into more detail on each part mentioned here as I approach implementation :)

## Languages

This time I going to talk a little about my early plans on incorporating languages into the game.

I want all the text you encounter in the game to mean something, even if it is in a made up alien language. To do this I'm going to generate (somewhat) meaningful sentences that are converted to the alien language. I'm thinking that simply using a generated font may be enough and it allows the player the chance to 'learn' an alien language by recognising which symbols mean which letters. I could take this further though. But having it all make sense underneath allows me to have universal translators or even subtitles on what you're trying to read :) Though I don't think subtitles work well on HMD. Perhaps something more like Word Lens would be cool.

With generating English I think I can pull this off to a hopefully acceptable level but I doubt I'll be able to do the same for other languageslanguages as I just don't know others well enough and the rules for building sentences can be quite involved. My best hope would be to generate in English and then run the result through a translation Api like Google translate.. and keep my fingers crossed! No doubt the results will be hilarious... :p

## Generating Things

A generated 'thing' can be either physical or abstract with no physical form. The personality of a villager or the characteristics of an average member of a species are a couple of examples of the kind of abstract things that can be generated.

All things being generated can have dependencies on other things, either abstract or physical. For example, generating the physical model for a villager depends on his personality traits being generated. If he has a violent personality he may have some scars and carry a knife. If he's an educated man perhaps he has glasses and carried a satchel of books. His generation may also depend on information about where he lives such as his town or kingdom. Perhaps he wears a pin with the kings crest on it etc.

When it comes to depending on these abstract things such as a species or nation I'm imagining that a list of options is generated that can be chosen from. A world will not have infinite nations to pick from, for example, but a limited number. These are generated and cached early on in a list. The generation then randomly picks an index into this list during the process.

A thing may depend on other physical things too. When generating a wheel for a car it will want to know the maximum dimensions of the wheel well or what terrain the car is intended for. Generating a door for an entranceway will need to know the doorway dimensions too etc.

In these cases what is happening is that somethings generation process is triggering the generation of further child things.. So the car generation triggers the generation of wheels. When it does this it provides a list of constraints for the children that they must meet. Maybe think of it as a high level blueprint. A thing can still be generated without constraints, in this case it randomises values within valid ranges for each constraint.

This means that a seed and a constraints list is required to replicate something exactly. This is good and bad. Bad in that more information has to be saved about something to generate it again, but good in that there's lots more than UINT_MAX possibilities for any given object type (if I use unsigned ints to store seeds). Also the constraints for the children are generated from the parents seed so for a hierarchy of things grouped together such as a car only the parents seed and constraints are required to duplicate them all.

I'll give some more examples of these generation hierarchies in the future to illustrate the process and show where the 'thing generator' editor will come in - I also have to come up with a better name than 'thing'!

## Generating Seeds

A seed is a number used to initialise a random number generator. They are important because it allows a generator to give the same sequence of random numbers again. In fact the sequence of numbers generated is typically deterministic, so the seed is a bit like giving it a starting point in this long sequence.

Without a seed you wouldn't be able to have a save game in a procedurally generated world and guarantee it would be the same world when you load it up again. (Unless this game saved all the generated data the first time it made it. But mesh!)

I'm using seeds as part of how I uniquely identify generated objects of a particular type. For example, let's say I'm generating seeds for cars. A car with seed 5 is different to a car with seed 6. Every time I generate car 5 though its identical to every other car 5 (I will be using auto tests to ensure as such). Next I generate planets. If a planet has seed 5 too it's fine, it doesn't matter that it shares a seed with a car. The seed is used to ensure the generation process makes the same result, that's all.

OK, let's say we're generating a solar system and we're making seeds for each planet. We want each solar system to be different so we make random seeds to fill them. If by chance our random number generator produces the same number twice then we'd have two identical planets. Totally identical planets in the same system. Down to the cities and forests and blades of grass. Not cool. Sometimes it's OK if you get the same thing made multiple times in a set, like trees in a forest, but not here.

A naive approach to solve this would be to check a newly produced seed against the set of seeds we've already produced to see if any are the same. If it's a duplicate then we make another. In small lists this may be OK but with larger lists things start to crawl, and even worse it will slow down unpredictably because its random as to when you'll make a new number that's OK.

My plan to deal with this is to use a Linear Feedback Shift Register (LFSR - http://en.wikipedia.org/wiki/Linear_feedback_shift_register). These can be used to create sequences of pseudo random numbers which generate each possible number within a finite range once before repeating. By using this you'll never have repeating planets within the same solar system Its not all perfect though, depending on what you need from it. Also this doesn't solve having the same planet appear many times within a galaxy, or in fact the same sequences of planets in different solar systems. But I'll discuss that more in future post.

## More Detailed Project Overview

I've got a few draft posts in the works but first I thought I should do a more detailed overview of what I'm planning starting with a sort of disclaimer. Everything I write about in this journal needs to be taken with a pinch of salt. Until I show actual screenshots everything I've planned has been a thought experiment! None of my planned approaches may work out, so feedback and criticisms on my posts is very welcome

The Game:
So the game. The premise is sort of simple but the implementation will be a nightmare I guess you can sum it up as the Star Trek Holo Deck. Or Red Dwarfs' 'Better Than Life' if you want to get creeped out

My plan is that it's like a customisable first person adventure game. The subject matter and genre can be anything - war, crime solving, drama, exploration, whatever! I imagine a typical user experience will be selecting rough duration of play, high level game world settings and then clicking Start. The game takes care of everything from then onwards. It will give you a unique seed if you enjoyed that particular adventure and want to share it or play it again.

You can be as detailed about what the adventure contains as you like. Whether it contains horror or comedy. Whether the universe contains magic, fantasy technology or is gritty and realistic. Whether it's set in the early days of civilisation or in the distant future. Whether the adventure is contained within one town or spans an entire galaxy.

I'm really trying to let the scope of this thing fly out of control! My first iterations will be confined and simple but I'm planning a framework that can just grow and grow as I add more to it. As I add new procedural object types or narrative structures they will just start to be used accordingly... and if I get it right and people enjoy the game then hopefully it will be simple enough for people to add their own stuff too!

The narratives and worlds will be procedurally filled according to the starting game settings. It will try to react to the player as they play in order to produce an unique experience and keep the narrative on track.
Ok and one last thing. As this will take a while to complete I'm planning for something that would more than likely cripple current hardware! I'm not letting current constraints hold me back. Everything is going to be horribly expensive resource wise so let's hope everything is super fast by the time I'm done. And that I can afford it

The Engine:
I'm basing this whole thing on my own engine. I think some of the tested frameworks out there like Unity are brilliant and no doubt it would massively speed things up using them but I'm not going to here. I love learning and there is no better learning experience than writing your own engine! Previously I've only done this with the 'game code' but this time I'm going further with rendering and physics too. Not audio though. That's just boring ;p

I'll post details about the engine but in a nutshell it's C++, heavily interfaced and using OpenGL 4+ for rendering. Performance is important as ever but not critical, I just want playable framerates for now. As I'm a one man show I don't have time to really optimise the whole thing. Instead I'm aiming primarily for readability in my code and trying to avoid coding myself into a spaghetti mess.

The engine will be separate to the game - I plan to use it for other projects too. Maintaining an engine/game separation is important to me for architecture reasons and keeping everything 'clean'. As such the game will be a DLL plugin to the engine itself.

Right that's a load of hot air/hype. Next post will have some actual content, promise!

## First!

Hey everyone. This blog will hopefully detail some of me efforts towards making a Big Procedural Game (tm). I'll post random thoughts and ideas on the procedural generation process as well as some of the design decisions I've made in the engine which will power this whole affair.

My ultimate goals are...
- My own engine in C++ which can run on multiple platforms. (I will happily by using 3rd party libs however! So I can't take credit for everything).
- It will target future hardware so I'm thinking big in many areas.
- It will target HMD play just as much as a classic 2d screen.
- The game will procedurally generate 99% of its content.. from graphics to narrative.
- The procedural generation will have high level constraints the players can put on it to tailor the game to their preferences.
..
- Profit?

I have a bunch of stuff written down in notebooks over the years so it will be nice to get it properly written up and illustrated here. I lost notebooks and scraps of paper far too often!

Ok everyone that's it for now :)