|
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
