Hi,
The map for a Pacman game is a 2D array. How would someone program a similar map for a starcraft 2 game? Do they use octagonal map, instead of a square one?
Do you think they use A* search algorithm?
Thank you.
I’m fairly certain that they use a* with a navmesh to handle their pathfinding. They also use steering behaviors to handle the pathing between the mesh nodes.
Thing is they also have a grid system that handles building placement so I’m not sure if they update the navmesh as buildings are placed or not. The reason I’m not sure is the way the units try to run past the buildings if there are blocking the quickest path (they don’t try to go around, usually).
I’m going to go out on a limb and say they don’t modify the navmesh; instead opting for the steering behavior to handle that portion too.
I think the units that travel up and down cliffs, colossus & reaper, are handled in a different manner and traverse the navmesh not based off edges, but strictly faces.
Edit: grammar
They do NOT use a navmesh. That would make zero sense in a game with 2D gameplay (everything is technically confined to a 2D heightmap after all).
http://www.teamliquid.net/forum/starcraft-2/132171-the-mechanics-of-sc2-part-1
The article has a few dead image links, but it’s still correct. Basically, they use a modified version of pathfinding that helps with flocking. If you remember SC1, you’ll remember how it was impractical to send units on long trips, because after pathfinding around a couple of corners your massive zergling rush would now be a long line of zerglings walking into the enemy base one by one and getting picked off easily. This is due to each zergling pathfinding independently, bumping into each other and then forming a line as they pretty much all have identical paths and need to wait for each other after a couple of corners. SC2 solved this by adding flocking behaviour to the pathfinding, so that the units maintain their “formation” as they follow their paths. This prevents a line of units from forming. How they actually find paths is not really a big deal. The simplest solution, A* on a grid, will be more than good enough for you.
I would like to point out that the thread you posted only talks in-depth about the pathfinding in BW. It talks about the flocking behaviors in SC2 and that’s about it, unless I missed where it explicitly says they use a grid based a* for SC2.
There are at least two other devs/game journalists that seem to think navmesh as well…
http://www.gamedev.net/topic/648438-how-to-do-starcraft-2-pathfinding/
http://www.codeka.com.au/blog/2010/03/pathfinding-in-starcraft-2
In my opinion the fact that they use flocking points to use of a navmesh. Why use a full grid if you’re just going to use a greedy search and not restrict any movement to grid squares?
Also, from what I remember painting out unwalkable areas in the level editor looks more like a navmesh than a grid based system.
I’m not saying that I know for sure, but to me it looks and feels like a navmesh.
Thank you.
Hmm. I guess they could be using a 2D navmesh. Usually navmeshes are used to solving more complicated problems. Most games have simple heightmap based terrain which fits very well with grid-based pathfinding. Navmeshes are mostly useful when solving much more complicated problems, where you could be having multiple layers/floors that overlap, or need to pathfind in 3D environment in general. My intuition tells me that there’s no way SC2 uses it, but I guess it is possible.
Again, what SC2 uses for finding the path from point A to B is really not that important. The overall approach/algorithm is the same; the rest is just changing the data or optimizing performance. Examples: grid vs navmesh, A* vs Dijkstra’s, hierarchical pathfinding, etc. You shouldn’t be aiming to copy SC2, but rather to code the pathfinder that you need. In most cases a simple Dijkstra’s/breadth-first-search is good enough. A* is just an optimization. If you have extremely long paths, hierarchical pathfinding can improve performance a lot.
The actual complexity and problem that SC2 solved in a new way was keeping the units grouped together as they follow their paths. This really has nothing to do with HOW you calculate the path. It’s simply a different AI for following the path while maintaining formation.