Part Dev Diary, part wonderings and sometimes questions too!

As you know, the goal of my game is to recreate a galaxy in which the players can have fun in. Although I’d love to have a galaxy that contains the average number of star in a galaxy, it’s simply not doable. Besides, int only go to 2.4 Billion. :wink: But, I do give the closest option (1% realist galaxy).



To give you a sample, here’s the rundown of star numbers per galaxy size.



[java]

/**

  • This method generates the number of stars based on galaxy radius
  • multiplied by the user’s choice in options screen.

    /

    protected void bigBang() {

    galaxyRadius = FastMath.nextRandomInt(MIN_RADIUS, MAX_RADIUS);

    // Calculate depending on user’s settings, for now force to 0/tiny

    int mult = 0;

    galaxySizeChoice = 0;

    switch (galaxySizeChoice) {

    case 8:

    /
    709 436 520 to 2 147 483 520 /

    mult = STARS_MULT_ONE_PERCENT_REALIST;

    break;

    case 7:

    /
    234 367 398 to 709 436 448 /

    mult = STARS_MULT_GIGANTIC;

    break;

    case 6:

    /
    77 633 918 to 234 999 968 /

    mult = STARS_MULT_HUGE;

    break;

    case 5:

    /
    8 472 630 to 25 646 880 /

    mult = STARS_MULT_ENORMOUS;

    break;

    case 4:

    /
    2 798 976 to 8 472 576 /

    mult = STARS_MULT_BIG;

    break;

    case 3:

    /
    924 630 to 2 798 880 /

    mult = STARS_MULT_MEDIUM;

    break;

    case 2:

    /
    305 398 to 924 448 /

    mult = STARS_MULT_LOW;

    break;

    case 1:

    /
    100 862 to 305 312 /

    mult = STARS_MULT_SMALL;

    break;

    case 0:

    /
    33 300 to 100 800 */

    mult = STARS_MULT_TINY;

    break;

    }

    numberOfStars = galaxyRadius * mult;

    }

    [/java]



    The main problem right now and I guess the hugest, is that even with a tiny galaxy with less than 100 800 stars, I’m getting into problems. When I generate close to that many stars including their planets and moons of each planet, the game is gobbling a chunk of memory and that’s when the generating doesn’t simply crash with a heap error.



    The game will have 12 sentient races that will be randomly (more or less) placed around the galaxy. To “finish” the game, you have to interact with those races, do quests, etc. Now, what the game also is is a sandbox-type game. Meaning that life could evolve on some planets, even evolve into sentience and if they’re lucky, roam around their local space. Although those could potentially exist, it won’t be necessary to interact with them to succeed the game. But, the possibility is there to do stuff with them. You can see these as side quests.

    So, all this to say that those secondary citizens need to be generated during the creation of the galaxy. Pretty much everything has to be generated and, honestly, with over 2 billion star systems that would include planets, moons, accretions disks, asteroid fields, races, ships… I probably wouldn’t be able to play my game with the 16 GB of ram in my computer.



    I need a plan to manage this.



    What I’m thinking right now is to compute only the stars in the galaxy.



    Then, once I have the OcTree filled with stars and found where the player will “land”, I could build that leaf’s solar systems. That would amount to around 200-2000 stars depending on the machine on which the game runs.



    As the player moves around and exit a leaf, I could build the next leaf.



    But the above means I would need to save the information to disk and retrieve it as the player switch leaf. Something I wanted to avoid because of the input/output save/load time it takes. It’s not a very big deal, but I wanted it to be seamless.



    I think that would be the best plan, but I’d love to hear what you guys have to say. I’ll admit my inexperience here is a big flaw. I have no idea how I could save what I generate on disk. :confused:



    Thanks.
1 Like

Firstly I need to say your game is starting to sound really interesting, good work!



Some thoughts on your issues :



Do you really need billions of planets ? or even hundreds of thousands ? a player will never have time to visit all them, perhaps scale back ?



You might need to look into procedural generation, I don’t have any links for you sorry, but the basic idea being rather than using completely random numbers to generate planets, you need to be able to generate a reproducible pseudo random list of numbers (this can be achieved by using a constant seed).



