7 ms·

Bootable Minecraft clone written partly in x86 Assembly

285 points by charliesome 13y ago

angersock 13y ago
I love that the author decided (if my interpretation is correct) "Writing a software rasterizer is annoying...fuck it, let's use a raytracer." Very nice!
- blt 13y ago
  Ray tracing is easier to implement than rasterization...
  - joakleaf 13y ago
    It really depends on how much functionality you want for both methods. Rasterization really doesn't require that much work, but you need to be able to do a world/view-transform, clip triangles/quads, and do perspective correct texturing. The most sophisticated bit of that is a clipping algorithm, which is really easy to implement. Ray tracing requires you to generate a ray per pixel (essentially the opposite world/view-transform), determine ray/box intersections, and based on the intersection coordinate of ray and box determine a texture coordinate. As someone who has done both, I would say the two procedures are pretty the same level of complexity (if you stay away from bilinear texture interpolation), but I admit that raytracing feels easier to implement as you avoid the clipping and perspective correct texturing. However, The Minecraft world is a uniform grid of "boxes", so it contains a lot of quads leading to potentially huge amounts of overdraw which quickly becomes infeasible for a software-rasterizer. So if you wish to rasterize in software, you'll need to do a bit of additional work to avoid drawing a lot of hidden box-sides (ignore shared sides), and you'll never get overdraw down to 0 unless you use additional screen-based data-structures. On the other hand, the author had to implement a raycasting algorithm on the uniform grid for the raytracer to be efficient. This is actually also a little bit painful. So for that reason, the ray-tracer is definitely the right decision here. On a related note, I tried to implement raycasting on a uniform 3D grid on a 486/66 Mhz in 1996... Got around 2-5 FPS in 320x200. So it was completely infeasible back then.
  - kaoD 13y ago
    I've done both and ray tracing techniques are much more complicated and heterogeneous.
- exDM69 13y ago
  This isn't a typical raytracer. Instead, it's a very clever ray marching in a uniform grid. It resembles a Wolfenstein/Doom -style raycaster more than what you usually think of as a raytracer.
yalue 13y ago
When I tried to build the project I got a linker error, but running the prebuilt iso (linked in the readme) with qemu worked just fine. A very impressive project! Edit: The link error is probably just a stupid mistake on my part; I was trying to build on a 64-bit machine. It doesn't seem to have any problems on 32 bit.
- Smerity 13y ago
  For others who might be interested, compilation works fine in Ubuntu 12.04 after `apt-get install build-essential nasm qemu`. If you install libsdl and libsdl-dev you can run the reference version written in C which runs significantly faster. It's indeed an impressive project, doubly so as it was initally only for a university project. Instead of just making a game in assembly he made the project his own by extending it -- bootable, raytaced, raytraced shadow, textures and so on! =]
  - 300bps 13y ago
    >Instead of just making a game in assembly Not to discount what he did, but he didn't write the game in Assembly. He wrote it in C then decompiled it to Assembly and used that as a starting point for the Assembly code. From the article: >Starting in assembly right away would be a bit too insane, so I first wrote a reference implementation in C As someone who started in Assembly right away creating several games with a much simpler 6510 CPU, I can vouch for the fact that starting in Assembly would be a bit too insane especially on modern CPUs.
    - 6ren 13y ago
      He doesn't say anything about decompiling. > Then I began slowly porting everything to handwritten assembly.
      - 300bps 13y ago
        >Starting in assembly right away would be a bit too insane, so I first wrote a reference implementation in C How did he make the reference code? I'm reading that as he wrote an implementation in C, then decompiled it and then cleaned up the decompiled Assembly language code. Maybe I'm wrong. How do you take his statement above?
hdra 13y ago
Wow. Impressive project, especially as a university assignment (I am assuming a bachelor's degree), considering I see a lot of people graduating university without being able to even write the most basic CRUD app. I myself can't even manage to finish a simple 2d game I started months ago. Kudos to the author.
- mjfl 13y ago
  as a Computer Science student, I am embarrassed that this is true at least for me, though I am eager to learn...
  - irishcoffee 13y ago
    Its only embarrassing if you've tried and couldn't figure it out.
    - graupel 13y ago
      And given up trying to!
    - deleted 13y ago
      [deleted]
  - hdra 13y ago
    the eagerness is the most important thing in learning. I'm sure we all know SE major students who aim to get a job as a "project manager" right off the bat, not because they actually love/know anything about managing a project, but simply because it is a managerial position where you don't have to code.
- ctdonath 13y ago
  Nicely complements the nearby thread "Building a Modern Computer from First Principles" https://news.ycombinator.com/item?id=5888705 https://news.ycombinator.com/item?id=5888705
- dom96 13y ago
  As a student who is hoping to study Computer Science in a years time, I hope that the university I enrol at encourages such projects!
kriro 13y ago
Impressive. I also like his approach of prototyping it in C first (I chuckled at the thought of C as a prototyping language). That reference is also in the repo and I hope to at least read that :)
- mrmekon 13y ago
  Everybody I know who writes assembly language in practice now, self included, prototypes most of it in C first -- why not take the huge headstart from the compiler generated ASM? And I usually prototype the C in Python first :D
  - mrbrowning 13y ago
    In those cases, are you writing in asm for fun? If not, what advantages do you see in taking this approach over just writing most of the project in C and using inline asm where necessary?
    - mrmekon 13y ago
      It usually is inline assembly, but you write it in C first and copy the disassembly as a starting point. We do this in the embedded world a lot because we're constantly switching architectures, and nobody memorizes the instruction set of every architecture :) The most common reason is using architecture-dependent instructions that the compiler doesn't generate well, or doesn't generate at all. Examples are SIMD (auto-vectorization is nice, but far from perfect) and DSPs that have specific multiple-and-accumulate instructions or flags that change the behavior of the accumulate register. In a project I'm currently working on, inlining was still inferior to fully native ASM. LLVM generated unnecessary stack loading in the prologue, and the completely unused memory access had something like a 4% speed penalty.
      - jevinskie 13y ago
        Would you please file a bug report [0] with a reproduction of the missed optimizations that you see? I'm interested in taking a look at it. Today LLVM trunk enabled the vectorizer for -O2 and -Os. [0]: http://llvm.org/bugs/enter_bug.cgi?product=libraries http://llvm.org/bugs/enter_bug.cgi?product=libraries
