09 Nov

Plenty of Room, Part II

This is the second part of the epic (two three-part) series of articles about tiny intros, the previous part was an essay about 256-byte intros in general.

Ed. note: Since this article seems to take forever to finish, here’s the first half of it. The (hopefully) final part will detail more of the specifics.

rubba As stated earlier, tiny intros written in assembly language fascinate me. I have written a few in x86 assembly language, here’s one of them. I have tried to make the inner workings of the program as accessible — or, at least as thought-provoking — as possible even if assembly wasn’t their weapon of choice.

I’ve included the original DOS intro (you can use DOSBox to run it, it should also work on Windows XP) and a Win32 port of it, written in C while trying to keep the original structure intact. I’ll also try to explain the general idea of the effect in pseudocode where syntax can be an obstacle. The archive rubba_c.zip contains the source code, rubba_b.exe which is the compiled Win32 executable and RUBBA.COM which is the 16-bit MS-DOS executable. To compile the C program, you need the TinyPTC library (like SDL but even more bare-bones).

I won’t go into details about x86 assembly language, I suggest anyone interested first reads an introduction and learns some of the basics. However, I’ll try to make the code look interesting, explain some weird or obfuscated code and probably show some basic size optimization tricks.

The Effect

The intro, called rubba_b, shows one effect: a twisting bar drawn using primitive light-shaded texture mapping. The color palette and the texture are generated run-time. The texturing is done using linear interpolation and no vector math is used even if the bar looks like it is rotated. The lighting is an extremely simple approximation of the light source being exactly where the camera is located. That is, the length of the textured line directly determines the light.

If looked from above, the bar will be a tower of squares. If one of the squares is rotated around the center, the corners will move in a circular pattern. So, the X coordinate will be equal to cos(corner_number*(360 degrees/4)+square_rotation), the Z coordinate (why Z? Because it goes towards the screen) is equal to the sine but it can be discarded because we will not need it for perspective calculation. Remember, we’re short on bytes.

We then modulate the bar rotation for each square in the tower. If the amount of rotation changes when moving up or down the tower, the bar will twist. If the rotation stays the same for each square, the bar will rotate uniformly and look uninteresting.

The textured horizontal line is drawn from each corner to the next corner, from left to right. If the line would be drawn from right to left, we know it isn’t facing towards the camera, another line facing the camera will be drawn over it and we simply skip the line. The color value fetched from the texture is multiplied by the line length which makes short lines darker.

Still with me?

The Code

Initialization

First things first. We need to set the video mode before we continue. In the Win32 version we simply open a TinyPTC window, in the original version we need to tell BIOS to go in a nice 320x200x8 video mode (the de facto video mode back in the day).

C asm
ptc_open("rubba_b",320,200)
mov al,13h
int 10h

In the above code, the Win32 part is self-explanatory. The assembly bit probably needs some clarification: we put the number 13h (hex) in the 8-bit register al and we request for interrupt 10h. This is the BIOS video interrupt and since register ax (which consists of al – “low” – and ah – “high”) equals to 0013h (when the program starts, ax is always zeroed), BIOS will call the routine for changing the video mode (ah=00h) to 13h.

If above sounds complicated, don’t worry. It’s just a matter of memorization – similar to how you would memorize the function name for changing the video mode.

The next thing we need is some space for the texture, the sine table and the double buffer. In the Win32 version this is obvious, we just add a few arrays (although since TinyPTC only supports 32-bit video modes, we will also have an array for the palette). Again, in the assembly version we won’t use any fancy way to reserve memory to save some precious bytes: we simply decide certain areas of the memory will be used for whatever we want. The benefits of no memory protection and single tasking. ;)

C asm
short int sinetab[SINETAB];
unsigned char palette[256*4];
unsigned char texture[256*256];
unsigned char screen[320*200];
mov dh,80h
mov gs,dx           
mov dh,70h
mov es,dx
mov dh,60h
mov fs,dx

The assembly version basically sets the register dx to 60xxh-80xxh (we set only the high byte, i.e. dh to save bytes, thus the low byte of dx is undefined – it won’t matter) and puts the value into various segment registers (es-gs).

