Building nodes and other helper fields

As you may or may not know, I've been attempting to write an editor. My
next portion of coding now requires an algorithm for a node builder, and
obviously produces a few questions.

For this posting, we will be using a generic sample map: a circular ring.
The ring is composed of two concentric circles, with an outer circle
defining the boundires of the map, and an inner circle that defines the
central pillar. The outer radius of the ring is 768 units, with the inner
radius being 512 units. However, this ring is asymettrical, as it has 9
sides (or some other odd number).

My diagram for this map simple has the outer circle being a scaled up
version of the inner circle, with lines going from the outer points to the
inner counterparts (or vice versa - can't count on the map designer being
consistant.)

Now, the questions:

1. I've been thinking about building the SSECTORS and SEGS first before the
nodes - however, the an initial BSP cut would obviously go right through
one of the segs in such a ring if it were radial. What is the procedure
for the SEGS in the remote sectors that get divided by this - is there some
magic number (such as -1) that needs to be set, or is there some other
procedure?

I do know that that partition lines seem to be spanning across multiple
sectors, as in E2M8 (sometimes going through the entire map but sometimes
stopping halfway through, where I assume another partition line is
located.)

2. The DOOM Specification is not exactly clear on the NODES and similar
lumps work - is there a better resource that describs the data structure
more clearly or is that the best thing our there aside from the Doom source
code?

3. For the BLOCKMAP, I've been attempting to write an algorithm that
minimize its size (since it is a significant bottleneck.) It basically
does a frequency count of the lines that are on a specific coordinate
(after X Modulus 128) from all points after the start line, and takes the
starting blockmap location to be the position that has the lowest frequency
count. Is this a correct algorithm, or is there a better alternative? (If
you've done something like this before, you either know what I'm talking
about or have something completely different.

That seems to be all of them. Normally, I'd check with another program to
see how it does the magic, but that would almost feel like plagerism
regardless of whether copying algorithms is permitted or not.

Raymond Martineau wrote:
> That seems to be all of them. Normally, I'd check with another
> program to see how it does the magic, but that would almost feel like
> plagerism regardless of whether copying algorithms is permitted or
> not.

There is nothing wrong with checking another program as long as you
respect its license. For the most part as long as you write it from
scratch you are okay, or if you use GPL code in a GPL project with
attribution you are perfectly within your legal rights. Same with BSD
licensed code in any project.

BSP is GPL'd and does an excellent job making nodes:
http://doombsp.sourceforge.net/

Grabbing the Doom source (now GPL'd) and seeing how the engine reads the
data structures may give you clues and insights into how to generate
those structures:
ftp://ftp.idsoftware.com

Note that certain ports such as ZDoom are licensed separately by id and
using their code may not be kosher. ZDoom, for example, uses code from
projects such as Heretic and Hexen and cannot be GPL'd, at least not
entirely. I am not am expert on ZDoom's license but I know enough to be
careful about borrowing code.

It is okay to use code -- authors know what the GPL means and make a
specific, deliberate choice to license their code that way knowing that
it means people such as you and I may copy their code in our own GPL
projects. Just be sure to give credit where credit is due.

--
John Gaughan
http://www.johngaughan.net/
john RemoveThis @johngaughan.net