Lockless Inc

A Roguelike in less than 512 Bytes

Rogue was one of the first graphical computer games. It involved a player searching a dungeon for treasure, whilst avoiding or defeating monsters. It used ascii characters for graphics in lieu of images due to the primitive nature of the hardware available at the time. The game eventually spawned copy-cat games, the most famous of which are Angband and Nethack. This category of dungeon-exploration game is called a "roguelike"

Roguelike games still have a large following today, and the development of which are often an open-ended project for an author to explore the usage of a newly learnt computer language. Back in 2006, there was a competition to develop such games with the limitiation that only seven days could be used. The seven-day-roguelike (7DRL) competition was a success, and produced many entries. Soon after the competition was completed, I decided to undertake creating such a game in two days instead of seven, with the further limitation that the source code must fit in under 2KiB. At the time, this 2KiB roguelike was the smallest game of its type ever created.

Over the past few years, others have attempted the creation of minature roguelike games, and there now are several 1kiB games in existance. Twice as small as the original smallest roguelike, these pushed forward the boundary of coding within a small number of bytes. Now, in order push forward even further into the rediculous, I have set myself the task of creating a roguelike within half a KiB (512 bytes) of source code. The resulting game follows:


#include<stdlib.h>
#define F(n)for(j=0;j<n;j++)
#define r rand()
int main(){int x,s=46,n,i,j,z=77,l[z];char m[z*s],h[z];initscr();raw();F(z*s)j[
m]=35;F(s)for(j[l]=i=(r%4+3)*z+(n=r%17*z+r%s+z);n<=i;n+=z)for(x=n;x<=n+j/2;m[++
x]=s);F(9)l[j][m]=z,j[h]=2;m[*l]=64;*h=5;l[j][m]=62;F(z){x=n=l[i++,i%=9];if(i)!
i[h]||*l^(n+=r%3+r%3*z+~z)||--*h?0:abort();else{F(25)mvaddnstr(j,i,m+j*z,z);j=s
-getch();m[n+=j/3*z-j%3+153]^62||main();F(9)l[j+1]^n||--h[j+1]||n[m]--;}n[m]^s
||(m[l[i]=n]=x[m],x[m]=s);}}

This weighs in at a hefty 493 bytes of C source code. I call it the "Monster Caves". Decend downwards, and kill as many monsters as you can. Beware! Hitting an already dead monster causes it to arise as a nearly unkillable Lich! How many monsters can you kill before your luck runs out, or you find the mysterious moving stairwell? Note that the game doesn't have enough bytes to remember (and print out) your kill total, so you'll have to do that yourself. You can use the numeric keypad (with num-lock on) to move about. Move into a monster to attack it, and move into a stairway to decend another level. If you get stuck in a disconnected part of a level, try pressing some other keys... you may just be able to teleport out.

To compile the source code use gcc -O2 source.c -o monster_caves -lcurses to link with the curses library. Note that one of the tricks used to shrink the source is to not include the curses header file. The functions called in the curses library are lucky enough to have the correct signature without it.

So the above source is extremely hard to read and understand, so how does it work? The first trick is to use the C pre-processor to replace the #defines with their macro-expanded result. This (together with the addition of the removed header) yields


#include<stdlib.h>
#include<curses.h>
int main(){int x,s=46,n,i,j,z=77,l[z];char m[z*s],h[z];initscr();raw();for(j=0;j<z*s;j++)j[
m]=35;for(j=0;j<s;j++)for(j[l]=i=(rand()%4+3)*z+(n=rand()%17*z+rand()%s+z);n<=i;n+=z)for(x=n;x<=n+j/2;m[++
x]=s);for(j=0;j<9;j++)l[j][m]=z,j[h]=2;m[*l]=64;*h=5;l[j][m]=62;for(j=0;j<z;j++){x=n=l[i++,i%=9];if(i)!
i[h]||*l^(n+=rand()%3+rand()%3*z+~z)||--*h?0:abort();else{for(j=0;j<25;j++)mvaddnstr(j,i,m+j*z,z);j=s
-getch();m[n+=j/3*z-j%3+153]^62||main();for(j=0;j<9;j++)l[j+1]^n||--h[j+1]||n[m]--;}n[m]^s
||(m[l[i]=n]=x[m],x[m]=s);}}

Unfortunately, this is less than enlightening, so some pretty-printing is in order. Adding in extra white-space together with more braces yields


