For a while now I have been building a "Rogue-Like" game, with the aim of targeting multiple computers from my retro collection.
Today I threw away a whole bunch of code and started over, building a maze-based game map instead of the hard-coded, human-designed levels I had been using up until now.
As if that wasn't enough of a challenge, it meant implementing a randomized maze generation algorithm while also tackling some of the quirks of cross-compiling with cc65.
Designing the Game Map
Our game’s world is a grid of ASCII characters. Previously, I had implemented an array of numbers (unsigned char) representing the ASCII or equivalent character codes, but that made designing levels slow, and I had to write a map designer - an extra project.
I started over today by, again, representing our game map as a two-dimensional array, but of strings that will be "procedurally generated" each time the map is built.
Although I am targeting my Linux laptop in testing, I have to keep in mind the potential other computers' varying display capabilities. For example, the Vic 20 display is 22 columns wide, but the PET variants vary from 40 characters to 80 characters wide,
In our game also, while the map might be 40 characters wide and 24 lines high, we need to reserve the top line and the bottom two lines for heads-up display (HUD) information like scores and commands. This means our maze will live in a “playable area” of 21 lines (24 total minus 1 for the top and 2 for the bottom).
Multidimensional Arrays for the Maze
We chose to use a multidimensional array because it gives us precise control over each row and column while abstracting away the actual display of the map.
Why? Consider I might have a version that uses graphics. Perhaps I want to reveal the map as you move around, rather than all at once. It also helps with translating from ASCII into the C64 or Atari character sets.
In C, each string literal represents a row of the maze. For example:
#define MAP_WIDTH 40
#define MAP_HEIGHT 24
#define HUD_TOP 1
#define HUD_BOTTOM 2
#define PLAYABLE_HEIGHT (MAP_HEIGHT - HUD_TOP - HUD_BOTTOM)
char map[MAP_HEIGHT][MAP_WIDTH + 1] = {
"HUD: Info goes here", // Top HUD line (example)
// 21 lines of playable area will be generated here...
"Status: OK", // Bottom HUD lines...
"Commands: WASD to move"
};
To complete our approach, we need to generate the maze within the playable area and then center it within the full map.
Generating the Maze
For the maze, for it to be playable, we need corridors (or passages) that are at least 3×3 in size, with walls (using the # character) that are thick enough to give our maze a solid structure.
I divided the maze into a grid of “cells” where each cell, when carved out, becomes a 3×3 open block. Adding walls between these cells guarantees that adjacent cells are separated by at least one wall.
Depth-First Search (DFS) and Recursive Backtracking
As with my Python maze generation example, I implemented a version of the recursive backtracking algorithm. It's a popular choice for maze generation because it is simple and relatively quick, while producing actually walkable mazes.
Divide the Maze into Cells:
Calculate the number of cells horizontally and vertically based on the playable area. For instance, with a 40×24 map (and after reserving HUD lines), we might get 9 cells horizontally and 5 cells vertically.
Carve Out a Maze:
Starting at a cell (usually at the top left), mark its corresponding 3×3 block as a passage (.) and then randomly choose one of its unvisited neighbors. When moving to a neighbor, we “carve” a corridor by clearing the wall between the current cell and the neighbor cell. This ensures that every passage is wide enough.
Centering the Maze:
Once the maze is generated in a temporary buffer, we copy it into our final game map array. The maze is centered horizontally and vertically within the playable area.
Placing the Player Character
After generating the maze, we want to place the player character (represented by @) in a randomly valid location. To avoid dead ends or cramped spaces, we ensure that the candidate spot:
- Is a passage (
.), and - Has open space (passages) immediately above, below, and to both sides.
We repeatedly pick random coordinates until one meets these conditions and then place the @ character there.
Adapting for cc65: Old-School C and Memory Constraints
When cross-compiling our game for retro platforms with cc65, I encountered some frustrations:
C89 Compatibility:
cc65 adheres to the older C89 standard. This means:- Variables must be declared at the beginning of a block, not inside for-loop headers.
- Initializer lists for local arrays (e.g.,
int directions[4] = {0,1,2,3};) may not be fully supported. Instead, we must declare the array and assign values individually.
Memory Constraints:
cc65 (targeting 6502 systems) has limited stack space. To avoid “too many local variables” errors, I moved large arrays—such as our temporary maze buffer, stack, and visited grid—to global scope.Time Function Limitations:
cc65’s libc does not fully support standard time functions (it tries to pull inclock_gettime, for example). We can solve this for now by either:- Using a fixed seed (e.g.,
srand(1);) for repeatable randomness, or - Providing a dummy implementation of
time().
- Using a fixed seed (e.g.,
Putting It All Together
Below is a simplified version of the final code. It compiles both with modern C compilers and for cc65, but will need a better randomisation for targets without the full time library:
#include <stdio.h>
#include <stdlib.h>
// Instead of time.h, you might need a fixed seed for cc65
// #include <time.h>
#define MAP_WIDTH 40
#define MAP_HEIGHT 24
#define HUD_TOP 1
#define HUD_BOTTOM 2
#define PLAYABLE_HEIGHT (MAP_HEIGHT - HUD_TOP - HUD_BOTTOM)
#define CELLS_X ((MAP_WIDTH - 1) / 4)
#define CELLS_Y ((PLAYABLE_HEIGHT - 1) / 4)
#define MAZE_WIDTH (CELLS_X * 4 + 1)
#define MAZE_HEIGHT (CELLS_Y * 4 + 1)
#define CELL_WIDTH 3
#define CELL_HEIGHT 3
char map[MAP_HEIGHT][MAP_WIDTH + 1];
char maze[MAZE_HEIGHT][MAZE_WIDTH + 1];
typedef struct {
int x, y;
} Cell;
Cell stack[CELLS_X * CELLS_Y];
int stackSize = 0;
int visited[CELLS_Y][CELLS_X];
void push(Cell c) {
stack[stackSize++] = c;
}
Cell pop(void) {
return stack[--stackSize];
}
int isEmpty(void) {
return (stackSize == 0);
}
void shuffle(int *array, int n) {
int i, j, temp;
for (i = n - 1; i > 0; i--) {
j = rand() % (i + 1);
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
void carveMaze(void) {
int i, j, k;
/* Initialize maze with walls */
for (i = 0; i < MAZE_HEIGHT; i++) {
for (j = 0; j < MAZE_WIDTH; j++) {
maze[i][j] = '#';
}
maze[i][MAZE_WIDTH] = '\0';
}
for (i = 0; i < CELLS_Y; i++) {
for (j = 0; j < CELLS_X; j++) {
visited[i][j] = 0;
}
}
/* Start at cell (0,0) */
{
int startX = 0, startY = 0, sx, sy;
startX = 0; startY = 0;
visited[startY][startX] = 1;
sx = startX * 4 + 1;
sy = startY * 4 + 1;
for (i = 0; i < CELL_HEIGHT; i++) {
for (j = 0; j < CELL_WIDTH; j++) {
maze[sy + i][sx + j] = '.';
}
}
{
Cell c;
c.x = startX;
c.y = startY;
push(c);
}
}
while (!isEmpty()) {
Cell current;
int directions[4];
int carved;
current = stack[stackSize - 1];
directions[0] = 0; directions[1] = 1;
directions[2] = 2; directions[3] = 3;
carved = 0;
shuffle(directions, 4);
for (k = 0; k < 4; k++) {
int dir, nx, ny;
dir = directions[k];
nx = current.x;
ny = current.y;
if (dir == 0) { ny--; }
else if (dir == 1) { nx++; }
else if (dir == 2) { ny++; }
else if (dir == 3) { nx--; }
if (nx < 0 || nx >= CELLS_X || ny < 0 || ny >= CELLS_Y)
continue;
if (visited[ny][nx])
continue;
{
int cx, cy, nx_maze, ny_maze;
cx = current.x * 4 + 1;
cy = current.y * 4 + 1;
nx_maze = nx * 4 + 1;
ny_maze = ny * 4 + 1;
if (dir == 0) {
int wallY = cy - 1;
for (j = 0; j < CELL_WIDTH; j++) {
maze[wallY][cx + j] = '.';
}
} else if (dir == 1) {
int wallX = cx + CELL_WIDTH;
for (i = 0; i < CELL_HEIGHT; i++) {
maze[cy + i][wallX] = '.';
}
} else if (dir == 2) {
int wallY = cy + CELL_HEIGHT;
for (j = 0; j < CELL_WIDTH; j++) {
maze[wallY][cx + j] = '.';
}
} else if (dir == 3) {
int wallX = cx - 1;
for (i = 0; i < CELL_HEIGHT; i++) {
maze[cy + i][wallX] = '.';
}
}
for (i = 0; i < CELL_HEIGHT; i++) {
for (j = 0; j < CELL_WIDTH; j++) {
maze[ny_maze + i][nx_maze + j] = '.';
}
}
}
visited[ny][nx] = 1;
{
Cell c;
c.x = nx;
c.y = ny;
push(c);
}
carved = 1;
break;
}
if (!carved) {
pop();
}
}
/* Copy maze into the final map */
for (i = 0; i < MAP_HEIGHT; i++) {
for (j = 0; j < MAP_WIDTH; j++) {
map[i][j] = '#';
}
map[i][MAP_WIDTH] = '\0';
}
{
int playable_offsetY, offsetX, offsetY;
playable_offsetY = HUD_TOP;
offsetX = (MAP_WIDTH - MAZE_WIDTH) / 2;
offsetY = playable_offsetY + ((PLAYABLE_HEIGHT - MAZE_HEIGHT) / 2);
for (i = 0; i < MAZE_HEIGHT; i++) {
for (j = 0; j < MAZE_WIDTH; j++) {
map[i + offsetY][j + offsetX] = maze[i][j];
}
}
}
}
void placePlayer(void) {
int row, col;
do {
row = (rand() % (PLAYABLE_HEIGHT - 2)) + HUD_TOP + 1;
col = (rand() % (MAP_WIDTH - 2)) + 1;
} while (map[row][col] != '.' ||
map[row-1][col] != '.' ||
map[row+1][col] != '.' ||
map[row][col-1] != '.' ||
map[row][col+1] != '.');
map[row][col] = '@';
}
int main(void) {
int i;
/* For cc65, consider using a fixed seed */
srand(1);
carveMaze();
placePlayer();
printf("HUD: Score 0\n");
for (i = HUD_TOP; i < MAP_HEIGHT - HUD_BOTTOM; i++) {
printf("%s\n", map[i]);
}
printf("Status: OK\n");
printf("Commands: WASD to move\n");
return 0;
}
What's next?
Here is where I am at currently working on Linux/Mac:
It's playable, and already there is some fun to be had, but object placement is purely random (while targeting an empty space as described earlier).
You move up a level after picking up a number of idols matching your level, so level 3 has 3x idols.
That is the only change in difficulty, so I need more and different enemies, plus currently there are keys but no doors. Some smart logic to place doors will make it much better.
dude this is SO COOL.
wow.
i compiled it but i dont know how to play it
maybe it doesnt play yet.
this is art though!
respect to you!
thanks for sharing
Oh that code just demonstrates the maze creation, I have the current build of the game in another listing in GitHub. When I’m back at my desk I’ll share :)
im actually new to rouge like games. i just started playing Noita. and its VERY impressive.... like i was blown away by it...