Sign in to follow this  

Unity Data structure in a block based game

This topic is 399 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello everyone! I've been working recently with a block-based building game in Unity, akin to Robocraft or Crossout, but i can't make up my mind on which would be the best way of storing the blocks. The idea is that the game should be based around larger components with a distinct function, the amount of blocks per construct should be in the ranges of 20 to 500. The blocks will be classes rather than structs, since they need to be mutable (each has a health property, etc). It is also important to be able to access nearby blocks on the grid, and to do path traversals between blocks to see if they are connected. The blocks come in different sizes and dimensions (1x1x1, 2x2x6, etc). The smallest unit is 1 meter which corresponds to the int value 1.

 

Here are the alternatives i've been considering so far:

 

The chunk approach

Basically, having a main object which contains a dictionary of "chunks" tied to positions (determined by chunk size), where each chunk is a 3d array of blocks. Accessing a single block would be done by calculating the modulo of the position in construct space with the chunk size to get the target chunk, and get the precise position from there. Accessing is fast, and the blocks themselves won't take much memory space, but you'll ultimately end up storing a lot of empty space. How large should the chunks be? Should empty space be filled with "air" blocks?

 

A dictionary of blocks

Simply having a dictionary where a Vector3i is the key and the block is the value. Storage becomes compact but access is slow, and i'm not sure what the performance situation would be when the dictionary hashtable resizes. Given that the block count will be moderately low, it might be sufficient.

 

Individual coordinates for each block

Unity is based around GameObjects, and each object by default has a transform. Let's say that i would use a GameObject for each block and make them children of the main construct - would this be easier to work with or just be a nightmare for performance? Accessing neighbors would probably involve short-distance raycasting and this in itself feels like an unprofessional solution. On the other hand, it feels like Unity is meant to be used this way.

 

Are there any other options for storing blocks in a useful way?

Share this post


Link to post
Share on other sites

For my Unity voxel game, I use 16*16*16 chunks, and use "Empty" values for empty spaces. These "Empty" values are skipped when building the mesh, leaving an empty space. This gives fairly good performance, considering I generate chunks in 3 directions instead of the most commonly used column system.

Share this post


Link to post
Share on other sites

The chunk approach Basically, having a main object which contains a dictionary of "chunks" tied to positions (determined by chunk size), where each chunk is a 3d array of blocks. Accessing a single block would be done by calculating the modulo of the position in construct space with the chunk size to get the target chunk, and get the precise position from there. Accessing is fast, and the blocks themselves won't take much memory space, but you'll ultimately end up storing a lot of empty space. How large should the chunks be? Should empty space be filled with "air" blocks?


Just to cut to the chase, this is the correct option.

Chunk sizes is a balancing act between wasting empty space and being efficiently accessed. 32x32x128 may be reasonable or 256x256x256 may be reasonable or so on. Done well, your actual chunk dimensions are an internal implementation detail that no external system needs to care about, so you can tweak the sizes and run various memory vs performance measurements and find the sweat spot.

Remember also that you can optimize chunks further where appropriate, e.g. run-length encoding or the like, assuming your process your chunks into more efficient data structures for specific use cases (e.g., a mesh for rendering). You might even have chunks of chunks that allow large scale operations to work on big chunks while smaller operations like physics work on sub-chunks that are elided for empty space or homogenous tiles.
 

A dictionary of blocks Simply having a dictionary where a Vector3i is the key and the block is the value. Storage becomes compact but access is slow, and i'm not sure what the performance situation would be when the dictionary hashtable resizes. Given that the block count will be moderately low, it might be sufficient.


This will be slow, though yes the total size of the world does matter. Remember that raw Vec3 positions are a _terrible_ hash function (just as raw integer or floating point values are terrible) because they lead to many hash collisions, which turns most hash tables into linked lists (and a handful of purpose-built tables into trees). If you toss in a real hash function then you need to scale all your individual tile accesses by the cost of the hash function; it's all O(1) but in high-performance situations that linear factor that comp-sci taught us to ignore becomes very significant (it's the difference between running your physics in 1ms or 10ms or 100ms). Also keep in mind that hash tables are typically very bad at locality - you're very rarely going to be looking at a single tile at a time and very often looking at clusters of adjacent tiles. With chunks, those adjacent tiles are actually close together in memory and require fewer cache misses to query while a hash table is likely going to incur a cache miss for every single tile, no matter how close they are in cartesian space.

