Dungeons and Dragons #1
=======================

Originally written in 1977 by Richard Garriott ("Lord English" of Ultima fame)
a challenge was posed to port this game to Javascript to run in a browser without
plugins.

The code was originally provided as a low-contrast scan in PDF format. OCR was
useless to try to read it, so I increased contrast first and tried again, but
to no avail... At best I had a character recognition rate around 50%.

A number of volunteers helped me manually type in the full listing. Correctness
checks were done by proof reading, automated line number checks (to ensure line
numbers were ordered) and by running a few duplicate pages through unix diff.

After a brief attempt to get the game to run in BWbasic, I decided to port it
from the tangled spaghetti code mess that is BASIC to a more structured language,
for which I chose to use C. The reasoning behind using C was that in terms of
required I/O it was a pretty good match with BASIC, and syntactically it was a 
lot closer to JavaScript while allowing me to focus on getting things to work.
I'd deal with getting things to work in a browser later.

I started out by writing a script to strip out unused line numbers, to make the
flow of the code clearer. I then proceeded to wrap code blocks into functions,
created a main loop for the program, and worked my way through the code until I 
had ported the whole thing.

I figured out that the missing data files could be generated with the rudimentary
dungeon editor that the original program provided, but thought it'd be much more
interesting to start out with a few generated mazes than to try to build dungeons
by hand, from scratch - so I wrote a maze generator in Perl. 
One interesting detail is that a generic maze algorithm will work best for an odd
number of rows and columns, while the game uses an even number; this did however
not pose serious issues.

When saving and loading games, I had some weird behaviour. Sure enough, it was 
because I had mistranslated something:

BASE 0
DIM C(7)

to

int C[7];

Although both zero based, they mean different things; DIM in BASIC specifies the upper
bound of the array, whilst the 7 in int C[7] specifies the number of elements in the 
array. Ah, the joy of C programming.

Once I could save and load games, I wanted to run some automated tests to ensure
that not too many crashes would occur. I wrote a perl script that simultaneously
opened STDIN and STDOUT and used both to send commands to the C program and intercept
the output. Since heavy string processing would be required, I chose Perl do do this.
I figured that opening both streams at the same time could be done with the 
syntactically obvious

	open (HANDLE,'|program|');

which would pipe both from and to the program. I was wrong; this didn't work.
Instead, I needed to use the Open2 module, which will return two file handles
instead.

Even then, output was being buffered and I realized that my C program needed
to flush all its buffers after every print statement.

To make that as painless as possible, I figured I'd replace all printf statements
in my C program to "uprintf" - "unbuffered printf" for which I could then define
a printf compatible function. This too was interesting as printf takes a variable
number of parameters, which is a technique I didn't fully master yet.

Once buffer flushing was sufficiently under control, I managed to run a number of
automated tests and got decent code coverage. Now all I needed to do was to get
this C program to run stand-alone as Javascript module in a browser.

A few months back I had heard of asm.js, which sounded promising as converting a
C program to JavaScript would be as simple as compiling C to JavaScript. I dug into 
clang, and soon I had compiled my C program to LLVM. I then used Empscripten to generate
a HTML page and JavaScript to run the program.

Full of expectation, I opened the page in a browser, but was rather disappointed. 
Although the program seemed to run, input was done by javascript "prompt" box which
obfuscated the printed output; there were output buffering issues, and occasionally
I was required to answer questions that hadn't appeared on screen yet, and the 
CPU pegged to 100%. Along with a rather hefty footprint of around a megabyte, I
concluded that perhaps console-style C isn't the most suitable candidate for an
emscripten conversion.

Soon, Chrome asked me if I wanted to kill the page. I said yes. 

He's dead, Jim!

Javascript won't let me SLEEP()
===============================
I put the project aside for a while before I decided to pick it up again. After all,
I already had a C version of the program - which was syntactically close to JavaScript,
so conversion from one to the other should be straightforward. Most importantly, I'd do
my own I/O handling, so I could mostly re-use my existing C code. The strategy was 
sound: I'd create a uprintf function for output an input(function) to wait for input.

The output function was soon ready and didn't face any major obstacles.

The input function would simply loop to check if there were any enter keys in the input
buffer, indicating the end of a line of user input. If detected, it would return the 
resulting buffer, and otherwise it would sleep for a tenth of a second and poll the 
input buffer again. The input buffer itself, of course, would be filled by the regular
keyboard handling of JavaScript. 