This makes it so that if we use the different segment registers, we can access each of the three 64 kilobyte segments as a 64 kilobyte array. E.g. the sine is in gs, thus mov ax,[gs:2] would move the second word in the sine table in ax. In C, the equivalent would be short int value=sinetab[1] (note how the C compiler knows the fact that a word is 2 bytes but in assembly you have to take care of that yourself – all memory accesses are always by the exact location, not the array element!).

All this is because in 16-bit memory accessing you can see only 64 kilobytes at one time. You can’t have a 128 KB array, nor can you have two 64 K arrays in the same segment. It’s something comparable to having a flashlight and a big sheet of paper in a dark room; you can move the light to show different areas but you will never see more than what there is in the spotlight.

The next two parts calculate the sine table (back in the day you simply could not do trigonometric stuff real-time, even in hardware — although in the intro it’s there just for show) and set the palette. This is pretty straight-forward stuff across the two versions. The only difference is that in the Windows version we have to remember the palette has 8-bit color components and the original has 6-bit components (0..255 ~ 0..63). And of course, the Windows version simply puts the values in a palette look-up table (because 32-bit video mode doesn’t use a palette) and the original actually sets the video mode colors.

I won’t reiterate the source code for the sine table and palette change here, I think you should be able to figure it out by comparing the source code. But in theory, here’s how to change a color: first, write the color index in port 3C8h, then write the three color components in port 3C9h (hint: dx first contains 3C8h and it’s incremented to 3C9h to save bytes).

The sine routine increases the angle (st0 the topmost register on the FPU) by 2*PI/32768 (a full circle is 2*PI, the sine table has 32768 elements). You probably should check some FPU tutorial, arithmetic on the 8087 is pretty interesting due to the stack-based architecture. For example, you first push in two numbers and then do an add, which (in most cases) pops out the two values and pushes in the result.

The texture generation bit is interesting. It also was annoying to port to C thanks to the fact you have to emulate how some instructions work – there are no accurate analogies in the C standard. A big thanks goes to baze whose code I originally cannibalized for this (I think). To be honest the conversion doesn’t work 100 % accurately but does still produce a nice texture.

The algorithm uses addition, bitwise operations and other simple things to achieve complexity thanks to how processors do arithmetics. Mainly, the results from an earlier calculation is carried over to the next calculation — when an addition or a subtraction overflows, i.e. the result is too large or too small to fit in a register, the processor lets the result wrap over but sets the carry flag.

This is quite similar to how you would carry numbers when calculating with a pen and a paper. The flag affects the results unpredictably because it’s used across quite different operations; usually you would just use to to add big numbers together as in the pen and paper example.

The Main Loop

Here is the meat of the code. The C version has many variables that are named after registers in order to see the connection with the original code. Sometimes, as with the 8-bit registers, some code doesn’t work exactly as in the original because you can’t do things similarly in C. E.g. you can’t have two variables that also are a part of one big register similarly how al and ah form ax (well, you can with pointers or unions but that is besides the point, kind of).

Self Modifying Code

I use self modifying code (SMC) in a few places because it produces faster and also much simpler code. For example, if you have a variable that is changed in a few places but used by one instruction only (and the instruction performs arithmetic or otherwise accepts a constant parameter), it’s much faster to store the variable where the constant for the instruction would be. That way you don’t have to read the variable in a register and then use the register to do something.

E.g. Let’s multiply cx by the variable foo:

Original SMC
  push ax ; save ax
  mov ax,[foo] ; move variable foo in ax
  imul cx,ax ; multiply cx by ax
  pop ax  ; restore ax
  ...
  mov ax,123   ; set foo ...
  mov [foo],ax ; ... to 123
  ...
foo: dw 0
  imul cx,123
foo equ $-2
  ...
  mov ax,123   ; set foo ...
  mov [foo],ax ; ... to 123

We can exploit the fact imul (signed multiplication) accepts constant multipliers. If you looked at the code with a hex editor, you’d see 123 next to the opcode. You can change the constant run-time and you do that exactly like you would change a variable: if you just define foo as the address where the constant is (the above code defines it as the last two bytes (i.e. word) of the previous instruction: in NASM, $ is the current location and $-2 equals the address of the previous word).

To be concluded…

10 Apr

Viewer2 Status

