|
Table of Content | Chapter Nineteen
(Part 8) |
|
Table of Content | Chapter Nineteen
(Part 8) |
| CHAPTER NINETEEN: PROCESSES, COROUTINES AND CONCURRENCY (Part 7) |
| 19.3.1 - AMAZE.ASM |
The best way to learn how to use coroutines is via example. The following program is an interesting piece of code that generates mazes on the PC's display. The maze generation algorithm has one major constraint - there must be no more than one correct solution to the maze (it is possible for there to be no solution). The main program creates a set of background processes called "demons" (actually, daemon is the correct term, but demon sounds more appropriate here). Each demon begins carving out a portion of the maze subject to the main constraint. Each demon gets to dig one cell from the maze and then it passes control to another demon. As it turns out, demons can "dig themselves into a corner" and die (demons live only to dig). When this happens, the demon removes itself from the list of active demons. When all demons die off, the maze is (in theory) complete. Since the demons die off fairly regularly, there must be some mechanism to create new demons. Therefore, this program randomly spawns new demons who start digging their own tunnels perpendicular to their parents. This helps ensure that there is a sufficient supply of demons to dig out the entire maze; the demons all die off only when there are no, or few, cells remaining to dig in the maze.
; AMAZE.ASM
;
; A maze generation/solution program.
;
; This program generates an 80x25 maze and directly draws the maze on the
; video display. It demonstrates the use of coroutines within a program.
.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 e.
pop bp
ret 4
; See if moving to this spot was an illegal move. There will be
; a NoWall value at this cell in the maze if the move is legal.
NotSolved: mov dl, sm_X
mov dh, sm_Y
MazeAdrs
mov bx, ax
cmp Maze[bx], NoWall
je MoveOK
mov ax, 0 ;Return failure
pop bp
ret 4
; Well, it is possible to move to this point, so place an appropriate
; value on the screen and keep searching for the solution.
MoveOK: mov Maze[bx], Visited
ifdef ToScreen
push es ;Write a "VisitChar"
ScrnAdrs ; character to the
mov bx, ax ; screen at this X,Y
mov ax, ScreenSeg ; position.
mov es, ax
mov word ptr es:[bx], VisitChar
pop es
endif
; Recusively call SolveMaze until we get a solution. Just call SolveMaze
; for the four possible directions (up, down, left, right) we could go.
; Since we've left "Visited" values in the Maze, we will not accidentally
; search back through the path we've already travelled. Furthermore, if
; we cannot go in one of the four directions, SolveMaze will catch this
; immediately upon entry (see the code at the start of this routine).
mov ax, sm_X ;Try the path at location
dec ax ; (X-1, Y)
push ax
push sm_Y
call SolveMaze
test ax, ax ;Solution?
jne Solved
push sm_X ;Try the path at location
mov ax, sm_Y ; (X, Y-1)
dec ax
push ax
call SolveMaze
test ax, ax ;Solution?
jne Solved
mov ax, sm_X ;Try the path at location
inc ax ; (X+1, Y)
push ax
push sm_Y
call SolveMaze
test ax, ax ;Solution?
jne Solved
push sm_X ;Try the path at location
mov ax, sm_Y ; (X, Y+1)
inc ax
push ax
call SolveMaze
test ax, ax ;Solution?
jne Solved
pop bp
ret 4
Solved:
ifdef ToScreen ;Draw return path.
push es
mov dl, sm_X
mov dh, sm_Y
ScrnAdrs
mov bx, ax
mov ax, ScreenSeg
mov es, ax
mov word ptr es:[bx], PathChar
pop es
mov ax, 1 ;Return true
endif
pop bp
ret 4
SolveMaze endp
; Here's the main program that drives the whole thing:
Main proc
mov ax, dseg
mov ds, ax
mov es, ax
meminit
call Init ;Initialize maze stuff.
lesi MainPCB ;Initialize coroutine
coinit ; package.
; Create the first demon.
; Set up the stack pointer for this guy:
mov cx, 256
malloc
add di, 248
mov DemonList.regsp, di
mov DemonList.regss, es
; Set up the execution address for this guy:
mov DemonList.regcs, cs
mov DemonList.regip, offset Dig
; Initial coordinates and direction for this guy:
mov cx, East ;Start off going east.
mov dh, StartY
mov dl, StartX
mov DemonList.regcx, cx
mov DemonList.regdx, dx
; Set up other misc junk:
mov DemonList.regds, seg dseg
sti
pushf
pop DemonList.regflags
mov byp DemonList.NextProc, 1 ;Demon is "active".
inc DemonCnt
mov DemonIndex, 0
; Set up the Timer demon:
mov DemonList.regsp+(size pcb), offset EndTimerStk
mov DemonList.regss+(size pcb), ss
; Set up the execution address for this guy:
mov DemonList.regcs+(size pcb), cs
mov DemonList.regip+(size pcb), offset TimerDemon
; Set up other misc junk:
mov DemonList.regds+(size pcb), seg dseg
sti
pushf
pop DemonList.regflags+(size pcb)
mov byp DemonList.NextProc+(size pcb), 1
inc DemonCnt
; Start the ball rolling.
mov ax, ds
mov es, ax
lea di, DemonList
cocall
; Wait for the user to press a key before solving the maze:
getc
mov ax, StartX
push ax
mov ax, StartY
push ax
call SolveMaze
; Wait for another keystroke before quitting:
getc
mov ax, 3 ;Clear screen and reset video mode.
int 10h
Quit: ExitPgm ;DOS macro to quit program.
Main endp
cseg ends
sseg segment para stack 'stack'
; Stack for the timer demon we create (we'll allocate the other
; stacks dynamically).
TimerStk byte 256 dup (?)
EndTimerStk word ?
; Main program's stack:
stk byte 512 dup (?)
sseg ends
zzzzzzseg segment para public 'zzzzzz'
LastBytes db 16 dup (?)
zzzzzzseg ends
end Main
|
Table of Content | Chapter Nineteen (Part 8) |
Chapter Nineteen: Processes,
Coroutines and Concurrency (Part 7)
29 SEP 1996