A Futile Exercise: C Roguelike in <4Kb

[GinDiamond]

Just for fun, I want to make a "roguelike" for the Synertek Sym-1 in under 4Kb... in C! I'm using the CC65 compiler. However, this number is more like 3.5Kb, because the first 512 bytes are used for the zero page and stack...

**EDIT**
You can also compile this on windows or linux to test out!

Originally, I wanted to compile it for purely the 6502, but the 65c02 option seems to generate slightly better code, so I'll use the 65c02 for now and switch back if I can.

Right now, after rewriting the dungeon generator (literally just make a box) and changing some variables and structures around, I have reduced the size from ~3200 bytes to 2688 bytes. However, I want to add in:
1. Multiple monsters!
2. Display your HP!
3. Simple combat!
4. Simple random floor generation (possibly just simple pillars?)

The code is such:

Code: Select all

// ------------------
// Roguelike for Sym-1
// Patrick Jackson
// ------------------

#define	SYM		1
//#include "symrogue.h"

#if (SYM == 1)

#include <symio.h>
#define	input()	getchar()
#define _putchar(c)	putchar(c)
#define puts(s) _puts(s)
#define	input()	getchar()

#if (ALTAIR == 1)
#define newline()   putchar('\r')
#else
#define newline()   putchar('\n');putchar('\r')
#endif

#else
#include <stdio.h>
#define	input()	getch()
#define newline()   putchar('\n');

#endif
#include <stdlib.h>
#include <string.h>

#define clrscr()    puts("\033[H");

#define ROW_LEN		10
#define	COL_HGHT	10
#define	MAP_SIZE	ROW_LEN * COL_HGHT
#define MONS_NUM    1

typedef struct
{
	int xy;
	int _xy;
	char ch;
} Entity;

Entity *monster;

int pos = 15;
char hp = 50;

unsigned char key_input = 0x00;

unsigned char map[MAP_SIZE + 1];

#if (SYM == 1)
void _puts(s)
char *s;
{
	char c;
	while ( c = *s++ )
		_putchar(c);
	newline();
}
#endif

// Function to create an X by Y box

void printMap()
{
	unsigned char i;
	for (i = 0; i < MAP_SIZE; i++)
	{
		putchar(map[ i ]);
		if ( ( (i + 1) % ROW_LEN) == 0)
			newline();
	}
}

void printStat()
{
    //
}

void combat()
{
    //
}

void gameLoop()
{
    static int _pos;
    static int m_dir;

    map[pos] = '.';
    map[monster->xy] = '.';
    _pos = pos;
    monster->_xy = monster->xy;

    switch (key_input)
    {
	case 'w':
		pos -= ROW_LEN;
		break;
    case 'a':
        pos--;
        break;
	case 's':
		pos += ROW_LEN;
		break;
    case 'd':
        pos++;
        break;
    default:
        break;
    }

    // check for wall tile
    if ( map[pos] == '#' )
        pos = _pos;

    // check for player combat
    if ( pos == monster->xy )
    {
        combat();
        pos = _pos;
    }

    // move monster
    m_dir = ( rand() % 4 );     // really large, perhaps there's a smaller way?
    switch ( m_dir )
    {
    case 0:
        monster->xy++;
        break;
    case 1:
        monster->xy--;
        break;
    case 2:
        monster->xy += ROW_LEN;
        break;
    case 3:
        monster->xy -= ROW_LEN;
        break;
    }
    if ( map[monster->xy] == '#' )
    {
        monster->xy = monster->_xy;
    }

    // print player
    map[pos] = '@';
    // print monster
    map[monster->xy] = monster->ch;

	clrscr();
    printMap();
    printStat();
}

int main(void)
{
	unsigned char i;

	Entity loc_monster = {75, 0, 'M'};

	monster = &loc_monster;

	// truly clears screen
	puts("\033[2J");

	// --------- Create map --------------

	// Fill entire grid with wall tiles '#'
	memset(map, '#', MAP_SIZE);

	// Fill interior with floor tiles '.'
	for (i = 0; i < COL_HGHT - 2; i++)
	{
		memset(map + (i * ROW_LEN + ROW_LEN + 1), '.', ROW_LEN - 2);
	}

	do
	{
	    gameLoop();
	    key_input = input();
	}
	while ( key_input != 'q' );

    return 0;
}