Now, of course, you can use a hash table to find the individual chunks, or use a spatial datastructure like an octree or kd-tree or so on.

You might also use such a structure for supplementary information. e.g. 20,000 blocks in a chunk might be all "stone" but 12 blocks might be signs that need metadata on the text they contain; 12 rare lookups for text is a very different thing than 20,000 lookups for everything, and you can't fit the text into the integer array of tile types anyway so you need a metadata storage strategy in any event.
 

Individual coordinates for each block Unity is based around GameObjects, and each object by default has a transform. Let's say that i would use a GameObject for each block and make them children of the main construct - would this be easier to work with or just be a nightmare for performance? Accessing neighbors would probably involve short-distance raycasting and this in itself feels like an unprofessional solution. On the other hand, it feels like Unity is meant to be used this way.


This is going to be an absolute nightmare for performance. Few engines scale well with the number of game objects and Unity is no exception. You're only going to get to a few thousands of objects before you start running into problems. Keep in mind that a mere 32x32x32 filled space is already 32,768 objects. That ain't going to work out well.

There's also no reason to think that having full objects/components for each block is going to make life easier. No sane approach here needs much more than a small integer for each block, plus metadata for the relative handful of blocks that need it.

Share this post


Link to post
Share on other sites

Thanks for all the good responses! I had a feeling that chunks were the better option, i was just hesitant considering that the main benefits from using 3d arrays come when you use them to store structs (since the blocks would be next to each other in memory). Regarding this:

 

 

For my Unity voxel game, I use 16*16*16 chunks, and use "Empty" values for empty spaces. These "Empty" values are skipped when building the mesh, leaving an empty space. This gives fairly good performance, considering I generate chunks in 3 directions instead of the most commonly used column system.

 

When you say "empty" value, do you mean a null value or a filler object? I've noticed that a lot of people use "air" blocks (perhaps to avoid dealing with null pointers), but i'm not sure if it makes sense from a memory point of view.

 

Remember that raw Vec3 positions are a _terrible_ hash function

 

Is the hash function just the sum of the vector elements? Because in that case, yeah, it's problematic to say the least.

 

You might also use such a structure for supplementary information. e.g. 20,000 blocks in a chunk might be all "stone" but 12 blocks might be signs that need metadata on the text they contain; 12 rare lookups for text is a very different thing than 20,000 lookups for everything, and you can't fit the text into the integer array of tile types anyway so you need a metadata storage strategy in any event.

 

My idea was to keep a "BlockType" class reference inside each block, and to create more specialized components by extending the block class. I was also planning to keep block groups (essentially lists) inside the main construct which keep track of categories such as propulsion blocks or weapon blocks.

Share this post


Link to post
Share on other sites

Thanks for all the good responses! I had a feeling that chunks were the better option, i was just hesitant considering that the main benefits from using 3d arrays come when you use them to store structs (since the blocks would be next to each other in memory). Regarding this:

 

 

For my Unity voxel game, I use 16*16*16 chunks, and use "Empty" values for empty spaces. These "Empty" values are skipped when building the mesh, leaving an empty space. This gives fairly good performance, considering I generate chunks in 3 directions instead of the most commonly used column system.

 

When you say "empty" value, do you mean a null value or a filler object? I've noticed that a lot of people use "air" blocks (perhaps to avoid dealing with null pointers), but i'm not sure if it makes sense from a memory point of view.

 

 

 

Remember that raw Vec3 positions are a _terrible_ hash function

 

Is the hash function just the sum of the vector elements? Because in that case, yeah, it's problematic to say the least.

 

 

 

You might also use such a structure for supplementary information. e.g. 20,000 blocks in a chunk might be all "stone" but 12 blocks might be signs that need metadata on the text they contain; 12 rare lookups for text is a very different thing than 20,000 lookups for everything, and you can't fit the text into the integer array of tile types anyway so you need a metadata storage strategy in any event.

 

My idea was to keep a "BlockType" class reference inside each block, and to create more specialized components by extending the block class. I was also planning to keep block groups (essentially lists) inside the main construct which keep track of categories such as propulsion blocks or weapon blocks.

 

I use actual values that say empty. Each block has properties, and believe it or not empty blocks have some important ones  - transparency, density, and other values are all needed for my game on a block-by-block basis. You may not need this, so it's really your design choice.

