Page 1 of 4

Minecraft + Physics = Awesome!

Posted: Wed Mar 09, 2011 6:07 pm
by Chris
There is an awesome video at the end of this post, but can you resist the temptation and read the context first?

Like many people I lost about a week of my life to Minecraft, obsessively mining and building and improving my zone until I had a vast interconnected array of castles, houses, and underground palaces. When a creeper attacked me outside the entrance to my underwater safe house and detonated himself, flooding my carefully crafted construction, my cry of “Nooooooo!!!” was more real than any game moment I can remember. It was awesome, one of the best game experiences I've had for a long time, and undoubtedly my game of the year for 2010. We were at the IGF awards ceremony just a few days ago, and it was frankly a relief to see Minecraft pick up the IGF grand prize (along with the audience award, and 3 of the Choice awards as well – has any game won awards in both the IGF indie section AND the choice awards before?) Why a relief? Let me explain.

It's probably not widely known, but I was one of the judges for the IGF Technical Excellence award this year, which went to the amazingly advanced graphics tech of Amnesia – a worthy winner in a category that specifically rewards tech over everything else. Minecraft was nominated in virtually every category, however I was a bit worried for the game, and the IGF in general. I got the impression of a strong and vocal undercurrent of voices that believed Minecraft shouldn't even be eligible for the IGF – because it had already been massively successful. These judges believed the primary purpose of the IGF was to shine a light on new Indie Gems that had yet to see major press/public attention, and that this would be wasted on Minecraft. The $20,000 prize money on offer would mean nothing to Notch, who probably earnt more than that while eating his breakfast that morning.

In my opinion the purpose of the IGF is to celebrate the best Indie games of that year, regardless of that game's commercial status. The discussions between the judges were making me really nervous – some believed it shouldn't be eligible, others believed it couldn't be beaten. If by some quirk of the final vote Minecraft didn't win a single IGF prize, what would this mean for the IGF? It certainly wouldn't look good, and would leave the judging process wide open to criticism of negative-favouritism and indie elitism – “you only get to be Indie if you live in your parents basement”. If you're not Indie, Fuck You! It makes me worried personally, because we may decide to enter our Next Game into the IGF, and I have to believe the judging process is fair. Would we be silently disqualified, simply because we've been around a while, and we're a prior winner? Thankfully in the grand prize group, clearer thinking seems to have prevailed. Well done Notch, and well done the IGF.

Like many Indie developers who lost time to Minecraft, once I'd stopped playing I begun the process of kicking myself for not thinking of it first. I wanted to understand how the underlying tech worked, and see if you could go further. So almost every tuesday afternoon at the CB2 Indies group in Cambridge UK, instead of working on Subversion I'd work on my minecraft inspired Voxel Engine. Sort of Minecraft crossed with Subversion crossed with Tron. It's been a really fun side project.

Image

Some Technical details, for those interested. My first version recreated a voxel engine in the simplest way I could think of. A massive array of cells, total size 128x128x128, each cell representing a single block in 3d space. Coupled with that, a single openGL vertex array of triangles. When the user switches a cell on, I add triangles into the vertex array to build a cube in the right place, and store the indices of the triangles in the cell. When the user switches a cell off, I look up the indices of the triangles that represent that cell visually, and set them all to zero, effectively removing them – openGL doesn't bother rendering triangles that are at zero/zero/zero. I render the world simply by rendering the entire vertex array in a single call. This was so quick and dirty I had the basics up and running in 3 hours. Of couse it's massively inefficient, because there are tons of wasted polygons – ie if two cubes are touching each other, you don't need any triangles between them, because the user can't see that bit, and also because your massive vertex array has tons of zeroed triangles in it, wasting tons of GPU time.

The second, much better version of the engine works basically how I *think* Minecraft is working. The world is actually divided into chunks, and each chunk represents an area 16x16x16. Putting lots of chunks together in a larger rubiks cube style 3d grid gives you your expansive world in all directions. Each chunk has its own storage for the cells, and its own Vertex Array. When the user switches a cell on or off, I look up the correct chunk first, then in that cell I change the cell data to represent the new value, then I rebuild the entire vertex array for that chunk. I was worried this would produce a noticable sudden slowdown when you toggled a block on or off, but actually it takes fractions of a millisecond to rebuild even a complex chunk. This is also much more efficient because you can be selective when building a vertex array – I don't bother adding triangles if I know they won't be seen. This means many chunks in the world are completely empty – ie totally underground, or totally in the air, and have zero triangles wasted on them. Rendering the world requires a render call for each visible chunk, probably several hundred chunks to render a scene, but easily low enough that my graphics card can keep up. This method took a lot longer to get right, but the end result is much faster and much more memory efficient, and much more open to massive world streaming.

Eskil Steenberg (creator of Indie MMO “Love” - which is also a Voxel world engine of sorts) has told me that he doesn't bother with small chunks – he just has a single Vertex Array that represents an entire quadrant of his spherical world, and to get around the massive waste of space he actually has to _defrag_ his graphics memory using his own memory management functions running on his GPU, effectively pushing all the active visible triangles together, and leaving a single large clear area of graphics memory for future triangles to be placed. This is the kind of batshit crazy engine programming I've come to expect from Eskil, and is not for the faint of heart.

Once I had the voxel stuff working I did some procedural generation experiments : a building, a large open landscape using a Perlin Noise function, and a pyramid. And then I had the brainwave : once you have chunks, there's nothing stopping you going all the way to rigid body physics. Each chunk gets its own physics mesh which is rebuilt using the same geometry as the vertex array. Then when you remove a block I also spawn a cube at the exact position and orientation, and hand it over to the physics library. (Which is Bullet Physics, for those interested). This totally fools the eye into believing the voxel cube in the world has suddenly taken flight and bounced around the world.

