Pathfinding with least turns

[Arkadesh]

Hello!

I'm looking for some pathfinding algorithm (for grid-based graphs) that produces path with as little turning points as possible. I am using A* currently, but creates a bit too jagged paths. Are there any known implementations that create more esthetically pleasing paths?

cheers,
Arkadesh

[ggambett]

Have you tried tweaking the arc cost function to penalize the movements you don't want?

[Arkadesh]

Hmm.. Could you elaborate a bit? I've tried changing it so ie horizontal movement costs less than vertical, but it helps only a bit - there still are jaggies in the path. And too extreme tweaking easily leads to paths that aren't shortest... Am I overlooking something?

cheers,
Arkadesh

[Bad Sector]

Try to create a curve for the path using the points of the A* algorithm as control points. Then make your object to follow the curve. I believe that the result will be very smooth :-)

[illume]

You can create a curve from the path points. Which creates more points that make the turns less gradual. That way smoothing out the path.

Or use circle paths to go around corners. Go through the path segments, and where the angle difference is > 45 make a circle path there.

But when you modify the path you need to check collisions between points again.

Cheer.

[Arkadesh]

Ah, no.. curve is rather far from what I want to achieve.. I just want my hero to walk in straight lines, but changing the direction as little as possible - so ie if he has to walk 4 grids down and 4 right I'd like him to go down first then turn right. A* will produce here a stairlike path, that is perfectly correct, just sprite changing direction all the time won't look nice...

cheers,
Arkadesh

[C_Coder]

A* has a tendency of going diagonal first and then continue in a straight line to the destination. I use cost 10 for horizontal & vertical and cost 14 for diagonal. This is the best config I found.

[Arkadesh]

To clarify things a bit more - I don't allow diagonal movements at all in my A*, just vertical and horizontal.

cheers,
Arkadesh

[Bad Sector]

Then you don't need A* but another algorithm (i can't think any like what you want however)

[ggambett]

A more complex solution would be to use DA* (Directional A*). Make a grid where each node encodes position and heading. For each grid node you'll have 4 A* nodes. Set the costs so that changing the heading and moving costs more than moving without changing the heading. Note that this isn't the same as "vertical costs more than horizontal".

[C_Coder]

Then you don't need A* but another algorithm (i can't think any like what you want however)

If that is the case then you have to make a big cost penalty when the direction is changed or else your 'objects' will move like a staircase!

[Davaris]

This is what you can do with the path A* returns:

For each point in the A* path check if you have a line of sight (LOS) from it to the first point.
If you have a LOS, throw that point away.
If you don't have a LOS add the previous point (that had a LOS) to your list of way points.

Repeat the above process with the point you just added and you will eventually get a much smaller list of way points each having LOS to the next point.

I haven't explained it very well. Try drawing a path on a grid that goes around some blocked areas and you'll see what I mean.

[PeterM]

Have you tried tweaking the arc cost function to penalize the movements you don't want?I would try this. Perhaps you could add to the path's cost for every direction change, leading to fewer staircase effects.

[Arkadesh]

Thanks for all the input. Now I'm a bit closer to posting on the Announcement section :)

cheers,
Arkadesh

[Robert Cummings]

I would have my movement decoupled from the grid and use hermite or catmull rom splines to achieve a nice smooth movement.

If that is not possible, then consider first generating your A* list of points to travel to, and from that list, generate a new path using interpolation or splines to create a more constant overall interpolated path. Note: I am not talking about player movement, but creating a new list of waypoints using a spline to smooth out the stair stepping waypoints.