A Futile Exercise: C Roguelike in <4Kb

Programming the 6502 microprocessor and its relatives in assembly and other languages.
greghol
Posts: 29
Joined: 04 Oct 2019
Location: Rancho Cordova, CA

Re: A Futile Exercise: C Roguelike in <4Kb

Post by greghol »

barrym95838 wrote:
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.
Barry,

This sounds like "OS Pragmatics" CSC159 at CSUS. :) I heard in the past that the target was a 68K dev board. When I took the class the target was a PC booted from a floppy as a boot loader for the OS transferred over the serial port. The dev environment was a PC running linux.

Greg
User avatar
barrym95838
Posts: 2056
Joined: 30 Jun 2013
Location: Sacramento, CA, USA

Re: A Futile Exercise: C Roguelike in <4Kb

Post by barrym95838 »

Greg, I'm 90% certain that you're 90% accurate. :lol:
The 68K target system was some type of generic-looking workstation similar to this, with serial links to athena (one of the campus' vaxen) and a few dumb terminals (to test our code's ability to handle them simultaneously). Many of the remaining details are fuzzy, because it was a long time ago and I was partying heavily at the time. I wasn't a good team member to my fellow classmates, Hiro and Ayub. Sorry, guys, wherever you are!
Got a kilobyte lying fallow in your 65xx's memory map? Sprinkle some VTL02C on it and see how it grows on you!

Mike B. (about me) (learning how to github)
GinDiamond
Posts: 39
Joined: 12 Feb 2022

Re: A Futile Exercise: C Roguelike in <4Kb

Post by GinDiamond »

Just to make sure you guys know this is still going on, here's an update!
Been busy the last week or so, but here's the code. Multiple monsters, and each can detect walls!
I'll add in combat, gold and health pickups, THEN I'll optimize even more. I'm keeping optimization in mind.

Can you guys take a look at my status bar function, it seems clunky, is there a better way to construct a status bar? I think it won't work if health is below a 2 digit number.

Oh yeah, its 2,594 bytes!!!!

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    3

uint8_t m_delta;
uint8_t newmpos;

char int_str[4];
char status_str[20];

uint8_t monster_xy[MONS_NUM];
uint8_t monster_ch[MONS_NUM];
uint8_t monster_hp[MONS_NUM];

uint8_t gold = 0;

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()
{
    itoa(hp, int_str, 10);
    strcpy(status_str, "HP: ");
    strcpy(status_str + 4, int_str);
    strcpy(status_str + 4 + 2, " \t");
    puts(status_str);
    strcpy(status_str, "Gold: ");
    itoa(gold, int_str, 10);
    strcpy(status_str + 4 + 2, int_str);
    puts(status_str);
}

void combat(i)
uint8_t i;
{
    //
}

void m_combat()
{
    //
}

void gameLoop()
{
    uint8_t _pos;
    uint8_t m_dir;
    uint8_t i;

	clrscr();

    map[pos] = '.';
    _pos = pos;

    for (i = 0; i < MONS_NUM; i++)
        map[monster_xy[i]] = '.';

    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
    for (i = 0; i < MONS_NUM; i++)
    {
        if ( pos == monster_xy[i] )
        {
            combat(i);
            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;
        default:
            break;
        }
        newmpos = (monster_xy[i] + m_delta);
        if ( map[newmpos] != '#' )
        {
            monster_xy[i] = newmpos;
        }

        // check for player combat
        if ( pos == monster_xy[i] )
        {
            m_combat();
            monster_xy[i] -= m_delta;
        }
        // print monster
        map[monster_xy[i]] = monster_ch[i];
        //printf("Monster: %d\tXY: %d\n", i, monster_xy[i]);
    }

    // print player
    map[pos] = '@';
    printMap();
    printStat();
}

int main(void)
{
	uint8_t iMulLen;

    uint8_t i;

    for (i = 0; i < MONS_NUM; i++)
    {
        monster_xy[i] = 75;
        monster_ch[i] = 'M';
        monster_hp[i] = 20;
    }

	// Start set up of status line
	strcpy(status_str, "HP: ");

	// 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;
}
SamCoVT
Posts: 344
Joined: 13 May 2018

