New NODE format?

Don't know if any of you have been following the large level - new node format discussion. It would be nice to have all the port incorporate an enhanced node format for large levels. The ease for doing this is the basic issue:

(This assumes large level support which is basically a change from signed to unsigned for sidedef references and also vertex indexing.

After I was discussing this issue, RH read it and released a node format that supports > 64k SEGS, however the new format is both zipped (zlib) and the format is radically different from before. The vertex coordinate format RH chose is fixed_t (takes care of splitting lines better), but there's another way to do this too.

My thinking was ease of implementation rather than size so that port authors would have little to do to use the expanded format. IOW same structures with field expansion.

The format I was thinking of involves a change to unsigned int in the respective fields and maybe a change in the vertex coordinate format (although that adds a little bit of extra work in porting).

The vertex coordinates can either be: 1) the same as they are now (no change); 2) fixed_t or 3) float. Looking towards the future, if there's a change, float may be more appropriate since converting that to fixed_t is easy to do. The new vertex data would be added at the end of one of the existing node lumps (eg NODES). Since there's a new id, there can be a length field so you can locate the vertex extension easily.

The question?

Would you prefer to use ZDOOM style nodes or a new node format that is identical to the old format except that fields are expanded to 4 bytes where applicable? (All this also involves GL nodes, but it already has a GL_VERT so slightly different here)

I was thinking my format would be much easier to implement, but maybe that's just me gNd3 would be the GL id and nNd3 perhaps for expanded stock nodes? This would also be easy for ZENNODE and BSP to support.

So far Legacy, DOOMSDAY and RISEN3D tend to favor the simpler change. It would be best if we all agreed and then perhaps I can talk to RH and also have him support this too.

Please let me know if that's of any interest or if I should just use the zdoom format for the expanded format. or if you have some other ideas.

Eternity may not be able to use the same compression library as zdoom, as I believe it's not GPL. Also, we have zero use for GL nodes as Eternity does not have a hardware renderer.

If you wanna come up with a format that doesn't involve compression or GL stuff, I'm open to supporting it; otherwise, no. I'd want to be able to create a version of BSP that supports the new format, and with those kinds of changes, that would not be possible.

Also, you would need to code some meta-data into the lump header so that it can be easily distinguished from normal node data, as I do not intend to translate old nodes into new ones at run time, or add a run-time BSP builder to my port.

As noted, the id for the new NODES is "nNd3" stored in the first 4 bytes of data in the "NODES" lump.

GL data is optional as it is now in GLBSP.

Didn't think that the compression stuff would present other issues, so thanks for pointing that out. You are correct, ZLIB is not GPL, however, anyone is free to use and modify it (just in case that makes a difference to you).

Overall, there's a preference for Vertex to be fixed_t. So the header in NODES tentative design layout would be:

"nNd3", "int length of extended nodes"
"extended node data...",
"vVr3", "int lenght of extended vertices",
"fixed_t vertices"

This would imply that the SSEGS, etc are also in extended format.

I don't really see the need for compression; the structures are getting marginally larger and people have millions of times the disk space and hundreds of times the internet bandwidth that they had in 1994. Decompression is slow, and would require dependency on yet another external library, which may not be available on every platform to which Eternity can otherwise be ported (including DOS). Thus I remain against dictating mandatory compression.

I would use more than 4 bytes for the magic identifier. Something longer would be less likely to be aliased by valid normal node data. Also, putting size and *file offset* for both the nodes section and the extended vertex section in the file header would make it significantly simpler to process the file.

In the end, the format needs to be described in BNF or some other formal language so that there is no ambiguity.

In short, this is a very messy undertaking and it seems that all the solutions people have cooked up seem very (read: VERY) hackish. For instance, can you guarantee that the first 4 bytes of the NODES lump could never otherwise be the 4 bytes nN3d (int: 1681084014, or in the case of a old-skool nodes lump, first vertex x coordinate: 20078 y coordinate: 25651)

Unless you can insure that no nodes lump ever created has a first vertex with those coords, you need to re-think your format a little bit.

SoM said:

In short, this is a very messy undertaking and it seems that all the solutions people have cooked up seem very (read: VERY) hackish. For instance, can you guarantee that the first 4 bytes of the NODES lump could never otherwise be the 4 bytes nN3d (int: 1681084014, or in the case of a old-skool nodes lump, first vertex x coordinate: 20078 y coordinate: 25651)

Unless you can insure that no nodes lump ever created has a first vertex with those coords, you need to re-think your format a little bit.

I think if the following 4 bytes are all 0 it would be safe. A partition line of length 0 doesn't make much sense, does it?

Quasar said:

I would use more than 4 bytes for the magic identifier. Something longer would be less likely to be aliased by valid normal node data. Also, putting size and *file offset* for both the nodes section and the extended vertex section in the file header would make it significantly simpler to process the file.

In the end, the format needs to be described in BNF or some other formal language so that there is no ambiguity.

Thanks for the info - idea is to make it work to everyone's satisfaction. (and yes, I agree that compression is not useful in today's world - simplicity is better).

Yes adding a bit more will make ambiguity pretty much 0. Can make the first 4 bytes xFFFFF, since that can never be valid vertex numbers. [the 0 Graf suggested works too) Can also add some redundancy since that will make safety checking rock solid.

Revisions: Add new id "eXt3", an offset to first Nodes and offset to first Vertex to accommodate the new ideas:

xFFFFFFFF, "eXt3",xFFFFFFFF (I just like FF since it's easy to spot)
int offset to extended nodes" (always 20)
int offset to extended vertex
"nNd3",
int length of extended nodes"
"extended node data...",
"vVr3",
int length of extended vertices
"fixed_t vertices ... "

So combined with that, here's the way all this has implicit safety:

If you find eXt3, using the offsets you better find nNd3 and vVr3 at those offsets. Plus the offsets can't exceed the lump size. Additional checking can use the length field to double check this even more. You can never exceed the length of the lump, plus the sizes have to integral units of the structures they define. (that's essentially what I was thinking with the older format too - but this is even better).

Conclusion: This will work without any ambiguity.

I think spec as struct layouts is simple and to the point. These translate directly to code.

deep said:

I think spec as struct layouts is simple and to the point. These translate directly to code.

Beware of endianness.

EDIT: Oh, and while we're talking about a new standard format, would be nice to work on a library people could use to manipulate the nodes without having to reinvent the wheel.

I dont think its a good idea because;

- You can already make extremely large levels with the 64k limit. Such big (detailed) maps even tend to run slow on modern computers.

- You can use hubs to make multiple maps act like 1, which is a much better idea, because it doesnt get slower as the whole map gets bigger.

- There will be more incompatibility problems until all the major nodebuilders have adapted. (Yuch, we already have enough people that post like "why does my map not run?" and "why does my nodebuilder not build?")

CodeImp said:

I dont think its a good idea because;

So what? Right now ZDoom has its proprietary extended node format and you can bet that somebody will use it sooner or later. Why not define a standard for this before it gets out of hand?

the zlib license is GPL compatible.. there would be no licensing issues using it in eternity.

"The license of ZLib.
This is a free software license, and compatible with the GPL."

from here


edit: its also extremely portable and it might even be possible to include the parts you need as part of the eternity codebase because of this

Julian! You have come out of hiding!

SoM said:

Julian! You have come out of hiding!

Only in your dreams ;P

CodeImp said:

I dont think its a good idea because;

Actually you can't make large levels without considering the node builder. IIRC, there are only 2 nodebuilder that support >32k sidedefs ATM (they can fall within the range of regular nodes .. with mods to unsigned in the regular nodes for up to 64k ssegs).

Hopefully, this discussion will also make the other node coders aware of the new extensions so they can revise both the regular node support as well as add the extended format.

FYI, large levels run just fine on current machines (starting with a 1gig PIII, GF2 and above) :)

The important thing is the goal. As Graf said, need to get a concensus before things get out of hand.

So, why not go for a further extended new level format while you're at it? Some more fields and flags for things, sides and sectors could make (advanced) editing infinitely more comfortable.

Fredrik said:

So, why not go for a further extended new level format while you're at it? Some more fields and flags for things, sides and sectors could make (advanced) editing infinitely more comfortable.