I envisioned that the input function would look something like this:

function input()
{
	inputbuffer="";
	while (1)
	{
		if (inputbuffer.strpos("\n")!=-1)
		{
			result=inputbuffer.substr(0,inputbuffer.length-1);
			return result;
		}
		sleep(.1);
	}
}

The rest of my code could then stay mostly the same.

How naive I was. The thing is, JavaScript doesn't have a sleep() statement.
Delays are possible, but only by writing CPU-hogging loops, through callbacks,
through plugins or external servers.
Plugins and external servers were out. CPU-hogging prevented the keyboard from 
being responsive. And callbacks... well, let's take a look at why callbacks 
aren't ideal.

Our structured C listing would typically interlace input and output in sort of
a dialogue. For example, take this simplified snippet of code:

void main()
{
	intro();
	uprintf("OLD OR NEW GAME");
	char* q=input();
	if (strcmp(q,"OLD")==0)
	{
		load_old_game();
	}
}

void intro()
{
        uprintf("     DUNGEONS AND DRAGONS #1\n");
        uprintf("\n");
        /* Added prompt Y/N here to enhance playability */
        uprintf("DO YOU NEED INSTUCTIONS (Y/N)\n");
        char* q=input();
        if (strncmp(q,"N",1)==0) return;
        /* INSTRUCTIONS */
        uprintf("WHO SAID YOU COULD PLAY\n");
        return;
}

Now let's see what happens if we try to translate this to a callback-based approach.
Instead of waiting for input with our ideal sleeping input function as described
before, we'll have input do a setTimeout instead.

Our library code would essentially be something like this:

function input(callback)
{
	setTimeout("wait_for_input(callback)",20);
}

function wait_for_input(callback)
{
	if (inputbuf.indexOf("\n")==-1)
	{
		// we must wait longer
		setTimeout("wait_for_input(callback)",20);
		return;
	}
	inputbuf=inputbuf.substsr(inputbuf.length-1);
	callback(myinputbuf);
}

Note - We could probably do a setInterval instead, but we'd have to keep a timeout 
handle to cancel it later on. Let's keep things simple.

Then here is our JavaScript code to use the input:

function main()
{
	intro();
	uprintf("OLD OR NEW GAME");
	input(
		function(inputbuf)
		{
			q=inputbuf;
			if (q=="OLD")
			{
				load_old_game();
			}
		}
	);
}

void intro()
{
        uprintf("     DUNGEONS AND DRAGONS #1\n");
        uprintf("\n");
        /* Added prompt Y/N here to enhance playability */
        uprintf("DO YOU NEED INSTUCTIONS (Y/N)\n");
	input(
		function(inputbuf)
		{
			q=inputbuf;
			if (q!="N")
			{
				/* INSTRUCTIONS */
				uprintf("WHO SAID YOU COULD PLAY");
			}
        		return;
		}
	);
}

At first sight, this looks fine. Unfortunately, it's wrong. The reason is that running
"input" doesn't make JavaScript wait - it merely queues an event, and as soon as the
event is queued, the code will continue execution.

In other words, before we've hit a key to reply to the input prompt,
what we'll see is...

     DUNGEONS AND DRAGONS #1

DO YOU NEED INSTUCTIONS (Y/N)?
OLD OR NEW GAME?

... and meanwhile the program races on. It might finish soon, but since input events 
are still queued, we might then provide the requisite input to which the program
might then respond, 

WHO SAID YOU COULD PLAY

The reason for this is that our "return" statement no longer returns to where we 
left off in the main() function - instead, it returns to the end of our wait_for_input
function, where our event was queued.

In contrast to should we have had a sleep function, from a structured programming point 
of view, a callback-based approach essentially breaks our call stack.

Let's see if we can fix this somehow. For starters, let's pretend we *do*
have a sleep-based, waiting input mechanism.

function three_inputs()
{
	for (i=1; i<=3; i++)
	{
		uprintf("WRITE SOMETHING: ");
		q=input();
		uprintf("YOU WROTE "+q+"\n");
	}
}

Three times in a row, this function will output

WRITE SOMETHING:

Then the function would wait for input, and finally output

YOU WROTE <whatever you wrote>

Finally, the function would terminate and return to its caller.

