Timeline for How can I remove unnecessary nodes from my path?
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 14, 2015 at 19:44 | comment | added | Draco18s no longer trusts SE | That is, if Node[n-2] - Node[n+1] AND Node[n-1] - Node[n+2] (with n being the previously removed node) both differ, don't always pick the same one. Randomly choose between the two or alternate back and forth. Edit: thinking about this some more, you'd want to pick the one with the shorter distance. That would insure the best trim. | |
| Dec 14, 2015 at 19:40 | comment | added | Draco18s no longer trusts SE | In order to do that, you should loop through the array to find a node such that Node[n-1] - Node[n] has a different vector than Node[n] - Node[n+1] and then test IsPassable(n-1, n+1). If true, remove n and recheck. That way you're cutting off the extremes of the corners first, slicing them off slightly until the optimal path is found (it may be suboptimal by 1, e.g your example returning 0 --> 2 --> 18 -->19 but its close enough to not make that big of a difference). Also make sure not to slice the same side first every time, or you'll end up in a similar position. | |
| Dec 14, 2015 at 19:36 | comment | added | kasztelan | Thank you for input. I know why the algorithm behaves that way (should probably mention that, will update question). What I don't know is how to fix it so it'll always return the shortest path. | |
| Dec 14, 2015 at 19:24 | history | answered | Draco18s no longer trusts SE | CC BY-SA 3.0 |