Image

Net result : Minecraft + Physics! This is just a prototype, just a tuesday afternoon hobby project, but wouldn't it be awesome to play an FPS or a wargame with this kind of totally destructible environment?

We are using youtube for all our videos now, instead of the xvid AVIs we've posted here before. This should mean videos play on everyones system, they can be embedded, they don't sap our bandwidth, and they can be streamed at whatever quality you want to see. Subscribe to our youtube channel to be sure you see everything we post. We are also using Twitter now @IVSoftware, and we posted a lot of live updates while we were at GDC this year. Sign up to stay in touch!

And here is the video I've been promising all along. We hope you enjoy it ;)


Posted: Wed Mar 09, 2011 6:51 pm
by Xocrates
Out of curiosity, how small can the voxels be or, alternatively, how big can the visible world be without killing a modern PC?

Posted: Wed Mar 09, 2011 6:56 pm
by ChicOrtiz
Hey nice Chris! Congratulations!

Would you care to comment what's your strategy to have this running fast across the network? (< Considering you already thought about that ; )

Posted: Wed Mar 09, 2011 7:01 pm
by verbii
Awesome vid, was wondering do you have any plans to add the kind of physics so that if enough of the building (or certain important parts) were destroyed it would collapse under its own weight?

Sure that would be 100 x more complicated but would be cool ;D

Posted: Wed Mar 09, 2011 7:18 pm
by Jordy...
As I watched this video, while my eyes filled up with tears, I envisioned a world that was a combination of minecraft and subversion, a world populated and controlled by players.

Now I realize that will never happen and I wonder, other then you showing of your brilliance to me, what does this video do for ME?!
I WANT GAMES!

Anyhow, on RPS I noticed a headline saying: "why Notch things minecraft 2 will not be made by him" or something alone those lines, I didn't bother reading it, but I'd say, hell better improve on the good stuff then to spent time re-inventing the wheel.

Posted: Wed Mar 09, 2011 7:39 pm
by _human_
Nice video but personally I don't share much enthusiasm about crumbling houses and pyramids...

Posted: Wed Mar 09, 2011 10:13 pm
by lozhuf
Ah, Voxels.

I so lament that they weren't embraced instead of polygons as the building blocks of advanced graphics engines. Imagine a world where voxels had had the budget/research of DX/OpenGL has had for the last 10 years (though there were obvious technical reasons). The ability to represent every "atom" of the world, and more than just color/position, also physical properties, such as conductivity/combustability/temperature/etc, leads to so many amazing gameplay possibilities.

I guess one of the main issues for non-procedurally generated worlds, beyond generating the assets, is storage - both level map files and in ram... a 1km cubed world of 1cm cubed voxels (pretty rough) would be 100,000*100,000*100,000*voxel. If a voxel is 1byte that would be a map file of 909TB! (obviously this is worst case, with no empty spaces...though you could argue there are no empty spaces, just atoms with different properties) Some sort of compression algorithm would obviously be needed, and I've wondered whether some of the ideas from 2d image compression could apply - gif perhaps, or even a variation on the ideas of jpeg compression.

I imagine that when the day comes when we are representing our games entirely with voxels, it will be a mix of procedural and pre-generated - define the broad strokes of the structure, and procedurally enhance the details as you get closer to the surface, perhaps based on the properties of surface itself.

Check this guy's work out for an interesting voxel implementation: http://www.youtube.com/watch?v=1sfWYUgxGBE

A man can dream...

CB2 Indies group

Posted: Wed Mar 09, 2011 10:19 pm
by Zarkonnen
You mention a "CB2 Indies group" in Cambridge. Is this a meet-up in the CB2 cafe? I ask because I'm a Cambridge-based indie developer.

Posted: Thu Mar 10, 2011 12:36 am
by quickdan
Awesome video. That would be neat to have different physical properties for different blocks. If they could figure out a way to make them more efficient they would be a much more realistic approach to how the world actually operates.

Posted: Thu Mar 10, 2011 2:51 am
by Stormy Dragon
Wow, with this post, the Introversion blog/news feeds have since last summer spent more time talking about Minecraft then anything Introversion is actually doing...

Posted: Thu Mar 10, 2011 3:20 am
by Feud
_human_ wrote:Nice video but personally I don't share much enthusiasm about crumbling houses and pyramids...


I, however, have nearly unbridled enthusiasm for crumbling houses and pyramids. :D

Re: CB2 Indies group

Posted: Thu Mar 10, 2011 4:50 am
by allen
Zarkonnen wrote:You mention a "CB2 Indies group" in Cambridge. Is this a meet-up in the CB2 cafe? I ask because I'm a Cambridge-based indie developer.


check here: http://cambridgeindies.com/

Posted: Thu Mar 10, 2011 5:04 pm
by Rkiver
Wow. That pretty much sums up the video.

I agree that while Minecraft should have won the award, due to the fact it's already a huge commercial sucess for a game not even released, perhaps a dual prize. One for cash given to the other winner, and a nod to Notch for what he created.

Regardless, nice video.

Re: CB2 Indies group

Posted: Thu Mar 10, 2011 7:29 pm
by Zarkonnen
allen wrote:check here: http://cambridgeindies.com/


Thanks - will check it out next Tuesday.

Posted: Thu Mar 10, 2011 9:39 pm
by skull13
Notch has actually just revealed a little bit about his terrain generation right here:
http://notch.tumblr.com/post/3746989361 ... ion-part-1