Jump to content
  • Advertisement
Sign in to follow this  
timaer

Anyone knows the contour tracing algorithm?

This topic is 4436 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!