Here are a few ideas to think about:
1) The popular A* algorithm is probably the most accurate and efficient pathfinding method for games that don't have many moving objects (quite rare). It will always find the shortest path to the goal (if possible). The only problem is that you have to map the grid every time an object moves, which is likely to be every step. This makes it slow and not suitable for most games. Also, it's very hard for inexperienced programmers to use.
2) Mark Overmars created a script that will move an object towards a goal while trying to avoid obstacles a while ago. It is now implemented into Game Maker as a set of functions. This method is great when there are few objects (and when they are small) but is not very accurate and will often fail or give weird results. The advantage is that it's a fast method that's easy to use. But it is not suitable for complex AI.
3. There are a few other techniques that can be used, for example the D* algorithm. There are other potential methods besides Marks. There is one that is quite reliable that I like. Basically, an object will keep a certain distance away from other objects until it meets the goal. The higher the distance between the objects, the less repulsion there is between them. When it fails, it doesn't give weird results like Mark's implementation does.
4. Another way to create effective pathfinding is to combine ideas. For example, an object may try to keep some distance away from other objects, but when it moves within a short range of obstacles it will try to use Marks potential scripts to navigate. And when the object has no other obstacles within a longer range, it might even use the A* to calculate the shortest path from start to finish.
Edited by xot, 13 April 2008 - 06:07 AM.
** Old Experts Topic **