xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) (04/18/91)
Archive-name: townmaze/part04
#! /bin/sh
# This is a shell archive. Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file". To overwrite existing
# files, type "sh file -c". You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g.. If this archive is complete, you
# will see the following message at the end:
# "End of archive 4 (of 4)."
# Contents: townpgmr.doc
# Wrapped by xanthian@zorch on Wed Apr 17 20:34:41 1991
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'townpgmr.doc' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'townpgmr.doc'\"
else
echo shar: Extracting \"'townpgmr.doc'\" \(39151 characters\)
sed "s/^X//" >'townpgmr.doc' <<'END_OF_FILE'
XFile townpgmr.doc, the programmers' documentation for townmaze.
X
X
XThis file documents the C code; see file README for compile and
Xexecute instructions, copyright restrictions, etc.
X
XSince townmaze is meant to be a set of software for use by programmers,
Xthere is going to be a _lot_ of programmer documentation. Each of the
Xfollowing source code files will be separately described.
X
X townmaze.h townproto.h
X
X cleanupmap.c closedoors.c closegates.c connectst.c
X filllist.c fillmaze.c finishalleys.c freespace.c
X getargs.c interiorcell.c makecourts.c makegates.c
X makestreet.c makespace.c makeunused.c movefromto.c
X nhbrexists.c nhbris.c showdbmaze.c showlistdet.c
X showlistsum.c showmaze.c townmain.c usage.c
X
XBut first, an overview.
X
XTownmaze works conceptually on a structure of maze cells in a
Xfour-connected (each cell has four neighbors) grid with one of five
Xstatuses:
X
XISOLATED - no neighbor of this cell is a street.
X
XLIVE - some neighbor of this cell is a street, and some neighbor of
Xthis cell is an isolated cell.
X
XDEAD - some neighbor of this cell is a street, but no neighbor of this
Xcell is an isolated cell.
X
XSTREET - the passageways for the adventurers; this cell is connected
Xby a series of other street cells to some origin point for a street.
X
XUNUSED - this cell is solid rock, it may neither become a room nor a
Xstreet, nor have a street cell as a neighbor.
X
XThe goal is to build a town maze like the upper level of Bard's Tale I,
Xwith a street to every door, and a fairly "double row of brownstones"
Xappearance, by looking two neighbor links away, to preserve where
Xpossible room cells in back to back rows.
X
XTo accomplish this, LIVE cells are used to indicate when at least one
Xdirection from the live cell, the next street is separated by an
XISOLATED cell and some other non-STREET cell on the far side. This
Xworks fairly well when the streets run very parallel, not so well when
Xthey don't. Better strategies may well exist, but this one does very
Xnice mazes for some parameter values.
X
XThe basic plan of townmaze is to
X
X1) Accept a set of command line parameters.
X
X2) Allocate two major data structures of the appropriate size in
Xaccordance with those parameters, one a two dimensional array of
Xcharacters which will be used to build and display the completed maze,
Xthe other a one dimensional array of structures which is used as a
Xstatus list to store the status of each maze cell, and to link maze
Xcells together in sublists for speed of processing.
X
X3) Fill in the maze as a solid array of rooms except the corners,
Xwhich are blocked off (they're too hard to use), each room without
Xdoors, and fill in the status list and link it together as a list of
XISOLATED cells, except again for the corners, which become UNUSED
Xcells.
X
X4) Seed the maze with uniquely numbered street origins at border or
Xinterior cells, and obstacles at interior cells only. Assure that
Xdifferent seed cells are far enough apart to allow successful maze
Xcreation. Update display to match; rooms beside streets get doors
Xfacing the streets; the outside wall next to a street becomes a
X"gate".
X
X4a) Seed any UNUSED cells in the interior of the maze.
X
X4b) Seed any "gate" STREET cells along the border of the maze.
X
X4c) Seed any "courtyard" STREET cells in the interior of the maze.
X
X5) Connect the streets by extending them until all streets have the
Xsame street number; merge street numbers when two streets meet. Again
Xupdate the display array to match; rooms are converted to streets by
Xremoving all doors. Rooms newly adjacent to streets gain a new door
Xon that street.
X
X6) When all streets are connected, continue to extend them as "alleys"
Xuntil no isolated room cells remain.
X
X7) Close most of the doors, leaving one open door per room, by
Xreplacing doors by walls.
X
X8) Possibly close some or all gates by replacing them with walls.
X
X9) Clean up "pillars"; bits of wall that have been isolated by being
Xsurrounded by streets.
X
X10) Display the maze.
X
X11) Free the allocated space.
X
X12) Exit.
X
XDetailed source module descriptions.
X
X-----------------------------------------------------------------------
X| townmaze.h
X-----------------------------------------------------------------------
X
XThis header file is where all the #ifdef controlling #defines are done
X(except MAINLINE, in townmain.c, and RAND48, in the make file), the
Xstructures are defined, the defined constants are declared, and the
Xexternal variables are declared or defined under #ifdef control.
X
XIn particular, the cmaze two dimensional character array for maze
Xdisplay, the statlist one dimensional structure array for cell
Xstatuses, and the various cell type link list head pointers isolated,
Xlive, dead, street, and unused, and their corresponding cell counters
Xisolatedct, livect, deadct, streetct, and unusedct, are all defined
Xhere. As well, streetnumct, the count of how many different street
Xnumbers exist, is defined here.
X
XAs well, the global parameters mazeheight, mazewidth, mazegates,
Xleftgates, mazecourts, mazeunused, with their appropriate defaults
Xwhen not read in from the command line, and randomseed without a
Xdefault value, and the derived global parameter listsize, are declared
Xand defined here.
X
XIn addition, the integer constants ISOLATED, LIVE, DEAD, STREET, and
XUNUSED are defined, and the character constants WALL, VDOOR, HDOOR,
Xand BLANK. Also defined here is NOPOINTER, which acts as a null
Xpointer in the statlist double linked lists, which use indices rather
Xthan pointers for links.
X
X
X-----------------------------------------------------------------------
X| townproto.h
X-----------------------------------------------------------------------
X
XThis header file contains all the function prototypes, since each
Xfunction is in its own separate source module, done in both ANSI C and
Xold K&R form, conditioned on __STDC__, the compiler defined constant
Xto identify ANSI C compilers. The same conditioning is done in each
X*.c module for compatibility.
X
X
X-----------------------------------------------------------------------
X| cleanupmap.c -- cleanmap()
X-----------------------------------------------------------------------
X
XThis is the routine that accomplishes step 9) above. It does this by
Xmoving to each intersection point in the cmaze display array interior
Xfor the horizontal and vertical walls (see fillmaze.c, below) of the
Xrooms, and looking at the north, south, east and west display
Xcharacters; if they are all blanks, then this is an isolated "pillar"
Xpiece of wall, so it is replaced by a blank.
X
X
X-----------------------------------------------------------------------
X| closedoors.c -- closedoors()
X-----------------------------------------------------------------------
X
XThis is the routine that accomplishes step 7) above. It does this by
Xwalking the DEAD list from list head pointer dead until a NOPOINTER
Xnext pointer is found. At each room on the dead list, it counts the
Xdoors by looking north, east, south, and west, then if more than one
Xexists, picks one at random to survive and replaces the others with
XWALL symbols. Most of the nasty looking arithmetic is just the
Xtranslation from statlist indices to cmaze locations; all the code is
Xrife with them.
X
XThe necessity for this routine is that when the previous street
Xcreation routines are complete, most of the room cells have most walls
Xas doors, which doesn't make for much of a challenge, the adventurer
Xdoesn't have to work down the street, but can instead just walk
Xthrough the row of rooms to the street behind.
X
XAlso, games like Bard's Tale are simpler to design if all normal rooms
Xhave only one exit, since then only one viewpoint and no choices need
Xbe presented to the player.
X
X-----------------------------------------------------------------------
X| closegates.c -- closegates()
X-----------------------------------------------------------------------
X
XThis is the routine that accomplishes step 8) above. It does this in
Xresponse to a comparision between the -g mazegates paramenter and the
X-l leftgates parameter; if more gates were seeded than were requested
Xin the final maze, then gates are closed at random until only
Xleftgates of them remain.
X
XHow many places along the maze periphery must be checked for gates is
Xprecomputed into possiblegates, which becomes the inner (for) loop
Xlimit.
X
XThe gate closing task is done by keeping track of how many gates are
Xleft with gatesleft, conditioning an outer while loop on gatesleft
Xbeing greater than leftgates, then withing the loop rolling a random
Xgate number into chosengate as a modulus of RANDOM() by gatesleft, and
Xthen walking the periphery of the maze in and inner for loop, looking
Xfor VDOOR or HDOOR elements in the outer wall, and counting how many
Xgates have been encountered in foundgate.
X
XWhen the gate encountered matches the number found, the gate is
Xclosed, the gatesleft decremented, and the inner loop broken.
X
XThe messy interior of the inner loop is unavoidable unless a link list
Xof gate cells is kept, which would have messed up statlist too much;
Xthe arithmetic to walk around the border of a rectangle when the
Xindices are in row major order instead of some nice inturning spiral
Xis just that ugly.
X
X
X-----------------------------------------------------------------------
X| connectst.c -- connectstreets()
X-----------------------------------------------------------------------
X
XThis is the routine that accomplishes step 5), above. The goal is to
Xmake all the streets in the maze into one connected street, decreasing
Xstreetnumct to 1, and this is where townmaze spends most of its time,
Xsince adding new street cells is what makes the maze.
X
XThis is one of the biggest routines in townmaze, because it needs
Xthree separate strategies to connect streets. First it tries to
Xconnect all the streets by only using cells from the LIVE list in
Xstatlist. If all the LIVE cells are used up and there are still more
Xthan one street noted in streetnumct, then the second strategy is to
Xuse only DEAD cells that touch two different streets as new street
Xcells. If worst comes to worst, if streetnumct is still greater than
Xone, then in the third strategy, the entire DEAD cell list is used as
Xtargets to connect the streets.
X
XThis routine runs a lot slower than first glance might suggest,
Xbecause called routine makestreet() can succeed as infrequently as
Xonce in a thousand calls, depending on the current configuration of
Xthe maze, and the mazestraightness parameter setting.
X
XThe first phase is done by picking a random LIVE list element, walking
Xthe live list to that element, and asking makestreet() to make a
Xstreet of it. The outer loop doing this is conditioned on both
Xstreetnumct being greater than 1, and livect being greater than zero.
XThe fact that makestreet() might refuse to make a street on
Xstraightness criteria is hidden by just running the outer loop until
Xone of the conditions fails.
X
XAfterthe outerloop selects a targetcell from the LIVE list based on a
Xmodulus of RANDOM() against the livect, the middle loop is used to
Xwalk livewalk down the LIVE list. This is where the maintenance of the
Xlinks lists pays off; without them, the walk to find the targetcell
Xamong the LIVE list cells would have to walk the whole statlist, a
Xmuch longer list.
X
XIn the inner loop, nhbrexists is used, here as elsewhere, to avoid
Xindexing an invalid entry of statlist, while nhbris is used to
Xtranslate simply from a neighbor number 0-3 to a statlist cell index.
XIf you want to be nice about it you could call this data abstraction.
X
XThe call to makestreet() contains "-1" as the last parameter, which
Xenables the straightness checks there.
X
XThe second phase is done by walking the DEAD list, seeking DEAD cells
Xwhose neighbors include streets with two or more different numbers.
XThis could probably have been done more cleanly with the "for(i" loop
Xreplaced by a "while (deadwalk != NOPOINTER)" loop, but this one
Xworks. Because the DEAD list is changing size while the list is
Xwalked, there are some hyper-defensive checks going on to make sure
Xthe DEAD list end isn't exceeded. For the same reason, deadwalk has
Xto be moved past the current cell before it is possibly yanked out
Xfrom under by makestreet (which will move it from the DEAD list to
Xthe STREET list if called), so lastdead is used to access the current
Xcell and then not used after the makestreet call.
X
XAt the top of the loops, a check is made that this cell is interior;
Xthe goal is to avoid running streets along the city wall, a boring
Xkind of design; take this check out if you want the occasional wall
Xhugger. The double loop on j and k is comparing neighbors, where they
Xexist, looking for streets with different numbers.
X
XTo avoid trying to break out of a double loop, not one of C's strong
Xpoints, another trick was used. The reason this loop doesn't keep
Xtrying to make a street out of the chosen cell after it has done so
Xonce is that makestreet() causes all the adjacent streets to be merged
Xand have the same street number, so that the inner if test always
Xfails after the first success.
X
Xhe call to makestreet is with a forcing actual direction last
Xparameter (see below about cheapdir) so the street is always created
Xon the first try. Except, that if the street is a neighbor of an
XUNUSED cell, then the check at the very top of makestreet() means
Xintsead that it will never be made into a street.
X
XThe double j, k loop can thus in either case safely be let run to
Xcompletion, since it will never ask makestreet() to make a street into
Xa street. Letting it spin through to completion is no big deal since
Xphase two is a very minor part of the overall time in any case, doing
Xno random calls.
X
XThe little trick down inside the loop with cheapdir is to adopt the
Xdirection of one of the streets whether this cell continues it or not,
Xand the second one if it happens to continue the street. This is not
Xperfectly fair, but it doesn't seem to hurt anything, and with at
Xleast two sides already streets, this cell is less likely than many to
Xwant to continue its direction into a subsequently-started-here alley
Xor street.
X
XThe third phase is much like the first, except that now the DEAD list
Xis being randomly used to extend the streets, rather than the live
Xlist. This tends to make the town maze more open, and to destroy the
Xback to back rooms that are the whole goal of townmaze, but it is
Xsometimes the only way to "make ends meet" and get all the streets
Xconnected, an absolute requirement. for townmaze. The only difference
Xfrom the first phase is that, unlike LIVE cells, which are always
Xinterior (to keep the streets from running down the city wall again),
XDEAD cells may be border cells, and we want explicitly to exclude the
Xborder cells from consideration for extending the streets.
X
X
X-----------------------------------------------------------------------
X| filllist.c -- filllist()
X-----------------------------------------------------------------------
X
XThis routine does half of step 3), above. This function takes the raw
Xspace allocated for statlist by makespace(), and turns it into an
Xarray which is also five doubly linked lists, all but the ISOLATED
Xlist empty and with list heads set to NOPOINTER, and list counts set
Xto zero, to start. The ISOLATED list count is set to listsize, and
Xthe list header pointing to the zeroth element of statlist. Just at
Xthe end it puts the four corner cells into the UNUSED list using
Xmovefromto(), and sets the streetnumct to zero (it needed to be done
Xsomewhere in setup, or static set there, and I prefer the self
Xdocumentation of an explicit action).
X
X
X-----------------------------------------------------------------------
X| fillmaze.c -- fillmaze()
X-----------------------------------------------------------------------
X
X
XThis routine does the other half of step 3), above. This function
Xmakes every even (zero origin, remember) row and column of the cmaze
Xcharacter array a WALL symbol, and the remaining doubly odd coordinate
Xinterstices BLANK symbols, and at the end fills in WALL symbols in the
Xfour corner cells' centers to make them UNUSED looking.
X
X
X-----------------------------------------------------------------------
X| finishalleys.c -- finishalleys()
X-----------------------------------------------------------------------
X
XThis is the routine that accomplishes step 6), above. After
Xconnectstreets() has made sure that all the streets in town are
Xinterconnected, there may still be ISOLATED (and thus LIVE) cells
Xremaining. This routine continues to turn LIVE cells into streets,
Xand thus ISOLATED cells into LIVE or DEAD cells and possible
Xconsequently LIVE cells into DEAD cells (from lack of a neighboring
XISOLATED cell and more) until no LIVE or ISOLATED cells remain.
X
XThis works just like the first phase of connectstreets(), except that
Xit is no longer conditioned on streetnumct > 1, just on livect > 0.
X
X[By the way, there's no special significance to "alleys" as opposed to
X"streets", the name just seemed homeyer.]
X
X
X-----------------------------------------------------------------------
X| freespace.c -- freespace()
X-----------------------------------------------------------------------
X
XThis routine does step 11), above. Sigh. There really ought to be a
Xlibrary routine to allocate, and another to free, the ugly messes C
Xuses for multidimensional arrays. So far as I can figure, you can
Xallocate a fixed size array without the intermediate pointer list only
Xat compile time, since there is no way to convince the compiled code
Xat run time that it knows the major dimension, so regular indexing
Xwon't work for an array dynamically allocated into an array declared
X"cmaze[][]", and the compiler complains if you try.
X
XIn any case, this does the standard stuff to give back the storage for
Xstatlist and cmaze. On a Unix box this is excessive neatness, but on
Xan Amiga that doesn't do resource tracking, this is mandatory to avoid
X"leaking" memory and forcing an eventual reboot.
X
XError checking is done on the free() calls; I don't have any recourse
Xif an error occurs in any case, but at least I can complain before
Xdying.
X
X
X-----------------------------------------------------------------------
X| getargs.c
X-----------------------------------------------------------------------
X
XThis routine accomplishes step 1) above. Sigh again. Lattice C for
Xthe Amiga doesn't have getopts() as a library routine, so I wrote this
Xspecial purpose beast. To avoid intensely ugly code, the nice
Xgetopts() feature of accepting both spaces and no spaces between the
Xflag and the value is foregone here; I just don't have that much
Xpatience. Leaving the space only option makes this code neat and
Xeasy.
X
XThe routine starts by checking for any arguments, and if none just
Xgoes down to compute listsize and (compile time ooptionally) do a
Xheader and return. If there are an odd number of argv entries (the
Xfunction name is counted in argc, so this means that flags and values
Xcome in pairs), the parameters are fetched in order into the
Xappropriate global parameter variables. If an even number of argv
Xentries exist, the routine complains and exits.
X
XThe switch statement is pretty standard; the only interesting element
Xis the -r switch, which loads a long instead of an integer, and also
Xcalls SEEDRANDOM(randomseed) to override the previous (in main()) call
Xto SEEDRANDOM(time()). This lets the random seed be forced, allowing
Xduplicate runs for debugging or for inclusion in a game where the code
Xand seeds are cheaper to store than the rooms. (Big game!)
X
XThe check below the switch is about half of the sanity in the whole
Xprogram:
X
X((mazewidth%2) != 1) -- The maze width must be odd.
X
X((mazeheight%2) != 1) -- The maze height must be odd.
X
X(mazewidth < 11) -- The maze must be at least five cells high to leave
Xroom for one interior row of buildings.
X
X(mazeheight < 11) -- The maze must be at least five cells wide to
Xleave room for one interior row of buildings.
X
X(mazegates < 0) -- There must be at least zero gates.
X
X(mazegates > (2*((mazeheight - 6)/7) + 2*((mazewidth- 6)/7))) -- There
Xcan be no more gates than one per three side cells between the unused
Xcorner cells, to assure that all gates will fit.
X
X(leftgates < 0) -- There must be at least zero gates left at the end.
X
X(leftgates > mazegates) -- There cannot be more gates left than there
Xwere to begin.
X
X(mazecourts < 0) -- There must be at least zero courtyards.
X
X(mazecourts > (((mazeheight - 5)/6)*((mazewidth - 5)/6))) --
XCourtyards must have room for at least two spaces between them,
Xotherwise they won't fit when makecourts() is run.
X
X((mazecourts + mazegates) < 1) -- There must be at least one street.
X
X(mazeunused > (((mazeheight - 1)/14)*((mazewidth - 1)/14))) -- Unused
Xcells must have room for at least three squares between them,
Xotherwise they can trap DEAD cells away from streets and won't fit when
Xmakeunused() is run..
X
X(mazestraightness < 0) -- Negative straightness makes no sense. [Zero
Xmeans don't do straightening, and that's OK.]
X
X(mazestraightness > 998) -- There must be at least one chance per
Xthousand of accepting a bend in the street, or an infinite loop might
Xoccur. 999 is the highest value returned by the random roll modded
Xagainst 1000, so 998 is the largest accpetable straightness parameter.
X
XIf all the parameters are right, the listsize (number of cell
Xstructures in statlist) is computed from the requested maze width and
Xheight. If the HEADER option is on (I always use it) a single line of
Xparameters is printed to standard out along with the eventual maze.
X[All other output goes to the standard error unit.]
X
X
X-----------------------------------------------------------------------
X| interiorcell.c -- interiorcell(cellid)
X-----------------------------------------------------------------------
X
XThis simple function just checks that the passed cell has all four
Xneighbors using nhbrexists(). Lots of stuff in townmaze specifies
Xinterior cells only.
X
X
X-----------------------------------------------------------------------
X| makecourts.c -- makecourts()
X-----------------------------------------------------------------------
X
XThis routine does step 4c), above. In response to the mazecourts
Xparameter value, this routine places "courtyards", STREET cells in the
Xinterior of the town maze, spaces them out by making sure before they
Xare placed that all neighbor cells and the randomly chosen cell are
XISOLATED cells, and uses a side effect of makestreet() to turn them
Xinto LIVE or DEAD cells as each courtyard is placed, effectively
Xfending off neighbors a bit.
X
XBecause there are so many ISOLATED cells when this is done, it is
Xbetter to roll the randomizer agains the whole maze and accept the
Xmisses where a non-ISOLATED cell is chosen, than to roll against the
Xlength of the ISOLATED list and walk it from the end each time. If
Xone habitually made the courtyard cells very high, it might be better
Xto do this the other way.
X
XThe random roll could be improved, but for small mazes it doesn't
Xmatter much. The bias of ignoring the mismatch between the modulus
Xand the length of the interval returned by RANDOM() in a maze 32K on a
Xside would probably be pretty obvious.
X
XBecause it was easier than explicitly compensating for the
Xinterference from UNUSED cells, a MAXTRIES limit is enforced for
Xplacing each courtyard cell. The limit is kept very high to prevent
Xinterference with the straightness parameter other places that it is
Xused, but with it in here, makecourts is guaranteed to terminate
Xeventually. On the other hand, it is not guaranteed to place as many
Xcourtyards as the user specified, which is one reason for the sanity
Xcheck at the start of connectstreets().
X
X
X-----------------------------------------------------------------------
X| makegates.c
X-----------------------------------------------------------------------
X
XThis routine does step 4b), above. In response to the makegates
Xparameter value, this routine places "gates", STREET cells along the
Xborder of the town maze, spacing them apart by insisting that all the
Xexisting neighbors when each gate cell is placed be ISOLATED cells,
Xincluding the chosen cell itself. It uses makestreet() as each gate
Xcell is placed, to turn the chosen cell into a street, its border cell
Xneighbors into DEAD cells, and its interior neighbor into a LIVE or
XDEAD cell depending on that neighbor's neighbors.
X
XIt would have been possible to just roll a randomizer against the
Xwhole statlist array, and then check the border and isolated
Xproperties, but for a very large town maze, this would have been
Xgrossly inefficient and slow, so the more complex method seen is used,
Xinstead. The random roll is effectively done against the number of
Xcell wallss in the town maze border, the border is walked using the
Xlogic that comprises the whole middle of this routine, and if the
Xchosen wall meets the criteria of ISOLATED self and neighbors, it is
Xselected. This can still be slow if gates are dense, but not nearly
Xas bad as scattershooting at the whole area.
X
XAs explained above for closegates(), the ugly arithmetic in the middle
Xborder walking logic is fairly inevitable, though perhaps it should be
Xhidden like nhbrexists() hides similar arithmetic. Maybe next time.
X
XNotice that, because we can't abstract away with interiorcell(), we
Xmust explicitly check nhbrexists() for each cell before using
Xnhbris() to index statlist.
X
XAlso, the test against MAXTRIES may not be needed here, but it was
Xeasier to put in the check than to do the analysis to prove it wasn't
Xneeded, and it makes future code changes like allowing non-corner
XUNUSED border cells more robust.
X
X
X-----------------------------------------------------------------------
X| makestreet.c -- makestreet(chosencell,streetid,streetpoints)
X-----------------------------------------------------------------------
X
XThis routine is charged with doing all the work to make a single cell
Xinto a street cell, including updating all the neighbor cells whose
Xstatus changes because this cell became a street cell, and doing all
Xthe corresponding architectural changes. It is also tasked with
Xenforcing the straightness parameter, which means that it gets to say
X"no I won't" a lot when told to make a street, and all the routines
Xthat call it have to either override that option with a explicit
Xdirection in the "streetpoints" parameter, or survive not being
Xobeyed. Not surprising that makestreet is a big routine.
X
XIt starts out by refusing to build a street alongside an UNUSED cell,
Xsince the point of an UNUSED cell is to have all neighbors be rooms.
XIt just returns immediately.
X
XNext, it checks the last parameter, and if it is "-1" (no street
Xdirection selected) enables the straightness check and does it by
Xmaking sure that the selected cell can continue some street's current
Xdirection. If not, it returns immediately.
X
XNext, it moves the chosen cell to the STREET list using movefromto().
X
XNext, it copies the streetid parameter to the cells
Xstatlist[].streetnum field.
X
XNext, it updates the cmaze display version of the town maze. As a
Xfirst guess, it makes all four walls into doors.
X
XNext, it starts working on the first order neighbors. If the neighbor
Xis a STREET, then the door becomes a BLANK or passageway. If the
Xchosen cell would continue the street direction, adopt that neighbor's
Xstreet direction for this cell; keep the last one thus adopted. If it
Xwouldn't continue an existing street direction, defer this matter for
Xthe bottom of the routine.
X
XNext, a very important check is done to see if a detected neighbor
Xstreet has a different street number than this streets number (passed
Xin as streetdir). If so, the higher number street is updated by a
Xwalk of the streetlist with the street number of the lower numbered
Xstreet, and the streetnumct is decremented. The two driving goals of
Xthe whole townmaze routine are to make streetnumct 1 and isolatedct 0.
X
XIf the neighbor is LIVE, make it DEAD and then check its neighbors and
Xif one is still ISOLATED, make it LIVE again.
X
XIf the neighbor is ISOLATED, things get complicated. This was hard
Xenough to see that it was the last big logic bug in the program. If
Xthe neighbor is ISOLATED, it becomes LIVE or DEAD, as appropriate,
Xexcept that border cells always become dead to keep the roads off the
Xwalls as mentioned previously.
X
XThis change, however, might mean that the formerly ISOLATED cells LIVE
Xneighbors, if any, no longer qualify as LIVE. So, each of those
Xsecondary neighbors is checked, and if it is LIVE, made DEAD, and then
Xeach of its (now tertiary) neighbors is checked in turn, and if it is
XISOLATED, the DEAD cell is revived to LIVE again. Whew! Making this
Xwork was what achieved back to back rows of rooms in the town maze
Xafter long programming effort.
X
XNext, the question of street direction for the new STREET cell is
Xrevived. If some of the above overroad the "-1" that was installed by
Xfilllist(), that value is retained. If not, and a valid (not -1)
Xdirection was passed in streetpoints, that value is adopted. If not,
Xthe direction from a neighboring street is adopted, and this becomes a
Xturning point in the street. Note that the effect of the whole
Xroutine is that if the straightness check near the top found a
Xdirection that this street could continue an existing street, then it
Xdoes continue some street, so we only get down here and turn the
Xstreet if the turn direction was passed in, or if the dice roll was
Xsuch as to allow a bend.
X
XAt the end, makestreet returns a True value; it several other places
Xreturns False; I'm not sure this is currently used anywhere, but if
Xdesired for your code, the return value tells whether a street cell
Xwas in fact created.
X
X
X-----------------------------------------------------------------------
X| makespace.c -- makespace()
X-----------------------------------------------------------------------
X
XThis routine does step 2) above. The predecessor to freespace(), this
Xroutine uses malloc() to allocate space for the statlist and cmaze
Xarrays, using the usual grotesque C mechanisms. It is very defensive
Xof freeing every bit of acquired memory if a malloc() call fails,
Xbecause on the Amiga, malloc()ed memory is lost if not free()d before
Xexit.
X
X
X-----------------------------------------------------------------------
X| makeunused.c -- makeunused()
X-----------------------------------------------------------------------
X
XThis routine does step 4a), above. In response to parameter
Xmazeunused, this routine makes some of the interior cells of the town
Xmaze have UNUSED status and a WALL symbol in the center. It looks
Xgrotesque, but that's just because it checks the chosen cell and its
X48 closest neighbors to be ISOLATED before accepting selection of the
Xcell for the UNUSED list.
X
XAttempts are controlled by MAXTRIES, and, since this is the hardest
Xseed item to place, it should be done first. The reason for the wide
Xband of ISOLATED cells is to assure that UNUSED cells, which cannot
Xhave streets beside them, have at least three rows of cells between
Xthem, so street connection is not blocked.
X
XAt the top of the routine, a choice existed to use simple math and
Xinefficient surplus random calls, or complex math so that only
Xinterior cells were eligible for the random call. The simple,
Xwasteful method was chosen, since the mazeunused parameter is
Xcarefully limited to make sure the UNUSED cells will actually fit, and
Xthe number used is zero by default. So totalcells is just the list
Xsize, and is used for the modulus against the RANDOM() call.
X
XThe outer loop is pretty simple, it just counts the requested
Xmazeunused cells whose creation is attempted, attempts to find one to
Xcreate upto to MAXTRIES attempts, and if one is found, as opposed to
Xfalling through on MAXTRIES, moves it to the UNUSED list with
Xmovefromto(), and makes the center a WALL symbol in cmaze with the
Xusual ugly arithmetic to convert from statlist to cmaze indices.
X
XThe inner loop is simpler yet, with just two statements, the random
Xcell choice to try, and a bump of tries to check each round against
XMAXTRIES.
X
XThe scary looking part is the 59 guard conditions on those two
Xstatements, perhaps some minor record. Dijkstra would be proud. There
Xis really a lot less than meets the eye. First, the tries against
XMAXTRIES test is done. Next, enough interiorcell() checks are done to
Xassure that all 49 cells exist, each check depending on some one
Xbefore for the existance of the next cell to check. Last, all 49
Xcells are checked to be ISOLATED cells. The thing that makes it look
Xmessy is that the nbhris() method of finding a neighbor is used rather
Xthan defining several extra functions to accomplish the same thing
Xwith fewer lines of code. Again, mainly defended by this being a low
Xcpu cost part of the code.
X
X-----------------------------------------------------------------------
X| movefromto.c -- movefromto(&fromlist,&fromcount,&tolist,&tocount,
X| newstat,cellnum)
X-----------------------------------------------------------------------
X
XThis lovely little routine is used to hide almost all of the details
Xof fairly tricky double linked list maintenance from the rest of the
Xcode.
X
XNothing terribly original is going on here; the cell pointers are
Xsaved, the cell is unlinked from the (middle of the) from list and
Xlinked into the head of the to list, the saved pointers are used to
Xrepair the rest of the from list, and the cell status is updated and
Xthe from and to counts corrected..
X
XThere is a little complexity because the list heads are "pointers"
X(indices really) rather than whole list elements, but that is one of
Xthe two standard approaches.
X
X-----------------------------------------------------------------------
X| nhbrexists.c -- nhbrexists(cellid,nhbrid)
X-----------------------------------------------------------------------
X
XThis simple little routine just converts the statlist cell index to
Xcell row and cell column, something that corresponds to no existing
Xarray in the program, and then checks to see if the neighboring cell
Xin the nhbrid direction (0==north==up; 1==east==right; 2==south==down;
X3==west==left) falls inside the bounds of the cell row and column
Xlimits and returns true or false.
X
X-----------------------------------------------------------------------
X| nhbris.c -- nhbris(cellid,nhbrid)
X-----------------------------------------------------------------------
X
XThis equally simple routine depends on the neighbor cell being known
Xto exist, and returns its statlist cell index given the current cell
Xindex and the neighbor direction.
X
X-----------------------------------------------------------------------
X| showdbmaze.c -- showdebugmaze()
X-----------------------------------------------------------------------
X
XThis routine is for debug, and is linked in but only called in error
Xconditions unless the SHOWSTART define is compiled set to 1.
X
XIt does give a very handy debugging display, though, with the cell
Xcenters of non-STREET cells replaced by letters showing the cell
Xstatus, I, L, D, U, or ? for bad status, and the centers of STREET
Xcells replaced by the direction of that street cell as ^ > v < or X
Xfor bad direction.
X
XThis lets one dump (in one case where I used it) a running list of
Xmazes, with a single street cell more progress for each, and visualize
Xhow the algorithm is working. I used this display to find the problem
Xwith tertiary neighbors of ISOLATED cells mentioned above under
Xmakestreet().
X
XThe method is to walk the entire cmaze character array, dumping the
Xarray contents for all but center-of-cell cmazearray characters (the
Xones with both indices odd), and, using a big switch statement on cell
Xstatus and a nested smaller switch statement on street direction for
Xstatus STREET, to chose the status or direction symbol to print in
Xplace of the usual BLANK or WALL center symbol.
X
XThe default: entries for the switch statements are bogosities, though
Xcute, but it's hard to put obsessively detailed debug statements into
Xwhat are already debug routines, so I didn't.
X
X-----------------------------------------------------------------------
X| showlistdet.c -- showlistdetail()
X-----------------------------------------------------------------------
X
XAnother debug routine, calls to which are commented out in main().
XThis and showlistsummary() together dump a detailed printout of the
Xcontents of statlist. Since mountains of data are useless for
Xdebugging, no attempt has been made to format this nicely for big
Xmazes; do your debugging with little ones. This part dumps the
Xcontents of each cell of the statlist, the prev, next, status,
Xstreetnum and streetdir fields.
X
X-----------------------------------------------------------------------
X| showlistsum.c -- showlistsummary()
X-----------------------------------------------------------------------
X
XAnother debug routine, calls to which are commented out in main().
XThis and showlistdetail() together dump a detailed printout of the
Xcontents of statlist and the list counts and pointers. This routine
Xdumps the list identifier integer value, the list header pointer
Xcontents, and the list count for each of the isolated, live, dead,
Xstreet, and unused lists, and with the street list items, the
Xstreetnumct global contents as well.
X
X-----------------------------------------------------------------------
X| showmaze.c -- showmaze()
X-----------------------------------------------------------------------
X
XThe routine that does step 10), show the final product, is extremely
Xsimple, just a row by row dump of the cmaze array with trailing
Xnewlines. The little #if condition on PROGRESS is so that the first
Xline of the maze won't get dumped starting in midline when the
Xoptional progress reports are turned on and showmaze() is being used
Xalong with showdbmaze() for debugging in mid run.
X
X-----------------------------------------------------------------------
X| townmain.c -- main(argc,argv)
X-----------------------------------------------------------------------
X
XThis is the main routine for townmaze. It just calls routines to do
Xthe steps listed at the top in order: seeds the random number
Xgenerator, gets the arguments from the command line, allocates array
Xspace, fills the cmaze array, fills the statlist array, seeds the
Xunused cells, seeds the gate cells, seeds the courtyard cells,
Xconnects the streets, runs alleys to the remaining isolated cells,
Xcloses off the extra doors open for each room, closes off any extra
Xopen gates, shows the maze, returns the allocated array space to the
Xfree list, and exits (step 12), uniquely a part of main()).
X
X-----------------------------------------------------------------------
X| usage.c -- usage()
X-----------------------------------------------------------------------
X
XThis routine is called by getargs if any of the command line arguments
Xare incorrect or unparsable, it just dumps a 22 or so line usage
Xmessage on the screen describing the parameters and their purpose
Xbriefly.
X
END_OF_FILE
if test 39151 -ne `wc -c <'townpgmr.doc'`; then
echo shar: \"'townpgmr.doc'\" unpacked with wrong size!
fi
# end of 'townpgmr.doc'
fi
echo shar: End of archive 4 \(of 4\).
cp /dev/null ark4isdone
MISSING=""
for I in 1 2 3 4 ; do
if test ! -f ark${I}isdone ; then
MISSING="${MISSING} ${I}"
fi
done
if test "${MISSING}" = "" ; then
echo You have unpacked all 4 archives.
rm -f ark[1-9]isdone
else
echo You still need to unpack the following archives:
echo " " ${MISSING}
fi
## End of shell archive.
exit 0