   How to store Data of entire Worlds?
  Hi all,I could use some help here:I'm new to game programming and am currently researchingwhat the best method is for storing world data for a 3D engineI plan to create (www.mrpgs.net). Here's the outline:The 3D engine does not have to feature hi resolution or any newlighting or shading technologies. I need the 3D engine more for simulation and giving maximum information about the data of a world than for looking real or "sexy". Heck, for all I care it could be in VGA! ;-) - But it should be able to handle entire universes!I want to create an engine where one can travel space in a spaceship, with hundreds of planets but also have adventures on these planets, in cities, dungeons, or even be transformed to an ant and crawl inside an ant pile, etc.AND any changes made to the world by the player, such as leaving valuable objects behind, killing creatures or destroying landmarks, etc. should be saved.What I am really looking for now, before even deciding whattechnology to use to render this world is how to store such kindof data.Since I want to have entire universes, but also the ability tohave an adventure in a particular city / dungeon or even an ant pile, a lot of data will probably have to be generated procedurally. But some also by hand where this is necessary.I'm sure Level-Of-Detail is a VERY important rendering technology for this.But before I even get to rendering, my concern is: What is the best method of storing such kind of data? What kind of data storage technologies are there?I hear there such things as "Octrees" and "BSB trees"?Should data be stored in a Voxel-based manner? Are these thebest technologies available for this?Are there any books on how to best store data of entire universesall the way down to details such as an ant pile (for games orsimulators)?There seem to be a lot of books about rendering technologies, butin all those I can't find much information on how data like thiscould be stored for usage by a 3D engine.Regards,Markie   
  I don't know how you really expect to come up with the data for all these worlds in the first place, but ignoring that, you really don't want to store the universe's data all at once. No data structure in the world is going to help you if that's your intention. You're going to want to do stream loading on the fly and only load what you need. For instance if you're in space you really only need to know the relative location of all the planets/asteroids/moons, you only need to load the ones that are relatively close(for instance you could just load a few billboarded textures to represent planets until you get close enough for it to load and render an actual model.I've never built a game like this myself as it's not my main interest (just so you know, and can take my input in context).You could use BSPs or octrees when you get down to a planet (it really depends on what you're trying to do though). And you could use some sort of octree in space too to decide what to load (i.e. make huge quadrants and separate planets that way).For now I'd really suggest just getting the on planet OR the in space stuff working, then worry about connecting the two and expanding the universe.   ;  Hi dashurc!Cool! Thanks! :-)Quote:Original post by dashurcI don't know how you really expect to come up with the data for all these worlds in the first placeThis isn't my primary worry. Basically I want to make the "engine" most of all. It's supposed to be open source and it's supposed to be ableto load "modules" or "adventures", so my primary worry is not theactual content itself, but making an engine that can handle anyand all content made by others. It want it to be able to use either predefined / programmed data or procedural content.It's supposed to be an engine for turn based RPGs of any kind.Quote:Original post by dashurc, but ignoring that, you really don't want to store the universe's data all at once. No data structure in the world is going to help you if that's your intention. Check! :-) The point is exactly that I basically want no limit in the amount of data or detail the universe or worlds will be made up of. So yes, stream loading on the fly is the only way to go!:-)Quote:Original post by dashurcYou're going to want to do stream loading on the fly and only load what you need. For instance if you're in space you really only need to know the relative location of all the planets/asteroids/moons, you only need to load the ones that are relatively close(for instance you could just load a few billboarded textures to represent planets until you get close enough for it to load and render an actual model.Very cool, yes, I'm sure this is what I need! :-)Does anyone know any references or books which I coulduse to learn this or as example? :-)Quote:Original post by dashurcI've never built a game like this myself as it's not my main interest (just so you know, and can take my input in context).No you've helped a lot, really! Thanks!Someone else has mentioned stream loading on the fly to me in anotherpost I've made but I havn't thought about it in this way yet, to linkit with different kinds of other technologies depending on how muchdetail is needed.Quote:Original post by dashurcYou could use BSPs or octrees when you get down to a planet (it really depends on what you're trying to do though). And you could use some sort of octree in space too to decide what to load (i.e. make huge quadrants and separate planets that way).YES!!! This is what I was thinking about!! :-)Although I really don't know what Octrees and BSPs are yet,I had the idea of kind of making some kind of set up where Isort of box octrees or BSPs in other octrees / BSPs.Have one for the universe, then one for a solar system,one for a planet, etc. all the way down to ant piles.Again, the problem is not filling all those possiblitieswith data (yet), but just making it possible with an appropriatedata structure / engine in the first place.Is it possible to "box" octrees or BSPs inside otheroctrees / BSP's? If so to how many levels / how many times?As you said, it's probably not possible to have one singleoctree / BSP with ALL the data of the entire universe loadall at once, but would it be possible to load on the fly only a certain fracture or segment of ONE big giant octree / BSP which holds the data of the entire universe on the fly?Kind of like holding a certain segment of the ONE big giantoctree / BSP in memory like a window?Or is this totally impossible due to how octrees / BSPs arehandled? Do they have to be split up in multiple smallerones to stream load the needed data on the fly?Could or should such an engine work with a Spatial Database?Again, are there any good books on this topic?Quote:Original post by dashurcFor now I'd really suggest just getting the on planet OR the in space stuff working, then worry about connecting the two and expanding the universe.I'm not even starting programming yet, not even with space.First I want to know exactly what technologies are involved,available and which should be used.Thanks for your reply, it gave me much to think about!:-)One last question perhaps: Does anyone know an existing 3D Engine which could handle something like this?Greetings,Mark   ;  Universes? Are you sure you didn't mean solar systems?Storing data is actually pretty cheap. By the time you finish this massive undertaking of a game, the average PC will probably boast 32+ gigs of memory. So unless the amount of data you place into single entities is exaggerated, you literally will be able to store the entire universe. Or at least its states. That's not including media resources, like textures and sound effects. Those you'll still need to load on demand. That is, unless everything will share the same basic resources.Any 3D engine can handle something like this. The main strain of creating an extremely detailed universe will be on the artists and programmers.   ;  There was an article somewhere here about using random number generators to generate an entire universe dynamically.The advantage is that this requires almost no space at all, since random numbers are repeatable (i.e. if you use a specific seed value, you always get the same sequence). So all you have to do is store one seed from which your whole world starts. This also places no limit on the amount of detail in your worlds, or any other limits what-so-ever. Which is to say, this is pretty cool.The hard part is creating algorithms that take these generated numbers and dynamically create world data based on them, in such a way that the world will look realistic and be fun to play in. I once made a tiled 2D game that generated its simple levels randomly, and I couldn't for the life of me figure out how to make the resulting levels playable, because something always wound up blocking player's way. I solved this problem by giving the player a "shotgun" with which they can "blow up" anything that blocks their path :) I used current time as a seed, so levels would be different every time.   ;Quote:Original post by KestUniverses? Are you sure you didn't mean solar systems?Yep. :-)I just want to have the possibility of allowing an RPGwhere players travel entire universes... Eh, O.K., ...I'll settle for GALAXIES. Is that a deal? ;-)Quote:Original post by KestStoring data is actually pretty cheap. By the time you finish this massive undertaking of a game, the average PC will probably boast 32+ gigs of memory. So unless the amount of data you place into single entities is exaggerated, you literally will be able to store the entire universe. Or at least its states. That's not including media resources, like textures and sound effects. Those you'll still need to load on demand. That is, unless everything will share the same basic resources.Any 3D engine can handle something like this. The main strain of creating an extremely detailed universe will be on the artists and programmers.It's possible to create vast spaces procedurally.Such as the old game ELITE, one of the first 3D games for home computers.In this article you can read that it was originally possible and plannedto ship the game with 282,000,000,000,000 galaxies with 256 stars each.And it would all fit in less than about 30KB or RAM..! :-)My plan is to make such things possible. And then try to combinesuch procedural content with actually programmed content, enablingplacement of programmed content / adventures in procedural galaxies.For instance. Really I just want to keep all options open since Iwant to make a simulator for ALL pen and paper RPGs, which also entailsALL possible (and impossible) adventures.I don't want to kill this with hardware, even if finishing thisproject will take much longer than just waiting for the 32Gig RAMPC. I want to solve the problem with smart coding which handlesor manages the problem.The hard part is probably finding the correct data structure(s)as well as combining procedural and non-procedural content fromuniverses to ant piles... ;-)Quote:Original post by ValManThere was an article somewhere here about using random number generators to generate an entire universe dynamically.The advantage is that this requires almost no space at all, since random numbers are repeatable (i.e. if you use a specific seed value, you always get the same sequence). So all you have to do is store one seed from which your whole world starts. This also places no limit on the amount of detail in your worlds, or any other limits what-so-ever. Which is to say, this is pretty cool.Perhaps that was the article I linked above about Elite(Masters of their universe)?Yes, I find this extremely cool as well.I can use that to fill the galaxies / worlds with data. And I want to combine that with allowing programmers / content providers to insert hand-made content anywhere within a procedurally generated universe.However, my problems now are more about what kind oftechnologies I need to study and buy books about, probably first and most important of all (if this is what the heartof a program really is?), what kind of data structure(s) would allow streaming loading of needed data on the fly when one travels from a galaxy to a planet, to a forest, and then to an ant pile (in cases where non-procedural content is used).Thanks for all your replies so far!Greetings,Mark;  Not to burst your bubble or anything, but this is a huge undertaking for someone who has not had much programming experience.While it is possible to procedurally create large universes, to the detail you describe would need an incredible amount of data to process, cull, blend, etc. Even if you imagine this game development lasting many years and when the release date is up home PCs have 32gb of ram, you still have the issue of not only creating the world, but should you have procedural content and hand made content, knowing how to blend the two would be an incredible task.The problem with procedural content is that generally, the programmer has no idea what the finished product will look like. One project that I have been following, and you would probably be interested in is Infinity: The quest for earth, the developer said himself that one of the best things he enjoys about his engine was flying around planets and finding areas that he didn't even know COULD exist. Now imagine a world in that context a world, and now try to place ant mounds.I'm not saying it's not possible, and I'm not saying don't do it, I'm merely pointing out that this is a subject that many people spend half their lives researching for various reasons. Just don't expect to have anything like you describe up and working in the near future (or distant future?).Since you have little programming experience, I would suggest a better idea would be to keep this project as a long term (very long term) goal, and use it to guide many much smaller projects. For example one good idea might be to generate some algorithm to randomly place spheres around in a solar system, then add moons and comets etc. Break your ideal up into many smaller projects and the problems you come up against with them will teach you many things that will help you when you're finally ready to attempt your larger project.I say all this because the questions you ask here probably haven't even been answered yet. You will find research papers and games that have implemented subsets of what you describe that will surely help, but generally, the best way to answer these questions is to do your own research. That is, try many little projects and you will start building an idea of how things will work.Other than that, good luck!;  Hi instiKt,Quote:Original post by instinKtNot to burst your bubble or anything, but this is a huge undertaking for someone who has not had much programming experience.Naw, you're not bursting my bubble. ;-)- Fortunately for me I have enough programming experience to knowthat I have no idea of what I am getting myself into! :-)But I can guess this is a "life" project which I canwork on my entire life and never finish. Hence it will beopen source (once there is any source worth "opening"! ;-)You might ask: Why bother in the first place if it's suchan oversized task / idea?Simple: I've been carrying this idea around with myselffor over 20 years now. It's obvious nobody else is goingto do this. So it's try it myself now or forget about it.Also I've wanted to really learn how to program games, butthat itself is also an oversized task. I simply never feltthe motivation or need to do so. Not for itself. Not justto be able to "program games". I'm a very "task"-driven type of person. If I have to learn something I don't know what I can use it for, I'm practically unable to learn it.On the other hand, if I *want* something, I can literally climbmountains of stuff to learn... :-)Since I've been interested in learning how to program games(I've been programming PHP several years and I know some C)for just as long but just laked the motivation or reasonfor really doing it and since I always wanted to play somethinglike the MRPGS which I plan, this is hitting two flies in onesweep for me. Learn the technologies needed (the way I canlearn, with a task at hand to do) and try to make or at least start MRPGS myself.If I fail at either, hopefully I will have had fun on myway and learned some interesting things. I don't think I willregret the very massive investment of time. - You have todo something with your time and I might as well do this.- But that's a personal matter I guess. ;-)Quote:Original post by instinKtWhile it is possible to procedurally create large universes, to the detail you describe would need an incredible amount of data to process, cull, blend, etc. Even if you imagine this game development lasting many years and when the release date is up home PCs have 32gb of ram, you still have the issue of not only creating the world, but should you have procedural content and hand made content, knowing how to blend the two would be an incredible task.Yes, it's an incredible task.But I see it as a challenge! I simply refuse togive up until I *believe* to know the facts myselfthat it's not possible. And that means learning allthe technologies involved. ;-)Knowing how to blend the massive procedural content withhand made content comes first though. This is basically whatI see pretty much at the heart of the project. - Blendinghand made and procedural content, or in other words allowingreplacement of procedural content anytime and anywhere andmanaging the updating of the universe, or rather subspaceswhich are currently needed. To me, these seem to be the most important problems for the game engine at this time. Andthey are very closely connected with how data should be handled.Procedural content generation, as well as display througha 3D engine are secondary at this time. I'll deal with thatlater! ;-)Quote:Original post by instinKtThe problem with procedural content is that generally, the programmer has no idea what the finished product will look like. One project that I have been following, and you would probably be interested in is Infinity: The quest for earth, the developer said himself that one of the best things he enjoys about his engine was flying around planets and finding areas that he didn't even know COULD exist. Now imagine a world in that context a world, and now try to place ant mounds.I'm not saying it's not possible, and I'm not saying don't do it, I'm merely pointing out that this is a subject that many people spend half their lives researching for various reasons. Just don't expect to have anything like you describe up and working in the near future (or distant future?).Thanks for your concern!I see you like my idea if you are in such support of mein having patience with it! :-) Thanks! :-)And not to worry! I realize this is a "life" project.Perhaps I won't even see the or any "end" of it.I am fully aware of this. - Currently I am orderingbooks from Amazon.com like I wanted to buy the company...;-)I realize just reading all those books will take a few yearsitself already. But that's not stopping me from "attacking on allfronts" so to say and trying to gain knowledge and resources as quickly as possible and / or by other means than just books alone. :-)Quote:Original post by instinKtSince you have little programming experience, I would suggest a better idea would be to keep this project as a long term (very long term) goal, and use it to guide many much smaller projects. For example one good idea might be to generate some algorithm to randomly place spheres around in a solar system, then add moons and comets etc. Break your ideal up into many smaller projects and the problems you come up against with them will teach you many things that will help you when you're finally ready to attempt your larger project.I say all this because the questions you ask here probably haven't even been answered yet. You will find research papers and games that have implemented subsets of what you describe that will surely help, but generally, the best way to answer these questions is to do your own research. That is, try many little projects and you will start building an idea of how things will work.Other than that, good luck!Thanks a lot! :-)))Yes, perhaps you're right, the questions I am asking here perhaps have not been answered yet. Or not in thisparticular context. (Hence I have to bother with tryingto make this thing myself... ;-) It's probably assemblingexisting solutions to many sub-problems which will deliver the final answer.I fully agree, breaking the task up into smaller projects is the *only* way to go about this. To keep the fun-factor and thus my motivation up, I'll pretty much do whatever seems most important or interesting at a given time. I know I'll have a lot of fun learning how to create procedural or hand-made solar systems, but right now I'm much more interested in the core and heart of the idea and if it's possible to do the whole thing the way I want. - And how.I have enough programming experience that I *believe* torealize that there is NO!!! replacement for sufficientplanning ahead, ESPECIALLY in large scale projects.The bigger the project, the more important planingahead BEFORE starting is. And the importance does notjust increase linearly with increasing project size! ;-) In small projects, you can easily re-write a gameengine. The bigger a project gets, the less you wantto do that. So now I face the somewhat difficult taskof trying to learn if the things I plan are possibleand if so, with what technologies AND trying to get toknow enough about those technologies to know IF I actually have to learn about them in the first place or not... ;-) - It's a chicken and egg problem for me,no doubt.I am trying to solve it the "natural" way. That is "attack at all fronts"! Try to bite into the problem from all sides at once if you don't know where to start. Eventually you might learn which is the right place to start. So currently I'm ordering a lot of books to give me an overview of what I need to know and I hope to minimize ordering books which I don't need. - Even if I do in general like books.;-)Regards,Mark;  I actually think such a project can be tackled rather easily. Once you're able to randomly generate a single solar system, then you're pretty much done with the bulk of the work. Just repeat that algorithm hundreds or thousands of times and assign them random hyperspace/lightspeed/subspace coordinates.The secondary task would be to randomly place aliens, items, events, minerals, or whatever types of resources your players will be looking for and coming into contact with while exploring. And the larger your universe, the more of these you'll need.The secondary step is absolutely essential. No matter how cool your typical worlds are, players will become bored with them after exploring a handful. It's all about the unique things that can happen to them as they explore. Without those, there's no incentive (apart from the end goal of the game) to keep wandering around.   ;  Well, what you describe has kinda already been done by a nifty little freeware game called Noctis. http://anywherebb.com/noctis.html   