proj5_2.asm

ART OF Assembly Language Programming, 很不错

; Project #2, Chapter five
;
; AMAZE.ASM
;
; A maze generation/solution program.
;
; This program generates an 80x25 maze and directly draws the maze on the
; video display.
;
; You need to supply some code to access the 80x25 cells of the maze on the
; video display.  For full details on how this program works, see the chapter
; on processes in the textbook.  Warning! This program is relatively complex.
; Don't try to understand how it works if you're working on this after
; just reading chapter five
;
; When this program runs it will generate a maze and then pause until you
; print a key.  Then it will solve the maze and stop on the next keypress.
;
; This version will only work on a color display.




cseg		segment	para public 'code'
		assume	cs:cseg, ds:dseg


; MazeAdrs computes the index into the maze array.
; Maze is a 27x82 array of words (maze:array[0..26,0..81] of word).
; The following procedure needs to compute the index into this array
; and return that index in the AX register.  On input, dx contains
; the X coordinate (0..81) and cx contains the Y coordinate (0..26).
; Each element of the array is a word.
;

MazeAdrs	textequ	<call DoMazeAdrs>

DoMazeAdrs	proc
		push	bx
		push	cx
		push	dx

		mov	cl, dh
		mov	dh, 0
		mov	ch, 0
		xchg	cx, dx

; Do your computations here:
	


; Complete your computations by this point.

		pop	dx
		pop	cx
		pop	bx
		ret
DoMazeAdrs	endp


; The following procedure needs to be just like the code above
; except the matrix it computes the index for is a 25x80 matrix,
; not a 27x82 matrix.  Once again, the X coordinate (0..79) is in
; CX and the Y coordinate (0..24) is in DX.  Use row major ordering.
; You may use the AX, BX, CX, and DX registers.  Return the index
; in the AX register.

ScrnAdrs	textequ	<call DoScrnAdrs>

DoScrnAdrs	proc
		push	bx
		push	cx
		push	dx

		mov	cl, dh
		mov	ch, 0
		mov	dh, 0
		dec	dx
		dec	cx
		xchg	cx, dx


; Do your computations here.


; Complete your computations by this point.

		pop	dx
		pop	cx
		pop	bx
		ret
DoScrnAdrs	endp



cseg		ends




; ***** Don't mess with anything beyond this point !!! ********






		.xlist
		include 	stdlib.a
		includelib	stdlib.lib
		.list

byp		textequ	<byte ptr>

dseg		segment	para public 'data'

; Constants:
;
; Define the "ToScreen" symbol (to any value) if the maze is 80x25 and you
; want to display it on the video screen.

ToScreen	equ	0


; Maximum X and Y coordinates for the maze (matching the display).

MaxXCoord	equ	80
MaxYCoord	equ	25

; Useful X,Y constants:

WordsPerRow	=	MaxXCoord+2
BytesPerRow	=	WordsPerRow*2

StartX		equ	1		;Starting X coordinate for maze
StartY		equ	3		;Starting Y coordinate for maze
EndX		equ	MaxXCoord	;Ending X coordinate for maze
EndY		equ	MaxYCoord-1	;Ending Y coordinate for maze

EndLoc		=	( (EndY-1)*MaxXCoord + EndX-1)*2
StartLoc	=	( (StartY-1)*MaxXCoord + StartX-1)*2

; Special 16-bit PC character codes for the screen for symbols drawn during
; maze generation.  See the chapter on the video display for details.

		ifdef	mono		;Mono display adapter.

WallChar	equ	7dbh		;Solid block character
NoWallChar	equ	720h		;space
VisitChar	equ	72eh		;Period
PathChar	equ	72ah		;Asterisk

		else			;Color display adapter.

WallChar	equ	1dbh		;Solid block character
NoWallChar	equ	0edbh		;space
VisitChar	equ	0bdbh		;Period
PathChar	equ	4e2ah		;Asterisk

		endif




; The following are the constants that may appear in the Maze array:

Wall		=	0
NoWall		=	1
Visited		=	2

; The following are the directions the demons can go in the maze

North		=	0
South		=	1
East		=	2
West		=	3


; Some important variables:


; The Maze array must contain an extra row and column around the
; outside edges for our algorithm to work properly.

Maze		word	(MaxYCoord+2) dup ((MaxXCoord+2) dup (Wall))



; PCB for the main program.  The last live demon will call this guy when
; it dies.

MainPCB		pcb	{}


; List of up to 32 demons.

MaxDemons	=	32			;Must be a power of two.
ModDemons	=	MaxDemons-1		;Mask for MOD computation.

DemonList	pcb	MaxDemons dup ({})

DemonIndex	byte	0			;Index into demon list.
DemonCnt	byte	0			;Number of demons in list.


; Random number generator seed (we'll use our random number generator
; rather than the standard library's because we want to be able to specify
; an initial seed value).

Seed		word	0

dseg		ends



; The following is the segment address of the video display, change this
; from 0B800h to 0B000h if you have a monochrome display rather than a
; color display.

ScreenSeg	segment	at 0b800h
Screen		equ	this word	;Don't generate in date here!
ScreenSeg	ends


cseg		segment	para public 'code'
		assume	cs:cseg, ds:dseg

; Totally bogus random number generator, but we don't need a really
; great one for this program.  This code uses its own random number
; generator rather than the one in the Standard Library so we can
; allow the user to use a fixed seed to produce the same maze (with
; the same seed) or different mazes (by choosing different seeds).

RandNum		proc	near
		push	cx
		mov	cl, byte ptr Seed
		and	cl, 7
		add	cl, 4
		mov	ax, Seed
		xor	ax, 55aah
		rol	ax, cl
		xor	ax, Seed
		inc	ax
		mov	Seed, ax
		pop	cx
		ret
RandNum		endp

; Init-	Handles all the initialization chores for the main program.
;	In particular, it initializes the coroutine package, gets a
;	random number seed from the user, and initializes the video display.

Init		proc	near
		print
		byte	"Enter a small integer for a random number seed:",0
		getsm
		atoi
		free
		mov	Seed, ax

; Fill the interior of the maze with wall characters, fill the outside
; two rows and columns with nowall values.  This will prevent the demons
; from wandering outside the maze.


; Fill the first row with Visited values.

		cld
		mov	cx, WordsPerRow
		lesi	Maze
		mov	ax, Visited
	rep	stosw

; Fill the last row with NoWall values.

		mov	cx, WordsPerRow
		lea	di, Maze+(MaxYCoord+1)*BytesPerRow
	rep	stosw

; Write a NoWall value to the starting position:

		mov	Maze+(StartY*WordsPerRow+StartX)*2, NoWall


; Write NoWall values along the two vertical edges of the maze.

		lesi	Maze
		mov	cx, MaxYCoord+1
EdgesLoop:	mov	es:[di], ax			;Plug the left edge.
		mov	es:[di+BytesPerRow-2], ax	;Plug the right edge.
		add	di, BytesPerRow
		loop	EdgesLoop


		ifdef	ToScreen

; Okay, fill the screen with WallChar values:

		lesi	Screen
		mov	ax, WallChar
		mov	cx, 2000
	rep	stosw

; Write appropriate characters to the starting and ending locations:

		mov	word ptr es:Screen+EndLoc, PathChar
		mov	word ptr es:Screen+StartLoc, NoWallChar

		endif	;ToScreen


; Zero out the DemonList:

		mov	cx, (size pcb)*MaxDemons
		lea	di, DemonList
		mov	ax, dseg
		mov	es, ax
		xor	ax, ax
	rep	stosb

		ret
Init		endp



; CanStart- This function checks around the current position
; to see if the maze generator can start digging a new tunnel
; in a direction perpendicular to the current tunnel.  You can
; only start a new tunnel if there are wall characters for at
; least two positions in the desired direction:
;
;			##
;		       *##
;			##
;
; If "*" is current position and "#" represent wall characters
; and the current direction is north or south, then it is okay
; for the maze generator to start a new path in the east dir-
; ection.  Assuming "." represents a tunnel, you cannot start
; a new tunnel in the east direction if any of the following
; patterns occur:
;
;		.#	#.	##	##	##	##
;	       *##     *##     *.#     *#.     *##     *##
;		##	##	##	##	.#	#.
;
; CanStart returns true (carry set) if we can start a new tunnel off the
; path being dug by the current demon.
;
; On entry, 	dl is demon's X-Coordinate
;               dh is demon's Y-Coordinate
;		cl is demon's direction

