And this is it in motion:
Impressive, isn't it? Out of curiosity, I took a look at the source code (http://olivier.poudade.free.fr/src/Wolf128.asm) and spent some time trying to figure out how it works. So now I'd like to share my findings here.
The algorithm
For each pixel, wolf128.asm performs two ray marching, one on X-Z plane, and one on Y-Z plane, to find out the distance to the nearest wall/ceiling/floor. The ray marching happens on 2D planes and are always axis aligned so there is no vector math needed.
For simplicity, below I'll use GLSL code to show how it works. Let's consider only the vertical direction first:
out vec4 outputColor;The output of this fragment shader is like this:
uniform vec2 iResolution;
void main(void)
{
// normalize y coordinate to 0-200, in consistent with wolf128's
// vga 320x200 mode
vec2 uv = gl_FragCoord.xy / iResolution.xy;
uint y = uint(uv.y * 200.0);
// initial depth is 0
uint z = 0u;
// the distance to wall(ceiling/floor)
uint ydist;
// we'll trace a maximun of 256 steps
for(int i = 0; i < 256; ++i)
{
// the distance to wall is propotional to depth,
// and propotional to the offset of the pixel from
// the center of the screen(which is 100, because
// the height of the screen is 200). In order to be
// consistent with wolf128, everything uses unsigned
// numbers, and we keep 8-bit precision for the result.
ydist = ((y - 100u) * z + 4096u) >> 8;
// If the distance exceeds a predefined threshold
if (ydist >= 32u)
break;
// next itration, increase depth by 1
++z;
}
// normalize the depth value to [0,1]
float c = float(z) / 256.0;
outputColor = vec4(vec3(c), 1.0);
}
Fairly simple isn't it? The only thing worth mention is the +4096 in our distance calculation. The reason we need this is because the nature of unsigned numbers. Imagine when the Y coordinate is less then 100, for example 99, now 99-100 will underflow and becomes a very large number, immediately exceeds the threshold. The answer is to add 4096 to the calculation. Why 4096? Because we shift result right by 8 bits and 4096 >> 8 = 16, which is in the middle of our threshold (32). This effectively shifts all results to the positive direction by 16, so <100 coordinates will get results starting from 16 and gradually decrease from there towards 0 until it underflows and trigger the >=32 condition. Meanwhile results from positive coordinates will start from 16 and adds up from there until reach 32.
Now let's add horizontal walls:
out vec4 outputColor;Almost identical, only added distance tracing for horizontal walls. And the result is no surprising:
uniform vec2 iResolution;
void main(void)
{
vec2 uv = gl_FragCoord.xy / iResolution.xy;
uint x = uint(uv.x * 320.0);
uint y = uint(uv.y * 200.0);
uint z = 0u;
uint xdist, ydist;
for(int i = 0; i < 256; ++i)
{
// horizontal center is 160
xdist = ((x - 160u) * z + 4096u) >> 8;
ydist = ((y - 100u) * z + 4096u) >> 8;
// break the loop if we hit a wall in either direction
if ((xdist >=32u) || (ydist >= 32u))
break;
++z;
}
float c = float(z) / 256.0;
outputColor = vec4(vec3(c), 1.0);
}
The above two shaders merely renders the depth value of a virtual tunnel (or distance field, if you prefer to use that term). Now let's add some textures.
Given the fact that for each pixel we already have the distance to horizontal and vertical walls and we have the depth value, that's enough information on all 3 dimensions. A very simple but effective way to generate some texture is to XOR all of them together, like this:
uint texel = xdist ^ ydist ^ z;
texel %= 16u; // adjust the period of the pattern to your liking
float c = float(texel) / 16.0;
outputColor = vec4(vec3(c), 1.0);
The result is this:
Now we are talking!
The next step is to make some corridors in this tunnel. We can do this with the depth information which we already have. The only change we need to make is change the loop exit condition. When we hit a horizontal wall, do not exit immediately, instead, check whether the depth satisfies some sort of conditions, for example turn wall on and off for every other 32 units:
This is what we get from this change:if ((xdist >=32u && ((z & 32u) != 0u)) || (ydist >= 32u))
break;
Now it looks almost exactly the same as the original wolf128.asm program:switch(z / 64u)
{
case 0u: xdist -= 10u; break;
case 1u: xdist -= 40u; break;
case 2u: xdist -= 20u; break;
case 3u: xdist -= 30u; break;
}
The full fragment shader code that produces the above output is this:
out vec4 outputColor;That's all about the algorithm. Next to follow is
uniform vec2 iResolution;
void main(void)
{
vec2 uv = gl_FragCoord.xy / iResolution.xy;
uint x = uint(uv.x * 320.0);
uint y = uint(uv.y * 200.0);
uint z = 0u;
uint xdist, ydist;
for(int i = 0; i < 256; ++i)
{
xdist = ((x - 160u) * z + 4096u) >> 8;
ydist = ((y - 100u) * z + 4096u) >> 8;
switch(z / 64u)
{
case 0u: xdist -= 10u; break;
case 1u: xdist -= 40u; break;
case 2u: xdist -= 20u; break;
case 3u: xdist -= 30u; break;
}
if ((xdist >=32u && ((z & 32u) != 0u)) || (ydist >= 32u))
break;
++z;
}
uint texel = (xdist & 255u) ^ (ydist & 255u) ^ z;
texel %= 16u;
float c = float(texel) / 16.0;
outputColor = vec4(vec3(c), 1.0);
}
Assembly code analysis
In order to minimize the size, wolf128.asm is a DOS .COM file. The advantage of .COM file is that it has zero fat. Every single byte in the file is program code. When executed, DOS(or Windows) loads the code to offset 0x100 of the current code segment, and fill the 256 bytes before it with the so called Program Segment Prefix (or PSP).Below I'll explain the code line by line.
; Call BIOS INT 10h set the display mode to VGA mode 13h,
; which is 320x200，256 color. It takes advantage of ah's
; initial value being 0, therefore save one instruction to
; load ah.
mov al,13h
int 10h
; bx has initial value 0, and ds is the same as cs，so ds:bx
; points to PSP.
; es <- 9FFF (PSP+2 is the end of DOS program area，which is 9FFF)
; dx is also assigned，but not used。Why load es with 9fff? That's
; because the VGA frame buffers starts at A000
les dx,[bx]
; cl <- 255, max loop count
A:mov cl,0ffh
; bl <- cl，bl keeps track of depth
B:mov bl,cl
; this is equivalent to bl = 255-cl
not bl
; ax <- 0xffee (di has initial value 0xfffe，minus 10h and get 0xffee)
; This will be the screen buffer size. Why 0xffee instead of
; 320x200=0xfa00? This is because in order to save space, wolf128 always
; writes 65535 bytes for each frame. Since our es segment is 9fff, and di
; is fffe, after 2 bytes, di will wrap back to 0, which is 9fff:0, and 16
; bytes before the VGA frame buffer at a000:0. So that's a total of 18
; extra bytes written before the frame buffer: 65535 - 18 = 0xffee
lea ax,[di-10h]
; bp <- 320，screen width
mov bp,140h
; dx <- 0000，cdq is in fact a 32-bit instruction, it sign extends eax to
; edx. here it takes advantage of the fact that the high word in eax is
; always 0 in 16-bit programs.
cdq
; DX:AX(FFEE) divide by BP(320)，get quotient(Y coordinate) in AX
; remainder(X coordinate) in DX
div bp
; calling G twice is equvalent to
; ax = ((ax - 100) * z + 0x13b0);
; dx = ((dx - 100) * z + 0x13b0);
; You should already be familiar with this formular. But Why 0x13b0
; instead of 0x1000(4096)? And why both are minus 100? Those are all
; for reducing program size. 0x13b0 is the first 2 bytes of the
; program, which can be loaded by taking advantage of SI's initial
; value being 0x100. And if the 2 formulars are written separately
; it'll take more instructions. The results are kept in 16-bit
; registers AX and DX but later we only use AH and DH, this is like
; an 8-bit right shift for free.
call G
call G
; the program keeps mouse button state at ds:1dh
test [1dh],7
; if no button is pressed then no need to look at mouse position
jz C
; ds:1fh keeps mouse X coordinate. Add to x distance if button is pressed
add dh,[1fh]
; ds:1eh is mouse Y coordinate, subtract from depth
sub bl,[1eh]
jmp short E
; fs has initial value 0, under DOS address 0x46c stores the current
; tick count. Put the tick in DL.
C:mov dl,[fs:46ch]
; Subtract an arbitary constant(0xb0，the first byte of program)
; It's picked to avoid collision with the walls too frequently
sub bl,[si]
; move to the right every 64 ticks
test dl,40h
jnz D
add dh,dl
; move forward
D:add bl,dl
; The shld instruction here effectively shifts depth right by 6 bits
; and put it in BP
E:shld bp,bx,10
; x distance minus an arbitary offset parameterized by depth>>6 to add
; variaty to the scene.
; The data used here is the first 4 bytes of PSP, but can be anything.
sub dh,[bp]
; Save x distance in al
mov al,dh
; What these 3 instructions do are very similar to
; (xdist >=32u && ((z & 32u) != 0u)) || (ydist >= 32u)
and dh,bl
or dh,ah
and dh,20h
; If condition is not met then --cl and keep marching
loopz B
; XOR al,bl,ah(x,y,z) together to create texture
xor al,bl
xor al,ah
; This undocumented instructino is a variant of AAM. It splits the
; high and low 4 bits of AL and put them in AH and Al. This effectively
; performs al % 16.
db 0d4h,10h
; Add 16 to texure. Why 16? because the we want to map the texture
; value to the second row of the VGA mode 13h palette (which is
; different shades of grays)
add al,10h
; write al to es:di (and di increase by 1)
stosb
; If di is not 0, it means we are not finished with a frame
; go back to compute the next pixel
or di,di
jnz A
; read mouse state
; INT 33,3 - Get Mouse Position and Button Status
; CX = horizontal (X) position (0..639)
; DX = vertical (Y) position (0..199)
; BX = button status:
; |F-8|7|6|5|4|3|2|1|0| Button Status
; | | | | | | | | `---- left button (1 = pressed)
; | | | | | | | `----- right button (1 = pressed)
; `------------------- unused
mov ax,3
int 33h
; left button down?
test bl,al
; Store button state at 1dh
mov [1dh],bl
; If button is not down, goto F
jz F
; If button is down, store Y coordinate at 1eh
mov [1eh],dl
; X coordinate at 1fh
mov [1fh],cl
; Read keyboard scancode from port 60h
F:in ax,60h
; The scancode of ESC is 1, so if scancode - 1 == 0, then quit
dec ax
jnz B
; This procedure is the formular
; ((x - 100) * z + 0x13b0)
G:xchg ax,dx
sub ax,64h
imul ax,bx
add ax,[si]
ret
This is it, the assembly code explained. Being assembly code it may still be rather difficult to read so below is a clone I wrote in D language. It does exactly the same thing as the assembly code, and has exactly the same code flow and is even annotated with the original assembly code, have fun!
import std.stdio;
import std.datetime;
import std.algorithm;
import std.array;
import std.random;
import derelict.sdl2.sdl;
void render(SDL_Renderer* ren, SDL_Texture* tex)
{
nextframe:
nextstep:
}
// ---------------------------------------------------------------------
uint convertPixel(ubyte p)
{
}
uint[] convert(const(ubyte)[] buf)
{
}
int main(char[][] args)
{
}
