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
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 (left/pink – centroids, middle/orange – midpoints, right/blue – 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, fixing remaining known issues with midpoint method which now seems like a clear winner.