Re: A Futile Exercise: C Roguelike in <4Kb

Post by SamCoVT »

GinDiamond wrote:
Can you guys take a look at my status bar function, it seems clunky, is there a better way to construct a status bar? I think it won't work if health is below a 2 digit number.

Code: Select all

void printStat()
{
    itoa(hp, int_str, 10);
    strcpy(status_str, "HP: ");
    strcpy(status_str + 4, int_str);
    strcpy(status_str + 4 + 2, " \t");
    puts(status_str);
    strcpy(status_str, "Gold: ");
    itoa(gold, int_str, 10);
    strcpy(status_str + 4 + 2, int_str);
    puts(status_str);
}
Why strcpy constant strings when you can just puts() them directly as you go along?

Code: Select all

void printStat()
{
    itoa(hp, int_str, 10);
    puts("HP: ");
    puts(int_str);
    puts(" \tGold: ");
    itoa(gold, int_str, 10);
    puts(int_str);
}
Also, I haven't seen anyone write new C code using this ancient format (original K&R C) before - although I have seen plenty of very old code written this way:

Code: Select all

void combat(i)
uint8_t i;
{
    //
}
The cool C kids these days use the ANSI/ISO format, which looks like this:

Code: Select all

void combat(uint8_t i)
{
    //
}
The old format is still considered valid C, so no need to change it. Indeed, I wondered if you were using it for a "retro" feel to your code.
GinDiamond
Posts: 39
Joined: 12 Feb 2022

Re: A Futile Exercise: C Roguelike in <4Kb

Post by GinDiamond »

Hey, thanks for the tips!
I use strcpy because I want the string to be in one line, puts does a new line. There's nothing saying I can't do a switch in my code to not put a newline, so that's always a possibility.

As for the K&R syntax, it started as a retro thing, then I quickly realized that the default C engine (or only engine) for cc65 is c89, which is wild to me.
I also did the k&r syntax so Aztec C can compile it natively for CP/M and Apple II, if you want!
SamCoVT
Posts: 344
Joined: 13 May 2018

Re: A Futile Exercise: C Roguelike in <4Kb

Post by SamCoVT »

GinDiamond wrote:
I use strcpy because I want the string to be in one line, puts does a new line.
That makes sense. I had forgotten about puts() adding a newline at the end. I often write my own routines for microcontrollers rather than use stdio.h routines to reduce compiled size, and my string printing routine doesn't add a newline.

I don't know how much space itoa is taking, but here is the routine I use for printing integers with a fixed width when I know the width. Adjust the mask for the max number of digits your value will ever have (eg. 100 for 3 digit numbers). SendChar() is my routine to send a single character (over the serial port).

Code: Select all

// Send a word (16-bits, 5 digits with leading 0s)
void SendWord(uint16_t w) {
  uint16_t mask = 10000;
  while (mask) {
    SendChar('0'+(w/mask));
    w %= mask;
    mask/=10;
  }
  return;
}
While % and / are expensive operations, you are likely already paying that price with the code in itoa(). It's also possible to write it without division like this snippet that I found in my collection of junk that I wrote a long time ago - which certainly has lots of room for optimization:

Code: Select all

void SendByte(unsigned char b) {
  unsigned char mask = 100;
  unsigned char digit;
  // 100s digit.
  digit = '0';
  while(b >= mask)
  {
    digit++;
    b = b - mask;
  }
  SendChar(digit);

  // 10s digit.
  mask = 10;
  digit = '0';
  while(b >= mask)
  {
    digit++;
    b = b - mask;
  }
  SendChar(digit);
  
  // 1s digit.
  mask = 1;
  digit = '0';
  while(b >= mask)
  {
    digit++;
    b = b - mask;
  }
  SendChar(digit);
  
  return;
}
GinDiamond wrote:
As for the K&R syntax, it started as a retro thing, then I quickly realized that the default C engine (or only engine) for cc65 is c89, which is wild to me.
I also did the k&r syntax so Aztec C can compile it natively for CP/M and Apple II, if you want!
So not just a retro feel, but actually compatible with retro compilers. That gets you bonus points, of course!
GinDiamond
Posts: 39
Joined: 12 Feb 2022

