                    Maze Solving With Intelligence 

                            Matthew Probert 
                           Servile  Software 



Amaze is an artificial intelligence system for testing the solvability 
of mazes. It is also fun for children, and illustrates how "panicing" 
in a maze does not help you to find an exit any quicker! 

You can select the prefences given to the chosen directions of travel 
and test the maze with these to see which solves the maze fastest. 

Mazes may be drawn with any screen designer package but must conform 
to the following rules: 

1. The path must be defined by character 32 (space) All other 
   characters are impassable.

2. The path must start at row 0 and finish at row 24.


LOAD MAZE

Before the computer can solve a maze, it must have one in memory! You 
can load a maze from disk. Mazes are stored as binary screen images 
and can be created with any screen designer program, such as "The 
Draw" or with Amaze's built in editor. 


SELECT WEIGHTING

The weightings define the order of preference given to the tested 
directions of travel in the orders listed below. Notice, weighting 'x' 
is an internal algorithm only and cannot be selected at the keyboard. 

WEIGHTING     PREFERENCE

0             forward, left, right, backward
1             forward, right, left, backward
2             forward, backward, right, left
3             right, forward, backward, left
4             left, right, forward, backward
5             Choose from one of 0 to 4 at random before each step
6             As weighting 5, but every ten dead ends "panic", that is
              the computer forgets where it has previously been.
7             The computer will select a weighting (0 to 4 or x) where 
              the highest preference is given to the last direction it 
              was travelling in.
8             If the exit is to the left; left forward, back, right
              if the exit is to the right; right, forward, backward, left
              otherwise; forward, left, right, backward
x             (internal only) Backwards, left, right, forward



Weighting 7 thus declares: Select at random an initial weighting 
between 0 and 4. At each step select a weighting bewteen 0 and 4 or 
select weighting x so that the direction we moved in this time will be 
the direction we try first at the next. 

SOLVE MAZE

The computer will tackle the maze and hopefully solve it! After 
solving or giving up the status line will reflect the time taken to 
solve the maze in seconds and the weighting used. 


DRAW NEW MAZE

Allows you to draw a new maze. You start off with a fully blocked 
screen. Onto this you should trace a path from the top to the bottom. 

The cursor can be moved with the arrow keys. Press the space bar to 
toggle the cell at the cursor from a clear path to a block and back 
again. 

Holding down the left shift key while pressing the arrow keys leaves a 
path behind the cursor. 

Holding down the right shift key while pressing the arrow keys leaves 
blocks behind the cursor. 

Press ESC to finish. You will then be prompted for a name to save the 
maze as. If you don't want to save it, press return and answer Y to 
the prompt about aborting the save. 

If the file name chosen is already in use, you will be asked if you 
want to overwrite the old file with the new maze. If you answer 
anything other than Y you will be asked to enter a new file name. 

In any event the drawn maze will replace the one currently in memory. 

EDIT MAZE

Allows you to change the currently loaded maze. See "DRAW NEW MAZE" 

QUIT

Returns you to DOS

AMAZE! Was written by Matthew Probert, published by Servile Software.
       Copyright (c)1994,1996 Servile Software

       Servile Software
       5 Longcroft Close
       Basingstoke
       Hampshire
       RG21 8XG
       England
       Telephone 01256 478576


Source listing for Amaze Version 2.1 follows:

-----------------------------Cut Here-----------------------------
/*
	Solving a maze with intelligence

	Written by Matthew Probert
	(c)1994,1996 Servile Software
*/

#include <stdio.h>
#include <ctype.h>
#include <bios.h>
#include <io.h>
#include <fcntl.h>
#include <dos.h>
#include <string.h>
#include <mem.h>
#include <conio.h>
#include <time.h>
#include <stdlib.h>
#include <sys\stat.h>

unsigned char MAZE[4000];

