home *** CD-ROM | disk | FTP | other *** search
/ Doom I/II Collection / DM12.ISO / edit / doombsp / savecnct.m < prev    next >
Text File  |  1994-04-06  |  11KB  |  556 lines
  1. // saveconnect.m
  2.  
  3. #import "doombsp.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 = MAXINT;
  49.     box->xh = box->yh = MININT;
  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.     PSmoveto (box->xl,box->yl);
  108.     PSlineto (box->xh,box->yl);
  109.     PSlineto (box->xh,box->yh);
  110.     PSlineto (box->xl,box->yh);
  111.     PSlineto (box->xl,box->yl);
  112.     PSstroke ();
  113.     NXPing ();
  114. }
  115.  
  116. void DrawDivline (bdivline_t *li)
  117. {
  118.     PSmoveto (li->x,li->y);
  119.     PSrlineto (li->dx,li->dy);
  120.     PSstroke ();
  121.     NXPing ();
  122. }
  123.  
  124. void DrawBChain (bchain_t *ch)
  125. {
  126.     int        i;
  127.     
  128.     PSmoveto (ch->points->x,ch->points->y);
  129.     for (i=1 ; i<ch->numpoints ; i++)
  130.         PSlineto (ch->points[i].x,ch->points[i].y);
  131.     PSstroke ();
  132.     NXPing ();
  133. }
  134.  
  135.  
  136. bdivline_t    ends[2], sides[2];
  137. int            end0out, end1out, side0out, side1out;
  138. bbox_t        sweptarea;
  139.  
  140.  
  141. /*
  142. ====================
  143. =
  144. = DoesChainBlock
  145. =
  146. ====================
  147. */
  148.  
  149. boolean DoesChainBlock (bchain_t *chain)
  150. {
  151. /*
  152.  
  153. if a solid line can be walked from one side to the other without going out
  154. an end, the path is blocked
  155.  
  156. */
  157.  
  158.     bpoint_t        *pt;
  159.     int                side, startside;
  160.     int                p;
  161.     
  162. // don't check if bounds don't intersect
  163.  
  164.     if (sweptarea.xl > chain->bounds.xh || sweptarea.xh < chain->bounds. xl ||
  165.     sweptarea.yl > chain->bounds. yh || sweptarea.yh < chain->bounds. yl)
  166.         return false;
  167.         
  168.     startside = -1;        // not started yet
  169.     
  170.     for (p=0, pt=chain->points ; p<chain->numpoints ; p++, pt++)
  171.     {
  172.     // find side for pt
  173. #if 0
  174. if (p>0)
  175. {
  176.     PSmoveto ((pt-1)->x, (pt-1)->y);
  177.     PSlineto (pt->x,pt->y);
  178.     PSstroke ();
  179.     NXPing ();
  180. }
  181. #endif
  182.  
  183.         if (BPointOnSide (pt, &ends[0]) == end0out)
  184.         {
  185.             startside = -1;    // off end
  186.             continue;
  187.         }
  188.         if (BPointOnSide (pt, &ends[1]) == end1out)
  189.         {
  190.             startside = -1;    // off end
  191.             continue;
  192.         }
  193.         if (BPointOnSide (pt, &sides[0]) == side0out)
  194.             side = 0;
  195.         else if (BPointOnSide (pt, &sides[1]) == side1out)
  196.             side = 1;
  197.         else
  198.             continue;        // in middle
  199.                     
  200.     // point is on one side or the other
  201.         if (startside == -1 || startside == side)
  202.         {
  203.             startside = side;
  204.             continue;
  205.         }
  206.                                 
  207.     // opposite of startside
  208.         return true;        // totally crossed area
  209.             
  210.     }
  211.  
  212.     return false;
  213. }
  214.  
  215. /*
  216. ====================
  217. =
  218. = BuildConnections
  219. =
  220. ====================
  221. */
  222.  
  223. enum {si_north, si_east, si_south, si_west};
  224.  
  225. void BuildConnections (void)
  226. {
  227.     int            blockcount, passcount;
  228.     int            i,j, k, s, bn;
  229.     int            x,y;
  230.     bbox_t        *bbox[2];
  231.     int            walls[4];
  232.     bpoint_t    points[2][2];
  233.         
  234. // look for obscured sectors
  235.     blockcount = passcount = 0;
  236.     bbox[0] = secboxes;
  237.     for (i=0 ; i<numsectors-1 ; i++, bbox[0]++)
  238.     {
  239.         bbox[1] = bbox[0] + 1;
  240.         if (bbox[0]->xh - bbox[0]->xl < 64 || bbox[0]->yh - bbox[0]->yl < 64)
  241.         {    // don't bother with small sectors (stairs, doorways, etc)
  242.             continue;
  243.         }
  244.  
  245.         for (j=i+1 ; j<numsectors ; j++, bbox[1]++)
  246.         {
  247.             if (bbox[1]->xh - bbox[1]->xl < 64 || bbox[1]->yh - bbox[1]->yl < 64)
  248.             {    // don't bother with small sectors (stairs, doorways, etc)
  249.                 continue;
  250.             }
  251.             if (bbox[1]->xl <= bbox[0]->xh && bbox[1]->xh >= bbox[0]->xl &&
  252.             bbox[1]->yl <= bbox[0]->yh && bbox[1]->yh >= bbox[0]->yl)
  253.             {    // touching sectors are never blocked
  254.                 passcount++;
  255.                 continue;
  256.             }
  257.  
  258.             sweptarea.xl = bbox[0]->xl < bbox[1]->xl ? bbox[0]->xl : bbox[1]->xl;
  259.             sweptarea.xh = bbox[0]->xh > bbox[1]->xh ? bbox[0]->xh : bbox[1]->xh;
  260.             sweptarea.yl = bbox[0]->yl < bbox[1]->yl ? bbox[0]->yl : bbox[1]->yl;
  261.             sweptarea.yh = bbox[0]->yh > bbox[1]->yh ? bbox[0]->yh : bbox[1]->yh;
  262.             
  263. //
  264. // calculate the swept area between the sectors
  265. //
  266.             for (bn=0 ; bn<2 ; bn++)
  267.             {
  268.                 memset (walls,0,sizeof(walls));
  269.                 if (bbox[bn]->xl <= bbox[!bn]->xl)
  270.                     walls[si_west] = 1;
  271.                 if (bbox[bn]->xh >= bbox[!bn]->xh)
  272.                     walls[si_east] = 1;
  273.                 if (bbox[bn]->yl <= bbox[!bn]->yl)
  274.                     walls[si_south] = 1;
  275.                 if (bbox[bn]->yh >= bbox[!bn]->yh)
  276.                     walls[si_north] = 1;
  277.  
  278.                 for (s=0 ; s<5 ; s++)
  279.                 {
  280.                     switch (s&3)
  281.                     {
  282.                     case si_north:
  283.                         x = bbox[bn]->xl;
  284.                         y = bbox[bn]->yh;
  285.                         break;
  286.                     case si_east:
  287.                         x = bbox[bn]->xh;
  288.                         y = bbox[bn]->yh;
  289.                         break;
  290.                     case si_south:
  291.                         x = bbox[bn]->xh;
  292.                         y = bbox[bn]->yl;
  293.                         break;
  294.                     case si_west:
  295.                         x = bbox[bn]->xl;
  296.                         y = bbox[bn]->yl;
  297.                         break;            
  298.                     }
  299.                     if (!walls[(s-1)&3] && walls[s&3])
  300.                     {
  301.                         points[bn][0].x = x;
  302.                         points[bn][0].y = y;
  303.                     }
  304.                     if (walls[(s-1)&3] && !walls[s&3])
  305.                     {
  306.                         points[bn][1].x = x;
  307.                         points[bn][1].y = y;
  308.                     }
  309.                 }
  310.                 
  311.                 ends[bn].x = points[bn][0].x;
  312.                 ends[bn].y = points[bn][0].y;
  313.                 ends[bn].dx = points[bn][1].x - points[bn][0].x;
  314.                 ends[bn].dy = points[bn][1].y - points[bn][0].y;
  315.             }
  316.  
  317.             sides[0].x = points[0][0].x;
  318.             sides[0].y = points[0][0].y;
  319.             sides[0].dx = points[1][1].x - points[0][0].x;
  320.             sides[0].dy = points[1][1].y - points[0][0].y;
  321.             
  322.             sides[1].x = points[0][1].x;
  323.             sides[1].y = points[0][1].y;
  324.             sides[1].dx = points[1][0].x - points[0][1].x;
  325.             sides[1].dy = points[1][0].y - points[0][1].y;
  326.             
  327.             end0out = !BPointOnSide (&points[1][0], &ends[0]);
  328.             end1out = !BPointOnSide (&points[0][0], &ends[1]);
  329.             side0out = !BPointOnSide (&points[0][1], &sides[0]);
  330.             side1out = !BPointOnSide (&points[0][0], &sides[1]);
  331.  
  332. //        
  333. // look for a line change that covers the swept area
  334. //
  335.             for (k=0 ; k<numbchains ; k++)
  336.             {
  337.                 if (!DoesChainBlock (&bchains[k]))
  338.                     continue;
  339.                 blockcount++;
  340.                 connections[i*numsectors+j] = connections[j*numsectors+i] = 1;
  341.                 
  342.                 if (draw)
  343.                 {
  344. EraseWindow ();    
  345. DrawBBox (bbox[0]);
  346. DrawBBox (bbox[1]);
  347. DrawDivline (&ends[0]);
  348. DrawDivline (&ends[1]);
  349. DrawDivline (&sides[0]);
  350. DrawDivline (&sides[1]);
  351. DrawBChain (&bchains[k]);
  352.                 }
  353.                 goto blocked;
  354.             }
  355.  
  356. // nothing definately blocked the path
  357.             passcount++;                
  358. blocked:;
  359.         }
  360.     }
  361.     printf ("passcount: %i\nblockcount: %i\n",passcount, blockcount);
  362. }
  363.  
  364.  
  365. /*
  366. ====================
  367. =
  368. = BuildBlockingChains
  369. =
  370. ====================
  371. */
  372.  
  373. void BuildBlockingChains (void)
  374. {
  375.     boolean    *used;
  376.     int            i,j;
  377.     bpoint_t    *temppoints, *pt_p;
  378.     bline_t    *li1, *li2;
  379.     id            chains_i;
  380.     bchain_t    bch;
  381.     int            cx, cy;
  382.     
  383.     used = alloca (numblines*sizeof (*used));
  384.     memset (used,0,numblines*sizeof (*used));
  385.     temppoints = alloca (numblines*sizeof (*temppoints));
  386.     
  387.     chains_i = [[Storage alloc]
  388.                     initCount:        0
  389.                     elementSize:    sizeof(bchain_t)
  390.                     description:    NULL];
  391.  
  392.     li1 = blines;
  393.     for (i=0 ; i<numblines ; i++, li1++)
  394.     {
  395.         if (used[i])
  396.             continue;
  397.         used[i] = true;
  398.         
  399.         // start a new chain
  400.         pt_p = temppoints;
  401.         pt_p->x = li1->p1.x;
  402.         pt_p->y = li1->p1.y;
  403.         pt_p++;
  404.         pt_p->x = cx = li1->p2.x;
  405.         pt_p->y = cy = li1->p2.y;
  406.         pt_p++;
  407.  
  408.         ClearBBox (&bch.bounds);
  409.         AddToBBox (&bch.bounds, li1->p1.x, li1->p1.y);
  410.         AddToBBox (&bch.bounds, cx, cy);
  411.         
  412.         // look for connected lines
  413.         do
  414.         {            
  415.             li2 = li1+1;
  416.             for (j=i+1 ; j<numblines ; j++,li2++)
  417.                 if (!used[j] && li2->p1.x == cx && li2->p1.y == cy)
  418.                     break;
  419.         
  420.             if (j==numblines)
  421.                 break;        // no more lines in chain
  422.                 
  423.         // add to chain
  424.             used[j] = true;
  425.             pt_p->x = cx = li2->p2.x;
  426.             pt_p->y = cy = li2->p2.y;
  427.             pt_p++;
  428.             AddToBBox (&bch.bounds, cx, cy);
  429.         } while (1);
  430.         
  431. // save the block chain
  432.         bch.numpoints = pt_p - temppoints;
  433.         bch.points = malloc (bch.numpoints*sizeof(*bch.points));
  434.         memcpy (bch.points, temppoints, bch.numpoints*sizeof(*bch.points));
  435.         [chains_i addElement: &bch];
  436. //DrawBChain (&bch);
  437.     }
  438.     
  439.     numbchains = [chains_i count];
  440.     bchains = [chains_i elementAt:0];
  441. }
  442.  
  443.  
  444. /*
  445. ====================
  446. =
  447. = ProcessConnections
  448. =
  449. ====================
  450. */
  451.  
  452. void ProcessConnections (void)
  453. {
  454.     int                    i, s, wlcount, count;
  455.     bbox_t                *secbox;
  456.     id                    lines;
  457.     worldline_t        *wl;
  458.     mapvertex_t        *vt;
  459.     maplinedef_t        *p;
  460.     mapsidedef_t        *sd;
  461.     bline_t            bline;
  462.     int                    sec;
  463.         
  464.     numsectors = [secstore_i count];
  465.     wlcount = [linestore_i count];
  466.  
  467.     connections = malloc (numsectors*numsectors+8); // allow rounding to bytes
  468.     memset (connections, 0, numsectors*numsectors);
  469.     
  470.     secboxes = secbox = malloc (numsectors*sizeof(bbox_t));
  471.     for (i=0 ; i<numsectors ; i++, secbox++)
  472.         ClearBBox (secbox);
  473.  
  474. //            
  475. // calculate bounding boxes for all sectors
  476. //
  477.     count = [ldefstore_i count];
  478.     p = [ldefstore_i elementAt:0];
  479.     vt = [mapvertexstore_i elementAt:0];
  480.     for (i=0 ; i<count ; i++, p++)
  481.     {
  482.         for (s=0 ; s<1 ; s++)
  483.         {
  484.             if (p->sidenum[s] == -1)
  485.                 continue;            // no back side
  486.             // add both points to sector bounding box
  487.             sd = (mapsidedef_t *)[sdefstore_i elementAt: p->sidenum[s]];
  488.             sec = sd->sector;
  489.             AddToBBox (&secboxes[sec], vt[p->v1].x, vt[p->v1].y);
  490.             AddToBBox (&secboxes[sec], vt[p->v2].x, vt[p->v2].y);
  491.         }
  492.     }
  493.  
  494. //    
  495. // make a list of only the solid lines
  496. //
  497.     lines = [[Storage alloc]
  498.                     initCount:        0
  499.                     elementSize:    sizeof(bline)
  500.                     description:    NULL];
  501.     
  502.     wl = [linestore_i elementAt: 0];
  503.     for ( i=0 ; i<wlcount ; wl++,i++)
  504.     {
  505.         if (wl->flags & ML_TWOSIDED)
  506.             continue;            // don't add two sided lines
  507.         bline.p1.x = wl->p1.x;
  508.         bline.p1.y = wl->p1.y;
  509.         bline.p2.x = wl->p2.x;
  510.         bline.p2.y = wl->p2.y;
  511.         [lines addElement: &bline];
  512.     }
  513.     blines = [lines elementAt: 0];
  514.     numblines = [lines count];
  515.     
  516. //
  517. // build blocking chains
  518. //
  519.     BuildBlockingChains ();
  520.  
  521. //
  522. // build connection list
  523. //
  524.     BuildConnections ();
  525. }
  526.  
  527.  
  528. /*
  529. =================
  530. =
  531. = OutputConnections
  532. =
  533. =================
  534. */
  535.  
  536. void OutputConnections (void)
  537. {
  538.     int        i;
  539.     int        bytes;
  540.     char    *cons;
  541.     char    *bits;
  542.     
  543.     cons = connections;
  544.     bytes = (numsectors*numsectors+7)/8;
  545.     bits = malloc(bytes);
  546.     
  547.     for (i=0 ; i<bytes ; i++)
  548.     {
  549.         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);
  550.         cons +=8;
  551.     }
  552.     
  553.     [wad_i addName: "reject" data:bits size:bytes];
  554.     printf ("reject: %i\n",bytes);    
  555. }
  556.