Share this post


Link to post
Share on other sites

Remember that raw Vec3 positions are a _terrible_ hash function

 
Is the hash function just the sum of the vector elements? Because in that case, yeah, it's problematic to say the least.


Just about any "cheap" hash of a Vec3 is going to be ineffective. Anything effective will be computationally expensive given the number of required lookups. 

You might also use such a structure for supplementary information. e.g. 20,000 blocks in a chunk might be all "stone" but 12 blocks might be signs that need metadata on the text they contain; 12 rare lookups for text is a very different thing than 20,000 lookups for everything, and you can't fit the text into the integer array of tile types anyway so you need a metadata storage strategy in any event.

 
My idea was to keep a "BlockType" class reference inside each block, and to create more specialized components by extending the block class. I was also planning to keep block groups (essentially lists) inside the main construct which keep track of categories such as propulsion blocks or weapon blocks.


Don't do that.

References are a minimum of the machine's native word size, e.g. 64 bits (8 bytes) on a 64-bit computer. Unless you're going to have close to 9,223,372,036,854,775,807 different types of blocks (spoiler: you won't) that's pretty wasteful. Given a 32x32x32 chunk, using 8 bytes per block would use 262Kb of memory. You can get by with 16-bit (2 byte) indices instead of references or even 9-bit (1 byte) indices for simpler games.

Use these indices into an array that can store your class references.

Though I wouldn't uses classes here, at least not in the general case. That's a lot of overhead for no good reason. Remember that class objects are heap-allocated anywhere in memory; if you have enough block types or your classes are too big, you may have trouble fitting all the relevant block types into L1 cache and hence suffer a lot of performance loss on every operation (drawing, physics, mining, etc.). Prefer separate arrays instead, e.g. an array of mesh properties, an array of physics properties, etc. A particular block type would use the same index into each array. This way you can have much more efficient lookup of block prroperties for a given operation with no extraneous indirections and with better CPU cache utilization (and given how many blocks can be in a scene, every nanosecond counts when it comes to working with blocks!).

Remember, OOP is but one tool in a large toolbox. Don't reach for it without determining that it's the correct tool to use. Given that you're potentially dealing with millions of blocks in even simple scenes, in this case you should be reaching for tools that absolutely maximize performance and OOP is rarely the best tool in terms of performance (there are many reasons and correct ways to use OOP; this just isn't one of them).

Share this post


Link to post
Share on other sites

While i'd understand this type of recommendation for a minecraft-like voxel game, where you'd have entire landscapes of blocks, i'm not sure if it's a big concern in my case. I'm actually not expecting to have more than 10,000 blocks in any given scene. If anything, i could compromise by having a static BlockTypes class which contains arrays for each property, and where you'd get a value by calling, say, BlockTypes.GetMaxHealth(blockId) etc, with blockId being an ushort. The important part is that the block types should should be easily generated from a JSON or XML file. Any ideas on how to generate block IDs in a way that doesn't ruin saves if you add a new block type?

Share this post


Link to post
Share on other sites

The other option you can do, is often times what is called a scan line if you're really hurting on memory constraints.

You'll have worse access time, but less memory usage. And the data structure is similar enough to that of a chunk.


You can start from the bottom, the sides or the tops. But you're scanning the run length of one particular type of block. The moment you hit a new block, you record that, and begin recording for the new block type for the very end.

I personally would not recommend doing this for live games unless you are trying to build for a mobile device. As this method is slower and harder to access data for. BUT it makes a great save format, as it's very quick to load from disk and ver compact. Assuming that your chunks are not completely noisy with the block type distribution. That, and a huge chunk of your block space is likely to be air anyways.

Edited by Tangletail

Share this post


Link to post
Share on other sites