Now let's do a naive, callback-based version of the above function.
It will look as follows:
 
function three_inputs()
{
	for (i=1; i<=3; i++)
	{
		uprintf("WRITE SOMETHING: ");
		input(
			function(inputbuf)
			{
				q=inputbuf;
				uprintf("YOU WROTE "+q+"\n");
				return;
			}
		);
	}
}

There are a few problems with this.
For starters, this will immediately output

WRITE SOMETHING: WRITE SOMETHING: WRITE SOMETHING: 

and queue three input events. 
And we're lucky since we only queued a limited number of events; 
If the for loop were an infinite while loop instead, the code would
look as follows and soon crash:

function infinite_inputs()
{
	/* Crashes the browser */
	while (1)
	{
		uprintf("WRITE SOMETHING: ");
		input(
			function(inputbuf)
			{
				q=inputbuf;
				uprintf("YOU WROTE "+q+"\n");
				return;
			}
		);
	}
}

One way to fix this is to only queue an input event when the previous one has completed.
And what more reliable place to do that, than in the callback?

function infinite_inputs()
{
	uprintf("WRITE SOMETHING: ");
	input(
		function(inputbuf)
		{
			q=inputbuf;
			uprintf("YOU WROTE "+q+"\n");
			infinite_inputs();
		}
	);
}

Effectively, what we have here is an infinite loop. Although it looks like we're
recursively calling infinite_inputs(), this is not the case; the reason for this 
is that the input() function merely queues an event and returns immediately, 
but it is the event itself that causes the next event to be queued.

But we didn't want infinite inputs - we were trying to write function three_inputs().
Since we cannot initialize the counter from three_inputs() itself, we need to do that
task outside our function:

function call_three_inputs()
{
	i=1;
	three_inputs(i);
	
}

function three_inputs(i)
{
	uprintf("WRITE SOMETHING: ");
	input(
		function(inputbuf,i)
		{
			q=inputbuf;
			uprintf("YOU WROTE "+q+"\n");
			if (i<=3)
			{
				three_inputs(i+1);
			}
		}
	);
}

Do you spot the problem? We need to adapt our input library so that it can 
forward arbitrary arguments (in this case variable i) to the callback.
Each callback may have a different set of arguments, so that's no good.

VISIONS OF GOTO
===============

Instead of changing the library to pass arbitrary arguments to callback functions, 
it was clear we'd go a lot further by making variables global as needed.

var i;
function call_three_inputs()
{
	i=1;
	three_inputs();
}
function three_inputs()
{
	uprintf("WRITE SOMETHING: ");
	input(
		function(inputbuf)
		{
			q=inputbuf;
			uprintf("YOU WROTE "+q+"\n");
			i++;
			if (i<=3)
			{
				three_inputs();
			}
		}
	);
}

This helped, syntactically speaking, but we still couldn't call two different 
input functions after one another:

var i;
function call_inputs()
{
	i=1;
	three_inputs();
	i=1;
	four_inputs();
}

because the latter one will be run immediately after the first event is queued.
Instead, we'd have to write this as follows:

var i;
function call_three_inputs()
{
	i=1;
	three_inputs();
}
function three_inputs()
{
	uprintf("WRITE SOMETHING: ");
	input(
		function(inputbuf)
		{
			q=inputbuf;
			uprintf("YOU WROTE "+q+"\n");
			i++;
			if (i<=3)
			{
				three_inputs();
			} else {
				i=1;
				four_inputs();
			}
		}
	);
}
function four_inputs()
{
	....
}

...where the function "four_inputs" is simply the continuation of what we'd like to do
after three_inputs. It should be clear by now that insofar we initially had 
a structured piece of code, we won't be able to maintain that structure.

In fact, in terms of the structure that we're forced to follow, the above piece of 
code bears an eerie resemblance to this:

	LET I=1
CALL_THREE_INPUTS:
	GOTO THREE_INPUTS

THREE_INPUTS:
	PRINT "WRITE SOMETHING ";
	INPUT Q$
	PRINT "YOU WROTE ";Q$
	I=I+1
	IF I<=3 THEN THREE_INPUTS
	I=1
	GOTO FOUR_INPUTS
FOUR_INPUTS:
	...
	
