How to minimize directional changes?

Beginner Questions
#1

Hi. I am a beginner to Unity and C#, and am making a real-time RPG where characters move by clicking somewhere on the screen.

I have been successful in getting the A* project to work, thanks to this tutorial: http://hobblygobbly.tumblr.com/post/93960257057/how-to-setup-the-a-pathfinding-project-in-a-2d

My characters are finding the optimal path, restricted to 8 directions, while moving through 16x16 nodes. The problem, however, is that the paths are often generated in a way such that there are way too many directional changes. This causes the character’s sprite to rapidly spasm between two adjacent directions. Here is an example of one such path: http://imgur.com/a/OAE8c

My solution was to perhaps change the algorithm so that it calculates P_min+T_min instead of P_min, where P_min is the minimum distance from the start to end nodes, while T_min is the least number of turns. This would eliminate the unnecessarily large number of turns. I’m not sure how I would implement that though. Can someone help me?

I haven’t touched any of the code from the download link, and am using the Free Version 4.0.10.

Any help would be appreciated!

#2

Hi

Try to change the ‘Heuristic’ setting in A* Inspector -> Settings -> Pathfinding.
Try to set it to Diagonal Manhattan or Manhattan. I think that should give you a better path.

#3

That’s a lot better. Thank you!

#4

I actually am running into a similar issue where I want the target to move in straight lines and avoid changing directions. Is there a way to set a penalty or something like that to discourage direction changes? I am using the Manhattan Heuristic.

#5

Any thoughts on an ideal location on where this could be updates? Ideally a way to increase the cost of directional changes.

#6

@ebbybeh
if you want to avoid changing directions, then I suggest you create two graphs: one is for horizontal and the other is vertical.
For horizontal graph you have to remove all the connections which are vertical, for vertical graph you have to remove all the connections which are horizontal.
https://arongranberg.com/astar/documentation/dev_4_3_84_2d0a89df0/gridnode.html#RemoveConnection

and it is easy to decide which graph you want to use for pathfinding.
if start.x == end.x then use horizontal graph
else if start.y == end.y then use vertical graph
else no path exist as it need direction changes

1 Like
#7

There’s no way to directly penalize direction changes with this package. Using the manhattan heuristic or diagonal manhattan often helps, but it does not directly penalize direction changes. Doing this properly would need a custom pathfinding algorithm, and pretty big changes to this package, I’m afraid.

#8

Gotcha, thanks for the response

#9

That’s an interesting idea, I’ll try exploring it more.