2
\$\begingroup\$

I have a character linked by a rope to a fixed point, in an environment with obstacles. I want to do a pathfind that take into account the rope.

Here, if the character followed my current pathfind in yellow, he would get stuck. I want to find the blue pathfind instead. To be more specific, I want to find the path so that the rope is the less "tense" possible when the character reach the target. Example 1

Another example with more obstacles: Example 2

I really don't know where to begin (Custom A* ? Graph theory ?) and would appreciate any help or documentation on the subject.

\$\endgroup\$

1 Answer 1

4
\$\begingroup\$

The simplest solution would be to always path find from the stationary anchor and then append that path to the rope from the player to the anchor and use string pulling to get the path for the player to follow.

That will always get the path that results in the least tension on the rope.

\$\endgroup\$
4
  • \$\begingroup\$ Exactly what I was looking for. Thanks a lot. \$\endgroup\$
    – Alikae
    Commented Jun 18 at 13:12
  • 1
    \$\begingroup\$ Note that the path to the target from the stationary anchor needs to be appended to the path the rope is currently taking from the player to the anchor - to make sure you correctly thread back through any obstacles you wove between to get where you are. This path will probably include a lot of unnecessary doubling-back, but the string pulling should take that up. \$\endgroup\$
    – DMGregory
    Commented Jun 18 at 14:40
  • \$\begingroup\$ After contemplating it for a moment, I think this is suboptimal in some cases, where the target is very close to the character, but there's an obstacle near the rope source. The ideal pathfind would be the direct route, but this algorithm would have the character backtrace to the source before backtracking to the target. I can't think of a more optimal solution that's also fast though. \$\endgroup\$ Commented Jun 18 at 19:37
  • 2
    \$\begingroup\$ @MooingDuck if the anchor is always fixed you can pre-floodfill up to the limit of the rope. That gives you an O(1) lookup though you'll still need to string pull for the actual path to follow. \$\endgroup\$ Commented Jun 19 at 5:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .