RSG: Procedural Environment

From Wikiid
Revision as of 18:56, 23 March 2010 by SteveBaker (Talk | contribs) (Building a Fluid Asteroid Belt)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search


Wikiid Pages relating to RSG)
RSG: Setting/Story
RSG: Size of Universe
RSG: Reference imagery
RSG: No FTL travel
RSG: Networking
RSG: Procedural Environment
RSG: Career paths
RSG: Scripting
RSG: Ship Design
RSG: Ground Installations
RSG: Ship Control
RSG: Graphics
RSG: Communications
RSG: Asteroid types
Edit this template

The idea is to have a large volume of space - full of interesting content - but without us having to model a gazillion things. The solution to that is to use procedural environment generation. Most things 'designed' using random numbers and software.


The game initially starts off in an asteroid belt, as it's the realistic equivalent to having many teeny planets like in Freelancer type games.

If ever more systems are added, then instead of faster than light (FTL) capability, a deep sleep should take it's place.

Filling the Sector with Stuff

Each sector of space is given a number, and everything within is seeded by that unique number, creating a random universe that remains the same between all copies of the game.

Building a Fluid Asteroid Belt

Procedural generation of 'stuff' works best if you have the random number generator 'seeded' with some number that relates to one's location in the universe. However, we want the asteroid belt to be more dynamic - with things moving around within it. The idea is to have fairly large 'blobs' of asteroids that move as a group. Let's suppose each blob is a roughly spherical group of maybe 100 rocks - and maybe it's 100 km across. We're going to have the entire blob orbit at some speed and distance from the star that's a little bit different from the other blobs...maybe it's slowly spinning too. Suppose the entire asteroid belt is made of a million blobs.

Each blob would be numbered uniquely from 1 to 1,000,000. It wouldn't take more than a few seconds to loop through all million blobs - and to generate a set of orbital parameters for each one using a random number generator 'seeded' from the blob's number. At the start of the game, each player's computer would take a few seconds to check all of those million sets of orbital parameters to decide which (say) thousand blobs are close enough to the player to be worth worrying about during (say) the next 20 minutes of top-speed travel through the game. We remember their numbers and forget the other 999,000 of them - so 1,000 blobs of 100 asteroids is 100,000 asteroids - which ought to be enough for 20 minutes of interesting game-play. But all we're storing at this point is a list of 1,000 blob numbers plus their orbital parameters.

Now, we look through those 1,000 blobs to find out which ones we can actually see (either on-screen or with radar or something). Maybe there are a few dozen blobs like that. Once we know where they are (and when they are - because they are moving), we can continually test just a few of the list of the million blobs each frame of the game to see if they are starting to get close enough to be worth paying attention to - and we can also continually monitor the few dozen "close enough" blobs to see if they are no longer close enough to be worth bothering with - and then we can delete all of their data except for the blob number and stop drawing them.

As we find blobs that enter our area of interest, we use the random seed approach again to generate how many asteroids there are, what their coordinates are relative to the center of the blob - then the type, shape, color, texture, etc of each asteroid - and the data for anything else within that blob that matters (wrecked warships full of useful supplies, alien artifacts with weird properties, rare metal deposits, etc).

This gives us a VAST space to explore. 100,000,000 asteroids is more than anyone could explore in a literal lifetime. It's "enough" - by any useful measure!

There are two tricky parts to this. One is that we can modify the world within the game. If there is a valuable alien artifact that happens to appear (at random) in blob #12,345 and we grab it and take it away...what's to stop it being generated again the next time? The trick here is to realize that over the (possibly) millions of random numbers that we generated to build our blob, very few of them are changed by doing this. Moreover, over a million blobs - the percentage that are modified is very tiny. We could have the server create a file on disk for every blob that's been modified.

Now, our client computers generate the list of blob numbers that it cares about - and sends that list to the server - which replies with a much smaller list of modified blobs...and when those blobs come close enough to the player to matter, the client can ask the server for a list of modified, missing and extra "objects" that relate to that blob. So the client computer generates the blob's contents normally at long range asks the server for the "mod-list" for that blob - and when the mod-list arrives, we modify the contents of the blob accordingly. Hopefully, the server responds fast enough that we get the modifications done before the player notices!

As events of the game unfold, the server needs to be told to create these mod-lists for modified blobs - and to periodically save them to disk in case the server crashes or something.

