Way back in the mid 80's , the Commodore-64 was the hot machine for hobbyists and gamers. Over time, a lot of the concepts and methods developed on it were eagerly transported to the PC by entheusiasts who migrated to the new intel-based machines from the programmer-friendly little machines. One of the "hot" ideas of the day was text-based adventure games. At the time , most people were of the opinion that such games were easy to write, but that the engines for these games were huge, requiring the programmer to cache huge amounts of information to, and from the disk, in order to even navigate the "world". In any case, I was having, one of those , "No, it does not have to be so bloody difficult..." conversations with another C-64 user , and losing the argument, so I decided to write a few lines of code in BASIC to prove my point. The program worked, and I never met that individual again ... I was never able to prove my point... so whoever and wherever you are... I WAS RIGHT!! SO THERE!

Recently, I rewrote that little program in C and stashed it away for future reference in the event I ever needed a quick-and-dirty engine for whatever... (maybe it was just nostalgia).

So what is this about??

This program struck me as a clever and simple solution to the problem of creating large maze-type games. Recently, a couple of people on #C were asking about similar engines , so I thought I would share my solution with others.

The idea is stunningly simple: Just consider the world as made up of a bunch of rooms, each having anywhere from one, to 4 doors, in any combination. There are 16 possible combinations of "doors" for any room, so the number and directions the doors lead in can be represented by a number from zero to 15. Simply stuff the data for the room into an array, and use a simple equation to navigate the "world" using X-Y coordinates.

With that in mind, all one needs to create a two dimensional world that can be fully navigated, is a matrix to store information in and a formula to navigate the matrix.

Here is how it works...

Consider a single room with doors in all four compass directions: North, South, East, and West. For our map, a door to the North has a numeric value of "1", a door to the south has a value of "2", East is "4", and West equals "8". So, if bit 1 of the byte is set, there is a door to the North, if bit 2 is set , there is a door to the south, and bit 3 sets the door to the east, and bit four sets the door to the west. A value of zero results on no door, and all other values are undefined.

For example, a room with only doors facing east and west will havie a value of 12 (4+8=12). A room with doors to the north and east will have a value of five (1+4=5).

Notice that we are only using 4 bits to store room information, and that the actual array in the program is declared as integer. On most (all ?) 32-bit systems, this means that 28 bits of the double word we have stored for each room is not used for anything. One could easily use the remaing 3 1/2 bytes to store information about room contents and game conditions. These things are not implimented here, but are left up to you to decide on. In the original C-64 version I added booby traps and hungry lions to maul and devour those who strayed from the correct path through the maze . Have fun... be creative and gnarly in your imagination.

Mapping the world...

I constructed the world as a single dimensional array of integer preloaded with values determined from a hand drawn map that I had laid out on a sheet of graph paper.

The map data of the world looked like this (all values are in decimal notation);

 Here is what a drawn map of the maze , with the correct path through it in red, looks like....

 

 Notice that there is only one path through the maze, and that each room can be entered and exited.

Dealing with reality... 

Real -world considerations force us to modify our ideal model a bit before we can actually make it work in a program.

First of all, we need to start our navigation and end it from outside of the maze. This means that two extra rows must be added to the map data. One at the top, and one at the bottom. So that we can start and finish outside of our tiny world and not wander into oblivion...

Also, if both the X , and Y coordinates become zero, our navigation equation tends to "blow up", and patching that kind of problem can be ugly. The simple solution is to pad the map data with zeroes to allow a world surrounded by rooms with no doors, so nobody can go there and blow up the navigation equation. Alternatively, the beginning of the map data can be padded with a single zero so that the map always is indexed to a nonzero result of the navagation equation. This eliminates the "one-off" problem for arrays that result from needing a nonzero result for an index.

Now , our map data looks like this:

Putting it all together..

The equation we need to navigate this map is: i=(Y*10)-X+10 Where i=the unique location of a room's data in a single-dimensional array. X= the X coordinate of the room, and Y= the Y coordinate of the room.

With all of that accomplished, we only need to actually write the program and we are ready to trek our little 2-d realm.

The program is simple, using an old-fashioned while loop to drive the engine. The logic is simple if-then statements, and room information is extracted from the array, by calculating the room 's location from X-Y coordinates and indexing the array with the results. Invalid states are trapped and the user's position and room status is displayed for each room.

The code was written on a PC running Windows NT Workstation, in ANSI C, using Borland C++ V 5.01. No os-dependant functions were used, so this code should compile and run on about any computer using an ANSI C compiler.

The original source for this program can be downloaded via anonymous FTP at: ftp://www.night-flyer.com/freeware/maze.c

PROGRAM BEGINS

/* A simple 100 room maze.   Written by Glen E. Gardner, Jr.  10-22-98 */
 
#include<stdio.h>
 
int main(void)
{
/* Store the map in a single-dimensiional array of integer */
int map[]={0,0,0,0,0,2,0,0,0,0,0,6,12,12,10,7,12,12,14,12,8,4,
12,8,3,3,6,8,3,4,8,5,12,12,9,7,10,4,9,6,8,3,2,6,12,12,13,8,2,
3,2,3,3,3,2,6,10,4,11,3,3,3,3,7,15,7,9,14,13,13,9,3,3,3,1,4,
12,14,14,12,10,3,3,7,12,12,10,3,3,6,9,5,11,3,2,6,9,3,1,9,2,
4,13,9,5,15,12,13,12,12,9,0,0,0,0,1,0,0,0,0,0};
 
/* Declare the needed variables */
int i,x,y;
int temp;
int loop=1;
int key;
int flag;
 
/* start the game with the player outside the entrance of the maze */
x=5;
y=11;
 
/* enter the game loop */
while(loop)
{
 
/* Set a sentinel on the game loop to record invalid moves */
flag=1;
 
/* get the location of the room data in the array */
i=10*y-x+10;
 
 
/* output the players position and current room info */
printf("%d %d          %d  %d\n",x,y,i,map[i]);
 
/* use boolean AND to see which doors are available */
temp=map[i];
if((temp&1)==1)printf("There is a door to the north.\n");
if((temp&2)==2)printf("There is a door to the south.\n");
if((temp&4)==4)printf("There is a door to the east.\n");
if((temp&8)==8)printf("There is a door to the west.\n");
 
/* get user input */
key=getc(stdin);
fflush(stdin);
if(key=='x')loop=0;
 
/* navagate the maze based on the key pressed and check for invalid moves */
if(key=='n')
	{
   temp=map[i];
   if((temp&1)==1)
   	{ 
   	flag=0;
   	y--;
      }
   }
 
if(key=='s')
	{
   temp=map[i];
   if((temp&2)==2)
   	{
   	flag=0;
   	y++;
      }
   }
 
if(key=='e')
	{
   temp=map[i];
   if((temp&4)==4)
   	{
   	flag=0;
   	x--;
      }
   if(x<1)x=1;
   }
 
if(key=='w')
	{
   temp=map[i];
   if((temp&8)==8)
      {
   	flag=0;
   	x++;
      }
   	if(x>10)x=10;
   }
 
/* advise the player of an invalid move. */
if(flag==1)
	{
   printf("You can't go in that direction.\n");
   }
}
return(0);
}
 
PROGRAM ENDS