Except extended nodes only imply changes in node builders. What you suggest would mean an incredible amount of changes within editors.

Editors progress.

Fredrik said:

So, why not go for a further extended new level format while you're at it? Some more fields and flags for things, sides and sectors could make (advanced) editing infinitely more comfortable.

wouldn't that conflict with ports that already provide a way for such things (like zdoom, and like eternity is currently developing)?

Changing the basic level format (VERTEX, LINEDEFS, SECTORS, THINGS) is only possible if ALL the current ports were to support the same format. And then all the popular support utilities have to be changed. However, it's an option when everything else is done :)

ATM the basic node format is challenged by the current level specs:)

Any extensions a port wants to add via custom lump names and that really doesn't affect any utilities is up to the port(s) authors.

Haven't read what Eternity is adding (please explain), but AFAIK none of the other ports add anything to the level format yet. They do add to the "things you can do" via various lumps like scripting and definitions of behavior.

Eternity is getting around the problem of binary format limitations by using a text script attached to a map via MapInfo called ExtraData. ExtraData is an EDF-like language that can provide extended values for line, sector, and thing map entities. In your editor you put in a special sort of that entity (for instance, the ExtraData control object), and then one of the fields on that object is interpreted as an ExtraData record number.

The engine hashes the record number and retrieves the appropriate ExtraData record, then puts the extended field values into the run-time version of the object (like mobj_t, line_t, etc).

This is infinitely extensible and can allow association of any type of information with map entities (integer, fixed-point, floating point, string, etc). It can even interact with EDF to a degree, and is thus very powerful.

As of right now, only ExtraData for mapthings is functional, and is required for use alongside the Small scripting engine. Line and sector extensions will be added gradually, however.

Is this extended node format dead? Nobody's talking.

I'm beginning to wonder myself. Maybe my requirements of no *required* compression (a flag or something to indicate compression wouldn't be a problem, as then I'd have the option of implementing support for it now, later, or never) and no mandatory GL nodes (have no use for them) were deemed unacceptable or something, I dunno.

At any rate, it's only a matter of time until Eternity supports 2^16-1 limits instead of 2^15-1. The use of shorts in DOOM was weird enough given the fact the code was 32-bit and hard drives were getting bigger every day, but the use of SIGNED shorts is plain illogical. Wherever -1 is used as a sentinel or null value, it is just as simple to use another number, such as the limit. Technically you could keep the short signed and program node builders to change their indexing to account for the negative indices, but that would really be dirty in the code in both editors and the engine. I wouldn't advocate a hack like that, so the change to unsigned is the most logical.

The only thing holding me back is the amount of code that'll probably need to be changed. I imagine that this kind of change can break stuff you don't expect it to even affect, and thus it will have to be done carefully.

No it's not dead.

I like to let the dust settle since RH got upset at me for suggesting a simpler alternative and felt he had no need to change anything. My POV is that if one is going to confiscate existing resource names and changing their contents, then one should discuss this with the other port authors. If he'd invented new lump names, none of this would have affected any of the ports, hence my desire to have a standard extended format to avoid ports crashing left and right.

As you can note in my first post above, I am looking for a concensus and asked Legacy, JDOOM and Risen3D the same question. The goal is to actually have ports support the very large levels possible and thus provided a design that is more straightforward to implement. The 2 formats have different id's, so implicitly that's how you can tell is one is compressed or not. (or did you mean an option within this new format?) GL nodes were always an option (either format), so also not a problem.

As I said, I can do either one - that was never the issue. But which one will actually get done given a choice?

Port wise (as you noted) there has to be support the large level format which also involves a change to the BLOCKMAP since it too will exceed the stock stuff. Lee K already did this, so maybe you already used his code? IOW, you build the blockmap from scratch at load time - takes a few ms of time.

Switching to unsigned is fairly simple. The compiler should flag most signed comparisons that turn out to be "always true". What I did was search for the vars that are changed to unsigned and then just verify the code at each location. Went very fast.

Most work is for sidedefs. You define NO_INDEX as 0xffff and compare to that (not -1). Vertices are real easy, since all they every do is index, same for linedefs in the node stuff. All in all, you should be able to do this no sweat.

