MineCraft style game

OK, I know I'm the 10,000 person to ask this question...but I couldn't find anything asking the right question.

I've had an idea for a game for quite awhile and my son playing minecraft has re-inspired me to pursue this project again. How on earth could I possibly manage the memory for a bunch of blocks (mincreaft style). It appears to have no small limits in any direction on the map but assumming a typical map is around 512 x 512 x 128, and 256 choices of blocks, we could easily be at over 33 meg storing that array of data, not even counting the objects and the textures. Do you think they handle this by just loading all the objects? Any thoughts or ideas on if this is possible within Unity (as it's done in Java, I'm guessing that with some clever design this is absolutely possible). If so, how about loading neighboring "biomes"? I'm hoping people want to brainstorm this concept a little bit. Just as a developer I'm facsinated with how clever this program is.

 

There is a minecraft clone project floating around somewhere on the forums. It's open to anyone to download and see how it was created. Just do a quick search. I've played around with it and it seems like everything ran just great.

 

Just created a Voxel Engine for Unity.

We simply store the voxels in Chunks of 32x32x32, in a Chunk controller holding all Chunks.
Each Voxel is a simple byte, in a list, deciding the type. Each Voxel also holds a ref to a color in a color array, which is used for when drawing or changing a voxel.

Sure it takes up some memory, but so does Minecraft. We tested a level the other day consisting of 150 million voxels, worked fine.

However changing the world needs you to redraw chunks, and worse re calculate the mesh, which can be a bitch. I used a lot of time coming up with a smart way of changing the mesh collider without killing performance. And there is a lot of other problems with it, so be ready to spend a LOT of time creating a game like this if it should work well.

We can however even create "2D" voxel worlds with great depth, from a single PNG now, and much more

 

Thanks! I will have to further research this. Perhaps I'm thinking a little too old school in CPU//memory capabilities.

 

Why do you do anything with a mesh collider? I haven't done this kind of thing, but I'd have thought that primitive colliders would be lightning fast for it.

 

If you want it to work with unity's rigid body or char controller, then you want a mesh colliders in order to have a small amount of objects in the game

 

What happens when the object count is too high? And what exactly are we calling high?

 

Performance goes to hell. We did start out by trying to use simple colliders for each voxel on an empty game object. Even small levels with a a few 1000 voxels were unplayable.

And as we need more then 100 million voxels in our levels for the game we are building you can see the problem. (Newest level runs smooth with 180 million voxels, but takes some time to load ofcause)

 

So am I understanding you right here...do you recreate the meshes of the objects on the fly and/or the colliders?

What I wanted to do was work with a fairly small single world (512x512x128 maybe). I was hoping I could get away with simply instantiating cubes everywhere, but in addition to that I do want to use physics. I guess I'll need to start some proof of concept apps.

 

Yes we change meshes and mesh colliders on the fly, so i can destroy and build the world. Mesh colliders is by far the biggest problem as its is extremely performance heavy, so you need to divide you chunk into as few as possible tri/verts if you do not want to wait a second everytime you change a single voxel. Also by chunking it up you got practically no draw calls, i think our level got like 25 draw calls

A 512x512x128 world is still 33 million Voxels. That is not possible with cubes.

 

Fair enough. I've been able to have a few thousand primitive colliders running on even mobile devices without an issue in the past, but I guess different scene structures could end up having wildly different performance characteristics.

 

Can you give me any ideas on where I can begin researching building these dynamic meshes? I've only ever created objects with 3d software. Are you really able to reduce the triangle count? I mean, I see how you could not include meshes completely surrounded by other meshes (granted, that would be the majority especially on an undug map). I haven't explored the boundaries on minecraft but I imagine you could build an intensive mine network that would make every cube visible...does this affect it's performance?

 

Mikola Lysenko's blog should be a good starting point
http://0fps.wordpress.com/2012/06/30/meshing-in-a-minecraft-game/

So will a google search for "greedy meshing".

I wouldn't worry too much about the polyreduction aspect, just the surface/interior testing, which by itself is pretty straightforward. Also, while memory requirements are probably not a major concern, some of the super-efficient clever code approaches are also very short and easy to implement, if you have a good intuitive grasp of what they're doing.

BFGames's suggestion to work with n*n*n chunks is excellent, for many reasons but especially resurfacing and sparse updates for serialization. As for physics, if MeshCollider is too slow, you could use something like the intersection tests from XNA (http://xbox.create.msdn.com/en-US/education/catalog/sample/collision). I'm using a modified version of that for content tools for an MMO with some partitioning and additional tests (different type of content but similar performance goals).

Cheers,
-Adrian

 

Thanks. That was a very helpful link.

The greedy meshing is interesting. I wrote something that did just for a ground map I made a while ago (iPhone didn't have the GPU for a larger terrain map). It didn't work out very well for me because of an unexpect side affect. Imagine if you have 2 cubes on row 1 and a double wide cube on row 2. Even though they line up perfectly in design, when you start to move the camera around the center points on row 1 will not always line up correctly with row 2. Perhaps I'm doing something wrong but in general I found that things look better if vertices meet at the same place. Am I mistaken on this? Plus, how would you handle textures?

 

Hm, you know, I remembered that post being more interesting, although reading over it again, it really is a lot heavier on polyreduction than I thought. I thought there was more about general implementation.

Minecraft just uses culling, as far as I know, since the issues you bring up with greedy meshes are definitely problems. You can see code for Lysenko's simple culling implementation here https://github.com/mikolalysenko/mikolalysenko.github.com/tree/gh-pages/MinecraftMeshes/js. Although you can see that he does not handle winding order.

But again, I think a naive implementation based on simple neighbor data would be pretty straightforward... basically if you don't have a neighbor in some direction, put two triangles there, wound appropriately (and then endless work related to caching I'd imagine). I don't think you'd want to try sharing verts, since you can't on corners or block type/texture seams anyway, but it's easy to add that if needed.

