I've recently been reading Asimov's Foundation trilogy and thinking about the scale of the galaxy. Combine that with playing Minecraft a bit and I've been thinking about how one might go about generating an 'infinite' galaxy -- that is to say, a galaxy with the 400 billion + stars that are estimated to be in the Milky Way. This would, of course, be more interesting if the world could have a Dwarf Fortress style history.
While I don't intend to attempt to implement anything other that perhaps a text-based prototype, out of sheer curiosity, I'm very interested in how the adept programmers here would go about generating an 'infinite' galaxy for use in a game.
Here are a few articles that I came across about infinite worlds:
- Discussion of bottlenecks in Minecraft (the comments are good, too): http://0fps.wordpress.com/2012/01/14...-like-engines/
- Discussion of infinite worlds in Malevolence: http://www.altdevblogaday.com/2012/0...eo-game-world/
I'm guessing that nothing truly would be generated unless the player was approaching it, already visited it, or if it was needed to support the DF-style history of the galaxy. Thoughts?
(This is meant more as a discussion thread about how you might go about this instead of a specific Q&A thread; I'm just curious about the topic.)
Randomly generating worlds is easy. Making them interesting is very, very hard, particularly if you want there to be some internal consistency on how high level elements (politics, trade) tie into low level stuff (resources), and how realistic you want it to be.
So that said, just start with a random generation algorithm and start tweaking. There's nothing else magical about it other than starting with the initial understanding that everything will feel fake for a long, long time.
DF and Minecraft take different tacks: Minecraft generates chunks as needed, and Dwarf Fortress generates a world at (kind of) coarse detail and fills in (every last brushstroke) as needed. It seems to me like combining them would be an interesting challenge.
You couldn't take the DF approach for a whole galaxy: to come up with unique names in [A-Z0-9] would take eight bytes per star for 2.9 terabytes for the whole thing.
I guess I'm more interested in the technical implementation and limitations than the details of the random generation, if that makes sense. For example, it seems to make more sense to go with chunks that are generated as needed than to try to pre-generate an entire galaxy.
That said, how do you give the player the feel of being in a huge galaxy without doing some coarse pre-generation? If the game purely involves discovery, then the entire galaxy can be in 'fog of war' and generated as needed, I suppose. Perhaps 1% of the star systems have some sort of pre-generated history that could be stored separately.
How would you conceive of 'chunks' at a galactic scale? How would you store them for serialization, lookup, etc?
You use a random generator that takes varying levels of 'roughness' to give you fine vs. coarse level detail, then take the output of that pRNG and use that to generate appropriate detail information (like height data or whatever).
Since it's all procedurally generated, you don't actually generate anything until it's necessary, which is usually when a player encounters an area. Where it gets a little tricky is if you allow persistent change. So if a player comes into a solar system and then somehow impacts things, you have to store that. If you removed the ability to dig/build, then Minecraft wouldn't need to store chunks to disk ever, and it would be a much easier system overall since the pRNG could generate identical data on the clients and the server with almost no network traffic.
To control how things are generated you'd precompute some seed values to ensure that you got something interesting.
All that is just for the generation of the base layer of information (worlds, solar systems, terrain), after that you'll usually want to do some kind of emergent stuff. For example, if you see that two systems are near each other and are rich in complementary resources, you'd assume that they're trade partners (or at war, or one is a territory of the other, etc. -- this is where you just tweak a lot).
And if they're trade partners, you would assume that there's some kind of pirate activity that is proportional to the traffic. You have to do lots of little emergent things like this to make it all feel good.
You can also choose where you do the cutoff between random and calculated somewhat arbitrarily. For example, you could randomly generate the star type, and then use a pseudosimulation to see what types of worlds are generated so that you have something that feels correct and thus avoid things like earth type planets circling a neutron star or something.
Yes, all this advice is good. Just break the generation down into bite sized chunks that each do one job well. One piece designs the galaxy structure and perhaps star types. When it is done, another chunk, the solar system builder goes to work and it may hand off things to a gas giant builder, or earth type world builder which in turn may hand off what it has done to some other system. It all depends upon how much detail you want to get into.
If any single piece seems too complex, perhaps that is a sign that it should be multiple pieces.
I think procedural content generation requires a very careful gameplay design to be any good, and it rarely works very well. I suspect a 4x galactic sandbox with procedural content will bore the player very quickly.
To the extent the "procedural content" is really rolling dice to place handcrafted content in random locations, that's something else, of course, but think of what Mass Effect 1 planets were like and they weren't even random, but handcrafted with low resources, which yields a similar result. Very different terrain, different skyboxes, and different lighting effects on each world, but the gameplay was exactly the same on every one, with the only variable being whether there were those maw-things or not. So sure, you can have gliding-through-the-atmosphere gameplay on gas-giants, and submersible gameplay on ocean worlds, but how are your zillion ocean worlds going to differ from one another in interesting ways without hand-crafted content?
That's the tricky bit, but it's still manageable. You start with 100% randomly generated (which is boring, weird, and inconsistent), and you then replace bits at a time by either tweaking the generators and/or including hand crafted content and/or something in between.So sure, you can have gliding-through-the-atmosphere gameplay on gas-giants, and submersible gameplay on ocean worlds, but how are your zillion ocean worlds going to differ from one another in interesting ways without hand-crafted content?
I suppose that's what I was getting at with the random generation vs. technical implementation point. I'm under no pretense that it would be either a good idea or make fun gameplay to generate a complete galaxy. I'm more curious about how one might go about the non-generator technical aspects. How do you store the data in arrays? Or do you use a dictionary? How do you serialize the data? Compress/Expand it? If a player makes a change to 1 of the worlds, how do you alter it in the array, etc?
Those are just general programming issues and nothing specific to procedurally generated universes. There are a jillion data structures you could use at the high level -- sparse arrays of some kind (maps/dictionaries). You'd only serialize those elements that had any persistent change (if you allowed it). In a Minecraft world you have to serialize everything since everything is destructible, but it's conceivable that in a static universe you don't have to store anything except player state.
I don't see why you have to worry about destructible or alterable objects at all until after they've been dirtied.
Say a 64 bit random seed generates this huge complex world, or will generate it if the player ever bothers to look at it. The world is completely destroyable and editable, but of course it hasn't been destroyed or edited yet.
Now the player visits the world, so you save the seed, but if the player does nothing to actually change the world, why do you have to do anything more? You just delete all the objects when the player leaves, and if they come back, you generate them again from the seed.
Now let's say the player nukes one continent. You still only need to save the changes, not data for the whole world. Now all the nuked landblocks are set to the nuked state and various other destroyed objects are deleted, so you note the list of deletions and the list of changed landblocks, but that's only that one continent. The rest of the world doesn't need to be serialized.
If you're clever and the world changes allow the notion, you don't even need to do that. Say the player detonates 72 10 gigaton nukes around the continent. If it's easy and fast to recreate the effects of the nukes, then you could conceivably just save the world seed and the locations and sizes of the nukes, and journal back the changes every time the player revisits the world. Of course, this may not be feasible for all kinds of world changes, depending on how they're modeled and what the player is allowed to do.
Depends on scale issues, I think. With the Minecraft example, there's a huge performance difference between generating chunk data and loading previously generated data, so you want to avoid regenerating them from scratch whenever possible. The saved chunk data is as much a cache as it is a record of changes.
Yes, I guess my post wasn't clear on that -- you only have to save out stuff if it's been altered, but as Fugitive says, there are potentially performance issues as well but these are implementation dependent.I don't see why you have to worry about destructible or alterable objects at all until after they've been dirtied.
All your suggestions are valid but they have different trade offs and constraints depending on the underlying model. If the world is a heightmap and you allow Magic Carpet style destruction of terrain, just storing the deltas may not be enough if the changes in elevation then create global effects (e.g. water flooding into new depressions).
But like I said earlier, all this stuff isn't particularly unique to procedurally generated worlds, it applies to word processors, image editors, etc. The trade offs all depend on the underlying implementation.
Just the thought of Minecraft where the entire world is simulated at the level of detail as Dwarf Fortress gets my blood pumping. We need faster computers!Originally Posted by Fishbreath
Nobody mentioned Elite, yet? Get off my lawn!
Elite worked basically like Bacon described (and ran on shitty 1mhz/64k computers!).
So -- why wouldn't this be possible with today's worlds? The DF worlds are pretty big, too...
Also, Elite is mentioned in the second link in the original post.
More specificaly Elite II(Frontier) and Elite III(FFE) used an actual real model for the galaxy. The first Elite was big (especialy for the tech at the time!), but it did not try to model our actual galaxy.
I'm working on a game design currently that will use the later Elites type of galaxy modeling, so at some point i also need to dig into the detail on just how David Brabben did that in those later Elite games.
Irrc, the suns were all pretty much as is in real life (types/distances/sizes etc), but at the time all the planets were pure random speculation as we had not discovered exo-planets at the time those games came out. But still the in-game navigational map was a thing of beauty, and education.
A really good reference for random planet generation are some of the GURPS Traveler source books.
I've been reading through the Wikipedia entry on Stellar Classification, which is pretty interesting:
http://en.wikipedia.org/wiki/Stellar_classification
Needless to say (?) there's on the order of a hundred billion stars in the galaxy. It would be crazy to develop a game that models them all, even if the planets will never be generated unless someone visits. I mean, that's three coordinate numbers plus some extra bits per star for stellar type, on the order of let us say 3 terabytes uncompressed, unless of course you use 64 bit coordinates, in which case it's over 6 tb....
Assuming a player actually lands on and explores interesting planets, how many can they reasonably visit in a normal game? 100 or so? So unless the galactic scale is an important part of the game concept, restricting the scale to be more like 100 LY radius (which volume around Sol contains over 3,500 stars) might be a better idea. If the galactic scale *is* important, you might consider restricting generation and travel access only to a relatively small sampling of type F-K stars that can conceivably have habitable zones, but even then, there's over 7 billion type G stars alone....
This makes me recall my dream for a game engine that was able to render human (or biological non-human) bodies down to an extremely fine level in order to more accurately simulate the effects of traumatic damage from weapons fire, blades, etc. Basically, seeing the exact same animation pop an arm or leg off at exactly the same place to be replaced by exactly the same generic "open wound with a bone" texture a thousand times in a game with otherwise gratuitous combat just feels like it's missing a golden opportunity.
But then you're going from a few thousand polygons per model to a far vaster number as you accurately model their skin, blood vessels (and blood!), muscles, bones, and organs and animate all of them in a quasi-realistic fashion, applying real physics to all to most properly portray what would happen when struck by a handheld nuclear device fired from a violent space marine some twenty feet hence. You'd need real-time deformation and destruction algorithms, be able to re-render models into their component parts, readjust physics on the fly to recalculate center of mass and the effects of gravity, dynamically generate new textures to accurately portray the damaged areas, etc.
Probably unrealistic for, say, Doom4 or God of War 4, but could something similar be implemented into, say, Soul Calibur (perhaps Bushio Blade would be a better fit, insofar as it pretty accurately assumed the catastrophic, fight-ending damage even a single well-aimed blow with a sword could do)? Maybe so. It's an unrealistic, absurd, almost pedantic (and perhaps somewhat pornographic) amount of data to model, but if a game design called for it and made legitimate and novel use out of it. . . maybe it'd be worthwhile.
Dwarf Fortress does most of that besides the graphics.
Why not generate the stars as well? Let the player look as far as he wants, everything just gets generated as he moves his view along, drawing from some stellar distribution parameterized by location in the galaxy.
I agreed that the galaxy is ridiculously huge, but once you've committed to a procedural approach, it doesn't matter how big whatever it is your are modelling is, just how quickly the player can generate deltas that have to be saved.
You seriously dreamed this!? No wonder gaming is what it is for a large part! (i'm half joking)
On Miramon's point about the maths (we say maths instead of math), i might be wrong, but i think the model used in Elite 2+3 used some form of mandelbrot equation? And i just found this link with a quick google that might shed some light on what those games did:
http://www.jongware.com/galaxy1.html
There is no such thing as the Mandelbrot equation unless you just mean the procedure for calculating the boundaries of the Mandelbrot set. The Mandelbrot set also appears to me to not be relevant.
But more to the point, I see no obvious application of fractals to procedural star generation and placement, since their distribution is not in self-similar structures, but is either in clusters or more generally according to the overall galactic spiral arm structure, which does not repeat at lower or higher levels.
I suppose it would be possible to use a fractal just to get irregular placements, but I don't see why you'd want to go to the trouble when you could just use a regular old distribution.
Yeah my mistake, after looking through that link it didn't mention that stuff (fractals), so it might have been from another game (something to do with planet generation iirc?).
The linked article seems to pretty much spell out how Braben and his coders did the galaxy size maths stuff for Frontier and FFE, so you might find it handy. I've bookmarked it for later as it seemed a pretty decent source.
That's quite comprehensive! I find the guy's narrative a bit tough to read, however. Thanks for the link.
Ah, it wasn't GURPS Traveller, but GURPS Space I was thinking about. I believe that's the one with a fairly comprehensive random system generator, and I think GURPS Traveller: First In had some other stuff in it as well for world creation.
Yeah all the traveller based stuff is pretty awesome, i got all the source books around someplace and dig them out from time to time, they sure put a lot of detail into a p+p system.
@Clay, your welcome (and good luck in your ambitious task!) and it seems from a mathmatical aspect you can simulate the massive numbers required, with some clever tricks as the difficult to follow article explains.
Check out this kickstarter: http://www.kickstarter.com/projects/...ral-space-game
Posting Permissions
Reply With Quote