While I’ve been working on the pathfinding in War Worlds, I’ve also been looking around at ways other games have been doing it. Check out the video below for an example of what I’d consider state-of-the-art. It’s the pathfinding in the upcoming Starcraft 2:
It’s a long video, but some of the stuff there really blows me away (I especially like right at the end where the zerg swarm over the base, destroying it in seconds)
So how do they do it? Obviously I don’t know, but I can guess.
The feature that makes it look like it does is the flocking behaviour. Now flocking is a fairly well-studied topic, and while Starcraft 2’s implement has some nice features, I don’t think it’s totally revolutionary. The main feature that I like about their flocking is the way that units in a big group like will “stream out” towards the goal in a long line, rather than trying to all stay in formation. Depending on the style of game, you might want them to stay in formation, but for what is basically a swarm of insects, the behaviour in SC2 looks really nice.
The main problem is how do you define the group so that flocking works, but not so that units get stuck. For example, imagine a situation like the one in the diagram below:
If you imagine you select both the red and blue units and click where the green “X” is. You would expect the red units to flock together and the blue units to flock together, but obviously, they would follow different paths.
Now, I don’t know how Starcraft does it, but to me this is a situation where a polygonal navmesh would shine. Basically, you define all units that are on the same polygon in the mesh as being in a single “flock” (and perhaps some additional logic to account for adjacent polygons) and then find a single path for the whole flock. Then the units would use a flocking/path-following algorithm (e.g. something like this) to make it look “natural".
Obviously, the path-finding in War Worlds is extremely basic compared to all of this (I don’t even use navmeshes yet!) but one day…
(Special thanks to this thread on gamedev.net for some of my ideas)