Simple question for you all, take a game like Dwarf Fortress, Minecraft, Infiniminer or Terraria (or any like them in some regard). How exactly would be the best way to store all the pieces of the world in memory, assuming a number of them over 2 million (low for Minecraft and Terraria)?
A standard array would be a huge sink, especially assuming several variables making up the class behind the pieces, even assuming just an array of pointers, you're looking at 8 million bytes in a straight run on memory space.
A linked list would consume even more as now you're adding two more 4 byte pointers to each element of the list, now looking at 24 MB.
I don't quite know how much a vector would use.
Even assuming the pointer space itself is low, you still need to link to now 2 million or more individual block classes (assuming the ability to individually interact) looking at possibly a couple gigabytes of total RAM taken unless I'm looking at this all wrong.
[QUOTE=StealthArcher;33728204]Simple question for you all, take a game like Dwarf Fortress, Minecraft, Infiniminer or Terraria (or any like them in some regard). How exactly would be the best way to store all the pieces of the world in memory, assuming a number of them over 2 million (low for Minecraft and Terraria)?
A standard array would be a huge sink, especially assuming several variables making up the class behind the pieces, even assuming just an array of pointers, you're looking at 8 million bytes in a straight run on memory space.
A linked list would consume even more as now you're adding two more 4 byte pointers to each element of the list, now looking at 24 MB.
I don't quite know how much a vector would use.
Even assuming the pointer space itself is low, you still need to link to now 2 million or more individual block classes (assuming the ability to individually interact) looking at possibly a couple gigabytes of total RAM taken unless I'm looking at this all wrong.[/QUOTE]
In my game, each block is a mere byte.
only a few chunks of the world are loaded at any time. When you move in a direction, it'll unload the chunks that are further away from you and start loading the chunks in front of you. And I think Minecraft just goes for the 3d array approach, but I'm not sure as I haven't actually ever looked at the source.
SVOs seem to be the most efficient method of storage, but I assume it's not much better if most of the world is solid. [url]http://en.wikipedia.org/wiki/Sparse_voxel_octree[/url]
[QUOTE=Jookia;33728142]I agree, but at the moment Clang is bugged so I can't use it. :([/QUOTE]
well, I _am_ writing this on OS X, so I'm using the one from XCode :v:
[QUOTE=StealthArcher;33728204]Simple question for you all, take a game like Dwarf Fortress, Minecraft, Infiniminer or Terraria (or any like them in some regard). How exactly would be the best way to store all the pieces of the world in memory, assuming a number of them over 2 million (low for Minecraft and Terraria)?
A standard array would be a huge sink, especially assuming several variables making up the class behind the pieces, even assuming just an array of pointers, you're looking at 8 million bytes in a straight run on memory space.
A linked list would consume even more as now you're adding two more 4 byte pointers to each element of the list, now looking at 24 MB.
I don't quite know how much a vector would use.
Even assuming the pointer space itself is low, you still need to link to now 2 million or more individual block classes (assuming the ability to individually interact) looking at possibly a couple gigabytes of total RAM taken unless I'm looking at this all wrong.[/QUOTE]
I don't see why a block would need to take more than 2 bytes per block. 2 million 2 byte blocks is only ~4Mb
[QUOTE=robmaister12;33728276]only a few chunks of the world are loaded at any time. When you move in a direction, it'll unload the chunks that are further away from you and start loading the chunks in front of you. And I think Minecraft just goes for the 3d array approach, but I'm not sure as I haven't actually ever looked at the source.
SVOs seem to be the most efficient method of storage, but I assume it's not much better if most of the world is solid. [url]http://en.wikipedia.org/wiki/Sparse_voxel_octree[/url][/QUOTE]
You're still looking at a huge number of blocks in memory at any time.
Minecraft: 9 chunks in any direction around you diagonals count as one 18*18 chunks (324) 16x16x128 (32768) blocks in a chunk for over 10 million blocks in memory.
Terraria keeps an entire world in memory at a largest size of 8400 x 2400 blocks = 20 million
[editline]14th December 2011[/editline]
[QUOTE=thisBrad;33728308]I don't see why a block would need to take more than 2 bytes per block. 2 million 2 byte blocks is only ~4Mb[/QUOTE]
Block 2 byte ID (1 byte limits you to 255 maximum types)
Block destruction and damage data
Entity flag
draw flag
lighting flag
etc.
You can rack up bytes of memory pretty quick when you want the world to be modifiable
[QUOTE=StealthArcher;33728405]You're still looking at a huge number of blocks in memory at any time.
Minecraft: 9 chunks in any direction around you diagonals count as one 18*18 chunks (324) 16x16x128 (32768) blocks in a chunk for over 10 million blocks in memory.
Terraria keeps an entire world in memory at a largest size of 8400 x 2400 blocks = 20 million
[editline]14th December 2011[/editline]
Block 2 byte ID (1 byte limits you to 255 maximum types)
Block destruction and damage data
Entity flag
draw flag
lighting flag
etc.
You can rack up bytes of memory pretty quick when you want the world to be modifiable[/QUOTE]
Assuming you pack flags into bits..
2 byte ID,
32 bits of flags
4 bytes of block destruction
4 bytes of some other data
5 million of those blocks is only 66MB.
20 million ~267MB. It's getting up there but since most people have a few gigs of ram, I wouldn't worry too much.
[QUOTE=thisBrad;33728652]Assuming you pack flags into bits..
2 byte ID,
32 bits of flags
4 bytes of block destruction
4 bytes of some other data
5 million of those blocks is only 66MB.
20 million ~267MB. It's getting up there but since most people have a few gigs of ram, I wouldn't worry too much.[/QUOTE]
Okay, yes, agreed, but it's not the question I asked, I wanted to know the best way to store it in memory. An array is clumsy and requires a large empty row of memory, a linked list consumes even more memory at those numbers (10 million plus). A vector i don't know enough about.
[QUOTE=thisBrad;33728652]Assuming you pack flags into bits..
2 byte ID,
32 bits of flags
4 bytes of block destruction
4 bytes of some other data
5 million of those blocks is only 66MB.
20 million ~267MB. It's getting up there but since most people have a few gigs of ram, I wouldn't worry too much.[/QUOTE]
I packed some of Terraria's fields to save space. Went from 600MB to 200MB of memory used but cpu usage went through the roof. Large maps would take 5-15 minutes to generate instead of the usual 1 minute.
[QUOTE=high;33728720]I packed some of Terraria's fields to save space. Went from 600MB to 200MB of memory used but cpu usage went through the roof. Large maps would take 5-15 minutes to generate instead of the usual 1 minute.[/QUOTE]
Generation speed is less important then play speed.
For most cases, you don't really need more than 1 byte per tile. Those respective tile types can hold specific behavior per-type without having to add much more data, or any at all into a structure. Damage and such shouldn't even be considered in my opinion, you can get away with creating "health" in certain ways without actually storing health anywhere.
As for the 20 million ~200+MB, that sounds about right; I remember doing server scaling at Brohoster and the prices you pay for game servers are inversely proportional to available server memory (for the most part). The prices for Terraria servers are a little high for some people due to memory consumption.
I don't know if this will ever be important to any of you, but a really big lesson I learned from that experience is that if you create a successful game, and want to see a lot of game servers up and running for it, you'll probably see more of them if your memory requirements are lower, considering that's essentially the largest factor for pricing game servers for them. That and CPU consumption.
Sorry. GSP ramblings. :c It's weird to think about now.
[editline]14th December 2011[/editline]
GSP page king.
[IMG]http://i.imgur.com/d30ba.png[/IMG]
[QUOTE=amcfaggot;33728873]For most cases, you don't really need more than 1 byte per tile. Those respective tile types can hold specific behavior per-type without having to add much more data, or any at all into a structure. Damage and such shouldn't even be considered in my opinion, you can get away with creating "health" in certain ways without actually storing health anywhere.
As for the 20 million ~200+MB, that sounds about right; I remember doing server scaling at Brohoster and the prices you pay for game servers are inversely proportional to available server memory (for the most part). The prices for Terraria servers are a little high for some people due to memory consumption.
I don't know if this will ever be important to any of you, but a really big lesson I learned from that experience is that if you create a successful game, and want to see a lot of game servers up and running for it, you'll probably see more of them if your memory requirements are lower, considering that's essentially the largest factor for pricing game servers for them. That and CPU consumption.
Sorry. GSP ramblings. :c It's weird to think about now.
[editline]14th December 2011[/editline]
GSP page king.[/QUOTE]
This is why I'm asking.
I'll still need data for damage due to the game mechanics, but yes, I can probably have the blocks reference structs/classes of data for their ID number (which is only 2 bytes), so that solves the consumption angle. I still would like opinions on the best way to actually store this though and it's surprising how much came out of this without the actual question being answered.
[QUOTE=nick10510;33728910][IMG]http://i.imgur.com/d30ba.png[/IMG][/QUOTE]
That is an intriguing menu
[QUOTE=StealthArcher;33728997]This is why I'm asking.
I'll still need data for damage due to the game mechanics, but yes, I can probably have the blocks reference structs/classes of data for their ID number (which is only 2 bytes), so that solves the consumption angle. I still would like opinions on the best way to actually store this though and it's surprising how much came out of this without the actual question being answered.[/QUOTE]
I'd personally probably have a secondary dictionary of tiles which are damaged, and their health. This way it's not tied to the tile structures directly in that you could have a bunch of tiles with full health (which you don't care about), but as a result, they take up space when saving this to a format, because the health value has to be known.
With that bridge crossed, you now have an array of only tiles that are damaged, thus reducing the overall save data dramatically.
[QUOTE=amcfaggot;33729203]I'd personally probably have a secondary dictionary of tiles which are damaged, and their health. This way it's not tied to the tile structures directly in that you could have a bunch of tiles with full health (which you don't care about), but as a result, they take up space when saving this to a format, because the health value has to be known.
With that bridge crossed, you now have an array of only tiles that are damaged, thus reducing the overall save data dramatically.[/QUOTE]
This is all very wonderful ideas, but I'm still not getting an answer to my original question :v:
I think I'll just roll with a self written LL class at this point.
[QUOTE=ZenX2;33729114]That is an intriguing menu[/QUOTE]
There's a video of it a few pages back, its either page 36 or 26.. one of those.
[QUOTE=StealthArcher;33728997]I still would like opinions on the best way to actually store this though and it's surprising how much came out of this without the actual question being answered.[/QUOTE]
There is no best way. You must simplify your problem right off the bat to even approach something like this.
If your data is dense and has embarrassingly high entropy but small range (or if your data has a small domain), use arrays. Several of them. Store culled arrays to the disk. Arrays are usually arranged into chunks based on locational proximity for easy culling (e.g. "3d" array in Minecraft).
If your data is low entropy but modifiable, a hybrid approach involving procedural generation, SVOs, and/or arrays as leaves of the aforementioned SVOs may be more appropriate, albeit more complicated to implement.
If your data has a wide range, embarrassingly high entropy, and high density, then you need to re-think your data.
[QUOTE=Night-Eagle;33729414]There is no best way. You must simplify your problem right off the bat to even approach something like this.
If your data is dense and has embarrassingly high entropy but small range (or if your data has a small domain), use arrays. Several of them. Store culled arrays to the disk. Arrays are usually arranged into chunks based on locational proximity for easy culling (e.g. "3d" array in Minecraft).
If your data is low entropy but modifiable, a hybrid approach involving procedural generation, SVOs, and/or arrays as leaves of the aforementioned SVOs may be more appropriate, albeit more complicated to implement.
If your data has a wide range, embarrassingly high entropy, and high density, then you need to re-think your data.[/QUOTE]
It's probably my ongoing sleep deprivation but quick reminder what entropy in programming data is again?
(Dammit I should remember this)
Entropy is loosely defined as I use it.
Short answer: disorder
A loose in-context interpretation:
If your data is all procedurally generated with a O(log(n)) time algorithm, your data has very low entropy.
If your data is procedurally generated with a O(n^2) time algorithm, your data has moderate entropy.
If your data is generated by a (creative) artist or a O(2^n) time algorithm, your data has embarrassingly high entropy.
[QUOTE=StealthArcher;33729334]This is all very wonderful ideas, but I'm still not getting an answer to my original question :v:
I think I'll just roll with a self written LL class at this point.[/QUOTE]
I would have thought by now you would understand that a straightforward spacial partition is fine. Even for numbers as high as 32 million tiles, which was discussed earlier. The reason I mentioned secondary, or extraneous data is because how else are you going to store values like that? That's probably more important, because you're going to be hit by memory consumption concerns with data past individual tile types.
Use plain arrays with your own choice of spacial partitioning, store extraneous tile data in other arrays so they're additive, and not some sort of tile member variable.
[QUOTE=StealthArcher;33729334]I think I'll just roll with a self written LL class at this point.[/QUOTE]
Why not std::list?
[QUOTE=amcfaggot;33729858]I would have thought by now you would understand that a straightforward spacial partition is fine. Even for numbers as high as 32 million tiles, which was discussed earlier. The reason I mentioned secondary, or extraneous data is because how else are you going to store values like that? That's probably more important, because you're going to be hit by memory consumption concerns with data past individual tile types.
Use plain arrays with your own choice of spacial partitioning, store extraneous tile data in other arrays so they're additive, and not some sort of tile member variable.[/QUOTE]
I'll run with it first, if it doesn't work I'll move on.
Regardless, thanks all for the advice. :)
Screwing around with Hollygram, it turns out the slant overflow thing wasn't due to an alpha channel in the image. I found the fix thanks to [url=http://www.ogre3d.org/forums/viewtopic.php?p=243314&sid=bdd71a0f0a357de0f5ea5d61d9c06fca#p243314]some dude on the Ogre 3D forums[/url].
I also got GWEN to work in my game, so now I have a GUI.
GWEN would be so useful in love.
Added Album art and progress bar (oh, and the ability to actually play a track)
[IMG]http://img12.imageshack.us/img12/6715/audiophilia201112150143.png[/IMG]
Edit:
Also fixed some threading issues that were randomly crashing the program
[QUOTE=thisBrad;33731318]Added Album art and progress bar (oh, and the ability to actually play a track)
[IMG]http://img12.imageshack.us/img12/6715/audiophilia201112150143.png[/IMG]
Edit:
Also fixed some threading issues that were randomly crashing the program[/QUOTE]
I love.....
That song
Implemented a call display so I can actually view calls to the server.
[img]http://goo.gl/qGwcY[/img]
[QUOTE=miceiken;33724308]Are you planning on making a game in outer space?[/QUOTE]
I find programming on planet earth difficult at times.
I just started learning Python so I started working on a quick text-based game, just so I can practice.
I used the [URL="http://sos.gd/themes/"]LD22 warmup theme generator[/URL] for the theme and a friend is helping me with the story.
[IMG]http://yourimg.in/m/6048i7f.png[/IMG]
:v:
Sorry, you need to Log In to post a reply to this thread.
