Search Unity

After playing minecraft...

Discussion in 'General Discussion' started by jc_lvngstn, Oct 8, 2010.

Thread Status:
Not open for further replies.
  1. PhobicGunner

    PhobicGunner

    Joined:
    Jun 28, 2011
    Posts:
    1,813
    The ripped textures were almost certainly from a Minecraft texture pack, which isn't surprising really (I've done the same thing before when just throwing a system together so I can see how it looks without having to play the role of artist)
    I'm assuming, because there is no license protecting on the package, he can't take sufficient legal action against anyone for using his code. Kind of like if I just posted code on the forums and someone used it, I can't take legal action against them for using my publicly posted code.
     
  2. GibTreaty

    GibTreaty

    Joined:
    Aug 25, 2010
    Posts:
    792
    I like using Minecraft's textures. They're so simplistic. If I used a 64+x64+ texture rather than the 16x16 that Minecraft uses, it would look absolutely gross. I've seen some HD texture packs that people put out for Minecraft and there's just something wrong about them, it's like they don't "fit". If the world looked more like a VoxelForm world then they would fit.

    But when it comes time to actually release something I would make my own textures.
     
  3. GenericGame

    GenericGame

    Joined:
    Nov 26, 2012
    Posts:
    206
    Here is my minecraft style building game using a 64 x 64 texture pack. Just released first playble version today, free to play: http://www.indiedb.com/games/edit/koncraft

    You can download it from indiedb.com
     
  4. Stopsecret

    Stopsecret

    Joined:
    Oct 31, 2012
    Posts:
    70
    Hello guys!

    First off, just want to say, some GREAT projects on here! (especially Alexzzzz's project and Block Story)
    I have started my own little project, but I would like a bit of help if anyone would be willing to answer a (possibly too broad) question and point me in the right direction.
    Here's some screens:

    $Shot1.png

    $Shot2.png

    As you can see, really crummy graphics (at the moment), but still a high frame rate. Well, when you're standing still. The way the generation works is that those diamond gizmos are spaced evenly apart and round to the size of a chunk, as you move forward, these diamonds check to see if there is a chunk where they're at. If there isn't, it generates a new chunk to compensate. And it generates these new chunks REALLY slowly.

    I assume others on this thread have run into these massive hiccup chunk generation problems problems and can at least point me in the right direction. Threading? Also, if someone has a faster way to generate chunks around the player without creating a large amount of gameObjects (as in my diamond system). I am versed in both C# and UnityScript, so any scripting advice you can throw at me would be great. Where did you guys find your largest bottleneck was? Assigning the mesh? Normals calculation?

    As a side note, right now I am not concerned about graphics, lighting. I am only concerned about fps speed ATM. Gameplay over graphics, right? :)

    I am especially interested to find out how Block Story is able to generate chunks fast enough to run their game on mobile, which is very impressive.

    Thanks! :D
    -Stopsecret
     
  5. GenericGame

    GenericGame

    Joined:
    Nov 26, 2012
    Posts:
    206
    These questions are undoubtedly going to be asked of you:

    question #1: are you using threads to calculate your terrain?

    question #2: are you destroying chunks that are too far away from the player once he moves? If you are, instead of destroying new chunks, just put them in a List or array object and set them to be reused so the mesh doesn't have to be continually regenerated.

     
  6. Stopsecret

    Stopsecret

    Joined:
    Oct 31, 2012
    Posts:
    70
    Answer to question 1 : No, I am not using any sort of threading. If this is essential to the speed of the generation, I would definitely try it though. (Unity's API doesn't seem to contain much/anything about threading though, except that coroutine stuff.)

    Answer to question 2 : No, I am not destroying chunks behind the player just yet (perhaps I will do that later), although that is a smart suggestion. The chunks themselves have an extremely low impact on frame rate. It is the generation I am having more of a problem with.
     
  7. goldbug

    goldbug

    Joined:
    Oct 12, 2011
    Posts:
    767
    There are really 2 pieces to focus on: sustained fps when not loading chunks, and latency spikes when loading terrain/models. Both of which are attacked independently.

    • Sustained fps means that what the game can perform like once everything is loaded. To get good fps, you have to have the minimum amount of draw calls possible. For block story we use chunks of 32x32x32, which are pretty massive. We also perform some optimization so that large areas of identical blocks are merged together to reduce the amount of triangles. This is essential in order to get bigger chunks.
    • Latency spikes is what I think you are having the most trouble with. For block story we do all the terrain calculation in a background thread, and then on an Update, we create the mesh with the results of the calculation. We try to keep the amount of work performed on the foreground thread to a minimum, so it does not kill fps. One particular thing to watch out for is that assigning mesh colliders is particularly expensive, more so than the visual meshes. Assigning mesh colliders is the single biggest cause of latency spike when loading chunks that we had. We resolved this particular issue by not using mesh colliders at all. Instead in Block Story we have our own collision detection system using sweep AABB algorithm.


    While I have not covered this specific subject in depth, I have written some articles describing the basics for how the block engine works in block story, which I believe you will find helpful.
     
  8. goldbug

    goldbug

    Joined:
    Oct 12, 2011
    Posts:
    767
    Our players have built some really impressive structures, including the empire states, sphinx, huge boats, millenium falcon and more.

    But It always frustrated me that people had to put block by block, and spend hours just building a rectangular surface rather than focus on their artistic talents. So we came up with a way for people to do mass building:



    Also to make it more fun, we made it so that monsters fight each other and the player can have a pet dragon and spider:



    We are celebrating reaching the top 35 paid arcade game in google play, our 1000 subscribers in youtube, 1 million downloads of the lite version
    and the incredible momentum we are having. We are reaching a point where we can live off the game.
     
  9. GenericGame

    GenericGame

    Joined:
    Nov 26, 2012
    Posts:
    206
    I also recommend reading goldbugs blog, he has a lot of useful information there and talks about the key points of world building that are important for developers.

    Unity does not have an implementation of threading. You can use Microsoft's implementation of it, err mono, but more info can be found here:
    http://msdn.microsoft.com/en-us/library/system.threading.thread.aspx

    It's important to note that Unity will not allow you to run anything relating to their engine on a different thread than the main thread. I also recommend loading all of your game objects at the beginning of world building, then reusing them. In my game, I load a huge list of objects and it takes quite some time, but I recycle the models I use, including the terrain mesh. But, it does offer better performance.

    Although my alpha versions I posted do not allow you to build infinitely, so it might not be the best example to view the source code. Try viewing the source code of block story instead if you are intent on using the minepackage system. I opted not to use it bust instead borrowed concepts from the cubic world package which is NOT multi-threaded, you would have to build your own.

    Coroutines are not threads, they are just delayed process mechanisms.

    Here is a GREAT resource that several people have put together: http://unitycoder.com/blog/2012/10/18/voxel-resources-engines-for-unity/
     
  10. GibTreaty

    GibTreaty

    Joined:
    Aug 25, 2010
    Posts:
    792
    Added submeshes for multiple block types. Instead of using the texture atlas method I decided to try what Alexzzzz mentioned. Using a texture atlas would mean smaller chunk meshes but I'm not too worried about that.

    [Before Optimization - 16x16x16]

    $Submeshes Before - 16x16x16.png

    [After Optimization - 16x16x16]
    $Submeshes After - 16x16x16.png
     
  11. GenericGame

    GenericGame

    Joined:
    Nov 26, 2012
    Posts:
    206
    Looks great! Is there a reference to building meshes like that I could look at or you just did this from scratch? I'd like to reduce my triangle count like that, INSANE difference.

     
  12. GibTreaty

    GibTreaty

    Joined:
    Aug 25, 2010
    Posts:
    792

    I do this weird thing where I start an entirely new project and using what I've learned from all my previous attempts at a game, I build something different and learn something new.

    Match Cubed

    That is the game that helped me figure out how to go about cycling through blocks and gather up similar ones. The process is simple but hard to figure out... until you do. In my mesh optimizer I take advantage of the Bounds struct and for each similar block, I add a 1x1x1 bound into the main bounds to make it bigger.

    So to calculate one side -
    1. Start at 0,0,0 and search for the first solid block
    2. Once a block is found keep counting to the right on the X axis until either you hit an air block or a block that's not similar.
    3. Once you hit a dead-end then you save an integer for how many blocks you were able to span.
    4. Next it moves onto the next loop which loops through the Y and X axis starting 1 block above the first block that was checked.
    5. Each new Y axis checked has to require that the whole span of blocks on that axis is the exact type as the beginning block that started this whole mess.
    6. Repeat 2-6.

    And if that wasn't enough explanation I'll try it with an ASCII picture.

    [0][0][0][0]
    [0][1][0][0]
    [1][1][1][2]
    [1][1][1][2]

    Note that #0 are air blocks in this case. The first loop would start at the bottom left and see a #1 block. It would then traverse to the right and would see 2 more #1 blocks. Once it sees the #2 block it would then stop and remember that the span of #1 blocks is 3 blocks long.

    Next it would go to the second row, see a #1 and require that 3 #1 blocks must be on this row, which there are. Then is goes to the next row, sees a #0, stops and finishes a Bound.

    It would then go on to the first #2 and traverse upwards once because that is all there is.

    Next it would see a single 1 and create what would seem like a regular sized block mesh and be done with the whole thing.

    The hard part was creating a single function to traverse each side, but I did it and it works.

    Code (csharp):
    1.  
    2. VoxelBounds GetSpans(bool[] checkedTiles, int face) {
    3.         List<MeshBounds> allBounds = new List<MeshBounds>();
    4.  
    5.         Vector3 normals = face.IntToDirection();
    6.         normals.x = Mathf.Abs(normals.x);
    7.         normals.y = Mathf.Abs(normals.y);
    8.         normals.z = Mathf.Abs(normals.z);
    9.         normals = Vector3.one - normals;
    10.  
    11.         int spanXIndex = 0;
    12.         int spanYIndex = 1;
    13.  
    14.         if(normals == new Vector3(0, 1, 1)) {
    15.             spanXIndex = 2; //z
    16.             spanYIndex = 1; //y
    17.             normals = Vector3.forward;
    18.         }
    19.         else if(normals == new Vector3(1, 0, 1)) {
    20.             spanXIndex = 0; //x
    21.             spanYIndex = 2; //z
    22.             normals = Vector3.right;
    23.         }
    24.         else if(normals == new Vector3(1, 1, 0)) {
    25.             spanXIndex = 0; //x
    26.             spanYIndex = 1; //y
    27.             normals = Vector3.right;
    28.         }
    29.  
    30.         for(int n = 0; n < size.size; n++)
    31.             //Don't check already checked tiles
    32.             if(!checkedTiles[n]) {
    33.                 checkedTiles[n] = true;
    34.                 VectorI3 index = n.FlatTo3DIndex(size);
    35.  
    36.                 //Check only solid tiles, no empties tiles
    37.                 //Also make sure it has no tile covering its side
    38.                 if(tiles[n]  !FindNeighbor(index, face)) {
    39.                     VectorI3 nextIndex = index;
    40.                     Bounds bounds = new Bounds(index + half, Vector3.one);
    41.                     int xSize = 0;
    42.  
    43.                     for(int x = (int)index.GetValue(spanXIndex); x < size.GetValue(spanXIndex); x++) {
    44.                         nextIndex += normals;
    45.  
    46.                         if(!nextIndex.ArrayOutOfBounds(size)) {
    47.                             int nextFlatIndex = nextIndex.FlatIndex(size);
    48.  
    49.                             if(!checkedTiles[nextFlatIndex]  tiles[nextFlatIndex].type == tiles[n].type) {
    50.                                 checkedTiles[nextFlatIndex] = true;
    51.  
    52.                                 if(tiles[nextFlatIndex]  tiles[nextFlatIndex].type == tiles[n].type  !FindNeighbor(nextIndex, face)) {
    53.                                     bounds.Encapsulate(new Bounds(nextIndex + half, Vector3.one));
    54.                                     xSize++;
    55.                                 }
    56.                                 else break;
    57.                             }
    58.                             else break;
    59.                         }
    60.                         else break;
    61.                     }
    62.  
    63.                     for(int y = (int)index.GetValue(spanYIndex) + 1; y < size.GetValue(spanYIndex); y++) {
    64.                         List<int> setChecked = new List<int>();
    65.                         bool noEmpties = true;
    66.  
    67.                         for(int x = 0; x < xSize + 1; x++) {
    68.                             nextIndex = index;
    69.                             nextIndex = nextIndex.SetValue(spanXIndex, nextIndex.GetValue(spanXIndex) + x);
    70.                             nextIndex = nextIndex.SetValue(spanYIndex, y);
    71.  
    72.                             if(!nextIndex.ArrayOutOfBounds(size)) {
    73.                                 int nextFlatIndex = nextIndex.FlatIndex(size);
    74.  
    75.                                 if(!checkedTiles[nextFlatIndex]  tiles[nextFlatIndex].type == tiles[n].type) {
    76.                                     setChecked.Add(nextFlatIndex);
    77.  
    78.                                     if(!(tiles[nextFlatIndex]  tiles[nextFlatIndex].type == tiles[n].type  !FindNeighbor(nextIndex, face))) {
    79.                                         noEmpties = false;
    80.                                         break;
    81.                                     }
    82.                                 }
    83.                                 else {
    84.                                     noEmpties = false;
    85.                                     break;
    86.                                 }
    87.                             }
    88.                             else {
    89.                                 noEmpties = false;
    90.                                 break;
    91.                             }
    92.                         }
    93.  
    94.                         if(noEmpties) {
    95.                             foreach(int a in setChecked)
    96.                                 checkedTiles[a] = true;
    97.  
    98.                             bounds.Encapsulate(new Bounds(nextIndex + half, Vector3.one));
    99.                         }
    100.                         else
    101.                             break;
    102.                     }
    103.  
    104.                     allBounds.Add(new MeshBounds(bounds, GetSubmesh(tiles[n].type)));
    105.                 }
    106.             }
    107.  
    108.         return new VoxelBounds(allBounds.ToArray(), face);
    109.     }
    110.  
    111. public struct VoxelBounds {
    112.     public MeshBounds[] bounds { get; set; }
    113.     public int direction { get; set; }
    114.     public int materialIndex { get; set; }
    115.  
    116.     public VoxelBounds(MeshBounds[] bounds, int direction) {
    117.         this.bounds = bounds;
    118.         this.direction = direction;
    119.     }
    120.  
    121.     public VoxelBounds(MeshBounds[] bounds, int direction, int materialIndex) {
    122.         this.bounds = bounds;
    123.         this.direction = direction;
    124.         this.materialIndex = materialIndex;
    125.     }
    126. }
    127.  
    128. public struct MeshBounds {
    129.     public Bounds bounds { get; set; }
    130.     public int subMesh { get; set; }
    131.  
    132.     public MeshBounds(Bounds bounds, int subMesh) {
    133.         this.bounds = bounds;
    134.         this.subMesh = subMesh;
    135.     }
    136. }
    137.  
     
    Last edited: May 10, 2013
  13. akorany321

    akorany321

    Joined:
    May 13, 2013
    Posts:
    1
    hey i need help with a block generator for unity im trying to make a minecraft like game and every code i try fails
     
  14. GenericGame

    GenericGame

    Joined:
    Nov 26, 2012
    Posts:
    206
    Thank you for this GibTreaty! Now I just have to find time to implement this in my project. Time is EviL =D
     
  15. GenericGame

    GenericGame

    Joined:
    Nov 26, 2012
    Posts:
    206
    Can you elaborate on your question? I don't understand what you are asking for.

     
  16. Captain Morgan

    Captain Morgan

    Joined:
    May 12, 2013
    Posts:
    144
    Hello!
    alexzzzz, can you explain how you create so amazing not smooth blocks. I understant that you, in some magic case, calculate some "noise" and after that shift some vertices by this "noise". But how exactly do you find this noise? How do you define which vertices need to move?
     
  17. Captain Morgan

    Captain Morgan

    Joined:
    May 12, 2013
    Posts:
    144
    also, alexzzzz, i read that you use "Optimized collider meshes". What is it? Its custom mesh collider, or maybe custom assets?
     
  18. GibTreaty

    GibTreaty

    Joined:
    Aug 25, 2010
    Posts:
    792
    Your welcome! Time really is evil, I could feel like I've spent 10 mins coding and in reality 2-3 hours have gone by with nothing to show for it but another new bug 0_o
     
  19. GenericGame

    GenericGame

    Joined:
    Nov 26, 2012
    Posts:
    206
    My new, in-game mass-cut/mass-place cursor is now working flawlessly. Glad i'm done coding that. =D
     
  20. GibTreaty

    GibTreaty

    Joined:
    Aug 25, 2010
    Posts:
    792
    For anyone wishing to see the Tile Optimizer in action here is a download link to the project

    http://www.mediafire.com/download/3h57q2e646g95v8/TileOptimizer.rar

    Note -
    The optimizer is set to optimize an entire world rather than specific chunks. In the scene it looks as if there are multiple chunks but each one is basically a world. I've been playing around with a different project that uses my optimizer and I'm working on a way to optimize individual chunks. I'll update this project when I can.
     
  21. GenericGame

    GenericGame

    Joined:
    Nov 26, 2012
    Posts:
    206
    Wish I could use that optimize method, but alas after investigating, I can't due to having random textures on every block placed. =/

    Here is my latest vid, showing random textures. As well, it also shows the voxel prefab maker along with the room cutter/placer tool. Additionally, a block rotation tool has been added to the interface. Another big feature is the ability to save your designs and make designs out of previous designs and so on.

    Here is a video of me just doodling turning 10 stones into 10,000,000. I don't know what I'm doing. lol

     
  22. Captain Morgan

    Captain Morgan

    Joined:
    May 12, 2013
    Posts:
    144
    Hello guys, i have a small question: how to swim in water? How to create that? there are special movement controll script?

    And also: if i create water as a block i need to fill 2 different vertices\indices array: first (with water) Mesh i will use with MeshFilter, second (without) - i will use with MeshCollider, right?
     
  23. jayhatmaker

    jayhatmaker

    Joined:
    May 14, 2013
    Posts:
    7
    Hi, currently I'm creating a 2D version of a procedurally generated world.

    I'm having trouble with chunk loading.
    My character has a visibility of 5x5 chunks (player in the middle, -2 chunks left, + 2 chunks right, +2 chunks up, -2 chunks down).
    Each time a character travels from one chunk to another, visible chunks are updated.

    The update method is simple, it just checks array of chunk and turn on/off accordingly.
    The problem is when a new chunk is instantiated(purely code based),
    the player stops moving for 1 second or 2, chunks gets loaded, then player moves again.
    I really need to fix this glitchiness.

    I'm guessing this happens because everything runs on main thread?
    If that's the case, could you share us your approach?
    I don't know how to prepare data/instantiate behind the main thread.

    [edit]
    I read first half of this thread and jumped to the last... same question was asked a page before... ooooooops.
    I will try to read into microsoft threading stuff. Doh.
     
    Last edited: May 28, 2013
  24. GibTreaty

    GibTreaty

    Joined:
    Aug 25, 2010
    Posts:
    792
    Yea I'm probably going to have to stick with the standard route if I want to keep certain features like vertex AO and deformation. It gives a big hit to the drawcalls too if you use the optimizer so I'm not sure how "optimized" it really is. The problem is that you have to use a different material per-block or else the texture won't be repeatable which then means you get more drawcalls. So what would be maybe 6 drawcalls per chunk maximum, would turn into 6*(material count)*chunks maximum. I haven't checked if it still gives you drawcalls for unused materials (the material still being on the MeshRenderer, just no mesh that uses it).

    I have learned my lesson though...

    STAY AWAY FROM MESH COLLIDERS IF YOU WANT SPEED
     
  25. Vanamerax

    Vanamerax

    Joined:
    Jan 12, 2012
    Posts:
    938
    Just thinking in terms of performance,

    would it help (or even be possible) to use the GPU for generating your 2D noise heightmap, like, writing the values to a texture and send that back to the CPU for conversion into 3D voxels? Or would that make no difference at all?
     
  26. GibTreaty

    GibTreaty

    Joined:
    Aug 25, 2010
    Posts:
    792
    If you were doing really complex algorithms to generate the terrain data then that sounds like it would be good. How would you do that on the GPU anyways.. through a shader?
     
  27. Captain Morgan

    Captain Morgan

    Joined:
    May 12, 2013
    Posts:
    144
    GibTreaty, do you use MeshCollider or some custom character controller with collider?
     
  28. GenericGame

    GenericGame

    Joined:
    Nov 26, 2012
    Posts:
    206
    i'm using a mesh renderer + simple raycasting and speed is good. But,since i'm not using any noise algos, maybe that's why I don't see the issues with speed. I don't have a need for noise since our game is basically a castle dungeon game, so i'll never need them. However, the noise i do have is randomly generating dungeon rooms, but not quite as intensive as noise generation.


    Here is the 4 minute version of building a super structure in koncraft with the recorder cube. Sorry bout that long video up above lol

     
  29. Chris12345

    Chris12345

    Joined:
    Jul 14, 2012
    Posts:
    10
    How did you make this? i am creating a game but i cannot figure out how to cut a mesh like you do in this video?
     
  30. GenericGame

    GenericGame

    Joined:
    Nov 26, 2012
    Posts:
    206
    I'm sorry, i don't understand your question.
     
  31. Captain Morgan

    Captain Morgan

    Joined:
    May 12, 2013
    Posts:
    144
    It's a regular mesh
     
  32. Chris12345

    Chris12345

    Joined:
    Jul 14, 2012
    Posts:
    10
    Can you give the unity project for this?
     
  33. GenericGame

    GenericGame

    Joined:
    Nov 26, 2012
    Posts:
    206
    I wish i could, but this is a commercial project, thousands of hours into it. I can certainly try to assist you with solving particular issues you have, however, i'm not the smartest cookie here on this forum to so lol.

    If by cutting the mesh, you mean modifying the mesh at runtime, wow, that is a whole lotta learning i think.

    Here is the single most important resource you could use if you want to start to understand voxel style mesh generation and the such:
    http://unitycoder.com/blog/2012/10/18/voxel-resources-engines-for-unity/
     
  34. Captain Morgan

    Captain Morgan

    Joined:
    May 12, 2013
    Posts:
    144
    Guys, can you share you custom character controller with collider. Coz MeshCollider is painful slowly
     
  35. GibTreaty

    GibTreaty

    Joined:
    Aug 25, 2010
    Posts:
    792
    When I use a MeshCollider for the chunks, I just use a CharacterController or a capsule Rigidbody. I haven't figured out how to do that whole AABB collision stuff for chunks that have no collider yet though :(

    It sucks that the perlin noise logic doesn't really crossover to dungeon generation. I'd like to try to make a random dungeon generator sometime.
     
  36. Captain Morgan

    Captain Morgan

    Joined:
    May 12, 2013
    Posts:
    144
    And what collider do you use now?
     
  37. GibTreaty

    GibTreaty

    Joined:
    Aug 25, 2010
    Posts:
    792
    At this point, nothing.
     
  38. Captain Morgan

    Captain Morgan

    Joined:
    May 12, 2013
    Posts:
    144
    And player falls through the block?
     
  39. GibTreaty

    GibTreaty

    Joined:
    Aug 25, 2010
    Posts:
    792
    There's actually no player at this point. Just a floating camera.
     
  40. GenericGame

    GenericGame

    Joined:
    Nov 26, 2012
    Posts:
    206
    I'm going to do what you are doing. I'm starting KonCraft from scratch and slowly import all code in a different manner piece by piece. I think I'll come out with a much more solid system than before. This might take a couple of weeks. =/
     
  41. Captain Morgan

    Captain Morgan

    Joined:
    May 12, 2013
    Posts:
    144
    GibTreaty, can you show screenshot of your world?
     
  42. GibTreaty

    GibTreaty

    Joined:
    Aug 25, 2010
    Posts:
    792
    All I have right now is in that Tile Optimizer project so there's not much of a world either, lol. Sorry to disappoint.
     
  43. Foam

    Foam

    Joined:
    Jun 13, 2012
    Posts:
    322
    My physics work has been like this:

    1. Started with MeshCollider. This was ok but ended up being way too slow.
    2. Moved on to writing my own Physics and AABB Sweep code. This was awesomely fast but took far more time to write than I wanted.
    3. Tried out using Jitter and Bullet for my physics and collision detection (but only got Jitter to work and it was kind of wonky).
    4. Optimized my collider meshes and switched back to using MeshCollider. So far this is as fast as AABB Sweep, at least on PC (it seems like MeshCollider instantiation is pseudo-exponential on the number of triangles so cutting the triangles by 10 fold results in a 100 fold speed up).

    Long story short, try optimizing your meshes first. I used the algorithm @ http://0fps.wordpress.com/2012/06/30/meshing-in-a-minecraft-game/ (if you have trouble with his exposition, look at his code instead. a lot of his post is about mathematically proving his method will always result in a more optimized mesh compared to naive culling, and has little to do with the actual implementation).

    The basic algorithm is:

    1. You're reducing the problem from 3D to 2D because you only have to treat 1 plane at a time (as you can't combine triangles that are not co-planar).

    2. So, make a pass through the cube in each direction (or once per dimension, depending on how you want to do it), looping through each plane in that direction.

    3. For each plane, loop through all the rows and columns to calculate a "mask" object that lists whether that square in the plane needs a face (that is, a 2D array of booleans or ints or whatever). You need to create this new mask object because you are going to be updating it as you go along so you don't create duplicate triangles.

    4. Loop through each row in the plane again and start calculating which squares can be combined into 1 triangle. Basically just start recording when you first need a square and keep going down the row until you hit a spot with no square. This will give you the lower left corner and the upper right corner of the square. (you will need to repeat this all the way down the row to catch all your rectangles)

    If you stop here, you get the "single dimension" greedy mesh algorithm pointed out below in the screenshot. this isn't perfect but it's actually pretty good, as just doing this will give you the single largest increase in triangle reduction (1 factor over naive versus only 50% for 2D greedy over 1D greedy). It's also pretty damn easy!

    5. When you find this new square/triangles, check the row above it to see if you can expand the triangle upwards by 1 row. (that is, if your square is Row 1, Blocks 0 through 4, check Row 2, Blocks 0 through 4... they all need to need faces to expand upwards). Keep doing this until you fail.

    6. Now you have 1 square and the coordinates for the triangles! Make sure you update the mask object though to say that the squares covered by that triangle don't need triangles now.

    For example, this example chunk, using the naive method with culling, ended up at 5,544 triangles.
    $naive_culled.png

    Using the greedy mesh algorithm ended up at 358 triangles. HUGE difference.
    $greedy_2.png

    Even the simple single-dimension version of the greedy mesh got the mesh down to 546 triangles.
    $greedy_1.png
     
    Last edited: Jun 1, 2013
    toqueteos likes this.
  44. Foam

    Foam

    Joined:
    Jun 13, 2012
    Posts:
    322
    Here is come code to guide you (it is in Boo, but it should be pretty self-explanatory... save it to a file and run "booi <filename>" and you will see the results as it runs through an example 2D plane).

    It should be much easier to understand than the javascript implementation at https://github.com/mikolalysenko/mikolalysenko.github.com/blob/gh-pages/MinecraftMeshes/js/greedy.js . The guy's looping style and variable naming is... fine, but there's also some implementation details mixed into it that make it a touch confusing at first (he is using a flattened 2D array so he has to keep track of positioning variables of that, along with positioning for the actual blocks, along with the loops, etc.).

    If you're unfamiliar with Boo or Python, all you need to know is:

    for x in range(10) is the same as for (x = 0; x < 10; x++)
    x = matrix(bool, 2, 3) creates a 2x3 array of booleans
    and types can usually be inferred so there's not much static typing going on (there is, but it's done by the compiler)


    PHP:
    # this just sets up an example 2D plane for testing purposes
    size # 7 x 7 plane 

    # mask is just a 2D array of bools, where true means that square needs a face drawn
    mask matrix(boolsizesize)
    for 
    y in range(size):
        for 
    x in range(size):
            
    mask[yx] = true


    mask
    [00] = false
    mask
    [01] = false
    mask
    [02] = false
    mask
    [03] = false
    mask
    [24] = false
    mask
    [25] = false
    mask
    [31] = false
    mask
    [41] = false
    mask
    [51] = false
    mask
    [61] = false

    # this is what this example plane looks like, where X means that block needs a face
    # X XXXXX
    # X XXXXX
    # X XXXXX
    # X XXXXX
    # XXXX  X
    # XXXXXXX
    #     XXX

    # this just prints out the plane in visuual format to help
    # you understand whats going on and such
    # (prints in reverse so that the top is, well, up top on a console)
    for y in range(size-1, -1):
        
    ''
        
    for x in range(size):
            if 
    mask[yx]:
                
    += 'X'
            
    else:
                
    += ' '
        
    print s




    # ok, let's go!
    for y in range(size):
        
        
    building false
        
    for x in range(size):
            if 
    mask[yx] and not building# start recording a new rectangle
                
    building true
                i 
    x
            
    # if you reach a block that needs no face, or you reach the end of the row, you're done
            
    if (not mask[yx] and building) or (== size-and building):
                if (
    not mask[yx] and building): # -1 because you've already passed the last block
                    
    1
                
    else:
                    
    x
                building 
    false
                done 
    false
                h 
    # height

                # look upwards to see if the row above this one needs faces in the exact same spots (width wise)
                # this loop is a little wonky but it works
                
    for y2 in range(y+1size): # check the row above up to the max row height
                    
    for x2 in range(ij): # check all the blocks in the range of our new rectangle
                        
    if not mask[y2x2]:
                            
    # cannot expand. get out of the loop.
                            
    done true
                            
    break
                    if 
    done:
                        break
                    
    # we got to the end of the range so we're good! increase height and let's try the next row
                    
    += 1

                
    # all done with this rectangle
                # lower left coordinate of the RECTANGLE = i, y
                # upper right coordinate of the RECTANGLE = j+1, y+h
                
    print yijh

                
    # update the mask to show that the spots covered by your rectangle no longer need faces
                
    for y3 in range(yh+y):
                    for 
    x3 in range(ij+1):
                        
    mask[y3x3] = false
    This algorithm can still be improved, as you can tell from the screenshots above. Since you're only checking in one direction, it's not always guaranteed to be the "best" direction. An easy solution to this without getting into the actual optimum mesh size (the mathematical theory of which you could easily spend your life working on) is to sweep in both directions per plane and use whichever result results in less triangles.

    I haven't bothered to test this out to see if it's worth it, performance wise, but I suspect that the above algorithm is "good enough" for most purposes. Unless you're trying to generate, display, and run physics on an absurd amount of chunks, in which case it might be worth improving.
     
    Last edited: Jun 1, 2013
    toqueteos likes this.
  45. Foam

    Foam

    Joined:
    Jun 13, 2012
    Posts:
    322
    FYI this algorithm works just as well if you want to consider multiple block types. Instead of looping through an array of booleans, you loop through an array of ints (or whatever) and break on the int value instead of boolean value. Easy!

    $greedy_3.png
     
    toqueteos likes this.
  46. DryTear

    DryTear

    Joined:
    Nov 30, 2012
    Posts:
    312
    Hello, I made this looking MinecraftClone in only 3 days total :), here are the very first features:

    • Placing and Removing Blocks
    • Flat Land and Terrain
    • Choosing Block
    • Inventory(WIP, need help)
    • Save and Load( Only during sessions, need help)
    • Re-spawning
    • Pause Menu
    • Minecraft Like GUI
    • Sand and Gravel physics ( They're AWESOME )
    • Multiplayer ( Not Finished, Need help)

    And off course, if people can help me out, ill defiantly add Inventory and Multiplayer :)
    And here are some pros and cons :

    • Has advanced sand physics ( Pro, cant do that in Minecraft can you? )
    • No survival mode ( Con, will be added later )
    • No third-person camera ( Con, will be added later )
    • No Infinite Terrains ( Con, could be added later )
    • Can change the specifications of the Terrain ( Pro, cant do that in Minecraft can you? )
    • No night and day cycles ( Con, will definitely be added later )
    • No built in shadows ( Con, can be added if people help )
    • Saves states only during sessions ( Con, help needed, cant load saves after relaunch)

    The list goes on and on, but hey I'm 14 years old, and im hoping some of you can help me out with some basic stuff to make it better and to improve features. If any of you want to help me make a better game, just post down a few links/tutorials/packages. Also the inventory isn't for selecting blocks, its for selecting different tools to use, such as a Flashlight, Binoculars or a Gun/Bow'n'Arrow.

    Download of the latest version : DOWNLOAD
    Link to Web Player : LINK ( Don't know how to set it up, I've tried many times :( )
    Also PM me, or Skype me : Dry.Tears.Unite, IF you can help me
     
  47. GibTreaty

    GibTreaty

    Joined:
    Aug 25, 2010
    Posts:
    792
    "Can change the specifications of the Terrain ( Pro, cant do that in Minecraft can you? )"

    Actually yes, yes you can. There are mods where people have created completely different biomes/worlds. Plus there's an option in regular minecraft to decide how the land is generated. But good job that you got most of it working in 3 days. Haven't tried your demo yet.

    Do you have any pictures?
     
    Last edited: Jun 3, 2013
  48. GenericGame

    GenericGame

    Joined:
    Nov 26, 2012
    Posts:
    206
    so, Notch from minecraft is now using Unity3d to design a Voxel Dungeon. A voxel dungeon, in unity3d, by notch himself, i'm gonna be trumped in no time. How much do you bet he is reading this forum thread? There is no way he is just going to instantly know how to use Unity3d to remake a voxel world using unity3d technology without first researching here.

    https://twitter.com/notch/status/331159968424271873

    If you are reading this notch, gimme thoughts on my game? be kind.
     
    Last edited: Jun 3, 2013
  49. goldbug

    goldbug

    Joined:
    Oct 12, 2011
    Posts:
    767
    ZorNiFied, it is looking great, I particularly like the mass building function.

    Are you planning on having enemies? or it is strictly a creative game?
     
  50. goldbug

    goldbug

    Joined:
    Oct 12, 2011
    Posts:
    767
    Having had quite a bit of success with Block Story, we are working on a new game called Cubica

    We want to use the technology we developed for Block Story, and turn it into an MMORPG for mobile. Here is a picture of what the character will looks like.

    $F8bUbKusvy4.jpg
     
    Last edited: Jun 5, 2013
Thread Status:
Not open for further replies.