eg: say you used this list of numbers to choose which race goes on which planet, the random list of numbers might be .82985, so:

the first planet has race 8

second planet has race 2

third planet has race 9

fourth planet has race 8

etc…



so the races are completely random, but every time they are generated, they will be the same because the random list of numbers will always be the same (make sense?).



Using this method you can reliably generate the content you need, as you need it, no need to pre compute 16gb of data. If you do this, you will not need to save and load leaf states because you can regenerate them exactly the same way every time they are needed. You may need to look at moving this generation process to a different thread so as not to slow down game play.



It sounds like what your trying to archive and the issues you will encounter are not all that dissimilar to those of Mythruna (generating large amounts of data and needed to stream them in seamlessly) so you should probably have a chat to pspeed - very smart man.



Also, if you find yourself really really suck on this, from my own experience I would suggest working with a very small number, say 10 or 20 planets and move onto another interesting part of your project for a while, otherwise you will run the risk of getting too bogged down in this one issue right now, which can be very taxing on you and your game.



Good luck!

James

If your data is compact and well organized, disk load/save can be almost free. Mythruna loads many tiles in around a millisecond and that’s with tile compression. That’s a 32x32x32 int block run length encoded. Even gzipping them was only adding about 10 milliseconds to save/load time… but I load a lot of tiles a LOT. :slight_smile:



One other trick would be to load the data in the background before you need it. So either load one extra leaf out or start loading the data when the player gets near the next leaf (funny, Mythruna’s engine calls its “tiles” leafs… and it’s not a coincidence even though I abandoned oct trees early on.:)).



But yeah, I think LOD is your friend. Plot out the stars themselves early with only basic information. Then as the player gets close enough to need more detail then build that detail. Build the planets when you need the planets, etc…



Which is pretty much inline with what you are thinking so far.

There will be no other way than to do actual graphics and use Spatials etc. around the player only and have the other parts of the world as abstract data (probably in a database) that runs only on a simplified, globalized version of the AI or whatever happens in your galaxies. Its a big task, the reason you don’t see this kind of stuff too often is probably that :wink: Thats why many games have “loading screens” “levels” what have you. Other games stream the data in and out seamlessly but in fact you are running around in a confined space of some 10.000 units being warped around like on a holodeck :wink:

normen said:
but in fact you are running around in a confined space of some 10.000 units being warped around like on a holodeck ;)


Hmmm... sounds familiar. :)

Thank you all for the feedback. I’ll try to address each post.


thetoucher said:
Firstly I need to say your game is starting to sound really interesting, good work!

Thanks. :)


Do you really need billions of planets ? or even hundreds of thousands ? a player will never have time to visit all them, perhaps scale back ?

Of course not, I don't need hundreds of millions of stars and as you hint at, something like 10 000 would be fine and dandy. Gameplay-wise this would work as good as having 2 000 000 stars. The thing is, I -want- it to have as many as possible. In a certain way, I'm also doing a galaxy simulator. Not an accurate one, but it's along the general lines. But don't you worry though. I am very much aware that having my sight on an enormous amount of stars could be a game killer (pun intented), and I do have a backup plan to scale way down. But until I hit that wall, I think I can (and will try to) get away with it. Last on that point; the importance here is not that you can and should visit all the systems, it's that they're there if you wish to and that it, somehow, reflects a bit what a galaxy looks like is what matters. It's like Minecraft and Mythruna. Those two games have an infinite world, but really, who will generate an "infinite" world?


You might need to look into procedural generation, I don't have any links for you sorry, but the basic idea being rather than using completely random numbers to generate planets, you need to be able to generate a reproducible pseudo random list of numbers (this can be achieved by using a constant seed).

This might work for what I call pseudo-space-games, but I don't want that. I don't want to use "templating" to create my worlds. Of course there is some "infused" randomness, but doing otherwise (totally random) would demand too much time to compute. Gamers, like me, want things done rapidly and want to jump into it ASAP, but at the same time, I/we don't want to visit worlds that all look alike up to a point.


