# Following a path in a smooth fashion

I am currently making a 2d tower defense game with a static, predetermined lane that the enemies follow (i.e. towers cannot block the path and path finding is not the problem I am trying to solve).

I am trying to figure how exactly to make units follow this lane in a smooth way. I have two rough ideas about how to do this, but I would love some input on which is likely to be easier to implement/the more standard technique. Or of course if I there is some totally different way that I haven't considered I would love to learn about that as well.

Waypoints: My first idea was to define the path as a series of hard coded waypoints. Units would then use a basic "seek" steering algorithm (such as this one) to move to each waypoint along the path in succession. However, I have wondered if it might be hard to keep the units from deviating to much from the lane I want them to follow. I wonder if inability to turn sharply enough might cause them to sort of "glide" out off of the desired lane. I suppose I might be able to prevent that though by allowing for a relatively strong steering force to be applied?

Bezier Curves: The second solution I have considered is to define the path with a bezier curve and at each time step calculate the point along the curve with is (dt * speed) away from the unit's current location. I suspect that this technique would make it much easier to precisely define the path that units will follow, but I don't know know how exactly to go about implementing this. Any suggestions?

Also, I don't this will change anyone's answers, but units also must be able to travel at a constant speed along the path. Additionally, I am programming this game in python using the pyglet framework.

Edit: Also for whatever its worth, I'm sort of trying to replicate the movement behavior of enemies in the Kingdom Rush.

-
Relevant: gamasutra.com/view/feature/131505/… What kind of unit density / size relative to tiles are you using? – monkey Feb 16 '13 at 21:31
I'll take a look at that article! I'm not actually using tiles though, just continuous coordinates to designate position. There will just be a static background image that shows the player where the units will move. – Pwnosaurus Feb 16 '13 at 21:39
I also found. gamedev.stackexchange.com/questions/26543/… A* works on non-grid maps. It could be a node path on kingdom that gets curved in a similar way. – monkey Feb 16 '13 at 22:27
Is there anything which can cause the enemies to leave the path and have to return to it? I ask because your Bezier-curve proposal suggests there is not, in which case there's no reason you can't precompute arbitrary data about the entire path and no "AI" logic is needed. – Kevin Reid Feb 17 '13 at 3:17

Allow me to introduce you to Craig Reynolds' famous paper on Steering Behaviors For Autonomous Characters. If you haven't read it, you should, it'll help you think through these sorts of problems, in particular take a look at the section on pathfinding.

The idea of Reynolds' paper is that you can use simple forces that combine to produce life-like, improvisational navigation around the environment. The movements are not based on path planning or global calculations, but instead use local information, such as neighbors’ forces, which makes them simple to understand and implement, but still produces very complex movement patterns.

The beauty of the approach is that you can combine several of the behaviors together. So, for example, your characters may have both a path-finding behavior as well as a separation behavior (to keep them from clumping too much), which can be combined as a weighted sum.

Another benefit to using steering behaviors is that there are a number of existing open source implementations in a variety of languages (e.g., opensteer).

UPDATE: I took a look at Kingdom Rush, and I think I may have misunderstood what you meant by "smoothly." I took it to mean more lifelike, but I think what you're after is more like the characters are on a train track. Also, reading more carefully, I see that one of your requirements is that "units must be able to travel at a constant speed along the path." Steering behaviors is not going to give you a constant speed of movement, but simple pathfinding combined with waypoints will. (I.e., don't use the "seek" behavior to get to the waypoint, instead simply determine the direction vector and have the unit move at full speed to that waypoint.) Use more waypoints to smooth out the route.

-

The solution in this Gamasutra article may be what you're looking for. The basic idea is to cast rays to a waypoint that is two steps ahead of your current waypoint "stepping" the ray a fraction of a cell's length and at each "stepping" of the ray checking to see if your player's collision volume collides with anything at the stepped position of the ray. If the ray gets all the way to the waypoint that's two steps ahead, then you can get rid of the intermediary waypoint. you can then continue this same process all the way to the "goal" waypoint...thus if your path can be accomplished by a straight line to the goal a straight line to the goal is the route your character will take. here's the article: http://www.gamasutra.com/view/feature/131505/toward_more_realistic_pathfinding.php?print=1

It also contains great things about turn radius and more natural turning behaviors and such...

-