Machine Problem 2: Labyrinth

In this MP, you will write a program that generates a maze randomly with size specified by the user. The program then finds all shortest paths from the starting position to the goal. If no path exists, the program reports this to the user.

Reading: Lab Notes -- Libraries (Chapter 9), Mixing Assembly and C (Section 8.2), 16-bit C Programming (Section 8.3), Arrays (Section 7.1).

Screen Dump

Below is a screenshot of an example run of the program. You can see three stages of the maze solution process: after generation at the top, after distance-marking in the middle, and after finding solutions on the bottom.

Program Specification

The program begins by asking the user what size maze to generate. Mazes are squares and can be from 4 to 20 blocks across. Each block is stored as a 16-bit word in the 2-D array maze. The blocks are stored in row-major order meaning that adjacent words in memory are located in the same row of the maze. The value of each word describes the corresponding block in the maze as follows:

EMPTY	0FFFDh	Block is empty and has not been entered
WALL	0FFFEh	Block represents a wall in the maze that cannot be crossed
SOLUTION	0FFFFh	Block has been identified as part of a shortest solution to the maze
Other	0 - 0FFFCh	This value is the minimum distance from this block back to the starting point

The three constants in bold are defined by EQU's at the top of mp2.asm so you can and should use these mnemonics rather than the hex values. There are two other notable features of the maze, the start and goal, which are not stored in the maze array. Rather, four variables, startX, startY, goalX, and goalY store the coordinates of the these two locations. Several examples below should help clarify what data is stored in the array at different points during execution.

Generating the maze involves initializing maze with WALL values around the edges of the maze and EMPTY values in the middle. Exactly one quarter of these EMPTY values are replaced with walls by writing WALL values to positions chosen at random throughout the maze. If you choose a random location and find that a wall already exists there, you must pick another location so that you still end up with the correct number of walls. After placing the walls, choose two more random locations as the start and goal positions whose coordinates are to be kept in the variables startX, startY, goalX, and goalY for future use. At this point, the maze might look something like this:

Solving the maze is a two step process. The first step is to recursively determine the distances to every reachable position in the maze with SolveMaze. When calling SolveMaze, you provide a position to start from and the number of steps that have already been taken. For example, to begin the solution process you would pass in (startX, startY) and zero steps.

The body of SolveMaze first checks the passed location in the maze. The corresponding value in maze must be one of the following:

1) EMPTY	, in which case we have not visited this location before, or
2) < #steps passed	, in which case we have found a shorter solution to this location.

If neither of these are true, the subroutine returns. Otherwise it writes into maze the number of steps passed and recursively calls itself on the four adjacent blocks in the maze. This will continue until all reachable positions have been marked with their minimum distances. Furthermore, the recursion must stop at this point because neither of the above conditions can be satisfied.

After SolveMaze runs we can tell whether or not a solution exists; if the value at goalX, goalY is something other than EMPTY, it must be the minimum number of steps required to that location, i.e., to solve the maze. If no solution exists notify the user. If a solution does exist, the maze from the above example would now look something like this:

maze array					->	Representation on screen
WALL	WALL	WALL	WALL	WALL	->	####	####	####	####	####
WALL	0004h	WALL	0000h	WALL	->	####	04	####	[SS]	####
WALL	0003h	0002h	0001h	WALL	->	####	[GG]	02	01	####
WALL	0004h	0003h	WALL	WALL	->	####	04	03	####	####
WALL	WALL	WALL	WALL	WALL	->	####	####	####	####	####

If a solution does exist, then the second step in solving the maze is to mark the solution by calling MarkSolutions which operates somewhat like SolveMaze did. This time however, you begin by calling MarkSolutions on the goal

MarkSolutions first marks the passed location as SOLUTION. Then it looks at its four neighbors and calls itself recursively on those neighbors that are one step closer to the start symbol (their distance is one less). Once the start symbol is reached (distance is zero) no further recursive calls are allowed. When MarkSolutions finally returns, all possible shortest solutions to the original maze have been marked with the SOLUTION value. In this final state, the maze we've been looking at should look like this:

There are a couple points in the program at which you should display the maze and they correspond to the three examples shown above. You should display the maze immediately after generating the maze, after marking the minimum distances, and, if a solution exists, after the solutions have been marked.

