I need to use the contour tracing algorithm making game AI, because it seems easier than A* algorithm, anyone knows about this algorithm or any suggestion to read ,thanks.

Contour tracing in a nutshell: Walk directly towards the goal. When you hit a wall, follow the wall around until you can walk directly towards the goal.

BTW, A* being difficult is not a good reason not to learn about it.

And contour tracing has it's issues.

For example, assume you had this room, where "G" is the goal, and "P" is the player.

+-----------------------+|                       ||   G    |    |         ||        |    |         ||        |P   |         ||        |    |         ||        +----+         ||                       ||                       ||                       |+-----------------------+

If your contour tracing decides to make left hand corners, your player may get to here (periods show its path)

+-----------------------+|                       ||   G    |   P|         ||        |   ^|         ||        |.  .|         ||        |....|         ||        +----+         ||                       ||                       ||                       |+-----------------------+

and realize nothing is stopping it from moving towards the goal... so it goes to the left and ends up against a wall.. starts making left hand turns, and gets stuck running in circles.

And obviously it can't make the decision as to whether it can walk towards the goal based on direct line of sight, since in this scenerio, it will never have line of sight.

+-----------------------+|                       ||        |              ||        |              ||        |   |          ||   G    |   |P         ||        |   |          ||        |              ||        |              ||                       |+-----------------------+

I think A* is pretty straightforward and computationally more efficient than this.

Edit: I forgot to mention that contour tracing will not help you at all with 3D terrain. It might be a good backup to use if the object encounters something in its path that wasn't handled by a more robust pathfinding algorithm though.

[Edited by - pragma Fury on March 31, 2006 7:44:11 AM]

Thanks Sneftel and pragma Fury.

Though I see the A* is much more popular than the contour tracing, however it looks a little complicated and need more knowledge about the data structure. In fact, I only need a easy and fast applied way to make the game AI, I still think the code with contour tracing will be much easier for understanding, but I can't find any relating reading about contour tracing, maybe that's because it's too old ,the A* may be powerful but not so easy for me to learn it in short time.

And hi, pragma Fury, could you tell me more how the contour tracing algorithm detect the line between the P and G, does that need collision test? thanks

Quote:Original post by timaer
And hi, pragma Fury, could you tell me more how the contour tracing algorithm detect the line between the P and G, does that need collision test? thanks

Yes, if you want to test for line of sight between P and G, you would need to do a collision test.
If you're unfamiliar with the various forms of collision detection for objects in motion, here's a pretty decent page of tutorials. Check out Tutorial A for sure.

Thanks pragma, but I'm afraid I can't read that tutorial,the link seems unavailing :(

Quote:Original post by timaer
Thanks pragma, but I'm afraid I can't read that tutorial,the link seems unavailing :(

That's very unusual. It seems to be working for me right now.