Good news. A new version of Viewer2 will be available in the near future. In addition to fixing the bugs that have been waiting for a fix for a year or so, it will be a significant improvement in performance (namely proper multi-threaded image loading that results in a lot smoother user interface especially when browsing over slow network connections) and also how the user interface works.

For example, there’s a new tag cloud view, a more traditional grid based thumbnail list and an improved version (or, a total rewrite) of the light table view which was the only view available until now (with more physical image groups that can contain other subgroups — in fact you can view a directory tree this way popping open the directories). Overall, it’s pretty sweet.

No estimates when it will be done, except for the infamous “when it’s done.”

05 Aug

Introducing Calculon

Here’s a desktop calculator I wrote because I thought the standard Windows Calculator sucks (which it does). I got annoyed of how you can’t paste more than a single number and how the scientific mode misses a simple shortcut to square root.

Calculon

My approach is closer to the Google Search calculator feature in that the program only has two text fields, one for the expression and one for the result. It also does conversions and has user-definable functions, constants and whatnot.

Currently, the software is in alpha state (which means it works but is not finished) which I hope will not be perpetual. It is already very much usable, though.

What is left to do is that currently the software does only 80-bit floating point arithmetics (the best precision offered by x87) and displaying the result is double precision (thanks to the fact MinGW uses Windows libraries for printing floats, which have support only up to double precision). I also plan adding simple graphical features for graphing functions.

You can find Calculon (a placeholder name) on its own project page.

18 Mar

More generated game content

Shmup Pixel Craft Generator

Shmup Pixel Craft Generator is another random sprite generator that is quite similar to Richard’s Evolving Sprite Tool from the last installment. SPCG too gives a sheet of sprites that you can pick from. The sprites make me think of Xevious, they have the feel of ancient space ships.

The author mentions Dave Bollinger’s Pixel Space Ships as his inspiration. Bollinger’s Pixel Robots was featured in the last installment as well.

Explosion generators

There are very many products for generating various effects by using a particle system. However, many of those products are very expensive as they are aimed at film and game industry instead of a hobbyist. Here are some alternatives.

ExGen is a commercial product but with a much nicer price (less than your average game). It is very feature rich, has a nice GUI and even exports as AVI.

The Explosion Graphics Generator or EGG is a very customizable particle system that uses a scripting language. It is free.

Explogen is similar to ExGen only that it is not as feature rich. It’s still worth checking out as it is free.

Positech Games has a free, unnamed generator as well. The page includes sheets of sprites so you don’t even have to download the software.

This blog writes about lhfire, a tool for generating particle effects for a Quake mod. I haven’t tested this myself but it should be good and also free.

22 Feb

Generating game content

Part 2 of this series »

If you can’t draw graphics or create sounds for your games, here are a few interesting tools I came across recently that can help you.

sfxr

sfxr generates random sound effects such as explosions, sounds for jumping and so on. The sounds are nice and crisp and you can easily tweak a randomly generated sound to suit your needs better. A nice feature is that you can click on sound types to generate a sound for common actions in games.

Pixel Robots & Invader Fractal

Pixel Robots generates random sprites that resemble robots (well, duh). It’s a Java applet (made with Processing) so you can (or, have to) run it in your web browser. Hence, it is not too convenient to use for pure sprite generation purposes – but it is quite nice eye candy.

The author mentions the Invader Fractal as his inspiration. It is a quite similar thing, in that it generates a sheet of tiny sprites and runs in browser (it’s a Flash applet).

Both generators are quite nice in that their authors give good insight how the programs generate the sprites.

Richard’s Evolving Sprite Tool

I saved the best for last. Richard’s Evolving Sprite Tool, as the name implies, evolves sprites. The main idea is that the program generates a grid of mutated sprites and you can choose the one that looks good. The selected sprite then spawns mutated offspring. This continues until you decide the sprite is good enough. On the left, there’s an example of an evolved and hand-colored sprite (grabbed from the Retro Remakes forum thread).

It is also much more of a tool than the two previous generators, the user can edit the sprites inside the program. After the user has edited a sprite, it can be evolved further. Very nice if you’re short on inspiration.

Next thing Richard needs to do is to add a way to colorize and animate the lovely sprites.

kometbombNote: Since this tool has gone AWOL, here’s something similar: Retro Avatar generator. For example, the avatar created from my name looks like what you see on the left (cute!).