Final consideration: The subroutines in this MP are to be written to accept arguments according to C-style conventions. For details, please see Sections 8.2 and 8.3 of the lab manual, but the basic gist of it is that arguments to a function are written to the stack by the calling function prior to the call. The called function returns its value in AL, AX, or DX:AX, depending on the size of the return value, and then it is up to the calling routine to take the arguments it passed back off the stack. As an example, the random number generator, Rand, that we provide you in this MP uses C calling conventions so you would call it like this to get a random number from 0 to AX-1:

  push ax
  call Rand
  add sp, 2	

Program Organization

The program has the following global variables:

Four functions are given to you, Main, Randomize, Rand, and DisplayMaze. Main, as in previous MPs, controls the flow of the program and is where execution begins. Randomize seeds the random number generator based on the system time in order to get a new number sequence each execution; it is called once near the start of procedure Main which is the only time it needs to be called; you will not need to call it in the functions you write. After Randomize has been called, calling Rand will return a random number in AX. Finally, Display draws the maze according to the state of the maze array. This is another function that is called in Main and should not need to be called elsewhere in the program.

It's up to you to replace the library versions of UserIn and the other procedures though. This is done by deleting the statements that call the libmp2 subroutine and by adding your own code. Each subroutine that you write should match the output of the library subroutine exactly. If you like, you are free to modify or re-implement DisplayMaze to display the maze in a different way but it should still be readable and it should still convey the same information (walls vs empty spaces, start and goal positions, distances, etc.).

Below is a detailed description of all the functions you are responsible for writing. Document each subroutine with a header. In the Lab Notes, standards for headers appear on page 4, and examples of subroutines on pages 28-33 and 84-88.

Friendly Advice

• The libmp2.lib file contains executable library subroutines for each of the routines that you need to implement. The library subroutines enable you to run the program and understand how it works before you implement it. You can test your program with any combination of your own code and library subroutines. You will receive credit only for the subroutines that you implement yourself.
• You may define new memory variables as needed. Variables associated with a subroutine may be declared between the header and the first instruction of the subroutine.
• Each subroutine should save and restore any registers that it uses, except for registers that deliver subroutine outputs. The caller may use registers without outputs and expect them to remain unchanged.
• Be careful when transmitting subroutine outputs via registers. For example, if you use POPA at the end of a subroutine, avoid overwriting a register that delivers an output.
• Likewise, be careful when dealing with arguments passed on the stack that you keep track of where on the stack they are. An argument that was at [SP + 4] when your function began will not still be at that location after you PUSHA. For functions that have arguments passed on the stack it's a good idea to copy the stack pointer, SP, into BP when you enter the function since BP won't change as you push and pop other variables.
• The maze array is an array of words. This is because the more complex maze generation algorithm originally planned could have resulted in a 20x20 maze where the distance from start to goal could have caused overflow problems. But as a consequence, when indexing the array you will need to double all your offsets. I.e., maze[y][x] is found at address maze + 2 * (y * mazeSize + x).
• Remember that it will cause problems in FindSpace if you place walls by generating X and Y coordinates separately.
• Monitor the course WebBoard for clarifications and help.
• START EARLY!

Files for MP2 are on the V: drive in the directory V:\ece390\mp2. In this directory are the program framework mp2.asm and a running version of the program mp2lab.exe. Lab versions of subroutines are in libmp2.lib, which contains all subroutines of LIB291 plus versions of the MP2 subroutines (libMain for Main, etc). You will use mp2xit instead of dosxit. You should start by copying these files to your home directory with the following command:
xcopy /s V:\ece390\mp2 W:\mp2
You may download the files from the server as mp2.zip

Demonstration, Documentation, and Grading

Demonstrate your program to an ECE 390 staff member.

As in MP1, keep an MP development log and write a cover memo, which should address the following questions:

• How much time did you spend on each subroutine, from planning and design through final debugging?
• What kinds of defects (bugs) did you find during the development of the program? When did you discover these defects (during code review or during testing)? How did you find them?
• What did you learn about design, coding, testing, and debugging in this MP?
• What went well in your work on this MP? What did not?
• What you would do differently for the next MP?

After the demonstration, submit your program and cover memo. Your program will be graded according to the clarity of your design and the quality of your documentation.

Gradesheet:

• UserIn: 10
• FindSpace: 10
• GenerateMazeOuter: 10
• GenerateMazeInner: 5
• SolveMaze: 15
• MarkSolutions: 10
• Technique: 3
• Documentation: 3
• Cover Memo: 4

