Metaphysical Developer

Implementing Minecraft in WebGL

Posted in hacking, Minecraft by Daniel Ribeiro on December 20, 2011

TL;DR: Source here, live demo here.

ROME project

ROME project

WebGL is an amazing piece of technology that enables browsers to natively render hardware accelerated 3d creations (yay, no o3d plugin needed!). I’ve always been specially amazed by what Mr Doob has been doing with his Three.js framework for quite a while (in particular his participation on the ROME project, which I briefly talked about recently). Nonetheless, there are some other amazing WebGL creations around, such as those featured on Chrome Experiments, those crafted by OOS and the projects recently presented on WebGLCamp (not to mention the amazing Team Fortress 2 level vizualizer).

One thing that has bothered me though, throughout all the examples, is the lack of interactivity (one glaring exception was GLGE‘s car demo) .

This seemed to be from the fact the 3d collision is quite a bit more involved than 2d (MIT’s lecture notes on Computational Geometry, and even on Doom 3′s recently released source code, can give you an idea of how much involved it can get). And since this is considered to be one of the important things  that 3d games need, I was not happy with my hands off answer of this topic on Hacker News. Thus I took the challenge of making a a 3d game in WebGL with collision detection.

Implementing Minecraft Classic (which is playable online for free) seemed like a good candidate for such project, as its mechanics are simple, and yet meaningful (not to mention that I am big fan of Notch’s creation). If you don’t know anything about Minecraft, I wrote a small intro about it a few months ago.

Enterprise created in Minecraft

Three.js was selected as the rendering lib not only because I really like Mr Doob’s work, but also because it has is quite mature, is open source, has lots of examples and provides a very promising starting point: a visualization of a Minecraft world, which includes a noise function for generating it.

So all that was left was just adding Collision Detection. Well… this is where things started getting interesting.

Minecraft Collision Detection Attempt 1: JigLibJS

Jiglibjs is a port of Jiglibflash, which in itself is a port of Jiglib for c++. It seemed pretty promising, since there was some people using it (along with three.js), and I had great success with using physics libs in the past for 2d games, so it seemed like a natural choice.

After getting it to work with a prototype of the game, it became clear that some things were very wrong. The amazing demos were too simple for Minecraft, and the rotation would get really wrong when walking on simple plane surfaces (something I speculate happening due to some numerical stability differences from ActionScript and Javascript, alongside with some AS3-> Flash compiler bugs).

JigLibJS demo

After some fun 4 dimension matrix hacking, and failing to get around the bugs, I was ready to move on. Thankfully I found another port of JigLibJS which seemed to correct such issues…

Minecraft Collision Detection Attempt 2: JigLibJS2

The fact that someone tried to make a more complex example on JigLibJS, failed, but was tenacious enough to write its own AS3 -> JS compiler to make another port (which worked!) made a very positive impression.

JigLibJS2 Vehicle Physics Demo

It was also very positive the fact that the interface was almost the same to JigLibJS, making the change to the existing code very small. The problems started to come when trying to make the player cube jump: the cube would not always collide with the bottom plane. This was solved by making more collision iterations. Soon enough another problem came up: when trying to move inside an adjacent static cube (even when both the player and the cube were in the same height), sometimes the player would get a rotation. Trying to set it to no rotation every iteration did not actually help, as the player would still sometimes get a vertical velocity when trying to penetrate the block.

Still, rolling my own Physics Engine seemed a bit daunting, and I decided to try out another lib:

Minecraft Collision Detection Attempt 3:  Ammo.js

Ammo.js is a port of the C++ physics engine BulletPhysics, that runs on top of the LLVM‘s Javascript port, aka Emscripten. Everything looked amazing this time: the demos not only looked great, but were very hackable, and had no problems that I previously had.

Ammo.js Demo

But then it came the time to try to get to more Minecrafty world dimensions. It was a bit disappointing when mere 400 cubes made the physics engine go to a crawl (even when using static cubes). It became clear that I needed O(1) collision algorithms, which is very doable for Minecraft Classic, as only the player can move, and there is always a constant amount of cubes the player can collide with at any given time. And now there were no more libs left to evaluate.

Minecraft Collision Detection Attempt 4:  Rays!

Rays are the standard way of detecting line/Object collision in Three.js. A very simple interactive demo by OOS seemed like it could do the trick. It had the advantage of being very simple, and constant time (given that I selected the possible blocks to collide with, as the traditional Ray.intersectObjects actually tries to intersect all objects on the Scene).

Ray Collision Demo

The OOS example had some issues (like trapping the player cube when jumping up and down, while hodling the forward key). This was solvable by using 12 rays correspoding to the edges of the cube that represented the player. Actually, this did not help all the time, as some rays would not collide with the world blocks if the ray’s origin inside a blocks’s face. This is a bug yet to be solved, but I got around it by using 24 rays (two directions for every edge of the player cube).