I'm looking to see if I can optimize anything for size even more, given this code. I'm honestly kind of stuck at this point.

I'm using the -Cl -Osir cc65 command line options for the Synertek Sym-1.

Does anyone have some pointers/ideas?

[drogon]

GinDiamond wrote:

Just for fun, I want to make a "roguelike" for the Synertek Sym-1 in under 4Kb... in C! I'm using the CC65 compiler. However, this number is more like 3.5Kb, because the first 512 bytes are used for the zero page and stack...

A great effort!

I did start off down the C route with my Ruby boards, but gave-up after a while (for BCPL, but that's another story). I went as far as to create a new platform for my board with its own library and so on, so I could use the -t ruby command-line option which worked well. I didn't use anything more than -O on the command-line for optimisations though.

I mostly gave up on C as cc65 can't target the '816 and while others can now, back in 2018/19 options were limited...

But if all you have is 4K then that's not bad at all... and I'm almost inspired to see if I can make a rogue-like game in TinyBasic now...

Cheers,

-Gordon

[barrym95838]

GinDiamond wrote:

I'm looking to see if I can optimize anything for size even more, given this code. I'm honestly kind of stuck at this point.

I'm using the -Cl -Osir cc65 command line options for the Synertek Sym-1.

Does anyone have some pointers/ideas?

My experience on the subject is only distantly related, but perhaps it could provide some food for thought. It has been about 35 years since I used a 68k cross compiler on vax ultrix32 to target an imbedded machine in college for an operating systems design class, but I remember manually trimming the header files, and avoiding expensive calls to stuff like printf() ... I was unable to find the command line options you describe, so I'm unsure what they do. I definitely used some type of -Os option, and it seemed to work well, relatively speaking. I had plenty of RAM on the target system, so it was mostly just for "smallest binary" bragging rights (most of the other students were using Modula-2, but there were a few other C users). I was pressed for time, or I would have probably manually edited the intermediate assembly file to try to gain more advantage, although I seem to remember that the -Os option did a pretty good job by itself.

[GinDiamond]

Ah, editing the intermediate assembly file, thats a good idea! It sounds a bit like cheating, but I mean, if it works...

I'll take another crack at adding features very soon, its a pretty interesting adventure. Also, the -Osir does inlines, the register keyword, and static locals.

[teamtempest]

Not sure if it will help much, but in this section you're accessing the monster position through a pointer (as opposed to the player position, which is much more direct).

Quote:

// move monster
m_dir = ( rand() % 4 ); // really large, perhaps there's a smaller way?
switch ( m_dir )
{
case 0:
monster->xy++;
break;
case 1:
monster->xy--;
break;
case 2:
monster->xy += ROW_LEN;
break;
case 3:
monster->xy -= ROW_LEN;
break;
}
if ( map[monster->xy] == '#' )
{
monster->xy = monster->_xy;
}

You might consider reducing pointer use by something like this:

Code: Select all

  // move monster
    m_dir = ( rand() % 4 );     // really large, perhaps there's a smaller way?
    switch ( m_dir )
    {
    case 0:
        delta = 1;
        break;
    case 1:
        delta = -1;
        break;
    case 2:
        delta =  ROW_LEN;
        break;
    case 3:
        delta = -ROW_LEN;
        break;
    }
    newmpos = (monster->xy += delta);
    if ( map[newmpos] != '#' )
    {
        monster->xy = newmpos;
    }

[John West]

Multiplication, division, and mod are going to be unpleasant for the 6502, which doesn't have instructions for them. Your

Code: Select all

 rand() % 4 

in the snippet above would probably be improved by replacing it with

Code: Select all

 rand() & 3 

unless the compiler is already able to apply that optimisation (which it probably can't, as rand() is declared to return a signed integer even though it never returns a negative value).

You also use % in printMap(). You could use the same trick there if you made ROW_LEN a power of 2. Or you could introduce a second variable which keeps track of the position within the current line:

Code: Select all

   unsigned char i;
   unsigned char posInLine;
   for (i = 0, posInLine = 0; i < MAP_SIZE; i++)
   {
      putchar(map[ i ]);
      posInLine++;
      if (posInLine == ROW_LEN)
      {
         posInLine = 0;
         newline();
      }
   }

Then there's the multiply when you're filling the map with '.' in main(). I don't know how good cc65's optimiser is - if it can apply strength reduction that should be fine. Otherwise you can do it yourself:

Code: Select all

   unsigned char iMulLen;
   for (i = 0, iMulLen = 0; i < COL_HGHT - 2; i++)
   {
      memset(map + (iMulLen + ROW_LEN + 1), '.', ROW_LEN - 2);
      iMulLen += ROW_LEN;
   }

and of course once you've done that you can remove i altogether.

[barrym95838]

GinDiamond wrote:

Also, the -Osir does inlines, the register keyword, and static locals.

I don't know if this is generally true, but I learned that in-lines are for increased performance, not reduced footprint. And for the 65xx, the register keyword seems a bit silly, but may still employ a useful strategy that's not immediately obvious, like using A:X to pass an int to and from a simple function.

[drogon]

GinDiamond wrote:

Ah, editing the intermediate assembly file, thats a good idea! It sounds a bit like cheating, but I mean, if it works...

If it works, good, but you'll need to do it every time to change and compile the C code...

I'd stick with "make it work, then make it work faster/smaller" ... Or Wirths: "Premature optimisation is the root of all evil". I've been guilty of that in the past...

-Gordon

[Proxy]

there is a page on github about some cc65 code optimization tips: https://github.com/ilmenit/CC65-Advance ... /README.md

on another note, personally i would try to stay away from C's regular data types like "int", "short", "long", etc and just always use the <stdint.h> variants like "uint8_t", "uint16_t", etc.
they're mainly intended to make porting software easier, as C's data types have no exact defined width (except for char), but i also just like to use them in general to make it easier to keep track of how much memory is being used and what the capacity of the variable is. (plus i just got sick of typing out "unsigned" every time, "uintX_t" is so much shorter and nicer to type IMO)

and the portability thing is also useful when you first make a prototype on your PC and then try it out on the actual hardware (or emulator).

.

anyways, the others have already found quite some things to optimize, but i hope you can make use of the page linked and finish that game!

[GinDiamond]

You guys have all been enormously helpful! I'll try a crack at this very soon, may even livestream it a bit! I'll have to let you know how it works out.
Super stoked for this, hopefully it will actually succeed!

[GinDiamond]

So, thanks to you guys, I'm making great headway! However, there's something kind of strange. When I do this code to print the map:

Code: Select all

int i;
    for (i = 0; i < MAP_SIZE; i++)
    {
        putchar( map [ i ] );
        if ( ( ( i + 1 ) & 15 ) == 0 )
            newline();
    }

On the Sym-1, I just get a single vertical line of wall tiles. When I run it on Windows, it works just fine.

Now, when I use this code:

Code: Select all

unsigned char i;
    unsigned char posInLine;
    for (i = 0, posInLine = 0; i < MAP_SIZE; i++)
    {
        putchar( map[ i ] );
        posInLine++;
        if ( posInLine == ROW_LEN )
        {
            posInLine = 0;
            newline();
        }
    }

then it works fine! However, its not quite as small as the supposedly "working" one. Any ideas?

The compiler options are 65C02 and -Cl -Osr

[GinDiamond]

Update! The binary is now 1692 bytes large! Still more optimizations to do:

Code: Select all

// ------------------
// Roguelike for Sym-1
// Patrick Jackson
// ------------------

#include "symRogue.h"

#define ROW_LEN		16
#define	COL_HGHT	10
#define	MAP_SIZE	ROW_LEN * COL_HGHT
#define MONS_NUM    1

typedef struct
{
	uint8_t xy;
	uint8_t ch;
} Entity;

Entity *monster;

uint8_t m_delta;
uint8_t newmpos;

uint8_t pos = 25;
uint8_t hp = 50;

uint8_t key_input = 0x00;

uint8_t map[MAP_SIZE + 1];

// Function to create an X by Y box

void printMap()
{
    uint8_t i;
    uint8_t posInLine;
    for (i = 0, posInLine = 0; i < MAP_SIZE; i++)
    {
        putchar( map[ i ] );
        posInLine++;
        if ( posInLine == ROW_LEN )
        {
            posInLine = 0;
            newline();
        }
    }
}

void printStat()
{
    //
}

void combat()
{
    //
}

void gameLoop()
{
    uint8_t _pos;
    uint8_t m_dir;

    map[pos] = '.';
    map[monster->xy] = '.';
    _pos = pos;

    switch (key_input)
    {
	case 'w':
		pos -= ROW_LEN;
		break;
    case 'a':
        pos--;
        break;
	case 's':
		pos += ROW_LEN;
		break;
    case 'd':
        pos++;
        break;
    default:
        break;
    }

    // check for wall tile
    if ( map[pos] == '#' )
        pos = _pos;

    // check for player combat
    if ( pos == monster->xy )
    {
        combat();
        pos = _pos;
    }

    // move monster
    m_dir = ( rand() & 3 );     // really large, perhaps there's a smaller way?
    switch ( m_dir )
    {
    case 0:
        m_delta = 1;
        break;
    case 1:
        m_delta = -1;
        break;
    case 2:
        m_delta = ROW_LEN;
        break;
    case 3:
        m_delta = -ROW_LEN;
        break;
    }
    newmpos = (monster->xy + m_delta);
    if ( map[newmpos] != '#' )
    {
        monster->xy = newmpos;
    }

    // print player
    map[pos] = '@';
    // print monster
    map[monster->xy] = monster->ch;

	clrscr();
    printMap();
    printStat();
}

int main(void)
{
	uint8_t iMulLen;

	Entity loc_monster = {75, 'M'};

	monster = &loc_monster;

	// truly clears screen
	puts("\033[2J");

	// --------- Create map --------------

	// Fill entire grid with wall tiles '#'
	memset(map, '#', MAP_SIZE);

	// Fill interior with floor tiles '.'
	for ( iMulLen = 0; iMulLen < MAP_SIZE - ( 2 * ROW_LEN );)
    {
        memset( map + (iMulLen + ROW_LEN + 1), '.', ROW_LEN - 2 );
        iMulLen += ROW_LEN;
    }

	do
	{
	    gameLoop();
	    key_input = input();
	}
	while ( key_input != 'q' );

    return 0;
}

That map printing function doesn't seem to want to work with the ampersand thing, even the modulo didn't work correctly. Still don't know why, I really want that fixed because I think it trims a bit of code too.

Instead of a struct for the monster, I think I may do something like this:

Code: Select all

#define MONSTERS 4
uint8_t monster_xy[MONSTERS] = {0};
uint8_t monster_ch[MONSTERS] = {'M'};

and loop through that instead of a struct.

**EDIT**
I did the above change, and even though I just have 1 monster, the binary is now 1,494 bytes!

[BillG]

GinDiamond wrote:

So, thanks to you guys, I'm making great headway! However, there's something kind of strange. When I do this code to print the map:

Code: Select all

int i;
    for (i = 0; i < MAP_SIZE; i++)
    {
        putchar( map [ i ] );
        if ( ( ( i + 1 ) & 15 ) == 0 )
            newline();
    }

On the Sym-1, I just get a single vertical line of wall tiles. When I run it on Windows, it works just fine.

Now, when I use this code:

Code: Select all

unsigned char i;
    unsigned char posInLine;
    for (i = 0, posInLine = 0; i < MAP_SIZE; i++)
    {
        putchar( map[ i ] );
        posInLine++;
        if ( posInLine == ROW_LEN )
        {
            posInLine = 0;
            newline();
        }
    }

then it works fine! However, its not quite as small as the supposedly "working" one. Any ideas?

The compiler options are 65C02 and -Cl -Osr

What is ROW_LEN when you are doing this?

If it is 16 decimal, 0x10 hex, it should work.

However, if it is 10 decimal, 0xA hex, the two code sequences will not do the same thing!

[GinDiamond]

It happened even when ROW_LEN is 16, strangely enough

[GinDiamond]

Just as an update, I'm adding in multiple monsters, combat, health, gold, and a status bar. So far, 2264 bytes.