As for dynamically creating meshes, it's actually really simple. Basically you are just populating buffers, the main two being vertices (Vector3[], one for each vert in the mesh), and triangles (int[], always a multiple of three of course). UV, UV2, normals, tangents, and colors are all per-vertex so you'd create them at the same time.

Winding order can be tricky to get right. I have a distantly-related project on my blog (http://adrianswall.com/?p=229), a retopologizer which goes through a Minecraft-looking phase, and although the code is overcomplicated and the problem it solves is different, the meshing code itself may be of some interest. Also, this recent post (http://forum.unity3d.com/threads/177659-Connect-2-meshes-in-script?p=1215037&viewfull=1#post1215037) creates a cylinder, and actually that's one of the smallest/clearest examples I can find of building a mesh right now! Where the triangle indices are added, you'll see it tries to reuse verts... if you instead created new verts and added their IDs for every tri, that would give you a faceted model, which is what you need for Minecraft meshing.

Completely OT: Since you mentioned large terrains, (again pulling from memory here), have you looked into geoclipmapping? http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter02.html That article gets lost in some weird details too, and the technique requires vertex texture fetch, something which iOS used to support but no longer does. Still an interesting concept.

Cheers,
-Adrian

 

Well I got into the idea and wanted to do a quick proof of concept of the quick neighbor test meshing, so here it is:


Project files: adrianswall.com/temp/SimpleMinecraft.zip

This isn't optimized, but it works as described above. For demonstration purposes, it builds out a ground at y=0, and has a chance of building up on +y from there. The point is to generate some type/neighbor data to demonstrate (implicitly culled) meshing from source arrays, and handling some specifics like chunks and UVs for cell types.

The code is in WizardBuildGround.cs.

Lots of places to go from here, but a decent quick and dirty proof of concept.

Cheers,
-Adrian

 

Any colliders on there?

 

No Unity colliders. As I was saying in a previous post, I've been using a modified version of an XNA intersection test suite (just a bunch of functions). This allows custom partitioning, return types, content-specific optimization, etc. It can also be run on a server alongside or instead of Jitter, which is nice as well.

This was done quickly mostly to answer the OP's followup question about meshing. But I was thinking about collision quite a bit.

Raycasting (for mining) doesn't need intersection, just use the cell type map, player position, and orientation. It's not even an AABB test because it's snapped to a grid too.

I'm not sure if this is true, but there might be some benefits to making local updates to chunk meshes, which requires knowing which polys belong to which cubes (cubeXYZ->first triangle index... since all verts and tris are built per cell in order in this example, you only need offset and number of faces to get polys). That's a lot of storage of course so I don't know how practical it is, although I do know it can be built at at almost no cost.

For character collision, type data and pooling AABB instances would work, or storing polys per cell. Or some basic partitioning, or maybe even none at all since the chunks already provide some. And I think you can do it without the capsule too, since there are no hip-level colliders in Minecraft. So everything could be two spheres and some AABBs. At least for this primitive terrain, and then per-poly tests for props or ramps.

So I like the collider-free approach, although it adds a lot of work on top of this simple meshing example.

Regards,
-Adrian

 

Im making an Minecraft like game too, but anyways i surfed thru the web and i found these two usefull links:

http://www.forum.unity3d.com/thread...se-in-progress-(terrain-generation-etc-).html

http://www.answers.unity3d.com/questions/177931/tutorial-minecraft-chunks.html

Hope it helps :]

 

Thanks for all the replies. Hausmaus, I couldn't get your code to do anything. Was it complete? DryTear, none of your links were working for me. I finally got a chance this morning to start digging into this and my licesnses are messed with the latest Unity, none of the samples are working, none of the links are working...off to a great start . I always forget how much trouble it is to reset up my UI after an update.

 

Chris,

Yes, my example is complete, if you downloaded the project. You should find a "Minecraft" option in the main menu, with only one entry. Click that, and it will do its thing. Note that it can be run many times, it will just destroy the previous output.

I have a modified version here which also does AO (seemed easy enough to add and I'm an AO whore) which I can post if that one still doesn't work.

 

Try now, if it still doesnt work- try to copy and paste the link into the address bar

 

what's this?

how can i fix this problem?

 

I am surprised you are using mesh colliders! If you are using square based voxels, it is much easier to do intersect testing!

 

Playbucks,

If it were consistent, it would look like the boundaries within your atlas are wrong (something is 65px wide instead of 64px) or you have a rounding error for UVs on one side of the cube. But it isn't consistent so a simple explanation like that doesn't seem like it would help.

Can you please explain how you are generating your mesh?

 

After receiving your files(`adrianswall.com/temp/SimpleMinecraft.zip`), it does not have a modify.
Just open and run..

 

We have a HUUUUGE thread already on this.
http://forum.unity3d.com/threads/63149-After-playing-minecraft