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

Improve this question
\$\endgroup\$
2
  • 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, 2019 at 9:33
  • \$\begingroup\$ Köszi, I knew that something was not quite right, there was a banal typo. \$\endgroup\$
    – Tudvari
    Apr 11, 2019 at 11:22

1 Answer 1

Reset to default
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.

Improve this answer
\$\endgroup\$

You must log in to answer this question.

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