I spent the weekend entering the Ludum Dare game jam. For this competition, entrants had two days to design and produce a game given the theme “Beneath The Surface”. I used this opportunity to try out the game engine I have been working on.
My entry is called Skull Mountain and can be found here.
I was recently searching through my hard drive looking for examples that might highlight my love of low level programming, and I present here one such project which is a good example of this.
THUMB is an instruction set that was added to some ARM processors as a way to reduce code size, which is advantageous as ARM typically finds use in very constrained devices. The processor can switch between two operating modes at the request of the program, switching from decoding ARM instructions to smaller THUMB instructions.
I found THUMB particularly interesting since the instruction set is clean and simple and it might make a nice basis for a virtual machine to execute programs written in it. My idea was to use programs written in C and compile them to THUMB and then execute them in a virtual machine, the entire process serving as a powerfully scripting system for games.
Ultimately, I switched to a MIPS processor as my basis for this project, but I still got as far as making a THUMB disassembler. I should point out that this was the first disassembler I ever wrote so it marks a large mile stone for me. Since then I have made a very nice MIPS disassembler using much of what I learned on this project. The code for the THUMB disassembler can be found here:
To test a disassembler there needs to be something to feed it. For that purpose, I compiled a small program in GCC targeted for the THUMB instruction set. The program is listed below, and is just a nonsense program designed only to be valid so as to generate some instructions:
One of my ambitions for a while was to create my own efficient ray casting function which I finally managed yesterday, which is great news because ray casting has so many cool applications. There are so many basic uses for ray casting, for instance, in line of sight detection in the field of AI, detecting the collision points when shooting bullets and importantly for my game, detecting where to attach grappling hooks. More advanced uses could be in inverse kinematic routines, procedural animation systems or even, as I eventually want to try, Wolfenstein style 2.5D ray-casting engines. With some extensions It should be possible to modify a ray-casting algorithm to perform somewhat naive Voxel rendering, which is something else I really want to try. Ever since I played Voxatron, I have since fallen in love with Voxels and its on my large project list to make something simmilar.
Over the last few years I have studied a large number of ray-casting algorithm available on the web and read many websites on the subject. I would be lying if I said I really understood all of the approaches I have seen to ray-casting, but it is clear that the efficiency of them varies quite substantially, and in this regard they are easily examined.
Perhaps the most understandable and readable tutorial for ray-casting I could find was here, in article by Lode Vandevenne. On the face of it, his algorithm seems very efficient and he talk in detail about the efficiency and speed concerns, and even in the main loop there is no multiply or divides used. However, in exploring the code we can see that to initialize a ray cast, two square route functions are called, which adds up when you consider that two called are made for each vertical column of the screen. Thus even at 320×240, 640 square route calls are made in rendering one frame. Square route calls can be optimized somewhat by approximation, or look-up tables, however this seems still like a weak point of the algorithm.
Another nice tutorial can be found here, written by F. Permadi. In his tutorial he advocates mostly the same strategy as the above, but the formers square route calls are now replaced with a call to the tangent function, shown here. This is more efficient, since the tangent function can easily be packed into a look-up table and accessed quite efficiently, just as I did for my sin wave approximation library. Still this look-up costs space and has accuracy tradeoffs thus reducing the overall efficiency in other ways.
For my algorithm, I managed to avoid square routes and look up tables of any kind, in fact there are just four divides and six multiplies called for each ray cast, the rest being just addition and subtraction. The inner loop is entirely performed using addition and subtraction also, so the overall efficiency seems bloody high. I do however test inside the inner loop to see if the ray has exited the map space, but if we can guarantee that a ray will hit a tile (such is the case, when the map is surrounded by tiles) then efficiency could again be dramatically increased by omitting these tests. In the code below that I provided, you will find there is one multiply in each inner look, to perform the wall hit test, but this can be optimized away to equivalent addition and subtraction, as I have done in my own personal version. In my scheme unlike that of Lode, I separate the ray cast into two stages, that of ray casting over the x-axis and next the y-axis. Each of these steps may produce a hit, and at the end of the algorithm we can compare the squared distance to efficiently select the closest of the two hits. I also break the ray cast through each axis into two parts, that for a positive increment, and that of a negative, since we can tailor the inner loop to be more efficient for each case.
I am sure this ray casting code will find loads of awesome use in Ninja Flare as well as my other projects. I also need to find a better name for the game, other than Ninja Flare, which was chosen quickly for the deadline of Ludum Dare.