Well, hello there. If you decided to read this, then I'll take it you are interested in helping me figure out some of these complecated algorithms. If you have any ideas or such, send me some mail, or send my friend Paul some E-mail. ----- Nodes ----- Well, ok, nodes have been the 'big deal' issue lately. If you are not too sure what a BSP tree is, you might want to look at and try to understand what's in the "nodes.txt" file first. Ok, I haven't really played with an algorithm for generating these yet, but I have been reading around them and trying to figure out all the important details about them. I'm putting in some routines to display the nodes, and run through them. First, you need to be in test mode (start DMapEdit with "dmapedit -test"). Then, press F10-F12. F10 is the seg viewer, which isn't really all that interesting anymore. F11 is the node tree navigator. You will start at the base. From here, you can pick the left node (in red) or the right node (blue) using "," or "." (look at the what you get with the shift key if you don't understand my choice of keys). When you branch off to the next node, the process continues again, until you get to an ssector. Ok, F12 is a recursed mode node viewer. Sort of interesting to look at, but may not be all that useful. Anyway.. Everyone seems to agree that generating nodes shouldn't be too hard, except for picking the nodeline to start with. I think I have a plan, though. balance = # of lines /* max inbalance */ for (line = 0 thru # of lines) for (line2 = 0 thru # of lines) if (line2 is on left side of line) left_count++ if (line2 is on right side of line) right_count++ } if ( abs(left_count - right_count) < balance) balance = abs(left_count - right_count node_line = line } Ok, this isn't a real C program, of course. Just an outline. Basically, we check every line and see which one is the most balanced. However, I haven't even looked at the nodeline (infinate length) spliting a line (line segment), which would cut the line in half, adding to both counts (one on each side). Then, of course, you would also keep track of the number of lines you split. So, how should we choose what line is best then? What sort of relation should the balance have with the # of lines split? Anyway, that's my plan for picking the line. Once you have your nodeline, you have 2 half sized areas to check over for the same thing (best nodeline). Doing this this way, it seems to me then when we get to a point where all the lines have a zero count on one of the two sides, you now have a convex polygon, and can make it a ssector. I'll have to analyze this theory, though, to make sure. Also, after the first split, you have 2 halves, about the same size. So, you only have half as many lines to check. But, since there are 2 of them, it will take just as long as the first time around (second level of the tree vs. the first "top" level (bottom?)) Not totally sure how much time this method would take, off hand, but I'm sure it won't be blindingly fast. Generating a blockmap ended up taking longer than I thought it would, but I think I understand why now. I might make a guess and say it would take 10 seconds to make the nodes for E1M1 (remember, I'm just guessing now!) Hmm, this might not be too hard to do after all. I think generating sectors is going to be harder.. ------- sectors ------- Ok, I also need to write up a routine to take your collection of lines and generate all the sectors. I have a plan for this, too, but there is one problem it can't deal with. I call it the "donut" situation. I'll get to this later, but first, my plan.. We start with some line. This line has 2 sides to it, left and right. So, we have to pick a side, lets say the left one. Ok, so we make a new sector and point the left sidedef to it. Also, we keep track of this lines first vertex. Now we check locate all the lines that connect to our working line's second vertex, and figure out which one we hit first going counter-clockwise. This now becomes our new working line. We set the left sidedef to point to out new sector also (if this new line's first vertex was the one that connected. If the second vertex wad the one that connected, we will use the right sidedef) we then move to the next vertex and check for the next line, until we return to our original vertex. Once we are back to out first vertex, we have make it around the sector. Now we have 1 sector. So, we look and find a sidedef without a sector, and repeat this whole process. When we no more "empty sidedefs" (sidedef not pointing to a sector), we are done, and have located all the sectors. Now, for the "donut" problem.. Consider these sectors: +------+ +-------------+ | | | | | +--+ | | +--+ +--+ | | | 1|2| | | 1|2 | 3| | | +--+ | | +--+ +--+ | | | | | +------+ +-------------+ The above method won't properly detect the sectors in these shapes. The only way I can see of properly making these sectors would be to use a "flood fill" type detection method to do them. This would really suck, if I have to do it that way. What I need is a way to tell if one sector is inside of another sector. Anyone have any ideas on how to do it? I think I could build a list of independant groups (groups of sectors that don't touch each other at any vertex), but I don't know how I'd figure out which ones are inside of sectors, if they even are. Please let me know if you have any ideas. Thanx. --------------- Other than that, I think I have everything figured out. Let me know if you find any bugs, or have any ideas for improvements.