[No] Exporting subsector data to zscript

[Rachael]

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.

[Graf Zahl]

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

[phantombeta]

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)

1. Trace the individual shapes by walking through the sector's lines, starting at some arbitrary line, it doesn't matter which.
   
   1. Start with some line. Use V2 as your current vertex and V1 as your previous vertex. [1]
   2. Iterate through V2's attached lines.
      
      1. Ignore the current line, when you reach it. [2]
      2. Ignore any lines we've already seen while tracing the shape.
      3. Ignore any lines that don't have our sector as one of their sides.
      4. 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.
      5. Calculate the angle made by V1, V2 and V3.
      6. 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.
      7. 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.
2. 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 ray casting algorithm)
3. Immediately flatten the shape tree, for simplicity.
   
   • 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.
4. Cut holes in the shapes. [3]
5. Triangulate by ear-clipping. [3]
6. (Optional - I currently don't do this) Improve the triangulation by performing a Delaunay triangulation on your triangulated shapes.

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 Triangulation by Ear Clipping, by David Eberly.

[Gez]

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

[TDRR]

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.