mp2.asm (program framework)

; MP2 - Labyrinth
;       Your Name
;       Today's Date

       BITS    16

;====== SECTION 1: Define constants =======================================

       CR        EQU  0Dh
       LF        EQU  0Ah
       ESC       EQU  1Bh
       BS        EQU  08h

       MAXSIZE   EQU  20
       EMPTY     EQU  0FFFDh
       WALL      EQU  0FFFEh
       SOLUTION  EQU  0FFFFh

; You may define additional constants here

;====== SECTION 2: Declare external procedures ============================

;from the 291 library
EXTERN  kbdin, dspout, dspmsg, ascbin, dosxit

GLOBAL Main, Randomize, Rand, DisplayMaze
EXTERN libUserIn, libFindSpace, libGenerateMazeOuter, libGenerateMazeInner
GLOBAL FindSpace, GenerateMazeOuter, GenerateMazeInner, SolveMaze, MarkSolutions
EXTERN libSolveMaze, libMarkSolutions, mp2xit
GLOBAL maze, mazeSize, blocks, startX, startY, goalX, goalY
GLOBAL inputBuffer, startSymbol, goalSymbol, emptySymbol, wallSymbol
GLOBAL solutionSymbol, nullMsg, newline

;====== SECTION 3: Define stack segment ===================================

SEGMENT stkseg STACK                    ; *** STACK SEGMENT ***
        RESB      64*8
stacktop:
        RESB    0                       ; NASM bug workaround

;====== SECTION 4: Define code segment ====================================

SEGMENT code                            ; *** CODE SEGMENT ***

;====== SECTION 5: Declare variables for main procedure ===================
maze        RESW  MAXSIZE*MAXSIZE
mazeSize    DB  MAXSIZE
blocks      DB  MAXSIZE*MAXSIZE/4

startX      DB  0
startY      DB  0
goalX       DB  0
goalY       DB  0

inputBuffer RESB 3
R           DW  1

startSymbol DB  '[SS]','$'
goalSymbol      DB  '[GG]','$'
emptySymbol DB  '    ','$'
wallSymbol  DB  '####','$'
solutionSymbol DB '....','$'
nullMsg     DB  '$'
newline     DB  CR,LF,'$'
original    DB  CR,LF,'Original Maze:',CR,LF,'$'
distances   DB  CR,LF,'Calculated Distances:',CR,LF,'$'
shortpaths  DB  CR,LF,'Shortest Paths to Goal:',CR,LF,'$'
noSolution  DB  CR,LF,'No Solution for this Maze :(',CR,LF,'$'



;====== You can create your own variables here ============================


;====== SECTION 6: Program initialization =================================

..start:
       mov  AX, CS                  ; Initialize Default Segment register
       mov  DS, AX
       mov  AX, stkseg              ; Initialize Stack Segment register
       mov  SS, AX
       mov  SP, stacktop            ; Initialize Stack Pointer register

;====== SECTION 7: Main procedure =========================================

Main:

       call Randomize
       call UserIn
       call GenerateMazeOuter
       call GenerateMazeInner

       mov  dx, original
       call dspmsg
       call DisplayMaze
       call kbdin

       push word 0
       movzx ax, [startY]
       push ax
       movzx ax, [startX]
       push ax
       call SolveMaze
       add  sp, 6
       ; SolveMaze(startX, startY, 0)

       mov  dx, distances
       call dspmsg
       call DisplayMaze
       call kbdin

       movzx ax, [goalY]
       movzx bx, [mazeSize]
       mul  bx
       movzx bx, [goalX]
       add  bx, ax
       shl  bx, 1
       cmp  word [maze + bx], EMPTY
       jne  .solution
       ; if maze[goalX][goalY] == EMPTY, no solution

.noSolution
       mov  dx, noSolution
       call dspmsg
       jmp  .done

.solution
       movzx ax, [goalY]
       push ax
       movzx ax, [goalX]
       push ax
       call MarkSolutions
       add  sp, 4
       ; MarkSolutions(goalX, goalY)

       mov  dx, shortpaths
       call dspmsg

.done
       call DisplayMaze
       call mp2xit
       ret

;       VOID Randomize()
;       PURPOSE: Seeds the random number generator based on the current time
;       INPUTS:  (IO) Current time
;       OUTPUTS: (Global) R: The current random number
;       CONVENTION: Procedure
Randomize:
       push ax
       push dx

       mov  ah, 2Ch
       int  21h
       mov  word [R], dx
       ; Use interrupt to request time.  DH = seconds, DL = hundredths

       pop  dx
       pop  ax
       ret

;       WORD Rand(WORD maxNumber)
;       PURPOSE: Generates random number
;       INPUTS:  (stack) maxNumber: range of random number
;                (global) R: current stored random number
;       OUTPUTS: (AX): random number in range 0 ... (maxNumber-1)
;       CONVENTION: C-style
Rand:
       push bp
       mov  bp, sp

       push dx
       push bx

       mov  ax, word [R]
       mov  bx, 2153
       mul  bx
       add  ax, 13849
       mov  word [R], ax
       mov  dx, 0
       div  word [BP + 4]
       mov  ax, dx

       pop  bx
       pop  dx
       pop  bp
       ret

;       VOID DisplayMaze()
;       PURPOSE: Draws the maze using symbols for EMPTY, WALL, start point, etc
;            Reachable squares have their distance printed instead of EMPTY
;       INPUTS:  (Global) mazeSize
;          (Global) maze
;          (Global) startX, startY, goalX, goalY
;       OUTPUTS: (IO) Maze written to screen
;       CONVENTION: Procedure
DisplayMaze:
       pusha

       mov  ch, 0
.outerLoop
       mov  cl, 0
.innerLoop

       cmp  cl, [startX]
       jne  .notStart
       cmp  ch, [startY]
       jne  .notStart
       mov  dx, startSymbol
       jmp  .innerLoopEnd

.notStart
       cmp  cl, [goalX]
       jne  .notGoal
       cmp  ch, [goalY]
       jne  .notGoal
       mov  dx, goalSymbol
       jmp  .innerLoopEnd

.notGoal
       mov  al, [mazeSize]
       mul  ch
       movzx bx, cl
       add  bx, ax
       sal  bx, 1
       mov  ax, [maze + bx]
       ; bx = 2 * (x + mazeSize * y), ax = maze[x][y]

       cmp  ax, EMPTY
       jne  .notEmpty
       mov  dx, emptySymbol
       jmp  .innerLoopEnd

.notEmpty
       cmp  ax, WALL
       jne  .notWall
       mov  dx, wallSymbol
       jmp  .innerLoopEnd

.notWall
       cmp  ax, SOLUTION
       jne  .notSolution
       mov  dx, solutionSymbol
       jmp  .innerLoopEnd

.notSolution
       mov  dl, ' '
       call dspout
       mov  dl, 10
       div  dl
       add  al, 30h
       mov  dl, al
       call dspout
       add  ah, 30h
       mov  dl, ah
       call dspout
       mov  dl, ' '
       call dspout
       ; convert ax (the distance) to 2 digit ascii number

       mov  dx, nullMsg
       ; don't display anything at the dspmsg below

.innerLoopEnd
       call dspmsg
       inc  cl
       cmp  cl, [mazeSize]
       jne  .innerLoop

       cmp  byte [mazeSize], MAXSIZE
       je   .outerLoopEnd
       ; if mazeSize == 20, the text will automatically wrap, otherwise add CR/LF

       mov  dx, newline
       call dspmsg

.outerLoopEnd
       inc  ch
       cmp  ch, [mazeSize]
       jne  .outerLoop

       popa
       ret


; Your code will start here.


UserIn:

    call    libUserIn

    ret


FindSpace:

    call    libFindSpace

    ret


GenerateMazeOuter:

    call    libGenerateMazeOuter

    ret


GenerateMazeInner:

    call    libGenerateMazeInner

    ret


SolveMaze:
    push bp
    mov  bp, sp

    push word [bp + 8]
    push word [bp + 6]
    push word [bp + 4]
    call libSolveMaze
    add  sp, 6

    pop  bp
    ret


MarkSolutions:
    push bp
    mov  bp, sp

    push word [bp + 6]
    push word [bp + 4]
    call libMarkSolutions
    add  sp, 4

    pop  bp
    ret

Makefile

MPNAME=mp2

all: $(MPNAME).exe

clean: 
    rm -f $(MPNAME).exe $(MPNAME).obj $(MPNAME).lst $(MPNAME).map

%.exe: %.obj
    tlink /c /v $<, $*.exe, $*.map, lib291.lib libmp2.lib

%.obj: %.asm
    nasm -g -f obj -o $*.obj $< -l $*.lst