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?

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.

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!