home *** CD-ROM | disk | FTP | other *** search
/ Toolkit for DOOM / DOOMTOOL.ISO / editors / dme301.zip / SOURCE.ZIP / ADVANCED.C next >
C/C++ Source or Header  |  1994-07-31  |  41KB  |  1,790 lines
  1. /*
  2.     This is a DMapEdit source code module.  Though it is copyrighted, you
  3.     may modify it and use it for your own personal use, meaning that new
  4.     modified code and anything derived from it (such as exe files) doesn't
  5.     get distributed to anyone, unless you get my permission first.  Code
  6.     from this file, or code based on ideas from this file may be used with
  7.     other programs, provided that you give credit for it in the source code,
  8.     documentation, and 'about' windows or screens, if one exists, for the
  9.     programs using it.  Giving credit means something like this:
  10.  
  11.     Code from DMapEdit was used in this program
  12.  
  13.                               or
  14.  
  15.     Some code for this program was based on ideas presented in DMapEdit
  16.  
  17.     Whatever.  Just be sure to mention "DMapEdit" in such a way that it's
  18.     self-evident how it was useful to the new program, and be sure to have
  19.     "DMapEdit is a trademark of Jason Hoffoss" in the docs.  That's all..
  20. */
  21.  
  22. #include <stdlib.h>
  23. #include <stdio.h>
  24. #include <conio.h>
  25. #include <graphics.h>
  26. #include <string.h>
  27. #include <math.h>
  28. #include <alloc.h>
  29. #include <limits.h>
  30. #include <time.h>
  31.  
  32. #include "dme.h"
  33. #include "dme2.h"
  34.  
  35. #define VL_MAX 2048
  36.  
  37. void check_vertexes(void);
  38. void check_things(void);
  39. void add_node_list(int far *list, int *index, int line, int v1, int v2);
  40. void remove_vertexes(void);
  41. uint nodize(uint size, int far *list);
  42. int resolve_space(int line, int size, int far *list,
  43.     int far *left_list, int far *right_list, int *lx1, int *ly1,
  44.     int *lx2, int *ly2, int *rx1, int *ry1, int *rx2, int *ry2, int test);
  45. void add_node_list2(int far *list, int index, int line, int v1, int v2,
  46.     int *x1, int *y1, int *x2, int *y2);
  47. int make_seg(int line, int v1, int v2);
  48.  
  49. int b_max=0;
  50. int optimize; /* method of optimizing node generation */
  51. int v_size_backup;
  52. int seg_orig;
  53. int i, j; /* general loop indexing variables */
  54. int nodeline; /* current nodeline */
  55. int convex; /* set if polygon is convex */
  56. int err; /* error code */
  57. uint lcount; /* # of lines to the left of nodeline */
  58. uint rcount; /* # of lines to the right of nodeline */
  59. int bal; /* difference between lcount and rcount (0 = perfect balance) */
  60. int splits; /* # of lines nodeline splits */
  61. int left_size; /* lcount of best case */
  62. int right_size; /* rcount of best case */
  63. int balance; /* best case balance */
  64. int splits_min; /* best case of minimum splits */
  65. int simple_splits; /* total number of simple splits */
  66. int complex_splits; /* total number of complex splits */
  67. int *slivers; /* list to track complex splits (cause of slivers) */
  68. uint link2; /* node/ssec left side link */
  69. char test_msg[80];
  70. time_t start, end;
  71.  
  72. void misc_options(void)
  73. {
  74.     int button;
  75.  
  76.     while (1)
  77.     {
  78.         window_text1("Misc. functions\t\n"
  79.             " @ Error-check Vertexes\n"
  80.             " @ Error-check Lines/Sidedefs \n"
  81.             " @ Error-check Things\n"
  82.             " @ Error-check Sectors\n\n"
  83.             " @ Fix lines\n"
  84.             " @ Generate Sectors\n"
  85.             " @ Fix Sectors\n"
  86.             " @ Generate Nodes\n"
  87.             " @ Generate Blockmap\n\n", 1, 0, 0);
  88.         b.pos[3].status = -1;
  89.         b.pos[6].status = -1;
  90.         draw_buttons();
  91.         set_cancel_bar();
  92.  
  93.         if ((button = window_check()) < 0)
  94.             return;
  95.  
  96.         switch(button)
  97.         {
  98.             case 0:
  99.                 check_vertexes();
  100.                 break;
  101.             case 1:
  102.                 check_lines();
  103.                 break;
  104.             case 2:
  105.                 check_things();
  106.                 break;
  107.             case 4:
  108.                 fixup_lines();
  109.                 break;
  110.             case 5:
  111.                 generate_sectors();
  112.                 break;
  113.             case 6:
  114.                 fixup_sectors();
  115.                 break;
  116.             case 7:
  117.                 generate_nodes();
  118.                 break;
  119.             case 8:
  120.                 generate_blockmap();
  121.                 break;
  122.         }
  123.         draw_map();
  124.     }
  125. }
  126.  
  127. void check_things(void)
  128. {
  129.     char msg[1024], temp[80];
  130.     int i, j, k, xx1, xx2, err1=15, err2=0, dm_entry=0;
  131.     ulong total, count, count2;
  132.  
  133.     if (!t_size)
  134.     {
  135.         error("There are no Things to check!");
  136.         return;
  137.     }
  138.  
  139.     window_text("Checking for Thing errors..\n\n\n", 1);
  140.     xx1 = draw_time_graph(win.top + 20);
  141.  
  142.     count = count2 = 0;
  143.     total = t_size;
  144.     for (i=0; i<t_size; i++)
  145.     {
  146.         if (things[i].type == 1)
  147.         {
  148.             if (!(err1 & 1))
  149.                 err1 |= 16;
  150.             err1 &= ~1;
  151.         }
  152.  
  153.         if (things[i].type == 2)
  154.         {
  155.             if (!(err1 & 2))
  156.                 err1 |= 32;
  157.             err1 &= ~2;
  158.         }
  159.  
  160.         if (things[i].type == 3)
  161.         {
  162.             if (!(err1 & 4))
  163.                 err1 |= 64;
  164.             err1 &= ~4;
  165.         }
  166.  
  167.         if (things[i].type == 4)
  168.         {
  169.             if (!(err1 & 8))
  170.                 err1 |= 128;
  171.             err1 &= ~8;
  172.         }
  173.  
  174.         if (things[i].type == 11)
  175.             dm_entry++;
  176.     }
  177.  
  178.     if (err1 || dm_entry < 4)
  179.     {
  180.         strcpy(msg, "Results\t\n");
  181.         if (err1 & 1)
  182.             strcat(msg, "Missing player #1 starting point\n");
  183.         if (err1 & 2)
  184.             strcat(msg, "Missing player #2 starting point\n");
  185.         if (err1 & 4)
  186.             strcat(msg, "Missing player #3 starting point\n");
  187.         if (err1 & 8)
  188.             strcat(msg, "Missing player #4 starting point\n");
  189.         if (err1 & 16)
  190.             strcat(msg, "Too many player #1 starting points\n");
  191.         if (err1 & 32)
  192.             strcat(msg, "Too many player #2 starting points\n");
  193.         if (err1 & 64)
  194.             strcat(msg, "Too many player #3 starting points\n");
  195.         if (err1 & 128)
  196.             strcat(msg, "Too many player #4 starting points\n");
  197.         if (dm_entry < 4)
  198.         {
  199.             sprintf(temp, "Only %d of 4 deathmatch entry points found\n",
  200.                 dm_entry);
  201.             strcat(msg, temp);
  202.         }
  203.         window_text(msg, 1);
  204.  
  205.     } else
  206.         window_text("Results\t\nNo errors found\n", 1);
  207.  
  208.     while (mouse_check());
  209.     while (!mouse_check())
  210.         if (keypress)
  211.             break;
  212.  
  213.     await_release();
  214.     return;
  215. }
  216.  
  217. void check_vertexes(void)
  218. {
  219.     char msg[256], temp[60];
  220.     int i, j, k, xx1, xx2, err1=0, err2=0;
  221.     ulong total, count, count2;
  222.  
  223.     if (!max_vertex)
  224.     {
  225.         error("There are no Vertexes to check!");
  226.         return;
  227.     }
  228.  
  229.     window_text("Checking for Vertex errors..\n\n\n", 1);
  230.     xx1 = draw_time_graph(win.top + 20);
  231.  
  232.     count = count2 = 0;
  233.     total = summation(max_vertex) + (ulong) max_vertex * l_size;
  234.     for (i=0; i<max_vertex; i++)
  235.     {
  236.         for (j=i+1; j<max_vertex; j++)
  237.         {
  238.             if (vertexes[i].x == vertexes[j].x &&
  239.                 vertexes[i].y == vertexes[j].y)
  240.             {
  241.                 err1++;
  242.                 for (k=0; k<l_size; k++)
  243.                 {
  244.                     if (linedefs[k].v1 == j)
  245.                         linedefs[k].v1 = i;
  246.                     if (linedefs[k].v2 == j)
  247.                         linedefs[k].v2 = i;
  248.                 }
  249.                 del_vertex(j);
  250.             }
  251.             count++;
  252.         }
  253.  
  254.         if ((count - count2) > 1024)
  255.         {
  256.             time_graph(count, total, xx1, win.top + 20);
  257.             count2 = count;
  258.         }
  259.  
  260.         for (j=k=0; j<l_size; j++)
  261.         {
  262.             if (linedefs[j].v1 == i)
  263.                 k++;
  264.             if (linedefs[j].v2 == i)
  265.                 k++;
  266.             count++;
  267.         }
  268.         if (!k)
  269.         {
  270.             err2++;
  271.             del_vertex(i--);
  272.         }
  273.  
  274.         if ((count - count2) > 1024)
  275.         {
  276.             time_graph(count, total, xx1, win.top + 20);
  277.             count2 = count;
  278.         }
  279.     }
  280.  
  281.     if (err1 || err2)
  282.     {
  283.         strcpy(msg, "Results\t\n");
  284.         if (err1)
  285.         {
  286.             sprintf(temp, "%d overlapping vertexes (fixed)\n", err1);
  287.             strcat(msg, temp);
  288.         }
  289.  
  290.         if (err2)
  291.         {
  292.             sprintf(temp, "%d unused vertexes (removed)\n", err2);
  293.             strcat(msg, temp);
  294.         }
  295.         window_text(msg, 1);
  296.  
  297.     } else
  298.         window_text("Results\t\nNo errors found\n", 1);
  299.  
  300.     while (!mouse_check())
  301.         if (keypress)
  302.             break;
  303.  
  304.     await_release();
  305.     return;
  306. }
  307.  
  308. void del_vertex2(int num) /* delete unused vertex */
  309. {
  310.     int i;
  311.  
  312.     for (i=num; i<v_size-1; i++)
  313.         vertexes[i] = vertexes[i+1];
  314.  
  315.     for (i=0; i<l_size; i++)
  316.     {
  317.         if (linedefs[i].v1 > num)
  318.             linedefs[i].v1--;
  319.         if (linedefs[i].v2 > num)
  320.             linedefs[i].v2--;
  321.     }
  322.  
  323.     for (i=0; i<seg_size; i++)
  324.     {
  325.         if (segs[i].v1 > num)
  326.             segs[i].v1--;
  327.         if (segs[i].v2 > num)
  328.             segs[i].v2--;
  329.     }
  330.  
  331.     v_size--;
  332.     max_vertex--;
  333.     return;
  334. }
  335.  
  336. void check_lines(void)
  337. {
  338.     char msg[4096], temp[60];
  339.     int i, j, xx1, xx2, xx3, num, v1, v2, v3, v4, sd1, sd2, total1, total2;
  340.     uint err;
  341.     ulong count, count2, total, err1, err2, err3, err4, err5;
  342.  
  343.     if (!l_size)
  344.     {
  345.         error("There are no Lines to check!");
  346.         s_size = 0; /* shouldn't be any sidedefs if no lines */
  347.         return;
  348.     }
  349.     if (!s_size)
  350.         error("No Sidedefs!");
  351.  
  352.     window_text("Checking for Line/Sidedef errors..\n\n\n\n", 1);
  353.     xx1 = draw_time_graph(win.top + 20);
  354.     xx2 = draw_time_graph(win.top + 29); /*
  355.     xx3 = draw_time_graph(win.top + 38); */
  356.     err1 = err2 = err3 = err4 = err5 = 0;
  357.  
  358. re_check1:
  359.     err = count = count2 = 0;
  360.     total = summation(l_size);
  361.     /* first check is overlapping lines */
  362.     for (i=0; i<l_size; i++)
  363.     {
  364.         v1 = linedefs[i].v1;
  365.         v2 = linedefs[i].v2;
  366.         if (v1 == v2)
  367.         {
  368.             err5++;
  369.             if (err == LL_MAX) /* too many errors to track */
  370.             {
  371.                 for (i=0; i<err; i++)
  372.                     del_line(llist[i]); /* fix and try again */
  373.                 reset_time_graph(count, total, xx1, win.top + 20);
  374.                 goto re_check1;
  375.             }
  376.             count += l_size - i - 1;
  377.             continue; /* no need to check further */
  378.         }
  379.  
  380.         for (j=i+1; j<l_size; j++) /* i and lower already checked */
  381.         {
  382.             v3 = linedefs[j].v1;
  383.             v4 = linedefs[j].v2;
  384.             if ((v1 == v3 && v2 == v4) || (v1 == v4 && v2 == v3))
  385.             {
  386.                 err1++;
  387.                 if (err == LL_MAX) /* too many errors to track */
  388.                 {
  389.                     for (i=0; i<err; i++)
  390.                         del_line(llist[i]); /* fix and try again */
  391.                     reset_time_graph(count, total, xx1, win.top + 20);
  392.                     goto re_check1;
  393.                 }
  394.                 llist[err++] = i;
  395.             }
  396.             count++;
  397.         }
  398.  
  399.         if ((count - count2) > 1024)
  400.         {
  401.             time_graph(count, total, xx1, win.top + 20);
  402.             count2 = count;
  403.         }
  404.  
  405.         if ((sd2 = linedefs[i].sd2) != -1 && linedefs[i].sd1 == -1)
  406.         { /* if only 1 sidedef, must be on right */
  407.             v1 = linedefs[i].v1;
  408.             linedefs[i].v1 = linedefs[i].v2;
  409.             linedefs[i].v2 = v1;
  410.  
  411.             linedefs[i].sd1 = sd2;
  412.             linedefs[i].sd2 = -1;
  413.             err4++;
  414.         }
  415.  
  416.         if ((sd1 = linedefs[i].sd1) != -1 && sd2 != -1)
  417.         { /* sidedef with most textures must also be on the right */
  418.             total1 = total2 = 0;
  419.  
  420.             if (sidedefs[sd1].top[0] != '-')
  421.                 total1++;
  422.             if (sidedefs[sd1].middle[0] != '-')
  423.                 total1++;
  424.             if (sidedefs[sd1].bottom[0] != '-')
  425.                 total1++;
  426.  
  427.             if (sidedefs[sd2].top[0] != '-')
  428.                 total2++;
  429.             if (sidedefs[sd2].middle[0] != '-')
  430.                 total2++;
  431.             if (sidedefs[sd2].bottom[0] != '-')
  432.                 total2++;
  433.  
  434.             if (total2 > total1)
  435.             {
  436.                 v1 = linedefs[i].v1;
  437.                 linedefs[i].v1 = linedefs[i].v2;
  438.                 linedefs[i].v2 = v1;
  439.  
  440.                 linedefs[i].sd1 = sd2;
  441.                 linedefs[i].sd2 = sd1;
  442.                 err4++;
  443.             }
  444.         }
  445.     }
  446.     time_graph(count, total, xx1, win.top + 20);
  447.     for (i=0; i<err; i++)
  448.         del_line(llist[i]);
  449.  
  450.     if (!s_size) /* skip sidedef checks */
  451.         goto re_check2;
  452.  
  453.     err = 0;
  454.     count = count2 = 0;
  455.     /* second check is for sidedef used only once. */
  456.     for (i=0; i<s_size; i++)
  457.     {
  458.         num = 0;
  459.         for (j=0; j<l_size; j++, count++)
  460.         {
  461.             if (linedefs[j].sd1 == i)
  462.             {
  463.                 if (num)
  464.                 {
  465.                     err2++; /* sidedef already used */
  466.                     linedefs[j].sd1 = add_sidedef(i);
  467.                 }
  468.                 num = 1;
  469.             }
  470.             if (linedefs[j].sd2 == i)
  471.             {
  472.                 if (num)
  473.                 {
  474.                     err2++; /* sidedef already used */
  475.                     linedefs[j].sd2 = add_sidedef(i);
  476.                 }
  477.                 num = 1;
  478.             }
  479.         }
  480.         if (!num)
  481.         {
  482.             err3++; /* sidedef wasn't used */
  483.             del_sidedef(i--);
  484.             count -= l_size;
  485.             count2 -= l_size;
  486.         }
  487.         if ((count - count2) > 1024)
  488.         {
  489.             time_graph(count, (ulong) s_size * l_size, xx2, win.top + 29);
  490.             count2 = count;
  491.         }
  492.     }
  493.  
  494. re_check2:
  495.  
  496.     if (err1 || err2 || err3 || err4 || err5)
  497.     {
  498.         strcpy(msg, "Results\t\n");
  499.         if (err1)
  500.         {
  501.             sprintf(temp, "%d overlapping lines (fixed)\n", err1);
  502.             strcat(msg, temp);
  503.         }
  504.  
  505.         if (err2)
  506.         {
  507.             sprintf(temp, "%d overused sidedefs (fixed)\n", err2);
  508.             strcat(msg, temp);
  509.         }
  510.  
  511.         if (err3)
  512.         {
  513.             sprintf(temp, "%d unused sidedefs (removed)\n", err3);
  514.             strcat(msg, temp);
  515.         }
  516.  
  517.         if (err4)
  518.         {
  519.             sprintf(temp, "%d lines needed inverting (fixed)\n", err4);
  520.             strcat(msg, temp);
  521.         }
  522.  
  523.         if (err5)
  524.         {
  525.             sprintf(temp, "%d line singularities (removed)\n", err5);
  526.             strcat(msg, temp);
  527.         }
  528.  
  529.         window_text(msg, 1);
  530.     } else
  531.         window_text("Results\t\nNo errors found\n", 1);
  532.  
  533.     while (!mouse_check())
  534.         if (keypress)
  535.             break;
  536.  
  537.     await_release();
  538.     return;
  539. }
  540.  
  541. long summation(uint num)
  542. {
  543.     int i;
  544.     long total=0L;
  545.  
  546.     if (num < 3)
  547.         return 1L;
  548.     for (i=1; i<num; i++)
  549.         total += i;
  550.     return total;
  551. }
  552.  
  553. void fixup_lines(void)
  554. {
  555.     int i, j, vertex, v, orig_line, side, dir, line, temp;
  556.     uint angle;
  557.  
  558.     draw_map();
  559.     if ((!max_vertex) || (!l_size))
  560.         return;
  561.     vertex = 0;
  562.     for (i=1; i<max_vertex; i++)
  563.         if (vertexes[i].y < vertexes[vertex].y)
  564.             vertex = i; /* find the bottom most vertex on map */
  565.     for (i=0; i<l_size; i++)
  566.         if (linedefs[i].v1 == vertex || linedefs[i].v2 == vertex)
  567.             if (vertexes[linedefs[i].v1].x != vertexes[linedefs[i].v2].x)
  568.                 break; /* get a non-vertical line from this vertex */
  569.     if ((line = i) == l_size)
  570.         fatal_error("Line not found");
  571.  
  572.     orig_line = line; /* this is our starting line */
  573.     v = linedefs[line].v1;
  574.     vertex = linedefs[line].v2;
  575.     side = dir = 0;
  576.     if (vertexes[v].x < vertexes[vertex].x)
  577.         side = 1;
  578.     angle = calc_angle(vertexes[v].x, vertexes[v].y,
  579.         vertexes[vertex].x, vertexes[vertex].y);
  580.  
  581.     do /* go through the entire outside border and make it all walls */
  582.     {
  583.         if (dir == side) /* which sidedef is which? */
  584.         {
  585.             if ((i = linedefs[line].sd2) != -1)
  586.             {
  587.                 del_sidedef(i);
  588.                 linedefs[line].sd2 = -1;
  589.             }
  590.             if (linedefs[line].sd1 == -1)
  591.                 linedefs[line].sd1 = add_sidedef(-1);
  592.         } else {
  593.             if ((i = linedefs[line].sd1) != -1)
  594.             {
  595.                 del_sidedef(i);
  596.                 linedefs[line].sd1 = -1;
  597.             }
  598.             if (linedefs[line].sd2 == -1)
  599.                 linedefs[line].sd2 = add_sidedef(-1);
  600.         }
  601.         linedefs[line].attrib |= 0x1; /* line is a wall */
  602.         linedefs[line].attrib &= 0xfffb; /* can't be transparent */
  603.  
  604.         color2wall(line, 96, 32);
  605.         dir = find_next_line(&vertex, &angle, &line, side);
  606.         if (dir == -1)
  607.             return;
  608.     } while (line != orig_line);
  609.  
  610.     for (i=0; i<l_size; i++)
  611.         if (linedefs[i].sd1 == -1 && linedefs[i].sd2 == -1)
  612.         { /* new line, not initialized yet */
  613.             linedefs[i].sd1 = add_sidedef(-1);
  614.             linedefs[i].sd2 = add_sidedef(-1);
  615.             linedefs[i].attrib &= 0xfffe; /* not a wall */
  616.             linedefs[i].attrib |= 0x4; /* probably will be transparent */
  617.  
  618.             sidedefs[linedefs[i].sd1].middle[0] = '-';
  619.             sidedefs[linedefs[i].sd2].middle[0] = '-';
  620.             for (j=1; j<8; j++)
  621.             {
  622.                 sidedefs[linedefs[i].sd1].middle[j] = 0;
  623.                 sidedefs[linedefs[i].sd2].middle[j] = 0;
  624.             }
  625.             continue;
  626.         }
  627.  
  628.     do
  629.     {
  630.         v = 0;
  631.         for (i=0; i<l_size; i++)
  632.         {
  633.             if (linedefs[i].sd1 == -1 && (dir = wall_check(i, 1)))
  634.             {
  635.                 if (dir == -1)
  636.                     return;
  637.                 linedefs[i].sd1 = add_sidedef(-1);
  638.                 v = 1;
  639.                 color2wall(i, 254, 96);
  640.             }
  641.             if (linedefs[i].sd2 == -1 && (dir = wall_check(i, 0)))
  642.             {
  643.                 if (dir == -1)
  644.                     return;
  645.                 linedefs[i].sd2 = add_sidedef(-1);
  646.                 v = 1;
  647.                 color2wall(i, 254, 32);
  648.             }
  649.         }
  650.     } while (v);
  651.  
  652.     for (i=0; i<l_size; i++)
  653.     {
  654.         if (linedefs[i].sd1 == -1 || linedefs[i].sd2 == -1)
  655.         {
  656.             linedefs[i].attrib |= 0x1;
  657.             linedefs[i].attrib &= 0xfffb;
  658.         } else {
  659.             linedefs[i].attrib &= 0xfffe;
  660.             linedefs[i].attrib |= 0x4;
  661.         }
  662.  
  663.         flip_line(i);
  664.     }
  665.     return;
  666. }
  667.  
  668. int wall_check(int line, int side)
  669. {
  670.     int line2, v1, v2, dir, vertex;
  671.     uint angle, angle2;
  672.  
  673.     v1 = linedefs[line].v1;
  674.     v2 = linedefs[line].v2;
  675.  
  676.     line2 = line;
  677.     vertex = v2;
  678.     angle = angle2 = calc_angle(vertexes[v1].x, vertexes[v1].y,
  679.         vertexes[v2].x, vertexes[v2].y);
  680.     if ((dir = find_next_line(&vertex, &angle, &line, side)) == -1)
  681.         return -1;
  682.     if (dir == side)
  683.     {
  684.         if (linedefs[line].sd2 != -1)
  685.             return 1;
  686.     } else {
  687.         if (linedefs[line].sd1 != -1)
  688.             return 1;
  689.     }
  690.  
  691.     line = line2;
  692.     vertex = v1;
  693.     angle = angle2 ^ 0x8000;
  694.     if ((dir = find_next_line(&vertex, &angle, &line, (side^1))) == -1)
  695.         return -1;
  696.     if (dir == side)
  697.     {
  698.         if (linedefs[line].sd1 != -1)
  699.             return 1;
  700.     } else {
  701.         if (linedefs[line].sd2 != -1)
  702.             return 1;
  703.     }
  704.     return 0;
  705. }
  706.  
  707. void generate_sectors(void)
  708. {
  709.     char msg[256], msg2[60];
  710.     int x, y, x1, y1, x2, y2, sector1, sector2, new_line;
  711.     int i, line, xx, vertex, orig_line, side, dir, temp, re_loop;
  712.     int min_vertex, min_vertex_y, sidedef, err_count=0, err_count2=0;
  713.     int l_index, v_index, angle, dist;
  714.     int vlist[VL_MAX];
  715.     uint uangle, dist_min;
  716.  
  717.     struct sec_struct sec_info = { 0, 72, "FLOOR4_8", "CEIL3_5", 255, 0, 0 };
  718.  
  719.     for (i=0; i<s_size; i++)
  720.         sidedefs[i].sector = -1; /* clear out sector references */
  721.  
  722.     window_text("Generating Sectors, please wait..\n\n\n", 1);
  723.     xx = draw_time_graph(win.top + 20);
  724.     draw_map();
  725.  
  726.     if (sec_max)
  727.         free_farmem(sectors, "Sectors");
  728.     if (r_size)
  729.         free_farmem(reject, "Reject bitmap");
  730.     l_index = v_index = sec_size = sec_max = r_size = 0;
  731.  
  732.     for (sidedef=0; sidedef<s_size; sidedef++)
  733.     {
  734.         if (sidedefs[sidedef].sector != -1)
  735.             continue;
  736.         for (line=0; line<l_size; line++)
  737.         {
  738.             if (linedefs[line].sd1 == sidedef)
  739.             {
  740.                 side = 1;
  741.                 break;
  742.             }
  743.             if (linedefs[line].sd2 == sidedef)
  744.             {
  745.                 side = 0;
  746.                 break;
  747.             }
  748.         }
  749.         if (line == l_size)
  750.         {
  751.             err_count++;
  752.             continue;
  753.         }
  754.         min_vertex_y = 32767;
  755.  
  756.         re_loop = 1;
  757.         while (re_loop)
  758.         {
  759.             orig_line = line;
  760.             temp = linedefs[line].v1;
  761.             vertex = linedefs[line].v2;
  762.             dir = 0;
  763.             uangle = calc_angle(vertexes[temp].x, vertexes[temp].y,
  764.                 vertexes[vertex].x, vertexes[vertex].y);
  765.  
  766.             do
  767.             {
  768.                 if (testmode > 1)
  769.                 {
  770.                     if (side)
  771.                     {
  772.                         tx1 = vertexes[temp].x;
  773.                         tx2 = vertexes[vertex].x;
  774.                         ty1 = vertexes[temp].y;
  775.                         ty2 = vertexes[vertex].y;
  776.                     } else {
  777.                         tx2 = vertexes[temp].x;
  778.                         tx1 = vertexes[vertex].x;
  779.                         ty2 = vertexes[temp].y;
  780.                         ty1 = vertexes[vertex].y;
  781.                     }
  782.                     setcolor(60);
  783.                     draw_side(tx1, ty1, tx2, ty2);
  784.  
  785.                     sprintf(msg, "Sidedef=%d Line=%d Sector=%d Angle=%u "
  786.                         "Line list=%d group list=%d",
  787.                         sidedef, line, sec_size, uangle, l_index, v_index);
  788.                     toptext(msg);
  789.                     for (i=0; i<(maxy/10); i++)
  790.                     {
  791.                         sprintf(msg, "  %d", llist[i]);
  792.                         text(-1, i*10, msg);
  793.                     }
  794.                     cursored_get(0, 9);
  795.                     setcolor(0);
  796.                     draw_side(tx1, ty1, tx2, ty2);
  797.                 }
  798.                 color2wall(line, 96, 96);
  799.                 if (dir == side)
  800.                 {
  801.                     sidedefs[linedefs[line].sd2].sector = sec_size;
  802.                     temp = linedefs[line].sd1;
  803.                 } else {
  804.                     sidedefs[linedefs[line].sd1].sector = sec_size;
  805.                     temp = linedefs[line].sd2;
  806.                 }
  807.                 if (temp != -1)
  808.                     if (sidedefs[temp].sector == -1)
  809.                     {
  810.                         if (l_index == LL_MAX)
  811.                         {
  812.                             error("Line list full!");
  813.                             return;
  814.                         }
  815.                         llist[l_index++] = line;
  816.                         llist[l_index] = -1;
  817.                     }
  818.  
  819.                 if ((temp = vertexes[vertex].y) < min_vertex_y)
  820.                 {
  821.                     min_vertex = vertex;
  822.                     min_vertex_y = temp;
  823.                 }
  824.                 temp = vertex;
  825.  
  826.                 dir = find_next_line(&vertex, &uangle, &line, side);
  827.                 if (dir == -1)
  828.                 {
  829.                     deadend_error();
  830.                     return;
  831.                 }
  832.             } while (line != orig_line);
  833.  
  834.             if (testmode == 1)
  835.             {
  836.                 sprintf(msg, "Sector #%d", sec_size);
  837.                 toptext(msg);
  838.                 cursored_get(0, 9);
  839.             }
  840.  
  841.             re_loop = 0;
  842.             sec_size++;
  843.             while (l_index)
  844.             {
  845.                 llist[l_index] = -1;
  846.                 l_index--;
  847.                 line = llist[l_index]; /* get next line */
  848.                 if ((temp = linedefs[line].sd1) != -1 &&
  849.                     sidedefs[temp].sector == -1) /* find the sidedef */
  850.                 {
  851.                     side = 1;
  852.                     re_loop = 1;
  853.                     break;
  854.                 }
  855.                 if ((temp = linedefs[line].sd2) != -1 &&
  856.                     sidedefs[temp].sector == -1)
  857.                 {
  858.                     side = 0;
  859.                     re_loop = 1;
  860.                     break;
  861.                 }
  862.             }
  863.         }
  864.         if (v_index == VL_MAX)
  865.         {
  866.             error("Vertex list full!");
  867.             return;
  868.         }
  869.         vlist[v_index++] = min_vertex;
  870.     }
  871.  
  872.     for (i=0; i<v_index; i++) /* now put sectors inside each other */
  873.     {
  874.         line = downward_line(vertex = vlist[i], &side, testmode);
  875.         if (side)
  876.             sidedef = linedefs[line].sd1;
  877.         else
  878.             sidedef = linedefs[line].sd2;
  879.         x = vertexes[vertex].x;
  880.         y = vertexes[vertex].y;
  881.  
  882.         line = inside_poly(x, y, &side, testmode);
  883.         if (!side)
  884.             side = linedefs[line].sd2;
  885.         else if (side == 1)
  886.             side = linedefs[line].sd1;
  887.  
  888.         if (sidedef == -1 || side == -1)
  889.         {
  890.             if (testmode > 1)
  891.             {
  892.                 setcolor(0);
  893.                 draw_side(tx3, ty3, tx4, ty4);
  894.                 setcolor(96);
  895.                 draw_line2(adjustx(tx3), adjusty(ty3),
  896.                     adjustx(tx4), adjusty(ty4));
  897.             }
  898.             if (sidedef != -1 || side != -1)
  899.                 err_count2++; /* interior mismatch */
  900.             continue;
  901.         }
  902.  
  903.         if (testmode > 1)
  904.         {
  905.             sprintf(msg, "Detected sidedefs: %d and %d", sidedef, side);
  906.             toptext(msg);
  907.             cursored_get(0, 9);
  908.             setcolor(0);
  909.             draw_side(tx1, ty1, tx2, ty2);
  910.             draw_side(tx3, ty3, tx4, ty4);
  911.             setcolor(96);
  912.             draw_line2(adjustx(tx1), adjusty(ty1),
  913.                 adjustx(tx2), adjusty(ty2));
  914.             draw_line2(adjustx(tx3), adjusty(ty3),
  915.                 adjustx(tx4), adjusty(ty4));
  916.         }
  917.  
  918.         sector1 = sidedefs[sidedef].sector;
  919.         sector2 = sidedefs[side].sector;
  920.         if (sector1 == sector2)
  921.             fatal_error("Groups already match");
  922.  
  923.         if (testmode)
  924.         {
  925.             for (line=0; line<l_size; line++)
  926.             {
  927.                 setcolor(255);
  928.                 test_draw_sector(line, sector1);
  929.                 setcolor(80);
  930.                 test_draw_sector(line, sector2);
  931.             }
  932.             sprintf(msg, "Sector %d merged with %d", sector2, sector1);
  933.             toptext(msg);
  934.             cursored_get(0, 9);
  935.         }
  936.  
  937.         for (sidedef=0; sidedef<s_size; sidedef++)
  938.         {
  939.             if (sidedefs[sidedef].sector == sector2)
  940.                 sidedefs[sidedef].sector = sector1; /* make 1 sector */
  941.             if (sidedefs[sidedef].sector > sector2)
  942.                 sidedefs[sidedef].sector--; /* close gap */
  943.         }
  944.         sec_size--;
  945.  
  946.         if (testmode)
  947.         {
  948.             setcolor(96);
  949.             for (line=0; line<l_size; line++)
  950.                 test_draw_sector(line, sector1);
  951.             toptext("");
  952.         }
  953.     }
  954.  
  955.     sec_max = sec_size;
  956.     sectors = get_farmem(sec_size * sizeof(struct sec_struct), "Sectors");
  957.     if (!sectors)
  958.     {
  959.         farmem_error("Sectors", sec_size);
  960.         sec_size = sec_max = 0;
  961.         return;
  962.     }
  963.     for (i=0; i<sec_size; i++) /* initialize the sectors */
  964.         sectors[i] = sec_info;
  965.     r_size = ((ulong) sec_size * sec_size + 7) / 8;
  966.     reject = get_farmem(r_size, "Reject bitmap");
  967.     for (i=0; i<r_size; i++)
  968.         reject[i] = 0;
  969.  
  970.     *msg = 0;
  971.     if (err_count)
  972.     {
  973.         sprintf(msg, "%d unused sidedefs detected", err_count);
  974.         if (err_count2)
  975.             strcat(msg, "\n");
  976.     }
  977.  
  978.     if (err_count2)
  979.     {
  980.         sprintf(msg2, "%d group mismatches detected", err_count2);
  981.         strcat(msg, msg2);
  982.     }
  983.  
  984.     if (err_count || err_count2)
  985.         error(msg);
  986.     return;
  987. }
  988.  
  989. void fixup_sectors(void)
  990. {
  991. }
  992.  
  993. void generate_nodes(void)
  994. {
  995.     char msg[256];
  996.     int index, v1, v2, far *list;
  997.     int i, button;
  998.     long j;
  999.     struct ss_struct ssec;
  1000.  
  1001.     optimize = 2;
  1002.     window_text("Generate Nodes\t\n"
  1003.         "Optimize for:\n\n"
  1004.         "@ Balance\n"
  1005.         "@     :\n"
  1006.         "@     :\n"
  1007.         "@ Least splits\n\n", 1);
  1008.  
  1009.     set_window_bars();
  1010.     b.pos[optimize].on = 1;
  1011.     while ((button = window_check()) > -1)
  1012.     {
  1013.         b.pos[optimize].on = 0;
  1014.         b.pos[button].on = 1;
  1015.         optimize = button;
  1016.     }
  1017.  
  1018.     if (button == -99)
  1019.         return;
  1020.  
  1021.     start = time(NULL);
  1022.     if (n_max)
  1023.         free_farmem(nodes, "Nodes");
  1024.     if (ss_max)
  1025.         free_farmem(ssectors, "Sub Sectors");
  1026.     if (seg_max)
  1027.         free_farmem(segs, "Segments");
  1028.     n_size = ss_size = seg_size = simple_splits = complex_splits = 0;
  1029.     n_max = 2;
  1030.     nodes = get_farmem(sizeof(struct n_struct) * n_max, "Nodes");
  1031.     ss_max = 1;
  1032.     ssectors = get_farmem(sizeof(struct ss_struct) * ss_max, "Sub Sectors");
  1033.     seg_max = l_size;
  1034.     segs = get_farmem(sizeof(struct seg_struct) * seg_max, "Segments");
  1035.  
  1036.     v_size = max_vertex;
  1037.     slivers = get_mem(4096, "Sliver tracking list");
  1038.     list = get_farmem(s_size * 6, "Base node list");
  1039.     {
  1040.         index = err = 0;
  1041.         clearviewport();
  1042.         setcolor(252);
  1043.         for (i=0; i<l_size; i++)
  1044.         {
  1045.             v1 = linedefs[i].v1;
  1046.             v2 = linedefs[i].v2;
  1047.             draw_line(i, SOLID_LINE);
  1048.  
  1049.             if (linedefs[i].sd1 != -1)
  1050.                 add_node_list(list, &index, i, v1, v2);
  1051.             if (linedefs[i].sd2 != -1)
  1052.                 add_node_list(list, &index, i, v2, v1);
  1053.         }
  1054.         if (nodize(index/3, list) != 65535)
  1055.         {
  1056.             free_farmem(list, "Base node list");
  1057.             remove_vertexes();
  1058.             free_mem(slivers, "Sliver tracking list");
  1059.  
  1060.             end = time(NULL);
  1061.             i = difftime(end, start);
  1062.             sprintf(msg, "Node generation completed\t\n"
  1063.                 "Took %d seconds\n"
  1064.                 "%d Nodes created\n"
  1065.                 "%d Sub Sectors created\n"
  1066.                 "%d Segments created\n"
  1067.                 "%d extra Vertexes created\n"
  1068.                 "%d simple splits occured\n"
  1069.                 "%d complex splits occured\n",
  1070.                 i, n_size, ss_size, seg_size, v_size - max_vertex,
  1071.                 simple_splits, complex_splits);
  1072.  
  1073.             window_text(msg, 1);
  1074.             while (!mouse_check())
  1075.                 if (keypress)
  1076.                     break;
  1077.  
  1078.             return;
  1079.         }
  1080.         free_farmem(list, "Base node list");
  1081.         free_mem(slivers, "Sliver tracking list");
  1082.     }
  1083.     if (!err)
  1084.         error("Out of far memory!");
  1085.     if (err == 1)
  1086.         error("Too many Nodes!");
  1087.     if (err == 2)
  1088.         error("Too many Segments!");
  1089.     if (err == 3)
  1090.         error("Too many Sub Sectors!");
  1091.     if (err == 4)
  1092.         error("Too many Vertexes!");
  1093.     n_size = ss_size = seg_size = 0;
  1094.     v_size = max_vertex;
  1095.     return;
  1096. }
  1097.  
  1098. /* used by generate_nodes() to built a list of starting segs */
  1099.  
  1100. void add_node_list(int far *list, int *index, int line, int v1, int v2)
  1101. {
  1102.     list[(*index)++] = line;
  1103.     list[(*index)++] = v1;
  1104.     list[(*index)++] = v2;
  1105.     return;
  1106. }
  1107.  
  1108. void remove_vertexes(void)
  1109. {
  1110.     int i, j, v;
  1111.  
  1112.     j = complex_splits;
  1113.     while (j--) /* resolve slivers by merging vertexes, since it's safe now */
  1114.     {
  1115.         v = slivers[j] + 1;
  1116.         for (i=0; i<seg_size; i++)
  1117.         {
  1118.             if (segs[i].v1 >= v)
  1119.                 segs[i].v1--;
  1120.             if (segs[i].v2 >= v)
  1121.                 segs[i].v2--;
  1122.         }
  1123.  
  1124.         for (i=v; i<v_size; i++)
  1125.             vertexes[i-1] = vertexes[i];
  1126.         v_size--;
  1127.     }
  1128.     return;
  1129. }
  1130.  
  1131. /*  recursive node generator  */
  1132.  
  1133. uint nodize(uint size, int far *list)
  1134. {
  1135.     int x1, y1, x2, y2, lx1, ly1, lx2, ly2, rx1, ry1, rx2, ry2;
  1136.     int num, far *left_list, far *right_list;
  1137.     uint link1;
  1138.  
  1139.     convex = 1;
  1140.     balance = splits_min = size;
  1141.     nodeline = -1;
  1142.     for (i=0, j=1; i<size; i++, j +=3)
  1143.     {
  1144.         x1 = vertexes[list[j]].x;
  1145.         x2 = vertexes[list[j+1]].x;
  1146.         y1 = vertexes[list[j]].y;
  1147.         y2 = vertexes[list[j+1]].y;
  1148.         setcolor(80);
  1149.         draw_side(x1, y1, x2, y2);
  1150.  
  1151.         if (resolve_space(i, size, list, left_list, right_list,
  1152.             &lx1, &ly1, &lx2, &ly2, &rx1, &ry1, &rx2, &ry2, 1))
  1153.                 return 65535;
  1154.         if (lcount && rcount) /* lines on both sides of nodelist */
  1155.             convex = 0; /* if ever so, can't be convex polygon */
  1156.  
  1157.         bal = abs(lcount - rcount);
  1158.         num = 0;
  1159.         switch (optimize)
  1160.         {
  1161.             case 0: /* optimize for balance */
  1162.                 if (bal < balance)
  1163.                     num++;
  1164.                 if (bal == balance && splits < splits_min)
  1165.                     num++;
  1166.                 break;
  1167.             case 3: /* optimize for least splits */
  1168.                 if (splits < splits_min)
  1169.                     num++;
  1170.                 if (splits == splits_min && bal < balance)
  1171.                     num++;
  1172.                 break;
  1173.             case 1: /* optimize equaly between both */
  1174.                 if ((bal + splits) <= (balance + splits_min))
  1175.                     if (bal < balance)
  1176.                         num++;
  1177.                 break;
  1178.             case 2: /* optimize both, mainly least splits, though */
  1179.                 if ((bal + splits*3) <= (balance + splits_min*3))
  1180.                     if (bal < balance)
  1181.                         num++;
  1182.         }
  1183.         if (!lcount || !rcount) /* all lines on one side */
  1184.             num = 0; /* ineligible, because we can't split anymore */
  1185.  
  1186.         if (num)
  1187.         {
  1188.             balance = bal;
  1189.             splits_min = splits;
  1190.             left_size = lcount;
  1191.             right_size = rcount;
  1192.             nodeline = i; /* best case for nodeline so far */
  1193.             setcolor(60);
  1194.             draw_side(x1, y1, x2, y2);
  1195.         } else {
  1196.             setcolor(0);
  1197.             draw_side(x1, y1, x2, y2);
  1198.             setcolor(146);
  1199.             draw_line2(adjustx(x1), adjusty(y1), adjustx(x2), adjusty(y2));
  1200.         }
  1201.     }
  1202.  
  1203.     if (convex) /* is a convex polygon, so generate an ssec */
  1204.     {
  1205.         if (ss_size == ss_max)
  1206.         {
  1207.             void far *ptr;
  1208.  
  1209.             ptr = resize_farmem(ssectors, (ss_max+20) *
  1210.                 sizeof(struct ss_struct), "Sub Sectors");
  1211.             if (!ptr)
  1212.             {
  1213.                 err = 3;
  1214.                 return 65535;
  1215.             }
  1216.             ssectors = ptr;
  1217.             ss_max += 20;
  1218.         }
  1219.         ssectors[ss_size].segptr = seg_size;
  1220.         ssectors[ss_size++].size = size;
  1221.  
  1222.         setcolor(255);
  1223.         for (i=0; i<size; i++)
  1224.         {
  1225.             num = i * 3;
  1226.             if (make_seg(list[num], list[num+1], list[num+2]))
  1227.             {
  1228.                 err = 2;
  1229.                 return 65535;
  1230.             }
  1231.         }
  1232.  
  1233.         if (testmode)
  1234.         {
  1235.             sprintf(test_msg, "Nodes=%u Sub Sectors=%u Segments=%u ",
  1236.                 n_size, ss_size, seg_size);
  1237.             toptext(test_msg);
  1238.             test_map();
  1239.         }
  1240.         return (32767 + ss_size); /* ssector link value */
  1241.     }
  1242.     if (nodeline == -1)
  1243.         fatal_error("No nodeline selected");
  1244.  
  1245. new_nodeline:
  1246.     num = nodeline * 3;
  1247.     x1 = vertexes[list[num+1]].x;
  1248.     x2 = vertexes[list[num+2]].x;
  1249.     y1 = vertexes[list[num+1]].y;
  1250.     y2 = vertexes[list[num+2]].y;
  1251.     if (left_size)
  1252.     {
  1253.         left_list = get_farmem(left_size * 6, "left node list");
  1254.         if (!left_list)
  1255.             return 65535;
  1256.     }
  1257.     if (right_size)
  1258.     {
  1259.         right_list = get_farmem(right_size * 6, "right node list");
  1260.         if (!right_list)
  1261.         {
  1262.             free_farmem(left_list, "left node list");
  1263.             return 65535;
  1264.         }
  1265.     }
  1266.  
  1267. re_resolve:
  1268.     lx1 = rx1 = ly1 = ry1 = INT_MAX; /* reset limits */
  1269.     lx2 = rx2 = ly2 = ry2 = INT_MIN;
  1270.     if (resolve_space(nodeline, size, list, left_list, right_list,
  1271.         &lx1, &ly1, &lx2, &ly2, &rx1, &ry1, &rx2, &ry2, 0))
  1272.     {
  1273.         free_farmem(left_list, "left node list");
  1274.         free_farmem(right_list, "right node list");
  1275.         return 65535;
  1276.     }
  1277.     if (!lcount || !rcount)
  1278.         fatal_error("convex polygon not detected");
  1279.  
  1280.     do
  1281.     {
  1282.         setcolor(32);
  1283.         setlinestyle(DOTTED_LINE, 0, 1);
  1284.         draw_box(lx1, ly1, lx2, ly2);
  1285.         setlinestyle(SOLID_LINE, 0, 1);
  1286.         plot_list(left_size, left_list);
  1287.         setcolor(96);
  1288.         setlinestyle(DOTTED_LINE, 0, 1);
  1289.         draw_box(rx1, ry1, rx2, ry2);
  1290.         setlinestyle(SOLID_LINE, 0, 1);
  1291.         plot_list(right_size, right_list);
  1292.         setcolor(60);
  1293.         if (nodeline < 0)
  1294.             draw_side(x2, y2, x1, y2);
  1295.         else
  1296.             draw_side(x1, y1, x2, y2);
  1297.         num = test_map2(left_size, right_size, size, left_list,
  1298.             right_list, list);
  1299.         if (num == -1)
  1300.         {
  1301.             i = x1;
  1302.             x1 = x2;
  1303.             x2 = i;
  1304.             i = y1;
  1305.             y1 = y2;
  1306.             y2 = i;
  1307.             goto re_resolve;
  1308.         }
  1309.         if (num > 0)
  1310.         {
  1311.             nodeline = num - 1;
  1312.             free_farmem(left_list, "left node list");
  1313.             free_farmem(right_list, "right node list");
  1314.             resolve_space(nodeline, size, list, left_list, right_list,
  1315.                 &lx1, &ly1, &lx2, &ly2, &rx1, &ry1, &rx2, &ry2, 1);
  1316.             goto new_nodeline;
  1317.         }
  1318.     } while (num);
  1319.  
  1320.     num = left_size; /* global var we need, and nodize recursion will scramble */
  1321.     link1 = nodize(right_size, right_list);
  1322.     free_farmem(right_list, "right node list"); /* don't need it anymore */
  1323.     if (link1 < 65535)
  1324.     {
  1325.         link2 = nodize(num, left_list);
  1326.         if (link2 < 65535)
  1327.         {
  1328.             free_farmem(left_list, "left node list");
  1329.             if (n_size == n_max)
  1330.             {
  1331.                 void far *ptr;
  1332.  
  1333.                 ptr = resize_farmem(nodes, (n_max+20) *
  1334.                     sizeof(struct n_struct), "Nodes");
  1335.                 if (!ptr)
  1336.                 {
  1337.                     err = 1;
  1338.                     return 65535;
  1339.                 }
  1340.                 nodes = ptr;
  1341.                 n_max += 20;
  1342.             }
  1343.  
  1344.             nodes[n_size].x = x1;
  1345.             nodes[n_size].y = y1;
  1346.             nodes[n_size].dx = x2 - x1;
  1347.             nodes[n_size].dy = y2 - y1;
  1348.             nodes[n_size].node1.x1 = rx1;
  1349.             nodes[n_size].node1.y2 = ry1;
  1350.             nodes[n_size].node1.x2 = rx2;
  1351.             nodes[n_size].node1.y1 = ry2;
  1352.             nodes[n_size].node2.x1 = lx1;
  1353.             nodes[n_size].node2.y2 = ly1;
  1354.             nodes[n_size].node2.x2 = lx2;
  1355.             nodes[n_size].node2.y1 = ly2;
  1356.             nodes[n_size].link1 = link1;
  1357.             nodes[n_size].link2 = link2;
  1358.             return n_size++; /* link to this node */
  1359.         }
  1360.     }
  1361.     free_farmem(left_list, "left node list");
  1362.     return 65535; /* error, return back through recursions */
  1363. }
  1364.  
  1365. /*  make left and right lists from master list  */
  1366.  
  1367. int resolve_space(int line, int size, int far *list,
  1368.     int far *left_list, int far *right_list, int *lx1, int *ly1,
  1369.     int *lx2, int *ly2, int *rx1, int *ry1, int *rx2, int *ry2, int test)
  1370. {
  1371.     int i, v1, v2, v3, v4, vv1, vv2, x, y, xx, yy, num;
  1372.     int angle1, angle2, left, right, line2;
  1373.     uint angle;
  1374.  
  1375.     lcount = rcount = splits = 0; /* reset counts */
  1376.  
  1377.     num = line * 3;
  1378.     vv1 = list[num + 1];
  1379.     vv2 = list[num + 2];
  1380.     x = vertexes[vv1].x;
  1381.     y = vertexes[vv1].y;
  1382.     angle = calc_angle(x, y, vertexes[vv2].x, vertexes[vv2].y);
  1383.  
  1384.     for (i=0; i<size; i++)
  1385.     {
  1386.         left = right = 0;
  1387.         num = i * 3;
  1388.         line2 = list[num];
  1389.         v1 = v3 = list[num + 1];
  1390.         v2 = v4 = list[num + 2];
  1391.  
  1392.         if (v1 == vv1)
  1393.             angle1 = 0;
  1394.         else {
  1395.             angle1 = adjusted_angle(angle, x, y, vertexes[v1].x, vertexes[v1].y);
  1396.             if (angle1 == INT_MIN) /* on line, but behind vertex 1 */
  1397.                 angle1 = 0;
  1398.         }
  1399.  
  1400.         if (v2 == vv1)
  1401.             angle2 = 0;
  1402.         else {
  1403.             angle2 = adjusted_angle(angle, x, y, vertexes[v2].x, vertexes[v2].y);
  1404.             if (angle2 == INT_MIN)
  1405.                 angle2 = 0;
  1406.         }
  1407.  
  1408.         if ((!angle1) && (!angle2)) /* on line */
  1409.         {
  1410.             if (adjusted_angle(angle, vertexes[v1].x, vertexes[v1].y,
  1411.                 vertexes[v2].x, vertexes[v2].y))
  1412.                 left = 1;
  1413.             else
  1414.                 right = 1;
  1415.         } else if (angle1 >= 0 && angle2 >= 0) /* totally right of line */
  1416.             right = 1;
  1417.         else if (angle1 < 1 && angle2 < 1) /* totally left of line */
  1418.             left = 1;
  1419.         else { /* nodeline must split this line */
  1420.             left = right = 1; /* line on each side */
  1421.             splits++; /* inc split count */
  1422.             if (!test) /* if in test mode, don't need to make new vertexes */
  1423.             {
  1424.                 if ((xx = calc_line_cross(&yy, x, y, vv2, v1, v2, angle)) == -1)
  1425.                 {
  1426.                     err = 4;
  1427.                     return -1;
  1428.                 }
  1429.  
  1430.                 if (angle1 < 0 && angle2 > 0) /* which direction is line? */
  1431.                 {
  1432.                     v1 = xx;
  1433.                     v4 = yy;
  1434.                 } else {
  1435.                     v2 = xx;
  1436.                     v3 = yy;
  1437.                 }
  1438.             }
  1439.         }
  1440.  
  1441.         if (!test) /* if not in test mode, build the lists */
  1442.         {
  1443.             if (right)
  1444.                 add_node_list2(right_list, rcount++, line2, v1, v2,
  1445.                     rx1, ry1, rx2, ry2);
  1446.             if (left)
  1447.                 add_node_list2(left_list, lcount++, line2, v3, v4,
  1448.                     lx1, ly1, lx2, ly2);
  1449.         } else {
  1450.             if (right) /* still need to track counts, though */
  1451.                 rcount++;
  1452.             if (left)
  1453.                 lcount++;
  1454.         }
  1455.     }
  1456.     return 0;
  1457. }
  1458.  
  1459. void add_node_list2(int far *list, int index, int line, int v1, int v2,
  1460.     int *x1, int *y1, int *x2, int *y2)
  1461. {
  1462.     uint idx;
  1463.  
  1464.     adjust_limit(vertexes[v1].x, vertexes[v1].y, x1, y1, x2, y2);
  1465.     adjust_limit(vertexes[v2].x, vertexes[v2].y, x1, y1, x2, y2);
  1466.  
  1467.     idx = index * 3;
  1468.     list[idx] = line;
  1469.     list[idx+1] = v1;
  1470.     list[idx+2] = v2;
  1471.     return;
  1472. }
  1473.  
  1474. void draw_side(int x1, int y1, int x2, int y2)
  1475. {
  1476.     int cx, cy, tx, ty;
  1477.     double angle;
  1478.  
  1479.     angle = ((double) calc_angle(x1, y1, x2, y2) - 16384.0) * M_PI / 32768.0;
  1480.     cx = (x1 + x2) / 2;
  1481.     cy = (y1 + y2) / 2;
  1482.     tx = cx + 16.0 * cos(angle);
  1483.     ty = cy + 16.0 * sin(angle);
  1484.     draw_line2(adjustx(x1), adjusty(y1), adjustx(x2), adjusty(y2));
  1485.     draw_line2(adjustx(cx), adjusty(cy), adjustx(tx), adjusty(ty));
  1486.     return;
  1487. }
  1488.  
  1489. int make_seg(int line, int v1, int v2)
  1490. {
  1491.     int v, vv, x, y, x1, y1, x2, y2, dir, dist;
  1492.     uint angle1, angle2;
  1493.  
  1494.     if (seg_size == seg_max)
  1495.     {
  1496.         void far *ptr;
  1497.  
  1498.         ptr = resize_farmem(segs, (seg_max+20) * sizeof(struct seg_struct),
  1499.             "Segments");
  1500.         if (!ptr)
  1501.             return -1;
  1502.         segs = ptr;
  1503.         seg_max += 20;
  1504.     }
  1505.  
  1506.     x1 = vertexes[v1].x;
  1507.     x2 = vertexes[v2].x;
  1508.     y1 = vertexes[v1].y;
  1509.     y2 = vertexes[v2].y;
  1510.     draw_side(x1, y1, x2, y2);
  1511.     v = linedefs[line].v1;
  1512.     vv = linedefs[line].v2;
  1513.     x = vertexes[v].x;
  1514.     y = vertexes[v].y;
  1515.  
  1516.     dir = dist = 0;
  1517.     angle1 = calc_angle(x1, y1, x2, y2);
  1518.     angle2 = calc_angle(x, y, vertexes[vv].x, vertexes[vv].y);
  1519.     if (labs((long int) angle2 - angle1) > 16384) /* opposite direction */
  1520.     {
  1521.         dir = 1;
  1522.         v = linedefs[line].v2;
  1523.         x = vertexes[v].x;
  1524.         y = vertexes[v].y;
  1525.     }
  1526.     if (v1 != v)
  1527.     {
  1528.         x = abs(x - x1);
  1529.         y = abs(y - y1);
  1530.         dist = sqrt((double) x * x + (double) y * y);
  1531.     }
  1532.  
  1533.     segs[seg_size].v1 = v1;
  1534.     segs[seg_size].v2 = v2;
  1535.     segs[seg_size].linedef = line;
  1536.     segs[seg_size].angle = angle1;
  1537.     segs[seg_size].dir = dir;
  1538.     segs[seg_size++].dist = dist;
  1539.     return 0;
  1540. }
  1541.  
  1542. void plot_list(int size, int far *list)
  1543. {
  1544.     int i, j, x1, y1, x2, y2;
  1545.  
  1546.     for (i=0, j=1; i<size; i++, j += 3)
  1547.     {
  1548.         x1 = vertexes[list[j]].x;
  1549.         y1 = vertexes[list[j]].y;
  1550.         x2 = vertexes[list[j+1]].x;
  1551.         y2 = vertexes[list[j+1]].y;
  1552.  
  1553.         draw_side(x1, y1, x2, y2);
  1554.     }
  1555.     return;
  1556. }
  1557.  
  1558. void calc_map_data(void)
  1559. {
  1560.     int i;
  1561.  
  1562.     for (i=0; i<max_vertex; i++)
  1563.     {
  1564.         adjvx[i] = adjustx(vertexes[i].x);
  1565.         adjvy[i] = adjusty(vertexes[i].y);
  1566.     }
  1567.  
  1568.     ll_size = 0;
  1569.     for (i=0; i<l_size; i++)
  1570.         if (line_visible(i))
  1571.             llines[ll_size++] = i;
  1572.  
  1573.     return;
  1574. }
  1575.  
  1576. int test_map(void)
  1577. {
  1578.     int i, key, rekey=0;
  1579.  
  1580.     if (!testmode)
  1581.         return 0;
  1582.  
  1583.     if (!(key = cursored_get(0, 9)))
  1584.         key = getch() + 1000;
  1585.     if (key >= 'A' && key <= 'Z')
  1586.         key += 0x20; /* remap uppercase to lowercase */
  1587.     if (map_keys(key))
  1588.         calc_map_data();
  1589.  
  1590.     clearviewport();
  1591.     setcolor(252);
  1592.     for (i=0; i<l_size; i++)
  1593.         draw_line(i, SOLID_LINE);
  1594.     return rekey;
  1595. }
  1596.  
  1597. int test_map2(int left, int right, int cur, int far *left_list,
  1598.     int far *right_list, int far *cur_list)
  1599. {
  1600.     int i, key, rekey=0, far *ptr;
  1601.  
  1602.     if (!testmode)
  1603.         return 0;
  1604.  
  1605.     sprintf(test_msg, "Current list=%d  Right list=%d  Left list=%d",
  1606.         cur, right, left);
  1607.     toptext(test_msg);
  1608.     if (!(key = cursored_get(0, 9)))
  1609.         key = getch() + 1000;
  1610.     if (key >= 'A' && key <= 'Z')
  1611.         key += 0x20; /* remap uppercase to lowercase */
  1612.     if (map_keys(key))
  1613.     {
  1614.         calc_map_data();
  1615.         rekey = -9;
  1616.     }
  1617.  
  1618.     switch (key)
  1619.     {
  1620.         case 'l':
  1621.             rekey = -9;
  1622.             showlist("Left", left, left_list);
  1623.             break;
  1624.         case 'r':
  1625.             rekey = -9;
  1626.             showlist("Right", right, right_list);
  1627.             break;
  1628.         case 'c':
  1629.             rekey = showlist("Current", cur, cur_list);
  1630.             break;
  1631.         case 'f':
  1632.             ptr = left_list;
  1633.             left_list = right_list;
  1634.             right_list = ptr;
  1635.             i = left;
  1636.             left = right;
  1637.             right = i;
  1638.             rekey = -1;
  1639.             break;
  1640.     }
  1641.  
  1642.     clearviewport();
  1643.     setcolor(252);
  1644.     for (i=0; i<l_size; i++)
  1645.         draw_line(i, SOLID_LINE);
  1646.     return rekey;
  1647. }
  1648.  
  1649. int showlist(char *name, int size, char far *list)
  1650. {
  1651.     int i;
  1652.  
  1653.     return 0;
  1654. }
  1655.  
  1656. /*  make polygon's sidedefs on both sided of <line> the same as <line>'s
  1657.      sidedefs
  1658. */
  1659.  
  1660. void fix_sidedefs(int line)
  1661. {
  1662.     fix_sidedef(line, 0);
  1663.     fix_sidedef(line, 1);
  1664.     return;
  1665. }
  1666.  
  1667. /*   make all sidedefs of polygon the same as <line>'s sidedef  */
  1668.  
  1669. void fix_sidedef(int line, int side)
  1670. {
  1671.     int orig_line, vertex, v1, dir;
  1672.     uint angle;
  1673.     struct s_struct sidedef_info;
  1674.  
  1675.     orig_line = line;
  1676.     v1 = linedefs[line].v1;
  1677.     vertex = linedefs[line].v2;
  1678.     angle = calc_angle(vertexes[v1].x, vertexes[v1].y,
  1679.         vertexes[vertex].x, vertexes[vertex].y);
  1680.     if (side)
  1681.         sidedef_info = sidedefs[linedefs[line].sd1];
  1682.     else
  1683.         sidedef_info = sidedefs[linedefs[line].sd2];
  1684.     dir = 0;
  1685.  
  1686.     do
  1687.     {
  1688.         if (dir == side)
  1689.             sidedefs[linedefs[line].sd2] = sidedef_info;
  1690.         else
  1691.             sidedefs[linedefs[line].sd1] = sidedef_info;
  1692.  
  1693.         dir = find_next_line(&vertex, &angle, &line, side);
  1694.         if (dir == -1)
  1695.         {
  1696.             deadend_error();
  1697.             return;
  1698.         }
  1699.     } while (line != orig_line);
  1700.     return;
  1701. }
  1702.  
  1703. void generate_blockmap(void)
  1704. {
  1705.     int i, xmin, ymin, xmax, ymax, x, y, x1, y1, x2, y2, xx, yy, block;
  1706.     int blockmax, xorigin, yorigin, xsize, ysize, point1, point2;
  1707.  
  1708.     window_text("Generating Blockmap, please wait..\n\n\n", 1);
  1709.     yy = win.top + 20;
  1710.     xx = draw_time_graph(yy);
  1711.  
  1712.     if (b_size)
  1713.         free_farmem(blockmap, "Blockmap");
  1714.     b_max = 1000;
  1715.     blockmap = get_farmem(b_max, "Blockmap");
  1716.  
  1717.     xmin = xmax = ymin = ymax = 0;
  1718.     if (v_size)
  1719.     {
  1720.         xmin = xmax = vertexes[0].x;
  1721.         ymin = ymax = vertexes[0].y;
  1722.         for (i=1; i<v_size; i++) /* figure out the size of the map */
  1723.             adjust_limit(vertexes[i].x, vertexes[i].y, &xmin, &ymin,
  1724.                 &xmax, &ymax);
  1725.     }
  1726.  
  1727.     blockmap->xorigin = xorigin = xmin & 0xfff8;
  1728.     blockmap->yorigin = yorigin = ymin & 0xfff8;
  1729.     blockmap->xsize = xsize = (xmax - xorigin) / 128 + 1;
  1730.     blockmap->ysize = ysize = (ymax - yorigin) / 128 + 1;
  1731.     block = 0;
  1732.     blockmax = b_size = xsize * ysize;
  1733.  
  1734.     for (y=0; y<ysize; y++)
  1735.         for (x=0; x<xsize; x++)
  1736.         {
  1737.             xmin = xorigin + (x * 128);
  1738.             ymin = yorigin + (y * 128);
  1739.             xmax = xmin + 127;
  1740.             ymax = ymin + 127; /* setup testing cubical */
  1741.             blockmap->offsets[block++] = b_size + 4;
  1742.  
  1743.             if (blockmap_add(0)) /* a header I guess */
  1744.                 return;
  1745.  
  1746.             for (i=0; i<l_size; i++)
  1747.             {
  1748.                 point1 = linedefs[i].v1;
  1749.                 point2 = linedefs[i].v2;
  1750.                 x1 = vertexes[point1].x;
  1751.                 x2 = vertexes[point2].x;
  1752.                 y1 = vertexes[point1].y;
  1753.                 y2 = vertexes[point2].y;
  1754.  
  1755.                 if (line_in_rect(x1, y1, x2, y2, xmin, ymin, xmax, ymax))
  1756.                     if (blockmap_add(i))
  1757.                         return;
  1758.             }
  1759.  
  1760.             if (blockmap_add(-1)) /* end-of-list */
  1761.                 return;
  1762.             time_graph(block, blockmax, xx, yy);
  1763.         }
  1764.  
  1765.     b_size = (b_size + 4) * 2;
  1766.     blockmap = resize_farmem(blockmap, b_size, "Blockmap");
  1767.     return;
  1768. }
  1769.  
  1770. int blockmap_add(int num)
  1771. {
  1772.     if ((b_size + 5) * 2 > b_max)
  1773.     {
  1774.         void far *ptr;
  1775.  
  1776.         ptr = resize_farmem(blockmap, b_max + 100, "Blockmap");
  1777.         if (!ptr)
  1778.         {
  1779.             error("Can't generate blockmap.  Map too big.");
  1780.             b_size = 0;
  1781.             return -1;
  1782.         }
  1783.         blockmap = ptr;
  1784.         b_max += 100;
  1785.     }
  1786.  
  1787.     blockmap->offsets[b_size++] = num;
  1788.     return 0;
  1789. }
  1790.