x86 Assembly — GitHub
MineAssemble is a tiny bootable Minecraft clone written partly in x86 assembly. I made it first and foremost because a university assignment required me to implement a game in assembly for a computer systems course. Because I had never implemented anything more complex than a "Hello World" bootloader before, I decided I wanted to learn about writing my own kernel code at the same time.
Note that the goal of this project was not to write highly efficient hand-optimized assembly code, but rather to have fun and write code that balances readability and speed. This is primarily accomplished by proper commenting and consistent code structuring.
Starting in assembly right away would be a bit too insane, so I first wrote a reference implementation in C using the SDL library, which can be found in the reference directory. I started writing it with the idea that if it was longer than 150 statements excluding boilerplate, it wouldn't be worth doing it in assembly. Like all estimates in the world of programming, this limit turned out to be a gross underestimate, reaching about 134 lines before adding even the texture or input code.
After completing the reference code, I wrote the kernel boilerplate code (setting up VGA, interrupts, etc.) and changed the reference C code to work with this. Then I began slowly porting everything to handwritten assembly.
Unfortunately this turned out to be a lot more work than I expected, so currently a large fraction of the codebase is still in C. Slowly porting everything to assembly is an ongoing process. The code also isn't fully compatible with all systems yet. It seems to cause floating point exceptions on some setups.
The inner workings of this demo are really quite straight-forward. The code can be divided into four different components.
The world is stored as an unsigned byte array where every block has a value of
BLOCK_DIRT. The array is stored in the BSS section and
is initialized by the
init_world function. It loops over every x, y and z and
creates a world where the lower half is dirt and the upper half is air.
While playing, other code calls
get_block to interact with
the world. These simply calculate the correct index and write to or read from
Input and collision
Keyboard input is collected by an IRQ1 interrupt handler. It writes the up/down
state to a 128-byte array indexed by the scan code.
It also sets the upper bit to
1 to mark that key as updated. It ignores a key
down event if the key is already set to down to ignore automatic key repeats.
Because the input handling needs to be independent of performance, an IRQ0
interrupt handler increases a
time variable by 1 every millisecond to keep
track of time. This is used to compute a delta time to scale movement by.
Before every frame is rendered, the
handle_input function is called and
collects the values from the
keys array written to by the interrupt handler.
If the upper bit of a cell is set to
1, then it knows that the key state has
changed and processes it accordingly. All keys except for the movement keys
(AWSD) are handled here.
After that, the update function is called to move the player according to the
current velocity. This velocity is controlled partly by the
function and partly by checking the down state of the AWSD keys in this
function. The Y velocity is decreased to simulate gravity. Then the next player
position is determined by adding the velocity multiplied by delta time.
Before the new position is assigned, the code first runs the
function for the head, center of the body and feet. It calls the raytrace
function from these positions with the velocity as direction to determine if
a collision will occur if the player moves to the new position. If that is the
case, the velocity is corrected to mostly prevent collision. (The algorithm
is not perfect, but it works pretty well.)
Normally games use rasterization to render and this is very fast. Unfortunately a graphics library like OpenGL is not available at this level. Instead, code needs to be written that writes directly to the graphics memory. At this point, I had two choices: write my own rasterizer or implement a raytracer. I decided to go with raytracing, because:
- It's much more straight-forward by simply computing the color per pixel
- It's cool, because it allows for easy effects like raytraced shadows
- It's fast enough, because we have a uniform 3D grid
The raytrace algorithm computes the distance to reach the sides of the block
the ray starts in for every dimension. The shortest distance wins and the ray
position is moved by that distance times the ray direction. This is repeated
until the position is inside a
BLOCK_DIRT or if it's out of the world. The
final position is used to compute the side that was hit and the texture
ray_color function is then called to let the block decide
what color it's going to output. This function calls the
again to decide whether the pixel is shadowed or not by using the
direction for the ray. It prevents infinite recursion by requesting an info
raytrace instead of a color raytrace. This alternative returns a struct with
hit info instead of a color.
One of the details you deal with when using a low-level VGA mode (mode
is that you can't just specify 24-bit or 32-bit RGB color for every pixel.
Instead, you have to decide on a 256 color palette and specify an index for
every pixel. The easy solution here is to use 3-2-3 bit channels and use an RGB
color as index into the palette. Unfortunately this doesn't work at all, because
with only 4 options for the green color channel, there's no way to represent all
the subtle different shades of a grass block.
So I decided to generate a palette that could represent every color that the textures used exactly, well almost exactly. The palette does allow you to specify RGB colors, but with only 6 bits per channel instead of 8. That means that colors will be slightly off, but this is pretty much unnoticeable.
I wrote a program in C# that took the grass, dirt and side textures along with the reserved colors black, white and sky and automatically generated a palette and a palette colored representation of the three textures. This ended up working perfectly!
The splash screen works slightly differently. The reason that it's a bitmap instead of just using text mode is to make things a bit more streamlined. I first tried encoding it the same way as the textures, but this resulted in a 6400 line C file. Then I changed it to simply write a string of 1's and 0's for every line, which works much better. It even allows you to view the splash screen using a text editor!
The bitmap of the splash screen is copied directly to VGA memory where
subtracted from every byte. The
keys array is then checked for an ENTER key
press before the game is loaded. A problem here is that the user has to press
ENTER in the GRUB bootloader menu as well, which means it would skip the splash
screen immediately. That problem is currently solved by waiting for an ENTER key
press twice. Somehow this even works when booting with Ctrl-X or another