Yes, you're seeing it right. In terms of program structure, callbacks force us to
- Use globals
- Queue events intended for sequential execution at the end of our code block
- And write generally unstructured code, just like in the old GOTO days.

Once I arrived at this point, it was clear to me that I wasn't going to port my C
program to JavaScript.

Instead, I'd convert the BASIC listing.        
Wouldn't setTimeout get too slow though? I solved that by using a zero timeout for
"GOTO" jumps and a longer timeout for input. Other than that - the program that I 
was porting was from 1977. Computers have become a little bit faster since. It 
was going to be Just Fine.

The only issue left was that the BASIC listing contained FOR loops. To make those
work in a callback-based setting and to prevent the event queue from being overloaded,
I'd have to replace those with initialization, increment, comparison and GOTO.
That's right - using GOTO instead of FOR loops was needed to actually make this work.

I interrupt this article to send a message to the developers of JavaScript.

>>>>
Hello, Javascript developers!! 

Please implement SLEEP. SetTimeout callbacks don't cut it; they are as bad as GOTO for
program structure and would therefore certainly have been considered harmful by the
late E. Dijkstra.

And please, don't come up with excuses that you can't make it work.
Javascript is event driven, and therefore sleeps, by definition. If you could implement
prompt() and XmlHTTPRequest, you can certainly implement sleep() just as well.

Thank you for your attention.
<<<<

Back to BASIC
=============

Having arrived at this point, I went back to the old BASIC listing since ironically
it was a better match for being ported to JavaScript than my much more structured C 
listing.

Since I expected there still to be a few bugs and untranslatables in the BASIC listing, 
I decided on the following translation strategy:

- Make a "next line" table to determine which line number would naturally 
  follow any block of instructions;
- Eliminate FOR loops in favour of init, increment, comparison and GOTO statement;
- Strip unused line numbers and convert the remaining ones to labels;
- Do the syntax conversion so the code would look (a lot more) like JavaScript;
- Postprocess incorrectly translated and untranslatable lines using a simple line-for-line
  replacement;
- Define a header with relevant functions and variable declarations.

This worked surprisingly well, and of the 1500 or so claimed lines of code (really 1300)
only 59 lines had to be provided manually. meaning pattern-based search and replace took
care of about 96% of the source.

The final straws
================
A few minor things were deemed untranslatable and had to be done manually.

READ and DATA were replaced by functions to simply fill arrays with content.

File functions were replaced by JavaScript localStorage.

GOSUB statements required a call stack, but since only one subroutine was being reused
(the HIT AND RANGE CHECK), I chose to use the previously written C function as replacement
for the BASIC code.

An HTML wrapper page was necessary. Rather than going for a teletype style interface,
we decided for a just slightly more modern green-on-black VT terminal style interface.
A nice green VT font was used.

Since each remaining GOTO line number was now converted into a function, to test if I 
had found all syntactical issues, I generated a script to call each function in turn.
This provided me with insights on a few remaining issues, which were soon resolved.

Maze generation - I used the dungeons generated by Perl and JS localStorage for any
changes to them.

Keyboard handling - turned out to be inconsistent across browsers. About an A4 sized
sheet of code took care of most of these differences. For kicks and giggles, I tried
the game on a mobile phone, only to realize that the on-screen keyboard didn't pop up.
A hidden input field was added to the HTML page to permit focusing on it to bring up
the on-screen keyboard, making the game playable on mobile phones.


Trivia:
=======
There are 6 dungeons in this Dungeons and Dragons game.
There are 10 different kinds of monster. None of them are dragons.

When fighting a monster bare handed, it helps to be near a door.

When fighting a monster by sword, a critical hit inflicts less damage
than a good hit.

In this game, daggers are throwing weapons rather than stabbing weapons 
- they have longer range than a sword and when you use them, you lose them.

Bugs:
=====
The game deals with 9 cleric spells, however only spells 1-8 can be bought.
--
When wizards choose spells, they're restricted to choosing spell 1..8 even
though they could buy spells 9 and 10.
--
Original code in cheat mode says "GOTO 10590" - which will buy wizard spell
Q. However, in cheat mode, Q is a player command, 10. Cheat mode appears to
be broken.
--
When fighting a monster by sword, a critical hit inflicts less damage
than a good hit.
-- 
There appears to be a bug in the original code when falling in a trap,
where you can never slip and fall back when having climbed halfway up the trap.