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