Things were going well enough that I finally moved into adding textures to the game. However, after making the player cuboid have size dimensions to Minecraft’s, instead of having the same size of the world’s cube (which was what I was experimenting with so far), I noticed that the ray would give false positives depending on the height position of the cube. This only happened when the numbers were all too exact, instead of with minor deltas, as you’d expect from using rays cast from the mouse pointer (as it is usually used on Three.js’ demos).

This, and the fact that collision was taking about half the time of every tick (which was constant, due the improved collision algorithm) made me move on to…

Minecraft Collision Detection Attempt 5: Cube Projection

Up until now I had hopes that I would be able to eventually rotate the player cuboid according to its camera. After having so many troubles with so many collision systems, I simplified the problem: collision of unrotated cuboids. This is a really simple problem: from the Separating Plane Theorem, it is easy to see that  I only need to see if the orthogonal projections of the cuboids, which, from the Separating Axis Theorem, means I only need to check out if the unrotated rectangles from the projected faces collide, which finally means I only need to check if the projected intervals collide. All of this amounts to 13 lines of Coffeescript:

CollisionUtils =
    # The two intervals are [s1, f1] and [s2, f2]
    testIntervalCollision: (s1, f1, s2, f2) -> !(s2 > f1 || s1 > f2)

    #Cubes are objects with vmax, vmin (the vertices with greatest/smallest values)
    #properties. Assumes unrotated cubes.
    testCubeCollision: (cube1, cube2) ->
        fcol = CollisionUtils.testIntervalCollision
        for axis in ['x', 'y', 'z']
            collides = fcol cube1.vmin[axis], cube1.vmax[axis]
            , cube2.vmin[axis], cube2.vmax[axis]
            return false unless collides
        return true

window.CollisionUtils = CollisionUtils

Which in retrospect is what I should have tried in the first place. At least I learned some stuff in the process.

Not quite finished yet: Camera

Paul Irish did a pretty amazing job with the Three.js FirstPersonControls.js, which is the one that powers the Three.js Minecraft visualizer. The problem with this camera is that it makes hard to actually play Minecraft, as its default mode is to be always moving, making hard to place/remove blocks. Real Minecraft uses first person shooter camera which cannot be achieved with current browsers, as there is no way to trap the user’s mouse. Nevertheless, Minecraft on Android uses a touch and drag camera that can easily be implemented in JS. This camera works they same way as the one on Brandon Jones’ Quake 3 WebGL implementation.

Quake 3 demo

Therefore I refactored, and converted to Coffeescript, the FirstPersonControls to work as a click and drag camera. The resulting 86 lines of code can be seen here.

Adding/Removing Blocks

This is where Rays worked really well. In fact, Mr. Doob even have a voxel editor example which shows really well how to make an app that adds/removes cubes on a 3d grid:

The only issue I’ve found was that my floor plane was too big, which messed up the Ray/plane collision in certain angles. So I coded this intersection directly:

    getCubeOnFloorPosition: (ray) ->
        return null if ray.direction.y >= 0
        ret = vec()
        o = ray.origin
        v = ray.direction
        t = (-o.y) / v.y
        ret.y = 0
        ret.x = o.x + t * v.x
        ret.z = o.z + t * v.z
        return @addHalfCube ret

Conclusions

I felt the result was quite satifying (the live demo, and the MIT licensed source, can both be found on Github):

Minecraft Brick Pyramid

WebGL Brick Pyramid

Granted, it starts skipping frames quite often as you add more blocks. The original example from Dr. Doob’s  didn’t because he created a single Mesh (aka object scene) composed of all blocks. Doing such would make adding/removing blocks a lot more involved (or force me to handle some area loading/unloading), which is a project in itself. Note that the rendering, and not the collision system, is the real bottleneck at this point.

All of this made me admire Notch’s work on Minecraft a lot more, as Minecraft can handle over 21×21 loaded chunks of 16x16x128 (over 14 million blocks!) in any given time. The Three.js community had some great insights on how to achieve such performance over WebGL, which requires the use of shaders, which are quite low level (even if you use the respective TDL Google Library for this, or GPipe to write the shaders in Haskell), and would probably require a lot of collision code to be also written in also a very low level language (slash GPipe’s Haskell). I found it also interesting that shaders can be used in some clever ways to improve JS performance.

And finally, it is important to note that a lot of very people a lot smarter than me have been doing some great work to make working with WebGL and making 3d games much simpler.

There are also other renderer libraries besides Three.js: Scene.js, PhiloGL, A3 (recently presented on the WebGL Camp), Coppercube (which is not open source, but can use flash for 3d rendering as well) and GLGE.

