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\$
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\$
  • 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 Jun 1 '15 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 Jun 1 '15 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 Jun 2 '15 at 0:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.