home *** CD-ROM | disk | FTP | other *** search
/ Toolkit for DOOM 1994 November / DOOMTOOL.ISO / node_bld / nodenav.txt < prev    next >
Encoding:
Text File  |  1994-05-12  |  4.6 KB  |  160 lines
  1.  
  2.  
  3. -----------------------------------------------------
  4.  
  5. Readme for NodeNav v0.8
  6.  
  7. NODES navigator for DOOM WAD file
  8.  
  9. Frank Palazzolo
  10. palazzol@msen.com
  11. 3/29/94
  12.  
  13. ***  Attention DOOM hackers!!!  ***
  14. Consider this a call to action!
  15.  
  16. According to the latest unofficial DOOM spec(*),
  17. the least understood data structure in the WAD file 
  18. is the NODES data structure.  Understanding how to generate 
  19. a NODES/SSECTORS/SEGS list from a VERTEX/LINEDEF
  20. description is crucial to being able to generate your
  21. own level (with your own wall structure). 
  22.  
  23. Note: If you don't know what I'm talking about,
  24.       please see the DOOM spec(*) and all will
  25.       become clear!
  26.  
  27. My program allows you to observe the geometry of the NODES
  28. structure for a particular DOOM level.  It is quite simple,
  29. but was a real hack job thrown together in a few days in
  30. in hybrid C/C++.  It has not been optimized and has not been used
  31. much as I am anxious to post it so that fellow computer graphics
  32. hacks can use it to (hopefully) come up with the answers!
  33.  
  34. Files:
  35. ------
  36.  
  37. DOS4GW.EXE    Dos extender necessary to run this
  38. NODENAV.EXE    The program!
  39. NODENAV.CPP    Watcom C++32 source
  40. NODENAV.H    (Include file)
  41. README        (this file)
  42.  
  43.  
  44. Command Line Parameters:
  45. ------------------------
  46.  
  47. NODENAV ExMx [wadfile]
  48.  
  49. ex. NODENAV E2M9    (Episode 2, Mission 9)
  50.  
  51. Note: E2M9 seems to be good test case, being fairly simple.
  52.  
  53. You are presented with a gray LINEDEF map of the level.
  54. The topline looks something like...
  55.  
  56. NodeNav v0.8         A:XX       B:YY    C:ZZ    
  57.  
  58. where...
  59.  
  60.    A is (N)ode, the current node with number XX.
  61.    It is represented by a GREEN line on the map...
  62.  
  63.    B is the "left" child of the current node,
  64.    either a (N)ode or (S)sector, with the number YY.
  65.    It is represented by a RED rectangle on the map...
  66.  
  67.    C is the "right" child of the current node,
  68.    either a (N)ode or (S)sector, with the number ZZ.
  69.    It is represented by a BLUE rectangle on the map...
  70.  
  71. Note: (My notions of left and right are PURELY arbitrary)
  72.  
  73. The commands are:
  74.  
  75.     U - Go up a level
  76.     L - Descend to the Left
  77.     R - Descend to the Right
  78.     Q - Quit
  79.  
  80. This first version automatically zooms in and out to
  81. allow you to see detail.
  82.  
  83. Future Enhancements:
  84. --------------------
  85.  
  86. More Commands.... Esc to exit, for example...
  87. Highlighting the actual SEGS in the SSECTOR when
  88. you get to the bottom of the tree...
  89. The sky's the limit here...
  90.  
  91. What We Know:
  92. -------------
  93.  
  94. The NODES structure seems to represent nodes in a
  95. Binary Space Partitioning tree-like structure.
  96. (Everything I know about these I've learned from 
  97. chap. 15 of Foley/Van Dam's "Computer Graphics"
  98. in the last few weeks).  Each node subdivides
  99. the map into smaller rectangular regions, subdividing 
  100. the entire level until finally only SSECTORS are left
  101. as the terminating leaves. (SSECTORS being groups of SEGS,
  102. and SEGS being pieces of LINEDEFS).
  103.  
  104. What I think:
  105. -------------
  106.  
  107. It seems that each SSECTOR is made up of SEGS which are
  108. in a certain way non-convex (sort of).  Namely, the SEGS
  109. in a SSECTOR (which bound a SECTOR), must intersect at a angle
  110. of <= 180 degrees, as measured from all SECTORS around this
  111. VERTEX.  This has the effect that...
  112.  
  113. Part of a SSECTOR can never be obscured by another part of the
  114. same SSECTOR (as long as you are in a "legal" part of the map,
  115. in a SECTOR).  
  116.  
  117. Furthermore, it seems that as you walk in any bounding 
  118. rectangle of a SSECTOR, there is a list you can create to render
  119. each SSECTOR in order from back to front, or front to back, as with
  120. a conventional BSP tree.
  121.  
  122. This means that all vertices which do not meet this criteria must
  123. eventually be split by a bounding rectangle in order to form
  124. part of two (or more) SSECTORS.
  125.  
  126. In creating these bounding rectangles, some LINEDEFS may be
  127. split incedentally, forming two SEGS.  This would explain
  128. why there are so many more SEGS than LINEDEFS.
  129.  
  130. Points of Confusion:   
  131. --------------------
  132.  
  133. As you will notice, sometimes the child rectangles 
  134. overlap, and the NODE line (green) does not split the 
  135. two at all! Maybe this doesn't matter, as long as 
  136. each terminating SSECTOR meets the "non-convex" criteria.
  137.  
  138. An algorithm to transform LINEDEFS/VERTICES into NODES/SSECTORS/
  139. SEGS is still unknown (to me at least) at this time.  I will 
  140. try my luck with this next.  
  141.  
  142. Good Luck!
  143.  
  144. *** Please email comments on this program and any 
  145. insights you have into the nature of NODES to me at...
  146.  
  147.     palazzol@msen.com
  148.  
  149.     (and post to comp.graphics.algorithms
  150.     and alt.games.doom if possible...)
  151.   
  152. ------------------------------------------------------------
  153. footnotes:
  154. (*)(v1.2, released by ap641@cleveland.freenet.edu)
  155.     to be found on wuarchive.wustl.edu...
  156.     (a must read for the DOOM hacker)
  157.  
  158.  
  159.  
  160.