1: /*      $NetBSD: hack.mklev.c,v 1.6 2003/04/02 18:36:38 jsm Exp $    */
    2: 
    3: /*
    4:  * Copyright (c) 1985, Stichting Centrum voor Wiskunde en Informatica,
    5:  * Amsterdam
    6:  * All rights reserved.
    7:  *
    8:  * Redistribution and use in source and binary forms, with or without
    9:  * modification, are permitted provided that the following conditions are
   10:  * met:
   11:  *
   12:  * - Redistributions of source code must retain the above copyright notice,
   13:  * this list of conditions and the following disclaimer.
   14:  *
   15:  * - Redistributions in binary form must reproduce the above copyright
   16:  * notice, this list of conditions and the following disclaimer in the
   17:  * documentation and/or other materials provided with the distribution.
   18:  *
   19:  * - Neither the name of the Stichting Centrum voor Wiskunde en
   20:  * Informatica, nor the names of its contributors may be used to endorse or
   21:  * promote products derived from this software without specific prior
   22:  * written permission.
   23:  *
   24:  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
   25:  * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
   26:  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
   27:  * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
   28:  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
   29:  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
   30:  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
   31:  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
   32:  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
   33:  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
   34:  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
   35:  */
   36: 
   37: /*
   38:  * Copyright (c) 1982 Jay Fenlason <hack@gnu.org>
   39:  * All rights reserved.
   40:  *
   41:  * Redistribution and use in source and binary forms, with or without
   42:  * modification, are permitted provided that the following conditions
   43:  * are met:
   44:  * 1. Redistributions of source code must retain the above copyright
   45:  *    notice, this list of conditions and the following disclaimer.
   46:  * 2. Redistributions in binary form must reproduce the above copyright
   47:  *    notice, this list of conditions and the following disclaimer in the
   48:  *    documentation and/or other materials provided with the distribution.
   49:  * 3. The name of the author may not be used to endorse or promote products
   50:  *    derived from this software without specific prior written permission.
   51:  *
   52:  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
   53:  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
   54:  * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
   55:  * THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
   56:  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
   57:  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
   58:  * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
   59:  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
   60:  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
   61:  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
   62:  */
   63: 
   64: #include <sys/cdefs.h>
   65: #ifndef lint
   66: __RCSID("$NetBSD: hack.mklev.c,v 1.6 2003/04/02 18:36:38 jsm Exp $");
   67: #endif                          /* not lint */
   68: 
   69: #include <unistd.h>
   70: #include <stdlib.h>
   71: #include "hack.h"
   72: #include "extern.h"
   73: 
   74: #define somex() ((random()%(croom->hx-croom->lx+1))+croom->lx)
   75: #define somey() ((random()%(croom->hy-croom->ly+1))+croom->ly)
   76: 
   77: #include "def.mkroom.h"
   78: #define XLIM    4          /* define minimum required space around a
   79:                                  * room */
   80: #define YLIM    3
   81: boolean         secret;         /* TRUE while making a vault: increase
   82:                                  * [XY]LIM */
   83: int             smeq[MAXNROFROOMS + 1];
   84: int             doorindex;
   85: struct rm       zerorm;
   86: schar           nxcor;
   87: boolean         goldseen;
   88: int             nroom;
   89: 
   90: /* Definitions used by makerooms() and addrs() */
   91: #define MAXRS   50                /* max lth of temp rectangle table -
   92:                                  * arbitrary */
   93: struct rectangle {
   94:         xchar           rlx, rly, rhx, rhy;
   95: }               rs[MAXRS + 1];
   96: int             rscnt, rsmax;   /* 0..rscnt-1: currently under consideration */
   97: /* rscnt..rsmax: discarded */
   98: 
   99: void
  100: makelevel()
  101: {
  102:         struct mkroom  *croom, *troom;
  103:         unsigned        tryct;
  104:         int x, y;
  105: 
  106:         nroom = 0;
  107:         doorindex = 0;
  108:         rooms[0].hx = -1;      /* in case we are in a maze */
  109: 
  110:         for (x = 0; x < COLNO; x++)
  111:                 for (y = 0; y < ROWNO; y++)
  112:                         levl[x][y] = zerorm;
  113: 
  114:         oinit();               /* assign level dependent obj probabilities */
  115: 
  116:         if (dlevel >= rn1(3, 26)) {    /* there might be several mazes */
  117:                 makemaz();
  118:                 return;
  119:         }
  120:         /* construct the rooms */
  121:         nroom = 0;
  122:         secret = FALSE;
  123:         (void) makerooms();
  124: 
  125:         /* construct stairs (up and down in different rooms if possible) */
  126:         croom = &rooms[rn2(nroom)];
  127:         xdnstair = somex();
  128:         ydnstair = somey();
  129:         levl[xdnstair][ydnstair].scrsym = '>';
  130:         levl[xdnstair][ydnstair].typ = STAIRS;
  131:         if (nroom > 1) {
  132:                 troom = croom;
  133:                 croom = &rooms[rn2(nroom - 1)];
  134:                 if (croom >= troom)
  135:                         croom++;
  136:         }
  137:         xupstair = somex();    /* %% < and > might be in the same place */
  138:         yupstair = somey();
  139:         levl[xupstair][yupstair].scrsym = '<';
  140:         levl[xupstair][yupstair].typ = STAIRS;
  141: 
  142:         /* for each room: put things inside */
  143:         for (croom = rooms; croom->hx > 0; croom++) {
  144: 
  145:                 /* put a sleeping monster inside */
  146:                 /*
  147:                  * Note: monster may be on the stairs. This cannot be
  148:                  * avoided: maybe the player fell through a trapdoor while a
  149:                  * monster was on the stairs. Conclusion: we have to check
  150:                  * for monsters on the stairs anyway.
  151:                  */
  152:                 if (!rn2(3))
  153:                         (void)
  154:                                 makemon((struct permonst *) 0, somex(), somey());
  155: 
  156:                 /* put traps and mimics inside */
  157:                 goldseen = FALSE;
  158:                 while (!rn2(8 - (dlevel / 6)))
  159:                         mktrap(0, 0, croom);
  160:                 if (!goldseen && !rn2(3))
  161:                         mkgold(0L, somex(), somey());
  162:                 if (!rn2(3)) {
  163:                         (void) mkobj_at(0, somex(), somey());
  164:                         tryct = 0;
  165:                         while (!rn2(5)) {
  166:                                 if (++tryct > 100) {
  167:                                         printf("tryct overflow4\n");
  168:                                         break;
  169:                                 }
  170:                                 (void) mkobj_at(0, somex(), somey());
  171:                         }
  172:                 }
  173:         }
  174: 
  175:         qsort((char *) rooms, nroom, sizeof(struct mkroom), comp);
  176:         makecorridors();
  177:         make_niches();
  178: 
  179:         /* make a secret treasure vault, not connected to the rest */
  180:         if (nroom <= (2 * MAXNROFROOMS / 3))
  181:                 if (rn2(3)) {
  182:                         troom = &rooms[nroom];
  183:                         secret = TRUE;
  184:                         if (makerooms()) {
  185:                                 troom->rtype = VAULT;       /* treasure vault */
  186:                                 for (x = troom->lx; x <= troom->hx; x++)
  187:                                         for (y = troom->ly; y <= troom->hy; y++)
  188:                                                 mkgold((long) (rnd(dlevel * 100) + 50), x, y);
  189:                                 if (!rn2(3))
  190:                                         makevtele();
  191:                         }
  192:                 }
  193: #ifndef QUEST
  194: #ifdef WIZARD
  195:         if (wizard && getenv("SHOPTYPE"))
  196:                 mkshop();
  197:         else
  198: #endif  /* WIZARD */
  199:         if (dlevel > 1 && dlevel < 20 && rn2(dlevel) < 3)
  200:                 mkshop();
  201:         else if (dlevel > 6 && !rn2(7))
  202:                 mkzoo(ZOO);
  203:         else if (dlevel > 9 && !rn2(5))
  204:                 mkzoo(BEEHIVE);
  205:         else if (dlevel > 11 && !rn2(6))
  206:                 mkzoo(MORGUE);
  207:         else if (dlevel > 18 && !rn2(6))
  208:                 mkswamp();
  209: #endif  /* QUEST */
  210: }
  211: 
  212: int
  213: makerooms()
  214: {
  215:         struct rectangle *rsp;
  216:         int             lx, ly, hx, hy, lowx, lowy, hix, hiy, dx, dy;
  217:         int             tryct = 0, xlim, ylim;
  218: 
  219:         /* init */
  220:         xlim = XLIM + secret;
  221:         ylim = YLIM + secret;
  222:         if (nroom == 0) {
  223:                 rsp = rs;
  224:                 rsp->rlx = rsp->rly = 0;
  225:                 rsp->rhx = COLNO - 1;
  226:                 rsp->rhy = ROWNO - 1;
  227:                 rsmax = 1;
  228:         }
  229:         rscnt = rsmax;
  230: 
  231:         /* make rooms until satisfied */
  232:         while (rscnt > 0 && nroom < MAXNROFROOMS - 1) {
  233:                 if (!secret && nroom > (MAXNROFROOMS / 3) &&
  234:                     !rn2((MAXNROFROOMS - nroom) * (MAXNROFROOMS - nroom)))
  235:                         return (0);
  236: 
  237:                 /* pick a rectangle */
  238:                 rsp = &rs[rn2(rscnt)];
  239:                 hx = rsp->rhx;
  240:                 hy = rsp->rhy;
  241:                 lx = rsp->rlx;
  242:                 ly = rsp->rly;
  243: 
  244:                 /* find size of room */
  245:                 if (secret)
  246:                         dx = dy = 1;
  247:                 else {
  248:                         dx = 2 + rn2((hx - lx - 8 > 20) ? 12 : 8);
  249:                         dy = 2 + rn2(4);
  250:                         if (dx * dy > 50)
  251:                                 dy = 50 / dx;
  252:                 }
  253: 
  254:                 /* look whether our room will fit */
  255:                 if (hx - lx < dx + dx / 2 + 2 * xlim || hy - ly < dy + dy / 3 + 2 * ylim) {
  256:                         /* no, too small */
  257:                         /* maybe we throw this area out */
  258:                         if (secret || !rn2(MAXNROFROOMS + 1 - nroom - tryct)) {
  259:                                 rscnt--;
  260:                                 rs[rsmax] = *rsp;
  261:                                 *rsp = rs[rscnt];
  262:                                 rs[rscnt] = rs[rsmax];
  263:                                 tryct = 0;
  264:                         } else
  265:                                 tryct++;
  266:                         continue;
  267:                 }
  268:                 lowx = lx + xlim + rn2(hx - lx - dx - 2 * xlim + 1);
  269:                 lowy = ly + ylim + rn2(hy - ly - dy - 2 * ylim + 1);
  270:                 hix = lowx + dx;
  271:                 hiy = lowy + dy;
  272: 
  273:                 if (maker(lowx, dx, lowy, dy)) {
  274:                         if (secret)
  275:                                 return (1);
  276:                         addrs(lowx - 1, lowy - 1, hix + 1, hiy + 1);
  277:                         tryct = 0;
  278:                 } else if (tryct++ > 100)
  279:                         break;
  280:         }
  281:         return (0);            /* failed to make vault - very strange */
  282: }
  283: 
  284: void
  285: addrs(lowx, lowy, hix, hiy)
  286:         int             lowx, lowy, hix, hiy;
  287: {
  288:         struct rectangle *rsp;
  289:         int             lx, ly, hx, hy, xlim, ylim;
  290:         boolean         discarded;
  291: 
  292:         xlim = XLIM + secret;
  293:         ylim = YLIM + secret;
  294: 
  295:         /* walk down since rscnt and rsmax change */
  296:         for (rsp = &rs[rsmax - 1]; rsp >= rs; rsp--) {
  297: 
  298:                 if ((lx = rsp->rlx) > hix || (ly = rsp->rly) > hiy ||
  299:                     (hx = rsp->rhx) < lowx || (hy = rsp->rhy) < lowy)
  300:                         continue;
  301:                 if ((discarded = (rsp >= &rs[rscnt]))) {
  302:                         *rsp = rs[--rsmax];
  303:                 } else {
  304:                         rsmax--;
  305:                         rscnt--;
  306:                         *rsp = rs[rscnt];
  307:                         if (rscnt != rsmax)
  308:                                 rs[rscnt] = rs[rsmax];
  309:                 }
  310:                 if (lowy - ly > 2 * ylim + 4)
  311:                         addrsx(lx, ly, hx, lowy - 2, discarded);
  312:                 if (lowx - lx > 2 * xlim + 4)
  313:                         addrsx(lx, ly, lowx - 2, hy, discarded);
  314:                 if (hy - hiy > 2 * ylim + 4)
  315:                         addrsx(lx, hiy + 2, hx, hy, discarded);
  316:                 if (hx - hix > 2 * xlim + 4)
  317:                         addrsx(hix + 2, ly, hx, hy, discarded);
  318:         }
  319: }
  320: 
  321: void
  322: addrsx(lx, ly, hx, hy, discarded)
  323:         int             lx, ly, hx, hy;
  324:         boolean         discarded;     /* piece of a discarded area */
  325: {
  326:         struct rectangle *rsp;
  327: 
  328:         /* check inclusions */
  329:         for (rsp = rs; rsp < &rs[rsmax]; rsp++) {
  330:                 if (lx >= rsp->rlx && hx <= rsp->rhx &&
  331:                     ly >= rsp->rly && hy <= rsp->rhy)
  332:                         return;
  333:         }
  334: 
  335:         /* make a new entry */
  336:         if (rsmax >= MAXRS) {
  337: #ifdef WIZARD
  338:                 if (wizard)
  339:                         pline("MAXRS may be too small.");
  340: #endif  /* WIZARD */
  341:                 return;
  342:         }
  343:         rsmax++;
  344:         if (!discarded) {
  345:                 *rsp = rs[rscnt];
  346:                 rsp = &rs[rscnt];
  347:                 rscnt++;
  348:         }
  349:         rsp->rlx = lx;
  350:         rsp->rly = ly;
  351:         rsp->rhx = hx;
  352:         rsp->rhy = hy;
  353: }
  354: 
  355: int
  356: comp(vx, vy)
  357:         const void *vx, *vy;
  358: {
  359:         const struct mkroom  *x = vx, *y = vy;
  360:         if (x->lx < y->lx)
  361:                 return (-1);
  362:         return (x->lx > y->lx);
  363: }
  364: 
  365: coord
  366: finddpos(int xl, int yl, int xh, int yh)
  367: {
  368:         coord           ff;
  369:         int x, y;
  370: 
  371:         x = (xl == xh) ? xl : (xl + rn2(xh - xl + 1));
  372:         y = (yl == yh) ? yl : (yl + rn2(yh - yl + 1));
  373:         if (okdoor(x, y))
  374:                 goto gotit;
  375: 
  376:         for (x = xl; x <= xh; x++)
  377:                 for (y = yl; y <= yh; y++)
  378:                         if (okdoor(x, y))
  379:                                 goto gotit;
  380: 
  381:         for (x = xl; x <= xh; x++)
  382:                 for (y = yl; y <= yh; y++)
  383:                         if (levl[x][y].typ == DOOR || levl[x][y].typ == SDOOR)
  384:                                 goto gotit;
  385:         /* cannot find something reasonable -- strange */
  386:         x = xl;
  387:         y = yh;
  388: gotit:
  389:         ff.x = x;
  390:         ff.y = y;
  391:         return (ff);
  392: }
  393: 
  394: /* see whether it is allowable to create a door at [x,y] */
  395: int
  396: okdoor(x, y)
  397:         int x, y;
  398: {
  399:         if (levl[x - 1][y].typ == DOOR || levl[x + 1][y].typ == DOOR ||
  400:             levl[x][y + 1].typ == DOOR || levl[x][y - 1].typ == DOOR ||
  401:             levl[x - 1][y].typ == SDOOR || levl[x + 1][y].typ == SDOOR ||
  402:             levl[x][y - 1].typ == SDOOR || levl[x][y + 1].typ == SDOOR ||
  403:             (levl[x][y].typ != HWALL && levl[x][y].typ != VWALL) ||
  404:             doorindex >= DOORMAX)
  405:                 return (0);
  406:         return (1);
  407: }
  408: 
  409: void
  410: dodoor(x, y, aroom)
  411:         int x, y;
  412:         struct mkroom  *aroom;
  413: {
  414:         if (doorindex >= DOORMAX) {
  415:                 impossible("DOORMAX exceeded?");
  416:                 return;
  417:         }
  418:         if (!okdoor(x, y) && nxcor)
  419:                 return;
  420:         dosdoor(x, y, aroom, rn2(8) ? DOOR : SDOOR);
  421: }
  422: 
  423: void
  424: dosdoor(x, y, aroom, type)
  425:         int x, y;
  426:         struct mkroom  *aroom;
  427:         int type;
  428: {
  429:         struct mkroom  *broom;
  430:         int tmp;
  431: 
  432:         if (!IS_WALL(levl[x][y].typ))  /* avoid SDOORs with '+' as scrsym */
  433:                 type = DOOR;
  434:         levl[x][y].typ = type;
  435:         if (type == DOOR)
  436:                 levl[x][y].scrsym = '+';
  437:         aroom->doorct++;
  438:         broom = aroom + 1;
  439:         if (broom->hx < 0)
  440:                 tmp = doorindex;
  441:         else
  442:                 for (tmp = doorindex; tmp > broom->fdoor; tmp--)
  443:                         doors[tmp] = doors[tmp - 1];
  444:         doorindex++;
  445:         doors[tmp].x = x;
  446:         doors[tmp].y = y;
  447:         for (; broom->hx >= 0; broom++)
  448:                 broom->fdoor++;
  449: }
  450: 
  451: /* Only called from makerooms() */
  452: int
  453: maker(lowx, ddx, lowy, ddy)
  454:         schar           lowx, ddx, lowy, ddy;
  455: {
  456:         struct mkroom  *croom;
  457:         int x, y, hix = lowx + ddx, hiy = lowy + ddy;
  458:         int xlim = XLIM + secret, ylim = YLIM + secret;
  459: 
  460:         if (nroom >= MAXNROFROOMS)
  461:                 return (0);
  462:         if (lowx < XLIM)
  463:                 lowx = XLIM;
  464:         if (lowy < YLIM)
  465:                 lowy = YLIM;
  466:         if (hix > COLNO - XLIM - 1)
  467:                 hix = COLNO - XLIM - 1;
  468:         if (hiy > ROWNO - YLIM - 1)
  469:                 hiy = ROWNO - YLIM - 1;
  470: chk:
  471:         if (hix <= lowx || hiy <= lowy)
  472:                 return (0);
  473: 
  474:         /* check area around room (and make room smaller if necessary) */
  475:         for (x = lowx - xlim; x <= hix + xlim; x++) {
  476:                 for (y = lowy - ylim; y <= hiy + ylim; y++) {
  477:                         if (levl[x][y].typ) {
  478: #ifdef WIZARD
  479:                                 if (wizard && !secret)
  480:                                         pline("Strange area [%d,%d] in maker().", x, y);
  481: #endif  /* WIZARD */
  482:                                 if (!rn2(3))
  483:                                         return (0);
  484:                                 if (x < lowx)
  485:                                         lowx = x + xlim + 1;
  486:                                 else
  487:                                         hix = x - xlim - 1;
  488:                                 if (y < lowy)
  489:                                         lowy = y + ylim + 1;
  490:                                 else
  491:                                         hiy = y - ylim - 1;
  492:                                 goto chk;
  493:                         }
  494:                 }
  495:         }
  496: 
  497:         croom = &rooms[nroom];
  498: 
  499:         /* on low levels the room is lit (usually) */
  500:         /* secret vaults are always lit */
  501:         if ((rnd(dlevel) < 10 && rn2(77)) || (ddx == 1 && ddy == 1)) {
  502:                 for (x = lowx - 1; x <= hix + 1; x++)
  503:                         for (y = lowy - 1; y <= hiy + 1; y++)
  504:                                 levl[x][y].lit = 1;
  505:                 croom->rlit = 1;
  506:         } else
  507:                 croom->rlit = 0;
  508:         croom->lx = lowx;
  509:         croom->hx = hix;
  510:         croom->ly = lowy;
  511:         croom->hy = hiy;
  512:         croom->rtype = croom->doorct = croom->fdoor = 0;
  513: 
  514:         for (x = lowx - 1; x <= hix + 1; x++)
  515:                 for (y = lowy - 1; y <= hiy + 1; y += (hiy - lowy + 2)) {
  516:                         levl[x][y].scrsym = '-';