TI-99/4A Hunt and Kill Maze Algorithm in Extended BASIC
Matthew Hagerty, Feb 2006 (http://digitalstratum.com)
This code is public domain.

Win994a Simulator disk file: hkmaze.TIDisk

Screen Shot It took about 2 minutes to generate this 12x12 character maze. Kind of slow I know, but the Hunt and Kill algorithm is not the fastest, just more memory efficient than the standard recursive backtracker.

Hunt and Kill Algorithm Operational Description

This algorithm is very simple and creates a 2D, normal, orthoganol, perfect maze, which simply means it is rectangular, has no loops or inaccessable areas, all passages intersect at right angles, and all cells connect to every other cell (you can get from any point to any other point, thus the maze is 100% solvable.)

To generate a maze, do:

1. Initialize all cells as unvisited.
2. Pick a random starting location and mark the cell as visited.
3. Chose a random direction and move to the adjacent cell in that direction unless that cell has already been visited or that direction is a border, in which case repeat this step, unless all directions have been found invalid, in which case set the cell as complete and go to step 4.
4. Begin a sequential scan of the cells until one is found that has been visited but is not yet complete, go to step 3. If all cells have been scanned and found complete, the maze is done.

Variable Use

Variable	Description
SX,SY	Size of maze.
OX,OY	Origin on screen of upper-left corner of maze.
MAZE	Maze array.
X,Y	Current cell in the maze.
NX,NY	Next tentative "current cell".
HX,HY	Last valid "hunting" location (prevents starting the hunting process over from the beginning every time.)
D,D1	Random direction. D1 is used to know when all 4 directions have been tried for a given cell.
P	Converts a direction into +/- values for X and Y.
DBIT	Converts a direction into a bit value for given direction.
DINV	Inverse of DBIT for setting an initial value of a cell that is entered from a given direction.
C	Character to be displayed in a given cell.
RESET	Used to indicate if "hunting" must restart at 1, 1.
I,J	General loops.

Cell Value	Description
-1	Out of bounds, will not exist in valid maze area.
0	Unvisited cell.
>=1	Bitmap of open cell directions, see below:

Cell value bitmap:

128	64	32	16	8	4	2	1
0	0	0	C	L	B	R	T

Bit representation when set:

Bit	Description
T	Cell open in the Top direction.
R	Cell open in the Right direction.
B	Cell open in the Bottom direction.
L	Cell open in the Left direction.
C	Cell Complete.

Implementation Notes

TI BASIC and Extended BASIC are extremely slow (due to double interpretation) when compared to other BASIC dialects of the day, but in some cases it can actually help write better code because everything you do affects the speed.

The Hunt and Kill algorithm does not require a stack of visited cells to track progress through the generation, so it is more memory efficient than some other algorithms like depth-first or recursive backtracker; and being memory efficient on an older computer with limited resources is a good thing.

The maze array has a 1-cell border that is set to -1. Although this requires a marginal increase in memory to store the maze, it allows bounds checking to be skipped, which saves 16 comparisons per cell. This works because having the 1-cell border means that all "new" position possibilities are valid maze array coordinates and we only have to check if the cell is valid to move into (which has to be done anyway.)

There is also the ability to have non-rectangular mazes as well as blocked out areas with no additional overhead. Just initialize the desired masked areas as "complete" in the maze array before running the main loop. All blocked out areas must be filled in (marked as invalid), otherwise the maze will not complete!

In TI BASIC/Extended BASIC you cannot dimmension an array with a variable.

This is illegal:

100 X=10 :: Y=10
110 DIM MAZE(X,Y)

This means that the maze size has to be fixed and cannot be changed at runtime. So, if you want to make a larger maze, make sure you change the SX,SY variables, as well as set the DIM MAZE() to the size plus 1. So, if SX=10 and SY=15, then DIM MAZE(11,16). An alternative would be to just dimmension the maze array to the maximum (32x24 for a full screen), and simply use a portion of the array for smaller mazes.

Functional Description

I don't use REM statements because they: 1. use memory, and 2. slow down execution, hence the reason for this functional description. Being somewhat of a comment zealot, this is very difficult for me, but REM statements take up memory and cause the program to run slower.

LINES 100 - 160

Setup of the characters we will use for display. Not critical to maze generation.

LINE 200

Initialize the maze screen offset and starting hunt mode coordinate.

LINES 210 - 240

Dimmension the MAZE array and initialize the border.

LINES 250 - 270

Dimmension and initialize the direction-to-offset lookup table. What this does is saves us from having to use IF statements to find out what to add to X and Y for a given direction D.

LINES 280 - 290

Dimmension and initialize the direction-to-bitmap lookup table. Given a direction D, this table returns the bitmap position of the corresponding wall.

DINV is the inverse of DBIT for opening the wall of a new cell that we just moved into from a given direction.

Think of it like this. There are two walls between any two cells, and to move from one cell to another, both walls must be set to open. So if we are leaving a cell to the left (D=4), then we use DBIT(D) to open the wall in the cell we are leaving, and DINV(D) to open the wall of the cell we are moving into.

LINES 300 - 320

Draw the initial maze, all walls up.

LINES 400 - 410

Pick a random starting point and enter kill mode.

LINE 420

Pick a random direction D (1-4) and remember it in D1 so we know when we have tried all 4 directions for this cell. RND is a very expensive instruction, as is the multiplication.

LINES 430 - 440

Generate a new cell location (NX,NY) and see if it is okay to move there.

LINES 450 - 490

Drop the wall in the current cell for the direction in which we are leaving the cell. Then display the proper wall character for this cell.

LINE 500

Set X,Y to the new cell and drop the wall for the direction in which we just entered the cell.

LINE 510

Jump back to pick a new random direction in which to continue.

LINES 550 - 560

These lines are reached if the chosen random direction for the currnet cell is invalid. The direction is incremented by 1 and execution jumps back to test this new direction. If all directions have been tested for this cell and found to be invalid, the mode changes to hunt.

LINES 600 - 640

Begin hunt mode. Displays the proper character for the current cell and marks the cell as complete.

LINES 700 - 720

Set up the hunt loops. Hunting is a sequential scan over the maze, looking for a cell that has been visited but is not yet complete. Once the whole maze has been scanned in hunt mode and all cells are found to be complete, the maze is done.

LINES 730 - 740

Looking for a visited cell to being kill mode again. All cells that are either 0 or >=16 are unvisited or complete, and are skipped.

If an unvisited cell (value of 0) is found, the next time we enter hunting mode, we must begin at the beginning (indicated by the RESET variable.) However, if there are no unvisited cells up to the next cell to continue with, we can pick up hunting were we left off.

LINES 750 - 790

A valid cell was found, so set that as the current cell. The direction is set instead of chosen again at random since: 1. this cell already had a random direction chosen for it initially, and 2. chosing a random number is expensive and we want to avoid it if possible. This is why we jump back to the line just following the random direction generation.

LINES 800 - 820

Hunting loop iterators. If we picked up hunting where we had left off on a previous hunting loop, the hunting column (HX) must be reset back to 1, otherwise hunting would miss chunks of the maze if we hunt past the current line during this hunting iteration.

LINES 900 - 1000

Finished.

100 CALL CLEAR :: OPTION BASE 0 :: RANDOMIZE
110 CALL CHAR(96,"0000000000000000")
120 CALL CHAR(97,"0101010101010101")
130 CALL CHAR(98,"00000000000000FF")
140 CALL CHAR(99,"01010101010101FF")
150 CALL CHAR(100,"017D4545457D01FF")
160 CALL COLOR(9,2,11)

200 OX=10 :: OY=6 :: HX=1 :: HY=1

210 SX=12 :: SY=12
220 DIM MAZE(13,13)
230 FOR I=0 TO SX+1 :: MAZE(I,0)=-1 :: MAZE(I,SY+1)=-1 :: NEXT I
240 FOR I=1 TO SY :: MAZE(0,I)=-1 :: MAZE(SX+1,I)=-1 :: NEXT I

250 DIM P(4,2)
260 P(1,1)=0 :: P(1,2)=-1 :: P(2,1)=1 :: P(2,2)=0
270 P(3,1)=0 :: P(3,2)=1 :: P(4,1)=-1 :: P(4,2)=0
280 DIM DBIT(4) :: DBIT(1)=1 :: DBIT(2)=2 :: DBIT(3)=4 :: DBIT(4)=8
290 DIM DINV(4) :: DINV(1)=4 :: DINV(2)=8 :: DINV(3)=1 :: DINV(4)=2

300 FOR I=OY TO OY+SY-1
310 CALL HCHAR(I,OX,99,SX)
320 NEXT I

400 X=INT(RND*SX)+1 :: Y=INT(RND*SY)+1 :: IF MAZE(X,Y)<>0 THEN 400
410 DISPLAY AT(1,1):"KILL"

420 D=INT(RND*3)+1 :: D1=D

430 NX=X+P(D,1) :: NY=Y+P(D,2)
440 IF MAZE(NX,NY)<>0 THEN 550
450 MAZE(X,Y)=MAZE(X,Y) OR DBIT(D)
460 C=99
470 IF (MAZE(X,Y) AND 2)=2 THEN C=98
480 IF (MAZE(X,Y) AND 4)=4 THEN IF C=98 THEN C=96 ELSE C=97
490 CALL HCHAR(OY+Y-1,OX+X-1,C)

500 X=NX :: Y=NY :: MAZE(X,Y)=DINV(D)
510 GOTO 420

550 D=D+1 :: IF D>4 THEN D=1
560 IF D<>D1 THEN 430

600 C=99
610 IF (MAZE(X,Y) AND 2)=2 THEN C=98
620 IF (MAZE(X,Y) AND 4)=4 THEN IF C=98 THEN C=96 ELSE C=97
630 CALL HCHAR(OY+Y-1,OX+X-1,C)
640 MAZE(X,Y)=MAZE(X,Y) OR 16

700 RESET=0
710 FOR J=HY TO SY :: DISPLAY AT(1,1):"HUNT: ";J
720 FOR I=HX TO SX
730 IF MAZE(I,J)=0 THEN RESET=1 :: GOTO 800
740 IF MAZE(I,J)>=16 THEN 800

750 X=I :: Y=J
760 IF RESET=0 THEN HX=I :: HY=J ELSE HX=1 :: HY=1
770 DISPLAY AT(1,1):"KILL"
780 D=4 :: D1=4
790 GOTO 430

800 NEXT I
810 HX=1
820 NEXT J

900 DISPLAY AT(1,1):"DONE"
910 CALL KEY(0,K,S) :: IF S=0 THEN 910

1000 END