Re: A Futile Exercise: C Roguelike in <4Kb

Post by GinDiamond »

Currently my problems aren't the optimization, its the roguelike stuff XD
Currently working on collision detection and such. May need to rewrite it a bit, THEN optimize...

Fixed collision! Commenting the code and restructuring so its easier to follow, THEEEENNN optimize....
GinDiamond
Posts: 39
Joined: 12 Feb 2022

Re: A Futile Exercise: C Roguelike in <4Kb

Post by GinDiamond »

I'm doing a rewrite here with a bit more optimization in mind. I've cut down on a bit!
Right now, the code only draws you and the map. Time to add in the monster stuff!
Note that I have a commented out drawmap function. This was suggested to me by google bard, and it seems to work except for the leading characters in the map don't quite work right. I need to figure out what's going on there if I want to use that instead.
I also redid the puts function a bit to use a register instead of 2 byte memory reads, it seems to have saved some space!

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 ROW_MASK    ( ROW_LEN - 1 )
#define MONS_NUM    3

//char* target_hp;

uint8_t pos;
uint8_t map[ MAP_SIZE ];
uint8_t key_input = 0x00;

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

/*
void printMap()
{
    uint8_t i, row;
    clrscr();

    for ( i = 0, row = 0; i < MAP_SIZE; ++i )
    {
        putchar( map[ i ] );
        if ( ! ( i & ( ROW_MASK ) ) )
        {
            row |= 1;
            newline();
        }
    }
}
*/

void parseInput()
{
    uint8_t _pos;

    map[pos] = '.';

    /* Back up current player position */
    _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 ] == '#' )
    {
        /* if wall tile, restore pos */
        pos = _pos;
    }

    map[ pos ] = '@';
}

void parseMonster()
{

}

int main(void)
{
    uint8_t i;

    // Set up player pos
    pos = 25;

    clrdraw();

    // --------- Create map ---------
    // Fill entire grid with wall tiles '#'
    memset( map, '#', MAP_SIZE );
    // Fill interior with floor tiles '.'
    for ( i = ROW_LEN; i < MAP_SIZE - ROW_LEN; i+= ROW_LEN )
        memset( map + i + 1 , '.', ROW_LEN - 2 );


    // --------- Main loop -----------
    do
    {
        parseInput();
        parseMonster();
        printMap();
        key_input = input();
    }
    while ( key_input != 'q' );

    return 0;
}
GinDiamond
Posts: 39
Joined: 12 Feb 2022

Re: A Futile Exercise: C Roguelike in <4Kb

Post by GinDiamond »

With help from Google Bard, I rewrote the printMap function a bit and I am using -Osir now, it generates slightly smaller code.

Code: Select all

void printMap()
{
    uint8_t i;

    clrscr();

    for ( i = 0; i < MAP_SIZE; ++i )
    {
        putchar( map[ i ] );
        if ( ! ( ( i + 1 ) & ( ROW_MASK ) ) )
        {
            newline();
        }
    }
}
So far, the binary is now 1084 bytes!!!

**EDIT**
Upon posting the og function, it seemed a little to AI-generated (an unused variable and even incremented it!)
teamtempest
Posts: 443
Joined: 08 Nov 2009
Location: Minnesota
Contact:

Re: A Futile Exercise: C Roguelike in <4Kb

Post by teamtempest »

You might be able to use the same "move" subroutine for both player and monster(s), since they move the same way.

Code: Select all