voltagex_ 13y ago
Cool! I think this would also be PXE-bootable with iPXE and a chain command.
FreeFull 13y ago
Seems to break when you press multiple keys at once. Movement starts and then doesn't stop. Otherwise, it is pretty good.
arsen1k1 13y ago
Looks like the kind of app the Kolibri OS (http://kolibrios.org/ http://kolibrios.org/) would love to see ported to their platform. Is it possible to do?
mosqutip 13y ago
I thought my asteroids game in assembly was cool. Great job!
- rpicard 13y ago
  Is the source code online somewhere?
  - TheAceOfHearts 13y ago
    Shameless plug of an ASM project I did: https://github.com/cesarandreu/INEL4206-XString https://github.com/cesarandreu/INEL4206-XString (Video in link)
rcthompson 13y ago
Now we just need a Redstone x86 processor to run it on.
parski 13y ago
It looks more like an Infiniminer clone. Impressive none the less.
mikkom 13y ago
Any screenshots?

285 points by charliesome 13y ago

I love that the author decided (if my interpretation is correct) "Writing a software rasterizer is annoying...fuck it, let's use a raytracer." Very nice!

blt 13y ago
Ray tracing is easier to implement than rasterization...
- joakleaf 13y ago
  It really depends on how much functionality you want for both methods. Rasterization really doesn't require that much work, but you need to be able to do a world/view-transform, clip triangles/quads, and do perspective correct texturing. The most sophisticated bit of that is a clipping algorithm, which is really easy to implement. Ray tracing requires you to generate a ray per pixel (essentially the opposite world/view-transform), determine ray/box intersections, and based on the intersection coordinate of ray and box determine a texture coordinate. As someone who has done both, I would say the two procedures are pretty the same level of complexity (if you stay away from bilinear texture interpolation), but I admit that raytracing feels easier to implement as you avoid the clipping and perspective correct texturing. However, The Minecraft world is a uniform grid of "boxes", so it contains a lot of quads leading to potentially huge amounts of overdraw which quickly becomes infeasible for a software-rasterizer. So if you wish to rasterize in software, you'll need to do a bit of additional work to avoid drawing a lot of hidden box-sides (ignore shared sides), and you'll never get overdraw down to 0 unless you use additional screen-based data-structures. On the other hand, the author had to implement a raycasting algorithm on the uniform grid for the raytracer to be efficient. This is actually also a little bit painful. So for that reason, the ray-tracer is definitely the right decision here. On a related note, I tried to implement raycasting on a uniform 3D grid on a 486/66 Mhz in 1996... Got around 2-5 FPS in 320x200. So it was completely infeasible back then.
- kaoD 13y ago
  I've done both and ray tracing techniques are much more complicated and heterogeneous.
exDM69 13y ago
This isn't a typical raytracer. Instead, it's a very clever ray marching in a uniform grid. It resembles a Wolfenstein/Doom -style raycaster more than what you usually think of as a raytracer.

yalue 13y ago

When I tried to build the project I got a linker error, but running the prebuilt iso (linked in the readme) with qemu worked just fine. A very impressive project! Edit: The link error is probably just a stupid mistake on my part; I was trying to build on a 64-bit machine. It doesn't seem to have any problems on 32 bit.

Smerity 13y ago
For others who might be interested, compilation works fine in Ubuntu 12.04 after `apt-get install build-essential nasm qemu`. If you install libsdl and libsdl-dev you can run the reference version written in C which runs significantly faster. It's indeed an impressive project, doubly so as it was initally only for a university project. Instead of just making a game in assembly he made the project his own by extending it -- bootable, raytaced, raytraced shadow, textures and so on! =]
- 300bps 13y ago
  >Instead of just making a game in assembly Not to discount what he did, but he didn't write the game in Assembly. He wrote it in C then decompiled it to Assembly and used that as a starting point for the Assembly code. From the article: >Starting in assembly right away would be a bit too insane, so I first wrote a reference implementation in C As someone who started in Assembly right away creating several games with a much simpler 6510 CPU, I can vouch for the fact that starting in Assembly would be a bit too insane especially on modern CPUs.
  - 6ren 13y ago
    He doesn't say anything about decompiling. > Then I began slowly porting everything to handwritten assembly.
    - 300bps 13y ago
      >Starting in assembly right away would be a bit too insane, so I first wrote a reference implementation in C How did he make the reference code? I'm reading that as he wrote an implementation in C, then decompiled it and then cleaned up the decompiled Assembly language code. Maybe I'm wrong. How do you take his statement above?

hdra 13y ago

Wow. Impressive project, especially as a university assignment (I am assuming a bachelor's degree), considering I see a lot of people graduating university without being able to even write the most basic CRUD app. I myself can't even manage to finish a simple 2d game I started months ago. Kudos to the author.

mjfl 13y ago
as a Computer Science student, I am embarrassed that this is true at least for me, though I am eager to learn...
- irishcoffee 13y ago
  Its only embarrassing if you've tried and couldn't figure it out.
  - graupel 13y ago
    And given up trying to!
  - deleted 13y ago
    [deleted]
- hdra 13y ago
  the eagerness is the most important thing in learning. I'm sure we all know SE major students who aim to get a job as a "project manager" right off the bat, not because they actually love/know anything about managing a project, but simply because it is a managerial position where you don't have to code.
ctdonath 13y ago
Nicely complements the nearby thread "Building a Modern Computer from First Principles" https://news.ycombinator.com/item?id=5888705 https://news.ycombinator.com/item?id=5888705
dom96 13y ago
As a student who is hoping to study Computer Science in a years time, I hope that the university I enrol at encourages such projects!

kriro 13y ago

Impressive. I also like his approach of prototyping it in C first (I chuckled at the thought of C as a prototyping language). That reference is also in the repo and I hope to at least read that :)

mrmekon 13y ago
Everybody I know who writes assembly language in practice now, self included, prototypes most of it in C first -- why not take the huge headstart from the compiler generated ASM? And I usually prototype the C in Python first :D
- mrbrowning 13y ago
  In those cases, are you writing in asm for fun? If not, what advantages do you see in taking this approach over just writing most of the project in C and using inline asm where necessary?
  - mrmekon 13y ago
    It usually is inline assembly, but you write it in C first and copy the disassembly as a starting point. We do this in the embedded world a lot because we're constantly switching architectures, and nobody memorizes the instruction set of every architecture :) The most common reason is using architecture-dependent instructions that the compiler doesn't generate well, or doesn't generate at all. Examples are SIMD (auto-vectorization is nice, but far from perfect) and DSPs that have specific multiple-and-accumulate instructions or flags that change the behavior of the accumulate register. In a project I'm currently working on, inlining was still inferior to fully native ASM. LLVM generated unnecessary stack loading in the prologue, and the completely unused memory access had something like a 4% speed penalty.
    - jevinskie 13y ago
      Would you please file a bug report [0] with a reproduction of the missed optimizations that you see? I'm interested in taking a look at it. Today LLVM trunk enabled the vectorizer for -O2 and -Os. [0]: http://llvm.org/bugs/enter_bug.cgi?product=libraries http://llvm.org/bugs/enter_bug.cgi?product=libraries

voltagex_ 13y ago

Cool! I think this would also be PXE-bootable with iPXE and a chain command.

FreeFull 13y ago

Seems to break when you press multiple keys at once. Movement starts and then doesn't stop. Otherwise, it is pretty good.

arsen1k1 13y ago

Looks like the kind of app the Kolibri OS (http://kolibrios.org/ http://kolibrios.org/) would love to see ported to their platform. Is it possible to do?

mosqutip 13y ago

I thought my asteroids game in assembly was cool. Great job!

rpicard 13y ago
Is the source code online somewhere?
- TheAceOfHearts 13y ago
  Shameless plug of an ASM project I did: https://github.com/cesarandreu/INEL4206-XString https://github.com/cesarandreu/INEL4206-XString (Video in link)

rcthompson 13y ago

Now we just need a Redstone x86 processor to run it on.

parski 13y ago

It looks more like an Infiniminer clone. Impressive none the less.

mikkom 13y ago

Any screenshots?