So, I’m about done with Efficient Triangulation-Based Pathfinding https://www.aaai.org/Papers/AAAI/2006/AAAI06-148.pdf. It sounded sooo simple! Let me know if this is of interest to you. I’ll polish it up for public consumption and maybe put it in C++.
EDIT: According to the paper, it out performs grid-based A*, but it doesn’t always produce the optimal path. Also, the number of nodes grows differently. A larger map doesn’t imply more nodes. It’s tied to the number of obstacles
What is the best way to create a map where I can access individual points and triangles?
Right now, I’m feeding the Triangulator maps with holes in them, but I want a big map with a bunch of holes for testing. Hard coding all of those points to ensure they’re CCW is going to be a PITA, unless someone knows an algorithm.
Plus, I was well into developing the above when I found out I need to implement Local Clearance Triangulation http://graphics.ucmerced.edu/papers/14-tog-lct.pdf because of a major bug in calculating the clearance across a triangle. So, I’ll need to alter the triangulation. I’d like to do it without having to copy the whole mesh every time I split a triangle, which is the only way I can figure to do it.