#include<stdlib.h>
#include<curses.h>
int main()
{
	int x, s = 46, n, i, j, z = 77, l[z];
	char m[z * s], h[z];
	
	initscr();
	raw();
	
	for  (j = 0; j < z * s; j++)
	{
		j[m] = 35;
	}
	
	for (j = 0; j < s; j++)
	{
		for (j[l] = i = (rand()%4+3)*z + (n = rand()%17*z+rand()%s+z); n <= i; n += z)
		{
			for (x = n; x <= n + j/2; m[++x] = s);
		}
	}
	
	for (j = 0; j < 9; j++)
	{
		l[j][m] = z, j[h] = 2;
	}
	
	m[*l] = 64;
	*h = 5;
	l[j][m] = 62;
	
	for (j = 0; j < z; j++)
	{
		x = n = l[i++, i %= 9];
		if (i)
		{
			!i[h] || *l ^ (n += rand()%3 + rand()%3*z + ~z) || --*h ? 0: abort();
		}
		else
		{
			for (j = 0; j < 25; j++)
			{
				mvaddnstr(j, i, m + j*z, z);
			}
			
			j = s - getch();
			m[n += j/3*z - j%3 + 153] ^ 62 || main();
			
			for (j = 0; j < 9; j++)
			{
				l[j+1]^n || --h[j+1] || n[m]--;
			}
		}
		n[m]^s || (m[l[i] = n] = x[m], x[m] = s);
	}
}

Now the main structure of the code can be seen. The first part initializes the map. This is followed by a loop which initilizes the monsters. The stairway is created, and then the main loop is entered. This prints the screen if it is the player's go, and handles monster and player movement. Finally, if the player hits a stairway, main() is called to generate a new level.

Note how boolean logic and short-circuit evaulation has been used instead of explicit if statements in many places. The resulting code is much shorter if done this way. Of particular note is that the xor operation (^) being used as a != operator. Another silly trick that doesn't actually reduce code size, but definitely makes things harder to read is the use of a[x] being the same as x[a] via the pointer arithmetic identity a[x] == *(a + x) == x[a]. Thus the expression l[j][m] is really evaluating m[l[j]], where m[] is the map array, and l[] is the location array for the monsters and player.

Another trick used is the insertion of the assignement of one variable within the expression for the assignment of another. i.e. m[l[i] = n] = x[m] is much easier to understand as l[i] = n; m[n] = m[x] This saves several bytes since the semi-colon and second evaluation of n aren't needed. More bytes are saved by using the ascii index of characters instead of character expressions.

More things to note are that the player command input is handled by a complex expression that just happens to use the fact that 46 (ascii for the floor character symbol '.') is the same as 49 mod 3, which is the ascii for '1', at the start of the numeric keypad. These ascii values are also used to define C99 dynamic arrays to hold the map and monster lists. The fact that 77, the ascii value of 'M' is close to 80, the width of the screen, is conveniently used.

Expanding the boolean logic expressions into more standard if/else statements will cause the code to balloon in size. The initial source for this game was about 2.6KiB. The compression by moving to single-character variable names, inlining procedures, and removing whitespace was enough to get down to about 1KiB. The other tricks described above provided the extra push to get down to the rediculously small size of 493 bytes.

Unfortunately, the game didn't quite get small enough that the extra feature of a kill counter could be added. Its tiny size also prevented some error checking that would be in a larger version. A player might press a non-numeric key causing the character to "teleport" across the map. Similarly, the lack of error checking causes strange things to happen when two monsters or a monster and the staircase are generated on top of each other. The moving staircase feature is actually this bug. By redefining these bugs into features they are fixed via lampshading.

Finally, here is the source code before any compression at all. Notice how the dungeon generation and monster placement algorithms were changed, and how the coordinate system was changed to be an absolute offset from the start of the map, rather than a x,y tuple.


#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <curses.h>

#define SIZEX	128
#define	SIZEY	64
static char map[SIZEY][SIZEX];

#define MMAX	50
static int mx[MMAX];
static int my[MMAX];
static char mc[MMAX];
static int mhp[MMAX];

static void draw_region(int x1, int x2, int y1, int y2, char c)
{
	int x, y;
	
	for (y = y1; y < y2; y++)
	{
		for (x = x1; x < x2; x++)
		{
			map[y][x] = c;
		}
	}
}

static int rr(int v1, int v2, int r)
{
	return (r % (v1 - v2)) + v1;
}

static void addm(int x, int y, int hp, char c)
{
	int i;
	
	for (i = 0; i < MMAX; i++)
	{
		if (!mc[i])
		{
			mx[i] = x;
			my[i] = y;
			mhp[i] = hp;
			mc[i] = c;
			return;
		}
	}
}

static int getm(int x, int y)
{
	int i;
	for (i = 0; i < MMAX; i++)
	{
		if ((mx[i] == x) && (my[i] == y)) return i;
	}
	
	return -1;
}

static void rand_place(char c, int hp)
{
	do
	{
		int x = rand()&127;
		int y = rand()&63;
		
		if (map[y][x] == '.')
		{
			map[y][x] = c;
			addm(x, y, hp, c);
			return;
		}
	}
	while(1);
}

