--------------------------------
           NODE_GEN.C
    Written by Jason Hoffoss
Copyright (C) 1994 Jason Hoffoss
--------------------------------

Notice:  I give hereby give permission to everyone to copy, distribute, 
and use these routines, in part or as a whole, so long as it is stated 
that I am the original author of these routines.  Routines based or 
derived from these routines should also state that they are based or 
derived from my routines.  You may not sell these routines, but you can 
sell programs with routines based or derived from these routines, or 
incorperating these routines, if these routines comprise less then 20% 
of your program.

Ok, so here is an algorithm I wrote to generate nodes.  It has all the 
routines and structures it need run inclusive, however it is not a stand 
alone program.  If you try to just compile it, you will get an error 
stating that the function "main" was not found.  Simply adding the 
function "main" and compiling it again will also not work.  It will 
compile at that point, but it will not have any data from which to 
generate the nodes.  It doesn't contain any routines for reading a wad 
file, either.  The purpose of these routines is to be informative, and 
to be used in other programs.  The main entry point to generate nodes 
is (of course) "generate_nodes()".

WARNING:  These routines don't fully work yet.  I don't know what's wrong
with them exactly, but I am sure it's something minor.  Therefore, the
third purpose of releasing these routines is so that hopefully someone can
figure out what I'm doing wrong.  From the information currently available
on nodes, it is working fine.  When you give it to doom to use, however, it
doesn't work so desirably.  Sometimes you get "hyper-junk" walls.  I have
also gotten a "M_Player located in unknown special sector #29" (and it
isn't a sector problem, either.)  I think there's something else that
needs to be done that no one has mentioned yet.

My favorite map to use for testing node generation is CROSS.WAD.  Being 
the simple map that it is, it's easy to see how everything fits 
together.  These routines will pick the same first nodeline as the 
author used, however all nodelines thereafter are picked differently.  
Why?  Better balance on the two sides.  If anyone has ideas on a better 
way to tell which nodeline should be used, let me know, eh?  Anyway, 
using CROSS.WAD, we end up with 6 nodes, 7 sub sectors, and 28 segments 
(no splits).  Here's a diagram of what it generated:

            +++++
            +   +
            +   +                 +++ single sided linedef
            + 6 +
            +   +                 --- double sided linedef
            +   +
        +B+++---+++++             ... imaginary node bounding limit
        +           +
        +     5     +             A-F nodelines: letter is at tail of line
+A+++++++...........+++++++++
+       |           F       +     1-7 Sub Sectors
+   2   E     0     |   1   +
+++++++++...........+++++++C+
        +           +                  Line Sidedef Dir Vertexes
        +     3     +
        +++++---+++D+                 A   0    0    ->   0 ->  1
            +   +                     B   2    2    ->   2 ->  3
            +   +                     C  10   10    <-  10 -> 11
            + 4 +                     D  12   12    <-  12 -> 13
            +   +                     E  20   20     ^  18 ->  1
            +   +                     F  22   24     v   8 -> 11
            +++++

Ok, so you start off in sub sector #2, facing right.  Once you enter Sub 
Sector #0, by crossing linedef #20 (which is nodeline E) you only see 
what's in front of you if you still are facing right.  The 2 imaginary 
node bounding limits on either side of you are no longer updated, and 
you just see hyper-junk there.  However, if you turn enough so that your 
gun points straight at a corner where nodeline F crosses nodeline A or 
C, then it detects sub sector 5 or 3, and will draw those walls again.  
I can see these symptoms, but I don't know what is causing them.  So, 
what I think I really need is to know how a program would use a BSP tree 
to detect what walls to draw.  Anyone ever write a program to use BSP 
trees?  I can't see how it one would even use such information.. 

Anyway, enjoy this little node generator.  When I get it working 
properly, I'll will release it too.  If anyone else has written a node 
generator, could I get a copy to examine?  As far as I know, only 
myself, the authors of DEU, and the team at ID have written node 
generators.  Post any comments about this to Alt.games.doom.

   -Jason Hoffoss
    DMapEdit author
