Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I have a list with coordinates - output from A* algorithm - and I would like to make my characters smoothly follow this path with rotations.

So I have something like A and I want to get C

enter image description here

How can I do this ?

EDIT

To make myself a little bit more clear:

I am more interested in smooth turning as I already know how to walk from one node to another.

EDIT

As many people find this useful (me too) I am posting link to Daniel Shiffman's "Nature of code" where he discusses a lot of game AI (and physics) problems e.g. steering behaviours http://natureofcode.com/book/chapter-6-autonomous-agents/#chapter06_section8

share|improve this question
    
Isn't pathfinding built-in in Unity? –  joltmode Jan 3 '13 at 10:07
    
@Tom Well yes but I have my version implemented anyway. The point of this question is to get smooth turns(rotations) while walking on the path. –  Patryk Jan 3 '13 at 10:09
3  
A nice term to Google in this regard is 'Steering Behavior' :) –  Roy T. Jan 3 '13 at 10:15
3  
@RoyT. Of course ! I have been reading this few weeks ago and already forgot :/ This is a great article on path following with awesome math + physics explanation natureofcode.com –  Patryk Jan 3 '13 at 10:20
1  
I just wanted to thank @Patryk for the link - looks really informative, and I've been searching for a good resource on steering behaviour. –  Christian Jan 3 '13 at 12:47
show 1 more comment

6 Answers 6

up vote 7 down vote accepted

If you want smooth paths in a tile-based environment, there's no way around applying some path-smoothing on your A* waypoints. In his book about programming game A.I., Matt Buckland describes a simple and fast algorithm to smooth a path (basically remove all edges that can be removed without causing an intersection with your obstacles).

Once you have remove unnecessary edges like this, your first case (A -> B) is solved. Smoothing out the edges in your graph could be accomplished in several ways. Most likely, Hermite splines would work (depending a bit on your obstacle density and tile-size). Another option could be steering behaviors, where you start to steer towards the next waypoint, as soon as you're half a tile away from the current target (this really depends on how fast your "agent" moves/turns).

share|improve this answer
add comment

A->B can be solved by using navigation meshes instead of a grid. This implies a big change in pathfinding data generation.

Cases like C and D are just corner cutting: if character is moving in a path and inside a "corner" (cell where previous, current, next cells are not on a straight line), push it in direction of both previous and next cell. The only problem is to determine the distance from real position (the pushing distance). That would probably require the distance from current cell as input. Something like this:

push_dir = average( prevcell.pos, nextcell.pos ) - curcell.pos;
push_dist = cell_half_width - distance( char.pos, curcell.pos );
char.pos += push_dir * push_dist;
share|improve this answer
add comment

To a more human realistic movement, try integrating with Steering Behaviors. (C# version of the classic OpenSteer http://sharpsteer.codeplex.com/) You get the output of AStar and let the steering behavior care about the movimentation (One of the samples show exactely how to do this, navigate following a path)

share|improve this answer
add comment

As others have mentioned, for the second case you will need to implement some sort of spline or (actually a better fit for your example) give the unit some sort of steering behavior.

However, for the first case, there is a solution that is both simpler and gives better results than path smoothing. It's called Theta*, and is a simple (and relatively new) extension of A* on grids that allows units to move in any direction between grid-points.

Theta* vs. path smoothing

There is a nice article explaining Theta* (from which I stole the above image) here

share|improve this answer
add comment

In case of navigation from point to point, I used the difference in angles (current player direction vs. direction from current point to next point) and then gradually changed the angle to final angle as the movement happens. Check this game here where the airplanes move from 1 point to another but the turn is not abrupt but on watching carefully one can identify the points of the path. (the game works only on mobile though preferably iPhone/iPad).

share|improve this answer
    
This is exactly what I ended up doing. –  Patryk Jan 9 '13 at 8:22
add comment

I've had good luck with Catmull-Rom splines (a type of cubic spline as also recommended by @bummzack). The good part about those is that the spline will always go through the control points, many others do not. Implement something like this:

t    = <time*>
t12  = t + 1.0
t23  = t
t34  = t - 1.0
t123 = (t + 1.0) / 2.0
t234 = t / 2

c1 = controlpoint[0];
c2 = controlpoint[1];
c3 = controlpoint[2];
c4 = controlpoint[3];

l12 = lerp(c1, c2, t12);
l23 = lerp(c2, c3, t23);
l34 = lerp(c3, c4, t34);
position = lerp(lerp(l12, l23, t123), lerp(l23, l34, t234), t);

*time is a value [0,1] between the control points 1 and 2.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.