CanStart	proc	near
		push	ax
		push	bx

		MazeAdrs		;Compute index to demon(x,y) in maze.
		mov	bx, ax

; CL contains the current direction, 0=north, 1=south, 2=east, 3=west.
; Note that we can test bit #1 for north/south (0) or east/west (1).

		test	cl, 10b		;See if north/south or east/west
		jz	NorthSouth

; If the demon is going in an east or west direction, we can start a new
; tunnel if there are six wall blocks just above or below the current demon.
; Note: We are checking if all values in these six blocks are Wall values.
; This code depends on the fact that Wall characters are zero and the sum
; of these six blocks will be zero if a move is possible.

		mov	al, byp Maze[bx+BytesPerRow*2]	 ;Maze[x,  y+2]
		add	al, byp Maze[bx+BytesPerRow*2+2] ;Maze[x+1,y+2]
		add	al, byp Maze[bx+BytesPerRow*2-2] ;Maze[x-1,y+2]
		je	ReturnTrue

		mov	al, byp Maze[bx-BytesPerRow*2]	 ;Maze[x,  y-2]
		add	al, byp Maze[bx-BytesPerRow*2+2] ;Maze[x+1,y-2]
		add	al, byp Maze[bx-BytesPerRow*2-2] ;Maze[x-1,y-2]
		je	ReturnTrue

ReturnFalse:	clc				;Clear carry = false.
		pop	bx
		pop	ax
		ret

; If the demon is going in a north or south direction, we can start a
; new tunnel if there are six wall blocks just to the left or right
; of the current demon.

NorthSouth:	mov	al, byp Maze[bx+4]		;Maze[x+2,y]
		add	al, byp Maze[bx+BytesPerRow+4]	;Maze[x+2,y+1]
		add	al, byp Maze[bx-BytesPerRow+4]	;Maze[x+2,y-1]
		je	ReturnTrue

		mov	al, byp Maze[bx-4]		;Maze[x-2,y]
		add	al, byp Maze[bx+BytesPerRow-4]	;Maze[x-2,y+1]
		add	al, byp Maze[bx-BytesPerRow-4]	;Maze[x-2,y-1]
		jne	ReturnFalse

ReturnTrue:	stc				;Set carry = true.
		pop	bx
		pop	ax
		ret
CanStart	endp




; CanMove-	Tests to see if the current demon (dir=cl, x=dl, y=dh) can
;		move in the specified direction.  Movement is possible if
;		the demon will not come within one square of another tunnel.
;		This function returns true (carry set) if a move is possible.
;		On entry, CH contains the direction this code should test.

CanMove		proc
		push	ax
		push	bx

		MazeAdrs			;Put @Maze[x,y] into ax.
		mov	bx, ax

		cmp	ch, South
		jb	IsNorth
		je	IsSouth
		cmp	ch, East
		je	IsEast

; If the demon is moving west, check the blocks in the rectangle formed
; by Maze[x-2,y-1] to Maze[x-1,y+1] to make sure they are all wall values.

		mov	al, byp Maze[bx-BytesPerRow-4]	;Maze[x-2, y-1]
		add	al, byp Maze[bx-BytesPerRow-2]	;Maze[x-1, y-1]
		add	al, byp Maze[bx-4]		;Maze[x-2, y]
		add	al, byp Maze[bx-2]		;Maze[x-1, y]
		add	al, byp Maze[bx+BytesPerRow-4]	;Maze[x-2, y+1]
		add	al, byp Maze[bx+BytesPerRow-2]	;Maze[x-1, y+1]
		je	ReturnTrue
ReturnFalse:	clc
		pop	bx
		pop	ax
		ret


