2
\$\begingroup\$

As a hobby project I am trying to re-create pathfinding similar to StarCraft 2 based on the presentation from GDC 2011: https://www.gdcvault.com/play/1014514/AI-Navigation-It-s-Not

Navmesh in SC2 (Image source)

The main takeaways from the talk are:

  • They build a dynamic navmesh calculating constrained Delaunay triangulation. They first calculate and cache it for the map in its initial state (static obstacles) and then re-run from there any time a building is added or destroyed.
  • They run a classic A* on the navmesh and then smooth the path using the funnel algorithm.
  • Units are not taken into account when building the navmesh. Walking around moving entities is handled by steering model based on Boids by Craig Reynolds.

So for the base path it's basically CDT → A* → funnel.

I solved all three separately. But the biggest unknown here is how to construct the navigation mesh from the triangulation.

I have tried multiple different methods, including:

  • graph connecting vertices of triangles
  • graph connecting centers (centroids) of triangles
  • graph connecting middle points of edges
  • combination of three above methods
  • merging triangles into convex polygons; connecting centroids

And all of the methods suffer from various problems. Graph based on the triangle edges uncontrollably 'likes' to pick the wrong side of obstacles, leading to path going around instead of straight (first image blue). Edge midpoint method doesn't do well with very long but narrow triangles at map edges (second image). Centroid method fails on zigzag triangles (first image pink). It is very hard to pick a method that would provide good paths in all interesting scenarios.

I made a demo app which allows to play with all the variants I tested: https://pathfinding-psi.vercel.app/.

I know that the map I am focusing on is very simple compared to a typical SC2 map, but I think the pathfinding should also work in a case like this (maybe this is where I am wrong).

Comparison of three methods

Comparison of three methods (left/pink - centroids, middle/orange - midpoints, right/blue - edges).

Midpoint method failing on long narrow triangles at map edges

Example showing where midpoints method produces undesirable results.

Generally the problem is that the real shortest post-funnel path often goes through part of the graph that due to the representation method is not the shortest path in the graph – creating cases like in the image where for centroid or edge method, the obvious shortest direct path loses because of, in this particular case, a zig-zag chain of triangles.

There are nowadays other solutions to the problem:

  • Theta* which allows jumping ahead in the graph if two neighbors are mutually visible.
  • Polyanya which directly outputs shortest euclidean path on a navigation mesh consisting of convex polygons.
  • And probably many more.

But the thing is – Blizzard supposedly managed to solve the problem using just A*. It was before 2010. And many other RTS games also solved the problem successfully, by which I mean players were satisfied with it.

So my question is: how does StarCraft 2 avoid the big shortcomings of my implementation? What graph representation do you think they picked? Is there something obvious that I am missing that would help me increase quality of my results?

Edit:

Previously I discarded the option to subdivide triangles as it causes problems with funnel – the algorithm treats the given chain of triangles as a corridor with hard walls, which means a random vertex in a middle of triangle can create invisible walls from funnel's POV.

However, I missed a case which is fully viable - subdividing just the outer edges. It breaks down long skinny triangles near the edges and helps in that case.

Fixed midpoint method

Edit 2:

After subdividing the outer edges I noticed I am still able to reproduce the midpoints problem but on a smaller scale. And this is generally the common issue of all methods I tried – every variant of the navigation graph is just an approximation and is not concerned about any later post-processing. Which means there will always be paths which are shorter from A* POV but after postprocessing they appear longer.

I think I might have explored all reasonable ways to make A* work here without 'looking inside'. I guess the algorithm needs to be tailored in some specific way.

I tried the method suggested by @DMGregory with tracking triangle entry points and using that for path calculations but I started running into common infinite loops. Which means that I have either messed up the code (quite likely) or this can't work (also possible).

So anyway the problem remains unsolved for me.

Another issue resurfacing after subdividing corners

\$\endgroup\$
5
  • 3
    \$\begingroup\$ In the early twenty-teens it was common wisdom that long skinny triangles tended to bring pathing problems, so games I worked on at that time would frequently insert extra vertices to limit this — e.g. subdividing the map into a grid, so no triangle edge would be longer than a grid cell diagonal. Is it possible the source geometry the SC2 team was using just had smaller triangles compared to their map/obstacle sizes, limiting the large-scale impact of these artifacts? \$\endgroup\$
    – DMGregory
    Commented May 6 at 12:14
  • 2
    \$\begingroup\$ Another thing you can try is for each A* node in the frontier to keep track of not just the path distance to a triangle, but the entry point on that triangle. When evaluating the distance to the next triangle, find the closest point on the shared edge from the entry point. This greedy optimization ensures we cross each triangle by the shortest sub-path, rather than going out of our way to reach a centroid/midpoint. It's more computation per node expanded though, because now your distances aren't just lookups, but it may perform better than scaling the graph density. \$\endgroup\$
    – DMGregory
    Commented May 6 at 12:27
  • \$\begingroup\$ Looking at the image I found, looks like StarCraft 2 doesn’t do any additional subdivision. However, the edges of the map seems to be jagged, maybe that’s intentional to avoid long triangles. \$\endgroup\$
    – Tchayen
    Commented May 6 at 13:00
  • 1
    \$\begingroup\$ I really like the idea of storing triangle entry points and calculating shortest path to exit a triangle. I will try adjusting my A* implementation and see if that helps. \$\endgroup\$
    – Tchayen
    Commented May 6 at 13:06
  • 1
    \$\begingroup\$ You can also group triangles into convex clusters, treating all perimeter edges of such a convex polygon as reachable from one another. That avoids some of the weird artifacts from skinny triangles, and leads to fewer hops in the paths because you skip processing edges internal to the cluster entirely. \$\endgroup\$
    – DMGregory
    Commented May 6 at 17:28

1 Answer 1

1
\$\begingroup\$

Instead of considering a single point per triangle or edge you could consider multiple points inside the triangle. Using the triangulation to maintain the connectivity graph (every point in a triangle can go to every other point in a neighboring triangle).

This also solves the long skinny triangle issue.

The downside is that the graph to search along becomes bigger. But most of the new connections you'll need to A* through won't result in a shorter path.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .