Download the full set of files for this week's port at our SourceForge repository!!
Perhaps more than anything else, "Amazing" demonstrates for us the truly unpleasant evil of abused GOTO statements in our old BASIC language source. Decoding the design intent of the original author from the source is manifestly difficult because so many switches in logic are reflected only in jumps to line numbers, that lead to more jumps to more line numbers, and then jump back near the beginning, to still more line numbers - and in many cases, to execute blocks of freqently repeated code.
The unfortuante aspect of this "death by 1,000 GOTO's" is that a rather elegant algorithm for constructing this electronic maze is buried amid the GOTO's. I remember studying this program extensively when I first bought this book, finding myself fascinated at the way the program was described as one *guaranteeing* only one path through - yet never understanding why. These undescriptive variables and chained GOTO's were part of the reason why I couldn't quite keep it straight - to say nothing of the single-letter variable names that didn't seem to remotely reflect their purpose.
Amazingly simple
"Amazing" models a maze as a simple grid of "cells" in the height and width specified by the user (see Figure 1). Building the maze amounts to knocking out walls by carving paths through the maze.
A simple 5x5 maze grid
Carving out paths
To start, each cell in the grid has four walls - north, east, south, and west. To carve out a path through the maze, it follows a simple algorithm:
1. Place a "visitor" in the maze - initially this is the "start" location. Mark the cell as having been "visited."
2. The "visitor" moves randomly by one cell in any direction - up, down, left or right - subject to the following rules
a. The visitor cannot go beyond the natural boundaries of the maze.
b. The visitor cannot go to a cell that's already been visited.
3. Remove the wall between where the visitor was and where he now stands.
4. If all cells have been visited, the maze is complete.
5. Repeat the process at step 2 unless the visitor has hit a dead end per the movement rules.
6. Retart the process, re-starting the visitor at a cell already visited on a previous path.
Amazing tracks "visited" cells separately from the maze's "walls." While each cell has four physical walls, those walls become two logical walls in the program - east and south (Figure 2).
Figure 2 - Cell walls
Amazing - Javascript style
Let's start the source for our Javascript version. The visitor tracking variables R and S become currentColumn and currentRow, respectively; H and V become width and height. "C," holding the cell number, becomes cellCount, and a curious ping-pong of "Z" and "Q" used to control when and if the exit has been created are replaced with a simple boolen "exitPlaced" variable.
function Amazing(gameConsole){
var ref=this;
var width, height; // maps to W, H in original
var wVisited=[]; // maps to "w" array in original; will become 2d when initialized [][]
var vWalls=[]; // maps to "V" array in original
var cellCount=1;
var currentRow, currentColumn;
var QControl=0;
var console = gameConsole;
var ZControl=true; // ZControl indicates whether an exit on the bottom row has been defined
// This allows us to go "down" on the bottom row *one* time - to define an exit.
var exitPlaced = false;
var visitedCellList= [];
this.Play = function(){
console.writeLine("AMAZING PROGRAM");
console.writeLine("CREATIVE COMPUTING - MORRISTOWN, NEW JERSEY");
console.writeLine("Original program credit: Jack Hauber of Windsor, Connecticut");
console.writeLine("Javascript port: David Whitney, Oklahoma City, OK");
ref.GetDimensions();
}
How it works
Figure 3 illustrates the first two theoretical paths through a sample 5x5 maze. The yellow arrows represent a "first" path traversal, entering at the maze starting point (Start #1, picked randomly along the first row), followed by a path carving sequence of right-down-right-up before dead-ending. Each cell visited in the first path is slightly shaded to indicate it having been visited. Following the dead-end of the first path, the algorithm repeats by randomly selecting a new starting position (Start #2) for the visitor somewhere along a non dead-end cell from any previously constructed path, moving again in once-cell steps, stopping when a dead end is reached (End #2).
The process of tracing paths by always starting the visitor in a location previously visited means that we're already expanding a previously defined path. Continuing that strategy eventually will extend, as noted, to the bottom row, and an exit. The code allows such a choice - going "down" from a cell on the bottom row - one time. Once the "exit" has been defined, the perpetual extension of the remaining paths simply fill the rest of the maze until all cells have been visited. That's how the code guarantees a single exit path from start to finish.
What makes this simple algorithm so hard to "see" amid the original BASIC source is, in addition to the GOTO's, the repeated "chunks" of code that are really doing nothing more than bounds checking to determine which "chunk" of options are possible for the visitor at a given point. The original source wants to know ahead of time if it's going to generate a choice, for example, between left, up, or down (line 350), up, right, or down (line 580), and so on. Doing this, however, requires pieces of the bounds checking code to be repeated.
Rather than try to reproduce this kind of logic, I opted to redesign it. I wrapped the bounds checking code into four simply named routines - canMove{Up/Down/Left/Right}(). The visitor is then allowed to make a random choice from among any of the "available" directions. If no directions are available, the visitor is dead-ended, and must restart his journey on a new location (cell) from among those previously visited.
function canMoveLeft(){
if (currentColumn==0)
return false;
else
return (wVisited[currentColumn-1][currentRow]==0);
};
function canMoveRight(){
if (currentColumn==width-1)
return false;
else
return (wVisited[currentColumn+1][currentRow]==0);
};
function canMoveDown(){
if (currentRow==height-1){
if (exitPlaced){
QControl =1;
return false;
} else {
return true;
}
}
else
return (wVisited[currentColumn][currentRow+1]==0);
};
function canMoveUp(){
if (currentRow==0)
return false;
else
return (wVisited[currentColumn][currentRow-1]==0);
};
// Replaces BASIC source lines 820-850
function moveUp(){
wVisited[currentColumn][currentRow-1]=cellCount;
vWalls[currentColumn][currentRow-1]=1;
visitedCellList.push( {column: currentColumn, row: currentRow-1} );
currentRow--;
cellCount++;
}
// Replaces BASIC source lines 910-955
function moveDown(){
if (currentRow!=height-1){
//if (QControl==0){
wVisited[currentColumn][currentRow+1]=cellCount;
visitedCellList.push( {column: currentColumn, row: currentRow+1} );
cellCount++;
if (vWalls[currentColumn][currentRow]==0){
vWalls[currentColumn][currentRow]=1;
} else {
vWalls[currentColumn][currentRow]=3;
}
currentRow++;
} else {
ZControl = false; // exit found, can't go down on bottom row now
exitPlaced=true;
//console.write("Exit placed.");
if (vWalls[currentColumn][currentRow]==0){
vWalls[currentColumn][currentRow]=1;
currentRow=0;
currentColumn=0;
} else {
vWalls[currentColumn][currentRow]=3;
}
QControl=0;
}
}
// BASIC lines 860-905
function moveRight(){
wVisited[currentColumn+1][currentRow]=cellCount;
visitedCellList.push( {column: currentColumn+1, row: currentRow} );
cellCount++;
if (vWalls[currentColumn][currentRow]==0){
vWalls[currentColumn][currentRow]=2;
} else {
vWalls[currentColumn][currentRow]=3;
}
currentColumn++;
}
// BASIC lines 790-815
function moveLeft(){
wVisited[currentColumn-1][currentRow]=cellCount;
visitedCellList.push( {column: currentColumn-1, row: currentRow} );
cellCount++;
vWalls[currentColumn-1][currentRow]=2;
currentColumn--;
}
Another change in the program's design I opted to implement improves the efficiency of the maze computation in a couple of ways. The original source, upon dead-ending, always moved linearly in a left-to-right, top-to-bottom fashion looking for an unvisited cell, sometimes restarting in the upper left-hand corner. I think this tended to generate mazes that were more "open" near the top, with longer walls at or near the bottom. To fix this, I added a "visitedCellList" array that gets the coordinates of each cell as it is visited. When the visitor's starting position must be assigned, a unlocked cell from this list is chosen at random, distributing the starting positions more evenly:
function isLocked(column, row){
return (
(column==0 || (wVisited[column-1][row] > 0)) &&
(row==0 || (wVisited[column][row-1] > 0)) &&
(column==width-1 || (wVisited[column+1][row] > 0)) &&
(row==height-1 || (wVisited[column][row+1] > 0))
);
}
function findStartingLocation2(){
while ((wVisited[currentColumn][currentRow]==0) || isLocked(currentColumn,currentRow)){
var newLocationIndex = random(visitedCellList.length-1);
currentColumn = visitedCellList[newLocationIndex].column;
currentRow = visitedCellList[newLocationIndex].row;
}
};
The redesign of the start position selection and movement logic allowed the generation of the entire maze to be reduced into a single loop, with the outermost loop merely checking the current cell count, and the inner loop moving the visitor so long as he isn't deadlocked along the current path. When the cell count is reached, indicating all cells have been visited, the maze is complete. For each iteration, we create a list of valid possible directions (validDirections[]), then pick a random number from among that list:
function constructMazePaths(){
// starting at the currentColumn,currentRow, snake up/down/left/right until we
// run out of cells or can't go anywhere else; then find a new starting position
// and continue
while (cellCount<=width*height){
var validDirections = [];
findStartingLocation2();
var onCurrentPath = true;
while (onCurrentPath){
validDirections.length=0;
//var onCurrentPath = (canMoveUp() || canMoveRight() || canMoveDown() || canMoveLeft());
// Direction are mapped 1:Up, 2:Right,3:Down, 4:Left
// Push valid current possible directions into an array, then
// randomly select from among the valid possible values.
if (canMoveUp()){
validDirections.push(1);
}
if (canMoveRight()){
validDirections.push(2);
}
if (canMoveDown()){
validDirections.push(3);
}
if (canMoveLeft()){
validDirections.push(4);
}
//if validDirections is length=0, no valid values, we're locked.
onCurrentPath = (validDirections.length>0);
if (onCurrentPath){
direction = validDirections[random(validDirections.length)-1];
switch(direction){
case 1: moveUp();
break;
case 2: moveRight();
break;
case 3: moveDown();
break;
case 4: moveLeft();
break;
}
}
onCurrentPath = onCurrentPath && (cellCount<=width*height);
}
}
}
Rendering the maze is a simple matter of iterating through the wall matrix one row at a time, interrogating each cell to determine if an east and/or a south wall must be displayed. I preserved the original program logic for this, reserving vertical walls in one physical line, and horizontal walls on the next. This could could be condensed and allow for larger display mazes if it were reworked to use an underscore and a vertical bar (pipe) for the south and east walls.
function renderMaze(){
for (var j=0; j< height; j++){
console.write("I");
for (var i=0; i< width; i++){
if (vWalls[i][j]<2){
console.write(" I");
} else {
console.write(" ");
}
}
console.writeLine("");
for (var i=0; i< width; i++){
if ((vWalls[i][j]==0) || (vWalls[i][j]==2)) {
console.write(":--");
} else {
console.write(": ");
}
}
console.writeLine(".");
}
}
The input for Amazing wants two comma-separated integers, and this is where I discovered a bug in our ConsoleWindow class. The keydown handler did not properly map the keycode for a comma, returning 188 and causing a "1/4" symbol to be displayed. A tweak to map this code to 44, for an actual comma, fixed this issue. The maze dimensions are the only input to Amazing, hence our CommandDispatcher is fairly trivial. We also provide a simple command validator to ensure numeric input, and initialize the visitation and cell wall arrays. I also added a simple utility function to provide a little syntactic sugar to random number generation:
function CommandDispatcher(command){
setTimeout(ref.BuildMaze(command),250);
}
this.GetDimensions = function(){
console.writeLine("WHAT ARE YOUR WIDTH AND LENGTH?");
console.readLine(CommandDispatcher);
};
function validArguments(param){
var parms = param.split(",");
if (parms.length != 2){
return false;
}
width = parseInt(parms[0]);
height = parseInt(parms[1]);
return (!isNaN(width) || !isNaN(height))
}
function initArrays(){
for (i=0; i< width; i++){
wVisited[i]=[];
vWalls[i]=[];
for (j=0; j< height; j++){
wVisited[i][j]=0;
vWalls[i][j]=0;
}
}
};
function random(number){
return Math.floor(Math.random()*number)+1;
};
All that's left now is to wrap up these helper methods into the core routine that will take the input, carve the paths, and render the maze, and that's in the BuildMaze function off our Play() method:
this.BuildMaze = function(command){
if (!validArguments(command)){
console.writeLine("MEANINGLESS DIMENSIONS. TRY AGAIN.");
ref.GetDimensions();
return;
}
// valid width, height in (surprise) width, height;
initArrays();
startOpening = random(width);
QControl=0;
ZControl=0;
// maps lines 165-190 for top line of maze
for (var tc=1; tc<=width; tc++){
if (tc!=startOpening)
console.write(".--");
else
console.write(". ");
}
console.writeLine(".");
wVisited[startOpening-1][0] = cellCount;
cellCount++;
currentColumn=startOpening-1;
currentRow=0;
constructMazePaths();
renderMaze();
// now we start snaking through a path
};
This was a fun and rather challenging port, because it was less about the language differences than it was decoding a design strategy buried in a "maze" of BASIC code. Here's hoping you enjoyed reading through and playing with the project as much as I did!!
Grab the code and the updated ConsoleWindow from the SourceForge repository, and please feel free to leave comments below.
Until next week!
No comments:
Post a Comment