5
\$\begingroup\$

I'm trying to implement pathfinding in my game, I'm using navmesh with triangles.

I'm able to find a path but I want to simplify the path. This is what I have right now :

path

Green quad is start position and blue quad is the destination, the path taken by my character is in white.

Wireframe :

wireframe

Node 1 and Node 2 are in differents triangles, I want to delete Node2 and go from Node1 to final destination.

How can I simplify this path ?

\$\endgroup\$

1 Answer 1

Reset to default
3
\$\begingroup\$

What you are looking for is called string pulling, or the funnel algorithm. Basically these algorithms work by seeing if they can straighten the path. They do this in small increments until they have straightened it as much as they can - taking into account static obstacles and such. Here's a link that ought to help get you started.

http://digestingduck.blogspot.com/2010/03/simple-stupid-funnel-algorithm.html?m=1

\$\endgroup\$
3
  • 1
    \$\begingroup\$ By the way, what are you using to path find? If using A* you may have your heuristic set up wrong. A* should do better than that on it's own! \$\endgroup\$
    – Alan Wolfe
    Commented Jun 1, 2015 at 21:01
  • \$\begingroup\$ Yes I'm using A*, thank you, I knew something was bad in my code, will try to make it better. What is the best path for you in my screen ? \$\endgroup\$
    – Aldo
    Commented Jun 1, 2015 at 21:32
  • \$\begingroup\$ I'd fix the A* and if that didn't help enough, then move onto string pulling. Imo \$\endgroup\$
    – Alan Wolfe
    Commented Jun 2, 2015 at 0:46

You must log in to answer this question.

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