Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[MrGimp]

Yo.  So I program C++ and I know a lot of you other DF types also program.

So Im making this galaxy simulator...like a Drake Equation calculator that allows you to go in and travel around and see the result.

Anyways, its made up of structures within structures within structures within structures.  Every structure has a pointer specific to its tier within the nested structures.  Obviously the galaxy is very big, and to map the array of about a trillion squares and a couple hundred billion stars it takes a lot of memory.  You cant straight up make an array of 'array[1000][1000][1000]' or something, thats too big and C++ wont let you do it.  But you can do structures of these arrays, and then structures of these structures.  Thats what Im doing as my work around.

I have the galaxy divided into 4 quadrants, which have 100 regions of magnitude 3, which each have 100 regions of magnitude 2, which have a 100 regions, and each region is divided into 100 sectors with 5 planes of 400 squares. 

Got all that?

Basically its 4*100*100*100*100*5*400 = 800,000,000,000 characters within the total array.

My problem is, I must be overloading something.  It was working fine when I had gotten to structures of structures.  But after the third layer of structures it started blowing up.  The debugger says its fine.  It builds and compiles properly.  When I run it however, it gives me an error and asks if I want to send a report to microsoft.  Pfff.  It gives it to me 6 times before closing actually.

So whats the limit on the size?  Am I using an insane amount of memory to do this task?  I thought nested structures were the way around that?  Its blowing up before the program even starts, it doesnt even get to the nested structures.

If anybody can help that would rock.

[Gigalith]

Basically its 4*100*100*100*100*5*400 = 800,000,000,000 characters within the total array.

Am I using an insane amount of memory to do this task?

Uh, yeah. That's about 0.8 PETABYTES of ram.

Either scale down your plans, or use seeds and generate things only when needed.

[MrGimp]

Basically its 4*100*100*100*100*5*400 = 800,000,000,000 characters within the total array.

Am I using an insane amount of memory to do this task?

Uh, yeah. That's about 0.8 PETABYTES of ram.

Either scale down your plans, or use seeds and generate things only when needed.

Hehe....you should have seen how much I was using before I figured out pointers.  I thought pointers would be the work around for the problem, so I could print only sections of the array one at a time.  But yeah....if Im initializing even one pointer then its gonna set aside that memory. 

I thought about the seed idea...but Im not sure how to code that.  How do I make it remember a location once its printed?  I could make a copy funtion, but how would I tie that memory down with its point in the super huge galactic array so that I could revisit the same site?

[MrGimp]

Are the pointers the problem because of having to initialize a new block of memory?

I.E. - could I do it the same way Im doing now, but with straightforward structure notation?  Because right now it fills each sector one at a time, and cycles through each region within each region.  So if I wasnt using pointer notation could I do it that way?

Errr....I mean...could I do it *theoretically* of course....I would have to write probably a billion lines of code to do it without pointers wouldnt I?

[qwertyuiopas]

Most games that go to such huge scale use a seeded randomization approach where it gets a random number based on(or seeded by, if you use a default random number function) the position and maybe some universe uniqueness factor.

But storing a 1000³ array for it is still 1GB even if you only use a single char to store each planet.

Plus, with a location-seeded approach, you have no limits.

Although if the player can change a planet, the changed planets must be stored to some extent, few players would even visit 100 of them, and yu can guarentee that 100000 is beyond the possibilities of a player to do in a lifetime.


This approach is used by noctis, and the location-seed technique has been used for decades where storage was a concern, like old console games, or full simulation is impossible, like any game that tries to store a huge ammount of space.

(had "new post" twice after writing that)

[MrGimp]

But storing a 1000³ array for it is still 1GB even if you only use a single char to store each planet.

*shakes fist at sky*

Why'd they make the galaxy so big!!! 

Sigh....I guess I cant get a fully articulated and fleshed out galaxy the way I was envisioning it.  Maybe in a couple decades when supercomputers fit in the palm of your hand huh?

I like your idea of storing only a hundred or so locations.  Thats a nice compromise, gen on the fly, maybe store critical locations like Earth or some such BS...but other than that just rewrite over old sectors.  Nice.

[MrGimp]

OOOOOOOOOHHHHHHH!!!!!

IDEA!!!

I could do the Drake Equation as a seed (it already was going to be once I had the array pinned down) and gen locations on the fly, storing the last hundred visited sectors or something.  But then have a command to save a location permanently, so if Im exploring and I find something cool, I can go to the hyperspace computer (or whatever) and in game give a command to save the location, and then I can have maybe a dozen or more of those permanently saved locations in addition to the last 100 or so visited.

[mainiac]

So if a planet is boring you can fly away and return later to find an intergalactic civilization sprouted up?

[qwertyuiopas]

You could probably get away with storing 100 000 without too many issues, depending on how much data is stored.

I know that noctis has a function or something that takes the X, Y , and Z, and generates a star, often with planets, but more often just blank space, with a weighted probability for empty space based on galaxy distribution or something of the sort so that the center is more clustered.
http://en.wikipedia.org/wiki/Noctis
It also applies the position-generator to the surface of planets making each planet a nearly boundless but still spherical(I think that in either the current or the planned version you could walk all the way around a planet and end up back where you started) and it doesn't have to store the specific terrain, only generate it when you visit.



Dwarf fortress stores a random seed for empty areas to save space as well, so it's a well used method of ultimate compression.


Oh, after reading the wikipedia article, it appears that noctis is open source.






You really have two choices:

Generate new planets when they are needed and store the most recent.


or


Generate them every time, maybe storing some information for recent alterations, but base the seed on their position so that they will be the same every time.


The first is better for smaller games as it gives variety to each game, or games where dynamic data must be stored about them such as player hostilities and such, more for a limited RPG lke simulation where the player may interact with the locals, while the second is better for exploring games that encourage players to keep moving to see what is out there and the player is unable to change the enviroment.

A hybrid of a sort would also work, storing player changed data about a sector while leaving things like history and unvisited parts to be generated when needed and discarded if nothing has changed when the player leaves.

[MrGimp]

Update on this project...


Ive been working on it for my C++ final, and it is much much more advanced than where it was when I posted this.  I got around the memory problem.  Stars get mapped out with seeds, and one local sector of stars is filled at any one time.  It then outputs that sector to a text file with the sector coordinates and then the character array below it.  It can then reload from that line in the text file if you revisit the same sector.

At least, its close to doing that.  Thats the idea Im working towards.  I almost have it all there.  Im sure you could still blow up the text files memory, I dont know what would happen then....but you'd have to spend days running this program to do it.

[Mr Tk]

First what messages does it give you when it blows up?

Second when you are saving the sector into a text document who do you do with the sector which is still residing in memory? Do you make sure that it is deleted? Because if are saving the sector but not unloading it from memory it's possible that you have orphaned sectors running around in memory. So through the process of load and save for each sector you may not be free the memory for the saved sector. (I'm sorta guessing what your program is doing at this point so this may not be correct. It also depends on how you are storing your sectors as well.)

A program like valgrind should be able give you an idea if any memory is not being freed.

[MrGimp]

Its not blowing up anymore, I solved that problem.  I was just saying that if you visited enough sectors, and output enough character arrays onto the text file, Im pretty sure you could blow up the text file.  I doubt notepad can store 20 gigabytes in one text file.

Maybe it can I dunno....I wouldnt expect it to though.  It might just overwrite data rather than blow up though, thats always a possibility.

I dont think I have stray memory leaking out.  Not on this program at least.  Ive coded many a buggy leaky program before, so I know what not to do at this point.

My main problem now is getting the character arrays to load back up properly.  I had finally gotten it working, then I tried to rewrite the code to make it more efficient and to fix one small bug.  Now it doesnt work anymore, and Im racking my brain trying to find the problem.  Im gathering that C++ doesnt like me putting while loops inside for loops, but thats the easiest way for me to do this!  Argh!

If anyone has done something like this before, how would you program an input from a file reading a very large character array that began with the '[' character and ended with the ']' character (like the DF raws but, 1500 characters long)?  Whats the most efficient easiest way?

[Virex]

If it only contains parts enclosed in brackets, you could use a while loop with char = ] as the end condition. That way you don't even need to start with [. Just use the while loop to load the chars into an array or string (or vector if you can't predict the size beforehand).

[MrGimp]

If it only contains parts enclosed in brackets, you could use a while loop with char = ] as the end condition. That way you don't even need to start with [. Just use the while loop to load the chars into an array or string (or vector if you can't predict the size beforehand).

Yeah that would work....then I could take the vector and use strstr to find the beginning of the character array right?

Actually, this is good....Ive never used vectors, but I think I understand them (and Ill never learn about them without trying em out).  So I could take a vector and load it up one character at a time with the entire sector output.  Then strstr through the vector looking for the matching galactic coordinates.  If it finds them, then another strstr through the vector again looking for the beginning of each of the ten size 1500 character arrays that make up each sector.

The complications are thus....

The output to the sectors text file looks like this....

<123412341>
[...extrememly long char arrays...]
[...extrememly long char arrays...]
[...extrememly long char arrays...]
[...extrememly long char arrays...]
[...extrememly long char arrays...]
[...extrememly long char arrays...]
[...extrememly long char arrays...]
[...extrememly long char arrays...]
[...extrememly long char arrays...]
[...extrememly long char arrays...]

Now multiply that by several dozen, hundred, or even thousand.  Thats what the sectors.txt file looks like after some exploring.  I want the vector to leave out the '[', ']', '<' and '>'s.  I want to strstr just for the nine digits of the galactic coordinates, then load the sector structure with the character arrays one at a time for each of the ten z-levels in a sector (by searching for '[' characters).

As you can see this is a very tedious process.  Im sure theres got to be a better way.  Maybe I could do it without the deleniating characters?  Thats how I was doing it before actually.  But that causes more handholding during the search for the right inputs. 

My brain hurts now.

[Virex]

You can do that with a sinlge if statement:

some metacode:
I = 0
while !(end of file) //or whatever you want to stop loading at.
{
while (C != ] )
{
C = (char number I from file)
if (C != [ && C != ] )
add C to vector
}
I++
}

That ought to leave out the [ and ]. You can construct a similar structure for loading the coordinates.