home *** CD-ROM | disk | FTP | other *** search
/ 1,001 Nights of Doom / 1001NightsOfDoom1995wickedSensations.iso / nodebild / idbsp10.zip / SAVECNCT.C < prev    next >
C/C++ Source or Header  |  1994-05-28  |  13KB  |  635 lines
  1. /* saveconnect.m */
  2.  
  3. #include "idbsp.h"
  4.  
  5. typedef struct
  6. {
  7.     int        x,y;
  8. } bpoint_t;
  9.  
  10. typedef struct
  11. {
  12.     int        xl, xh, yl, yh;
  13. } bbox_t;
  14.  
  15. typedef struct
  16. {
  17.     bpoint_t    p1, p2;
  18. } bline_t;
  19.  
  20. typedef struct
  21. {
  22.     int            numpoints;
  23.     bbox_t        bounds;
  24.     bpoint_t    *points;
  25. } bchain_t;
  26.  
  27. typedef struct
  28. {
  29.     int        x,y;
  30.     int        dx,dy;
  31. } bdivline_t;
  32.  
  33.  
  34. /* [numsec][numsec] array */
  35. byte        *connections;
  36.  
  37. int            numblines;
  38. bline_t    *blines;
  39.  
  40. int            numsectors;
  41. bbox_t        *secboxes;
  42.  
  43. int            numbchains;
  44. bchain_t    *bchains;
  45.  
  46. void ClearBBox (bbox_t *box)
  47. {
  48.     box->xl = box->yl = INT_MAX;
  49.     box->xh = box->yh = INT_MIN;
  50. }
  51.  
  52. void AddToBBox (bbox_t *box, int x, int y)
  53. {
  54.     if (x < box->xl)
  55.         box->xl = x;
  56.     if (x > box->xh)
  57.         box->xh = x;
  58.     if (y < box->yl)
  59.         box->yl = y;
  60.     if (y > box->yh)
  61.         box->yh = y;
  62. }
  63.  
  64.  
  65. /*
  66. ==================
  67. =
  68. = BPointOnSide
  69. =
  70. = Returns side 0 (front), 1 (back), or -1 (colinear)
  71. ==================
  72. */
  73.  
  74. int    BPointOnSide (bpoint_t *pt, bdivline_t *l)
  75. {
  76.     int        dx,dy;
  77.     int        left, right;
  78.  
  79.     if (!l->dx)
  80.     {
  81.         if (pt->x < l->x)
  82.             return l->dy > 0;
  83.         return l->dy < 0;
  84.     }
  85.     if (!l->dy)
  86.     {
  87.         if (pt->y < l->y)
  88.             return l->dx < 0;
  89.         return l->dx > 0;
  90.     }
  91.  
  92.  
  93.     dx = pt->x - l->x;
  94.     dy = pt->y - l->y;
  95.  
  96.     left = l->dy * dx;
  97.     right = dy * l->dx;
  98.  
  99.     if (right < left)
  100.         return 0;        /* front side */
  101.     return 1;            /* back side */
  102. }
  103.  
  104.  
  105. void DrawBBox (bbox_t *box)
  106. {
  107. /*
  108.     PSmoveto (box->xl,box->yl);
  109.     PSlineto (box->xh,box->yl);
  110.     PSlineto (box->xh,box->yh);
  111.     PSlineto (box->xl,box->yh);
  112.     PSlineto (box->xl,box->yl);
  113.     PSstroke ();
  114.     NXPing ();
  115. */
  116. }
  117.  
  118. void DrawDivline (bdivline_t *li)
  119. {
  120. /*
  121.     PSmoveto (li->x,li->y);
  122.     PSrlineto (li->dx,li->dy);
  123.     PSstroke ();
  124.     NXPing ();
  125. */
  126. }
  127.  
  128. void DrawBChain (bchain_t *ch)
  129. {
  130. /*
  131.     int        i;
  132.  
  133.     PSmoveto (ch->points->x,ch->points->y);
  134.     for (i=1 ; i<ch->numpoints ; i++)
  135.         PSlineto (ch->points[i].x,ch->points[i].y);
  136.     PSstroke ();
  137.     NXPing ();
  138. */
  139. }
  140.  
  141.  
  142. bdivline_t    ends[2], sides[2];
  143. int            end0out, end1out, side0out, side1out;
  144. bbox_t        sweptarea;
  145.  
  146.  
  147. /*
  148. ====================
  149. =
  150. = DoesChainBlock
  151. =
  152. ====================
  153. */
  154.  
  155. boolean DoesChainBlock (bchain_t *chain)
  156. {
  157. /*
  158.  
  159. if a solid line can be walked from one side to the other without going out
  160. an end, the path is blocked
  161.  
  162. */
  163.  
  164.     bpoint_t        *pt;
  165.     int                side, startside;
  166.     int                p;
  167.  
  168. /* don't check if bounds don't intersect */
  169.  
  170.     if (sweptarea.xl > chain->bounds.xh || sweptarea.xh < chain->bounds. xl ||
  171.     sweptarea.yl > chain->bounds. yh || sweptarea.yh < chain->bounds. yl)
  172.         return false;
  173.  
  174.     startside = -1;        /* not started yet */
  175.  
  176.     for (p=0, pt=chain->points ; p<chain->numpoints ; p++, pt++)
  177.     {
  178.     /* find side for pt */
  179. #if 0
  180. if (p>0)
  181. {
  182.     PSmoveto ((pt-1)->x, (pt-1)->y);
  183.     PSlineto (pt->x,pt->y);
  184.     PSstroke ();
  185.     NXPing ();
  186. }
  187. #endif
  188.  
  189.         if (BPointOnSide (pt, &ends[0]) == end0out)
  190.         {
  191.             startside = -1;    /* off end */
  192.             continue;
  193.         }
  194.         if (BPointOnSide (pt, &ends[1]) == end1out)
  195.         {
  196.             startside = -1;    /* off end */
  197.             continue;
  198.         }
  199.         if (BPointOnSide (pt, &sides[0]) == side0out)
  200.             side = 0;
  201.         else if (BPointOnSide (pt, &sides[1]) == side1out)
  202.             side = 1;
  203.         else
  204.             continue;        /* in middle */
  205.  
  206.     /* point is on one side or the other */
  207.         if (startside == -1 || startside == side)
  208.         {
  209.             startside = side;
  210.             continue;
  211.         }
  212.  
  213.     /* opposite of startside */
  214.         return true;        /* totally crossed area */
  215.  
  216.     }
  217.  
  218.     return false;
  219. }
  220.  
  221. /*
  222. ====================
  223. =
  224. = BuildConnections
  225. =
  226. ====================
  227. */
  228.  
  229. enum {si_north, si_east, si_south, si_west};
  230.  
  231. void BuildConnections (void)
  232. {
  233.     int            blockcount, passcount;
  234.     int            i,j, k, s, bn;
  235.     int            x,y;
  236.     bbox_t        *bbox[2];
  237.     int            walls[4];
  238.     bpoint_t    points[2][2];
  239.  
  240. /* look for obscured sectors */
  241.     blockcount = passcount = 0;
  242.     bbox[0] = secboxes;
  243.     printf("\n");
  244.     for (i=0 ; i<numsectors-1 ; i++, bbox[0]++)
  245.     {
  246.         printf("connection #%d of %d\r",i,numsectors-1);
  247.         bbox[1] = bbox[0] + 1;
  248.         if (bbox[0]->xh - bbox[0]->xl < 64 || bbox[0]->yh - bbox[0]->yl < 64)
  249.         {    /* don't bother with small sectors (stairs, doorways, etc) */
  250.             continue;
  251.         }
  252.  
  253.         for (j=i+1 ; j<numsectors ; j++, bbox[1]++)
  254.         {
  255.             if (bbox[1]->xh - bbox[1]->xl < 64 || bbox[1]->yh - bbox[1]->yl < 64)
  256.             {    /* don't bother with small sectors (stairs, doorways, etc) */
  257.                 continue;
  258.             }
  259.             if (bbox[1]->xl <= bbox[0]->xh && bbox[1]->xh >= bbox[0]->xl &&
  260.             bbox[1]->yl <= bbox[0]->yh && bbox[1]->yh >= bbox[0]->yl)
  261.             {    /* touching sectors are never blocked */
  262.                 passcount++;
  263.                 continue;
  264.             }
  265.  
  266.             sweptarea.xl = bbox[0]->xl < bbox[1]->xl ? bbox[0]->xl : bbox[1]->xl;
  267.             sweptarea.xh = bbox[0]->xh > bbox[1]->xh ? bbox[0]->xh : bbox[1]->xh;
  268.             sweptarea.yl = bbox[0]->yl < bbox[1]->yl ? bbox[0]->yl : bbox[1]->yl;
  269.             sweptarea.yh = bbox[0]->yh > bbox[1]->yh ? bbox[0]->yh : bbox[1]->yh;
  270.  
  271. /*
  272.  calculate the swept area between the sectors
  273. */
  274.             for (bn=0 ; bn<2 ; bn++)
  275.             {
  276.                 memset (walls,0,sizeof(walls));
  277.                 if (bbox[bn]->xl <= bbox[!bn]->xl)
  278.                     walls[si_west] = 1;
  279.                 if (bbox[bn]->xh >= bbox[!bn]->xh)
  280.                     walls[si_east] = 1;
  281.                 if (bbox[bn]->yl <= bbox[!bn]->yl)
  282.                     walls[si_south] = 1;
  283.                 if (bbox[bn]->yh >= bbox[!bn]->yh)
  284.                     walls[si_north] = 1;
  285.  
  286.                 for (s=0 ; s<5 ; s++)
  287.                 {
  288.                     switch (s&3)
  289.                     {
  290.                     case si_north:
  291.                         x = bbox[bn]->xl;
  292.                         y = bbox[bn]->yh;
  293.                         break;
  294.                     case si_east:
  295.                         x = bbox[bn]->xh;
  296.                         y = bbox[bn]->yh;
  297.                         break;
  298.                     case si_south:
  299.                         x = bbox[bn]->xh;
  300.                         y = bbox[bn]->yl;
  301.                         break;
  302.                     case si_west:
  303.                         x = bbox[bn]->xl;
  304.                         y = bbox[bn]->yl;
  305.                         break;
  306.                     }
  307.                     if (!walls[(s-1)&3] && walls[s&3])
  308.                     {
  309.                         points[bn][0].x = x;
  310.                         points[bn][0].y = y;
  311.                     }
  312.                     if (walls[(s-1)&3] && !walls[s&3])
  313.                     {
  314.                         points[bn][1].x = x;
  315.                         points[bn][1].y = y;
  316.                     }
  317.                 }
  318.  
  319.                 ends[bn].x = points[bn][0].x;
  320.                 ends[bn].y = points[bn][0].y;
  321.                 ends[bn].dx = points[bn][1].x - points[bn][0].x;
  322.                 ends[bn].dy = points[bn][1].y - points[bn][0].y;
  323.             }
  324.  
  325.             sides[0].x = points[0][0].x;
  326.             sides[0].y = points[0][0].y;
  327.             sides[0].dx = points[1][1].x - points[0][0].x;
  328.             sides[0].dy = points[1][1].y - points[0][0].y;
  329.  
  330.             sides[1].x = points[0][1].x;
  331.             sides[1].y = points[0][1].y;
  332.             sides[1].dx = points[1][0].x - points[0][1].x;
  333.             sides[1].dy = points[1][0].y - points[0][1].y;
  334.  
  335.             end0out = !BPointOnSide (&points[1][0], &ends[0]);
  336.             end1out = !BPointOnSide (&points[0][0], &ends[1]);
  337.             side0out = !BPointOnSide (&points[0][1], &sides[0]);
  338.             side1out = !BPointOnSide (&points[0][0], &sides[1]);
  339.  
  340. /*
  341.  look for a line change that covers the swept area
  342. */
  343.             for (k=0 ; k<numbchains ; k++)
  344.             {
  345.                 if (!DoesChainBlock (&bchains[k]))
  346.                     continue;
  347.                 blockcount++;
  348.                 connections[i*numsectors+j] = connections[j*numsectors+i] = 1;
  349. /*
  350.                 if (draw)
  351.                 {
  352.                 EraseWindow ();
  353.                 DrawBBox (bbox[0]);
  354.                 DrawBBox (bbox[1]);
  355.                 DrawDivline (&ends[0]);
  356.                 DrawDivline (&ends[1]);
  357.                 DrawDivline (&sides[0]);
  358.                 DrawDivline (&sides[1]);
  359.                 DrawBChain (&bchains[k]);
  360.                 }
  361. */
  362.                 goto blocked;
  363.             }
  364.  
  365. /* nothing definately blocked the path */
  366.             passcount++;
  367. blocked: ;
  368.         }
  369.     }
  370.     printf ("passcount: %i\nblockcount: %i\n",passcount, blockcount);
  371. }
  372.  
  373.  
  374. /*
  375. ====================
  376. =
  377. = BuildBlockingChains
  378. =
  379. ====================
  380. */
  381.  
  382. void BuildBlockingChains (void)
  383. {
  384.     boolean    *used;
  385.     int            i,j;
  386.     bpoint_t    *temppoints, *pt_p;
  387.     bline_t    *li1, *li2;
  388. /*    id            chains_i; */
  389.     STORAGE *chains_i;
  390.     bchain_t    bch;
  391.     int            cx, cy;
  392.  
  393.     used = alloca (numblines*sizeof (*used));
  394.     memset (used,0,numblines*sizeof (*used));
  395.     temppoints = alloca (numblines*sizeof (*temppoints));
  396. /*
  397.     chains_i = [[Storage alloc]
  398.                     initCount:        0
  399.                     elementSize:    sizeof(bchain_t)
  400.                     description:    NULL];
  401. */
  402.     chains_i = (STORAGE *)SafeMalloc(sizeof(STORAGE));
  403.     chains_i->data = (bchain_t *)SafeMalloc(sizeof(bchain_t));
  404.     chains_i->count = 0;
  405.     chains_i->size = sizeof(bchain_t);
  406.  
  407.     printf("\n");
  408.     li1 = blines;
  409.     for (i=0 ; i<numblines ; i++, li1++)
  410.     {
  411.         printf("bline #%d of %d\r",i,numblines);
  412.         if (used[i])
  413.             continue;
  414.         used[i] = true;
  415.  
  416.         /* start a new chain */
  417.         pt_p = temppoints;
  418.         pt_p->x = li1->p1.x;
  419.         pt_p->y = li1->p1.y;
  420.         pt_p++;
  421.         pt_p->x = cx = li1->p2.x;
  422.         pt_p->y = cy = li1->p2.y;
  423.         pt_p++;
  424.  
  425.         ClearBBox (&bch.bounds);
  426.         AddToBBox (&bch.bounds, li1->p1.x, li1->p1.y);
  427.         AddToBBox (&bch.bounds, cx, cy);
  428.  
  429.         /* look for connected lines */
  430.         do
  431.         {
  432.             li2 = li1+1;
  433.             for (j=i+1 ; j<numblines ; j++,li2++)
  434.                 if (!used[j] && li2->p1.x == cx && li2->p1.y == cy)
  435.                     break;
  436.  
  437.             if (j==numblines)
  438.                 break;        /* no more lines in chain */
  439.  
  440.         /* add to chain */
  441.             used[j] = true;
  442.             pt_p->x = cx = li2->p2.x;
  443.             pt_p->y = cy = li2->p2.y;
  444.             pt_p++;
  445.             AddToBBox (&bch.bounds, cx, cy);
  446.         } while (1);
  447.  
  448. /* save the block chain */
  449.         bch.numpoints = pt_p - temppoints;
  450.         bch.points = (bpoint_t *)malloc (bch.numpoints*sizeof(*bch.points));
  451.         memcpy (bch.points, temppoints, bch.numpoints*sizeof(*bch.points));
  452. /*        [chains_i addElement: &bch]; */
  453.         memcpy((bchain_t *)chains_i->data + chains_i->count, &bch, sizeof(bchain_t));
  454.         chains_i->count += 1;
  455.         chains_i->data = (bchain_t *)realloc(chains_i->data,
  456.                                             sizeof(bchain_t) * (chains_i->count + 1));
  457. /*DrawBChain (&bch); */
  458.     }
  459.  
  460. /*
  461.     numbchains = [chains_i count];
  462.     bchains = [chains_i elementAt:0];
  463. */
  464.     numbchains = chains_i->count;
  465.     bchains = chains_i->data;
  466. }
  467.  
  468.  
  469. /*
  470. ====================
  471. =
  472. = ProcessConnections
  473. =
  474. ====================
  475. */
  476.  
  477. void ProcessConnections (void)
  478. {
  479.     int                    i, s, wlcount, count;
  480.     bbox_t                *secbox;
  481. /*    id                    lines; */
  482.     STORAGE *lines;
  483.     worldline_t        *wl;
  484.     mapvertex_t        *vt;
  485.     maplinedef_t        *p;
  486.     mapsidedef_t        *sd;
  487.     bline_t            bline;
  488.     int                    sec;
  489.     int RonsLines=0;
  490.  
  491. /*
  492.     numsectors = [secstore_i count];
  493.     wlcount = [linestore_i count];
  494. */
  495.  
  496.     numsectors = secstore_i->count;
  497.     wlcount = linestore_i->count;
  498.  
  499.     connections = (unsigned char *)malloc (numsectors*numsectors+8); /* allow rounding to bytes */
  500.     memset (connections, 0, numsectors*numsectors);
  501.  
  502.     secboxes = secbox = (bbox_t *)malloc (numsectors*sizeof(bbox_t));
  503.     for (i=0 ; i<numsectors ; i++, secbox++)
  504.         ClearBBox (secbox);
  505.  
  506. /*
  507.  calculate bounding boxes for all sectors
  508.  
  509.     count = [ldefstore_i count];
  510.     p = [ldefstore_i elementAt:0];
  511.     vt = [mapvertexstore_i elementAt:0];
  512. */
  513.  
  514.     count = ldefstore_i->count;
  515.     p = ldefstore_i->data;
  516.     vt = mapvertexstore_i->data;
  517.     printf("\n");
  518.     for (i=0 ; i<count ; i++, p++)
  519.     {
  520.         printf("BBox #%d of %d\r",i,count);
  521.         for (s=0 ; s<1 ; s++)
  522.         {
  523.             if (p->sidenum[s] == -1)
  524.                 continue;            /* no back side */
  525.             /* add both points to sector bounding box */
  526. /*        sd = (mapsidedef_t *)[sdefstore_i elementAt: p->sidenum[s]]; */
  527.             sd = (mapsidedef_t *)sdefstore_i->data + p->sidenum[s];
  528.             sec = sd->sector;
  529.             AddToBBox (&secboxes[sec], vt[p->v1].x, vt[p->v1].y);
  530.             AddToBBox (&secboxes[sec], vt[p->v2].x, vt[p->v2].y);
  531.         }
  532.     }
  533.  
  534. /*
  535.  make a list of only the solid lines
  536. */
  537. /*
  538.     lines = [[Storage alloc]
  539.                     initCount:        0
  540.                     elementSize:    sizeof(bline)
  541.                     description:    NULL];
  542. */
  543. /*
  544.     lines = SafeMalloc(sizeof(STORAGE));
  545.     lines->data = SafeMalloc(sizeof(bline));
  546.     lines->count = 0;
  547.     lines->size = sizeof(bline);
  548. */
  549.  
  550. /*    wl = [linestore_i elementAt: 0]; */
  551.     printf("\n");
  552.     wl = linestore_i->data;
  553.     for (i=0; i<wlcount; wl++,i++)
  554.         {
  555.         if (wl->flags & ML_TWOSIDED)
  556.             continue;
  557.         RonsLines++;
  558.         }
  559.  
  560.     lines = (STORAGE *)SafeMalloc(sizeof(STORAGE));
  561.     lines->data = (bline_t *)SafeCalloc(RonsLines,sizeof(bline));
  562.     lines->count = 0;
  563.     lines->size = sizeof(bline);
  564.  
  565.     wl = linestore_i->data;
  566.     for ( i=0 ; i<wlcount ; wl++,i++)
  567.     {
  568.         printf("Line #%d of %d\r",i,wlcount);
  569.         if (wl->flags & ML_TWOSIDED)
  570.             continue;            /* don't add two sided lines */
  571.         bline.p1.x = wl->p1.x;
  572.         bline.p1.y = wl->p1.y;
  573.         bline.p2.x = wl->p2.x;
  574.         bline.p2.y = wl->p2.y;
  575. /*        [lines addElement: &bline]; */
  576.         memcpy((bline_t *)lines->data + lines->count, &bline, sizeof(bline));
  577.         lines->count += 1;
  578. /*
  579.         lines->data = (bline_t *)realloc(lines->data,
  580.                                     sizeof(bline_t) + (lines->count + 1));
  581. */
  582.     }
  583.  
  584. /*
  585.     blines = [lines elementAt: 0];
  586.     numblines = [lines count];
  587. */
  588.  
  589.     blines = lines->data;
  590.     numblines = lines->count;
  591.  
  592. /*
  593.  build blocking chains
  594. */
  595.     printf("\nBuildBlockingChains\n");
  596.     BuildBlockingChains ();
  597.  
  598. /*
  599.  build connection list
  600. */
  601.     printf("\nBuildConnections\n");
  602.     BuildConnections ();
  603. }
  604.  
  605.  
  606. /*
  607. =================
  608. =
  609. = OutputConnections
  610. =
  611. =================
  612. */
  613.  
  614. void OutputConnections (void)
  615. {
  616.     int        i;
  617.     int        bytes;
  618.     char    *cons;
  619.     char    *bits;
  620.  
  621.     cons = connections;
  622.     bytes = (numsectors*numsectors+7)/8;
  623.     bits = (char *)malloc(bytes);
  624.  
  625.     for (i=0 ; i<bytes ; i++)
  626.     {
  627.         bits[i] = cons[0] + (cons[1]<<1) + (cons[2]<<2) + (cons[3]<<3) + (cons[4]<<4) + (cons[5]<<5) + (cons[6]<<6) + (cons[7]<<7);
  628.         cons +=8;
  629.     }
  630.  
  631. /*    [wad_i addName: "reject" data:bits size:bytes]; */
  632.     addName("reject", bits, bytes);
  633.     printf ("reject: %i\n",bytes);
  634. }
  635.