Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Novalis

3D Pathfinding in real time

This topic is 6237 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

Ok folks, here''s this problem I''ve been working on for many months now... I had a working solution to it a while ago, but it was quite ugly, and since I''ve been away from it for long enough to forget half the code I''m convinced I''m better off looking for a more elegant solution. Now to the problem... I have program which loads and renders Quake maps in real time. It also keeps track of and draws dynamic models (read "people") in that map. My goal is to be able to click on one of the models, and then click somewhere else on the map, and have the model figure out how to get from where it is, to where I clicked, and then do it. I have a pretty good idea in my head of how I''d like that to happen, but I got stuck on one detail of that idea which I have posted a question about in the math and physics forum. So, while I''m still hoping to solve that detail, I''m wondering if anyone else has done something similar, and if so, what their approach was?

Share this post


Link to post
Share on other sites
Advertisement
Hi Novalis... not seen you around for a while.

Can''t answer your question directly, but have you tried digging up some of the old bot code? I remember Reaperbots were very effective at learning the map layout, for example. I believe they did something like set up a network of valid nodes through trial and error, and then traversed them with pretty much any standard graph algorithm such as A* or whatever.

Share this post


Link to post
Share on other sites
Greets Kylotan! Yah, I''ve been lurking around a bit, but I haven''t had a lot of energy for these mind bending personal coding projects lately...

After some helpful tips from Graham over in the Math and Physics thread I started, I believe I have an outstanding solution to my problem. It lies in computing the "Medial Axis Transform" of my entire BSP. This transform provides a linked set of points that are equidistant from all nearby polygons. So if I use the MAT junctions as the nodes for an A* search, I should in theory get even faster paths then using the BSP leaves (since there should be far fewer MAT junctions then BSP leaves), with the added bonus that I don''t have to do any collision detection because I can pre-compute the largest bounding sphere which can travel from any given MAT junction to another.

The only problem is that I don''t fully understand the paper I have on computing MATs Hopefully this weekend I''ll be able to puzzle it out and return with good news Monday!

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

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

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!