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.

How do you know when a path-finding algorithm is really needed?

There are contexts, where you just want to improve AI navigation to avoid an object, like a space -ship that won't crash on a planet or a car that already knows where to steer, but needs small corrections to avoid a road bump.

As I've seen on similar posts, the obvious solution is to implement some path-finding algorithm, most likely like A*, and let your AI-controlled object to navigate through the path.

Now, I have the necessary skills to implement a path-finding algorithm, and I'm not being lazy here, but I'm still a bit skeptical on if this is really needed. I have the impression that path-finding is appropriate to navigate through a maze, or picking a path when there are many alternatives. But in obstacle avoidance, when you do know the path, but need to make slight corrections, is path finding really necessary? Even when the obstacles are too sparse or small ?

I mean, in real life, when you're driving and notice a bump on the road, you will just have to pick between steering a bit on the left (and have the bump on your right side) or the other way around. You will not consider stopping, or going backwards. A path finding would be appropriate when you need to pick a route through the city, right ?

So, are there any other methods to help AI navigation, except path-finding? And if there are, how do you know when path-fining is the appropriate algorithm ?

Thanks for any thoughts

share|improve this question
2  
I would say nop: red3d.com/cwr/steer –  nathan Oct 20 '13 at 13:46
    
steering is a form of pathfinding, I think this question should be phrased "Do I need A* for pathfinding"... –  BlueRaja - Danny Pflughoeft Oct 20 '13 at 17:33
    
@BlueRaja I disagree, path finding != obstacle ovoiding. But that's your opinion, and I asked for any thoughts, so.. thanx! –  yannicuLar Oct 20 '13 at 17:43

1 Answer 1

up vote 9 down vote accepted

No.

There are a few levels of navigation available to you. In order of complexity, the choices go something like:

  1. Scripted movement. All the movements are pre-programmed. Characters follow pre-defined paths, simply updating their position to make them move along a path.
  2. Random changes. Characters continue moving forward, and at random intervals turn left or right. Collision detection and response still have a factor here, but it only keeps the character from walking through walls, not avoiding obstacles.
  3. Simple steering. When an object is detected ahead of the character, it randomly chooses between a right or left turn. There are two forms of this:
    1. Turn when colliding with the object. This is the easier form, since it can use the existing collision detection and response code to add some steering.
    2. Turn before colliding with the object. This is a little more advanced where the characters need to test the position where they're going to be soon. When an obstacle is detected in that forward position, the character turns (hopefully avoiding a collision altogether).
  4. Steering. More advanced steering. This type uses the "checking in front" type of avoidance. It will decide a direction to turn based on a various factors. It can use a ray cast to determine the normal of the collision that's about to happen. With that normal, we can get a slightly better idea of which way to turn. For example, when approaching a wall like this: enter image description here
    It makes a lot more sense to turn right instead of left.
  5. Advanced Steering. The most advanced steering. This type uses multiple probes to detect obstacles ahead and in multiple directions. This gives us the most information when deciding how to turn, and how much to turn to avoid an object. In this way we can just make slight adjustments to avoid collisions.

As Nathan linked in his comment, the red3D article on steering is one of the best around. Their demos show some of the features you'd want to implement, including an example of advanced obstacle avoidance:

enter image description here

There are also a number of questions and answers about the topic on this site. Some good search terms would be: Steering and Boids.

share|improve this answer
    
Thank you for a very helpful and detailed answer –  yannicuLar Oct 20 '13 at 17:39

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.