; If the demon is going east, check the blocks in the rectangle formed
; by Maze[x+1,y-1] to Maze[x+2,y+1] to make sure they are all wall values.

IsEast:		mov	al, byp Maze[bx-BytesPerRow+4]	;Maze[x+2, y-1]
		add	al, byp Maze[bx-BytesPerRow+2]	;Maze[x+1, y-1]
		add	al, byp Maze[bx+4]		;Maze[x+2, y]
		add	al, byp Maze[bx+2]		;Maze[x+1, y]
		add	al, byp Maze[bx+BytesPerRow+4]	;Maze[x+2, y+1]
		add	al, byp Maze[bx+BytesPerRow+2]	;Maze[x+1, y+1]
		jne	ReturnFalse
ReturnTrue:	stc
		pop	bx
		pop	ax
		ret


; If the demon is going north, check the blocks in the rectangle formed
; by Maze[x-1,y-2] to Maze[x+1,y-1] to make sure they are all wall values.

IsNorth:	mov	al, byp Maze[bx-BytesPerRow-2]	;Maze[x-1, y-1]
		add	al, byp Maze[bx-BytesPerRow*2-2];Maze[x-1, y-2]
		add	al, byp Maze[bx-BytesPerRow]	;Maze[x,   y-1]
		add	al, byp Maze[bx-BytesPerRow*2]	;Maze[x,   y-2]
		add	al, byp Maze[bx-BytesPerRow+2]	;Maze[x+1, y-1]
		add	al, byp Maze[bx-BytesPerRow*2+2];Maze[x+1, y-2]
		jne	ReturnFalse
		stc
		pop	bx
		pop	ax
		ret



; If the demon is going south, check the blocks in the rectangle formed
; by Maze[x-1,y+2] to Maze[x+1,y+1] to make sure they are all wall values.

IsSouth:	mov	al, byp Maze[bx+BytesPerRow-2]	;Maze[x-1, y+1]
		add	al, byp Maze[bx+BytesPerRow*2-2];Maze[x-1, y+2]
		add	al, byp Maze[bx+BytesPerRow]	;Maze[x,   y+1]
		add	al, byp Maze[bx+BytesPerRow*2]	;Maze[x,   y+2]
		add	al, byp Maze[bx+BytesPerRow+2]	;Maze[x+1, y+1]
		add	al, byp Maze[bx+BytesPerRow*2+2];Maze[x+1, y+2]
		jne	ReturnFalse
		stc
		pop	bx
		pop	ax
		ret

CanMove		endp




; SetDir- Changes the current direction.  The maze digging algorithm has
; decided to change the direction of the tunnel begin dug by one
; of the demons.  This code checks to see if we CAN change the direction,
; and picks a new direction if possible.
;
; If the demon is going north or south, a direction change causes the demon
; to go east or west.  Likewise, if the demon is going east or west, a
; direction change forces it to go north or south.  If the demon cannot
; change directions (because it cannot move in the new direction for one
; reason or another), SetDir returns without doing anything.  If a direction
; change is possible, then SetDir selects a new direction.  If there is only
; one possible new direction, the demon is sent off in that direction.
; If the demon could move off in one of two different directions, SetDir
; "flips a coin" to choose one of the two new directions.
;
; This function returns the new direction in al.

SetDir		proc	near

		test	cl, 10b			;See if north/south
		je	IsNS			; or east/west direction.

; We're going east or west.  If we can move EITHER north or south from
; this point, randomly choose one of the directions.  If we can only
; move one way or the other, choose that direction.  If we can't go either
; way, return without changing the direction.

		mov	ch, North		;See if we can move north
		call	CanMove
		jnc	NotNorth
		mov	ch, South		;See if we can move south
		call	CanMove
		jnc	DoNorth
		call	RandNum			;Get a random direction
		and	ax, 1			;Make it north or south.
		ret

DoNorth:	mov	ax, North
		ret

NotNorth:	mov	ch, South
		call	CanMove
		jnc	TryReverse
DoSouth:	mov	ax, South
		ret



; If the demon is moving north or south, choose a new direction of east