So you want to make a new level?
Alistair Brown
Thanks to everyone for the email asking about BSP trees and how I did them...
I thought that explaining how I made a (very simple) level by hand would
be more informative.
Firstly, I wrote a program in borland c++ that created the various data
structures (i.e. LINEDEFS, SIDEDEFS etc.) and used a cutomised version of
the PWAD writing routine from the newdeu sources. (great program BTW esp.
with the source code included). I may release the code for my program
when I get the automatic blockmap generator sorted out...
Anyway, first step was to draw the map on paper. This wasn't too difficult
as the level consisted of a square room with a square dais in the centre.
I needed this map a LOT. Mainly for making sure that I was using the correct
vertex numbers, and for other things like linedefs & segments.
Once I had the map and worked out a coordinate system (i.e. the scale + origin
of the map), I created the VERTICES. Note that the 8 vertices at this stage
(4 from the outer square + 4 from the inner), were not all the vertices that
were created. Some are created when you work on the NODES.
The LINEDEFS were the next stage. As far as I can tell, the first of the
two SIDEDEFS is the right hand side, of the line, the second for the left.
In other words, it's made a lot simpler if all the linedefs that surround a
sector go clockwise around it. (Note that I haven't tried the situation where
the first sidedef is -1 and the second is the sidedef to the left of the
linedef yet.)
Next the SIDEDEFS & SECTORS were created. For exact details on how each of
these are formed, see the doom specs (currently at version 1.2).
Now for the fun bit! The NODES are fairly complex to understand until you
get used to the idea of its tree structure. Basically an algorithm for NODES
would go something like this:
Nodes( in: box)
BEGIN
Choose a linedef in box - call it your nodeline
Create two boxes, left & right
Put in the left box all the linedefs to the left of the nodeline
Put in the right box all the linedefs to the right of the nodeline
IF the left hand box contains lines that COULD overlap one another
from a viewpoint the player can get to THEN
Call nodes(left hand box)
ELSE
Create a ssector with the lines in the left hand box
If the right hand box contains lines that COULD overlap one another...
Call nodes(right hand box)
ELSE
Create a ssector with the lines in the right hand box
Go back up a stage (i.e. return from this level of recursion)
There are two things to watch out for. Firstly, if a LINEDEF contains two
SIDEDEFS then when that LINEDEF is chosen as a nodeline, the right hand sidedef
is allocated to the right hand box, the left hand sidedef to the left hand
box.
The second thing is that the choice of linedef can be important. If you want
full details then have a look at Foley, van Dam, Feiner & Hughes "Computer
Graphics: Principles and Practice (2nd Ed.)" on the section about BSP trees
and how they relate to visible surface determination. (Watch out, there are
two sections on them). Basically, you want to choose a nodeline that causes
the fewer overall intersections with other linedefs, I'll explain about them
in a minute. Since this is not very easy to find (i.e. you would have to
build a BSP tree for each prospective linedef and compare the number of
overall intersections to find the fewest), it is easier to choose a nodeline
that interesects with the fewest LINEDEFS.
Secondly, the nodes are stored in the nodelist BACKWARDS to how you
would expect them to be defined. The golden rule is that no node will
make reference to a node that has a higher number than itself. So node
2 can only make reference to node 1, not node 3. Node 1 will reference
two ssectors, as it can't possibly reference another node as it has the
lowest number. Also, if you work backwards through the node list, the
left hand box is always dealt with before the right hand box. As way of
illustration, consider that a BSP tree has been generated from the above
algorithm that looks something like this:
A
/ \
/ \
B C
/ \ / \
a D b E
/ \ / \
c d e f
A capital letter represents a node, a lower case letter means a SSECTORS.
The 'leaves' of the tree will all be SSECTORS. This would be stored in
the node list as:
f,e,E,b,C,d,c,D,a,B,A
Now that the nodes were defined, the SSECTORS were created. These contained
the segs, NOT the linedefs. This is because a nodeline will usually
divide at least one linedef into two pieces. (One piece is assigned to
the left hand box, the other to the right hand box, sound familiar yet? :-)
In effect the segs are 'segments' of the linedefs, hence the name.
Okay, the hard bits past. REJECT contains a table (in bits) of whether
monsters can see from one sector to another. If all the bits are set to
0, then a mosnter will be able to detect you from any sector when you are
on any sector. (Not sure how much walls affect it though :-). If all the
bits were set to 1 then all the monsters would be blind, never able to
see you. From what I remember when I last played with reject, it's set up
like follows:
To sector
0, 1, 2, 3...
0 0 1 1 0
From sector 1 1 0 0 0
2 0 0 0 0
3 0 0 0 0
...
The bits are then constructed in the bytes (LSB to MSB) from top left to
bottom right as you read the table. So the above would be encoded as follows:
00010110 00000000
(as two successive bytes, assuming only 4 sectors are in the map). I hope
that I have the 'To' & 'From' round the right way, it HAS been a while...
Finally, the BLOCKMAP was the fiddliest bit of all. Mainly because it was
fairly difficult to come up with a suitable data structure to hold it. In
the end I made do with a linked list. All the blockmap contains is the
lines that exist in each square of the automap. Each square is decimal 128
wide & high, so my map was divided into 128 wide chunks, and the data for
each (reading from bottom left to top right) entered along with the origin.
NOTE: The blockmap is probably the most important element. If you make a
mistake with the blockmap and miss out a line then the level will crash at
some point (Usually when you try to move). If you have a zero length blockmap
then it won't crash but it works like an idspispopd simulation. (no clipping).
And that was it. I strongly recommend the doom specs produced by Matt Fell
and distributed by Hank Leukart on this newsgroup & several ftp sites inc.
wuarchive.
If you have any questions, critisisms additions, mistakes & general blunders
(bar spelling) to make, then feel free to email me (or post to the group).
Alistair
--
Email A.D....@bradford.ac.uk
Tom Neff
What I wonder is: Can't we *translate* the output of some CAD/CAM type
program -- a program that would make creating rooms, halls, etc, etc, as
easy as pie -- into BSP/PWAD ready data? Is there some standard that
hackers could code to?
Matt Tagliaferri
A.>Newsgroup: alt.games.doom
A.>Organization: University of Bradford, UK
A.>Hi,
A.>.... I may release the code for my program
A.>when I get the automatic blockmap generator sorted out...
I'll trade you a working Blockmap algorithm for a Working Node Algorithm!
matt.tag...@swcbbs.com!!!!
---
* OLX 2.1 TD * Hastur! Hastur! Hastur! Who says he can't be named?