Obviously, in a "persistant world", the number and size of these mod-lists grows - which slowly eats up disk space on the server - but that's the only bad effect - for the players, the number of mod-lists that they care about is limited to the distance they can see in the game. Admittedly, when a heavy amount of game activity has gone on - the local neighbourhood may be seriously trashed with dozens, perhaps hundreds of mod-lists being created there. But because the blobs are orbitting at different speeds - those mod-lists will gradually spread out and distribute themselves throughout the asteroid belt such that they don't stay bunched up for more than (let's say) a day or two.

If the server starts to run short of disk space - we can simply delete the oldest mod-lists using their time-stamps and quite automatically, those least-recently-modified blobs will magically 'repair' themselves. We may want to be a little more subtle about that though to prevent players from gaming the system. If a blob has a rare artifact in it - we don't want the player to realize that he can come back to that location a year from now and grab the exact same artifact again. So we might label blobs that were once found to have something super-significant in them so that we NEVER delete them...or perhaps, in general, simply apply an "importance" factor to each modification to a blob so that unimportant changes get erased very quickly and game-changing mods are never forgotten.

The second big problem with this scheme is that the blobs don't know about each other - so they will often move through each other (that's actually a desirable feature here because it makes for a more dynamic and interesting environment). So we'd need to do collision detection between the asteroids and figure out what happens between them. If the consequences are just modifications to the blobs containing those asteroids - then a mod-file change will do the job - but what we can't to is to make them spin off at different speeds and such because that would soon push them far out of the blob's radius. So probably:

  • When two colliding asteroids are very different in size, we should destroy the smaller of the two (updating the mod file) - fire off some inconsequential debris (which would simply cease to exist once it's outside of the current play area) and maybe start the larger one spinning or something (which could be handled in the mod-file).
  • With two small asteroids, we can just smash them both into debris and delete both of them.
  • But for two large asteroids, I think we have a problem. One possible solution for that is to calculate when they are going to collide when a new blob is added into the scene (we know their orbital parameters - so it's a foregone conclusion) - and subtly nudge their coordinates such that they just miss each other - or perhaps just clip each other, if they just clip then you can set them spinning, smash up their surfaces and throw off inconsequential debris. Of course doing this means that when you come back to that blob sometime later, the position of the asteroid is back where it would have been if it had never been collided with - but the error will be at most the radius of the asteroid. This situation will of course be rare.

One horrible error with this (and one we certainly can't address) is that when nobody is near a colliding blobfull of asteroids, they'll pass harmlessly through each other - because until someone flies close enough for a computer to generate the contents, nobody can possibly know that a collision occurred. Kinda like "If a tree falls in a forest and nobody is there to hear it - does it make a sound?" this case "No!".

Set Piece and 'hero' objects.

Sometimes, we're going to want large 'set piece' areas - very large planets, naval shipyards, mining colonies, that kind of thing. For these, the simplest solution is to pick a blob for them to belong in and create a mod-file by hand. You could have the mod file delete everything in the blob and create all of the new things you need. Now your set-piece flies around in orbit just like the other blobs. The game engine can be blissfully unaware that there is anything special about blob #654,321 until it loads the mod-file for it and gets instructions to load all of this special content and scripting.

One ikky game problem might be dealing with asteroid collisions wiping out critical game elements (like the store you go to when you want to spend your in-game cash). One possible way to handle that would be to search through the 1,000,000 blobs and find the ones with the fastest and slowest orbital speeds and use those for set pieces. The fastest blobs can only collide with things in front of them because nothing else can catch up with them. So the 'back' sides of all of the bodies within those fast blobs are a safe place to build large constructions. Similarly, the slowest moving blobs will never catch up with anything else - so the front sides of their asteroids are also 100% safe from collisions. Of course if you don't pick literally the single fastest or the single slowest blobs in the entire 1,000,000 set - then you might still see a collision (eg when the (normally-safe) front-side of the second-slowest blob collides with the back side of the absolutely slowest) - but those are astronomically (hehehe!) unlikely events. The probability of this happening is amazingly small - and (more importantly) the probability of it happening when anyone is close enough to notice is amazingly small times a million. If we actually cared about this, we could calculate the times when these events happened (like once every million years) and simply set the game in a period of history when it doesn't! However, I think the odds are too small for it to matter.

Another nice aspect of this is that we know which blobs players have played a lot in - so if we want to add content after the game has been running for a long time, we can easily find blobs without mod-lists and create new content there with a very low risk of anyone wondering why that massive alien base wasn't there when they last looked.

Efficient collision detection

This organization into blobs makes for efficient collision detection in-game because you know that you don't have to do any calculations at all unless the imaginary blob-spheres are overlapping - and you can do the calculations at your leisure because they are 100% predictable. This would also allow things like having AI's evacuate their asteroids just before the collision and such like.