That's quite interesting, i've never heard of that method before. Either way, i think i'm settling with using chunks. A new problem though is how to represent that a grid location is occupied by another block. At first, i figured that just setting all occupied spots to point towards the block would do it, but that won't work since you need the block's array position to represent the position of the mesh in local space. Another way is to use an "occupied" or "indirect" block which contains the x,y,z grid coordinates to its parent block (3x32 bits worth of integer might as well be replaced by an object reference - but then we won't know its position. Perhaps it is acceptable to use short ints?). In this case, if a child block is hit by a projectile, you can use it to reference the parent block - and if the hit kills it, you can use its Vector3 bounds to access all child blocks and remove them (i've got an integer version of Vector3). Let me know what you think of this solution.

 

 

 

I use actual values that say empty. Each block has properties, and believe it or not empty blocks have some important ones - transparency, density, and other values are all needed for my game on a block-by-block basis. You may not need this, so it's really your design choice.

 

I understand this, but why not just create a static block instance called "Air", and then check "if (chunk[x,y,z] == null) return Block.Air"? You won't be manipulating the air anyways, and it probably won't have a mesh assigned to it. To me, storing air in memory feels like.... well, storing air. Unless your blocks are structs, in which case i guess you might as well store air since the memory is allocated anyways.

Edited by khalvr

Share this post


Link to post
Share on other sites

This topic is 399 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

  • Forum Statistics

    • Total Topics
      628707
    • Total Posts
      2984310
  • Similar Content

    • By Dafu
      FES Retro Game Framework is now available on the Unity Asset Store for your kind consideration!
      FES was born when I set out to start a retro pixel game project. I was looking around for an engine to try next. I tried a number of things, from GameMaker, to Fantasy Consoles, to MonoGame and Godot and then ended up back at Unity. Unity is just unbeatable in it's cross-platform support, and ease of deployment, but it sure as heck gets in the way of proper retro pixel games!
      So I poured over the Unity pipeline and found the lowest levels I could tie into and bring up a new retro game engine inside of Unity, but with a completely different source-code-only, classic game-loop retro blitting and bleeping API. Months of polishing and tweaking later I ended up with FES.
      Some FES features:
      Pixel perfect rendering RGB and Indexed color mode, with palette swapping support Primitive shape rendering, lines, rectangles, ellipses, pixels Multi-layered tilemaps with TMX file support Offscreen rendering Text rendering, with text alignment, overflow settings, and custom pixel font support Clipping Sound and Music APIs Simplified Input handling Wide pixel support (think Atari 2600) Post processing and transition effects, such as scanlines, screen wipes, screen shake, fade, pixelate and more Deploy to all Unity supported platforms I've put in lots of hours into a very detail documentation, you can flip through it here to get an better glimpse at the features and general overview: http://www.pixeltrollgames.com/fes/docs/index.html
      FES is carefully designed and well optimized (see live stress test demo below). Internally it uses batching, it chunks tilemaps, is careful about memory allocations, and tries to be smart about any heavy operations.
      Please have a quick look at the screenshots and live demos below and let me know what you think! I'd love to hear some opinions, feedback and questions!
      I hope I've tickled your retro feels!



      More images at: https://imgur.com/a/LFMAc
      Live demo feature reel: https://simmer.io/@Dafu/fes
      Live blitting stress test: https://simmer.io/@Dafu/fes-drawstress
      Unity Asset Store: https://www.assetstore.unity3d.com/#!/content/102064

      View full story
    • By Dafu
      FES Retro Game Framework is now available on the Unity Asset Store for your kind consideration!
      FES was born when I set out to start a retro pixel game project. I was looking around for an engine to try next. I tried a number of things, from GameMaker, to Fantasy Consoles, to MonoGame and Godot and then ended up back at Unity. Unity is just unbeatable in it's cross-platform support, and ease of deployment, but it sure as heck gets in the way of proper retro pixel games!
      So I poured over the Unity pipeline and found the lowest levels I could tie into and bring up a new retro game engine inside of Unity, but with a completely different source-code-only, classic game-loop retro blitting and bleeping API. Months of polishing and tweaking later I ended up with FES.
      Some FES features:
      Pixel perfect rendering RGB and Indexed color mode, with palette swapping support Primitive shape rendering, lines, rectangles, ellipses, pixels Multi-layered tilemaps with TMX file support Offscreen rendering Text rendering, with text alignment, overflow settings, and custom pixel font support Clipping Sound and Music APIs Simplified Input handling Wide pixel support (think Atari 2600) Post processing and transition effects, such as scanlines, screen wipes, screen shake, fade, pixelate and more Deploy to all Unity supported platforms I've put in lots of hours into a very detail documentation, you can flip through it here to get an better glimpse at the features and general overview: http://www.pixeltrollgames.com/fes/docs/index.html
      FES is carefully designed and well optimized (see live stress test demo below). Internally it uses batching, it chunks tilemaps, is careful about memory allocations, and tries to be smart about any heavy operations.
      Please have a quick look at the screenshots and live demos below and let me know what you think! I'd love to hear some opinions, feedback and questions!
      I hope I've tickled your retro feels!



      More images at: https://imgur.com/a/LFMAc
      Live demo feature reel: https://simmer.io/@Dafu/fes
      Live blitting stress test: https://simmer.io/@Dafu/fes-drawstress
      Unity Asset Store: https://www.assetstore.unity3d.com/#!/content/102064
    • By Dafu
      Hello all,
      I've been hard at work on a new retro pixel-perfect framework called FES Retro Game Framework. It is now available on the Unity Asset Store for your kind consideration!
      FES was born when I set out to start a retro pixel game project. I was looking around for an engine to try next. I tried a number of things, from GameMaker, to Fantasy Consoles, to MonoGame and Godot and then ended up back at Unity. Unity is just unbeatable in it's cross-platform support, and ease of deployment, but it sure as heck gets in the way of proper retro pixel games!
      So I poured over the Unity pipeline and found the lowest levels I could tie into and bring up a new retro game engine inside of Unity, but with a completely different source-code-only, classic game-loop retro blitting and bleeping API. Months of polishing and tweaking later I ended up with FES.
      Some FES features:
      Pixel perfect rendering RGB and Indexed color mode, with palette swapping support Primitive shape rendering, lines, rectangles, ellipses, pixels Multi-layered tilemaps with TMX file support Offscreen rendering Text rendering, with text alignment, overflow settings, and custom pixel font support Clipping Sound and Music APIs Simplified Input handling Wide pixel support (think Atari 2600) Post processing and transition effects, such as scanlines, screen wipes, screen shake, fade, pixelate and more Deploy to all Unity supported platforms I've put in lots of hours into a very detail documentation, you can flip through it here to get an better glimpse at the features and general overview: http://www.pixeltrollgames.com/fes/docs/index.html
      FES is carefully designed and well optimized (see live stress test demo below). Internally it uses batching, it chunks tilemaps, is careful about memory allocations, and tries to be smart about any heavy operations.
      Please have a quick look at the screenshots and live demos below and let me know what you think! I'd love to hear some opinions, feedback and questions!
      I hope I've tickled your retro feels!



      More images at: https://imgur.com/a/LFMAc
      Live demo feature reel: https://simmer.io/@Dafu/fes
      Live blitting stress test: https://simmer.io/@Dafu/fes-drawstress
      My own game I started working on using FES, a roguelike, very early: https://simmer.io/@Dafu/merl
      Unity Asset Store: https://www.assetstore.unity3d.com/#!/content/102064
       
       
    • By Apollo Cabrera
      Yasss!!! My first Unity3d game is on the App Store and Google Play.
      Download please! About 30 minutes to get through 5 missions.
      Let me know what you guys think.
      Thanks a bunch
       
    • By Mert Oguz
      well, i have started developing games last year, alone , I made a singleplayer 3d openworld rpg on unity you can look at it on googleplaystore ( kooru stone rpg ) whatever, this year, i wanted to make mmo, which gone really fine until I first try real hosting, I was working on "wamp" until then. The reason i am desperate now is that the way my game works.
      On my pc, using wamp mysql , with localhost as host for my game, i was testing my mmorpg with using andorid emulators, ofcourse no lag no issues no restrictions, beautiful dream... But then, I wanted to get real host from web, so, I rent a basic, cheaphest ever web host ( 10$ year ), and transferred my php files along with sql database. 
      So, I launched the game, still no issues, tried to handle 2-3 players by using my pc, phone, friend's phone...  
      After a while, ( after really short time (3-4mins)) host started not to respond, beacause those web hosting were not fit to handle mmos, i predicted that.
      now what i am explaining is that my game works like this and asking what way should i use to handle it :
      - Creates web request ( like : webhost.com/game/getplayerdata.php?ID=2 )
      -Reads request ( request result be like = "ID2-GoodGuyXx-23-123-4-123-43 )
      -Builds player using result string
      -does similar requests REEAALY FREQUENTLY  ( total requests of 8 - 12 times per seconds )
      With my current ultimate cheap web hosting, i can handle 2 players with low lag ( lol ) but, i want to handle around 20-100 players,
      just need a clear path, i have been struggling with google cloud sql and other vps server dedicated server options, i dont wanna pay much and get ripped off.
  • Popular Now