How to do starcraft pathfinding?

Question

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.

Answer 1

If you have Starcraft 2 installed, open up the map editor and toggle the pathfinding. You will be able to see how the nav mesh is constructed as you place buildings and other obstacles around.

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.

Shouldn't be a problem - Starcraft 1's pathfinding was silly. This blog post by one of the programmers talks about it.

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?

It's about making the AI not dumb more than optimal. Your units end up with zig-zag movement between nodes if you don't apply a bit of smoothing.

When doing path planning, you will have a refinement stage where you look at what nodes your unit needs to walk through to get to their goal, and then you start taking out excess nodes in the middle of the path that we don't need to follow, i.e. we can directly go from node A to node C through B without static collisions, so ignore B entirely.

This ends up straightening out the path.

I'm looking for some gritty detailed explaination and not the generic super high level overviews that are typical in search results.

If you want a solid explanation, this is already covered nicely in books (with working game code, even). So if you have some money to burn, check out Programming Game AI By Example and/or Artificial Intelligence for Games. Both of them discuss these topics in great depth.