1
\$\begingroup\$

There is a path, generated by my implementation of A*, where diagonals aren't allowed, and the heuristics is the Manhattan distance.

Is there a way to always or nearly always find a path with the least amount of turns? Even if it's a bit longer, and even if it costs more computationally.

Or is there a way to algorithmically "fix" a path later? Like on the image below, cut those long detours and replace them with those blue parts.

My current version is far from optimal, both length-wise, and both turn-wise. I also tried multiplying the heuristic value of a tile, if:

  • it isn't going in the same direction as the line made from the previous 2 tiles. But that didn't help either.

enter image description here

\$\endgroup\$
  • 2
    \$\begingroup\$ Why do you even have those detours? Especially the second one that hugs the wall. That shouldn't happen with A* \$\endgroup\$ – Bálint Apr 11 '19 at 9:33
  • \$\begingroup\$ Köszi, I knew that something was not quite right, there was a banal typo. \$\endgroup\$ – Tudvari Apr 11 '19 at 11:22
4
\$\begingroup\$

First fix your A* implementation so that it will find the shortest path.

Adjust the cost of the turn instead of the heuristic. This means that when you generate the neighbours the one going straight ahead gets cost 1 and the one where you make a left or right gets a higher cost depending on how large a detour you accept.

This means that every tile can get up to 4 nodes in the A* graph, one for each direction the entity can come from. For the purpose of A* you have to treat them as separate nodes.

It is fine if the heuristic underestimates the total cost, but not if it overestimates. So manhattan will still be good enough.

\$\endgroup\$

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.