From Matthew Probert · 1996-04-10 00:41 · #75270 in R25C
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 (*
--- WILDMAIL!/WC v4.12
* Origin: Ooh! BBS, London [MULTILINES] 0181-395-3108 (2:254/233.0)