eg: say you used this list of numbers to choose which race goes on which planet, the random list of numbers might be .82985, so:
the first planet has race 8, etc...

so the races are completely random, but every time they are generated, they will be the same because the random list of numbers will always be the same (make sense?).


The races you're talking about here, I gather, refers to the "side-quest" type of races I mention above. Well, that's exactly the type of thing I want to avoid. Each randomly generated race will have it's uniqueness that will distinguish it from pretty much any race you will encounter and/or could get from generating 2 different galaxies. Ok, yes, there will be a finite number of permutations and luck should make it so they're always different and shouldn't have the same visual outlook, at least that's the plan.


Using this method you can reliably generate the content you need, as you need it, no need to pre compute 16gb of data.

Nothing is pre-computed. Let me rephrase that. Nothing is predetermined except the parameters to define physical components. Once a planet is generated and that it has a potential for harboring life, an algorithm (I'm not there yet) will come up with the type of life that exist and at what evolutionary step it's at. It could be microbial lifeform or it could be sentient. They could be long-lived but slow-evolving, or short-lived and quick evolving. Anything goes (some of those parameters are already there, just not being used right now).

Reading what you suggest, at least the way I understand it, would completely wipe that. Races will not be defined using a cookie-cutter. I'm adamant on that, but if I have to compromise on this I will. I'm not there yet and that's not until I'm there that I'll have to think really hard about it. :)

The 12 races I was talking about are those that will be set in stone (at least some aspects of them will be) and they will be scattered throughout the galaxy. Those races will have some scripted elements to them so the game can go forward and you can find your way back to Earth. There's no other choice here. :)


If you do this, you will not need to save and load leaf states because you can regenerate them exactly the same way every time they are needed. You may need to look at moving this generation process to a different thread so as not to slow down game play.

One way or the other, snapshots of the leaf will have to be made. At least for the sentient-space-faring-inhabited leafs. And of course the leafs containing the main antagonists.


Also, if you find yourself really really suck on this, from my own experience I would suggest working with a very small number, say 10 or 20 planets and move onto another interesting part of your project for a while, otherwise you will run the risk of getting too bogged down in this one issue right now, which can be very taxing on you and your game.

As it is right now, when randomness plays nice and I don't get a crash when generating moons, and the game gives me around 75 000 stars to play with, it takes about 30 seconds to generate the whole galaxy.

To be more specific:
That's more or less 75 000 stars.
Each star has a solar system that consist of:
0 to x planets (x being about .02% the mass of the star).
If 0 planet, it might have an accretion disk instead.
Then, if it has planets:
Each planet can have up to 5 moons (depending on planet's mass).
Also, planets have an atmosphere that is randomly generated. (depends on the planet, mass, location, etc)
You could find one of more asteroid belts.
Later, comets and asteroids (planned and some code done, but not implemented yet).

As you can imagine, when you add moons, data starts to pile up pretty damn fast because of the numbers of planets... Quick math: 75 000 stars * 6 (average planets per system) * 2.5 moons per planet = 1.125 million moons. Then you add the other data... That's a lot.
pspeed said:
If your data is compact and well organized, disk load/save can be almost free. Mythruna loads many tiles in around a millisecond and that's with tile compression. That's a 32x32x32 int block run length encoded. Even gzipping them was only adding about 10 milliseconds to save/load time... but I load a lot of tiles a LOT. :)

For some reason I'm stuck in the old idea that loading/saving on the fly is really really bad. And it's not for the lack of contrary proofs I might add lol. Mythruna does it quite well, so does many other games.


One other trick would be to load the data in the background before you need it. So either load one extra leaf out or start loading the data when the player gets near the next leaf (funny, Mythruna's engine calls its "tiles" leafs... and it's not a coincidence even though I abandoned oct trees early on.:)).

