Grid Graph find path is zig zag?

[Cabriter]

Grid Graph
4 connections
Heuristic Manhattan
Heuristic Scale 3

ref:

Can I reduce the Manhattan zig zag?

I’m using a Manhattan heuristic and four connections to get my seeker to turn at right angles (so it only moves North, South, East, and West to get to where it needs to go). This works, but the paths generated tend to involve many rapid turns, producing a zig zag effect: [image] Ideally, in an open area like that, it would be great if the path were a simple “L”, with only the one turn, but even just reducing the number of unnecessary turns would be great. Is there a way that I can reduce/elim…

Is there a 'string pulling' or 'funnel modifier' built in to use with a Grid Graph + AI Lerp?

Hey there, I want to find a way to have less zig-zaggy paths on a grid graph using AI Lerp. Should http://arongranberg.com/astar/docs/class_pathfinding_1_1_funnel_modifier.php - do the job? Are there any examples I can look at?

[Cabriter]

[Cabriter]

That’s what I want，Make as few turns as possible。

ref:
https://arongranberg.com/astar/docs/pathfinding.html#Heuristic

[Cabriter]

[Cabriter]

That’s what I want，Make as few turns as possible。

[aron_granberg]

Hi

There’s no way to find a path with a minimum number of turns. That would require a completely different pathfinding algorithm. However, the manhattan one should give you a pretty decent result on an axis aligned graph. Is your graph rotated perhaps?

[Cabriter]

Yes, it rotated by 45 degrees

[aron_granberg]

Hmm, yeah, in that case the manhattan heuristic will not work as well for what you want.

[Cabriter]

Are there other heuristics we can look at? And if I want to change the algorithm, where should I change it to be more compliant?

[aron_granberg]

The relevant part of the code is the Path.cs script -> CalculateHScore method. You probably want a manhattan heuristic, but rotated 45 degrees in the XZ plane so that it lines up with your graph.