uint8_t move(pos, direction, glyph)
{

    uint8_t _pos;

    _pos = pos;

    map[ _pos ] = '.';

   switch( direction )
   (
   case 'w': case 0:
       _pos -= ROW_LEN;
       break;
   case 'a': case 1:
       _pos--;
       break;
   case 's': case 2:
      _pos += ROW_LEN;
      break;
   case 'd': case 3:
      _pos++;
   default:
      break;
   }

   if ( map[_pos] == '#' )
       _pos = pos;
 
   map[ _pos ] = glyph;

   return _pos;
}

/* then the main loop looks like: */

do {

     playerpos = move( playerpos, key_input, '@' );
     monsterpos = move( monsterpos, random() & 0x03, '&' );
     printMap();
    key_input = input();
    }
    while ( key_input != 'q' )
...where how the monster move is generated and what glyph it uses are just guesses. If you have more than one monster, just put their positions in an array and loop on that move() line.
GinDiamond
Posts: 39
Joined: 12 Feb 2022

Re: A Futile Exercise: C Roguelike in <4Kb

Post by GinDiamond »

Thanks for the idea! I'll implement that!

Also going to do a reformat, I tried compiling it for CP/M and it failed miserably on Aztec C...works fine on z88dk.
But I want it to be true C89 compliant for all you old guys out there!
GinDiamond
Posts: 39
Joined: 12 Feb 2022

Re: A Futile Exercise: C Roguelike in <4Kb

Post by GinDiamond »

Your code works a treat! I'll fix it up so there's much less stack work, the custom push and pop for cc65 is quite heavy. I'll see what I can do! Thank you so much!

**EDIT**

Right now, the SYM-1 binary is 1614 bytes! I got to add in combat detection, but I got to remove the stack from the new function, so it may sort itself out! I then need to do the hacky printf, but you guy's ideas I think will help a ton! Then I need to add in floor and item generation, then it *should* be done!
GinDiamond
Posts: 39
Joined: 12 Feb 2022

Re: A Futile Exercise: C Roguelike in <4Kb

Post by GinDiamond »

Here's the code so far. I need to add combat detection and my printf implementation, then it will be back to "original" functionality!

It compiles to 1520 bytes!!!

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 ROW_MASK    ( ROW_LEN - 1 )
#define MONS_NUM    3

unsigned char map[ MAP_SIZE ];

unsigned char lpos, direction, glyph;

unsigned char pos;
unsigned char hp;

unsigned char mons_xy[MONS_NUM];
unsigned char mons_ch[MONS_NUM];
unsigned char mons_hp[MONS_NUM];

unsigned char key_input = 0x00;

void printMap()
{
    unsigned char i;

    clrscr();

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

unsigned char move()
{
    unsigned char _lpos;

    _lpos = lpos;
    map[ _lpos ] = '.';

    switch ( direction )
    {
    case 'w': case 0:
        _lpos -= ROW_LEN;
        break;
    case 'a': case 1:
        _lpos--;
        break;
    case 's': case 2:
        _lpos += ROW_LEN;
        break;
    case 'd': case 3:
        _lpos++;
    default:
        break;
    }

    if ( map[ _lpos ] == '#' )
        _lpos = lpos;
    map[ _lpos ] = glyph;
    return _lpos;
}

int main()
{
    unsigned char i;

    /* Set up player pos */
    pos = 25;

    for ( i = 0; i < MONS_NUM; ++i )
        mons_xy[ i ] = 50;

    clrdraw();

    /* --------- Create map ---------
       Fill entire grid with wall tiles '#' */
    memset( map, '#', MAP_SIZE );
    /* Fill interior with floor tiles '.' */
    for ( i = ROW_LEN; i < MAP_SIZE - ROW_LEN; i+= ROW_LEN )
        memset( map + i + 1 , '.', ROW_LEN - 2 );


    /* --------- Main loop ----------- */
    do
    {
        lpos = pos;
        direction = key_input;
        glyph = '@';
        pos = move();
        for ( i = 0; i < MONS_NUM; i++ )
        {
            lpos = mons_xy[ i ];
            direction = rand()  & 0x03;
            glyph = 'M';
            mons_xy[ i ] = move();
        }
        printMap();
        key_input = input();
    }
    while ( key_input != 'q' );

    return 0;
}
GinDiamond
Posts: 39
Joined: 12 Feb 2022

Re: A Futile Exercise: C Roguelike in <4Kb

Post by GinDiamond »

So, I need to work on the random number generator that you guys have suggested to fix, and the printf function. The combat functions are placeholders, but I anticipate them to be super simple to implement cheaply.
This is the code so far! We got a moving player, monsters, and collision detection!

It is 1580 bytes!!

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 ROW_MASK    ( ROW_LEN - 1 )
#define MONS_NUM    3

unsigned char map[ MAP_SIZE ];

unsigned char lpos, direction, glyph;

unsigned char pos;
unsigned char hp;

unsigned char mons_xy[MONS_NUM];
unsigned char mons_ch[MONS_NUM];
unsigned char mons_hp[MONS_NUM];
unsigned char m_i;

unsigned char key_input = 0x00;

void printMap()
{
    unsigned char i;

    clrscr();

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

void chkMCmbt()
{
    //
}

void chkPCmbt()
{
    //
}

unsigned char move()
{
    unsigned char _lpos;

    /* Move character around */
    _lpos = lpos;
    map[ _lpos ] = '.';

    switch ( direction )
    {
    case 'w': case 0:
        _lpos -= ROW_LEN;
        break;
    case 'a': case 1:
        _lpos--;
        break;
    case 's': case 2:
        _lpos += ROW_LEN;
        break;
    case 'd': case 3:
        _lpos++;
    default:
        break;
    }

    /* Check for wall, player, or monster collision */
    if (map[_lpos] == '#')
        _lpos = lpos;
    else if (map[_lpos] == 'M')
    {
        chkPCmbt();
        _lpos = lpos;
    }
    else if (map[_lpos] == '@')
    {
        chkMCmbt();
        _lpos = lpos;
    }
    map[_lpos] = glyph;

    return _lpos;
}

int main()
{
    unsigned char i;

    /* Set up player pos */
    pos = 25;

    for ( i = 0; i < MONS_NUM; ++i )
        mons_xy[ i ] = 50;

    clrdraw();

    /* --------- Create map ---------
       Fill entire grid with wall tiles '#' */
    memset( map, '#', MAP_SIZE );
    /* Fill interior with floor tiles '.' */
    for ( i = ROW_LEN; i < MAP_SIZE - ROW_LEN; i+= ROW_LEN )
        memset( map + i + 1 , '.', ROW_LEN - 2 );


    /* --------- Main loop ----------- */
    do
    {
        lpos = pos;
        direction = key_input;
        glyph = '@';
        pos = move();
        for ( m_i = 0; m_i < MONS_NUM; m_i++ )
        {
            lpos = mons_xy[ m_i ];
            direction = rand()  & 0x03;
            glyph = 'M';
            mons_xy[ m_i ] = move();
        }
        printMap();
        key_input = input();
    }
    while ( key_input != 'q' );

    return 0;
}
**EDIT**
Binary is now 1572 bytes, I crunched it a bit more by moving the offset addition to the variable definition in the for loop for the map generation. Looking to see if I can also put in an int cast of the map memory pointer to shrink it a tad more...

Code: Select all

/* Fill interior with floor tiles '.' */
for ( i = ROW_LEN + 1; i < MAP_SIZE - ROW_LEN; i+= ROW_LEN )
    memset( map + i, '.', ROW_LEN - 2 );
User avatar
Proxy
Posts: 746
Joined: 03 Aug 2018
Location: Germany

Re: A Futile Exercise: C Roguelike in <4Kb

Post by Proxy »

one other optimization i could think of is to put certain global variables, ones that are often used, into Zeropage. this can be done via some pragma's:

Code: Select all

// bss-name -> uninitialized variables, data-name -> initialized variables
#pragma bss-name (push,"ZEROPAGE")
uint8_t player_pos, player_hp;          // Both of these are now in zeropage
#pragma bss-name (pop)
depending on how much ZP space you have, you might be able to fit quite a few variables into it.
Post Reply