static void init_map(void)
{
	int i, x1, x2, y1, y2;
	
	draw_region(0, SIZEX - 1, 0, SIZEY, '#');
	
	for (i = 0; i < 200; i++)
	{
		int r = rand();
		x1 = rr(1, SIZEX-20,r);
		x2 = rr(x1+5, x1+19,r);
		y1 = rr(1, SIZEY-8,r);
		y2 = rr(y1+3, y1+7,r);
		
		draw_region(x1, x2, y1, y2, '.');
	}
	
	rand_place('@', 5);
	
	for (i = 0; i < 10; i++)
	{
		rand_place('m', 2);
	}
}

static void draw_screen(void)
{
	int y;
	
	clear();
	
	/* Dump map */
	for (y = 0; y < SIZEY; y++)
	{
		mvaddstr(y, 0, map[y]);
	}
}

static int sgn(int x)
{
	return (x>0)-(x<0);
}

int main(void)
{
	int c;
	int i = 0;
	srand(time(0));
	init_map();
	
	initscr();
	cbreak();
	
	while (1)
	{
		int nx = mx[i], ny = my[i];
		if (!i)
		{
			draw_screen();
			c = 0;
			
			while (!(c=getch()));
			
			if ((c == '1') || (c == '4') || (c == '7')) nx -= 1;
			if ((c == '3') || (c == '6') || (c == '9')) nx += 1;
			if ((c == '7') || (c == '8') || (c == '9')) ny -= 1;
			if ((c == '1') || (c == '2') || (c == '3')) ny += 1;
			
			if (map[ny][nx] == 'm')
			{
				int j = getm(nx, ny);
				
				mhp[j]--;
				
				if (!mhp[j])
				{
					map[ny][nx] = '.';
					mc[j] = 0;
				}
			}
		}
		
		if (mc[i] == 'm')
		{
			nx += sgn(mx[0]-nx);
			ny += sgn(my[0]-ny);
			
			if (map[ny][nx] == '@')
			{
				mhp[0]--;
				
				if (!mhp[0])
				{
					endwin();
					exit(0);
				}
			}
		}
			
		if (mc[i] && (map[ny][nx] == '.'))
		{
			map[my[i]][mx[i]] = '.';
				
			mx[i] = nx;
			my[i] = ny;
				
			map[ny][nx] = mc[i];
		}
		
		i++;
		
		if (i == MMAX) i = 0;
	}
	
	return(0);
}

Comments

Mingos said...
Nice, and very instructive from a programmer's point of view.
BTW, the captcha on the comments is for superhuman captcha readers... 4 tries so far...
jice said...
What the ... !!

j[m] = 35;

j being an int and m an array of char, shouldn't that be m[j] ?!

Does the second version of the code really compile ?
elig said...
Jice: Actually, this is allowed. Even when j is the index and m is the array. It's a standard but little used feature, much like jumping.
jice said...
wow ! awesome. I had to compile it to believe it :)
So what does j[m] represents ?? the same as m[j] ?
jice said...
oh yeah... I should have read the article before the code X)
Researcho said...
i love that, it's like a "hello world" of the roguelikes!

i ported to python with libtcod (jice and mingos roguelike API)

https://sites.google.com/site/comoelroguesite/MonsterCaves.zip?attredirects=0&d=1

i think the (v1 - v2) must be (v2 - v1) to work properly in the rr function
osaksycpdd said...
qxnitmpdlmfttjod, <a href="http://www.wnfuoveknj.com/">tmlsejacda</a> , [url=http://www.atqcsbjvpt.com/]uaokcgjetx[/url], http://www.nxcdwaestm.com/ tmlsejacda
csmyxanjrd said...
acbejmpdlmfttjod, <a href="http://www.qfvhtixdep.com/">ahbxahxcva</a> , [url=http://www.xejlyuscrl.com/]drzneunbau[/url], http://www.kpofpcjvjb.com/ ahbxahxcva
You said...
Awesome! Very usefull
CaptainMcClellan said...
Amazing! Very useful and the program works great. Impressive as well that you were able to make it such a small source.
Virtua Sinner said...
I don't suppose there's anywhere to find an executable, is there?
said...
Enter your comments here
said...
Enter your comments here
said...
said...
Enter your comments here
said...
First Try
said...
Another 1st try of the captha
said...
Enter your comments here
said...
Enter your comments here
said...

Enter the 10 characters above here


Name
Linux
Windows
Developers
About Us Returns Policy Privacy Policy Send us Feedback
Company Info | Product Index | Category Index | Help | Terms of Use
Copyright © Lockless Inc All Rights Reserved.