Then when that is done, I have a sample level with over 64k sidedefs and 33k linedefs so you can test. This is the same level I gave RH quite a while back so he could test the large level stuff.

If there's real interest I can supply the alternate node format described (more or less) in this sample level. We have the summer to work this out.

There's also the simplest alternative - just keep everything more or less the way it is and rely on implicit identification. IOW, all the node field formats stay basically the same with just some fields adjusted as required. A rought overview:

1. NODES - increase to unsigned int the 2 "child" or "ssector" reference(vs short now). Allows for SSECTOR indexing past 32k that are possible with large levels. Vertex stuff optionally increased to int ? (see notes below).

2. SSECTOR - increase to int first SSEG. Could increase number of SSEGS to int, but unsigned probably fine since 64k SSEGS per SSECTOR is OK (comment?). This allows for > 64K SSEGS

3. Vertex, linedef references within NODES and SSEGS all changed to unsigned. Could make some int vs unsigned short just to be ready for anything (same notes comment).

Notes: Things to consider (add more if this is something that is of interest vs the other "signature" method)

a. There's a theoretical chance that when extra vertices are added by the node build process, you can exceed 64k verts, however, in practice, that's extremely unlikely since the only way to get that many verts is to pack sidedefs - which takes an ungodly amount of time for a level that size, plus makes editing almost impossible. Hence having verts as int (vs unsigned short) solves a problem that may never occur except by someone to prove a point:) I made a level like that, just for the academic drill to see what problems it presented.

b. Storing the vertexes created using the same current x,y format makes this very simple, but brings up the "slime" issue in situations of close tolerances where the node building process rounding error causes a renderer "line" - same as what you get now. That was the original impetus for the fixed format that added quite a bit more work. Depends on how fussy one gets vs what you get back for the effort.

You'd identify this type of format implicitly since the lump sizes will exceed the maximums possible using the current format. For example, if the number of SSEGS is > 64k (since that's the first object that gets into range trouble), it has to be this format. This also means that this extended format will never be generated unless the SSEGS exceeds 64k.

Anyway, that's another POV for something that is easiest of all with the main issue being the fixed vs stock vertex format.

Comments?

Why would RH need to support it?. Zdoom is unlikely to support legacy, eternity etc specific maps and it has it's own nodes builder. So there's little point in supporting the new format.

It's an issue for the other ports as they share the same nodes builders. And of course an added pain for codeimp and yourself to support yet more formats.

Szymanski said:

Why would RH need to support it?.

Theoretically not at all. ZDoom already has an extended node format. It's just that some people think they have to do it differently and frankly, after deep's latest posts here I somehow doubt he will create something better because there's already talk about compromises.
ZDoom's format doesn't take any compromises but it just happens that it's compressed and for whatever reason I don't get this scares certain people off.

Read the posts Graf - we are focused on cooperative objectives, not innuendo. My reasons are very simple and are as stated (read them) - not just to do it "different". I don't believe in making things overly complicated just to save a few bytes. Waste of coding time in today's world.

The overall issues are all discussed above - the difference is more than just compression - it's one giant lump, format is different, extra code beyond reading the data is required and so on. Besides that, ZDBSP doesn't support "fake bridges" and some other constructs, so there are real level problems with it. Meaning, that the other node builders also need to get revised and making it simpler for them to achieve the same result would benefit everyone, not just Zdoom.

The issue is not to be different (and I never said so, in fact it's a choice as stated in the 1st post and I invited RH to join this discussion!). The issue is to get ports to use whichever one makes sense for whatever reasons port authors have.

The "talk about compromise" is getting easier options and choices confused with "compromise". IMO, the fixed thing is not significant - but if someone thinks it is, we'll stick to the original spec. It's nice to be able to see more than 1 alternative. I really don't care. For that matter if they think the zipped etc stuff works, do that - said so right up front. The choice is given to everyone.

For sure the latter option given is much simpler to implement. Whether the rare "lines" are an issue is up to others to decide. It's not a level breaking issue though.

PS: as a point of interest, RH's current format can't run the sample level I made :)