TI-99/4A Hunt and Kill Maze Algorithm in Extended BASIC
Matthew Hagerty, Feb 2006 (http://digitalstratum.com)
This code is public domain.
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:
- Initialize all cells as unvisited.
- Pick a random starting location and mark the cell as visited.
- 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.
- 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.
Size of maze.
Origin on screen of upper-left corner of maze.
Current cell in the maze.
Next tentative "current cell".
Last valid "hunting" location (prevents starting the hunting process over from the beginning every time.)
Random direction. D1 is used to know when all 4 directions have been tried for a given cell.
Converts a direction into +/- values for X and Y.
Converts a direction into a bit value for given direction.
Inverse of DBIT for setting an initial value of a cell that is entered from a given direction.
Character to be displayed in a given cell.
Used to indicate if "hunting" must restart at 1, 1.
Cell Value Description
Out of bounds, will not exist in valid maze area.
Bitmap of open cell directions, see below:
Cell value bitmap:
128 64 32 16 8 4 2 1
Bit representation when set:
Cell open in the Top direction.
Cell open in the Right direction.
Cell open in the Bottom direction.
Cell open in the Left direction.
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,SYvariables, as well as set the
DIM MAZE()to the size plus 1. So, if
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.
I don't use
REMstatements 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
REMstatements 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.
Initialize the maze screen offset and starting hunt mode coordinate.
LINES 210 - 240
MAZEarray 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
IFstatements to find out what to add to
Yfor a given direction
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.
DINVis the inverse of
DBITfor 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.
Pick a random direction
D(1-4) and remember it in
D1so we know when we have tried all 4 directions for this cell.
RNDis a very expensive instruction, as is the multiplication.
Generate a new cell location (
LINES 430 - 440
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.
X,Yto the new cell and drop the wall for the direction in which we just entered the cell.
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
>=16are 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
RESETvariable.) 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
TI-99/4A Extended BASIC Source
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