Hacker News Comments

25 Responses

Subscribe to comments with RSS.

  1. roger said, on December 20, 2011 at 1:44 pm

    NaCl?

  2. Jedediah Smith said, on December 21, 2011 at 6:35 am

    Are you culling buried block faces? That is a very important part of Minecraft’s renderer. It only draws exposed faces, which is a very small portion of them in a typical environment. I would imagine it pre-computes the set of exposed faces and updates it incrementally when blocks are added or removed, which should be doable in constant time.

    • Daniel Ribeiro said, on December 22, 2011 at 3:35 am

      This is actually a nice suggestion. However, minecraft goes on really well even when you call see tens of thousands of blocks onscreen at the same time. Three.js is not prepared for this kind of stuff. Other renderers may do it better. One way to handle this is to use Doob’s cheat: when you come close to a region, it becomes active. Active regions have the real blocks, which can be easily removed/added as it is now. Inactive regions would be rendered as a single object (using the composite geometry Dr Doob uses on his minecraft demo). This should allow the game to have blocks on the range of thousands. After that, three.js has to be either optimized/replaced. They way minecraft shows many stuff onscreen is really quite impressive (see the enterprise demo for many exposed blocks at the same time), and I am not sure it is possible to achieve such performance without resorting to shaders.

  3. [...] Implementing Minecraft Classic with cutting edge web technologies (WebGL) and Coffeescript    Javascript Read the original post on DZone… [...]

  4. hollister said, on December 22, 2011 at 6:30 am

    What a magical world

  5. Alexander Overvoorde said, on December 22, 2011 at 9:17 am

    Perhaps I missed that part, but why did you intend to use a rigid-body physics engine for a world with thousands of blocks? And why are you using a 3D engine to render blocks in the first place?

    I find this article disappointing because of the seeming lack of experience. I hope I just wrongly observed that.

    • Daniel Ribeiro said, on December 23, 2011 at 4:21 am

      Great points Alexander. Good physics engine could be very efficient, but none of of them are on this case. They do not try to scale down (very few static bodies), as that is not their goal. But you can design a scale up/down physics engine. It just hasn’t been done for 3d (box2 does this really well for 2d though).

      The rendering engine is used for simplicity. If you can prove it can be done faster/easier without it, please knock yourself out. It is all open source on Github. I’d love to see it working.

      • Alexander Overvoorde said, on December 23, 2011 at 6:41 am

        Thank you for your response. I am currently working on my own implementation and will let you know how it goes.

        Also, your post is still a great reference for different physics engines to use on the web. Thanks for that.

        • Daniel Ribeiro said, on December 26, 2011 at 9:56 pm

          Awesome! Can’t wait to see how others spin this idea.

          Thanks for the feedback. I am happy that my post had any use to any audience.

          I hope this will bring more attention to WebGL, and how we can create great stuff on the browsers nowadays. Hopefully more people will join the fun, and we will also have better frameworks/libraries supporting it.

    • Rob Hawkes said, on December 23, 2011 at 7:24 am

      “I find this article disappointing because of the seeming lack of experience. I hope I just wrongly observed that.”

      Stop trolling. Daniel has put a lot of time and effort into exploring this project, as should be commended for documenting it and releasing it in public to help others.

      I’m sorry everyone can’t be as experienced as you are.

  6. eddyb said, on December 22, 2011 at 11:08 am

    What about cursor locking (see http://blog.sethladd.com/2011/09/mouse-lock-for-html5-fps-games.html for an example)? It would make it much easier to move around. Also, I have a platform ready for SMP in browser, but I didn’t have time for an interface. If you want, I can put it on github and maybe we can work it out ;).

  7. rafaelrinaldi said, on December 24, 2011 at 12:27 am

    This is just fantastic, dude!

  8. Freshly Brewed CoffeeScript Issue #2 said, on January 4, 2012 at 3:55 pm

    [...] Implementing Minecraft in WebGL (and CoffeeScript) – An article on how to implement basic features of Minecraft using WebGL and CoffeeScript by Daniel Ribeiro. Very cool! [...]

  9. SylvainPV said, on January 5, 2012 at 7:45 am

    I’ve done a fork of alteredqualia demo with three.js. I added a FPS camera controlled with mouse and ZQSD keys, collision detections with ground, jump, and day/night cycle.

    Enjoy : http://syllab.fr/projets/minecraft/minecraft.html

  10. [...] Implementing Minecraft in WebGL « Metaphysical Developer [...]

  11. iamtanmay said, on June 19, 2013 at 5:52 pm

    Hey, there is something newer and better out there now: http://biz.turbulenz.com/samples#x3d-physics

    Its really fast. Faster than Ammo.js by miles, and its all open source on js

    Neat, huh amigo ?


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: