I've been trying to figure out how to implement something like the pathfinding in Starcraft 2. I'm not looking for all the sophisticated features like flocking, queueing, etc. In fact I like how in Starcraft 1 the units would interfere with each other. But I do want a path finder better than that used in Starcraft 1.
From the Google searches I've done the various answers have something to do with A* over a navigation mesh and/or dealing with some kind of "visibility graph". But I've gotten somewhat conflicting or unclear answers on what I should do.
One thing I read about has something to do with doing A* over the vertices of a triangle mesh (the navigation mesh). And then somehow "straightening out the path" which I don't know how to do. But that doesn't guarantee optimality right?
Another question I had is how does the starcraft 2 pathfinding deal with the fact that the units are discs with a finite radius and not points when dealing with corners? And how to deal with dynamic obstacles like idle units or even other moving units.
I'm looking for some gritty detailed explaination and not the generic super high level overviews that are typical in search results.
If it matters I've already looked at Amit’s Notes about Path-Finding. I've heard of but not read Computational Geometry: Algorithms and Applications. And a blog post about a AI navigation presentation at GDC 2011 mentioned that Starcraft 2 uses a constrained delaunay triangulation for a navmesh. Although the blog post mentions Boids steering and "horizon analysis", it doesn't mention exactly how the core pathfinding is done on the navmesh.