Now that's funny. It's funny because when I started the project I had this all so nice "document" that I had made that was pretty much an exact copy of what you're suggesting. For an unknown reason it got discarded along the way. But, I haven't forgotten about it. Actually, it got discarded because of the flawed vision I had in mind with the way I wanted to implement the OcTree (before I knew of those). In fact, I was reinventing the wheel and making it triangle. So I ditched the whole plan instead of just throwing away what was wrong with it.


But yeah, I think LOD is your friend. Plot out the stars themselves early with only basic information. Then as the player gets close enough to need more detail then build that detail. Build the planets when you need the planets, etc..

Which is pretty much inline with what you are thinking so far.

Because of the reasons I outlined above, the solar systems have to be generated when the player enters a leaf. Activity might take place, the local (randomly generated) race might be harvesting resources from the local star systems and those have to show up (ships going to and fro, etc).

Nonetheless, what you're suggesting seems to fit with the revised vision I have in mind. I have been thinking about that change for the last couple of days because of the moons accumulation problems.
normen said:
There will be no other way than to do actual graphics and use Spatials etc. around the player only and have the other parts of the world as abstract data (probably in a database) that runs only on a simplified, globalized version of the AI or whatever happens in your galaxies. Its a big task, the reason you don't see this kind of stuff too often is probably that ;) Thats why many games have "loading screens" "levels" what have you. Other games stream the data in and out seamlessly but in fact you are running around in a confined space of some 10.000 units being warped around like on a holodeck ;)


That took me several rereadings to understand what you're suggesting. :P But yes. You're right. Up to a point. Some of that data has to be available during the world creation because interaction of the player with the rest of the galaxy depends on it and so are the visuals (ships going to and fro to gather resources, exploring, etc).

Speaking of 10 000 units, could it be possible to extend that range to 1 000 000 or more? Please? Pretty please? Ok then. I'll scaled things down. :P

I think the consensus agrees with my conclusion (please if you think otherwise I’d love to hear it).



Generating the galaxy’s stars (all of them) including their characteristics (not talking about spatials here).

Putting the above stars in the OcTree.

Save the tree.

Get player placement leaf.

Retrieve leaf.

Generate that leaf’s solar systems (planets, moons, etc) then save those to disk.

Let player have fun.



When player gets to a boundary (or close to it), save current leaf and load next leaf.



I think that should work. Of course things like the current OcTree will have to be modified as I won’t have to hold the information for each and every leaf, but only their boundaries so I can quickly assess where the player’s ship is. Small stuff like that…



Now, as mentioned on that last line of my first post, I have no idea how to save the internal state of anything to disk. Huh, anyone has resources (links, tutorials, etc) on how do that? I’d be very grateful to have some info about that! :smiley:


Now, as mentioned on that last line of my first post, I have no idea how to save the internal state of anything to disk. Huh, anyone has resources (links, tutorials, etc) on how do that?


Do you mean Serialization ? I have had success using this JSON library combined with a custom simple JSON reader/write class registered with assetManager to persist world states in JME to disk, then read them back again.

Thanks @thetoucher! I’ll take a hard look at those tomorrow. Now it’s time for some New Vegas. :wink:

Binary data will be faster to save and load than JSON because it’s closer to the final form. It’s down side is that you need to be aware of format changes and potentially plan for them. For example, all of mythruna’s binary files have a protocol version as one of the first ints in the file.



For my file formats, I hand-rolled the serialization to hand tune it. Java’s built in Object serialization is pretty good but my data structures are such that I knew I could trivially shrink them further. If you go the route of hand rolling your own and you have never done binary files before, DataInputStream and DataOutputStream wrapped in BufferedInputStream and BufferedOutputStream (<- a must for performance) are pretty simple to use.



Regarding Oct-trees… you might seriously consider abandoning this over a straight three dimensional grid. Oct-tree traversal is done in log time (I’m talking CS style big O here, ignore me if this makes no sense) while a straight grid can be traversed in constant time. This is why I abandoned oct-trees in Mythruna shortly after naming my ‘tiles’ “leafs”. Given a coordinate, finding the grid cell I’m in is just a single math operation… and I don’t waste splits on open space.



