ZDoom

Honestly, I dunno if you guys would be okay with this, but at this point I think it'd take a lot less finagling to just do what I'm doing already with the TDBots. Add a node every 16 tics or so on a human player's position, if it's too close to another visible and reachable node then get rid of it. Link them every 15 seconds or so and you have your nodes. It works well with the really barebones and simplistic "pathing" (if you can call it that) of the originals, and I imagine it'd be even better here having the ability to find a pickup and other targets, and so a reason to have actual pathing.

Of course if anything else materializes it'd be better to use that. But if not, I doubt anyone would be exactly furious about a system like this, if it'd probably still give better results than any of the other bots in currently maintained ports.

Both SLADE and UDB use triangulators and they handle most brokenhack issues fine.

I doubt this would need particularly complex "broken map fixing". For most cases, throwing away individual unconnected lines and "welding" the vertices of technically-not-closed shapes should be more than enough.
For the rest of the cases, it can connect the open ends of the lines and hope for the best (chances are the issues will be minimal in 90% of maps, given what it'd be used for), and provide a way for adding "fixes" to maps externally for the rare case this isn't enough.
Those that need manual fixes would honestly be a lost cause for automatic fixing, anyway, and in my opinion simply aren't worth the effort and the risk of breaking other maps trying to fix them. Acting like whatever is done needs to be perfect is counterproductive- there's no way to fix every single case correctly without external input.

In my engine, I triangulate sectors planes as such: (This should be helpful to anyone triangulating Doom maps)
[list=1]
[*]Trace the individual shapes by walking through the sector's lines, starting at some arbitrary line, it doesn't matter which.
[list=1]
[*]Start with some line. Use V2 as your current vertex and V1 as your previous vertex. [1]
[*]Iterate through V2's attached lines.
[list=1]
[*]Ignore the current line, when you reach it. [2]
[*]Ignore any lines we've already seen while tracing the shape.
[*]Ignore any lines that don't have our sector as one of their sides.
[*]Get the opposite vertex from V2, your current vertex. You'll have to check whether the current vertex is V1 or V2 of the new line, and grab the opposite of that. This will be "V3", your next vertex.
[*]Calculate the angle made by V1, V2 and V3.
[*]Select the line pair with the smallest angle, and now V2 will become V1, V3 will become V2, and we'll go back to the beginning.
[*]We've found a shape when we get back to our first vertex. If we end up at a vertex with no other lines, we've found an unclosed shape.[/list][/list]
[*]Build a "shape tree" from these shapes. If a shape is entirely contained by another, it's a child of that shape. (I use the [url=https://en.wikipedia.org/wiki/Point_in_polygon#Ray_casting_algorithm]ray casting algorithm[/url])
[*]Immediately flatten the shape tree, for simplicity.
[list]
[*]Shapes with even depth are solid shapes.
[*]Shapes with odd depth are holes in their parent shape.
[*]Shapes with a hole as their parent are solid shapes inside the hole, and can be simply turned into a depth 0/root shape, flattening the tree.[/list]
[*]Cut holes in the shapes. [3]
[*]Triangulate by ear-clipping. [3]
[*](Optional - I currently don't do this) Improve the triangulation by performing a [url=https://en.wikipedia.org/wiki/Delaunay_triangulation]Delaunay triangulation[/url] on your triangulated shapes.[/list]

Notes:
[1] You'll find your unclosed shapes during this step. Probably best to deal with them at this point.
[2] You can also ignore lines that have both sides pointing to your current sector, depending on what they are. Since this is for a navmesh, you'll probably have to take into account whether they're blocking, though.
[3] As described in the paper [url=https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf]Triangulation by Ear Clipping, by David Eberly[/url].

If there was a simple solution it'd be used by the engine already for some things.

Please don't hate me for saying this, but, I feel like we are no closer to a solution on this issue than when I made the first post in this thread.

I know people are coming in here with a good intent to try and offer a solution to TDRR for his issue, and that is good - but there's also a lot of naysaying going on in response to those solutions about how they won't work - but those naysaying posts never, themselves, offer a concrete solution that can send TDRR on his way with what he needs for this.

My main and only real interest with this is having bots in GZDoom once more that aren't broken. But TDBots is more than just "working bots" - it does have a navigation system. And for it to work - it's gotta somehow get nodes - from somewhere. That is really what would be helpful right now.

Right now the only real workable solution we have is pregenerated node lists that are uploaded either to maps themselves directly or spawned at the start of a level via ZScript by checking against the current map's md5 checksum.

If the goal here is to make bots that can navigate the IWAD levels, why not create LevelCompatibility fixes to close off those opened sectors?

[quote="JPL"]I kinda wish there were a highly portable (plain C?) library for triangulating Doom level geo, since I've seen enough people reinvent this over the years, that could be used in both engines and editors/viewers.[/quote]


As long as all sectors are properly closed, any generic triangulator would do. All the problems here come from those maps which have mapping errors like several of the IWAD maps (id's original editor made it far too easy to create broken stuff), or use open sectors for render hacks. There's no simple way to even construct proper polygons here that could be fed to a triangulator.

[quote="Graf Zahl"]Some of the IWAD maps would be affected, there's several with broken sectors in there.[/quote]
I'm not sure what your point is. It isn't trying to render the maps, so if it simply closes any subpath for a broken sector that would probably be good enough.

I kinda wish there were a highly portable (plain C?) library for triangulating Doom level geo, since I've seen enough people reinvent this over the years, that could be used in both engines and editors/viewers.

Some of the IWAD maps would be affected, there's several with broken sectors in there.

[quote="Graf Zahl"]Triangulating sectors in Doom is a non-trivial matter, because there's no sanity checks for proper construction. How would you try to handle maps with open sectors, either due to mapping bugs or render hacks?[/quote]
Personally I would just not support it. Automatic node layout of this sort assumes some level of sanity for the input data anyway - it will never work universally for any imaginable mod out there.

Keep in mind this entire thread is based on the premise that you can build a navigation mesh by placing points in the center of the subsectors and then do line tests to the centers of any touching subsector to see which paths are valid. That entire strategy only go so far. Also, as far as I know UDB uses an earclip triangulator for its sectors, so any map built in that thing would probably work just fine for this.

[quote="dpJudas"]In my opinion it would be better to triangulate the sectors in ZScript (using earclip or constrained delaunay triangulation) specifically for the purpose.
[/quote]

Triangulating sectors in Doom is a non-trivial matter, because there's no sanity checks for proper construction. How would you try to handle maps with open sectors, either due to mapping bugs or render hacks?

In my opinion it would be better to triangulate the sectors in ZScript (using earclip or constrained delaunay triangulation) specifically for the purpose.

The quality of BSP subsectors is affected by many things since they have to subdivide the entire map (with the painters algorithm for the software render), which can create local areas with an unexpected high count of subsectors. Those areas could make the navigation mesh behave buggy in the worst case scenario (the route of that the bots would follow could be very unintuitive). A recompile of the map, or GZDoom rebuilding the nodes with a new node builder, would alter how the game behaves. In short: while it is tempting to use this shortcut, it is not a good idea.

[quote="Rachael"]TDRR said that he needed the subsector data in order to effectively build the bot nodes in a level. The nodes would help the bots more intelligently navigate the levels than what means are currently available for this.[/quote]

I would also find this useful for making monsters that have an AI navigation route. Generally I have to place nodes by hand and painstakingly link them by TIDs or have them take off NOBLOCKMAP and do a trace to any that can be seen in order to record them.

The idea was to place nodes at the center of each subsector. Link them, and prune out all nodes with no links, or any that are in a place no player would be able to fit in. I assume something similar is perfectly possible with the triangulated mesh, I just don't know exactly how yet.