How can I make my units follow predetermined paths?

Question

I'm planning my first game and am planning on using the engine set out in Beginning Android Games, as it deals with a load of stuff that is just noise at the moment to me (because I've no real world experience yet). There's no real time restraint - this is a learning experience more than a real world project, although I would love to be able to release something at the end of this project.

The way the book tells me how to do movement has been very much acceleration and velocity based with other forces thrown in (wind, gravity etc) but it's not covered how I can set a predetermined path for an enemy to follow. I was thinking that I could use a lookup table to map points for the enemy to head for, and then I'd just need a way of smoothing out the turning so that the motion is fluid. Is this the correct approach?

I know this is a bit of a vague question, and I would give you some code, but I'm very much in the planning phase at the moment, so I'm just looking for some pointers or things to think about whilst I'm trying to work out how it's all going to hang together.

Answer 1

Here are some resources to get you started:

• What path finding algorithms are there?
• Amit’s Game Programming Information
  • This article in particular discusses path smoothing, like you had mentioned.
• Pfadsuche-Applet (Pathfinding Applet)
  • This site's in German, but useful once you figure it out. Hint: The big green Start button doesn't start the applet, it changes the brush. The little grey Start button starts it.
• Clearance-based Pathfinding
  • This technique is useful for games with units of variable sizes.

You can find more on Wikipedia, which has some good articles on specific algorithms, and of course Google. Once you start investigating a little more, feel free to post more questions specific to your implementation.

Answer 2

This tutorial at XNA Resources shows one approach.

Basically, you store your waypoints as a queue of coordinates, then move the entity toward the first point in the list. Once you reach that point, remove it from the queue and continue to the next point. Depending on your game, you might want to set some limits on how quickly the entity can change speed/angle so the corners aren't so sharp.

Answer 3

You could use a steering algorythm, giving the entity a (set of) goals/waypoints and let the entity manage itself, considering its position/velocity/acceleration and its goal.

• The avantage is that is easy to go from a static waypoint to a mobile target :)
• The inconvenient is that its not really a pathfinding, and more a local search : the entity react to obstacle, but does not search the map (to avoid ntering a cul-de-sac for exemple). You may have to add some waypoints using some higher level reasonning (ie high level pathfinding to get the waypoints, and low-level steering to go from one waypoint to another one)

There are some good algo and exemples here, with differents method.

Answer 4

I'd suggest creating a list of cubic Bézier curves for each unit to follow. This will give you nice smooth paths.

To join multiple curves into a single curve smoothly, every control point at which two curves join must be on the line between the two control points on either side.

They only difficulty with them is that maintaining a consistent speed of travel requires a bit of extra work. One way to achieve that is to do a binary search each frame to find the new value of the curve parameter required to travel a specified distance.