Most oct-trees devolve into grids anyway if you stop at a minimum size and have sparse data. And if you consider the grid the data structure then you can get away with only storing the grid cells that have things in them. And note: even a galaxy, much like a planet’s surface, is kind of 2.5 D since they tend to shape into discs. So one dimension of your grid could be considerably shorter… and you could theoretically go on infinitely in the other two directions.



Which brings me to bridging a gap in the conversation regarding repeatable randomness… There is repeatable in the style of what you shun (and rightfully so) and there’s repeatable in the style that Mythruna strives for.



My world is completely random based on a seed. A different seed gets you a different world… but the same seed gets you the same world. That’s because the nature of the fractals relies on a 3D pseudorandom number that can be seeded. And the nice thing about the way the fractals are implemented in Mythruna is that I can ask for elevation at any point in the world without ever having prebuilt anything. But nothing is “precalculated”… it’s just repeatable.



the nice thing is that if you start at the far edge of the world and I start at the other edge and we walk to meet each other, when we meet in the middle the terrain and everything else still makes sense.



Adapting this to the other things other than elevation is hard but not impossible. It may be nearly so in your case but it’s worth considering ways to get there when you can.

  1. wall of text crits you for 9999.
  2. but doing otherwise (totally random) would demand too much time to compute

Wrong it wont because :

a) you run the specified random generation algorithm based on distance. E.g you dont need to render / generate world above the max distance. So if i say max distance 32 meters, it will have performance cost O(32) even a dos 30 years ago could play that kind of games e.g elder scrolls daggerfall. Based on distance you will call a corresponding generation method something like lod, e.g instead of generatePlanet (That has animals etc) at <32, use generateGalaxy (which makes planets that look as a particle (an image))) at 32 < distance < 500.

3) int capacity shouldn’t be your issue.

Remember how dungeon siege 1 removed float capacity / accuracy problem by having a coordinate system that split the world into zones. The player could switch zones in 0 time seamlessly.

http://www.gamedev.net/topic/336765-coordinate-translation-in-huge-world/

I will address both message in their entirety tomorrow, but the next part I want to reply right away before I forget.


tralala said:
1) wall of text crits you for 9999.

Looks like it wasn't enough since you're still there and replying. ;)


2)
Wrong it wont because :
a) you run the specified random generation algorithm based on distance. E.g you dont need to render / generate world above the max distance.

You misunderstand (or I misphrased what I meant). What I meant was that to do everything I wanted to do randomly (and accurately, according to what we know of planet/star/moon formation) it would be too long to generate for the amount of stars in a given "sector" for what it would be used for.

Ex.: I have the libraries for a program that does similar things starting from a star that I do with my game. But, that generator starts everything from the standpoint of a huge ball of gas and dust and computes what the final result of the solar system will be including detailed gas discrimination in each planet's atmosphere. There is NOTHING not based on hard science (at the time, this was done in early 2003 iirc) or if not on hard science, on very well educated guesses and/or published papers from astrophysicists, geologists, etc.

Considering that with the above library, generating one solar system takes about 1 to 1.5 seconds, I don't want to think about doing 200 in a row.

That's what I meant. Sorry for the long post. :P

Ok, I’ve got a bit of time before bed.


