Timeline for Dynamic navigation mesh generation algorithm
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 22, 2016 at 12:27 | comment | added | Stormwind | Looking into this soon, solved the triangulation already, using a "sweep over" method. I'll edit the answer instead of explaining it in this comment. | |
| Apr 21, 2016 at 13:36 | history | bounty awarded | Apolo | ||
| Apr 19, 2016 at 15:30 | comment | added | Apolo | Yep, I get it ! Could you complete the answer for future reference and so I can give you the bounty ? Many thanks for your time and help ! | |
| Apr 19, 2016 at 13:02 | comment | added | Stormwind | The only criterion being that a "connect" does not run over an obstacle. In fact, connecting to a closest-by obstacle should work as well, since eventually (even if all obstacles were connected to other obstacles but none to the arena) the last obstacle will be connected to the arena (as you'd loop through them all). To be more exact re. the "share vertices" i wrote earlier: They would not share a single vertex, only share the same location, but still be separate vertexes (as one is "earlier" in the big poly, the other "later"). In the end, there would be a dataset with convex polys. | |
| Apr 19, 2016 at 12:53 | comment | added | Stormwind | Maybe just construct a parallel data set? Something like: Define an approximate "game arena centerpoint" or "chunk centerpoint". For each obstacle, define a centerpoint. For each obstacle, calc the distacne to the arena centerpoint. Sort them so the biggest distance is first. Loop through them all, each time connecting to what is so far the arena poly. Ie. the arena poly grows, and obstacles may in fact be connected to (former) obstacles. In the end, you have one single poly in parallel data only. Apply HM on that to partition into convex polys, use the convex poly set for pathfinding? | |
| Apr 19, 2016 at 12:24 | comment | added | Apolo | So I should track those "fake edges" to re-link vertices that are on them after triangulation (not sure to be clear - I mean it will be seen as an obstacle in the node graph, so I should correct it) | |
| Apr 17, 2016 at 11:57 | comment | added | Stormwind | You would connect the obstacle square/poly with the surrounding arena poly, by drawing two lines, one from an arena corner A to an obstacle corner B, and one from that same corner B back to the same arena corner A, hence merging the two polys into one. It would have two vertexes on top of each other, but that shouldn't be a problem, just keep track of the line segment's direction, to be able to skip the bad line of them when testing for opposite vertexes in the HM partition. Ofc cut the arena poly where this happens. Same with next obstacle, "bridge" to a nearby arena poly vertex. | |
| Apr 17, 2016 at 10:01 | comment | added | Apolo | Maybe I should go for a Delaunay triangulation instead ? It seems to accept holes in the poly | |
| Apr 17, 2016 at 10:00 | comment | added | Apolo | I made a pen to show different use case : codepen.io/VincentCharpentier/full/bpMYVd I don't see how you would merge an obstacle with the area polygon if they have no vertice in common (first example). (Thanks for your help) | |
| Apr 16, 2016 at 19:20 | comment | added | Stormwind | It's not as much the circle (which IS a polygon) being the problem, but that your polygon is not simple - you want to triangulate between multiple polygons. BUT: Would it be acceptable to merge any obstacle polygon with the surrounding "arena" polygon, each time one appears (and reverse as it disappears), so that you still end up with one simple polygon for that chunk? This would simply mean finding the closest vertex in the "full" poly. THEN the HM algorithm (which is rather simple to implement) would do the job you want. You'd possibly have to number each obstacle, for chain breaking issues. | |
| Apr 16, 2016 at 17:01 | comment | added | Apolo | Thanks for your try. I'm aware circle being a problem, that's why I turn them into polygons. I had a look at people.mpi-inf.mpg.de/~mehlhorn/ftp/FastTriangulation.pdf and I am looking for the outer tirangulation algorithm. My map is divided into chunks and each one is responsible of maintaining its navmesh. This way I have multiple levels of pathfinding and I can avoid generating a huge navmesh each time something is added. | |
| Apr 16, 2016 at 0:53 | history | answered | Stormwind | CC BY-SA 3.0 |