Hi all,
I have one question that always bugs me. It might be considered the de facto standard for pathfinding in games to use search algorithms such as Dijkstra and A* (or any A* variants). Couple it with a decent map representation and you already have a navigation system. In fact, I always resort to this mechanism when implementing pathfinding. However, I also notice that in the field of Computational Geometry, there are some algorithms to find the shortest path between two points in a 2D or 3D environment. As the field name suggests, their approaches are geometrical. Here are some paper examples of the aforementioned techniques (I'm not sure if their free copies are available on the internet though).

• [font="arial"]M. Sharir and A. Baltsan. On shortest paths amidst convex polyhedra. Proceedings of the second annual symposium on Computational geometry, ACM, 1986, 193-206.
• [font="arial"][font="arial"]M. Sharir and A. Schorr. On shortest paths in polyhedral spaces. SIAM Journal on Computing, SIAM, 1986, 15, 193-215.
• [font="arial"][font="arial"][font="arial"]P. K. Agarwal, R. Sharathkumar, and H. Yu. Approximate Euclidean shortest paths amid convex obstacles. Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2009, 283-292.
  So my question is, why does the AI approach seem to be more appealing to the game developer community? What is the limitation of the geometrical approaches? I suppose it's about their rather simple obstacles, which usually only consider simple, but not necessarily convex, polygons or polyhedra. But then again...anybody has an opinion?
  
  Thank you.

There's a slight difference between gaming approach and computational geometry approach :
- In gaming aspect, most of the time we try to find the paths in the space which contains multiple disconnected objects (which may have high polys), and there are restrictions about which region on the space can be passed or not (eg. tank cannot pass river, has to go through bridge, or tank cannot climb wall, etc.). Moreover, the target is real-time.
- Computation geometry approach, most of the time they find the shortest geodesic distance only on the surface of a single object (which may have high polys). I believe, most of the time the path can go anywhere as long as it's on the object surface. In other world, it's free to go anywhere on 2d manifold. Since the aim in computational geometry is not for gaming (not sure what are the applications, lol), their approaches may not be in real-time, as long as it can find accurate shortest distance (and can publish a paper from it, rofl).

Hi EonStrife, thank you for your response.

- In gaming aspect, most of the time we try to find the paths in the space which contains multiple disconnected objects (which may have high polys), and there are restrictions about which region on the space can be passed or not (eg. tank cannot pass river, has to go through bridge, or tank cannot climb wall, etc.).

Yes, this is what I am suspecting. Computational Geometry approaches apparently only consider simple obstacles, and treat every part of the obstacles similarly.

Moreover, the target is real-time.

However, the original Dijkstra & A* are not real-time as well. At least, they don't have the notion of "elapsed time". There are real-time variants of A* (LRTA*, TBA*, ...), but similarly, I am of the belief that we can also design real-time variants of the geometric approaches.

- Computation geometry approach, most of the time they find the shortest geodesic distance only on the surface of a single object (which may have high polys). I believe, most of the time the path can go anywhere as long as it's on the object surface. In other world, it's free to go anywhere on 2d manifold.

One problem is, of course, to find the shortest geodesic path on the surface of an object. However, the second problem, that I am more concerned about, is how to safely navigate in an environment consisting of obstacles, which is similar to the common pathfinding problem in computer games.

their approaches may not be in real-time, as long as it can find accurate shortest distance

Well, this doesn't seem to always be the case. The last paper that I mentioned in the original post saves the computational time by only finding an (adjustably) approximate path.

(and can publish a paper from it, rofl).

LOL at this too. Ironically, I am a PhD student.

you need to 'filter' which computational geometry technique can be used. If you use directly, then it will not make sense. For example, there's a building mesh, the tank might climb up and down the bulding mesh if the computation is only about finding the shortest distance.

Keep in mind that the best answer to these problems is often a hybrid. For example, you could use A* on the high level (e.g. room-to-room plan), a navmesh on the middle level (moving through a complex room), and local steering to deal with dynamic obstacles (e.g. other people).

If, as is often the case in academia, you are more concerned with ideologically pure silver bullets, you often will come up with a substandard result.

Rather than phrasing the competition as AI vs. Computational Geometry, I'd think of this as Heuristic vs Algorithmic.
Dijkstra's algorithm can be proved to give the shortest path in a given worst-case time budget;
A* is a heuristic (and a great one) that helps direct the Dijkstra search in most instances, but that can actually make it take longer.
And as other replies indicate, the correct answer is to use the ideas from both.

Heuristic solutions are very common in game development, since they are often easy to generate and test and the world in which they operate is often more controlled.
Computational Geometry is a branch of the theory of computer science that attacks problems from the algorithmic side, so it focusses on exact or precisely controlled approximations to shortest paths, for example by coming up with continuous analogs of Dijkstra's algorithm or exploring how adding nodes to a mesh can improve the quality of Dijkstra solutions or generalizing to large data sets with I/O efficient models of computation.
When you have time, it is often beneficial to step back from heuristics to see if ideas from exact algorithms give new insights that can be used to improve heuristics.

Another thing to consider is, what is to be gained by the "perfect path"? As engineers, we are often searching for optimality of a behavior when, in reality, humans (et al) are rarely optimal. Also, there is also a threshold of perception. If you burned 4x more clock cycles on a path, but you can't perceive the difference, what did you gain?

@EonStrife

there's a building mesh, the tank might climb up and down the bulding mesh if the computation is only about finding the shortest distance.

It seems to me that by considering, for example, the simpler bounding boxes of the meshes, we can use computational geometry approaches too, can't we?

***

@IADaveMark

Hi Dave, thank you for your response.

Keep in mind that the best answer to these problems is often a hybrid. [size=2]For example, you could use A* on the high level (e.g. room-to-room plan) […]<br /> </blockquote><br /> <br /> I realise that there is no one-suits-all solution. My initial question was whether geometric approaches can act similarly to A* to find a path in the environment. However, from your explanation (as well as EonStrife&#39;s comment), geometric algorithms seems to fail to (or at least are hard to) find a path for higher lever abstraction, so A* is more suitable for that purpose.<br /> <br /> <br /> <p style="text-align:center;">***</p><br /> <span style="font-weight:bold;">@jack snow</span><br /> <br /> Thank you for your response too, Jack.<br /> <br /> <blockquote class="ipsQuote" data-ipsquote data-ipsquote-contentapp="forums" data-ipsquote-contentclass="forums_Topic" data-ipsquote-contenttype="forums" data-ipsquote-username="jack snow"><br /> Rather than phrasing the competition as AI vs. Computational Geometry, I&#39;d think of this as Heuristic vs Algorithmic. <br /> </blockquote><br /> Honestly speaking, I am not sure about the paraphrasing, as heuristic algorithms are also…algorithmic, no?<br /> <br /> <blockquote class="ipsQuote" data-ipsquote data-ipsquote-contentapp="forums" data-ipsquote-contentclass="forums_Topic" data-ipsquote-contenttype="forums" data-ipsquote-username="jack snow"><br /> Heuristic solutions are very common in game development, since they are often easy to generate and test and the world in which they operate is often more controlled. <br /> Computational Geometry is a branch of the theory of computer science that attacks problems from the algorithmic side, so it focusses on exact or precisely controlled approximations to shortest paths<br /> </blockquote><br /> OK, I&#39;m a bit confused by the term &quot;controlled&quot;. For the heuristic solutions, if &quot;the world in which they operate is often more controlled&quot;, how is it different from the geometric techniques, which focus &quot;on exact or precisely controlled approximations to shortest paths&quot;?<br /> Nevertheless, from these sentences, it seems like the targets of these solutions are different, aren&#39;t they?<br /> <br /> <blockquote class="ipsQuote" data-ipsquote data-ipsquote-contentapp="forums" data-ipsquote-contentclass="forums_Topic" data-ipsquote-contenttype="forums" data-ipsquote-username="jack snow"><br /> When you have time, it is often beneficial to step back from heuristics to see if ideas from exact algorithms give new insights that can be used to improve heuristics.<br /> </blockquote><br /> When I started studying game programming during my undergrad years, I found that people always used these heuristic algorithms, so I learnt about that. Only recently I read about Computational Geometry&#39;s shortest path problem, and it seems like people in that area see the problem from a different perspective. The mechanisms may not be easily adaptable to computer games (not to say that we may not see the applications of those mechanisms in computer games), but it still is interesting and useful to learn from their point of view. Drawing inspirations from the two approaches might be beneficial to solve the general pathfinding problem. Although, no silver bullet.<br /> <br /> <p style="text-align:center;">***</p><p style="text-align:left;"><span style="font-weight:bold;">@IADaveMar</span></p><p style="text-align:left;"><span style="font-weight:bold;"><br /> </span></p><blockquote class="ipsQuote" data-ipsquote data-ipsquote-contentapp="forums" data-ipsquote-contentclass="forums_Topic" data-ipsquote-contenttype="forums" data-ipsquote-username="IADaveMark"><br /> Another thing to consider is, what is to be gained by the &quot;perfect path&quot;?<br /> </blockquote><br /> Yes indeed. It is often the case that we don&#39;t need such optimal path, and finding it is a waste of resources. When I posted the original question, I was thinking that the geometric techniques can also produce approximately short path for games, but considering jack snow&#39;s comment, it might not be comparable.

The problem as I see it (from my limited knowledge of computational geometry) is that CG and pathfinding are approaching different problems.

Traditional pathfinding is about avoiding regions with high traversal cost or which are not traversable; this means potentially scoring different paths and taking the best from among a series of options. It's about the least cost traversal - not necessarily the shortest path traversal. Yes, the least cost generally decays to shortest path in trivial environments, but keep in mind that game environments are often far from trivial. As Dave noted, you may need to do several types of pathing: steering around mobile obstacles (which AFAIK CG can't handle at all), moving around hazards, avoiding slowdowns, selecting routes between abstract locations... these can actually mostly be collapsed into a single pathfinding operation with suitable cost metrics for A* and especially hierarchical A*, which is why that method enjoys such success in game development.

By contrast, CG seems to be concerning itself entirely with shortest path traversal. Mathematically, it should be possible to deform the search space such that you can create an isomorphism between shortest path and least cost (e.g. just stretch out areas with higher traversal cost to make them "longer") but it seems to be that this transformation would actually be harder to compute than to simply use a pathfinding algorithm to begin with. It also doesn't seem to work well in cases with large amounts of non-traversable space; you again can deform the search space to suit, but computing the deformations would be incredibly difficult in the general case.

Consider that every time you deform the search space manifold to have a "hole" representing non-traversable space, you are in fact increasing the order of the surface. To put it simply, you're making the search space many times more complicated, and increasing the difficulty of the CG approach correspondingly. The papers I've scanned over concern themselves entirely with 2-manifolds, i.e. surfaces along 3D shapes, whereas even a single holed geometry (e.g. a torus) is not a 2-manifold anymore. My topology is rusty, but IIRC, the more holes you add and the higher order the surface, the more difficult it becomes to solve a shortest-path problem in the general case. Supposing you have several thousand non-traversable spaces in your search space (not unrealistic for a game like, say, Starcraft II) you're talking about shortest-path geometry in a search space that is quite likely well beyond the largest that tenable search algorithms have been developed for in the CG field.

In short, yes, you could probably substitute computational geometry for A* or what have you, but the cost of modifying the problem to suit the CG approach is almost certainly prohibitive... especially with virtually optimal graph-search algorithms like A* available.