Minecraft + Physics = Awesome!
Posted: Wed Mar 09, 2011 6:07 pm
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.
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.
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
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.
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.
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