How to create a smooth path for characters to follow in 2D game

Question

I am creating an iPhone / Android tower-defense type game were the enemy units must follow a predetermined path, which will be the same for the iPhone and Android versions. I had initially thought cubic bezier curves or a b-spline would be the way to go, however I haven't found a straightforward way to generate the paths and describe them.

Is this the right approach, and if so are there any tools to generate the path graphically and determine the coordinates of the control points, etc?

The path also needs to be smoothed (i.e. not a collection of line segments).

Answer 1

What I'm looking for is a Catmull-Rom spline (see: http://www.cubic.org/docs/hermite.htm) which is just a type of Hermite curve where the control points are computed "automatically". Apple actually uses this in the SDK (search the docs for catmull-rom).

See also the Wikipedia article.

Basically, this just allows you to input a list of points, and the function will give you a smooth path passing through those points.

Answer 2

The simplest path-finding algorithm I know of is A* search. It will give you the shortest open path between two points. To describe a specific path through the game you just need to set waypoints essentially and A* from point to point. Hope this helps. Good Luck!

EDIT: You can find A* implementations everywhere, Wikipedia being the obvious place to start.

Answer 3

Have you try A-Star algorithm? I think it is quite good for path finding. A-Star algorithm has input of two points, the first is the object to move, the second is destination, the algorithm will then find a path between both, by evading block objects.