unsigned char MMENU[] =
{
   "\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07"
   "\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07"
   "\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07"
   "\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07"
   "\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07"
   "\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07"
   "\x07\x07\x07 \x07S\x07""e\x07r\x07v\x07i\x07l\x07""e\x07 \x07S"
   "\x07o\x07""f\x07t\x07w\x07""a\x07r\x07""e\x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   "M\x07""A\x07Z\x07""E\x07 \x07S\x07Y\x07S\x07T\x07""E\x07M\x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07""C\x07o\x07p\x07y\x07r\x07i\x07g\x07h\x07t\x07 \x07(\x07""c"
   "\x07)\x07""1\x07""9\x07""9\x07""4\x07 \x07\x07\x07\x07\x07\x07"
   "\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07"
   "\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07"
   "\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07"
   "\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07"
   "\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07"
   "\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07\x07\x07\x07\x07\x07\x07"
   "\x07\x07\x07\x07O\x07P\x07T\x07I\x07O\x07N\x07S\x07\x07\x07"
   "\x07\x07\x07\x07\x07\x07\x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07\x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07\x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07\x07 \x07"
   " \x07[\x07""1\x07]\x07 \x07L\x07o\x07""a\x07""d\x07 \x07M\x07""a\x07"
   "z\x07""e\x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07\x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07\x07 \x07 \x07[\x07""2\x07]\x07 \x07S\x07""e\x07l\x07""e\x07"
   "c\x07t\x07 \x07W\x07""e\x07i\x07g\x07h\x07t\x07i\x07n\x07g\x07 \x07"
   " \x07\x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07\x07 \x07 \x07[\x07""3\x07]\x07 \x07S\x07o\x07"
   "l\x07v\x07""e\x07 \x07M\x07""a\x07z\x07""e\x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07\x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07\x07 \x07 \x07[\x07""4\x07]\x07"
   " \x07""D\x07r\x07""a\x07w\x07 \x07N\x07""e\x07w\x07 \x07M\x07""a\x07"
   "z\x07""e\x07 \x07 \x07 \x07 \x07 \x07\x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07\x07 \x07 \x07"
   "[\x07""5\x07]\x07 \x07""E\x07""d\x07i\x07t\x07 \x07M\x07""a\x07z\x07"
   "e\x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07\x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   "\x07 \x07 \x07[\x07""6\x07]\x07 \x07M\x07""a\x07n\x07u\x07""a\x07"
   "l\x07 \x07S\x07o\x07l\x07v\x07""e\x07 \x07 \x07 \x07 \x07 \x07 \x07"
   "\x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07\x07 \x07 \x07[\x07""7\x07]\x07 \x07Q\x07u\x07i\x07"
   "t\x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07\x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07\x07\x07\x07\x07\x07\x07\x07\x07"
   "\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07"
   "\x07\x07\x07\x07\x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07\x07\x07S\x07t\x07""a\x07t\x07u\x07s\x07\x07\x07"
   "\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07"
   "\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07"
   "\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07"
   "\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07"
   "\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07"
   "\x07\x07\x07\x07\x07\x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07 \x07"
   " \x07 \x07 \x07 \x07 \x07 \x07\x07\x07\x07\x07\x07\x07\x07"
   "\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07"
   "\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07"
   "\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07"
   "\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07"
   "\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07\x07"
   "\x07\x07\x07\x07\x07\x07\x07\x07\x07"
};

typedef struct
{
	int left;
	int right;
	int forward;
	int backward;
}
BRANCH;

BRANCH tree[2000];


unsigned vram;
unsigned far *video_port;
char far *video;
int weighting;


void cursor(int , int );
void DESIGN(int);
void print(char *);
int LOOK_BD(int , int );
int LOOK_FD(int , int );
int LOOK_LT(int , int );
int LOOK_RT(int , int );
int MANUAL(void);
void MENU(void);
void NO_CURSOR(void);
void RESET_TREE(void);
void SHOW_CURSOR(void);
int SOLVE(int);

void main()
{
	randomize();

	NO_CURSOR();

	/*
		Determine type of video card, mono or colour
	*/
	video_port = MK_FP(0x40,0x63);

	if (*video_port == 0x3B4)
		video = MK_FP(0xB000,0);
	else
		video = MK_FP(0xB800,0);

	weighting = 0;

	MENU();
	clrscr();
	SHOW_CURSOR();

	printf("Thanks for using Amaze!");
	printf("\n\nAn artificial intelligence application brought to you by Servile Software\n");
}


void RESET_TREE()
{
	/*
		Reset tree, effectively 'forget' what the simulation knows about
		a maze
	*/
	int n;
	for (n = 0; n < 2000; n++)
	{
		tree[n].forward = 0;
		tree[n].backward = 0;
		tree[n].left = 0;
		tree[n].right = 0;
	}
}

int SOLVE(int rw)
{
	int x;
	int ex;
	int y;
	int pos;
	int dead_end;
	int pc;
	int give_up;
	int ow;

	give_up = 0;
	y = 0;
	pc = 0;
	ow = weighting;

	/*
		Find maze entrance on top line
	*/
	for(x = 0; x < 80; x++)
	{
		pos = y * 80 + x;
		if (video[y * 160 + x * 2] == 32)
			break;
	}
	if (rw == 4)
	{
		/*
			Find maze exit on bottom line
		*/
		for(ex = 0; ex < 80; ex++)
		{
			if (video[24 * 160 + ex * 2] == 32)
				break;
		}
	}

	if (weighting == 7)
		weighting = random(5);

	dead_end = 0;

	while(y < 24 && !dead_end)
	{
		video[y * 160 + x * 2] = 32;

		/* Determine possible routes */
		if (y == 0)
			tree[pos].backward = -1;
		else
		if (video[(y-1) * 160 + x * 2] != 32)
			tree[pos].backward = -1;
		else
		if (LOOK_BD(x,y))
			tree[pos].backward = -1;

		if (video[(y+1) * 160 + x * 2] != 32)
			tree[pos].forward = -1;
		else
		if (LOOK_FD(x,y))
			tree[pos].forward = -1;


		if (video[y * 160 + (x - 1) * 2] != 32)
			tree[pos].left = -1;
		else
		if (LOOK_LT(x,y))
			tree[pos].left = -1;

		if (video[y * 160 + (x + 1) * 2] != 32)
			tree[pos].right = -1;
		else
		if (LOOK_RT(x,y))
			tree[pos].right = -1;

		dead_end = 1;

		if (rw > 0 && rw < 2)
			weighting = random(5);
		else
		if (rw == 4)
		{
			/* Emphasise left/right movement toward exit */

			if (x > ex)
				weighting = 6;
			else
			if (x < ex)
				weighting = 3;
			else
				weighting = 0;
		}

		if (weighting == 0)
		{
			if (tree[pos].forward == 0 && tree[pos+80].backward != pos )
			{
				y++;
				tree[pos].forward = y * 80 + x;
				dead_end = 0;
				if (rw == 3)
					weighting = 0;
			}
			else
			if (tree[pos].left == 0 && tree[pos-1].right != pos)
			{
				x--;
				tree[pos].left = y * 80 + x;
				dead_end = 0;
				if (rw == 3)
					weighting = 4;
			}
			else
			if (tree[pos].right == 0 && tree[pos+1].left != pos)
			{
				x++;
				tree[pos].right = y * 80 + x;
				dead_end = 0;
				if (rw == 3)
					weighting = 3;
			}
			else
			if (tree[pos].backward == 0 && tree[pos-80].forward != pos)
			{
				y--;
				tree[pos].backward = y * 80 + x;
				dead_end = 0;
				if (rw == 3)
					weighting = 5;
			}
			pos = y * 80 + x;
		}
		else
		if (weighting == 1)
		{
			if (tree[pos].forward == 0 && tree[pos+80].backward != pos )
			{
				y++;
				tree[pos].forward = y * 80 + x;
				dead_end = 0;
				if (rw == 3)
					weighting = 0;
			}
			else
			if (tree[pos].right == 0 && tree[pos+1].left != pos)
			{
				x++;
				tree[pos].right = y * 80 + x;
				dead_end = 0;
				if (rw == 3)
					weighting = 3;
			}
			else
			if (tree[pos].left == 0 && tree[pos-1].right != pos)
			{
				x--;
				tree[pos].left = y * 80 + x;
				dead_end = 0;
				if (rw == 3)
					weighting = 4;
			}
			else
			if (tree[pos].backward == 0 && tree[pos-80].forward != pos)
			{
				y--;
				tree[pos].backward = y * 80 + x;
				dead_end = 0;
				if (rw == 3)
					weighting = 5;
			}
			pos = y * 80 + x;
		}
		else
		if (weighting == 2)
		{
			if (tree[pos].forward == 0 && tree[pos+80].backward != pos )
			{
				y++;
				tree[pos].forward = y * 80 + x;
				dead_end = 0;
				if (rw == 3)
					weighting = 0;
			}
			else
			if (tree[pos].backward == 0 && tree[pos-80].forward != pos)
			{
				y--;
				tree[pos].backward = y * 80 + x;
				dead_end = 0;
				if (rw == 3)
					weighting = 5;
			}
			else
			if (tree[pos].right == 0 && tree[pos+1].left != pos)
			{
				x++;
				tree[pos].right = y * 80 + x;
				dead_end = 0;
				if (rw == 3)
					weighting = 3;
			}
			else
			if (tree[pos].left == 0 && tree[pos-1].right != pos)
			{
				x--;
				tree[pos].left = y * 80 + x;
				dead_end = 0;
				if (rw == 3)
					weighting = 4;
			}
			pos = y * 80 + x;
		}
		else
		if (weighting == 3)
		{
			if (tree[pos].right == 0 && tree[pos+1].left != pos)
			{
				x++;
				tree[pos].right = y * 80 + x;
				dead_end = 0;
				if (rw == 3)
					weighting = 3;
			}
			else
			if (tree[pos].forward == 0 && tree[pos+80].backward != pos )
			{
				y++;
				tree[pos].forward = y * 80 + x;
				dead_end = 0;
				if (rw == 3)
					weighting = 0;
			}
			else
			if (tree[pos].backward == 0 && tree[pos-80].forward != pos)
			{
				y--;
				tree[pos].backward = y * 80 + x;
				dead_end = 0;
				if (rw == 3)
					weighting = 5;
			}
			else
			if (tree[pos].left == 0 && tree[pos-1].right != pos)
			{
				x--;
				tree[pos].left = y * 80 + x;
				dead_end = 0;
				if (rw == 3)
					weighting = 4;
			}
			pos = y * 80 + x;
		}
		else
		if (weighting == 4)
		{
			if (tree[pos].left == 0 && tree[pos-1].right != pos)
			{
				x--;
				tree[pos].left = y * 80 + x;
				dead_end = 0;
				if (rw == 3)
					weighting = 4;
			}
			else
			if (tree[pos].right == 0 && tree[pos+1].left != pos)
			{
				x++;
				tree[pos].right = y * 80 + x;
				dead_end = 0;
				if (rw == 3)
					weighting = 3;
			}
			else
			if (tree[pos].forward == 0 && tree[pos+80].backward != pos )
			{
				y++;
				tree[pos].forward = y * 80 + x;
				dead_end = 0;
				if (rw == 3)
					weighting = 0;
			}
			else
			if (tree[pos].backward == 0 && tree[pos-80].forward != pos)
			{
				y--;
				tree[pos].backward = y * 80 + x;
				dead_end = 0;
				if (rw == 3)
					weighting = 5;
			}
			pos = y * 80 + x;
		}
		else
		if (weighting == 5)
		{
			if (tree[pos].backward == 0 && tree[pos-80].forward != pos)
			{
				y--;
				tree[pos].backward = y * 80 + x;
				dead_end = 0;
				if (rw == 3)
					weighting = 5;
			}
			else
			if (tree[pos].left == 0 && tree[pos-1].right != pos)
			{
				x--;
				tree[pos].left = y * 80 + x;
				dead_end = 0;
				if (rw == 3)
					weighting = 4;
			}
			else
			if (tree[pos].right == 0 && tree[pos+1].left != pos)
			{
				x++;
				tree[pos].right = y * 80 + x;
				dead_end = 0;
				if (rw == 3)
					weighting = 3;
			}
			else
			if (tree[pos].forward == 0 && tree[pos+80].backward != pos )
			{
				y++;
				tree[pos].forward = y * 80 + x;
				dead_end = 0;
				if (rw == 3)
					weighting = 0;
			}
			pos = y * 80 + x;
		}
		else
		if (weighting == 6)
		{
			if (tree[pos].left == 0 && tree[pos-1].right != pos)
			{
				x--;
				tree[pos].left = y * 80 + x;
				dead_end = 0;
				if (rw == 3)
					weighting = 4;
			}
			else
			if (tree[pos].forward == 0 && tree[pos+80].backward != pos )
			{
				y++;
				tree[pos].forward = y * 80 + x;
				dead_end = 0;
				if (rw == 3)
					weighting = 0;
			}
			else
			if (tree[pos].backward == 0 && tree[pos-80].forward != pos)
			{
				y--;
				tree[pos].backward = y * 80 + x;
				dead_end = 0;
				if (rw == 3)
					weighting = 5;
			}
			else
			if (tree[pos].right == 0 && tree[pos+1].left != pos)
			{
				x++;
				tree[pos].right = y * 80 + x;
				dead_end = 0;
				if (rw == 3)
					weighting = 3;
			}
			pos = y * 80 + x;
		}

		if (dead_end)
		{
			/* Increment panic counter */
			pc++;

			/* Need to backtrack */
			/* First try backwards */
			if (tree[pos - 80].forward == pos && y > 1)
			{
				/* Move back */
				y--;
				pos -= 80;
				/* Prevent retracing of this direction */
				tree[pos].forward = -1;
				dead_end = 0;
			}
			else
			/* try forwards */
			if (tree[pos + 80].backward == pos)
			{
				/* Move forward */
				y++;
				pos += 80;
				/* Prevent retracing of this direction */
				tree[pos].backward = -1;
				dead_end = 0;
			}
			else
			/* try left */
			if (tree[pos - 1].right == pos)
			{
				/* Move left */
				x--;
				pos--;
				/* Prevent retracing of this direction */
				tree[pos].right = -1;
				dead_end = 0;
			}
			else
			/* try right */
			if (tree[pos + 1].left == pos)
			{
				/* Move right */
				x++;
				pos++;
				/* Prevent retracing of this direction */
				tree[pos].left = -1;
				dead_end = 0;
			}
		}

		video[y * 160 + x * 2] = 1;
		video[y * 160 + x * 2 + 1] = 7;
		delay(150);

		if (rw == 2 && pc > 10)
		{
			/* Simulate a panic! */
			pc = 0;
			RESET_TREE();
		}
		if (dead_end)
		{
			RESET_TREE();
			rw = 0;
			give_up++;
			weighting++;
			if (weighting > 6)
				weighting = 0;
			if (give_up < 6)
				dead_end = 0;
		}
	}

	weighting = ow;

	if (rw)
		weighting = 4 + rw;
	if (dead_end)
		return -1;
	else
		return 0;
}

void MENU()
{
	/* Main menu of facilities */
	int n;
	char name[80];
	struct time start;
	struct time finish;
	int secs;

	secs = 0;
	while(1)
	{
		/* Display options */

		_fmemcpy(&video[0],&MMENU[0],4000);

		if (secs == -1)
		{
			cursor(23,2);
			printf("Couldn't solve the maze");
		}
		else
		if (secs > 0)
		{
			cursor(23,2);
			if (weighting == -1)
				printf("You took %d seconds to solve the maze",secs);
			else
				printf("Maze solved in %d seconds (weighting == %d)",secs,weighting);
		}

		n = getch() - '0';
		switch(n)
		{
			case 1 : do
					 {
						 secs = 0;
						 _fmemcpy(&video[0],&MMENU[0],4000);
						 cursor(23,2);
						 printf("FILE: ");
						 /*
							This is a simple way to get console input
						 */
						 fgets(name,60,stdin);
						 /*
							Lose trailing CR
						 */
						 name[strlen(name)-1] = 0;
						 if (*name)
						 {
							 n = _open(name,O_RDWR);
							 if (n < 0)
							 {
								_fmemcpy(&video[0],&MMENU[0],4000);
								cursor(23,2);
								printf("File Not Found!");
								sound(300);
								delay(500);
								nosound();
								delay(1000);
								_fmemcpy(&video[0],&MMENU[0],4000);
								cursor(23,2);
							 }
							 else
							 {
								_read(n,&MAZE,4000);
								if (*video_port == 0x3B4)
								{
									/* Set image attribute to light grey on black */
									for(n = 1; n < 4000; n += 2)
										MAZE[n] = 7;
								}
								close(n);
							 }
						 }
						 else
							n = 1;
					 }
					 while(n < 1);
					 break;

			case 2:	secs = 0;
					_fmemcpy(&video[0],&MMENU[0],4000);
					cursor(23,2);
					printf("Select weighting (0, 1, 2, 3, 4, 5, 6, 7 or 8)");
					do
					{
						weighting = getch() - '0';
					}
					while(weighting < 0 || weighting > 8);
					break;

			case 3: if (MAZE[0] == 0)
					{
						cursor(23,2);
						printf("No maze is loaded!                                                       ");
						sound(300);
						delay(500);
						nosound();
						delay(1000);
						cursor(23,2);
						printf("                                                                         ");
					}
					else
					{
						for(n = 0; n < 4000; n++)
							video[n] = MAZE[n];
						RESET_TREE();
						gettime(&start);
						if (weighting > 4)
							secs = SOLVE(weighting - 4);
						else
							secs = SOLVE(0);
						gettime(&finish);
						if (secs == 0)
						{
							secs = finish.ti_hour * 3600 + finish.ti_min * 60 + finish.ti_sec;
							secs -= (start.ti_hour * 3600 + start.ti_min * 60 + start.ti_sec);
						}
					}
					break;

			case 4: DESIGN(1);
					break;

			case 5: DESIGN(0);
					break;

			case 6: if (MAZE[0] == 0)
					{
						cursor(23,2);
						printf("No maze is loaded!                                                       ");
						sound(300);
						delay(500);
						nosound();
						delay(1000);
						cursor(23,2);
						printf("                                                                         ");
					}
					else
					{
						for(n = 0; n < 4000; n++)
							video[n] = MAZE[n];
						gettime(&start);
						if (!MANUAL())
						{
							gettime(&finish);
							secs = finish.ti_hour * 3600 + finish.ti_min * 60 + finish.ti_sec;
							secs -= (start.ti_hour * 3600 + start.ti_min * 60 + start.ti_sec);
							weighting = -1;
						}
						else
							secs = -1;
					}
					break;

			case 7: return;
		}
	}
}

void cursor(int y, int x)
{
	union REGS rg;

	rg.x.ax = 0x0200;
	rg.x.bx = 0;
	rg.x.dx = ((y << 8) & 0xff00) + x;
	int86(16,&rg,&rg);
}

void curr_cursor(int *y, int *x)
{
	union REGS rg;

	rg.x.ax = 0x0300;
	rg.x.bx = 0;
	int86(16,&rg,&rg);
	*x = rg.h.dl;
	*y = rg.h.dh;
}

void NO_CURSOR()
{
	union REGS rg;

	rg.x.ax = 0x0100;
	rg.x.cx = 0x2000;
	int86(16,&rg,&rg);
}

void SHOW_CURSOR()
{
	union REGS rg;

	rg.x.ax = 0x0100;
	rg.x.cx = 0x0607;
	int86(16,&rg,&rg);
}


void print(char *str)
{
	/*
	Prints characters only directly to the current display page
	starting at the current cursor position. The cursor is not
	advanced.
	*/

	int offset;
	int row;
	int col;
	char far *ptr;

	curr_cursor(&row,&col);

	offset = row * 160 + col * 2;

	ptr = MK_FP(vram,offset);

	while(*str)
	{
		*ptr++= *str++;
		ptr++;
	}
}

void DESIGN(int clear)
{
	/* Design your own maze */
	int n;
	int x;
	int y;
	int key;
	int mod;
	char name[80];

	if (clear)
	{
		for(n = 0; n < 4000; n+= 2)
		{
			MAZE[n] = 176;
			MAZE[n + 1] = 7;
		}
	}

	/* Display the maze */
	for(n = 0; n < 4000; n++)
		video[n] = MAZE[n];

	SHOW_CURSOR();

	x = 0;
	y = 0;

	do
	{
		/* Space will toggle bit at cursor */
		/* Arrow keys move */
		/* Left shift leads path, right shift blocks path */

		cursor(y,x);
		key = bioskey(0);
		mod = bioskey(2);

		if ((mod & 1) == 1)
		{
			MAZE[y * 160 + x * 2] = 176;
			_fmemcpy(&video[0],&MAZE[0],4000);
		}
		else
		if ((mod & 2) == 2)
		{
			MAZE[y * 160 + x * 2] = 32;
			_fmemcpy(&video[0],&MAZE[0],4000);
		}

		switch(key)
		{
			case 19200: if (x > 0)
							x--;
						break;
			case 19712: if (x < 79)
							x++;
						break;
			case 18432: if (y > 0)
							y--;
						break;
			case 20480: if (y < 24)
							y++;
						break;
			case 14624: if (MAZE[y * 160 + x * 2] == 32)
							MAZE[y * 160 + x * 2] = 176;
						else
							MAZE[y * 160 + x * 2] = 32;
						_fmemcpy(&video[0],&MAZE[0],4000);
						break;

		}
	}
	while(key != 283);
	NO_CURSOR();

	x = 0;
	do
	{
		_fmemcpy(&video[0],&MMENU[0],4000);

		cursor(23,2);
		printf("SAVE AS: ");
		fgets(name,60,stdin);
		name[strlen(name)-1] = 0;
		if (*name)
		{
			n = _open(name,O_RDWR);
			if (n > 0)
			{
				_fmemcpy(&video[0],&MMENU[0],4000);
				cursor(23,2);
				printf("File already exists. Overwrite? (y/N)");
				key = toupper(getch());
				if (key == 'Y')
				{
					close(n);
					n = _open(name,O_RDWR|O_CREAT);
					chmod(name,S_IWRITE);
					x = 1;
				}
			}
			else
			{
				n = open(name,O_BINARY|O_RDWR|O_CREAT,S_IWRITE);
				if (n > 0)
					x = 1;
				else
				{
					_fmemcpy(&video[0],&MMENU[0],4000);
					cursor(23,2);
					perror("ERROR: Can't create file!");
					sound(300);
					delay(500);
					nosound();
					delay(2000);
				}
			}
		}
		else
		{
			_fmemcpy(&video[0],&MMENU[0],4000);
			cursor(23,2);
			printf("Abort save? (y/N)");
			key = toupper(getch());
			if (key == 'Y')
			{
				x = 1;
				n = 0;
			}
		}
	}
	while(!x);
	if(n > 0)
	{
		_write(n,&MAZE,4000);
		close(n);
	}
	/*
		Empty keyboard buffer of any stray key strokes!
	*/
	while(bioskey(1))
		bioskey(0);
}

int MANUAL()
{
	int x;
	int y;
	int key;
	int vpos;
	int left;
	int right;
	int backward;
	int forward;

	y = 0;

	/* Find maze entrance on top line */
	for(x = 0; x < 80; x++)
	{
		if (video[y * 160 + x * 2] == 32)
			break;
	}

	while(y < 24)
	{
		/* Show position */
		vpos = y * 160 + x * 2;
		video[vpos] = 1;

		left = right = forward = backward = 0;

		/* Determine possible routes */
		if (y == 0)
			backward = -1;
		else
		if (video[vpos - 160] != 32)
			backward = -1;

		if (video[vpos + 160] != 32)
			forward = -1;

		if (video[vpos - 2] != 32)
			left = -1;

		if (video[vpos + 2] != 32)
			right = -1;


		key = bioskey(0);
		switch(key)
		{
			case 283:   /* Give up */
						return 1;


			case 19200: if (x > 0 && left != -1)
						{
							video[vpos] = 32;
							x--;
						}
						break;
			case 19712: if (x < 79 && right != -1)
						{
							video[vpos] = 32;
							x++;
						}
						break;
			case 18432: if (y > 0 && backward != -1)
						{
							video[vpos] = 32;
							y--;
						}
						break;
			case 20480: if (y < 25 && forward != -1)
						{
							video[vpos] = 32;
							y++;
						}
						break;

		}
	}
	return 0;
}

int LOOK_FD(int x, int y)
{
	int exits;

	do
	{
		y++;
		if (y > 24)
			return 0;

		exits = 0;

		if (video[(y+1) * 160 + x * 2] == 32)
			exits++;

		if (video[y * 160 + (x - 1) * 2] == 32)
			return 0;

		if (video[y * 160 + (x + 1) * 2] == 32)
			return 0;
	}
	while(exits == 1);
	return 1;
}

int LOOK_BD(int x, int y)
{
	int exits;

	do
	{
		y--;
		exits = 0;

		if (video[(y-1) * 160 + x * 2] == 32)
			exits++;

		if (video[y * 160 + (x - 1) * 2] == 32)
			return 0;

		if (video[y * 160 + (x + 1) * 2] == 32)
			return 0;
	}
	while(exits == 1);
	return 1;
}

int LOOK_RT(int x, int y)
{
	int exits;
	do
	{
		x++;
		exits = 0;

		if (video[y * 160 + (x + 1) * 2] == 32)
			exits++;

		if (video[(y - 1) * 160 + x * 2] == 32)
			return 0;

		if (video[(y + 1) * 160 + x * 2] == 32)
			return 0;
	}
	while(exits == 1);
	return 1;
}

int LOOK_LT(int x, int y)
{
	int exits;

	do
	{
		x--;
		exits = 0;

		if (video[y * 160 + (x - 1) * 2] == 32)
			exits++;

		if (video[(y - 1) * 160 + x * 2] == 32)
			return 0;

		if (video[(y + 1) * 160 + x * 2] == 32)
			return 0;
	}
	while(exits == 1);
	return 1;
}
-----------------------------Cut Here-----------------------------