Regarding Oct-trees… you might seriously consider abandoning this over a straight three dimensional grid. Oct-tree traversal is done in log time (I'm talking CS style big O here, ignore me if this makes no sense) while a straight grid can be traversed in constant time. This is why I abandoned oct-trees in Mythruna shortly after naming my 'tiles' "leafs". Given a coordinate, finding the grid cell I'm in is just a single math operation… and I don't waste splits on open space.


My OcTree isn't a real octree. I actually don't have to traverse anything. The base of it was an octree, but it devolved into something else. I wouldn't know how to call it. The only octree-ness it has is that I'll split a leaf when it hits the max_capacity into 8 leafs. Once I'm done filling it, I remove every leaf not containing anything. So I guess it is and isn't an octree.

Also, I don't need to do lookups because I've made a lookup table that is easily and rapidly parsed. Up to now it hasn't failed me. *shrug*

I guess you could call my octree implementation a 3D container octree? lol

So far I can't say I've hit any slowdown (anyway nothing I can link to that or that I can notice). I'm not saying what you're suggesting is bad though. I'll also take a look at it tomorrow.

I followed a similar path in my early geospatial work… you might end up in the same place.



When you can look up every node by a “key” and no longer traverse the tree because you are indexing them… and when you have a minimum split size (in geospatial quad trees this is very common)… and when you don’t even create leaves for the areas that don’t have data… then eventually the “why do I even have a tree?” question often arises.



In my cases, I eventually chose just to use a fixed grid. No indexing is necessary because the leaf ID is also its location.



Random somewhat related trivia:The US military uses a grid coordinate system that has level of detail built in. (MGRS if you want to read about it). So the longer the “coordinate” the smaller the grid cell if refers to. They can map the whole world down to the centimeter this way or refer to really large areas with the same type of coordinate. Basically, the earth is divided into zones and these are subdivided into grid cells, and those are sub-divided and so on. Each digit set in the full coordinate tells you the next level of cell.



Back to reality, in an Oct-tree or quad tree, this is sort of the equivalent if giving each node an ID unique to its split level… and then accumulating them on the way down to the leaf. So in a quad tree where each split gets A, B, C, D as children… AAACD refers to a specific quad 5 splits down.



And the next leap is realizing that the four or eight way split is arbitrary once the tree is gone. These were useful for traversing because a plane test can easily be used to figure out which branch to traverse… but it’s not a requirement when never traversing the tree.



For the curious, Mythruna has essentially three “splits”… named arbitrarily at this point: Nodes, Leafs, and Cells. A node is a 3D grid of 32x32x5 leafs, a leaf is 32x32x32 cells… and a cell is 1 meter cube so any float x,y,z coordinate can be turned into a cell coordinate by calling floor(). A leaf location by dividing by 32, location within a leaf by mod’ing with 32, etc… IDs of any level are pretty trivial to calculate at that point. Without ever pre-calculating or pre-indexing anything, I can tell you precisely what the node or leaf ID would be for any location on the world.

  1. generate the solar system in another thread.
  2. you dont need accuracy for objects that are far away, user wont notice.
  3. use your own bad looking solar generation system for far away objects. And maybe use scientific solar system rendering, if the user is close to it. Remember than in spore you cant see the planet inhabitants unless you zoom in and enter the planet.

Actually you can optimize space games a lot, especially when there is no multiplayer. As you then have afar more time for loading and background work.



→ Make a algorithm that genreates Star positions procedually.



Now for each star → render the nearest 10k stars to to 6 textures, use that textures as skybox for your current system. (This works espcially as you usally don’t want players to fly endless between galaxy but have some kind of warp hypterdrive jumpdevice, so they will never fly so far they recogines the skybox is not moving.)



In my current project I use a trick to get more size per sector. The server calcuates everything in 64 bit, (and uses a own 64 bit jbullet version) The client now calcualtes a offset so that the player always stays at around 0,0,0 in jme space, that way I can have realsize 1mm precision up to pluto from earth. (though i only need a few cm precision so it could be far larger).



Floats would be good enough if you use miniature spaceships and do not plan on having humans and spaceships in one scene so you don’t see how small the spaceships are.



Only the system you are in needs to calcualted with physic, all others can be used without, to imporrve perforamnce and simplify npc ai. Despawn everything not visible. (So if a look into a secot with a camera satelite or something just spawn them exactly that moment due to global data.

(Like you know where wich ressource is needed and where sold, so you can belivable generate the trading ships only based on that accuratly enough to fool the user)

Thanks for all the input guys. It’s appreciated.



I’ll look into those suggestions/solutions in the next few days, but right now I have to save the generated basic galaxy to disk before I do anything else since without this, going further is pretty much useless.



Hopefully my head won’t esplode while reading about serialization. :wink:

Yes, saving is good.



You don’t know how many times I ran and played Mythruna before saving was implemented. It was very Zen to build elaborate structures that whooshed away when I shut the game down. :slight_smile: I still have some of the photos though. :slight_smile: