Fractal Generation System

Talk among developers, and propose and discuss general development planning/tackling/etc... feature in this forum.
Post Reply
mkruer
Site Administrator
Site Administrator
Posts: 1089
Joined: Thu Jan 02, 2003 10:07 am
Contact:

Fractal Generation System

Post by mkruer »

The idea of a Fractal Generation System is not to replace anything currently in VS, but rather augment what is there by adding additional missing material. The question still remains, why use fractals? Simple, fractals are the most efficient way to generate complex objects that with perfectly reproducible results. Fractals are only generated when needed, saving drive space, and fractals will allow for infinite detail. Because the way Fractals work, there is a key seed number that is used to generate everything.

In order to optimize an fractal algorithm it is important that we set limits for various classes of object, there is not point in trying to render object less then say 1 meter in space.

The Fractal Generation System as I see it is not just one huge fractal, but rather a series of fractals each specifically engineered to generate specific objects

Thinking from, the larges structure down. You have

Galaxy Fractal; This Factual is responsible for generation of the overall shape (structure) of the galaxy(s) and the type of star class. Ideally you would like 400 billion points, but realistically you are probably looking at 100 million max (never the less the power should be there). This class will affect the system fractal, both in size, color, mass.
* Mass Limit to classify as a star is aprox 0.08 solar masses.

Next is the System Fractal. This is responsible for generation the location and orbit of all major planets, asteroids belts and comets, but not necessarily planetary rings. It is here that the zones would be set up that will determine what type of planet you should find.
Example closer to a star there is a higher probability of finding terrain class planets then gas giants.

Planetary Fractal. This is where terrain features both textures, height maps are generated and or planetary ring objects should be generated. This level would also include such things as cities

You will notice there is a lot of cross over between all three level, and the way I broke it down is immediate location, not by entity.

I am looking for someone(s) to help in the development of a Fractal Generation System. I myself suck at programming but am very knowledgeable with mathematics (ironic I know)

The way I would like to build the Fractal up is from the smallest part to the next size up, planets, and then if needs be galaxy. It is important to get the fundamentals correct, because if we have to go back and change an equation, there are massive repercussions with the outcome. It also needs to be modular, what I mean by this is at any point you should be able to use any of the sub functions to complete your systems. A good example would be if you already have made your system, but need to add an asteroid belt, but do not want to have to list tens of thousands of objects, or better yet if you have a ring around your planet, you do not want to have to manually enter objects. Averyhing sould be made as accruatly as possable with definded terms.

Here is a general list of items that need to be created. This will become more complex as time porgresses, but should offer a good starting point.

Texture Generation
* Terrain 1056663390_climate.bmp
o Height Maps (part of the 3d Object Generation)
* Gas
o Cloud Generation for Normal Planets
* Cratered Moon / Cratered Terran ()

Object Generation
* Ice (crystalline structures) crystal.gif
* Comets / Asteroids (asteroid-prop-2.jpg)
* Planet Surfaces

Fractal planet generation (with source)
http://www.ehynan.com/java_applet/fract ... actApplet/
http://sourceforge.net/projects/fracplanet/ (Linux Only) (Anyone want to make a Windows version?)

Now that I scared everyone off, anyone willing to give this a try?
You do not have the required permissions to view the files attached to this post.
Last edited by mkruer on Sat Jan 24, 2004 9:21 pm, edited 1 time in total.
I know you believe you understand what you think I said.
But I am not sure you realize that what you heard is not what I meant.

Wing Commander Universe Forum | Wiki
Wing Commander: The Wasteland Incident
Xhivion

Post by Xhivion »

Sounds ggggreat! I agree that we shoudl do it now rather than later. This looks like a very very good way to get real planets .sorted/ Make sure they are relistic size tho (well... they are planets... so can be any size!!! lol)... i just want some nice biggg ones :) The manzorian swamp world.... oooo so .. big ... etc

This is going to ROCK!

Poping lazers in the cities will be fun too :).
Swibble

Post by Swibble »

If anyone seen the Orbiter space simulator(not a game), they have a perfect example of entering a planet as such. too bad its for windows though.

make some planets gas planets too.
Runner
Hunter
Hunter
Posts: 72
Joined: Thu Jan 09, 2003 6:55 pm
Location: Leipzig

Post by Runner »

Double Thumbs up should vegastrike ever decide to use fractals. I think it's the right way:

Use fractals to generate practically everything and then just add custom gamecontent like special planets, special objects, stations, ships and such.

And after all it might even simplify code a bit because once that fractal thing is running, it does many things with all the same code...

And after all, if it's possible to code it in assembler(sic!) back in the times of elite2&3 then it should be possible in C++ or Python or whatever. It should be even easier...

cya, Runner
Mikeeusa

Post by Mikeeusa »

Fractuals will KICK ASS for multiplayer too, oo look you added a new system to your server, the client just down loads the algo, o a new planet too, client downloads the less than 1KB algo! Oh look you added a new city to your planet... yep an algorithm,,,, o it uses new textures.... glad im on broadband :D....

Oh you added a new space quadrant... the algorithim is down the pipe in a small fraction of a second on dialup. (BTW for speech between players [radio mic] we can use Xiphous opensource speech codec http://www.speex.org/ it can do as low as 2kbit/s)...(the server should be all tcp (atleast as an option) so it can be pipped over SSH etc easily, world wide lan parties... and i like gaming under protection)...

Are You Ready for planets.... :)
eddyster

I like it!!!

Post by eddyster »

I used to play some of the earlier versions of VegaStrike, and coming back now it looks beautiful!!!

All sounds brill.
Wireless Caller
Merchant
Merchant
Posts: 43
Joined: Tue Mar 16, 2004 7:31 pm

Post by Wireless Caller »

looks cool..

just don't have over a billion of starsystems.

i know it wouldent be realistic but it would make a better gameplay.

i would say between 150-800 systems.
Stargazer
Insys Pilot
Insys Pilot
Posts: 2
Joined: Sun Jan 05, 2003 1:58 pm
Location: Starship Thor Heyerdahl, continuing voyage

Post by Stargazer »

Wireless Caller wrote:i know it wouldent be realistic but it would make a better gameplay.

i would say between 150-800 systems.


I agree, million systems could become an overkill with VegaStrike, although multiple billions (if not practicly unlimited) of systems can be done theoreticly.
1,000 systems or somewhere around there should in theory be enough for everyone in VS, methinks, although the milky way has some 200-400 billion stars in real-life.

Anyway, I also agree that if VS could get something like this running, it would become quite impressive. So, I'm all for StarSeed-technology and fractals as well! :D

Say, I wonder why so few is using this technology in our days - I mean, when we can generate a galaxy which can actually fit on a floppy-disk, all with unique random-textures, planet surfaces, and star-types, why is it used so relatively rarely?
Last edited by Stargazer on Wed Jan 28, 2004 11:25 am, edited 1 time in total.
"We have lingered long enough on the shores of the cosmic ocean.
We are ready to set sail towards the stars
" --- Carl Sagan.
--
Visit Noctis
Visit Orbiter
hurleybird
Elite
Elite
Posts: 1671
Joined: Fri Jan 03, 2003 12:46 am
Location: Earth, Sol system.
Contact:

Post by hurleybird »

I think that there should at least be an option for VS to continue generating systems. In elite you had an infininte number of systems, beacause the game would generate more whenever you got to the edge of known space.
zaydana
Site Administrator
Site Administrator
Posts: 478
Joined: Thu Jan 02, 2003 10:05 am
Location: Perth, Western Australia
Contact:

Post by zaydana »

the main reason we don't see this type of thing is the raw processing power required. To generate nice looking planets, it can take anywhere up to 10 seconds on a 1.5ghz machine :S Of course, we would probably have a lower detail level than that anyways. My point is, tho, to have a consistent universe generated every time you started a new game, the load time would be horendous. And then there is the problem of actually storing all the generated data ni memory. Hello 5gb swap file ;)

It would be possible to generate each system as you enter them, and then delete all the other systems while you are in jump transit... as the fractal algorithm would make it possible to get the same system every time. But that would give us a bit of a hard time with the dynamic universe. Our main problem with fractal universes isn't going to be the fractal algos, but finding a way to manage the memory required, and knowing when to keep systems in memory and when not to.
mkruer
Site Administrator
Site Administrator
Posts: 1089
Joined: Thu Jan 02, 2003 10:07 am
Contact:

Post by mkruer »

Well I guess here is the good thing. You have to take it from this stand point. What is the maximum resolution of a screen you will ever draw? Realistically maybe 1920x1440?
You do not have to do this every single frame; and you don’t have to generate things you don’t see, and if fast enough. you don’t have to save anything.

Theoretically, It would not take as long at you might think, because there is the option to scale the image and subdivide. This would be accomplished by treating the image not at Static Bitmap, but rather as a Dynamic Vector Graphic (PlanetGen *Cough*). Because you are in essence doubling the size you already have half the data, so the next size increase will only take 1/2 the time.

For you tech buffs.
I am running a stock AthlonXP 1800+ with 512MB ram.
It took my CPU 34 seconds (full CPU load) to generate both the Climate Map and the Relief Map, with 10 iterations and at a resolution of 2048x1024.

I don’t know about you, but with a little tweaking, I could easily see this being a background operation, in VS

Finally I have technology on my side. In the not two distant future all chips will have Dual Core and/or Hyper Threading, and eventually 64-bits. This is not fantasy, this is reality. And with this the final barrier will be broken. I want to start to implement now, not in 3yrs. The longer, we, as a community wait, the deeper a hole we will dig ourselves into and the harder it will be to dig ourselves out.

I guess in the end, there is no reason not to implement this. It will probably be at least a year before we see anything and by then
I know you believe you understand what you think I said.
But I am not sure you realize that what you heard is not what I meant.

Wing Commander Universe Forum | Wiki
Wing Commander: The Wasteland Incident
hurleybird
Elite
Elite
Posts: 1671
Joined: Fri Jan 03, 2003 12:46 am
Location: Earth, Sol system.
Contact:

Post by hurleybird »

Using fractals you only need to store in memory what you currently see. You do not generate the entire universe, you just generate the system you are in. When you enter a new system, you forget the old one and generate the new one from scratch. This new system will always be the same no matter how many times you regenerate it. This is the beuty of fractals.
zaydana
Site Administrator
Site Administrator
Posts: 478
Joined: Thu Jan 02, 2003 10:05 am
Location: Perth, Western Australia
Contact:

Post by zaydana »

yes, i understand that, but then what happens to the 'dynamic' universe? If the universe doesn't exist in memory, it will be interesting trying to keep it dynamic.

I suppose we could keep a record of all events from other systems since you last entered the system in memory, and then when you enter the system it would do a big chunk of processing to generate events, but then you have the problem of things like unexpected evenst in other systems and 'news' - where does it come from? If the system you are generating news for isn't in memory, your going to have a hard job getting the news to be related at all to the system. Also, if you take this aproach, the 'history' is going to end up being quite large, especially when you can never visit all 1 million systems ;)

I'm sure there are solutions, so lets get thinking. Or otherwise you might already have solutions, and i'm just a tad stupid (this is the more probably answer)...
hurleybird
Elite
Elite
Posts: 1671
Joined: Fri Jan 03, 2003 12:46 am
Location: Earth, Sol system.
Contact:

Post by hurleybird »

Well, personally I dont think we should fix what isnt broken. The entire universe does not need to be generated with fractals, if it were I dont think it would be much better than what we currently have now. About the only thing which would be needed to be generated would be planet surfaces.

Is there anyway that would interfere with the dynamic universe? I cant think of anything off hand which would.
pincushionman
ISO Party Member
ISO Party Member
Posts: 467
Joined: Mon Jan 13, 2003 9:55 pm
Location: Big, flat Kansas
Contact:

Post by pincushionman »

I think if someone wants to expand it to be able to generate anything, that's fine, just make it so pregenerated data always overrides the fractal. It would be useful in some mods, or maybe unstable wormholes might occasionally drop you into totally uninhabited systems, where a fractal would be used instead of generating and storing a whole bunch of "worthless" systems.

-pincushionman
Conquer space!
-pincushionman

---------------------------------------

Kansas really is flatter than a pancake!
www.improbable.com/airchives/paperair/v ... ansas.html
zaydana
Site Administrator
Site Administrator
Posts: 478
Joined: Thu Jan 02, 2003 10:05 am
Location: Perth, Western Australia
Contact:

Post by zaydana »

Hurleybird - the way a fractal universe would interfere with a dynamic universe is similar to the way in which a compressed program stops the operating system from running it. To actually do anything with any of the systems, you need to know what is in them. To do this, you need to 'unzip' (create) the system with a fractal algo. The way that this interferes with a dynamic universe is that it can't be dynamic if it can't be read. Of course, there are ways around this, we just need to think of them.

One possible solution is to store some really basic information in a save game file... even that could get to 50mb if there is a million systems and each has 50bytes of data, but at least that way we would be able to have the info needed for a dynamic universe in a file.

Its just a matter of thinking of the best solution.
mkruer
Site Administrator
Site Administrator
Posts: 1089
Joined: Thu Jan 02, 2003 10:07 am
Contact:

Post by mkruer »

Whoa pull back a sec. First I don’t think VS is the proper game for the millions of systems, and even on top of that, the fact remains that the more systems you have, the more generic each system on average should become. Put another way, you will/should only have say 800 exceptional worlds that have “stuffâ€
I know you believe you understand what you think I said.
But I am not sure you realize that what you heard is not what I meant.

Wing Commander Universe Forum | Wiki
Wing Commander: The Wasteland Incident
zaydana
Site Administrator
Site Administrator
Posts: 478
Joined: Thu Jan 02, 2003 10:05 am
Location: Perth, Western Australia
Contact:

Post by zaydana »

ok ok, you got a point. but just because we won't likely have a million systems, that doesn't mean we should make our code to cope with it. In fact, it is the oppisite, we should definitely make our code to cope with that type of stuff.

I also agree that XML is definitely not the thing for vegastrike... but neither do I think mySQL is. We nede to try and find (or make) a database optimized for continuously recieving scores of queries that provide a LOT of data. Also, it would be nice if it didn't have a huge footprint on the harddrive, or on CPU.
mkruer
Site Administrator
Site Administrator
Posts: 1089
Joined: Thu Jan 02, 2003 10:07 am
Contact:

Post by mkruer »

Give me a break. Have you even looked at MySQL to see just how much of this "Memory Foot Print" takes up? Wow a whole 8MB added.

To be fair though the MySQL does take more VM but there is a reason, the main difference is that now the whole galaxy table for Celestia is loaded up; All 100,000 stars in the current catalog. Where the standard Celestia loads NOTHING!

I think I have sufficiently blowing out the MySQL being too large.
You do not have the required permissions to view the files attached to this post.
I know you believe you understand what you think I said.
But I am not sure you realize that what you heard is not what I meant.

Wing Commander Universe Forum | Wiki
Wing Commander: The Wasteland Incident
zaydana
Site Administrator
Site Administrator
Posts: 478
Joined: Thu Jan 02, 2003 10:05 am
Location: Perth, Western Australia
Contact:

Post by zaydana »

whep, my bad. I have it on my process list as well ;) still, it is a lot bigger than it needs to be... and it grows considerably when it is in use. One question on how we would do it - would each time we need something be a query, or would we load the system into memory while we is in jump transit?
mkruer
Site Administrator
Site Administrator
Posts: 1089
Joined: Thu Jan 02, 2003 10:07 am
Contact:

Post by mkruer »

The only time you really need to have direct access to it is when you are pulling up information, not directly related to the system you are in; or if the system you are in is highly complex. But on top of that I want it for WCU as well because I found a neat trick with access I can use MS Access for RAD development and export the data directly to the MySQL tables. Now I can build a quick GUI add and change what I want and then save it back. Because of this I was going to save all the ships data. This is where MySQL would come in extremely handy again. I can effictivey do in month, what whould take years to do in the old way.

8MB core is still relatively small for the power behind it. And as VS becomes more complex. MySQL becomes even more obvious of a choice.
I know you believe you understand what you think I said.
But I am not sure you realize that what you heard is not what I meant.

Wing Commander Universe Forum | Wiki
Wing Commander: The Wasteland Incident
richard
Bounty Hunter
Bounty Hunter
Posts: 162
Joined: Mon Jan 26, 2004 9:29 am
Location: Melbourne, Australia
Contact:

Things to consider

Post by richard »

Hi, I'm new to Vega Strike, and am liking what I'm seeing a *lot*. I've got extensive Python experience (see my pet project, http://roundup.sf.net/). I'm looking forward to playing with the Python scripting angle with VS :) I've also played with some of the ideas you're tossing around in this thread.

First up, I like the idea of having fractally-generated planets - it means for each planet you really only need a single number as seed for the number generator used by the planet renderer (I would recommend that you code your own "random" number generator so that the results are the same regardless of platform / C library :)

There are some really neat extensions to the standard midpoint fractalisation method that may be used when you're working with a sphere. The method works something like this:

1. Run a plane through your sphere at some angle and offset from the sphere center. Alternatively raise or lower all the vertexes in the sphere on one side of that plane.
2. repeat 1 :)

This generates quite reaslistic-looking planets (and asteroids, if the raising / lowering is dramatic enough). It requires at least 1000 or so iterations to produce something realistic-looking, but you would be able to operate the changes on levels of detail and use other optimisations like pre-generating the planet, and using the result to generate a texture to be applied thereafter.

I have some C / OpenGL source that compiles on Linux that demonstrates this generation system, if anyone's interested.

On a different subject, I noted that MySQL was brought up as a storage mechanism. Let me suggest that you investigate something like sqlite (if you must use SQL) or metakit (if you're somewhat flexible). Both of these are significantly faster than MySQL, and since VS doesn't need multi-user support, there seems to be no benefit in the hassle of setting up MySQL.
Gamer, Python programmer
hurleybird
Elite
Elite
Posts: 1671
Joined: Fri Jan 03, 2003 12:46 am
Location: Earth, Sol system.
Contact:

Post by hurleybird »

Salutations! :D

You have no idea how much we could use someone for python mission scripting, any help you can give will be vastly appreciated.

Zaydana: what i was saying earlier was that using fractals for planet generation (not for the entire solar system) would not break the dyanmic universe. I dont think that the dynamic universe does anything with the planet terrain. Can you give me one example of how this would break the dynamic universe?
zaydana
Site Administrator
Site Administrator
Posts: 478
Joined: Thu Jan 02, 2003 10:05 am
Location: Perth, Western Australia
Contact:

Post by zaydana »

Fractals for planet terrain generation? That should be fine, why didn't you say so before? You probably did ;) O well, maybe I'll read it properly next time.
hurleybird
Elite
Elite
Posts: 1671
Joined: Fri Jan 03, 2003 12:46 am
Location: Earth, Sol system.
Contact:

Post by hurleybird »

About the only thing which would be needed to be generated would be planet surfaces.


yup, I did say that.

Anyway... Why even bother generating fractal solar systems if we already have a good database full of nasa data, and it would pose problems with the dynamic universe, whats the point of generating every single object with fractals when they can be done just as good without them?
Post Reply