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