Timeline for Funnel algorithm : not possible with all convex polygons?
Current License: CC BY-SA 4.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 9, 2023 at 1:18 | answer | added | DisturbedBerry | timeline score: 3 | |
| Nov 8, 2023 at 21:22 | comment | added | Romen | It seems to me that the algorithm would have worked if you traverse the edge that actually narrows the funnel, instead of the one that widens it in B. Then the rays end up crossing and have to restart from that corner (either works). Repeating the algo from there finds a solution (done in my head). So I think your example is not implementing the algorithm correctly by allowing a widening step instead of narrowing. | |
| Nov 8, 2023 at 21:19 | comment | added | DisturbedBerry | Thanks for your input Romen. I added a disclaimer in my post ! I just found the answer to my problem elsewhere. I'll write it down a bit later to share it. | |
| Nov 8, 2023 at 21:18 | history | edited | DisturbedBerry | CC BY-SA 4.0 |
added 110 characters in body
|
| Nov 8, 2023 at 21:14 | comment | added | Romen | I think you need to eliminate some confusion with an edit. When you mention a "polygon" I am thinking of the overall navmesh. Obviously that polygon is not even convex in your case and the first comment probably understood it that way too. The subdivisions of the navmesh are also polygons (quads in your case) and they are all convex in your example. The comment you refer to that the polygons can be convex is actually referring to the subdivisions, not the overall navmesh. | |
| Nov 8, 2023 at 20:20 | comment | added | DisturbedBerry | Well @Romen that's exactly my point ! The author (and some others) claim that this algorithm CAN work with any convex polygons π I'm aware that I'm not using triangles in this example and I want to know if it's possible, in some way, to use any convex polygon instead of triangles, like some are claiming ! (For the record, I tried the algorithm with triangles only, and it works like a charm. I would just prefer to be able to use any convex polygon) | |
| Nov 8, 2023 at 20:17 | comment | added | Romen | Something else that I have noticed, you have not triangulated your nav mesh the same way as the article. I see quadrilaterals in your navmesh, where they only have triangles. Your example of the alogirthm failing also seems to be related to checking vertices that belong to different triangles too. | |
| Nov 8, 2023 at 18:50 | comment | added | DisturbedBerry | Hi @Romen π We only restart the algorithm when one of either side is trying to pass over the other. (From what I understand. In fact, it works very well for me this way if I only use triangles) This happens mostly when you need to get around a corner. In this case, we are simply blocked because both sides are stuck. The more I think about it, the more I'm sure this algorithm doesn't necessarily work with all convex polygons. Thanks for your comment ! | |
| Nov 8, 2023 at 18:39 | comment | added | Romen | I think you're missing a step from the article "and restart the algorithm from there (G)." It looks like this is supposed to be used recursively/hierarchically using a new starting point based on the last cycle? | |
| Nov 8, 2023 at 15:49 | history | edited | DisturbedBerry | CC BY-SA 4.0 |
added 199 characters in body
|
| Nov 8, 2023 at 15:41 | comment | added | Pikalek | As far as convexity, I didn't see any claim about that in Demyen's thesis (starting on pg 52) - it was designed for pathfinding in a triangulation. It may still work with polygons (haven't worked through enough of the math to say), but convexity doesn't seem to be the issue. | |
| Nov 8, 2023 at 15:39 | comment | added | Pikalek | It might help if you edit to include a link to the article that you're following, but it looks like you're either misunderstanding the algorithm or maybe there's a lack of clarity in the material - when you hit that impasse, the path gets updated & the funnel gets reset. | |
| Nov 8, 2023 at 15:15 | history | edited | DisturbedBerry | CC BY-SA 4.0 |
edited title
|
| Nov 8, 2023 at 15:14 | history | edited | DisturbedBerry | CC BY-SA 4.0 |
deleted 8 characters in body; edited title
|
| Nov 8, 2023 at 15:12 | comment | added | DisturbedBerry | All of these polygons are convex though. If the map as a whole must be convex the algorithm won't be really useful π | |
| Nov 8, 2023 at 15:06 | comment | added | Adam | That shape in your diagram isn't a convex polygon | |
| S Nov 8, 2023 at 14:31 | review | First questions | |||
| Nov 8, 2023 at 15:11 | |||||
| S Nov 8, 2023 at 14:31 | history | asked | DisturbedBerry | CC BY-SA 4.0 |